Proof. This is simply because if $\prec $ is a wellorder (in the real world) which belongs to $L_\alpha $ , then $L_\alpha $ can recursively construct an isomorphism from $\prec $ to an ordinal, so if $\eta _\beta <\alpha $ , then $\eta _{\beta +1}\leq \alpha $ .

Proof. This is immediate from the previous lemma.

Proof. Let $\phi $ be the $\Sigma _1$ formula which defines over $L_\beta $ a wellordering of length $\gamma $ . Then, the formula

$$\begin{align*}\phi^*(x,y,\beta)\leftrightarrow L_\beta\models \phi(x,y)\end{align*}$$

is $\Sigma _0$ (thus $\Sigma _1$ ) over $L_{\eta _\alpha }$ with parameters in $L_{\eta _\alpha }$ .

Proof. This is proved by induction. The limit stages are immediate. Supposing $\eta _\alpha $ satisfies those closure properties and $\beta ,\gamma $ are $\eta _\alpha $ -r.e., we can use the fact that $\eta _\alpha $ is multiplicatively indecomposable (thus closed under coding of tuples) to combine the definitions of $\beta ,\gamma $ into $\eta _\alpha $ -r.e. wellorderings of length $\beta +\gamma $ and $\beta \cdot \gamma $ . Closure under the Veblen functions is a bit tricker and will not be used below, but it can be done by lifting the proof that $\omega _1^{ck}$ is closed under the Veblen functions (see, e.g., [Reference Rathjen, Weiermann, Cooper and Sorbi19]).

Proof. Let $\prec $ be such a linear order. Using the closure properties provided by Lemma 2.4, we may construct inside of $L_{\eta _{\alpha +1}}$ an isomorphism

$$\begin{align*}i_x:\prec\upharpoonright x \to \beta_x\end{align*}$$

for some $\beta _x$ , for each x in the wellfounded part of $\prec $ . The construction of $i_x$ is by transfinite recursion on $\prec \upharpoonright x$ and requires $\beta _x$ stages, so it belongs to $L_{\eta _\alpha + \beta _x}$ . Since $L_{\eta _{\alpha +1}}$ is additively indecomposable, $i_x \in L_{\eta _{\alpha +1}}$ . The function f given by $f(x) = \beta _x$ is partial $\Delta _1$ over $L_{\eta _\alpha +1}$ , with domain a subset of $L_{\eta _\alpha }$ which need not be $\Delta _1$ over $L_{\eta _\alpha +1}$ . Consider the set

$$\begin{align*}A = \{x<\eta_\alpha: x \in {\text{dom}}(f)\}.\end{align*}$$

Thus, A is $\Sigma _1$ -definable over $L_{\eta _\alpha +1}$ . A is precisely the wellfounded part of $\prec $ , for if $x \in \text {wfp}(\prec )\setminus A$ , then $\prec \upharpoonright x$ cannot be isomorphic to an ordinal smaller than $\eta _{\alpha +1}$ (otherwise $f(x)$ would be defined), so $\prec \upharpoonright x$ is an $\eta _{\alpha }$ -r.e. wellorder of length at least $\eta _{\alpha +1}$ , which contradicts the definition. Using A we can replicate the proof of König’s lemma: by induction on $i\in \mathbb {N}$ , define $x_{i+1}$ to be the $<_L$ -least $x \not \in A$ such that $x \prec x_i$ . This defines an infinite descending chain through $\prec $ .

As for the complexity of this sequence s, we have $x_i <\eta _\alpha $ for each i, and the restriction of $<_L$ to $L_{\eta _\alpha }$ is $\Sigma _1$ over $L_{\eta _\alpha }$ and hence an element of $L_{\eta _\alpha +1}$ . Therefore, s is the unique $\omega $ -sequence all of whose elements $x_i$ have the following properties:

1. (1) $x_i \not \in A$ ;

2. (2) $x_{i+1} \prec x_{i}$ ;

3. (3) for all $y\in \eta _\alpha $ , if $y \prec x_i$ and $y\not \in A$ then $x_{i+1} <_L y$ .

The first condition is $\Pi _1$ over $L_{\eta _{\alpha +1}}$ ; the second is $\Delta _0$ ; and the third is $\Pi _2$ , since $x_{i+1}<_L y$ is equivalent to $L_{\eta _\alpha }\models x_{i+1}<_L y$ (we cannot conclude that the third condition is $\Sigma _1$ , because $\eta _{\alpha +1}$ may not be admissible).

Proof. This follows from the preceding argument, using the observation that if the range of f is bounded below $\eta _{\alpha +1}$ , say $f[\eta _\alpha ] \subset \beta < \eta _{\alpha +1}.$ Then, A is $\Sigma _1$ -definable over $L_\beta $ .

Proof. Suppose first that $\eta _\alpha $ is a successor effective cardinal and let $\beta $ be its predecessor. Since $\eta _\alpha $ is locally countable, there is a real $x \in L_{\eta _\alpha }$ coding a wellordering of $\mathbb {N}$ of length $\beta $ . Let $\gamma $ be least such that $x \in L_{\gamma +1}$ . Then, for each $\xi $ ,

$$\begin{align*}L_{\xi} \subset L_{\xi}[x] \subset L_{\gamma+1+\xi}.\end{align*}$$

Since $\eta _\alpha $ is additively indecomposable, we have

$$\begin{align*}L_{\eta_\alpha} = L_{\eta_\alpha}[x].\end{align*}$$

