Timeline for Relation between $\eta$ and $\omega^L_1$
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 29, 2021 at 3:53 | comment | added | lyrically wicked | How large is the supremum $\beta$ of stabilization times of OTMs with no oracles? Is $\beta$ equal to the least ordinal $\delta$ such that $L_{\delta}$ has the right $\Sigma_2^L$ theory? Or $\beta$ is equal to the least ordinal $\delta$ such that $L_{\delta} \prec_{\Sigma_2} L$? | |
| Nov 18, 2019 at 17:54 | comment | added | SSequence | One of the sentences in second-last comment above should be: "Though I think I do understand well-enough that why the supremum of stabilization times would be an ordinal of the form $\omega^L_\alpha$." Anyway, I will stop bothering with comments. I might ping upon posting a follow-up question. | |
| Nov 18, 2019 at 17:46 | comment | added | SSequence | @JoelDavidHamkins I have been thinking about a more specific notion than I mentioned in the question (more specific than the notion of "markable") and have understood a few things about it. What I wrote in the (current) edit is only partially relevant (I didn't modify the question again because I generally prefer to limit no. of modifications to avoid bumping). If I do find a question related to that notion that I think might be interesting to analyze than I might post it sometime as sort of a follow-up to this question (but it isn't necessary that I will post a follow-up question though). | |
| Nov 18, 2019 at 17:41 | comment | added | SSequence | @DmytroTaranovsky Thanks for the response. What you wrote is a bit beyond my level, but it makes "some" sense to me that the notions you mentioned would be captured by appropriate quantifications. Though I think I do understand well-enough that why the supremum of stabilization would be an ordinal of the form $\omega^L_\alpha$ (obviously a far stronger condition than admissibility, which I mentioned in comments above). | |
| Nov 12, 2019 at 18:40 | comment | added | Dmytro Taranovsky | @SSequence More generally, using a class of ordinals $S$ as an oracle, the writable reals are the ones in $Δ_{1,S}^{L[S]}$, the eventually writable reals are the ones in $Δ_{2,S}^{L[S]}$, and the accidentally writable reals are the ones in $L[S]$. (Also, in place of reals, one can use sets of ordinals if the formula complexity is for equality rather than membership.) If $S=∅$, the supremum of stabilization times for eventually writable reals is the least $L$-cardinal $δ$ such that $L_δ$ has the right $Σ_2^L$ theory. This is a large $L$-cardinal, but below the least $δ$ with $L_δ ≺_{Σ_2} L$. | |
| Nov 4, 2019 at 12:14 | vote | accept | SSequence | ||
| Nov 4, 2019 at 12:10 | comment | added | Joel David Hamkins | Well, certainly the oracle concept is natural, and people have studied it. I don't understand what the question is that you might have, but if you do ask it, it should be a separate question. | |
| Nov 4, 2019 at 12:06 | comment | added | SSequence | Regarding what I wrote in earlier deleted comments, that's was mostly related to explicit implementation (and doesn't change anything theoretically ofc). Regarding what I wrote in the last comment (below question): I think it shouldn't be difficult to formulate an equivalent oracle machine with just tapes. I just worded it this way because it was easier to write in less number of words (in comments). Anyway, if you aren't interested enough, I won't be posting it as a separate question (since generally, the interest doesn't seem to be that high). | |
| Nov 4, 2019 at 12:03 | comment | added | Joel David Hamkins | Your comment is related to ordinal register machines, and you seem to be describing some mixture of ordinal tape+register machines. I don't find that a compelling model, given that we have the other models, and they are known to be equi-powerful in various senses. If you want to use ordinal registers, use a register machine. If you want to use tapes, use a tape machine. The marking method on the tape seems to simulate whatever you want from a register, and so I don't find it desirable to change the underlying model. | |
| Nov 4, 2019 at 11:59 | comment | added | SSequence | OK that's good. Initially I thought that $\omega^L_1$ stabilization would lead to $\eta_0<\eta$ (with $\eta_0$ itself having strong closure properties). But after the comment, I assumed it to be correct naturally (since it was from an expert). Anyway, what do you think about the (last) comment I posted under the question. Would it be a suitable separate question? I don't think there would be that much interest generally though. So if you aren't interested enough, I won't be posting it as a separate question. | |
| Nov 4, 2019 at 10:50 | comment | added | Joel David Hamkins | Note: Merlin Carl has retracted his claim on math.SE about the stabilization times being countable, and he said he agrees with my argument about it. | |
| Nov 4, 2019 at 0:14 | comment | added | Joel David Hamkins | Yes, it obviously has countable cofinality. | |
| Nov 3, 2019 at 23:37 | comment | added | SSequence | "If my thinking is correct, this is uncountable in $L$,....." I don't know what that means precisely so my comment might be off. But shouldn't it be easy to give an (increasing) $\omega$-sequence for the sup of stabilization times (say $\mathcal{S}$) just based on appropriate parameters? (but it would require $\mathcal{S}$ itself as a parameter too though) | |
| Nov 3, 2019 at 23:03 | comment | added | Joel David Hamkins | It will be much larger than $\aleph_\omega^L$, since the existence of each $\aleph_n^L$ is $\exists\forall$ expressible: "there exists a finite sequence of $n$ limit ordinals, such that there is no function collapsing one of them to the previous." And yes, it will be admissible for similar reasons. | |
| Nov 3, 2019 at 22:58 | comment | added | SSequence | Sorry I don't understand this very well (of course). Will it be admissible (it must be I think). Will it have countable cofinality? And how small it would be compared to something like $\aleph^L_{\omega}$ (assuming this terminology makes sense). | |
| Nov 3, 2019 at 22:51 | comment | added | Joel David Hamkins | The supremum of the stabilization times, it seems to me, must be the first 2-stable ordinal, the first ordinal $\alpha$ with $L_\alpha\prec_{\Sigma_2} L$. If my thinking is correct, this is uncountable in $L$, precisely because $\omega_1^L$ is the least ordinal not seen as countable in $L$, which is a $\forall\exists$ property. This is a much stronger property than that mentioned by Merlin Carl, namely, merely of having the right $\forall\exists$ theory. | |
| Nov 3, 2019 at 22:47 | comment | added | SSequence | Another thing is that your last paragraph is ofc correct. But it produces a real which has already been produced (via stabilization at countable time). I am not sure whether it matters or not, but I thought it is worth pointing out (and, in this sense, it might be interesting thinking in terms of "smallest" stabilization time for a given real). | |
| Nov 3, 2019 at 22:33 | comment | added | SSequence | The point being that something like $\omega^{CK}_{\omega_1+1}$ (taking $\omega_1=\omega^L_1$?) doesn't have the properties mentioned in the previous paragraph, so then $\mathcal{S}$ has to be different and bigger. | |
| Nov 3, 2019 at 22:24 | comment | added | SSequence | A few observations. If we denote the supremum of stabilization times as $\mathcal{S}$ and if we have $\mathcal{S}>\omega^L_1$ then there are two things: (i) It must have countable cofinality. (ii) It must be admissible. Also, I agree with your last paragraph. Though one question is that whether the intention of the quoted comment (regarding stabilization times) was only with those outputs that produce a code for an ordinal or not. But I am being speculative here. | |
| Nov 3, 2019 at 10:13 | comment | added | SSequence | At any rate, thanks for your answer. I will try to read it carefully. Since it is closely related to what I asked, I am upvoting it. I will also try to think about $\omega^L_1$-stabilization issue independently (to understand it better). | |
| Nov 3, 2019 at 10:09 | comment | added | SSequence | "I am saying that there are algorithms whose first $\omega$ many cells stabilize, but not at any countable stage." OK this seems to go against the comment that I quoted above (from MSE thread) ......... unless I happen to missing something obvious. | |
| Nov 3, 2019 at 10:06 | comment | added | Joel David Hamkins | I am saying that there are algorithms whose first $\omega$ many cells stabilize, but not at any countable stage. One can see this easily: compute the theory of $L_\alpha$ as $\alpha$ increases, and flash a cell whenever $L_\alpha$ thinks $\omega_1$ does not exist. This will flash unboundedly often for $\alpha<\omega_1^L$, but after that, it will stop flashing. | |
| Nov 3, 2019 at 10:00 | comment | added | SSequence | Because that would go against what you have written: "In particular, it follows from what we've said so far that eventually writable reals do not stabilize in time $\omega^L_1$." | |
| Nov 3, 2019 at 9:56 | comment | added | SSequence | Thanks, I have taken a brief look only, but this seems quite related to the question. One brief question before I take a detailed look. Are you saying that the comment (on MSE): "OK, so you are asking for the supremum of what is usually called the "stabilization times". All stabilization times are countable and in fact, their supremum is again $\eta$" has a mistake? [you can find it just below the answer given on MSE thread] | |
| Nov 3, 2019 at 9:35 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 18 characters in body
|
| Nov 3, 2019 at 9:25 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 3512 characters in body
|
| Nov 1, 2019 at 18:48 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 966 characters in body
|
| Nov 1, 2019 at 18:28 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |