Timeline for An alternative definition of computable ordinals
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 17, 2022 at 7:03 | comment | added | Dan | Ah, every node is just a sequence $(x_1, \dots, x_n)$ where $x_1$ is the index of a root subtree, $x_2$ is the index of child subtree, etc. We can computably compare the notations and check if a notation corresponds to a node. | |
| Oct 17, 2022 at 6:19 | comment | added | Dan | @DanTuretsky As I understand, for a computable well-ordered relation we can enumerate all lesser relations. So the alternative definition is not less restrictive. But the reverse statement is not that obvious. Why the corresponding Kleene-Brouwer well-ordering has a computable relation? I guess we need to show that the alternative definition implies that there is a concrete notation for all nodes in a tree. And from this notation we can get a computable relation. | |
| S Oct 17, 2022 at 5:04 | history | suggested | C7X | CC BY-SA 4.0 |
Possibly confusing if (x_i) looks like a length-1 sequence
|
| Oct 17, 2022 at 4:03 | review | Suggested edits | |||
| S Oct 17, 2022 at 5:04 | |||||
| Oct 16, 2022 at 22:39 | comment | added | Patrick Lutz | @DanTuretsky I think you may have misinterpreted the original question (though since I'm not the OP I'm not totally sure). I interpreted the question as "if we define computable tree in a slightly different way than normal, is the set of possible ranks still exactly $\omega_1^{CK}$?" The answer is "yes" and the proof is easy but it's not quite what you and Andreas mentioned. | |
| Oct 16, 2022 at 21:42 | comment | added | Dan Turetsky | As Andreas said, this is the same. In one direction, from a computable well-ordering, make the tree of descending sequences. In the other direction, give a computable well-founded tree the Kleene-Brouwer ordering to get a well-ordering at least as large as the tree rank (and then invoke downward closure of computable ordinals). | |
| Oct 16, 2022 at 19:58 | comment | added | Dan | @AndreasBlass, thanks, I clarified the indexing. | |
| Oct 16, 2022 at 19:57 | history | edited | Dan | CC BY-SA 4.0 |
added 306 characters in body
|
| Oct 16, 2022 at 18:57 | comment | added | Andreas Blass | In clause 2 of your definition of computable trees, you'll need an indexing of trees to talk about "a computable enumeration of them." If you set up the indexing reasonably, you'll get exactly the computable ordinals as the ranks of your computable trees. (This ought to be in textbooks that cover the theory of $\Pi^1_1$ sets.) | |
| Oct 16, 2022 at 18:13 | history | edited | Dan | CC BY-SA 4.0 |
added 65 characters in body
|
| Oct 16, 2022 at 16:41 | history | asked | Dan | CC BY-SA 4.0 |