show that for every consistent theory there is a complete consistent theory
Let $mathcal{L}$ be any language of predicate logic, $Sigma_0$ a consistent theory in $mathcal{L}$. Let P be the set of all consistent theories $Sigma supseteq Sigma_0$ in $mathcal{L}$.
With the relation $subseteq$ P becomes partial ordered.
I'm trying to show that
1) every chain in P (i.e., every through $subseteq$ total ordered subset K$subseteq$ P) is limited. (I.e. for every chain $K subseteq P$ there is $Sigma^{ast} in P$ such that for all $Sigma in K$ $Sigma subseteq Sigma^{ast}$ holds.
The suggestion ist to check, if the constructed set $Sigma^{ast}$ really is in P and to not forget that not every chain is orderisomorphic (I hope that's the correct English word for it) to $(mathbb{N}, <)$;
2) if $Sigma in P_{mathcal{L}}$ is maximal (i.e. there's no $Sigma' supseteq Sigma$ in P), then $Sigma$ is complete;
3) conclude with the Lemma of Zorn that for every consistent theory there is a complete consistent theory, which is superset of it.
My problem lies within point 1). Neither do I see intuitively how this holds nor do I have an idea of how to proof it.
3) Will be easy once 1) and 2) are shown, I think.
So I'm looking forward to your ideas for 1) and 2).
first-order-logic predicate-logic proof-theory formal-proofs
asked Nov 24 at 17:47
Studentu
988
add a comment |
Let $mathcal{L}$ be any language of predicate logic, $Sigma_0$ a consistent theory in $mathcal{L}$. Let P be the set of all consistent theories $Sigma supseteq Sigma_0$ in $mathcal{L}$.
With the relation $subseteq$ P becomes partial ordered.
I'm trying to show that
1) every chain in P (i.e., every through $subseteq$ total ordered subset K$subseteq$ P) is limited. (I.e. for every chain $K subseteq P$ there is $Sigma^{ast} in P$ such that for all $Sigma in K$ $Sigma subseteq Sigma^{ast}$ holds.
The suggestion ist to check, if the constructed set $Sigma^{ast}$ really is in P and to not forget that not every chain is orderisomorphic (I hope that's the correct English word for it) to $(mathbb{N}, <)$;
2) if $Sigma in P_{mathcal{L}}$ is maximal (i.e. there's no $Sigma' supseteq Sigma$ in P), then $Sigma$ is complete;
3) conclude with the Lemma of Zorn that for every consistent theory there is a complete consistent theory, which is superset of it.
My problem lies within point 1). Neither do I see intuitively how this holds nor do I have an idea of how to proof it.
3) Will be easy once 1) and 2) are shown, I think.
So I'm looking forward to your ideas for 1) and 2).
first-order-logic predicate-logic proof-theory formal-proofs
asked Nov 24 at 17:47
Studentu
988
add a comment |
Let $mathcal{L}$ be any language of predicate logic, $Sigma_0$ a consistent theory in $mathcal{L}$. Let P be the set of all consistent theories $Sigma supseteq Sigma_0$ in $mathcal{L}$.
With the relation $subseteq$ P becomes partial ordered.
I'm trying to show that
1) every chain in P (i.e., every through $subseteq$ total ordered subset K$subseteq$ P) is limited. (I.e. for every chain $K subseteq P$ there is $Sigma^{ast} in P$ such that for all $Sigma in K$ $Sigma subseteq Sigma^{ast}$ holds.
The suggestion ist to check, if the constructed set $Sigma^{ast}$ really is in P and to not forget that not every chain is orderisomorphic (I hope that's the correct English word for it) to $(mathbb{N}, <)$;
2) if $Sigma in P_{mathcal{L}}$ is maximal (i.e. there's no $Sigma' supseteq Sigma$ in P), then $Sigma$ is complete;
3) conclude with the Lemma of Zorn that for every consistent theory there is a complete consistent theory, which is superset of it.
My problem lies within point 1). Neither do I see intuitively how this holds nor do I have an idea of how to proof it.
3) Will be easy once 1) and 2) are shown, I think.
So I'm looking forward to your ideas for 1) and 2).
first-order-logic predicate-logic proof-theory formal-proofs
asked Nov 24 at 17:47
Studentu
988
Let $mathcal{L}$ be any language of predicate logic, $Sigma_0$ a consistent theory in $mathcal{L}$. Let P be the set of all consistent theories $Sigma supseteq Sigma_0$ in $mathcal{L}$.
With the relation $subseteq$ P becomes partial ordered.
I'm trying to show that
1) every chain in P (i.e., every through $subseteq$ total ordered subset K$subseteq$ P) is limited. (I.e. for every chain $K subseteq P$ there is $Sigma^{ast} in P$ such that for all $Sigma in K$ $Sigma subseteq Sigma^{ast}$ holds.
The suggestion ist to check, if the constructed set $Sigma^{ast}$ really is in P and to not forget that not every chain is orderisomorphic (I hope that's the correct English word for it) to $(mathbb{N}, <)$;
2) if $Sigma in P_{mathcal{L}}$ is maximal (i.e. there's no $Sigma' supseteq Sigma$ in P), then $Sigma$ is complete;
3) conclude with the Lemma of Zorn that for every consistent theory there is a complete consistent theory, which is superset of it.
My problem lies within point 1). Neither do I see intuitively how this holds nor do I have an idea of how to proof it.
3) Will be easy once 1) and 2) are shown, I think.
So I'm looking forward to your ideas for 1) and 2).
first-order-logic predicate-logic proof-theory formal-proofs
first-order-logic predicate-logic proof-theory formal-proofs
asked Nov 24 at 17:47
Studentu
988
asked Nov 24 at 17:47
Studentu
988
edited Nov 24 at 22:19
asked Nov 24 at 17:47
Studentu
988
asked Nov 24 at 17:47
Studentu
988
asked Nov 24 at 17:47
Studentu
988
988
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
For part one, you want to take $Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $Sigma_0.$ That it extends $Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $varphi_1,ldots varphi_nin Sigma^*$. For each $varphi_i,$ choose a $Sigma_iin K $ such that $varphi_iin Sigma_i.$ Then take $Sigma$ to be the maximum of $Sigma_1,ldots, Sigma_n.$ Then $Sigmain K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.
I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.
For 2, show that if $Sigma$ is not complete, then there is a sentence $varphinotin Sigma$ such that $Sigmacup{varphi}$ is consistent.
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
|
show 3 more comments
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%2f3011853%2fshow-that-for-every-consistent-theory-there-is-a-complete-consistent-theory%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
For part one, you want to take $Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $Sigma_0.$ That it extends $Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $varphi_1,ldots varphi_nin Sigma^*$. For each $varphi_i,$ choose a $Sigma_iin K $ such that $varphi_iin Sigma_i.$ Then take $Sigma$ to be the maximum of $Sigma_1,ldots, Sigma_n.$ Then $Sigmain K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.
I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.
For 2, show that if $Sigma$ is not complete, then there is a sentence $varphinotin Sigma$ such that $Sigmacup{varphi}$ is consistent.
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
|
show 3 more comments
For part one, you want to take $Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $Sigma_0.$ That it extends $Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $varphi_1,ldots varphi_nin Sigma^*$. For each $varphi_i,$ choose a $Sigma_iin K $ such that $varphi_iin Sigma_i.$ Then take $Sigma$ to be the maximum of $Sigma_1,ldots, Sigma_n.$ Then $Sigmain K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.
I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.
For 2, show that if $Sigma$ is not complete, then there is a sentence $varphinotin Sigma$ such that $Sigmacup{varphi}$ is consistent.
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
|
show 3 more comments
For part one, you want to take $Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $Sigma_0.$ That it extends $Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $varphi_1,ldots varphi_nin Sigma^*$. For each $varphi_i,$ choose a $Sigma_iin K $ such that $varphi_iin Sigma_i.$ Then take $Sigma$ to be the maximum of $Sigma_1,ldots, Sigma_n.$ Then $Sigmain K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.
I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.
For 2, show that if $Sigma$ is not complete, then there is a sentence $varphinotin Sigma$ such that $Sigmacup{varphi}$ is consistent.
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
For part one, you want to take $Sigma^*$ to be the union of the chain $K$. You need to show it is a consistent theory extending $Sigma_0.$ That it extends $Sigma_0$ is obvious. If it were inconsistent, the inconsistency would come from some finite number of sentences $varphi_1,ldots varphi_nin Sigma^*$. For each $varphi_i,$ choose a $Sigma_iin K $ such that $varphi_iin Sigma_i.$ Then take $Sigma$ to be the maximum of $Sigma_1,ldots, Sigma_n.$ Then $Sigmain K,$ and is inconsistent, contradicting the fact that $K$ only contains consistent sets of statements.
I’m not sure what to make of the suggestion that $K$ is not necessarily order isomorphic to $mathbb N.$ I guess maybe people in the past have written the above proof making a tacit assumption that it is and they want to warn you against that.
For 2, show that if $Sigma$ is not complete, then there is a sentence $varphinotin Sigma$ such that $Sigmacup{varphi}$ is consistent.
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
edited Nov 25 at 6:12
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
answered Nov 24 at 18:27
spaceisdarkgreen
32.3k21753
32.3k21753
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
|
show 3 more comments
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
Thank you! I'd completely forgotten about the trick to take the union! For 2), we assume that $Sigma$ is not complete. So there is $phi$ in $mathcal{L}$ such that it doesn't hold that either $Sigma vdash Phi$ or $Sigma vdash neg phi$. We consider $Sigma':=Sigma cup phi$. We do this with all $psi$ which cause $Sigma$ to not be complete until we have the theory $tilde{Sigma}$. Then $tilde{Sigma}supset Sigma$ and $tilde{Sigma} in P$ in contradiction to the maximality of $Sigma$. But I don't see how to explain the $tilde{Sigma}$ is consistent?
– Studentu
Nov 25 at 4:22
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
3) With the Lemma of Zorn we get that there is at least one maximal element in P. Due to 2), this element is also complete. But I don't get how to explain that 3) follows from this. Intuitively, it is clear to me, but if we take the maximal element $Sigma^{ast}$ for example, it doesn't have to hold that $Sigma_0 in Sigma^{ast}$, because it could be another maximal element which $Sigma_0$ is a subset of.
– Studentu
Nov 25 at 4:23
1
1
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
For 2 you only need to show that if $Sigma nvdash phi$ and $Sigma nvdash lnotphi,$ then either $Sigmacup{phi}$ or $Sigmacup{lnotphi}$ are consistent (actually, both are). This shows that if $Sigmain P$ is incomplete, then it is not maximal in $P,$ which is what you need. For 3, yes it does have to hold that $Sigma_0subseteq Sigma^*$ since all $Sigma in P$ have $Sigma_0subseteqSigma.$
– spaceisdarkgreen
Nov 25 at 6:11
1
1
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
The general theorem you can show it that $Sigmacup {phi}$ is consistent if and only if $Sigma nvdash lnotphi .$ For the direction you need, assume $Sigmacup {phi}$ is inconsistent then show $Sigma vdash lnot phi.$ You only need to use very general facts about the system. For instance by the deduction theorem, if $Sigmacup {phi}vdash psi,$ and $Sigmacup {phi}vdash lnotpsi,$ then $ Sigma vdash phito psi$ and $Sigma vdash phito lnot psi.$ Can you show from there that $Sigma vdash lnotphi$?
– spaceisdarkgreen
Nov 25 at 19:34
1
1
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
@Studentu Some of that is on the right track, but you need $Sigma vdash lnotphi,$ not just $Sigmacup{phi}vdash lnot phi.$ If you have the $bot,$ symbol, you might just do $ Sigmacup{phi}vdashbot,$ and then use the deduction theorem to get $Sigma vdash phito bot.$ How close this is to $Sigmavdash lnot phi$ depends on the system you're using (in some systems it's the same thing by definition).
– spaceisdarkgreen
Nov 25 at 21:16
|
show 3 more comments
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3011853%2fshow-that-for-every-consistent-theory-there-is-a-complete-consistent-theory%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
