**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](http://repository.cmu.edu/philosophy/48/)), 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?
> 
> 
> 



About primitively recursively recognizable ordinals
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).)


