Skip to main content
3 of 7
deleted 4438 characters in body
SSequence
  • 881
  • 1
  • 5
  • 10

Relation between $\eta$ and $\omega^L_1$

I posted this question on MSE (link: Eventual Writability (general)) about 10 days ago. The current version of this question is quite similar to the one posted there, except that I have added a shorter version of the main statement at the beginning.

Other than that, I will perhaps add some details later-on (probably few weeks). Though the question, in current form, is in reasonably good format (I think) because I edited it before once (about five days ago) to make it more organized.


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.

Short Version:

If the answer to part-(A) below is positive then why can't we set a variable whose value stablizes to $\omega^L_1$ (never to be changed again). And, in that case, then why can't we set a variable whose value stablizes to $\eta$ itself?

Long Version:

For the rest of the post I use $\omega_1$ to mean $\omega^L_1$. 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.

[EDIT:] This outline might make it easier to understand what I am trying to say below under the given heading [END]

$\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 was mentioned by MCarl in comments below the answer (in the MSE version of the question), 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$.

SSequence
  • 881
  • 1
  • 5
  • 10