Formula Complexity of $models_n$
$begingroup$
I want to show $models_0$ is $Sigma_1$, and $forall n geq 1, models_n$ is $Sigma_n$.
So for the base case, $models_0 ulcorner phi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Delta_0$ and $ exists M (M$ is transitive and $(M , in ) models phi$). So, I have to show that those three conditions can be expressed as $Sigma_1$ formulas. I think the first two be expressed as $Delta_0$ under any reasonable coding, correct? And I'm having trouble with expressing the last condition, particularly with expressing $(M , in ) models phi$ as $Delta_0$ or $Sigma_1$.
Once we have the base case, the inductive step follows pretty easily since $models_n ulcorner exists xphi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Pi_{n-1}$ and $exists a neg models_{n-1} neg phi(a)$. That the first two are expressible as $Sigma_n$ would again follow from a reasonable coding procedure and the last is $Sigma_n$ since we are just prefixing an $exists$ and a $neg$ to a $Sigma_{n-1}$ formula.
Any general advice for approaching formula complexity problems would also be appreciated. Sometimes what we are trying to express as a formula can get fairly ugly formula-wise. It seems like the only strategy here is to memorize at which formula complexity a lot of the fundamental notions are and then to try to reduce the problem at hand to those fundamental notions, right?
logic set-theory
asked Nov 9 '14 at 16:35
David B.David B.
506214
$endgroup$
add a comment |
$begingroup$
I want to show $models_0$ is $Sigma_1$, and $forall n geq 1, models_n$ is $Sigma_n$.
So for the base case, $models_0 ulcorner phi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Delta_0$ and $ exists M (M$ is transitive and $(M , in ) models phi$). So, I have to show that those three conditions can be expressed as $Sigma_1$ formulas. I think the first two be expressed as $Delta_0$ under any reasonable coding, correct? And I'm having trouble with expressing the last condition, particularly with expressing $(M , in ) models phi$ as $Delta_0$ or $Sigma_1$.
Once we have the base case, the inductive step follows pretty easily since $models_n ulcorner exists xphi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Pi_{n-1}$ and $exists a neg models_{n-1} neg phi(a)$. That the first two are expressible as $Sigma_n$ would again follow from a reasonable coding procedure and the last is $Sigma_n$ since we are just prefixing an $exists$ and a $neg$ to a $Sigma_{n-1}$ formula.
Any general advice for approaching formula complexity problems would also be appreciated. Sometimes what we are trying to express as a formula can get fairly ugly formula-wise. It seems like the only strategy here is to memorize at which formula complexity a lot of the fundamental notions are and then to try to reduce the problem at hand to those fundamental notions, right?
logic set-theory
asked Nov 9 '14 at 16:35
David B.David B.
506214
$endgroup$
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
1
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01
add a comment |
$begingroup$
I want to show $models_0$ is $Sigma_1$, and $forall n geq 1, models_n$ is $Sigma_n$.
So for the base case, $models_0 ulcorner phi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Delta_0$ and $ exists M (M$ is transitive and $(M , in ) models phi$). So, I have to show that those three conditions can be expressed as $Sigma_1$ formulas. I think the first two be expressed as $Delta_0$ under any reasonable coding, correct? And I'm having trouble with expressing the last condition, particularly with expressing $(M , in ) models phi$ as $Delta_0$ or $Sigma_1$.
Once we have the base case, the inductive step follows pretty easily since $models_n ulcorner exists xphi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Pi_{n-1}$ and $exists a neg models_{n-1} neg phi(a)$. That the first two are expressible as $Sigma_n$ would again follow from a reasonable coding procedure and the last is $Sigma_n$ since we are just prefixing an $exists$ and a $neg$ to a $Sigma_{n-1}$ formula.
Any general advice for approaching formula complexity problems would also be appreciated. Sometimes what we are trying to express as a formula can get fairly ugly formula-wise. It seems like the only strategy here is to memorize at which formula complexity a lot of the fundamental notions are and then to try to reduce the problem at hand to those fundamental notions, right?
logic set-theory
asked Nov 9 '14 at 16:35
David B.David B.
506214
$endgroup$
I want to show $models_0$ is $Sigma_1$, and $forall n geq 1, models_n$ is $Sigma_n$.
So for the base case, $models_0 ulcorner phi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Delta_0$ and $ exists M (M$ is transitive and $(M , in ) models phi$). So, I have to show that those three conditions can be expressed as $Sigma_1$ formulas. I think the first two be expressed as $Delta_0$ under any reasonable coding, correct? And I'm having trouble with expressing the last condition, particularly with expressing $(M , in ) models phi$ as $Delta_0$ or $Sigma_1$.
Once we have the base case, the inductive step follows pretty easily since $models_n ulcorner exists xphi urcorner$ is true iff $ulcorner phi urcorner in Formulas$, $ulcorner phi urcorner in Pi_{n-1}$ and $exists a neg models_{n-1} neg phi(a)$. That the first two are expressible as $Sigma_n$ would again follow from a reasonable coding procedure and the last is $Sigma_n$ since we are just prefixing an $exists$ and a $neg$ to a $Sigma_{n-1}$ formula.
Any general advice for approaching formula complexity problems would also be appreciated. Sometimes what we are trying to express as a formula can get fairly ugly formula-wise. It seems like the only strategy here is to memorize at which formula complexity a lot of the fundamental notions are and then to try to reduce the problem at hand to those fundamental notions, right?
logic set-theory
logic set-theory
asked Nov 9 '14 at 16:35
David B.David B.
506214
asked Nov 9 '14 at 16:35
David B.David B.
506214
asked Nov 9 '14 at 16:35
David B.David B.
506214
asked Nov 9 '14 at 16:35
David B.David B.
506214
asked Nov 9 '14 at 16:35
David B.David B.
506214
506214
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
1
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01
add a comment |
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
1
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
1
1
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$varphi$ is a formula" is $Delta_1$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $ngeq 1$, the sentence "$varphi$ is $Sigma_n$" is also $Delta_1$, and is sketched in Lemma 9.13. Satisfiability for sets $M$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $Delta_1$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $Form$.
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
$endgroup$
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%2f1013507%2fformula-complexity-of-models-n%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$
I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$varphi$ is a formula" is $Delta_1$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $ngeq 1$, the sentence "$varphi$ is $Sigma_n$" is also $Delta_1$, and is sketched in Lemma 9.13. Satisfiability for sets $M$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $Delta_1$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $Form$.
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
$endgroup$
add a comment |
$begingroup$
I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$varphi$ is a formula" is $Delta_1$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $ngeq 1$, the sentence "$varphi$ is $Sigma_n$" is also $Delta_1$, and is sketched in Lemma 9.13. Satisfiability for sets $M$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $Delta_1$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $Form$.
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
$endgroup$
add a comment |
$begingroup$
I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$varphi$ is a formula" is $Delta_1$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $ngeq 1$, the sentence "$varphi$ is $Sigma_n$" is also $Delta_1$, and is sketched in Lemma 9.13. Satisfiability for sets $M$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $Delta_1$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $Form$.
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
$endgroup$
I highly recommend Chapter I.9 of Devlin's "Constructibility", where many of the subtleties of this are worked out. It takes about 6 pages to show that "$varphi$ is a formula" is $Delta_1$; see Lemma 9.4. For each fixed (meta-mathematical) natural number $ngeq 1$, the sentence "$varphi$ is $Sigma_n$" is also $Delta_1$, and is sketched in Lemma 9.13. Satisfiability for sets $M$ is definitely the most involved part; this is completed in Lemma 9.10 and shown to be $Delta_1$. I think Jech was expecting students to just take these three facts for granted, as he never specifies a fixed definition of $Form$.
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
answered Dec 21 '18 at 0:08
Pace NielsenPace Nielsen
26336
26336
add a comment |
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%2f1013507%2fformula-complexity-of-models-n%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
$begingroup$
What is $models_n$? I mean, I know what $models$ is, but I don't quite understand what the subscript is doing there.
$endgroup$
– Nagase
Nov 12 '14 at 19:57
1
$begingroup$
The definitions are basically what I wrote in the first sentences of the first two main paragraphs. They are introduced on page 186 of Jech's Set Theory.
$endgroup$
– David B.
Nov 12 '14 at 20:01