3
$\begingroup$

This question is about eventual writability in the setting of OTM or a similar model. Let's first observe how we might try to generalise the relevant notions.

Let's first observe how we might try to define the relevant notions. First consider the notions of "eventually writable real" and "accidentally writable real". If we are talking about OTM then it seems reasonable to designate the initial $\omega$ length of tape and consider this in defining the relevant notions. Similarly, if we have a program that supports a variable (of type list), then we can have a separate (list) variable where the first $\omega$ elements are observed. Also observe that, as in original definition, we want the program to start from empty tape and/or zero/uninitialized variables.

Let's write "accidentally writable" and "eventually writable" as AW and EW respectively. So we have the notions of: (i) AW-real (ii) Sup of AW-ordinal (iii) EW-real (iv) Sup of EW-ordinals. Let's simply use $AW$ and $EW$ to denote (i) and (iii) respectively. We will only be concerned with subsets of $\omega$ so it wouldn't be a problem. Let's use the symbols $\mathcal{A}$ and $\eta$ for the ordinals in (ii) and (iv) respectively. We can say that an ordinal $<\eta$ is eventually writable if its code (in the sense of well-order of $\mathbb{N}$) appears on the output section (of $\omega$-length) never to be changed again.

The main question is in Part-(B). Part-(A) asks a question whose (positive) answer is used in part-(B).

(A)

First a very basic question (this might be related to second one). I have read that constructible sets of ordinals are exactly the same as those which are ordinal computable (given some finite parameters with appropriate values).

And now, in a reasonable sense, there should exist a non-halting program which can basically enumerate (under a specific definition) all $\alpha$-computable sets for any arbitrary $\alpha$ (by trying out all possible combination of parameters). By "enumerate" I just mean that we have an (unbounded) region designated for output and the contents of all the sets that we generate are appropriately listed (and also stored there indefinitely).

Now let's restrict ourselves to subsets of $\omega$ (that is, to reals). Then as much as I can gather, the specific notion of enumeration mentioned in previous paragraph should coincide with the notion of AW-real described in the beginning of the question.

Now a natural question is what is the value of $\mathcal{A}$ when compared to $\omega^L_1$ (which I "guess" means $\omega_1$ under constructibility axiom). Based on what I have been able to understand we should have $\mathcal{A} \leq \omega^L_1$. From what I have been able to gather after a number of questions/answer (here and on mathoverflow) it should be true that $\mathcal{A} = \omega^L_1$.

(B)

For the rest of the post I use $\omega_1$ to mean $\omega^L_1$ (I could be misunderstanding something obvious here). For the rest of the question "code for $\alpha$" simply means "well-order of $\mathbb{N}$ (in suitably encoded form) with order-type $\alpha$".

First we assume the access to an onto function $f:Ord \rightarrow AW$. That is, we have a program which when given any arbitrary input $x$ will halt and return a real that belongs to $AW$. Essentially, $f(x)$ corresponds to the "$x$-th time" an AW-real appears on the output (for a program that enumerates all elements of $AW$). Based on what I have been able to gather via a number of questions/answers, it seems that more things can be said about this function $f$ (basically based on what seems to be known about constructible reals). However, we won't be needing that (strictly speaking). So to keep the question shorter, let's move on.

And now the main question. The trouble I have is that if the answer to question in part-(A) is in positive. Our concern is that what is the value of $\eta$? Based on the fact that EW-reals are subset of AW-reals, we should have $\eta \leq \mathcal{A}$. And because $\mathcal{A}=\omega_1$ (based on part-(A)) we have $\eta \leq \omega_1$. Consider the case $\eta = \omega_1$. It seems that this would imply that $\mathcal{A}>\omega_1$. But this isn't allowed because we have $\mathcal{A}=\omega_1$.

So $\eta$ must be countable. But let's try to analyze this in a bit of detail. Because we have $\mathcal{A}=\omega_1$ there exists a variable which eventually settles to a value $\omega_1$ (and never changes after that). Setting-up such a variable (let's call it $v$) in a program isn't difficult. Initially set $v:=\omega$. Then go through $range(f)$ while waiting for code of $\omega$ to appear. Once it appears the command $v:=v+1$ is triggered. But this is also true in general. If, at any point, we have $v$ equal to $\alpha<\omega_1$, then go through $range(f)$ while waiting for code of $\alpha$ to appear. Once again this triggers the command $v:=v+1$.

