Timeline for Mapping between Notations
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 31 at 5:20 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Defined the \operator math command
|
| S Oct 31 at 5:20 | history | suggested | Matemáticos Chibchas | CC BY-SA 4.0 |
Fonts for operators implemented
|
| Oct 31 at 4:12 | review | Suggested edits | |||
| S Oct 31 at 5:20 | |||||
| Oct 30 at 19:28 | history | edited | Farmer S |
edited tags
|
|
| Oct 30 at 16:41 | answer | added | Farmer S | timeline score: 3 | |
| Aug 8 at 0:41 | history | edited | Joel David Hamkins |
edited tags
|
|
| Aug 7, 2017 at 2:02 | vote | accept | SSequence | ||
| Aug 6, 2017 at 3:05 | review | First posts | |||
| Aug 6, 2017 at 5:42 | |||||
| Aug 6, 2017 at 1:23 | comment | added | SSequence | Perhaps the comment about strictly breaking bound of corresponding "busy beaver" is not quite correct. As I have read that there exist functions which are recursively unbounded but can't be used to calculate $BB$ (and probably then these kind of functions would also exist for higher analogues of $BB$ in arithmetic hierarchy). But whether these kinds of functions can be used in $P{_1}{_2}$, I don't have any idea. I guess I am confusing things more than necessary at this point. TOTAL-computably bounded might be better and more accurate to say perhaps. | |
| Aug 6, 2017 at 0:49 | comment | added | SSequence | My (rough) guess that some kind of simple upper bound on complexity should exist, stems from the fact that if the well-orderings corresponding to $N_1$ and $N_2$ are computable then we have the following fact: "If $P{_1}{_2}$ and $P{_2}{_1}$ are recursively bounded then $P{_1}{_2}$ is recursive." So I "think" it "seems" to me to break the bound of TOTAL-computable for isomorphism you would also have to break the bound of "busy beaver" for the corresponding oracle-program. And so on for more complex sets in arithmetic hierarchy. I would find it interesting to see how it would be done. | |
| Aug 5, 2017 at 20:53 | history | edited | SSequence | CC BY-SA 3.0 |
deleted 72 characters in body
|
| Aug 5, 2017 at 20:52 | comment | added | SSequence | @Gro-Tsen Well yes, I meant the functions that are computable given the access to oracle representing "indexes of total recursive functions". And if that doesn't suffice, what would be appropriate upper-bound on complexity. Sorry for slightly confusing wording. | |
| Aug 5, 2017 at 20:36 | comment | added | Gro-Tsen | @PeterLeFanuLumsdaine I think OP wants to know whether the isomorphism belongs to $\mathbf{0}''$ (the use of the phrase "Total-computable" refers to this, I think). | |
| Aug 5, 2017 at 20:36 | answer | added | Joel David Hamkins | timeline score: 9 | |
| Aug 5, 2017 at 20:35 | comment | added | Gro-Tsen | Your question is very confusingly worded, but I think what you want to ask is this: “let $<_1$ and $<_2$ be two computable well-orders on $\mathbb{N}$ representing the same (computable) ordinal: is it true that the unique isomorphism between them belongs to the Turing degree $\mathbf{0}''$ (of indexes of total recursive functions)?” Correct? If this is indeed what you want to ask, I suggest you write it roughly as I just did. | |
| Aug 5, 2017 at 20:25 | comment | added | Peter LeFanu Lumsdaine | I suspect the lack of answers may be because the presentation is a bit unclear — all the setup of "notations" is really tangential to the main question itself. The question can be given in a single sentence: given two computable well-orderings on $\newcommand{\N}{\mathbb{N}}\N$ which happen to have the same order-type, is the induced automorphism of $\N$ computable? | |
| Aug 5, 2017 at 20:01 | history | asked | SSequence | CC BY-SA 3.0 |