4
$\begingroup$

Let $A$ and $B$ denote two countably infinite sets of ordinals.

Let $W_A$ denote the supremum of ordinals writable by Ordinal Turing Machines with the set $A$ given as the source of parameters. That is, for any element $\tau$ of $A$, a $\tau$-th cell of the input tape is marked with $1$ before the start of a computation.

Similarly, let $W_B$ denote the supremum of ordinals writable by Ordinal Turing Machines with the set $B$ given as the source of parameters. That is, for any element $\tau$ of $B$, a $\tau$-th cell of the input tape is marked with $1$ before the start of a computation.

Here “an ordinal writable by Ordinal Turing Machines” implies a countable ordinal $\alpha$ such that an Ordinal Turing Machine halts with an infinite binary sequence (written in the initial segment of length $\omega$ on the output tape) which encodes a well-ordering of natural numbers of order-type $\alpha$.

Question: do there exist a pair of $A$ and $B$ such that the supremum of all elements of $A$ is greater than the supremum of all elements of $B$, yet $W_A < W_B$? If no, why? The question separates into two possible situations: (i) an element in $A$ or $B$ may be uncountable; (ii) all elements in $A$ and $B$ are countable.

$\endgroup$
12
  • $\begingroup$ Could you clarify whether the computations are provided with all members of A as input, or merely with one element (or finitely many?) at a time? $\endgroup$ Jul 13 at 5:52
  • $\begingroup$ @JoelDavidHamkins: the first assumption is correct: all elements (of the corresponding set) are used as parameters (simultaneously). That is, before the start of any computation, we assume that a $\tau$-th cell is marked with $1$ whenever $\tau$ is an element of the corresponding set ($A$ or $B$). $\endgroup$ Jul 13 at 6:09
  • $\begingroup$ @lyricallywicked I didn't read "countably infinite" at the beginning of question. I thought that $A$ and $B$ could be countably finite. What about an example like this (modification to example in deleted comment): Assume $V=L$. Take $A=\{x\in \omega_1+\omega \,|\, x \geq \omega_1\}$. Now for a "sufficiently large" countable ordinal $\beta$ we can take the set $B=\{x \in \beta+\omega \,|\, x \geq \beta \}$. We will have $W_A<W_B$ and also $sup(A)=\omega_1+\omega>sup(B)=\beta+\omega$. $\endgroup$
    – SSequence
    Jul 13 at 6:28
  • $\begingroup$ @SSequence: so if an element of $A$ may be uncountable, then such pair exists, but if all elements in $A$ and $B$ are necessarily countable, then such pair does not exist? $\endgroup$ Jul 13 at 6:50
  • 1
    $\begingroup$ @lyricallywicked It seems to me that there should be a simple example for all elements of $A$ and $B$ being countable too (if I am not missing something). Once again assuming the setting of $V=L$, take $A=\{ x \in \omega \cdot 2 \,|\, x \geq \omega\}$. Take $B$ to be a sufficiently complicated subset of $\omega$. It seems that we will have $W_A<W_B$ and yet we have $sup(A)=\omega \cdot 2>sup(B)=\omega$. This does leave the possibility of all elements of both $A$ and $B$ being uncountable ordinals. $\endgroup$
    – SSequence
    Jul 13 at 7:12
6
$\begingroup$

The answer is yes. In fact, you can make the difference enormous.

First, let me construct a certain set of ordinals.

Lemma. There is a countable set $X$ of ordinals such that:

  1. Every OTM program that halts with $X$ as input, halts strictly before $\sup X$.
  2. If a program does not halt with $X$ as input, then there is no countable end-extension $Y\supset X$ for which the program would halt on input $Y$.

Proof. We can construct $X$ in stages. Enumerate the programs $p_0$, $p_1$, and so on. To begin, start with any countable set $X_0$. If $X_n$ is defined, ask whether there is some countable end-extension of it to $X_{n+1}$, extending only above the space used by the earlier programs, in such a way that $p_n$ halts with this new input oracle. Let $X=\bigcup_n X_n$ be the limit oracle. This set is countable, and it has the two properties by construction. The computation of any program that halts was preserved, since the new ordinals were added only beyond the use of that program. And if a program does not halt with $X$, then no end-extension would make it halt, since otherwise we would have done so at the stage that that program was considered. $\quad\Box$

To form the desired sets $A$ and $B$, let $\alpha$ be any ordinal larger than $\sup X$. Let $A=X\cup\{\alpha+n\mid n\in\omega\}$. And let $B=\omega\cup\{\alpha\}$.

Notice that $\sup B<\sup A$. But by the lemma, the possible outputs of computations with $A$ are the same as the possible outputs from $X$, since $A$ end-extends $X$. Basically, the extra stuff we added on top of $A$ was no help in any computation, since all the computations used only the $X$ part and never got out to $\alpha$. But with $B$ as an oracle, we can search for the input $\alpha$ and thereby use $\alpha$ in effect as an input. So anything that $\alpha$ can write is also $B$-writable. In particular, with $B$ we can give $\alpha$ itself as output, but all ordinal outputs with $A$ are less than $\alpha$.

