About primitively recursively recognizable ordinals

Question

Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\limsup$ in definition of primitive recursion). If there is any doubt, I refer to the notion defined in either one of the following papers:

• Stephen G. Simpson, “Short Course on Admissible Recursion Theory”, in: Fenstad, Gandy & Sacks (eds.), Generalized Recursion Theory II (Oslo 1977), North-Holland (1978), p. 355–390, esp. §2.

• Jeremy Avigad, “An Ordinal Analysis of Admissible Set Theory Using Recursion on Ordinal Notations” (J. Math. Log. 2 (2002), 91–112; preprint version here), esp. §3–4.

(If they are not equivalent, then there is something seriously wrong with my understanding of the universe.)

Definition: Say that an ordinal $\alpha$ is primitively recursively recognizable (or p.r.-recognizable for short) if the ordinal function taking the value $1$ on $\alpha$ and $0$ on every other ordinal is primitive recursive (without parameters, of course).

Remarks: Obviously every finite ordinal is p.r.-recognizable. Also, $\omega$ is p.r.-recognizable (because the predicate “$\alpha$ is finite” is p.r., for example it can be tested as $1+\alpha > \alpha$ and addition of ordinals is p.r.).

Less obviously, I think the function taking the value $1$ on the admissible ordinals and $0$ otherwise is primitive recursive (I don't have a satisfactory reference, but Hinman, Recursion-Theoretic Hierarchies, Persp. Math. Logic. 9, Springer 1978, states something slightly weaker in corollary VIII.2.19, and I think the proof he gives actually yields the statement I wrote), so the $n$-th admissible ordinal (and in particular, the Church-Kleene ordinal) is p.r.-recognizable for every finite $n$; the same should also be true of the $n$-th recursively inaccessible ordinal (and much more).

On the other hand, not every ordinal is p.r.-recognizable (because there are only countably many p.r. functions [without parameters]).

More precisely, I think that if $L_\gamma \mathrel{\preceq_1} L_\beta$ with $\gamma<\beta$ (where $\preceq_1$ means “is a $1$-elementary submodel”) then no ordinal $\alpha$ such that $\gamma\leq\alpha<\beta$ can be p.r.-recognizable, because p.r. functions are absolute for the $L_\beta$ (right?), so if $L_\beta \models \exists \alpha.\varphi(\alpha)$ with $\varphi$ a p.r. predicate recognizing an ordinal, then $L_\gamma \models \exists \alpha.\varphi(\alpha)$ and $\alpha<\gamma$. [Edit: After reading the answer by Philip Welch, I now realize why this reasoning is incorrect: in writing $L_\beta \models \exists \alpha.\varphi(\alpha)$ I implicitly assumed that $\beta$ is p.r.-closed so that no value higher than $\beta$ is used in computing $\varphi(\alpha)$.]

Question: What is the smallest non p.r.-recognizable ordinal? More precisely, how does it compare with the smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_{\alpha+1}$?

[Edit: After reading the answer by Philip Welch, I realize that the ordinal I should be asking for comparison with is the smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_{\varphi(\omega,\alpha+1)}$.]

Further comments: The smallest $\alpha$ such that $L_\alpha \mathrel{\preceq_1} L_{\alpha+1}$ is the smallest $\Pi^1_0$-reflecting ordinal, meaning $\Pi_n$-reflecting for every $n$: see Richter & Aczel, “Inductive Definitions and Reflecting Properties of Admissible Ordinals”, in: Fenstad & Hinman (eds.), Generalized Recursion Theory (Oslo 1972), North-Holland (1974), p. 301–381, specifically theorem 1.18 on p. 313&333.

For some reason, I had gotten into my head (based on §3 of the aforementioned Richter&Aczel paper) that an ordinal is p.r.-recognizable if and only if, for some (first-order, i.e., $\Pi^1_0$) statement $T$ of the language of set-theory, it is the smallest $\alpha$ such that $L_\alpha \models T$ (this would solve the above question). But there's something seriously wrong, here [edit: no there isn't], because $\alpha$ is p.r.-recognizable iff $\alpha+1$ is, and the statement “there exists a largest ordinal $\gamma$ and $L_\gamma \mathrel{\preceq_1} L$” is first-order and the first $\beta$ such that $L_\beta$ satisfies it is precisely the first $\alpha+1$ such that $L_\alpha \mathrel{\preceq_1} L_{\alpha+1}$… so I run into a contradiction and there must be something seriously wrong with what I wrote. My main goal here is to understand the source of my confusion and dispel it.

