Mixing
Doubts about Goedel Completeness Theorem
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
My book (Mendelson) states this theorem the following way:
(1) A logically valid formula of a first order theory is a theorem.
On Wikipedia the statement is a little more general:
(2) For any first-order theory T with a well-orderable language, and any sentence s in the language of the theory, there is a formal proof of s in T if and only if s is satisfied by every model of T.
Now “well-orderable language†is implicit in (1), and the “only if†part is fairly obvious. My doubt is about the hypothesis of “validity†used in (1) which is stronger than “true in any model†used in (2).
Because you can have an interpretation of a 1st order language which satisfies all the logic axioms, but doesn’t satisfy proper axioms, so isn’t a model of the theory. Basically valid means true under any interpretation, and there are more interpretations than models.
Am I understanding this right? Is the stronger hypothesis of (1) strictly required? Or it is also possible to prove the theorem:
(1’) A formula true in any model of a first order theory is a theorem.
logic first-order-logic predicate-logic proof-theory formal-proofs
edited Aug 6 at 16:21
DanielV
17.4k42651
asked Aug 6 at 14:50
Markus Steiner
354
add a comment |Â
up vote
2
down vote
favorite
My book (Mendelson) states this theorem the following way:
(1) A logically valid formula of a first order theory is a theorem.
On Wikipedia the statement is a little more general:
(2) For any first-order theory T with a well-orderable language, and any sentence s in the language of the theory, there is a formal proof of s in T if and only if s is satisfied by every model of T.
Now “well-orderable language†is implicit in (1), and the “only if†part is fairly obvious. My doubt is about the hypothesis of “validity†used in (1) which is stronger than “true in any model†used in (2).
Because you can have an interpretation of a 1st order language which satisfies all the logic axioms, but doesn’t satisfy proper axioms, so isn’t a model of the theory. Basically valid means true under any interpretation, and there are more interpretations than models.
Am I understanding this right? Is the stronger hypothesis of (1) strictly required? Or it is also possible to prove the theorem:
(1’) A formula true in any model of a first order theory is a theorem.
logic first-order-logic predicate-logic proof-theory formal-proofs
edited Aug 6 at 16:21
DanielV
17.4k42651
asked Aug 6 at 14:50
Markus Steiner
354
Which book are you reading?
– user 170039
Aug 6 at 14:56
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
My book (Mendelson) states this theorem the following way:
(1) A logically valid formula of a first order theory is a theorem.
On Wikipedia the statement is a little more general:
(2) For any first-order theory T with a well-orderable language, and any sentence s in the language of the theory, there is a formal proof of s in T if and only if s is satisfied by every model of T.
Now “well-orderable language†is implicit in (1), and the “only if†part is fairly obvious. My doubt is about the hypothesis of “validity†used in (1) which is stronger than “true in any model†used in (2).
Because you can have an interpretation of a 1st order language which satisfies all the logic axioms, but doesn’t satisfy proper axioms, so isn’t a model of the theory. Basically valid means true under any interpretation, and there are more interpretations than models.
Am I understanding this right? Is the stronger hypothesis of (1) strictly required? Or it is also possible to prove the theorem:
(1’) A formula true in any model of a first order theory is a theorem.
logic first-order-logic predicate-logic proof-theory formal-proofs
edited Aug 6 at 16:21
DanielV
17.4k42651
asked Aug 6 at 14:50
Markus Steiner
354
My book (Mendelson) states this theorem the following way:
(1) A logically valid formula of a first order theory is a theorem.
On Wikipedia the statement is a little more general:
(2) For any first-order theory T with a well-orderable language, and any sentence s in the language of the theory, there is a formal proof of s in T if and only if s is satisfied by every model of T.
Now “well-orderable language†is implicit in (1), and the “only if†part is fairly obvious. My doubt is about the hypothesis of “validity†used in (1) which is stronger than “true in any model†used in (2).
Because you can have an interpretation of a 1st order language which satisfies all the logic axioms, but doesn’t satisfy proper axioms, so isn’t a model of the theory. Basically valid means true under any interpretation, and there are more interpretations than models.
Am I understanding this right? Is the stronger hypothesis of (1) strictly required? Or it is also possible to prove the theorem:
(1’) A formula true in any model of a first order theory is a theorem.
logic first-order-logic predicate-logic proof-theory formal-proofs
edited Aug 6 at 16:21
DanielV
17.4k42651
asked Aug 6 at 14:50
Markus Steiner
354
edited Aug 6 at 16:21
DanielV
17.4k42651
edited Aug 6 at 16:21
DanielV
17.4k42651
edited Aug 6 at 16:21
DanielV
17.4k42651
17.4k42651
asked Aug 6 at 14:50
Markus Steiner
354
asked Aug 6 at 14:50
Markus Steiner
354
asked Aug 6 at 14:50
Markus Steiner
354
354
Which book are you reading?
– user 170039
Aug 6 at 14:56
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03
add a comment |Â
Which book are you reading?
– user 170039
Aug 6 at 14:56
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03
Which book are you reading?
– user 170039
Aug 6 at 14:56
Which book are you reading?
– user 170039
Aug 6 at 14:56
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem
Every validity is provable from the empty theory
implies the seemingly-stronger completeness theorem
For every theory $T$ and every sentence $varphi$ true in every model of $T$, we have $Tvdashvarphi$,
or in symbols why "$emptysetmodelsvarphiimpliesemptysetvdashvarphi$" implies "For all $T$, $Tmodelsvarphiimplies Tvdashvarphi$."
You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:
First, we handle the case where $T$ is finite. If $varphi$ is a formula of $T$ then $varphiwedgepsi$ is a validity (where $psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $emptysetvdashvarphiwedgepsi$; this in turn gives $psivdashvarphi$, and that gives $Tvdash varphi$ since we have $Tvdashpsi$.
Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $varphi$ is true in every model of $T$, then there is some finite subtheory $T_0subseteq T$ such that $varphi$ is true in every model of $T_0$. (HINT: note that $Tcupnegvarphi$ is unsatisfiable ...) Hence $T_0vdashvarphi$, and a fortiori $Tvdashvarphi$.
However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.
answered Aug 6 at 17:46
Noah Schweber
111k9140264
add a comment |Â
up vote
-1
down vote
You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.
answered Aug 6 at 17:44
PMar
1
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem
Every validity is provable from the empty theory
implies the seemingly-stronger completeness theorem
For every theory $T$ and every sentence $varphi$ true in every model of $T$, we have $Tvdashvarphi$,
or in symbols why "$emptysetmodelsvarphiimpliesemptysetvdashvarphi$" implies "For all $T$, $Tmodelsvarphiimplies Tvdashvarphi$."
You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:
First, we handle the case where $T$ is finite. If $varphi$ is a formula of $T$ then $varphiwedgepsi$ is a validity (where $psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $emptysetvdashvarphiwedgepsi$; this in turn gives $psivdashvarphi$, and that gives $Tvdash varphi$ since we have $Tvdashpsi$.
Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $varphi$ is true in every model of $T$, then there is some finite subtheory $T_0subseteq T$ such that $varphi$ is true in every model of $T_0$. (HINT: note that $Tcupnegvarphi$ is unsatisfiable ...) Hence $T_0vdashvarphi$, and a fortiori $Tvdashvarphi$.
However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.
answered Aug 6 at 17:46
Noah Schweber
111k9140264
add a comment |Â
up vote
3
down vote
accepted
Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem
Every validity is provable from the empty theory
implies the seemingly-stronger completeness theorem
For every theory $T$ and every sentence $varphi$ true in every model of $T$, we have $Tvdashvarphi$,
or in symbols why "$emptysetmodelsvarphiimpliesemptysetvdashvarphi$" implies "For all $T$, $Tmodelsvarphiimplies Tvdashvarphi$."
You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:
First, we handle the case where $T$ is finite. If $varphi$ is a formula of $T$ then $varphiwedgepsi$ is a validity (where $psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $emptysetvdashvarphiwedgepsi$; this in turn gives $psivdashvarphi$, and that gives $Tvdash varphi$ since we have $Tvdashpsi$.
Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $varphi$ is true in every model of $T$, then there is some finite subtheory $T_0subseteq T$ such that $varphi$ is true in every model of $T_0$. (HINT: note that $Tcupnegvarphi$ is unsatisfiable ...) Hence $T_0vdashvarphi$, and a fortiori $Tvdashvarphi$.
However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.
answered Aug 6 at 17:46
Noah Schweber
111k9140264
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem
Every validity is provable from the empty theory
implies the seemingly-stronger completeness theorem
For every theory $T$ and every sentence $varphi$ true in every model of $T$, we have $Tvdashvarphi$,
or in symbols why "$emptysetmodelsvarphiimpliesemptysetvdashvarphi$" implies "For all $T$, $Tmodelsvarphiimplies Tvdashvarphi$."
You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:
First, we handle the case where $T$ is finite. If $varphi$ is a formula of $T$ then $varphiwedgepsi$ is a validity (where $psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $emptysetvdashvarphiwedgepsi$; this in turn gives $psivdashvarphi$, and that gives $Tvdash varphi$ since we have $Tvdashpsi$.
Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $varphi$ is true in every model of $T$, then there is some finite subtheory $T_0subseteq T$ such that $varphi$ is true in every model of $T_0$. (HINT: note that $Tcupnegvarphi$ is unsatisfiable ...) Hence $T_0vdashvarphi$, and a fortiori $Tvdashvarphi$.
However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.
answered Aug 6 at 17:46
Noah Schweber
111k9140264
Rephrasing your question a bit more clearly, you're asking why the seemingly-weaker completeness theorem
Every validity is provable from the empty theory
implies the seemingly-stronger completeness theorem
For every theory $T$ and every sentence $varphi$ true in every model of $T$, we have $Tvdashvarphi$,
or in symbols why "$emptysetmodelsvarphiimpliesemptysetvdashvarphi$" implies "For all $T$, $Tmodelsvarphiimplies Tvdashvarphi$."
You are right to be suspicious: on the face of it you cannot immediately deduce the stronger version from the weaker version. However, they are nonetheless equivalent:
First, we handle the case where $T$ is finite. If $varphi$ is a formula of $T$ then $varphiwedgepsi$ is a validity (where $psi$ is the conjunction of the axioms in $T$), hence by the weak version we have $emptysetvdashvarphiwedgepsi$; this in turn gives $psivdashvarphi$, and that gives $Tvdash varphi$ since we have $Tvdashpsi$.
Next, we handle the case where $T$ is infinite. Here we cannot "put all of $T$ into one sentence." However, the compactness theorem fixes things: if $varphi$ is true in every model of $T$, then there is some finite subtheory $T_0subseteq T$ such that $varphi$ is true in every model of $T_0$. (HINT: note that $Tcupnegvarphi$ is unsatisfiable ...) Hence $T_0vdashvarphi$, and a fortiori $Tvdashvarphi$.
However, this isn't really necessary: the proof of the seemingly-stronger version of completeness is basically the same as the proof of the seemingly-weaker version.
answered Aug 6 at 17:46
Noah Schweber
111k9140264
edited Aug 6 at 17:52
answered Aug 6 at 17:46
Noah Schweber
111k9140264
answered Aug 6 at 17:46
Noah Schweber
111k9140264
answered Aug 6 at 17:46
Noah Schweber
111k9140264
111k9140264
add a comment |Â
add a comment |Â
up vote
-1
down vote
You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.
answered Aug 6 at 17:44
PMar
1
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
add a comment |Â
up vote
-1
down vote
You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.
answered Aug 6 at 17:44
PMar
1
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
add a comment |Â
up vote
-1
down vote
up vote
-1
down vote
You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.
answered Aug 6 at 17:44
PMar
1
You are confused. A first-order language includes both the logic axioms and the proper axioms; it is not defined by the logic axioms alone. So an 'interpretation' which satisfies the logic axioms but not the proper axioms simply isn't an interpretation of that language, period. An interpretation is a mapping between the 'concepts' (i.e predicates, functions, constant terms, etc) of the language and corresponding objects in the model - ALL of them. In that sense, 'interpretation' and 'model' are synonymous terms.
answered Aug 6 at 17:44
PMar
1
answered Aug 6 at 17:44
PMar
1
answered Aug 6 at 17:44
PMar
1
answered Aug 6 at 17:44
PMar
1
1
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
add a comment |Â
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
This isn't the OP's confusion. They're asking why "Every validity is provable from the empty theory" implies "Every sentence true in every model of $T$ is provable from $T$," and this isn't quite trivial since $T$ might be an infinite theory.
– Noah Schweber
Aug 6 at 17:47
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873942%2fdoubts-about-goedel-completeness-theorem%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Which book are you reading?
– user 170039
Aug 6 at 14:56
"My book states ..." You are asking a question about a certain book, but you do not identify the book? How come? If the competeness theorem is badly stated in your book, that could be of interest to other people, who might be considering buying that book.
– bof
Aug 6 at 14:57
@bolf I added the reference to book, the theorem is presented as corollary to Skolem theorem, and is not called "Goedel theorem" by the way.
– Markus Steiner
Aug 6 at 15:03