model theory - completeness of a theory
0
$begingroup$
For an $L$-structure $mathcal{A}$, the $L$-theory of $mathcal{A}$ is the set of $L$-sentences:
$$
mathrm{Th}_L(mathcal A) = {sigma : mathcal A models sigma}
$$
Prove that $mathrm{Th}_L(mathcal A)$ is complete.
Whys is this true? Why can't there be an $L$-sentence such that it is neither true or false?
logic model-theory
asked Dec 8 '18 at 16:20
bofbof
152
$endgroup$
add a comment |
0
$begingroup$
For an $L$-structure $mathcal{A}$, the $L$-theory of $mathcal{A}$ is the set of $L$-sentences:
$$
mathrm{Th}_L(mathcal A) = {sigma : mathcal A models sigma}
$$
Prove that $mathrm{Th}_L(mathcal A)$ is complete.
Whys is this true? Why can't there be an $L$-sentence such that it is neither true or false?
logic model-theory
asked Dec 8 '18 at 16:20
bofbof
152
$endgroup$
add a comment |
0
0
0
$begingroup$
For an $L$-structure $mathcal{A}$, the $L$-theory of $mathcal{A}$ is the set of $L$-sentences:
$$
mathrm{Th}_L(mathcal A) = {sigma : mathcal A models sigma}
$$
Prove that $mathrm{Th}_L(mathcal A)$ is complete.
Whys is this true? Why can't there be an $L$-sentence such that it is neither true or false?
logic model-theory
asked Dec 8 '18 at 16:20
bofbof
152
$endgroup$
For an $L$-structure $mathcal{A}$, the $L$-theory of $mathcal{A}$ is the set of $L$-sentences:
$$
mathrm{Th}_L(mathcal A) = {sigma : mathcal A models sigma}
$$
Prove that $mathrm{Th}_L(mathcal A)$ is complete.
Whys is this true? Why can't there be an $L$-sentence such that it is neither true or false?
logic model-theory
logic model-theory
asked Dec 8 '18 at 16:20
bofbof
152
asked Dec 8 '18 at 16:20
bofbof
152
asked Dec 8 '18 at 16:20
bofbof
152
asked Dec 8 '18 at 16:20
bofbof
152
asked Dec 8 '18 at 16:20
bofbof
152
152
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
2
$begingroup$
Assume there's an $L$-sentence $sigma$ that's neither true nor false. Then we have that $mathcal{A}nvDashsigma$ and $mathcal{A}nvDashnegsigma$. But this is a contradiction since $mathcal{A}vDashsigma$ if and only if $mathcal{A}nvDashnegsigma$, and vice versa, by definition of what a structure is.
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
$endgroup$
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
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
});
}
});
draft saved
draft discarded
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%2f3031303%2fmodel-theory-completeness-of-a-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
2
$begingroup$
Assume there's an $L$-sentence $sigma$ that's neither true nor false. Then we have that $mathcal{A}nvDashsigma$ and $mathcal{A}nvDashnegsigma$. But this is a contradiction since $mathcal{A}vDashsigma$ if and only if $mathcal{A}nvDashnegsigma$, and vice versa, by definition of what a structure is.
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
$endgroup$
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
add a comment |
2
$begingroup$
Assume there's an $L$-sentence $sigma$ that's neither true nor false. Then we have that $mathcal{A}nvDashsigma$ and $mathcal{A}nvDashnegsigma$. But this is a contradiction since $mathcal{A}vDashsigma$ if and only if $mathcal{A}nvDashnegsigma$, and vice versa, by definition of what a structure is.
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
$endgroup$
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
add a comment |
2
2
2
$begingroup$
Assume there's an $L$-sentence $sigma$ that's neither true nor false. Then we have that $mathcal{A}nvDashsigma$ and $mathcal{A}nvDashnegsigma$. But this is a contradiction since $mathcal{A}vDashsigma$ if and only if $mathcal{A}nvDashnegsigma$, and vice versa, by definition of what a structure is.
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
$endgroup$
Assume there's an $L$-sentence $sigma$ that's neither true nor false. Then we have that $mathcal{A}nvDashsigma$ and $mathcal{A}nvDashnegsigma$. But this is a contradiction since $mathcal{A}vDashsigma$ if and only if $mathcal{A}nvDashnegsigma$, and vice versa, by definition of what a structure is.
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
answered Dec 8 '18 at 16:24
quanticboltquanticbolt
769514
769514
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
add a comment |
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
I'm sorry if this is a really basic question but why is it that you can construct such sentence that is neither true nor false under Godel's incompleteness theorem but not here? Thanks!
$endgroup$
– bof
Dec 8 '18 at 16:26
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
$begingroup$
For a detailed explanation, see here. But basically, Godel's incompleteness theorem is not a negation of Godel's completeness theorem. Also, here we are dealing with a structure, not a set of sentences (which is what Godel's incompleteness theorem talks about).
$endgroup$
– quanticbolt
Dec 8 '18 at 16:39
1
1
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof That's an incorrect statement of Godel's incompleteness theorem. There is a distinction between truth in a model/structure (fixing a structure $M$, everything is either true in $M$ or false in $M$) and provability from a theory (= truth in every model of that theory; since a given theory might have many disagreeing models, there are in general independent sentences, and this is what Godel's incompleteness theorem is about).
$endgroup$
– Noah Schweber
Dec 8 '18 at 16:40
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
@bof For any sentence $varphi$ and any structure $A$ the definition of $Amodels lnot varphi$ is that $Anotmodels varphi$. It immediately follows that either $Amodels varphi$ or $Amodels lnot varphi$.
$endgroup$
– Alex Kruckman
Dec 8 '18 at 18:34
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
$begingroup$
thank you everyone
$endgroup$
– bof
Dec 8 '18 at 19:27
add a comment |
draft saved
draft discarded
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.
draft saved
draft discarded
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%2f3031303%2fmodel-theory-completeness-of-a-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