One thing in last paragraph is that the value of $v$ is only ever increased. And because we have $\mathcal{A}=\omega_1$, the value of $v$ should stabilize to $\omega_1$, never to change again. Now we want another variable (let's call it $u$), which we want to stabilize to $\eta$ (and never changing again). Let's try to see how we can do that.

Let's denote $O_e(t)$ to mean that output of program with index $e \in \mathbb{N}$ at a time $t \in Ord$. Note that because we are talking about a program that starts from blank state, we can talk about a natural number as an index. Suppose at some point we had $v:=V$. We want to calculate the value of $u$ corresponding to the given value of $v$. Roughly speaking, for any time, the variable $u$ tries to "guess" $\eta$ in a local sense based on the current value of $v$. First, we wish to calculate a subset of ordinals, say $X$.

For all indexes $e \in \mathbb{N}$ we check whether there exists a value $x<V$ such that for all $x \leq y \leq V$ we have $O_e(x)=O_e(y)$. In-case this happens to be true check $O_e(V)$. If it happens that this contains a code for ordinal, then that ordinal belongs to $X$. Once we repeat this process for all indexes (and not just $e$), we have the set $X$. We can set the value of $u$ as the smallest ordinal not in $X$. We can also set the output to contain a code for the current value of $u$.

Finally let's try to observe what happens when $v:=\omega_1$. We have a combination of programs that do and do not stabilize permanently (that is, not just in limit $\omega_1$ but in actuality). Based on what is mentioned by MCarl in comments below the answer, all programs that do stabilize happen to do so in countable time. This is an important observation (generally speaking too but more so in the context of the current question). Because that would mean that when $v:=\omega_1$ we will be able to set $u$ as some value $\geq \eta$. Based on what is mentioned in last paragraph, we can also set the output to contain a code for the current value of $u$.


Here are few observations: (1) When we are trying to calculate $u$ for any given value of $v:=V$, we can suitably restrict $X$ to be a subset of $V$.

(2) When $v:=\omega_1$, we might say that there might be a third possibility where the output becomes stable at a point $\alpha<\omega_1$ and then remain stable for a whole stretch of $[\alpha,\omega_1)$ interval and then changes some time after that. But this isn't possible. That's because programs with access to arbitrary parameters $\leq \alpha$ will always halt at countable time (starting from empty input, but with parameters). This requires some more detailed justification (which I have skipped). But the point is that a change in output after staying stable for a whole stretch $[\alpha,\omega_1)$ means the existence of a program (with parameter $\alpha$) which halts at point $\geq \omega_1$.

The lack of existence of such programs seems to imply that $u$ will be set exactly to $\eta$ when $v:=\omega_1$.

(3) Without going into detail, it seems that it might be appropriate to add something about the function $f:Ord \rightarrow AW$. It can be shown that (if the answer to part-(A) is in positive) the code for all ordinals $<\omega^L_1$ must appear within the countable inputs for the function $f$. Once again we can show it by demonstrating that if that weren't the case then a program with no input and parameters $<\omega^L_1$ can halt beyond $\omega^L_1$ (which shouldn't be possible). So in that sense the values $f(x)$ (where $x<\omega^L_1$) are of particular interest.

