4
$\begingroup$

According to Lemma 3.14 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”, there is a real $x$ in $L$ which is recognizable from some ordinal $\alpha$ that is countable in $L$, but not from $\omega_1$.

But I have the following question: do there exist a countable ordinal $\alpha < \omega_1$ and a real $x$ such that there exists an OTM-program which eventually writes $x$ in the parameter $\alpha$, but there does not exist an OTM-program which eventually writes $x$ in the parameter $\omega_1$?

Here “eventually writes $x$” implies that an infinite binary sequence written in an initial segment of length $\omega$ of the output tape stabilizes, and this stable value is equal to $x$. Additionally, “in the parameter $\alpha$” implies that all machines start a computation with zeroes written on all cells of all tapes, except that the symbol $1$ is written on an $\alpha$-th cell of the input tape.

$\endgroup$
7
  • 4
    $\begingroup$ Unless I'm missing something, for each ordinal $\alpha$ the set of reals eventually writeable in parameter $\alpha$ is countable in $L$. So you just need to show that there are $L$-uncountably-many reals which are eventually writeable in some ordinal parameter. $\endgroup$ Jul 6, 2021 at 4:26
  • 3
    $\begingroup$ Noah, why don't you post that as an answer? Namely, there are only countably many reals eventually writable from parameter $\omega_1$, but for every countable ordinal $\alpha$, we can write the theory of $L_\alpha$. There are uncountably many such theories in $L$ because every countable ordinal $\beta$ is definable without parameters in some such $L_\alpha$, and so the digits of the $L$-least real coding $\beta$ is part of that theory. So some such real is writable from a countable $\alpha$ but not from $\omega_1$. $\endgroup$ Jul 6, 2021 at 8:29
  • 1
    $\begingroup$ I think the answer to the question is positive in the sense that even with parameter $\omega_1$ it wouldn't be possible to (eventually) write the code (well-order relation on $\mathbb{N}$) of some ordinal $\beta<\omega^L_1$. However, given any arbitrary ordinal $\alpha<\omega^L_1$, one can always (eventually) write the code for $\alpha$. So we can just take the code of $\beta$ as the real $x$ required in the question. $\endgroup$
    – SSequence
    Jul 6, 2021 at 9:07
  • 1
    $\begingroup$ Is the answer also "Yes" if "eventually writable" is replaced with "antirecognizable"? Is the set of reals antirecognizable in the parameter $\omega_1$ countable in $L$? $\endgroup$ Jul 6, 2021 at 9:12
  • 1
    $\begingroup$ Yes, that is equivalent to what I said. And so there are only countably many (for any fixed input), because each program determines at most one such real. $\endgroup$ Jul 6, 2021 at 9:50

1 Answer 1

1
$\begingroup$

Firstly, the question was already answered before my comment. This is how I thought about it (perhaps this slow thinking might be helpful for other non-experts, though I am not quite certain about this).

(1) In general, first we can observe that, given an ordinal parameter $\alpha$, if an ordinal $x$ is eventually writeable then every ordinal less than $x$ is also eventually writeable.

(2) Now observe that for any arbitrary ordinal $\alpha<\omega^L_1$, given the parameter $\alpha$, the code of $\alpha$ is eventually writeable. By code of $\alpha$ I mean the well-order (on $\mathbb{N}$) with order-type $\alpha$.

(3) Finally observe that if a real number $r$ (seen as a subset of $\omega$) is eventually writeable using some ordinal parameter $\alpha$ then it is also "ordinal computable" using suitably large ordinal parameters. To be specific, suppose the program with index $e$ when given the parameter $\alpha$ permanently stabilizes its first $\omega$ cells to $r$ beyond some time $T$. Or to put it other way, $T$ is the stabilization time for the real $r$ given the ordinal parameter $\alpha$ and program $\phi_e$.

Now, alternatively, we can think of $r$ as being computed with ordinal parameters $\alpha$ and $T$. This re-phrasing can be relevant (and is relevant in the context of this question), due to equivalence of "ordinal computation with parameters" with "constructible subsets of ordinals".


Now the answer to the question is implicit in the above points. That is, suppose that using the parameter $\omega_1$ it was possible to eventually write the code for some ordinal $\geq \omega^L_1$. By point-(1) above, then using the parameter $\omega_1$ it would also be possible to eventually write the code for some ordinal $\omega^L_1$ itself. However, now by point-(3) that would imply that code of $\omega^L_1$ is constructible (which is clearly false).

Hence we conclude that our original assumption was incorrect and hence using the parameter $\omega_1$ it is impossible to eventually write the code for some ordinal $\geq \omega^L_1$. That means that there exists a countable ordinal $\beta<\omega^L_1$ whose code is not eventually writeable using the parameter $\omega_1$. But now, using point-(2), the code for $\beta$ is writeable using the ordinal parameter $\beta$.

$\endgroup$
1
  • $\begingroup$ "(2) Now observe that for any arbitrary ordinal $\alpha<\omega^L_1$, given the parameter $\alpha$, the code of $\alpha$ is eventually writeable." I guess instead of "the code of $\alpha$", it should be something like "some code for $\alpha$". $\endgroup$
    – SSequence
    Jul 6, 2021 at 10:25

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.