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?

up vote 5 down vote accepted

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

  • 1
    Thanks, this clarifies a lot of things, and I now realize why my reasoning as to why $L_γ\mathrel{\preceq_1}L_β$ with $γ<β$ implies $γ$ not p.r.-recognizable, was incorrect. I do have three small questions which you might still clarify, though: • (A) Can you remind me (or provide a reference) why the smallest $α$ s.t. $L_α\models A$ is p.r.-recognizable? • (B) Could you detail your final comment? • (C) Do you think that the first p.r.-reflecting is what you called $β_0$ and that the first p.r.-recognizable after that is $β$ or do you expect complications? – Gro-Tsen Aug 6 '17 at 18:23
  • (Sorry I had missed your edit. I don't know why MO didn't notify me.) Great answer, and thanks again for all the clarifications! – Gro-Tsen Aug 8 '17 at 13:48

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.