Timeline for Mapping between Notations
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2017 at 12:11 | comment | added | Joel David Hamkins | There is quite a bit of work aimed at the computable ordinals, and much of it is wrapped up with set theory, particularly admissible set theory, and the study of the hyperarithmetic sets, since the computable ordinals turn out to be the same as the hyperarithmetically definable ordinals, and $L_{\omega_1^{CK}}$ is a model of Kripke-Platek set theory. So the keywords would be: hyperarithmetic, admissible set theory, KP, Churck-Kleene ordinal. | |
| Aug 9, 2017 at 12:10 | comment | added | SSequence | @AndreasBlass Perhaps you can also comment if you know some references that consider this kind of question. Also, the example for $\omega$ was just meant as a specific example/case. What I meant was the question in the general sense. | |
| Aug 9, 2017 at 12:05 | comment | added | SSequence | @JoelDavidHamkins I have a related question that came to my mind. Is there known work regarding which well-orderings are provably not recursive? The second statement of Andreas above in comments can be thought of as a tool in this direction. A simple and specific example: consider the notation $N$ for $\omega$ which happens to be same as natural numbers. Every notation whose isomorphism is recursive with $N$ is trivially recursive. However, clearly there are many notations whose isomorphism with $N$ is $0\,'$-computable yet they are not recursive. Any references for work in this direction? | |
| Aug 7, 2017 at 2:56 | comment | added | Joel David Hamkins | Thanks very much, I find the question very interesting. By the way, I think you'll be more readily understood if you refer to the $0''$-computable functions, rather than the TOTAL-computable functions. The issue is that the phrase "total computable function" is commonly used to refer to the functions that are computable (not using any oracle) and total, as opposed to partial. Since Tot is Turing equivalent to $0''$, however, I think most computability theorists would refer to your class of functions as the $0''$-computable functions. | |
| Aug 7, 2017 at 2:02 | vote | accept | SSequence | ||
| Aug 7, 2017 at 2:00 | comment | added | SSequence | Very well-structured answer, I just have trouble with the last theorem. But that's just because it's in more abstract/symbolic form (and hence just shows my own lack of understanding). Though now that I know that this kind of example exists, I am confident enough that I can re-create an example of lack of TOTAL-computable isomorphism (using less abstract form of programs). I think it is somewhat remarkable that the isomorphism function can be made so difficult to dominate (in terms of growth rate). | |
| Aug 7, 2017 at 1:46 | comment | added | SSequence | "Anyway, I think that I can create an example for $\omega$ (without much difficulty) where the isomorphism isn't halt-computable" .... I posted this in one my previous comments but this is incorrect (as follows trivially from the very first theorem in the answer). I am not removing that comment to avoid unnecessary confusion (w.r.t. flow of conversation). | |
| Aug 6, 2017 at 4:51 | comment | added | Andreas Blass | As @RobinSaunders said, I meant well-orderings of $\omega$, not well-orderings of order-type $\omega$. (Rereading my comments, I see that I got lucky and actually wrote what I meant.) | |
| Aug 6, 2017 at 2:00 | comment | added | Joel David Hamkins | Ah, thanks, in that case, I think he is right! Meanwhile, my updated answer shows that one needs to the order type to increase to form counterexamples as the oracle increases in strength. | |
| Aug 6, 2017 at 1:57 | comment | added | Robin Saunders | Perhaps Andreas did not mean well-orderings of type $\omega$, but merely well-orderings of a countable set. | |
| Aug 6, 2017 at 1:42 | comment | added | Joel David Hamkins | By the way, there seems to be room in the results I mentioned to improve the last theorem to produce computable relations of type $\omega^3$ that are not isomorphic even allowing oracle $0'''$. This would show the earlier result to be optimal, and I suspect this is the case. | |
| Aug 6, 2017 at 1:40 | comment | added | Joel David Hamkins | I'd have to think about it. | |
| Aug 6, 2017 at 1:36 | comment | added | SSequence | @JoelDavidHamkins Well most likely your construction would be correct, so forget about it. I do have a question before I start reading though (which would take me quite some time). For the example you have constructed for $\omega^3$ for example, is the function $P{_1}{_2}$ computably unbounded w.r.t. TOTAL-programs (programs with access to oracle for TOTAL). | |
| Aug 6, 2017 at 1:27 | comment | added | Joel David Hamkins | I'm unsure to which result you refer. Can you state it here? Meanwhile, I've updated my answer to explain things a little more clearly. Let me know if you have any questions. Your conjecture about $0''$ is wrong in light of the counterexample order I give with order-type $\omega^3$, but but it is right for order-types below $\omega^2$, although in that case $0'$ also suffices. | |
| Aug 6, 2017 at 1:24 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Re-did the presentation for a more thorough presentation and fixed several issues.
|
| Aug 6, 2017 at 0:57 | comment | added | SSequence | My question/guess was partially motivated by my own "result", which I mentioned in the closed (soon to be deleted) thread. If any user here says that their construction is correct, most likely it is. However, you might still want to briefly check my comment under the original question. | |
| Aug 5, 2017 at 22:41 | comment | added | Joel David Hamkins | 0' can compute isomorphisms for orders up to omega squared, and 0'' up to omega cubed. | |
| Aug 5, 2017 at 21:48 | comment | added | Joel David Hamkins | *next element.. | |
| Aug 5, 2017 at 21:47 | comment | added | Joel David Hamkins | Andreas's conjecture is too strong, since with an oracle for 0' we can identify the not element by recognizing adjacent points. So the order types must go beyond omega. | |
| Aug 5, 2017 at 21:42 | comment | added | SSequence | @JoelDavidHamkins Thanks for answer. I will need quite some time to read your answer (so it may take some time marking your answer). Anyway, I think that I can create an example for $\omega$ (without much difficulty) where the isomorphism isn't halt-computable (using bad notation where successor function won't be computable). Beyond that for $\omega$, I don't know much. As for the first conjecture by Andreas Blass, in case true, I think there might be another parameter as to the smallest ordinal (where the isomorphism isn't computable from a given set). Quite beyond my scope though. | |
| Aug 5, 2017 at 21:18 | comment | added | Joel David Hamkins | I posted the $0''$ result, and I believe as Andreas has commented that this can be pushed much further. My argument used basically $\omega^2$, and it seems one can go higher in the arithmetic hierarchy using taller order types. Perhaps one can get this down to $\omega$, but I don't quite see it yet. | |
| Aug 5, 2017 at 21:16 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 110 characters in body
|
| Aug 5, 2017 at 21:04 | comment | added | Andreas Blass | The second conjecture in my previous comment seems to have an easy proof. The isomorphism sends $a$ in the first order to $b$ in the second iff there's an isomorphism between the predecessors of $a$ in the first and the predecessors of $b$ in the second. So the isomorphism is $\Sigma^1_1$. For a $\Pi^1_1$ definition, just say that the $\Sigma^1_1$ definition doesn't hold for $a$ and any $b'\neq b$. | |
| Aug 5, 2017 at 21:01 | comment | added | Andreas Blass | At the risk of requiring a transfinite sequence of edits of this answer, I'll conjecture that, given any hyperarithmetical set $A$, there exist two isomorphic, computable well-orderings of $\omega$ such that the isomorphism between them is not computable from $A$. On the other hand, I conjecture that the isomorphism between two computable well-orders of $\omega$ is always hyperarithmetical. (I think there's a result in reverse mathematics saying that comparability of well-orders is equivalent to $\text{ATR}_0$, which suggests my conjectures.) | |
| Aug 5, 2017 at 20:53 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 110 characters in body
|
| Aug 5, 2017 at 20:44 | comment | added | Gro-Tsen | Can you add this to your answer, then? Even if it's not exactly what OP wanted, it's interesting, and I don't find it obvious. | |
| Aug 5, 2017 at 20:41 | comment | added | Joel David Hamkins | You may be right, but I think I can also make a counterexample for that, with a longer order. | |
| Aug 5, 2017 at 20:39 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 110 characters in body
|
| Aug 5, 2017 at 20:38 | comment | added | Gro-Tsen | From the way I understand (the confusing wording of) OP's question, they want to know whether the isomorphism belongs to $\mathbf{0}''$ ("Total-computable"), not $\mathbf{0}$. | |
| Aug 5, 2017 at 20:36 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |