Skip to main content
6 of 7
added 2075 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 a highly abridged version of the one posted there. Let's write "accidentally writable" and "eventually writable" as AW and EW respectively. See definition-3.10 (page-8) here for the definitions. 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. Let's use the symbols $\mathcal{A}$ and $\eta$ for the ordinals in (ii) and (iv) respectively.

Short Version:

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$". 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$).

This outline might make it easier to understand what I am trying to say (in what follows). $\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$.

EDIT:

The question essentially depends on at least some code for arbitrary $\alpha<\eta$ stabilizing at times $<\omega^L_1$. Unfortunately, since I didn't mention it right at the beginning of the question, this is why it might have seemed confusing.

But my reason for edit is mostly related to the answer and the discussion related to it (and this might be too long for a comment). Given the variable $v$ (in the question), each time when its increase is triggered we can flash the output (for example, in the outline I linked above, this would occur within the "if" condition). In the answer given to the question, what I have called variable $v$, more or less corresponds to the position of "red mark". This flashing is mentioned in the answer (see the last paragraph of the answer) as an example of a program whose output doesn't stabilize at any point $<\omega^L_1$.

There is still something unsettling for me regarding this. Maybe I am imagining things incorrectly (since I haven't thought about it in precise way yet) but the thing that is unsettling for me is the rate/frequency at which the variable $v$ will increase (or alternatively, the position of "red mark").

Because, at a basic thought, it seems that the frequency of this change must be fairly high. Because if $v$ stays constant for too long then a program with empty input (and with access to parameters $<p$ where $p<\omega^L_1$) would be able to halt beyond the supremum of the allowed halting positions. $p$ is a fixed value in the previous sentence. Obviously this isn't allowed, so $v$ can't be staying constant (for long stretches) below $\omega^L_1$.

But obviously above $\omega^L_1$ this is what happens (so it actually stays constant forever). Perhaps there is an easy explanation for this. I will think over it carefully (and possibly post it as a separate question) after thinking about it more closely (i.e. whether it can be made precise or not) and if it seems like a genuine question. In-case there is an easy explanation to this, it would be interesting to read.

SSequence
  • 881
  • 1
  • 5
  • 10