(If you want to consider reals coding ordinals, then we can find an $\alpha$ such that from $\alpha$ we can write a real coding an ordinal bigger than any ordinal coded by output from $X$. For this, we do the whole construction inside $L$, so $X$ is in $L$, and then pick $\alpha$ so that in $L_\alpha$ we can define a real coding an ordinal larger than the countably many ordinals coded by reals output by $A$. Now, from $B$ we can compute $\alpha$ and therefore $L_\alpha$ and therefore give this real as output.)

By choosing $\alpha$ suitably, therefore, we shall have $B<A$ but $W_B>W_A$, as desired.

Moral. The main idea is that we hid $\alpha$ from $A$, since it got lost in the complexities of $X$, and no program could find $\alpha$ at the top. But $\alpha$ is not hidden in $B$, because it is the only infinite ordinal in $B$, and so a program can easily find it.

$\endgroup$
1
  • $\begingroup$ You accepted my answer, and I thank you, but I think that the solution of SSequence may be superior, being simpler. So if it is posted, please feel free to change the acceptance. $\endgroup$ Jul 13 at 8:35
5
$\begingroup$

Writing an answer because it was suggested/advised. I will assume constructibility for simplicity. Also, I will assume writeable to mean as written in second last paragraph of question. Going through various examples:

(1) All elements of $A$ are countable and all elements of $B$ are uncountable.

Take $A=\{x \in \omega_1+\omega \,|\, x \geq \omega_1\}$. Now take a "sufficiently large" countable ordinal $\beta$ such that $W_A<\beta$. We can take the set $B=\{x∈\beta+\omega \,|\, x \geq \beta\}$. Since $W_B>\beta$, we will have $W_A<W_B$ and also $\sup(A)=\omega_1+\omega>\sup(B)=\beta+\omega$.

(2) All elements of both $A$ and $B$ are countable.

Take $A=\{x \in \omega \cdot 2 \,|\, x\geq \omega\}$. Take $B$ to be a sufficiently complicated subset of $\omega$. It seems that we will have $W_A<W_B$ and yet we have $\sup(A)=\omega \cdot 2>\sup(B)=\omega$. It seems that the point is that the "reach" of the sets $A$ and $B$ (measured by their supremum) doesn't relate to $W_A$ and $W_B$.

Let $C_0$ be the supremum of halting times (empty input, no parameters). If we want to be more detailed here, we want an accidentally writeable real $r$ that, for some specific program $\phi_n$, appears on the initial $\omega$ length of tape after time $C_0$. This way we will have $W_A=C_0$ and $W_B>C_0$.

As a corollary (which we don't necessarily need though), it is fairly easy to show that whenever $r$ appears for any other program $\phi_i$ (with $i \neq n$) on the initial $\omega$ length of tape, it will have to appear after time $C_0$.

(3) All elements of both $A$ and $B$ are uncountable.

Take $A=\{x \in \omega_2+\omega \,|\, x\geq \omega_2\}$. Now take "sufficiently large" countable ordinal $\beta$ such that $W_A<\beta$. Now take the set $B=\{x \in \omega_1 \cdot 2 \,|\, x \geq \omega_1+\beta \}$. It is reasonably clear that $W_B>\beta$.

We have $\sup(A)=\omega_2+\omega >\sup(B)=\omega_1 \cdot 2$ but $W_A<W_B$.


This covers some of the combinations. This leaves a few of them, but it does not seem that something completely different would be required in those cases too.

$\endgroup$
2
  • $\begingroup$ As I mentioned that there can be number of other combinations. For example, $A$ or $B$ may contain both countable and uncountable elements which greatly increases the number of combinations. However, none of those cases seem to be substantially different (I haven't tried to look at them exhaustively though). $\endgroup$
    – SSequence
    Jul 13 at 10:13
  • $\begingroup$ "I will assume writeable to mean as written in second last paragraph of question" — I don't know why I added that paragraph to the original version of the question. It was by mistake. If I was interested in uncountable parameters, there was no point in definining writability this way: no matter how we choose the set $A$, even a single countable ordinal allows to obtain an arbitrarily large supremum of writable ordinals. $\endgroup$ Jul 14 at 2:43
3
$\begingroup$

I believe there are some simpler direct possibilties here? Let $A=\omega +1$. Then $(W_\varnothing =) W_A = \beta$ for some countable ordinal $\beta$. Let $B\subseteq \omega$ be a code of a wellorder of type $\beta$. Then $W_B>W_A$. If you want (either of) $A$ or $B$ to have uncountable ordinals, let $A'=\omega \cup\{\omega_1+1\}$ and $B'=\{\omega_1 \}\cup \bar B$ where $\bar B\subseteq \omega$ and codes a wellorder of type $W_{A'}$. Again $W_{B'}>W_{A'}$.

$\endgroup$

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.