Because of this confusion, I'm also not sure whether the p.r.-recogizable ordinals are an initial segment of the ordinals. So let's make this into an:

Extra question: Are the p.r.-recognizable ordinals an initial segment of the ordinals? If not, what is the smallest ordinal which is p.r.-recognizable but which is greater than at least one non-p.r.-recognizable ordinal?

Answer 1

Call $\alpha\in On$ p.r.closed, if every p.r. set function $f$ is total on $L_{\alpha}$.

(Note (1) If $\alpha^\ast$ is the least p.r. closed ordinal $> \alpha$ then it is the next image of a point in the $\omega$'th Veblen function, so in any case is much smaller than the next admissible. Hence (2) the p.r.closed ordinals form a c.u.b. class, and in fact are c.u.b. below any admissible ordinal $>\omega$. (3) By Jensen-Karp [1] the p.r. functions on ordinals to ordinals are all the restrictions of the p.r. set functions to $On$. Hence it is easier to reason with the latter class.)

Definition Let $\delta$ be p.r. reflecting if for all p.r. functions $F:On\rightarrow On$, if $F(\delta)\neq 0$ then $\exists \alpha < \delta (F(\alpha)\neq 0 )$.

Then

Claim $\delta$ not p.r. reflecting iff $\delta$ is p.r. recognizable.

Now let $\beta$ be the least p.r. closed ordinal with a $\beta_0<\beta$ satisfying $L_{\beta_0}\prec_{\Sigma_1}L_\beta$. (So larger than the least $\Pi^1_0$-reflecting ordinal, but less than the least $\Pi^1_1$-reflecting ordinal.) By p.r. closure, and $\Sigma_1$-elementarity, the totality of the p.r. functions on $L_\beta$ ensures:

Lemma The least p.r. reflecting ordinal is less than or equal to $\beta_0$.

This gives an upper bound to the first p.r. reflecting, and so non-p.r. recognizable, ordinal, and will answer the first part of the Extra Quest. negatively, as we shall see below there are p.r. recognisable ordinals $>\beta$.

As an imprecise lower bound one can take the least $\Pi^1_0$-reflecting ordinal mentioned above. [Edit: This is fully answered below at (C).] (If $\gamma$ is this ordinal, and so we have $L_\gamma \prec_{\Sigma_1}L_{\gamma +1}$, it is easy to see all ordinals $\tau < \gamma$ are p.r. recog. as for any such $\tau$ there is some sentence $B$ so that $L_\tau$ is the least level of the $L$-hierarchy where $B$ is true. But $\gamma+1$ is itself p.r. recog. as the first $\tau$ where $L_\tau$ has a proper $\Sigma_1$-substructure, etc., etc. (This answers the second part of the original Question) Similar statements hold for larger stretches of the ordinals $[0,\gamma']$ for $\gamma + 1 < \gamma'$.)

To find the least upper bound of the p.r. recog. ordinals, one can reason as follows:

If the $\Sigma_1$ sentence $A$ is first true at some stage $L_{\delta}$, then $\delta$ is p.r. recog. Consequently the p.r. recog. ordinals will be cofinal in $\sigma_1$ the least $\Sigma_1$-stable ordinal, i.e. the least ordinal with $L_{\sigma}\prec_{\Sigma_1}V $ (as new $\Sigma_1$-sentences become true cofinally in $\sigma_1$). Thus for example if $\delta$ is least so that $L_\delta$ is a $ZF^-$ model, it will be p.r. recog. Note then that no ordinal $\geq \sigma_1$ can be p.r.recongizable, as otherwise this would be a new $\Sigma_1$ fact true at a stage beyond $\sigma_1$. Thus:

Lemma The supremum of the p.r. recognisable ordinals is $\sigma_1$.

If $\tau_0$ is the least p.r. reflecting ordinal, and $\tau >\tau_0$ the least p.r. closed ordinal above that, then the answer to the second question of the Extra Question, is to take $\tau +1$. The $\Sigma_1$ statement that "there exists such a pair $\tau_0<\tau$ " can be used to recognise this ordinal.

Comment: if the definition of recognizable is adjusted (call it recognizable*) so that $\alpha$ is recognizable* if for some p.r. function $F$, $F$ is everywhere $0$ except that for some (unique) $\tau$ $F(\tau)=\alpha$, (and thus $\alpha$ is the sole non-zero value that $F$ takes) then the recognizable* ordinals are precisely those $< \sigma_1$.

[1] R.B. Jensen and C. Karp Primitive Recursive set functions, in Proceedings of Symposia in Pure Mathematics,vol.13 Part 1, "Axiomatic Set Theory", Ed. D. Scott, AMS, 1971, pp 143-167.

---

Edit added to address Gro-Tsen's queries (see comment below) and intended to complete both the original Question and its second reformulation:

(A) The function $F(\delta)=L_\delta$ is p.r. (See Devlin, "Constructibility" but I think it is in [1] anyway.) Satisfaction is likewise p.r., hence the function:

$G(\delta)=1$ if $L_\delta \vDash $ '' $A\wedge \forall\delta' L_{\delta'} \vDash \neg A$'';

$G(\delta)=0$ otherwise

is p.r. and gives that the least $\delta$ with $L_\delta\vDash A$ is p.r. recognizable.

(B) Let $\beta<\sigma_1$ . We want that $\beta$ is p.r. recognizable*. Let $A$ be a $\Sigma_1$ sentence that is first true at some $\gamma \in (\beta, \sigma_1)$. By standard arguments the $<_L$-least bijection $f_\gamma:\omega\leftrightarrow \gamma$ is definable over $L_\gamma$. Suppose $f_\gamma(n)=\beta$. By the kind of argument in (A) we see that $ \gamma$ is p.r. recog*. But then so is $L_{\gamma+1}$ and $f_\gamma$. Put these facts together to build a p.r. function $G$ whose only non-zero value is $G(\gamma)=\beta$.

(C) We answer this (and, using the first Lemma above, finish the original Question) by:

Lemma Let $\alpha < \beta_0$. Then $\alpha$ is p.r. recog. Hence the least p.r. reflecting ordinal is $\beta_0$ which in turn is the least non-p.r. recog. ordinal.

Proof: Say that $\alpha$ begins a gap if $\exists \delta ( L_\alpha \prec_{\Sigma_1} L_\delta)$. We say that $[\alpha,\delta]$ is a gap, if $\alpha$ begins a gap, and $\delta$ is maximal with $L_\alpha \prec_{\Sigma_1} L_\delta$.

$\bullet$ If $\omega < \delta < \beta_0$ is not in any gap, then we are sufficiently low down in the $L$-hierarchy where there is a $\Sigma_1$ sentence $A=A(\delta)$ so that

$L_{\delta+1}\vDash $ ``$A\wedge\forall \delta’<\delta L_{\delta’ + 1}\vDash \neg A$ ‘’. As argued above at (A), this makes $\delta+1$ and so $\delta$ p.r. recog.

We just need the ordinals of gaps $[\alpha,\delta]$ with $\alpha <\beta_0$ to be p.r. recognizable.

So let $[\alpha,\delta]$ be such a gap. We show that $\alpha$ is p.r. recog. and variants of the argument suffice for the other ordinals in the gap. Then $\alpha < \delta < \alpha^* <\beta_0$. Using (un)/pairing functions (which are p.r.) etc. one has that the closure of $\{\alpha\}$ under p.r. functions includes all ordinals up to $\alpha^*$. So let $F$ be a p.r. function, with $F(\alpha)=\delta’$ for some $\delta’\in (\delta,\alpha^*)$. Let $A=A(\delta’)$. Let:

$G(\xi) = 1$ if $L_{F(\xi)+1}\vDash A$;

$G(\xi) = 0$ otherwise.

Then $G$ witnesses that $\alpha$ is p.r. recognizable, so we are done. Q.E.D.

(The definition of $\beta_0$ and $\beta$ is that given in Gro-Tsen's second formulation of question, in terms of the Veblen function (if I understand the terms correctly).)