A question about the non-transitivity of $leq_{walpha}$Question about the “source code” of a recursive...
Vector-transposing function
How to increase accuracy of Plot
Is the differential, dp, exact or not?
After Brexit, will the EU recognize British passports that are valid for more than ten years?
How spaceships determine each other's mass in space?
Having the player face themselves after the mid-game
Why do we say 'Pairwise Disjoint', rather than 'Disjoint'?
Has a sovereign Communist government ever run, and conceded loss, on a fair election?
Why does this boat have a landing pad? (SpaceX's GO Searcher) Any plans for propulsive capsule landings?
Can a space-faring robot still function over a billion years?
What is Tony Stark injecting into himself in Iron Man 3?
Is there a logarithm base for which the logarithm becomes an identity function?
Either of .... (Plural/Singular)
The (Easy) Road to Code
Was it really inappropriate to write a pull request for the company I interviewed with?
Prove that this is a surjection and find the kernel
What to do if my university does not offer any advanced math courses?
Should we avoid writing fiction about historical events without extensive research?
Rationale to prefer local variables over instance variables?
How do you make a gun that shoots melee weapons and/or swords?
Did Amazon pay $0 in taxes last year?
What are the characteristics of a glide in English?
Color each edge separately in TikZ
Why would /etc/passwd be used every time someone executes `ls -l` command?
A question about the non-transitivity of $leq_{walpha}$
Question about the “source code” of a recursive functionQuestion about computability of true/provable formulasQuestion about $Sigma_n$-soundnessquestion about Gödel numberingA question on non-standard ordinals in $alpha-$recursionA Question About Tennebaum's Theorem?Question about the definition of Diophantine setsQuestion about the set of all non-recursively enumerable languagesFirst reflection theorem for $Pi_1^1$ on $Pi_1^1$ propertiesA heuristic for the consistency of ZFC (Fine Structure Theory)
$begingroup$
A very natural question when reading about $alpha$-recursion theory is why and when the weak $alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The Irregular and Non-Hyperregular $alpha$-r.e. Degrees by Shore, in theorem $3.1$. Unfortunately, the characterization he gives for the ordinals such that the reducibility fails to be transitive relies on the existence of a complete $alpha$-r.e. set $A$ such that $forall X(Aleq_{walpha}Xleftrightarrow Aleq_alpha X)$. The book by Sacks is given as a reference, but I am unable to locate the result, or to see how this is implied by the others in the book (the main reason is that Shore gives §25 as the number of the chapter where to find this result, but there is no such chapter in the book, probably because it still hadn't bee published by that time). Could anyone explain to me why a set $A$ as above exists, or point me to a proof?
logic computability
asked yesterday
Leo163Leo163
1,760512
$endgroup$
add a comment |
$begingroup$
A very natural question when reading about $alpha$-recursion theory is why and when the weak $alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The Irregular and Non-Hyperregular $alpha$-r.e. Degrees by Shore, in theorem $3.1$. Unfortunately, the characterization he gives for the ordinals such that the reducibility fails to be transitive relies on the existence of a complete $alpha$-r.e. set $A$ such that $forall X(Aleq_{walpha}Xleftrightarrow Aleq_alpha X)$. The book by Sacks is given as a reference, but I am unable to locate the result, or to see how this is implied by the others in the book (the main reason is that Shore gives §25 as the number of the chapter where to find this result, but there is no such chapter in the book, probably because it still hadn't bee published by that time). Could anyone explain to me why a set $A$ as above exists, or point me to a proof?
logic computability
asked yesterday
Leo163Leo163
1,760512
$endgroup$
add a comment |
$begingroup$
A very natural question when reading about $alpha$-recursion theory is why and when the weak $alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The Irregular and Non-Hyperregular $alpha$-r.e. Degrees by Shore, in theorem $3.1$. Unfortunately, the characterization he gives for the ordinals such that the reducibility fails to be transitive relies on the existence of a complete $alpha$-r.e. set $A$ such that $forall X(Aleq_{walpha}Xleftrightarrow Aleq_alpha X)$. The book by Sacks is given as a reference, but I am unable to locate the result, or to see how this is implied by the others in the book (the main reason is that Shore gives §25 as the number of the chapter where to find this result, but there is no such chapter in the book, probably because it still hadn't bee published by that time). Could anyone explain to me why a set $A$ as above exists, or point me to a proof?
logic computability
asked yesterday
Leo163Leo163
1,760512
$endgroup$
A very natural question when reading about $alpha$-recursion theory is why and when the weak $alpha$-reducibility is not transitive. A complete answer to this question can be found in the paper The Irregular and Non-Hyperregular $alpha$-r.e. Degrees by Shore, in theorem $3.1$. Unfortunately, the characterization he gives for the ordinals such that the reducibility fails to be transitive relies on the existence of a complete $alpha$-r.e. set $A$ such that $forall X(Aleq_{walpha}Xleftrightarrow Aleq_alpha X)$. The book by Sacks is given as a reference, but I am unable to locate the result, or to see how this is implied by the others in the book (the main reason is that Shore gives §25 as the number of the chapter where to find this result, but there is no such chapter in the book, probably because it still hadn't bee published by that time). Could anyone explain to me why a set $A$ as above exists, or point me to a proof?
logic computability
logic computability
asked yesterday
Leo163Leo163
1,760512
asked yesterday
Leo163Leo163
1,760512
edited yesterday
Leo163
asked yesterday
Leo163Leo163
1,760512
asked yesterday
Leo163Leo163
1,760512
asked yesterday
Leo163Leo163
1,760512
1,760512
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:={delta<alpha: K_deltacap Aneqemptyset}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*leq_{walpha}Brightarrow Aleq_{alpha} B$, and since $A=_alpha A^*$ we are done.
answered yesterday
Leo163Leo163
1,760512
$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%2f3139528%2fa-question-about-the-non-transitivity-of-leq-w-alpha%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$
okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:={delta<alpha: K_deltacap Aneqemptyset}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*leq_{walpha}Brightarrow Aleq_{alpha} B$, and since $A=_alpha A^*$ we are done.
answered yesterday
Leo163Leo163
1,760512
$endgroup$
add a comment |
$begingroup$
okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:={delta<alpha: K_deltacap Aneqemptyset}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*leq_{walpha}Brightarrow Aleq_{alpha} B$, and since $A=_alpha A^*$ we are done.
answered yesterday
Leo163Leo163
1,760512
$endgroup$
add a comment |
$begingroup$
okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:={delta<alpha: K_deltacap Aneqemptyset}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*leq_{walpha}Brightarrow Aleq_{alpha} B$, and since $A=_alpha A^*$ we are done.
answered yesterday
Leo163Leo163
1,760512
$endgroup$
okay, false alarm: I was being misled by the requirement that $A$ had to be complete. The result I was trying to prove actually holds for every $alpha$-r.e. set $A$ (and maybe also for other sets): it is enough to consider a slight modification of the set $A$, say $A^*:={delta<alpha: K_deltacap Aneqemptyset}$ (this is actually in Sacks' book, so my bad for checking poorly). For every set $B$, clearly $A^*leq_{walpha}Brightarrow Aleq_{alpha} B$, and since $A=_alpha A^*$ we are done.
answered yesterday
Leo163Leo163
1,760512
answered yesterday
Leo163Leo163
1,760512
answered yesterday
Leo163Leo163
1,760512
answered yesterday
Leo163Leo163
1,760512
1,760512
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%2f3139528%2fa-question-about-the-non-transitivity-of-leq-w-alpha%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