Anyway, it seems to me that what I mentioned in last paragraph is very well-known (so I won't make this post any more lengthy than it is). But what I did want to mention is that it is of sufficient interest to look at run-times for $f$. We can consider a (simple) specific implementation of $f$. The run-time would be relevant if we want to place a more concrete bound on the time for stabilization in the construction in part-(B).


Note: I suppose the question is that if $v$ stabilizes to $\omega_1$ then why can't we have a variable $u$ which eventually stabilizes to $\eta$? (and hence the existence of a program for which, at output, a code for some value $\eta$ is stabilized at some time $\geq \omega_1$).

I also tried to search whether I could find something related and hence better understand about the notion mentioned in the question. I could only find this (starting from "definition-3.9" on page-8, see the next two pages). The context is too advanced but I am posting it for the sake of reference (as it might be useful for someone else).

The question has been edited substantially to make it more organized and easier to read.

$\endgroup$
6
  • $\begingroup$ On some more thought, it seems to me that the assumption that every value $\alpha<E$ gets written (in a stable way) by some program at time less than $\omega^L_1$ needs a closer examination. I can't think of a clear way to rule it out (even though it seems hard to visualize). So it seems that this particular point needs to be examined (I made the given assumption at two points in part-(B)). $\endgroup$
    – SSequence
    Oct 22 '19 at 0:33
  • $\begingroup$ It seems that "Lemma-3.12" on page-9 (for the link towards the end of question) might be quite relevant w.r.t. what I wrote in previous comment. However, since I don't understand it, it is difficult for me to comment any further on this. $\endgroup$
    – SSequence
    Oct 22 '19 at 1:27
  • $\begingroup$ I happen to sit across the desk from Philipp right now, and I've alerted him to your question. $\endgroup$
    – Asaf Karagila
    Oct 22 '19 at 15:13
  • $\begingroup$ @AsafKaragila Thanks, that's great. $\endgroup$
    – SSequence
    Oct 22 '19 at 15:44
  • 1
    $\begingroup$ Posted on mathoverflow: mathoverflow.net/questions/345007 $\endgroup$
    – SSequence
    Nov 1 '19 at 9:54
2
$\begingroup$

Both questions are answered in the paper you refered to (i.e., "Recognizable sets and Woodin cardinals: computation beyond the constructible universe") https://arxiv.org/abs/1512.06101 in Lemma 3.13 (I will write "OTM-aw" and "OTM-ew" for "OTM-accidentally writable" and "OTM-eventually writable":

Concerning accidental writability: You are right, the OTM-aw real numbers are exactly the constructible ones. More or less, one can see this in the way you indicated by simultaneously simulating all OTM-programs in all parameters and, whenever one of these outputs a real number, one writes this to the output section.

Concerning eventual writability: If $\eta$ is minimal such that $L_{\eta}$ is a $\Sigma_{2}$-submodel of $L$ then $x\subseteq\omega$ is OTM-ew if and only if $x\in L_{\eta}$.

However, it is possible, as you indicate, to see that the supremum of the OTM-ew ordinals must be countable without determining its value: Each coded ordinal will be countable in $L$, and there are only countable many programs, hence at most countably many OTM-ew ordinals. Finally, the function $f:\omega\rightarrow\omega_{1}^{L}$ mapping $i$ to the ordinal eventually written by the $i$th OTM-program (if it exists) and to $0$, otherwise, is definable in $L$, hence contained in $L$, and now the supremum of the OTM-ew ordinals is $\bigcup f[\omega]$, which is countable in $L$.

I understand that part B is asking what is wrong with the following method to eventually write the supremum of the OTM-ew ordinals: Run all program simultaneously, write a code for the sum of the outputs to the output section. At some point, all programs that stabilize have stabilized and then, the output will be stable and equal the sum of all OTM-ew ordinals. The problem is that, if we do this with all programs, then the output will not stabilize, because it will include the outputs of non-stabilizing programs. It would work if we could restrict ourselves to those programs that stabilize; however, the set of programs that stabilize is quite complicated and in particular not OTM-ew (basically, this section is a reductio proof of this), so this also does not work.

edited: Previously, this post stated that $\eta$ merely needs to be minimal such that $L_{\eta}$ and $L$ have the same $\Sigma_{2}$-theory, which would mean that it is an $L$-countable ordinal. As Joel Hamkins pointed out below, this is false.

$\endgroup$
21
  • $\begingroup$ Unfortunately I don't understand the phrase (not enough background in logic): "If $\eta$ is minimal such that $L_{\eta}$ and $L$ have the same $\Sigma_2$-theory". Few quick questions (hopefully). (1) I denoted supremum of OTM-ew as $E$. Are you using a specific symbol (perhaps $\eta$) to denote it? (or $\eta$ is little different?) (2) For all $\alpha<E$ ($E$ being sup of OTM-ew) is it true that there exists an $E_0<E$ such that no program exists so that the well-order/code for all values in interval $[E_0,E)$ is never stabilized before $\omega^L_1$? $\endgroup$
    – SSequence
    Oct 22 '19 at 20:30
  • $\begingroup$ Also currently, part-(B) in the question may look a bit weird. At the time of posting, I didn't realize that I was implicitly making the assumption mentioned as (2) (about lack of $E_0$) in comment above. $\endgroup$
    – SSequence
    Oct 22 '19 at 20:37
  • 1
    $\begingroup$ The $\Sigma_{2}$-theory of a structure is the set of $\Sigma_{2}$-formulas that hold in that structure. For the notion of a $\Sigma_{2}$-formula, see en.wikipedia.org/wiki/L%C3%A9vy_hierarchy . (1) $\eta$ is such that $L_{\eta}$ contains all codes for OTM-ew ordinals. This indeed coincides with the supremum of the OTM-ew ordinals, which is your E. I still don't really understand (2). $\endgroup$
    – M Carl
    Oct 22 '19 at 20:56
  • 1
    $\begingroup$ 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$. $\endgroup$
    – M Carl
    Oct 23 '19 at 6:12
  • 2
    $\begingroup$ You are quite right, we need the smallest $\eta$ such that $L_{\eta}\prec_{\Sigma_{2}}L$, not just equal theory. In the published version of the paper above, this is stated correctly (see Lemma 3.7 in sciencedirect.com/science/article/abs/pii/S0168007217301495 ). We should probably update the arxiv-version to accomodate this. Thanks for pointing this out, I am editing my answer accordingly. $\endgroup$
    – M Carl
    Nov 4 '19 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.