The proof that $\omega _1^{ck}$ is the least admissible ordinal (see [Reference Barwise7]) relativizes and shows that $\omega _1^x$ , the supremum of x-recursive ordinals, is least such that $L_{\omega _1^x}[x]$ is admissible. Thus,

$$\begin{align*}L_{\eta_\alpha^+} = L_{\omega_1^x} = L_{\omega_1^x}[x].\end{align*}$$

Therefore, there are $\eta _\alpha $ -r.e. wellorderings of lengths cofinal below $\eta _\alpha ^+$ and the result follows.

The previous argument applies also to the case that $\eta _\alpha $ is a limit effective cardinal, but there is a largest admissible smaller than $\eta _\alpha $ ; the remaining case is that $\eta _\alpha $ is an inadmissible limit of admissibles. This case will not be necessary below, but it is good to note. To obtain it, follow the argument of Gostanian [Reference Gostanian9, Theorem 2.1] replacing ${\mathsf {KP}}$ by ${\mathsf {KPl}}$ throughout. This shows that if $\alpha $ is a locally countable limit of admissibles, then the $\alpha $ -recursive wellorders are cofinal below $\alpha ^+$ unless $\alpha $ is $\Sigma ^1_1$ -reflecting. This is enough to yield the result, since $\Sigma ^1_1$ -reflecting ordinals are all admissible.

Proof. If T is a wellfounded $\alpha $ -r.e. tree, then its Kleene–Brouwer linearization $\prec _T$ is an $\alpha $ -r.e. wellorder. A simple induction shows that the length of $\prec _T$ is at least the rank of T. Conversely, suppose $\prec $ is an $\alpha $ -r.e. wellorder and let $T_\prec $ be the tree of all descending chains through $\prec $ ordered by end-extension. Then this is a wellfounded $\alpha $ -r.e. tree and—as before—a simple induction shows that its rank is at least the length of $\prec $ .

Proof. It follows from Lemma 2.7 that for all $i \in \mathbb {N}$ with $i \neq 0$ , $L_{\eta _{\xi + i}}$ is not locally countable. This implies in particular that for each i,

$$\begin{align*}\mathcal{P}(\mathbb{N}) \cap L_\gamma = \mathcal{P}(\mathbb{N}) \cap L_{\eta_{\xi+i}} = \mathcal{P}(\mathbb{N}) \cap L_{\eta_\xi},\end{align*}$$

so $L_{\gamma }$ is also not locally countable. It remains to show that

$$\begin{align*}L_{\gamma}\models \text{"every wellfounded tree has a rank."}\end{align*}$$

If $\prec $ is a linear ordering in $L_\gamma $ , then $\prec $ is $\eta _{\xi +i}$ -r.e. for some i, by Lemma 2.3. Thus, there are two possibilities: either $\prec $ is wellfounded (in the real world) and thus isomorphic to some ordinal ${<}\eta _{\xi +i+1}$ . If so, then such an isomorphism can be constructed within $L_{\eta _{\xi +i+1}}$ and belongs to $L_\gamma $ . Otherwise, $\prec $ is illfounded (in the real world) and thus has an infinite descending chain in $L_{\eta _{\xi +i}+1}$ (by Lemma 2.5) and thus in $L_\gamma $ .

Proof. Clearly $\eta _{\zeta +\omega }$ is inadmissible. We prove that for each i, $\eta _{\zeta +i}<\theta $ and $\eta _{\zeta +i}$ is inadmissible. This implies that $\eta _\zeta $ is not $\omega $ -Gandy and that $\eta _{\zeta +\omega }\leq \theta $ , so that $\eta _{\zeta +\omega } = \theta $ by Lemma 3.5 and the minimality of $\theta $ .

Inductively, suppose that $\eta _{\zeta +i}<\theta $ and that either $i = 0$ or $\eta _{\zeta +i}$ is inadmissible.

Proof. Suppose otherwise and let $\beta \neq \eta _{\zeta +i}$ be least such that there is an infinite descending chain through $\prec $ in $L_{\beta +1}$ and let d be such a chain. By the definition of $\theta $ , $\beta <\theta $ . We have

$$\begin{align*}\zeta = \omega_1^{L_\theta} = |\eta_{\zeta+i}|^{L_\theta},\end{align*}$$

as witnessed by a bijection $f: \eta _{\zeta +i} \to \zeta $ . Using the hypothesis that each $\eta _{\zeta + j}$ is inadmissible for $0 < j \leq i$ , we see that there is no admissible ordinal between $\zeta $ and $\eta _{\zeta +i}$ , and thus such a bijection is definable over $L_{\eta _{\zeta +i}}$ . Then, $f[d]$ is an $\omega $ -sequence of ordinals countable in $L_{\theta }$ which belongs to $L_{\beta +1}$ and not to $L_{\eta _{\zeta +i}+1}$ . By Gödel’s condensation lemma, $\zeta $ is no longer a cardinal in $L_{\beta +1}$ , which is a contradiction.

It follows from the first claim that the set of indices of $\eta _{\zeta +i}$ -r.e. wellorders is definable over $L_{\eta _{\zeta +i} +1}$ . Thus, there is a linear order in $L_{\eta _{\zeta +i} + 2}$ (and thus in $L_\theta $ ) which is longer than all $\eta _{\zeta +i}$ -r.e. wellorders (namely, the sum of all $\eta _{\zeta +i}$ -r.e. wellorders) and thus has length at least $\eta _{\zeta +i+1}$ . Therefore, $\eta _{\zeta +i+1} < \theta $ .