How to give formal proof in logic?
$begingroup$
I am taking a course on mathematical logic and am struggling to give formal proofs of theorems or claims. Currently doing first order logic. Here, an example:
Claim: $models (exists x)big(A(x)Rightarrow (forall y)(A(y))big)$
where $A$ is an unary predicate. I am asked to prove this. This is how I would reason:
By the rule of propositional logic $PRightarrow Q$ is equivallent to $neg Pvee Q$. So we wish to show that $$models(exists x)big(neg A(x)vee (forall y)(A(y))big)$$
So, assume we have an arbitrary interpretation of language $mathcal{L}={A}$, that is a nonempty set $M$ together with unary predicate $A$.. By Tarski's definition of truth, there is some $min M$ for which is $neg A(m)$ or for all $nin M$ $A(n)$ holds. But this is clearly true (logically valid). Because whenever there is some $min M$ for which $neg A(m)$, then the formula is satisfied. If not, then for all $nin M$ for which $A(n)$, which makes it also satisfied.
Now, I am wondering whether this can be taken as a formal proof of the claim that the formula is logically valid in any interpretation of the language $mathcal{L}={A}$. It seems really trivial, but I am afraid I am using too much of set theory.
Another reasoning could be: In fact, when $A$ is an unary predicate, that means $A$ is a subset of $M$. Now distinguish two cases: 1. $A=M$, then $(forall y)((yin M) Leftrightarrow (yin A))$ in other words $(forall y)(A(y))$. If $Asubsetneq M$ then it is clear there is some $min M$ that is not in $A$, in this case the part $(exists x)(neg A(x))$ is true. Now, this uses the definition of equality between sets and what is a subset.
Another idea: Using a contradiction. Assume this was not logically valid, so there exists some interpretation $mathcal{M}$ and value assignment $e$ for which $mathcal{M}models neg(exists x)big(A(x)Rightarrow (forall y)(A(y))big)$, that is $mathcal{M}models(forall x)(A(x)wedge (exists y)(neg A(y))$, thus for all $m$ $mathcal{M}models A(m)wedge (exists y)(neg A(y))$, by definition again there is some $nin M$ for which $mathcal{M}models A(m)wedge neg A(n)$, this gives $mathcal{M}models A(n)$ (the $n$ must be one of all of the $m$'s) but also $mathcal{M}models neg A(n)$. Which is contradiction by the law of excluded middle, so the statement before was logically valid.
Or just by looking: It is clear that either for all $x$ $A(x)$ holds, or there is some $x$ for which $A(x)$ doesn't hold...
All this seems like a handwaving...
So, what tools/methods/kind of reasoning should I use at most when proving such claims and theorems in logic/model theory? I would be grateful for opinions and/or more examples (sources).
proof-verification logic proof-writing first-order-logic model-theory
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
$endgroup$
add a comment |
$begingroup$
I am taking a course on mathematical logic and am struggling to give formal proofs of theorems or claims. Currently doing first order logic. Here, an example:
Claim: $models (exists x)big(A(x)Rightarrow (forall y)(A(y))big)$
where $A$ is an unary predicate. I am asked to prove this. This is how I would reason:
By the rule of propositional logic $PRightarrow Q$ is equivallent to $neg Pvee Q$. So we wish to show that $$models(exists x)big(neg A(x)vee (forall y)(A(y))big)$$
So, assume we have an arbitrary interpretation of language $mathcal{L}={A}$, that is a nonempty set $M$ together with unary predicate $A$.. By Tarski's definition of truth, there is some $min M$ for which is $neg A(m)$ or for all $nin M$ $A(n)$ holds. But this is clearly true (logically valid). Because whenever there is some $min M$ for which $neg A(m)$, then the formula is satisfied. If not, then for all $nin M$ for which $A(n)$, which makes it also satisfied.
Now, I am wondering whether this can be taken as a formal proof of the claim that the formula is logically valid in any interpretation of the language $mathcal{L}={A}$. It seems really trivial, but I am afraid I am using too much of set theory.
Another reasoning could be: In fact, when $A$ is an unary predicate, that means $A$ is a subset of $M$. Now distinguish two cases: 1. $A=M$, then $(forall y)((yin M) Leftrightarrow (yin A))$ in other words $(forall y)(A(y))$. If $Asubsetneq M$ then it is clear there is some $min M$ that is not in $A$, in this case the part $(exists x)(neg A(x))$ is true. Now, this uses the definition of equality between sets and what is a subset.
Another idea: Using a contradiction. Assume this was not logically valid, so there exists some interpretation $mathcal{M}$ and value assignment $e$ for which $mathcal{M}models neg(exists x)big(A(x)Rightarrow (forall y)(A(y))big)$, that is $mathcal{M}models(forall x)(A(x)wedge (exists y)(neg A(y))$, thus for all $m$ $mathcal{M}models A(m)wedge (exists y)(neg A(y))$, by definition again there is some $nin M$ for which $mathcal{M}models A(m)wedge neg A(n)$, this gives $mathcal{M}models A(n)$ (the $n$ must be one of all of the $m$'s) but also $mathcal{M}models neg A(n)$. Which is contradiction by the law of excluded middle, so the statement before was logically valid.
Or just by looking: It is clear that either for all $x$ $A(x)$ holds, or there is some $x$ for which $A(x)$ doesn't hold...
All this seems like a handwaving...
So, what tools/methods/kind of reasoning should I use at most when proving such claims and theorems in logic/model theory? I would be grateful for opinions and/or more examples (sources).
proof-verification logic proof-writing first-order-logic model-theory
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
$endgroup$
1
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12
add a comment |
$begingroup$
I am taking a course on mathematical logic and am struggling to give formal proofs of theorems or claims. Currently doing first order logic. Here, an example:
Claim: $models (exists x)big(A(x)Rightarrow (forall y)(A(y))big)$
where $A$ is an unary predicate. I am asked to prove this. This is how I would reason:
By the rule of propositional logic $PRightarrow Q$ is equivallent to $neg Pvee Q$. So we wish to show that $$models(exists x)big(neg A(x)vee (forall y)(A(y))big)$$
So, assume we have an arbitrary interpretation of language $mathcal{L}={A}$, that is a nonempty set $M$ together with unary predicate $A$.. By Tarski's definition of truth, there is some $min M$ for which is $neg A(m)$ or for all $nin M$ $A(n)$ holds. But this is clearly true (logically valid). Because whenever there is some $min M$ for which $neg A(m)$, then the formula is satisfied. If not, then for all $nin M$ for which $A(n)$, which makes it also satisfied.
Now, I am wondering whether this can be taken as a formal proof of the claim that the formula is logically valid in any interpretation of the language $mathcal{L}={A}$. It seems really trivial, but I am afraid I am using too much of set theory.
Another reasoning could be: In fact, when $A$ is an unary predicate, that means $A$ is a subset of $M$. Now distinguish two cases: 1. $A=M$, then $(forall y)((yin M) Leftrightarrow (yin A))$ in other words $(forall y)(A(y))$. If $Asubsetneq M$ then it is clear there is some $min M$ that is not in $A$, in this case the part $(exists x)(neg A(x))$ is true. Now, this uses the definition of equality between sets and what is a subset.
Another idea: Using a contradiction. Assume this was not logically valid, so there exists some interpretation $mathcal{M}$ and value assignment $e$ for which $mathcal{M}models neg(exists x)big(A(x)Rightarrow (forall y)(A(y))big)$, that is $mathcal{M}models(forall x)(A(x)wedge (exists y)(neg A(y))$, thus for all $m$ $mathcal{M}models A(m)wedge (exists y)(neg A(y))$, by definition again there is some $nin M$ for which $mathcal{M}models A(m)wedge neg A(n)$, this gives $mathcal{M}models A(n)$ (the $n$ must be one of all of the $m$'s) but also $mathcal{M}models neg A(n)$. Which is contradiction by the law of excluded middle, so the statement before was logically valid.
Or just by looking: It is clear that either for all $x$ $A(x)$ holds, or there is some $x$ for which $A(x)$ doesn't hold...
All this seems like a handwaving...
So, what tools/methods/kind of reasoning should I use at most when proving such claims and theorems in logic/model theory? I would be grateful for opinions and/or more examples (sources).
proof-verification logic proof-writing first-order-logic model-theory
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
$endgroup$
I am taking a course on mathematical logic and am struggling to give formal proofs of theorems or claims. Currently doing first order logic. Here, an example:
Claim: $models (exists x)big(A(x)Rightarrow (forall y)(A(y))big)$
where $A$ is an unary predicate. I am asked to prove this. This is how I would reason:
By the rule of propositional logic $PRightarrow Q$ is equivallent to $neg Pvee Q$. So we wish to show that $$models(exists x)big(neg A(x)vee (forall y)(A(y))big)$$
So, assume we have an arbitrary interpretation of language $mathcal{L}={A}$, that is a nonempty set $M$ together with unary predicate $A$.. By Tarski's definition of truth, there is some $min M$ for which is $neg A(m)$ or for all $nin M$ $A(n)$ holds. But this is clearly true (logically valid). Because whenever there is some $min M$ for which $neg A(m)$, then the formula is satisfied. If not, then for all $nin M$ for which $A(n)$, which makes it also satisfied.
Now, I am wondering whether this can be taken as a formal proof of the claim that the formula is logically valid in any interpretation of the language $mathcal{L}={A}$. It seems really trivial, but I am afraid I am using too much of set theory.
Another reasoning could be: In fact, when $A$ is an unary predicate, that means $A$ is a subset of $M$. Now distinguish two cases: 1. $A=M$, then $(forall y)((yin M) Leftrightarrow (yin A))$ in other words $(forall y)(A(y))$. If $Asubsetneq M$ then it is clear there is some $min M$ that is not in $A$, in this case the part $(exists x)(neg A(x))$ is true. Now, this uses the definition of equality between sets and what is a subset.
Another idea: Using a contradiction. Assume this was not logically valid, so there exists some interpretation $mathcal{M}$ and value assignment $e$ for which $mathcal{M}models neg(exists x)big(A(x)Rightarrow (forall y)(A(y))big)$, that is $mathcal{M}models(forall x)(A(x)wedge (exists y)(neg A(y))$, thus for all $m$ $mathcal{M}models A(m)wedge (exists y)(neg A(y))$, by definition again there is some $nin M$ for which $mathcal{M}models A(m)wedge neg A(n)$, this gives $mathcal{M}models A(n)$ (the $n$ must be one of all of the $m$'s) but also $mathcal{M}models neg A(n)$. Which is contradiction by the law of excluded middle, so the statement before was logically valid.
Or just by looking: It is clear that either for all $x$ $A(x)$ holds, or there is some $x$ for which $A(x)$ doesn't hold...
All this seems like a handwaving...
So, what tools/methods/kind of reasoning should I use at most when proving such claims and theorems in logic/model theory? I would be grateful for opinions and/or more examples (sources).
proof-verification logic proof-writing first-order-logic model-theory
proof-verification logic proof-writing first-order-logic model-theory
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
edited Dec 27 '18 at 13:24
Michal Dvořák
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
asked Dec 27 '18 at 12:42
Michal DvořákMichal Dvořák
1,007416
1,007416
1
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12
add a comment |
1
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12
1
1
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your proof is correct. You used the mathematical definitions of all the terms involved, like "valid", "interpretation", and "true in an interpretation" and came up with a rigorous argument that the statement was in fact valid according to those definitions.
People often are under the mistaken impression that just cause we're studying logic, we need to stop being mathematicians and turn into C++ compilers. (Mathematical) logic is a branch of mathematics like any other, where we argue informally$^*$ but rigorously about mathematical constructions. It's just that in the case of logic, our arguments are often about formal proofs, which are themselves mathematical constructions. However, in a certain sense, the whole point of semantics and model theory is to eschew formal proofs and to instead think about sentences in their 'plain meaning' within mathematical structures they might talk about.
Semantics do require stronger philosophical precepts than syntactical proofs (as you allude to, there is some set theory involved). You could also construct a formal proof of your statement in some proof calculus for first order logic, and such a construction would only involve finitary ideas. If we do this we would say that $vdash (exists x)big(neg A(x)vee (forall y)(A(y))big)$ (with a $vdash$ meaning "provable (in some given deductive system)" rather than a $models$ meaning "valid").
Remarkably, the standard proof systems for first order logic are complete and sound, i.e. they can prove a sentence if and only if it is semantically valid, i.e. $vdash phiiff modelsphi$. While formal proofs are less of a philosophical burden, as a practical matter it is generally harder to construct formal proofs than to make semantic arguments. But formal proofs are very important philosophically, especially if you're worried about foundational matters. They are also interesting objects of study in their own right. (And the notion that “true in all models” and “effectively provable in a formal system” are equivalent is particular to first order logic, anyway.)
$^*$Here we might have a clash of terminology between the way you’re using the term "formal" vs the way logicians typically use the term. To a logician, a formal proof of a logical sentence is a mathematical object constructed according to some formal mathematical rules for proof construction. A rigorous natural language argument that a certain mathematical statement is true is an informal proof, regardless of how water-tight and well-explained the reasoning is. (Although you will still hear logicians occasionally use 'formal' to mean 'careful / detailed / rigorous'). Formal proofs are meant as models of well-reasoned arguments, and of course the more careful / detailed / rigorous - ly an informal proof is phrased, the easier it is to imagine it being translated into a formal proof in some suitable system.
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
$endgroup$
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053892%2fhow-to-give-formal-proof-in-logic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your proof is correct. You used the mathematical definitions of all the terms involved, like "valid", "interpretation", and "true in an interpretation" and came up with a rigorous argument that the statement was in fact valid according to those definitions.
People often are under the mistaken impression that just cause we're studying logic, we need to stop being mathematicians and turn into C++ compilers. (Mathematical) logic is a branch of mathematics like any other, where we argue informally$^*$ but rigorously about mathematical constructions. It's just that in the case of logic, our arguments are often about formal proofs, which are themselves mathematical constructions. However, in a certain sense, the whole point of semantics and model theory is to eschew formal proofs and to instead think about sentences in their 'plain meaning' within mathematical structures they might talk about.
Semantics do require stronger philosophical precepts than syntactical proofs (as you allude to, there is some set theory involved). You could also construct a formal proof of your statement in some proof calculus for first order logic, and such a construction would only involve finitary ideas. If we do this we would say that $vdash (exists x)big(neg A(x)vee (forall y)(A(y))big)$ (with a $vdash$ meaning "provable (in some given deductive system)" rather than a $models$ meaning "valid").
Remarkably, the standard proof systems for first order logic are complete and sound, i.e. they can prove a sentence if and only if it is semantically valid, i.e. $vdash phiiff modelsphi$. While formal proofs are less of a philosophical burden, as a practical matter it is generally harder to construct formal proofs than to make semantic arguments. But formal proofs are very important philosophically, especially if you're worried about foundational matters. They are also interesting objects of study in their own right. (And the notion that “true in all models” and “effectively provable in a formal system” are equivalent is particular to first order logic, anyway.)
$^*$Here we might have a clash of terminology between the way you’re using the term "formal" vs the way logicians typically use the term. To a logician, a formal proof of a logical sentence is a mathematical object constructed according to some formal mathematical rules for proof construction. A rigorous natural language argument that a certain mathematical statement is true is an informal proof, regardless of how water-tight and well-explained the reasoning is. (Although you will still hear logicians occasionally use 'formal' to mean 'careful / detailed / rigorous'). Formal proofs are meant as models of well-reasoned arguments, and of course the more careful / detailed / rigorous - ly an informal proof is phrased, the easier it is to imagine it being translated into a formal proof in some suitable system.
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
$endgroup$
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
add a comment |
$begingroup$
Your proof is correct. You used the mathematical definitions of all the terms involved, like "valid", "interpretation", and "true in an interpretation" and came up with a rigorous argument that the statement was in fact valid according to those definitions.
People often are under the mistaken impression that just cause we're studying logic, we need to stop being mathematicians and turn into C++ compilers. (Mathematical) logic is a branch of mathematics like any other, where we argue informally$^*$ but rigorously about mathematical constructions. It's just that in the case of logic, our arguments are often about formal proofs, which are themselves mathematical constructions. However, in a certain sense, the whole point of semantics and model theory is to eschew formal proofs and to instead think about sentences in their 'plain meaning' within mathematical structures they might talk about.
Semantics do require stronger philosophical precepts than syntactical proofs (as you allude to, there is some set theory involved). You could also construct a formal proof of your statement in some proof calculus for first order logic, and such a construction would only involve finitary ideas. If we do this we would say that $vdash (exists x)big(neg A(x)vee (forall y)(A(y))big)$ (with a $vdash$ meaning "provable (in some given deductive system)" rather than a $models$ meaning "valid").
Remarkably, the standard proof systems for first order logic are complete and sound, i.e. they can prove a sentence if and only if it is semantically valid, i.e. $vdash phiiff modelsphi$. While formal proofs are less of a philosophical burden, as a practical matter it is generally harder to construct formal proofs than to make semantic arguments. But formal proofs are very important philosophically, especially if you're worried about foundational matters. They are also interesting objects of study in their own right. (And the notion that “true in all models” and “effectively provable in a formal system” are equivalent is particular to first order logic, anyway.)
$^*$Here we might have a clash of terminology between the way you’re using the term "formal" vs the way logicians typically use the term. To a logician, a formal proof of a logical sentence is a mathematical object constructed according to some formal mathematical rules for proof construction. A rigorous natural language argument that a certain mathematical statement is true is an informal proof, regardless of how water-tight and well-explained the reasoning is. (Although you will still hear logicians occasionally use 'formal' to mean 'careful / detailed / rigorous'). Formal proofs are meant as models of well-reasoned arguments, and of course the more careful / detailed / rigorous - ly an informal proof is phrased, the easier it is to imagine it being translated into a formal proof in some suitable system.
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
$endgroup$
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
add a comment |
$begingroup$
Your proof is correct. You used the mathematical definitions of all the terms involved, like "valid", "interpretation", and "true in an interpretation" and came up with a rigorous argument that the statement was in fact valid according to those definitions.
People often are under the mistaken impression that just cause we're studying logic, we need to stop being mathematicians and turn into C++ compilers. (Mathematical) logic is a branch of mathematics like any other, where we argue informally$^*$ but rigorously about mathematical constructions. It's just that in the case of logic, our arguments are often about formal proofs, which are themselves mathematical constructions. However, in a certain sense, the whole point of semantics and model theory is to eschew formal proofs and to instead think about sentences in their 'plain meaning' within mathematical structures they might talk about.
Semantics do require stronger philosophical precepts than syntactical proofs (as you allude to, there is some set theory involved). You could also construct a formal proof of your statement in some proof calculus for first order logic, and such a construction would only involve finitary ideas. If we do this we would say that $vdash (exists x)big(neg A(x)vee (forall y)(A(y))big)$ (with a $vdash$ meaning "provable (in some given deductive system)" rather than a $models$ meaning "valid").
Remarkably, the standard proof systems for first order logic are complete and sound, i.e. they can prove a sentence if and only if it is semantically valid, i.e. $vdash phiiff modelsphi$. While formal proofs are less of a philosophical burden, as a practical matter it is generally harder to construct formal proofs than to make semantic arguments. But formal proofs are very important philosophically, especially if you're worried about foundational matters. They are also interesting objects of study in their own right. (And the notion that “true in all models” and “effectively provable in a formal system” are equivalent is particular to first order logic, anyway.)
$^*$Here we might have a clash of terminology between the way you’re using the term "formal" vs the way logicians typically use the term. To a logician, a formal proof of a logical sentence is a mathematical object constructed according to some formal mathematical rules for proof construction. A rigorous natural language argument that a certain mathematical statement is true is an informal proof, regardless of how water-tight and well-explained the reasoning is. (Although you will still hear logicians occasionally use 'formal' to mean 'careful / detailed / rigorous'). Formal proofs are meant as models of well-reasoned arguments, and of course the more careful / detailed / rigorous - ly an informal proof is phrased, the easier it is to imagine it being translated into a formal proof in some suitable system.
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
$endgroup$
Your proof is correct. You used the mathematical definitions of all the terms involved, like "valid", "interpretation", and "true in an interpretation" and came up with a rigorous argument that the statement was in fact valid according to those definitions.
People often are under the mistaken impression that just cause we're studying logic, we need to stop being mathematicians and turn into C++ compilers. (Mathematical) logic is a branch of mathematics like any other, where we argue informally$^*$ but rigorously about mathematical constructions. It's just that in the case of logic, our arguments are often about formal proofs, which are themselves mathematical constructions. However, in a certain sense, the whole point of semantics and model theory is to eschew formal proofs and to instead think about sentences in their 'plain meaning' within mathematical structures they might talk about.
Semantics do require stronger philosophical precepts than syntactical proofs (as you allude to, there is some set theory involved). You could also construct a formal proof of your statement in some proof calculus for first order logic, and such a construction would only involve finitary ideas. If we do this we would say that $vdash (exists x)big(neg A(x)vee (forall y)(A(y))big)$ (with a $vdash$ meaning "provable (in some given deductive system)" rather than a $models$ meaning "valid").
Remarkably, the standard proof systems for first order logic are complete and sound, i.e. they can prove a sentence if and only if it is semantically valid, i.e. $vdash phiiff modelsphi$. While formal proofs are less of a philosophical burden, as a practical matter it is generally harder to construct formal proofs than to make semantic arguments. But formal proofs are very important philosophically, especially if you're worried about foundational matters. They are also interesting objects of study in their own right. (And the notion that “true in all models” and “effectively provable in a formal system” are equivalent is particular to first order logic, anyway.)
$^*$Here we might have a clash of terminology between the way you’re using the term "formal" vs the way logicians typically use the term. To a logician, a formal proof of a logical sentence is a mathematical object constructed according to some formal mathematical rules for proof construction. A rigorous natural language argument that a certain mathematical statement is true is an informal proof, regardless of how water-tight and well-explained the reasoning is. (Although you will still hear logicians occasionally use 'formal' to mean 'careful / detailed / rigorous'). Formal proofs are meant as models of well-reasoned arguments, and of course the more careful / detailed / rigorous - ly an informal proof is phrased, the easier it is to imagine it being translated into a formal proof in some suitable system.
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
edited Dec 28 '18 at 3:45
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
answered Dec 27 '18 at 19:24
spaceisdarkgreenspaceisdarkgreen
33.5k21753
33.5k21753
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
add a comment |
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
Thanks for nice explanation. True, I quite mixed up the terms. In my case, I am not actually looking for the formal proof as a sequence of formulas beginning from axioms and applying interference rules etc. I was just wondering, if I can be more rigorous or if there is something more behind my reasoning. All the way throughout logic and these definitions of truth seem really circular to me. Say $mathcal{M}models forall xvarphi [e]$ if for any $min M$ $mathcal{M}models varphi[e(x/m)]$....
$endgroup$
– Michal Dvořák
Dec 28 '18 at 0:22
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
@Michal Well, your argument was rigorous enough for me. I think you’ll find if you think about it long enough is that it is not circular at all. What it is is obvious. Tarski’s famous phrase was “‘Snow is white’ is true if and only if snow is white.” How would you assess the meaning of the sentence $exists x(x^2=2)$? First you’d ask what the sentence is supposed to be about. Say it’s the real numbers. Then you’d assess whether there is some real number that squares to $2.$ It’s a very simple process that can be afforded an obvious mathematical description.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:02
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
Think about it this way: you are taking a meaningless sequence of symbols and giving them a meaning (by interpreting them in a structure). $exists xphi(x)$ should mean no more and no less than “there is a $a$ in the domain such that $phi(x/a)$ is true.” First order logic is a language we associate naturally with making statements about structures with definite truth values.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:08
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
However the simplicity in this special case (which is generally the first and perhaps only kind of semantics people learn other than truth tables) is misleading. There are many ways to attach mathematical objects to sentences other than just a binary true or false (even within the confines of classical first order logic) and many other different types of logic that require more mathematically sophisticated types of semantics to study.
$endgroup$
– spaceisdarkgreen
Dec 28 '18 at 1:22
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
$begingroup$
Thanks for your words, I think I have better idea about it now =)
$endgroup$
– Michal Dvořák
Dec 28 '18 at 4:31
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3053892%2fhow-to-give-formal-proof-in-logic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
The first proof is correct and very easy to follow; thus, IMO, is good. You can "merge" 1 and 2 avoiding the propositional transromation and consider the two cases directly in 1 : either (i) all $m in M$ are $A$s (in which case the conditional has True consequent and is True), or there is some $m_0 in M$ that is not $A$ (in which case the conditional is False $to$ False and thsu True for it).
$endgroup$
– Mauro ALLEGRANZA
Dec 27 '18 at 13:12