Mixing
Where is the theorem related to the construction of countable admissible ordinals by Turing machines with...
$begingroup$
Wikipedia contains the following information in the article "Admissible ordinal":
By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles. [Reference: Friedman, Sy D. (1985), "Fine structure theory and its applications"]
I have found the referenced paper, but I cannot seem to find any reference to this theorem there.
Question: where can I find this theorem? What is its name (or identifier)?
logic reference-request ordinals turing-machines oracles
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
$endgroup$
add a comment |
$begingroup$
Wikipedia contains the following information in the article "Admissible ordinal":
By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles. [Reference: Friedman, Sy D. (1985), "Fine structure theory and its applications"]
I have found the referenced paper, but I cannot seem to find any reference to this theorem there.
Question: where can I find this theorem? What is its name (or identifier)?
logic reference-request ordinals turing-machines oracles
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
$endgroup$
add a comment |
$begingroup$
Wikipedia contains the following information in the article "Admissible ordinal":
By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles. [Reference: Friedman, Sy D. (1985), "Fine structure theory and its applications"]
I have found the referenced paper, but I cannot seem to find any reference to this theorem there.
Question: where can I find this theorem? What is its name (or identifier)?
logic reference-request ordinals turing-machines oracles
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
$endgroup$
Wikipedia contains the following information in the article "Admissible ordinal":
By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles. [Reference: Friedman, Sy D. (1985), "Fine structure theory and its applications"]
I have found the referenced paper, but I cannot seem to find any reference to this theorem there.
Question: where can I find this theorem? What is its name (or identifier)?
logic reference-request ordinals turing-machines oracles
logic reference-request ordinals turing-machines oracles
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
edited Jan 31 at 8:33
lyrically wicked
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
asked Jan 31 at 6:13
lyrically wickedlyrically wicked
20818
20818
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.
The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.
A couple quick remarks about the result:
The "computability-to-admissibility" half, that $omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $omega_1^{CK}$ is admissible: you prove that $L_{omega_1^r}[r]models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{Mcap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $omega_1^{CK}$ of some real: namely, if $beta$ is admissible and $alpha$ is the next admissible above $beta$, let $G$ be $Col(omega,beta)$-generic over $L_alpha$. $G$ essentially is an $omega$-copy of $beta$, so trivially $omega_1^G>beta$; but $Col(omega,beta)in L_alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $omega_1^Glealpha$. This means $omega_1^G=alpha$ since $omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $omega_1^{CK}$s.
It's also worth noting that for $alpha$ admissible, we may indeed need to step outside of $L_alpha$ to find a real whose $omega_1^{CK}$ is $alpha$. In particular, if there is some $rin L_alpha$ with $omega_1^r=alpha$, then $L_alpha$ will be locally countable (= $L_alphamodels$ "every set is countable"). But plenty of countable admissible $alpha$s don't give rise to locally countable levels of $L$! In particular, if $alpha$ is an admissible limit of admissibles (= "recursively inaccessible") then every real in $L_alpha$ is contained in some admissible $L_beta$ with $beta<alpha$. But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $alpha=$ the image of $omega_1$ under the Mostowski collapse of a countable $Mprec H_{omega_2}$).
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
$endgroup$
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
|
show 7 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%2f3094574%2fwhere-is-the-theorem-related-to-the-construction-of-countable-admissible-ordinal%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$
Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.
The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.
A couple quick remarks about the result:
The "computability-to-admissibility" half, that $omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $omega_1^{CK}$ is admissible: you prove that $L_{omega_1^r}[r]models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{Mcap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $omega_1^{CK}$ of some real: namely, if $beta$ is admissible and $alpha$ is the next admissible above $beta$, let $G$ be $Col(omega,beta)$-generic over $L_alpha$. $G$ essentially is an $omega$-copy of $beta$, so trivially $omega_1^G>beta$; but $Col(omega,beta)in L_alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $omega_1^Glealpha$. This means $omega_1^G=alpha$ since $omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $omega_1^{CK}$s.
It's also worth noting that for $alpha$ admissible, we may indeed need to step outside of $L_alpha$ to find a real whose $omega_1^{CK}$ is $alpha$. In particular, if there is some $rin L_alpha$ with $omega_1^r=alpha$, then $L_alpha$ will be locally countable (= $L_alphamodels$ "every set is countable"). But plenty of countable admissible $alpha$s don't give rise to locally countable levels of $L$! In particular, if $alpha$ is an admissible limit of admissibles (= "recursively inaccessible") then every real in $L_alpha$ is contained in some admissible $L_beta$ with $beta<alpha$. But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $alpha=$ the image of $omega_1$ under the Mostowski collapse of a countable $Mprec H_{omega_2}$).
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
$endgroup$
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
|
show 7 more comments
$begingroup$
Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.
The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.
A couple quick remarks about the result:
The "computability-to-admissibility" half, that $omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $omega_1^{CK}$ is admissible: you prove that $L_{omega_1^r}[r]models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{Mcap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $omega_1^{CK}$ of some real: namely, if $beta$ is admissible and $alpha$ is the next admissible above $beta$, let $G$ be $Col(omega,beta)$-generic over $L_alpha$. $G$ essentially is an $omega$-copy of $beta$, so trivially $omega_1^G>beta$; but $Col(omega,beta)in L_alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $omega_1^Glealpha$. This means $omega_1^G=alpha$ since $omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $omega_1^{CK}$s.
It's also worth noting that for $alpha$ admissible, we may indeed need to step outside of $L_alpha$ to find a real whose $omega_1^{CK}$ is $alpha$. In particular, if there is some $rin L_alpha$ with $omega_1^r=alpha$, then $L_alpha$ will be locally countable (= $L_alphamodels$ "every set is countable"). But plenty of countable admissible $alpha$s don't give rise to locally countable levels of $L$! In particular, if $alpha$ is an admissible limit of admissibles (= "recursively inaccessible") then every real in $L_alpha$ is contained in some admissible $L_beta$ with $beta<alpha$. But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $alpha=$ the image of $omega_1$ under the Mostowski collapse of a countable $Mprec H_{omega_2}$).
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
$endgroup$
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
|
show 7 more comments
$begingroup$
Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.
The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.
A couple quick remarks about the result:
The "computability-to-admissibility" half, that $omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $omega_1^{CK}$ is admissible: you prove that $L_{omega_1^r}[r]models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{Mcap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $omega_1^{CK}$ of some real: namely, if $beta$ is admissible and $alpha$ is the next admissible above $beta$, let $G$ be $Col(omega,beta)$-generic over $L_alpha$. $G$ essentially is an $omega$-copy of $beta$, so trivially $omega_1^G>beta$; but $Col(omega,beta)in L_alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $omega_1^Glealpha$. This means $omega_1^G=alpha$ since $omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $omega_1^{CK}$s.
It's also worth noting that for $alpha$ admissible, we may indeed need to step outside of $L_alpha$ to find a real whose $omega_1^{CK}$ is $alpha$. In particular, if there is some $rin L_alpha$ with $omega_1^r=alpha$, then $L_alpha$ will be locally countable (= $L_alphamodels$ "every set is countable"). But plenty of countable admissible $alpha$s don't give rise to locally countable levels of $L$! In particular, if $alpha$ is an admissible limit of admissibles (= "recursively inaccessible") then every real in $L_alpha$ is contained in some admissible $L_beta$ with $beta<alpha$. But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $alpha=$ the image of $omega_1$ under the Mostowski collapse of a countable $Mprec H_{omega_2}$).
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
$endgroup$
Friedman's paper mentions Sacks' result on page $265$ (the first page of lecture $3$). It's just a one-line mention, though, so it's not really helpful - and Friedman's bibliography doesn't mention Sacks' paper.
The paper you want is Sacks' Countable admissible ordinals and hyperdegrees - namely, you want the first half of Theorem $4.26$. I don't think it has a name.
A couple quick remarks about the result:
The "computability-to-admissibility" half, that $omega_1^r$ is admissible for all reals $r$, is Exercise VII.$1.13$ in Sacks' higher recursion theory book. It's just the relativized version of showing that $omega_1^{CK}$ is admissible: you prove that $L_{omega_1^r}[r]models$ KP, by exactly the same argument (remember that if $M$ is an admissible set then $L^M=L_{Mcap Ord}$ is also admissible).
There's a quick proof that every successor admissible is the $omega_1^{CK}$ of some real: namely, if $beta$ is admissible and $alpha$ is the next admissible above $beta$, let $G$ be $Col(omega,beta)$-generic over $L_alpha$. $G$ essentially is an $omega$-copy of $beta$, so trivially $omega_1^G>beta$; but $Col(omega,beta)in L_alpha$, set forcing preserves admissibility, and no real in an admissible set computes the height of that admissible set, so we get $omega_1^Glealpha$. This means $omega_1^G=alpha$ since $omega_1^G$ is admissible. So the interesting part is showing that admissible limits of admissibles occur as $omega_1^{CK}$s.
It's also worth noting that for $alpha$ admissible, we may indeed need to step outside of $L_alpha$ to find a real whose $omega_1^{CK}$ is $alpha$. In particular, if there is some $rin L_alpha$ with $omega_1^r=alpha$, then $L_alpha$ will be locally countable (= $L_alphamodels$ "every set is countable"). But plenty of countable admissible $alpha$s don't give rise to locally countable levels of $L$! In particular, if $alpha$ is an admissible limit of admissibles (= "recursively inaccessible") then every real in $L_alpha$ is contained in some admissible $L_beta$ with $beta<alpha$. But there are even successor admissible ordinals not giving rise to locally countable levels of $L$ (take e.g. $alpha=$ the image of $omega_1$ under the Mostowski collapse of a countable $Mprec H_{omega_2}$).
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
edited Feb 1 at 3:40
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
answered Feb 1 at 3:18
Noah SchweberNoah Schweber
128k10152294
128k10152294
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
|
show 7 more comments
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
There is one detail here that I want to clarify: assuming that $alpha$ is an arbitrary countable (computable or uncomputable) ordinal greater than $0$ and a family $F_alpha$ of Turing machines is equipped with an oracle for a copy of $omega_{alpha}^{text{CK}}$, can we assume that for any ordinal $beta < omega_{alpha+1}^{text{CK}}$, there exists the corresponding machine that belongs to $F_alpha$ and computes $beta$?
$endgroup$
– lyrically wicked
Feb 1 at 6:34
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
@lyricallywicked You seem to be conflating $omega_{alpha+1}^{CK}$ (the $(alpha+1)$th admissible ordinal) and $omega_1^alpha$ (the first admissible ordinal $>alpha$). For example, taking $alpha=omega+17$, the first admissible above $alpha$ is just $omega_1^{CK}$ but $omega_{alpha+1}^{CK}$ is quite huge; this is analogous to $vertomega_1+17vert<aleph_{omega_1+17}$. (Also, when you say "a family," I presume you mean the family of all oracle machines - otherwise, what family do you have in mind? Certainly some families won't have any interesting computational power at all ...)
$endgroup$
– Noah Schweber
Feb 1 at 13:59
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
The question I think you mean to ask is: suppose $r$ is a real coding a copy of a countable ordinal $alpha$, and $beta<omega_1^{CK}(alpha)$ (that is, $beta$ is less than the first admissible $>alpha$). Then must we have $rge_Ts$ for some real $s$ coding a copy of $beta$? ("$age_Tb$" here means, "there is some index $e$ for an oracle Turing machine such that $Phi_e^b=a$.") The answer to this is yes: we clearly have $omega_1^{CK}(r)>alpha$, and by the first part of Sacks' theorem we know that $omega_1^{CK}(r)$ is admissible, so $omega_1^{CK}(r)>beta$. Now use the definition...
$endgroup$
– Noah Schweber
Feb 1 at 14:01
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
1/3: no, I am not conflating, your first assumption was right: when I write $omega_{alpha+1}^{text{CK}}$, I mean the $(alpha+1)$th admissible ordinal. I am trying to clarify this comment on Math.SE.
$endgroup$
– lyrically wicked
Feb 2 at 8:48
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
$begingroup$
2/3: For example, let $r_1$ denote a particular real that encodes a particular copy of $omega_1^{text{CK}}$. Consider Turing machines with an oracle for $r_1$. Let $beta_1$ denote the supremum of all ordinals that are computable by such machines. Question $1$: is $beta_1$ equal to $omega_2^{text{CK}}$? If yes, is this process applicable to all countable ordinals? That is, instead of $omega_2^{text{CK}}$, the ordinal $omega_{alpha+1}^{text{CK}}$ could be produced by a similar process.
$endgroup$
– lyrically wicked
Feb 2 at 9:17
|
show 7 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.
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%2f3094574%2fwhere-is-the-theorem-related-to-the-construction-of-countable-admissible-ordinal%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
