Skip to main content
MathOverflow

Return to Question

fix/update statements following Philip Welch's answer
Source Link
Gro-Tsen
Gro-Tsen
  • 32.5k
  • 5
  • 88
  • 375

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

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

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

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

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

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

Source Link
Gro-Tsen
Gro-Tsen
  • 32.5k
  • 5
  • 88
  • 375

About primitively recursively recognizable ordinals

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

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}$?

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, 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?