Patterns of resemblance and Bachmann-Howard fixed points

Abstract

Timothy Carlson’s patterns of resemblance employ the notion of $\Sigma _1$-elementarity to describe large computable ordinals. It has been conjectured that a relativization of these patterns to dilators leads to an equivalence with $\Pi ^1_1$-comprehension (Question 27 of A. Montalbán’s “Open questions in reverse mathematics”, Bull. Symb. Log. 17(3)2011, 431-454). In the present paper we prove this conjecture. The crucial direction of the equivalence (towards $\Pi ^1_1$-comprehension) is reduced to a previous result of the author, which is concerned with relativizations of the Bachmann-Howard ordinal.

1 Introduction

In their simplest form, T. Carlson’s patterns of resemblance are defined as follows (cf. [5, Section 10]): Consider the language $\mathcal {L}=\{\le ,\le _1\}$ with two binary relation symbols. We only interpret this language in structures that have a set of ordinal numbers as universe, and $\le$ is always interpreted as the usual order between ordinals. Let us agree that each ordinal is identified with its set of predecessors. We now determine the interpretation of $\le _1$ by the recursive clause

$$\begin{aligned} \alpha \le _1\beta \quad :\Leftrightarrow \quad \alpha \,\text { is a}\, \Sigma _1\text {-elementary}\, \mathcal {L}\text {-substructure of}~\beta . \end{aligned}$$

The right side is equivalent to the conjunction of $\alpha \le \beta$ and the following: For all finite $X\subseteq \alpha$ and $Y\subseteq \beta \backslash \alpha$, there is a $\widetilde{Y}\subseteq \alpha$ and a bijection $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ that fixes X and satisfies $f(\gamma )\le f(\gamma ')\Leftrightarrow \gamma \le \gamma '$ and $f(\gamma )\le _1f(\gamma ')\Leftrightarrow \gamma \le _1\gamma '$ for all $\gamma ,\gamma '\in X\cup Y$. Note that the given condition does only depend on the restriction of $\le _1$ to $\beta \times \beta$, which can thus be defined by recursion on $\beta$.

Patterns of resemblance are attractive due to their connections with several different areas: Carlson first used them to show that epistemic arithmetic is consistent with the statement “I know that I am a Turing machine” (known as Reinhardt’s strong mechanistic thesis, see [4]). They also offer a new approach to the large computable ordinals considered in ordinal analysis, including a conjectured characterization of the proof-theoretic ordinal of full second order arithmetic (see [5, Section 13]). This viewpoint has been clarified and expanded in subsequent work of G. Wilken (see [25,26,27,28] and the joint paper [6] with Carlson). Furthermore, Carlson has pointed out similarities with the core models studied in set theory, and expressed the hope that proof-theoretic and set-theoretic approaches “will find common ground someday” (see again [5, Section 13]). The present paper establishes connections with weak set theories and reverse mathematics (a research program developed by H. Friedman [15] and S. Simpson, cf. his textbook [23]).

For the version of patterns that we have presented above, the smallest ordinal $\alpha$ such that $\alpha \le _1\beta$ holds for all $\beta \ge \alpha$ is equal to $\varepsilon _0=\min \{\gamma \,|\,\omega ^\gamma =\gamma \}$, the proof-theoretic ordinal of Peano arithmetic (see [5, Section 10] for a proof and [24, Chapter 2] for general background). The ordinals that arise become much larger if we enrich the language: Let $\le _1^+$ be defined just as $\le _1$, but with $\mathcal {L}=\{\le ,\le _1\}$ replaced by $\mathcal {L}_+=\{0,+\le ,\le _1^+\}$, for a constant 0 and a ternary relation symbol $+$ that is interpreted as the graph of ordinal addition. Now the minimal $\alpha$ with $\alpha \le _1^+\beta$ for all $\beta \ge \alpha$ is equal to the proof-theoretic ordinal of $\Pi ^1_1\textsf {-CA}_0$ (as announced in [5] and proved in [27]), which dwarfs $\varepsilon _0$. Carlson himself has suggested (see [5, Section 1] and also [20, Section 4.5]) to consider much more general extensions of the language that arise from dilators. This will be done in the present paper.

In the following we present constructions that are needed to explain our main result. The discussion will remain on a somewhat informal level, with full details deferred to Section 2 below. Let us consider the category of ordinals (still identified with their sets of predecessors) and strictly increasing functions between them. Dilators, as defined by J.-Y. Girard [16], are functors from ordinals to ordinals that preserve direct limits and pullbacks. These conditions ensure that each ordinal $\gamma <D(\alpha )$ has a unique representation of the form $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ with $\gamma _0<\dots<\gamma _{n-1}<\alpha$, where $\sigma \in D(n)$ can be seen as a constructor symbol that takes $\gamma _0,\dots ,\gamma _{n-1}$ and $\alpha$ as arguments (but not all $\sigma \in D(n)$ will be allowed as constructors). By a pre-dilator we shall mean a functor from finite ordinals to ordinals that has the categorical properties of a dilator. Via the aforementioned representations, each pre-dilator can be extended into a functor from ordinals to linear orders. If the indicated extension has well-founded values (which fails for some pre-dilators), then it corresponds to a unique dilator. Conversely, the restriction of any dilator yields a pre-dilator from which it can be reconstructed. The point is that pre-dilators are set-sized objects that can be used to represent dilators, even though we have introduced the latter as proper classes.

In general, the aforementioned representation of $\gamma <D(\alpha )$ by an expression $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ may depend on $\alpha$: for $\alpha <\beta$, the same $\gamma <D(\alpha )\le D(\beta )$ can have entirely different representations with respect to $\alpha$ and to $\beta$. The reason is that the inclusion $\iota :\alpha \hookrightarrow \beta$ may induce a function $D(\iota ):D(\alpha )\rightarrow D(\beta )$ that is not an inclusion itself (i. e., the range of $D(\iota )$ need not be an initial segment of $D(\beta )$). On the other hand, the representations are independent of $\alpha$ when D preserves inclusions. Dilators with this property are called flowers by Girard. We will work with a slightly more restrictive notion called normal dilator (previously studied in [13]), which blends Girard’s flowers with P. Aczel’s normal functors [1, 2]. If D is a normal dilator, then $\alpha \mapsto D(\alpha )$ is a normal function in the usual sense, i. e., it is strictly increasing and we have $D(\lambda )=\sup _{\alpha <\lambda }D(\alpha )$ whenever $\lambda$ is a limit ordinal. More importantly, the aforementioned representations become independent of the last component: assuming that D is normal, we write

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D \end{aligned}$$

(1)

if $\gamma$ has representation $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ for some (equivalently: for every) ordinal $\alpha$ with $\gamma <D(\alpha )$. Now consider (1) as an $(n+1)$-ary relation in $\gamma _0,\dots ,\gamma _{n-1}$ and $\gamma$. Let $\mathcal {L}_D$ be the language that contains a relation symbol for each such relation (i. e., for each constructor symbol associated with D), as well as two binary relation symbols $\le$ and $\le _1^D$. The interpretation of $\le _1^D$ is defined as the interpretation of $\le _1$ above, but with $\mathcal {L}_D$ at the place of $\mathcal {L}$. We now state our main result:

Theorem 1.1

The following are equivalent over $\textsf {ATR}_0^{\textsf {set}}$:

• (i) for any normal dilator D, there is an ordinal $\Omega$ with $\Omega \le _1^D D(\Omega +1)$,

• (ii) every set is contained in an admissible set.

The theory $\textsf {ATR}_0^{\textsf {set}}$ is a set-theoretic version of $\textsf {ATR}_0$ (one of the central systems from reverse mathematics), over which it is conservative (due to Simpson [22, 23]). We declare that $\textsf {ATR}_0^{\textsf {set}}$ contains the axiom of countability (as in [23, Section VII.3], while this axiom is marked as “optional” in [22]). Concerning statement (ii), we recall that admissible sets are defined as transitive models of Kripke-Platek set theory (see [3]). Over $\textsf {ATR}_0^{\textsf {set}}$, statement (ii) is equivalent to $\Pi ^1_1$-comprehension, another important principle of reverse mathematics (by [18, Section 7] in conjunction with [7, Section 1.4]). This shows that our base theory is weak enough to make the equivalence informative (since $\Pi ^1_1$-comprehension is known to be unprovable in $\textsf {ATR}_0$). It also reveals that Theorem 1.1 answers Question 27 from A. Montalbán’s list [20], which asks for an equivalence between statement (i) and $\Pi ^1_1$-comprehension.

The motivation for our choice of base theory will become fully transparent in Section 2. For now, we just stress that $\textsf {ATR}_0^{\textsf {set}}$ is a set theory. This allows us to work with the “semantic” definition of $\le _1^D$ that was given above. Patterns of resemblance can also be approached in a more “syntactic” way (cf. [6, 26]). Based on such an approach, one may be able to prove a variant of Theorem 1.1 with a much weaker base theory in the language of second order arithmetic. This would certainly be of interest. For the present paper, we have decided that the elegance of the semantic definition is more important than an optimal base theory.

To prove one direction of Theorem 1.1, we will show that (i) holds when $\Omega$ is the height of a suitable admissible set, as provided by (ii). Details for this direction are given in Sect. 4. The converse (and probably more surprising) direction from (i) to (ii) relies on a previous result of the author [8,9,10]. For this result it is crucial to consider dilators that are not normal (as explained in the next paragraph). If D is such a dilator, there may not be any fixed point $\alpha =D(\alpha )$. The best we can hope for is an “almost” order preserving function $\vartheta :D(\alpha )\rightarrow \alpha$. In order to make this precise, we recall that each ordinal $\gamma <D(\alpha )$ has a unique representation $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ with $\gamma _0<\dots<\gamma _{n-1}<\alpha$. We will write ${\text {supp}}_\alpha (\gamma )=\{\gamma _0,\dots ,\gamma _{n-1}\}$. Now a function $\vartheta :D(\alpha )\rightarrow \alpha$ is called a Bachmann-Howard collapse if the following holds for all $\gamma ,\delta <D(\alpha )$:

• if we have $\gamma <\delta$ and ${\text {supp}}_\alpha (\gamma )\subseteq \vartheta (\delta )$, then we have $\vartheta (\gamma )<\vartheta (\delta )$,

• we have ${\text {supp}}_\alpha (\gamma )\subseteq \vartheta (\gamma )$.

If such a collapse exists, then $\alpha$ is called a Bachmann-Howard fixed point of D. This notion can be seen as a relativization of the Bachmann-Howard ordinal, which plays an important role in ordinal analysis (see e. g. [14, 17, 21]). In [8] it has been shown that statement (ii) from Theorem 1.1 is equivalent to the assertion that every dilator has a Bachmann-Howard fixed point.

Let us stress that the notion of Bachmann-Howard collapse is most interesting when D is not normal. Indeed, if D is normal, there will be a limit ordinal $\lambda$ that is equal to $D(\lambda )$. One can then define a Bachmann-Howard collapse by

$$\begin{aligned} D(\lambda )=\lambda \ni \gamma \mapsto \vartheta (\gamma ):=D(\gamma +1)\in D(\lambda )=\lambda , \end{aligned}$$

as verified in Remark 3.1 below. The proof that $\lambda =D(\lambda )$ exists for normal D does only require (a small amount of) $\Pi ^1_1$-transfinite induction, by a result of M. Rathjen and the present author [11,12,13] (which also involves a reversal). This induction principle is considerably weaker than $\Pi ^1_1$-comprehension, which confirms that the strength of Bachmann-Howard fixed points can only be exhausted by dilators that are not normal.

Assuming statement (i) from Theorem 1.1, we will show that any given dilator D has a Bachmann-Howard fixed point, so that (i) follows by the result from [8]. Let us sketch the argument, which is made precise in Sect. 3: The first step is to transform D into a normal dilator $\Sigma D$ that is given by $\Sigma D(\alpha ):=\Sigma _{\gamma <\alpha }1+D(\gamma )$. Invoking statement (i), we now fix an ordinal $\Omega \le _1^{\Sigma D}\Sigma D(\Omega +1)$. To get an embedding $\xi :D(\Omega )\rightarrow \Sigma D(\Omega +1)$, we set $\xi (\gamma ):=\Sigma D(\Omega )+1+\gamma$. It is not hard to see that $\Omega \le _1^{\Sigma D}\Sigma D(\Omega +1)$ yields $\Omega \le _1^{\Sigma D}\xi (\gamma )$, for an arbitrary $\gamma <D(\Omega )$. Assume that we have $\xi (\gamma )\simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_{\Sigma D}$. We will see that $\Sigma D(\Omega )\le \xi (\gamma )<\Sigma D(\Omega +1)$ entails $n>0$ and $\gamma _{n-1}=\Omega$. Hence $\eta =\Omega$ witnesses that the $\Sigma _1$-formula

$$\begin{aligned} \exists \eta \,[(\gamma _0<\eta \wedge \ldots \wedge \gamma _{n-2}<\eta )\wedge \eta \le _1^{\Sigma D}(\sigma ;\gamma _0,\dots ,\gamma _{n-2},\eta )_{\Sigma D}] \end{aligned}$$

holds in $\Sigma D(\Omega +1)$. Due to $\Omega \le _1^{\Sigma D}\Sigma D(\Omega +1)$, the same formula must hold in $\Omega$. Still assuming $\xi (\gamma )\simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_{\Sigma D}$, this allows us to set

$$\begin{aligned} \vartheta (\gamma ):=\min \{\eta <\Omega \,|\,\{\gamma _0,\dots ,\gamma _{n-2}\}\subseteq \eta \text { and }\eta \le _1^{\Sigma D}(\sigma ;\gamma _0,\dots ,\gamma _{n-2},\eta )_{\Sigma D}\}. \end{aligned}$$

We will see that this defines a Bachmann-Howard collapse $\vartheta :D(\Omega )\rightarrow \Omega$, as needed to derive statement (ii) from Theorem 1.1 (via the result from [8]). The construction of Bachmann-Howard fixed points via $\Sigma _1$-elementarity is interesting in its own right: it sheds further light on the collapsing construction that is so central to ordinal analysis.

2 Normal dilators and patterns of resemblance

In this section we recall the notion of (normal) dilator and its formalization in weak set theories. We then show how patterns of resemblance can be relativized to a normal dilator, making the discussion from the introduction precise.

Unless otherwise noted, the base theory for all definitions and results is $\textsf {ATR}_0^{{\text {set}}}$. Let us point out that Simpson gives two somewhat different but equivalent axiomatizations in [22] and [23, Section VII.3] (see the comparison in [7, Section 1.4]). For our purpose, the following facts will be central: First, $\textsf {ATR}_0^{\textsf {set}}$ includes axiom beta, which states that any well-founded relation can be collapsed to set-membership. In our context, this will ensure that the values of dilators exist as actual ordinals (which arise by collapsing certain term representation systems, cf. Definition 2.5). Secondly, the theory $\mathsf {ATR}_0^{\textsf {set}}$ shows that all primitive recursive set functions (in the sense of R. Jensen and C. Karp [19]) are total. This will, in particular, allow us to define the restriction of $\le _1^D$ to $\beta \times \beta$ by recursion on the ordinal $\beta$. Finally, as agreed in the introduction, we work with the version of $\mathsf {ATR}_0^{\textsf {set}}$ that includes the axiom of countability. This axiom asserts that any set admits an injection into the finite ordinals (equivalently, a surjection in the converse direction, provided we are concerned with a non-empty set). It ensures that statement (ii) in Theorem 1.1 is equivalent to $\Pi ^1_1$-comprehension over the natural numbers. Even more importantly, it is used in the proof of a previous result [8], to which Theorem 1.1 will be reduced. While the countability assumption may be unusual in the context of set theory, it is very natural from the viewpoint of reverse mathematics.

Let us write $\textsf {Ord}$ for the category whose objects are the ordinals and whose morphisms are the strictly increasing functions between them (where each ordinal is identified with the ordered set of its predecessors). By $\textsf {Nat}$ we denote the full subcategory of finite ordinals (natural numbers). We write $[\cdot ]^{<\omega }$ for the finite subset functor from the category of sets to itself, with

$$\begin{aligned}{}[X]^{<\omega }&:=\text {the set of finite subsets of}~X,\\ [f]^{<\omega }(a)&:=\{f(x)\,|\,x\in a\}\quad \text {(for}\, f:X\rightarrow Y\,\text { and}\, a\in [X]^{<\omega }). \end{aligned}$$

To recall the general definition, a functor maps the objects and morphisms of one category to those of another, in such a way that identity morphisms and compositions are respected. In our case, the condition on compositions amounts to

$$\begin{aligned} {[}g\circ f]^{<\omega }=[g]^{<\omega }\circ [f]^{<\omega }\quad \text {(with}\, f:X\rightarrow Y\,\text { and }\,g:Y\rightarrow Z). \end{aligned}$$

We will often omit the forgetful functor from (finite) ordinals to sets (which sends each ordinal to the unordered set of its predecessors). In particular, this explains the application of $[\cdot ]^{<\omega }$ to ordinals. Conversely, we often assume that sets of ordinals are equipped with the usual order. For $n\in \textsf {Nat}$, the set $[n]^{<\omega }$ is, of course, the full powerset of $n=\{0,\dots ,n-1\}$. The following definition does not quite coincide with the ones in [16, Section 4.4] and [10, Section 2]. However, the resulting notion of dilator will be equivalent (cf. the proof of Theorem 2.6). Note that ${\text {rng}}(g)$ denotes the range (image) of g. The notion of natural transformation is recalled below.

Definition 2.1

A pre-dilator consists of a functor $D:\textsf {Nat}\rightarrow \textsf {Ord}$ and a natural transformation ${\text {supp}}:D\Rightarrow [\cdot ]^{<\omega }$, such that

$$\begin{aligned} {\text {supp}}_n(\sigma )\subseteq {\text {rng}}(f)\quad \Rightarrow \quad \sigma \in {\text {rng}}(D(f)) \end{aligned}$$

(``support condition'')

holds for any morphism $f:m\rightarrow n$ in $\textsf {Nat}$ and any element $\sigma \in D(n)$.

By (implicitly) composing with the forgetful functor, we can view D and $[\cdot ]^{<\omega }$ as functors between the same categories, namely from finite ordinals to sets. This allows us to consider a natural transformation ${\text {supp}}:D\Rightarrow [\cdot ]^{<\omega }$. The double arrow indicates that we are concerned with a natural (see below) family of ‘components’

$$\begin{aligned} {\text {supp}}_n:D(n)\rightarrow [n]^{<\omega }, \end{aligned}$$

one for each object $n\in \textsf {Nat}$. The components of a natural transformations are required to be morphisms in the relevant category. For transformations beween functors into $\textsf {Nat}$ or $\textsf {Ord}$, this will mean that the components must be strictly increasing. There is no such requirement in the present case, as a morphism in the category of sets is simply a function. Naturality means that the components commute with applications of our functors to morphisms. To make this explicit for the present case, the requirement is that

$$\begin{aligned} {\text {supp}}_n\circ D(f)=[f]^{<\omega }\circ {\text {supp}}_m \end{aligned}$$

holds for any strictly increasing function $f:m\rightarrow n$ between objects $m,n\in \textsf {Nat}$. We can now observe that the converse of the support condition in Definition 2.1 is automatic, as $\sigma =D(f)(\sigma _0)\in {\text {rng}}(D(f))$ yields

$$\begin{aligned} {\text {supp}}_n(\sigma )={\text {supp}}_n(D(f)(\sigma _0))=[f]^{<\omega }({\text {supp}}_m(\sigma _0))\subseteq {\text {rng}}(f). \end{aligned}$$

In [10, Definition 2.1], the support condition was only required for the unique morphism $f_\sigma :m_\sigma \rightarrow n$ with range ${\text {supp}}_n(\sigma )$, where $m_\sigma$ is determined as the cardinality of that set. This does not make a difference, as any morphism $f:m\rightarrow n$ with ${\text {supp}}_n(\sigma )\subseteq {\text {rng}}(f)$ allows for a factorization $f_\sigma =f\circ g$ with $g:m_\sigma \rightarrow m$.

To see an example of a pre-dilator, recall that any $\gamma <\omega ^\alpha$ has a unique Cantor normal form $\gamma =\omega ^{\gamma _0}+\ldots +\omega ^{\gamma _{n-1}}$ with $\gamma _{n-1}\le \ldots \le \gamma _0<\alpha$ (with $n=0$ for $\gamma =0$). For a strictly increasing $f:\alpha \rightarrow \beta$, we consider the functions

$$\begin{aligned} \omega ^f&:\omega ^\alpha \rightarrow \omega ^\beta \quad \text {with}\quad \omega ^f(\omega ^{\gamma _0}+\ldots +\omega ^{\gamma _{n-1}}) :=\omega ^{f(\gamma _0)}+\ldots +\omega ^{f(\gamma _{n-1})},\\ \quad {\text {supp}}_\alpha&:\omega ^\alpha \rightarrow [\alpha ]^{<\omega }\quad \text {with} \quad {\text {supp}}_\alpha (\omega ^{\gamma _0}+\ldots +\omega ^{\gamma _{n-1}}):=\{\gamma _0,\ldots ,\gamma _{n-1}\}, \end{aligned}$$

where the arguments are assumed to be in Cantor normal form. The restrictions of these constructions to finite ordinals yield a pre-dilator in the sense of Definition 2.1.

In second-order set theory we would be able to define class-sized dilators as functors from ordinals to ordinals that preserve pullbacks and direct limits. The last two conditions are equivalent to the existence of (necessarily unique) supports as in Definition 2.1 (see [7, Remark 2.2.2]). Hence the restriction of a class-sized dilator to $\textsf {Nat}$ is a pre-dilator in the sense of Definition 2.1. To get back the class-sized dilator from its restriction, it suffices to extend the latter by direct limits (see below and [10, Proposition 2.1]). Indeed, any pre-dilator in the sense of Definition 2.1 can be extended in this way. The extension will automatically preserve pullbacks and direct limits, but in general it will be a functor into linear orders rather than ordinals. On the other hand, the requirement that all values are well-founded (and hence isomorphic to unique ordinals) can be expressed in the usual first-order language of set theory. This shows that the second-order viewpoint is not required after all.

We now recall the extension of a pre-dilator D in detail. Crucially, the support condition ensures that any $\tau \in D(k)$ lies in the range of $D(e):D(n)\rightarrow D(k)$, for the strictly increasing $e:n=|{\text {supp}}_k(\tau )|\rightarrow k$ with range ${\text {supp}}_k(\tau )$. We can uniquely write $\tau =D(e)(\sigma )$ and ${\text {supp}}_k(\tau )=\{\gamma _0,\ldots ,\gamma _{n-1}\}$ with $\gamma _0<\ldots<\gamma _{n-1}<k$. The idea is to represent $\tau \in D(k)$ by the expression $(\sigma ;\gamma _0,\ldots ,\gamma _{n-1};k)$. At least intuitively, the same observations would apply to infinite k if D was defined on all of $\textsf {Ord}$. Note that n would remain finite even when k was infinite. In any case, the naturality of supports yields

$$\begin{aligned} {[}e]^{<\omega }({\text {supp}}_n(\sigma ))={\text {supp}}_k(D(e)(\sigma ))={\text {supp}}_k(\tau ). \end{aligned}$$

Hence $n=|{\text {supp}}_k(\tau )|$ (which was our definition of n) is equivalent to ${\text {supp}}_n(\sigma )=n$. This motivates the following notion due to Girard [16].

Definition 2.2

The trace of a pre-dilator $D=(D,{\text {supp}})$ is given by

$$\begin{aligned} {\text {Tr}}(D)=\{(\sigma ,n)\,|\,n\in \textsf {Nat}\text { and }\sigma \in D(n)\text { with }{\text {supp}}_n(\sigma )=n\}. \end{aligned}$$

Note that $\textsf {Nat}$ is a small category equivalent to the large (but locally small) category of all finite linear orders. In order to make the equivalence explicit, we write |a| and ${\text {en}}_a:|a|\rightarrow a$ for the cardinality and the strictly increasing enumeration of a finite order a. If $f:a\rightarrow b$ is a strictly increasing function between finite orders, we write $|f|:|a|\rightarrow |b|$ for the unique morphism in $\textsf {Nat}$ that satisfies ${\text {en}}_b\circ |f|=f\circ {\text {en}}_a$. Given an order Y and a suborder X, we will write $\iota _X^Y:X\hookrightarrow Y$ for the inclusion. The following coincides with [10, Definition 2.2].

Definition 2.3

Given a pre-dilator D and an ordinal $\alpha$, we define $\overline{D}(\alpha )$ as the set of all expressions $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ for an element $(\sigma ,n)\in {\text {Tr}}(D)$ and ordinals $\gamma _0<\dots<\gamma _{n-1}<\alpha$. To get a binary relation $<_{\overline{D}(\alpha )}$ on $\overline{D}(\alpha )$, we declare that

$$\begin{aligned} (\sigma ;\gamma _0,\dots ,\gamma _{m-1};\alpha )_D<_{\overline{D}(\alpha )}(\tau ;\delta _0,\dots ,\delta _{n-1};\alpha )_D \end{aligned}$$

is equivalent to $D(|\iota _c^{c\cup d}|)(\sigma )<_{D(|c\cup d|)}D(|\iota _d^{c\cup d}|)(\tau )$ with $c=\{\gamma _0,\dots ,\gamma _{m-1}\}$ and $d=\{\delta _0,\dots ,\delta _{n-1}\}$ (where $c\cup d$ carries the usual order between ordinals). For a morphism $f:\alpha \rightarrow \beta$ of $\textsf {Ord}$, we set

$$\begin{aligned} \overline{D}(f)\left( (\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D\right) :=(\sigma ;f(\gamma _0),\dots ,f(\gamma _{n-1});\beta )_D \end{aligned}$$

to define a function $\overline{D}(f):\overline{D}(\alpha )\rightarrow \overline{D}(\beta )$.

One can verify that $\overline{D}$ is a functor from ordinals to linear orders (with strictly increasing functions as morphisms, cf. [10, Lemma 2.2]). Also,

$$\begin{aligned} \{\delta _0,\dots ,\delta _{n-1}\}\subseteq {\text {rng}}(f)\quad \Rightarrow \quad (\sigma ;\delta _0,\dots ,\delta _{n-1};\beta )_D\in {\text {rng}}(\overline{D}(f)) \end{aligned}$$

holds for any morphism $f:\alpha \rightarrow \beta$ and any element $(\sigma ;\delta _0,\dots ,\delta _{n-1};\beta )_D$ of $\overline{D}(\beta )$. Hence $\{\delta _0,\dots ,\delta _{n-1}\}$ can be seen as the support of the given element.

To take up the example from above, note that $\sigma :=(\omega ^1+\omega ^0,2)$ and $\tau :=(\omega ^0,1)$ lie in the trace of our pre-dilator D with $D(\alpha )=\omega ^\alpha$ (while $(\omega ^1,2)$ does not). At least intuitively, the expressions $(\sigma ;5,\omega ;\omega \cdot 2)_D$ and $(\tau ;\omega +1;\omega \cdot 2)_D$ correspond to the ordinals $\omega ^\omega +\omega ^5$ and $\omega ^{\omega +1}$, respectively, which are both smaller than $\omega ^{\omega \cdot 2}$. To become familiar with the notation, the reader may wish to confirm that the characterization of the order in Definition 2.3 amounts to

$$\begin{aligned} (\sigma ;5,\omega ;\omega \cdot 2)_D<_{\overline{D}(\omega \cdot 2)}(\tau ;\omega +1;\omega \cdot 2)_D\quad \Leftrightarrow \quad \omega ^1+\omega ^0<_{D(3)}\omega ^2. \end{aligned}$$

In order to make the reconstruction of class-sized dilators official, we focus on pre-dilators that preserve well-foundedness. The following terminology is justified by the paragraph after Definition 2.5.

Definition 2.4

A pre-dilator D is called a dilator if the linear order $\overline{D}(\alpha )$ is well founded for every ordinal $\alpha$.

The construction below is possible because our base theory $\textsf {ATR}_0^{\textsf {set}}$ includes axiom beta, which allows us to collapse well orders to ordinals. Let us point out that the action of a dilator D on objects and morphisms of $\textsf {Nat}$ is already defined. The following does not lead to any conflict, since [13, Lemma 2.6] provides a family of isomorphisms $D(n)\cong \overline{D}(n)$ that is natural in $n\in \textsf {Nat}$ and respects supports.

Definition 2.5

Assume that D is a dilator. For each ordinal number $\alpha$, let $D(\alpha )$ and $\eta _\alpha :D(\alpha )\rightarrow \overline{D}(\alpha )$ be unique such that $D(\alpha )$ is an ordinal and $\eta _\alpha$ is an order isomorphism. Given a morphism $f:\alpha \rightarrow \beta$ in $\textsf {Ord}$, we define $D(f):D(\alpha )\rightarrow D(\beta )$ as the unique function with $\eta _\beta \circ D(f)=\overline{D}(f)\circ \eta _\alpha$. By

$$\begin{aligned} {\text {supp}}_\alpha (\gamma ):=\{\gamma _0,\dots ,\gamma _{n-1}\}\quad \text {for}\quad \eta _\alpha (\gamma )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D \end{aligned}$$

we define a family of functions ${\text {supp}}_\alpha :D(\alpha )\rightarrow [\alpha ]^{<\omega }$.

For any dilator in the sense of Definition 2.4, the previous construction yields a class-sized dilator D in the sense discussed above (see [10, Lemma 2.2]). Also, the restriction of any class-sized dilator is a dilator in the sense of Definition 2.4. The two constructions are inverse to each other, i. e., Definition 2.5 reconstructs a class-sized dilator from its set sized-restriction (see [10, Proposition 2.1]).

Even though the functors $D:\textsf {Ord}\rightarrow \textsf {Ord}$ and $\overline{D}$ are equivalent by construction, there is an important foundational difference: the map $\alpha \mapsto \overline{D}(\alpha )$ is a primitive recursive set function while $\alpha \mapsto D(\alpha )$, in general, is not (since primitive recursive set functions cannot collapse arbitrary well orders, cf. [10, Remark 2.3.7]). We have mentioned that the present definition of pre-dilators is slightly different from the one in [10]. Let us verify that the following crucial result remains valid:

Theorem 2.6

([8, 10]). The following are equivalent over $\textsf {ATR}_0^{\textsf {set}}$:

• (i) for any dilator D there is an $\alpha \in \textsf {Ord}$ and a function $\vartheta :D(\alpha )\rightarrow \alpha$ such that

  • (a) if $\gamma<\delta <D(\alpha )$ and ${\text {supp}}_\alpha (\gamma )\subseteq \vartheta (\delta )$, then $\vartheta (\gamma )<\vartheta (\delta )$,

  • (b) we have ${\text {supp}}_\alpha (\gamma )\subseteq \vartheta (\gamma )$ for all $\gamma <D(\alpha )$,

• (ii) every set is contained in an admissible set.

A function $\vartheta$ as in statement (i) is called a Bachmann-Howard collapse. If such a function exists, then $\alpha$ is called a Bachmann-Howard fixed point of D.

Proof

If we were to replace “dilator” (in the sense of Definitions 2.1 and 2.4 above) by “set-sized dilator” (in the sense of [10, Definitions 2.1 and 2.3]), then the result would hold by [8, Theorem 9.7] and [10, Proposition 2.2]. The only difference between the two notions is that the values of a set-sized dilator may be arbitrary well orders rather than ordinals. This makes the notion more general in the absence of axiom beta. Since the latter is included in our base theory $\mathsf {ATR}_0^{\textsf {set}}$, the difference vanishes. More precisely, axiom beta allows us to transform a given set-sized dilator into an isomorphic dilator in the sense of the present paper. Also, if statement (i) holds for a dilator D, then it holds for any (set-sized) dilator that is isomorphic to D, as verified in the proofs of [10, Proposition 2.2 and Lemma 2.5]. $\square$

For $\alpha <\beta$, the inclusion $\iota :\alpha \hookrightarrow \beta$ induces a morphism $D(\iota ):D(\alpha )\rightarrow D(\beta )$. In general, the latter will not coincide with the inclusion $D(\alpha )\hookrightarrow D(\beta )$ (since the range of $\overline{D}(\iota ):\overline{D}(\alpha )\rightarrow \overline{D}(\beta )$ need not be an initial segment of $\overline{D}(\beta )$, even though $\overline{D}(\iota )$ is an inclusion by construction). When $D(\iota )$ is not the inclusion, there is no obvious syntactical relation between the expressions $\eta _\alpha (\gamma )\in \overline{D}(\alpha )$ and $\eta _\beta (\gamma )\in \overline{D}(\beta )$ that represent the same ordinal $\gamma <D(\alpha )\le D(\beta )$. This turns out to be inconvenient in the context of patterns of resemblance. We will see that the issue vanishes for dilators with the following additional structure (cf. [13]).

Definition 2.7

A normal (pre-)dilator consists of a (pre-)dilator $(D,{\text {supp}})$ and a natural transformation $\mu :I\Rightarrow D$ (for the inclusion functor $I:\textsf {Nat}\rightarrow \textsf {Ord}$) with

$$\begin{aligned} \sigma <\mu _n(k)\quad \Leftrightarrow \quad {\text {supp}}_n(\sigma )\subseteq k=\{0,\dots ,k-1\} \end{aligned}$$

(``normality condition'')

for any $k<n\in \textsf {Nat}$ and $\sigma \in D(n)$.

In view of the paragraph after Definition 2.1, the components of $\mu$ are strictly increasing functions

$$\begin{aligned} \mu _n:I(n)=n=\{0,\ldots ,n-1\}\rightarrow D(n). \end{aligned}$$

They are natural in the sense that we have $D(f)\circ \mu _m=\mu _n\circ I(f)=\mu _n\circ f$ for any morphism $f:m\rightarrow n$. In particular, we obtain $\mu _n(k)=\mu _n\circ f(0)=D(f)\circ \mu _1(0)$ if we take $m=1$ and define $f:m\rightarrow n$ by $f(0):=k$ for given $k<n$. This shows that the entire transformation $\mu$ is determined by the single value $\mu _1(0)$. Nevertheless, it makes sense to state Definition 2.7 in terms of a family of functions, since the normality condition should be checked for all $n\in \mathbb {N}$.

To take up the example from above, note that our dilator D with $D(\alpha )=\omega ^\alpha$ becomes normal if we define $\mu _n:n\rightarrow \omega ^n$ by setting $\mu _n(k):=\omega ^k$. Indeed, for an ordinal $\omega ^{\gamma _0}+\ldots +\omega ^{\gamma _{m-1}}<\omega ^n$ in Cantor normal form, the inequality

$$\begin{aligned} \omega ^{\gamma _0}+\cdots +\omega ^{\gamma _{m-1}}<\mu _n(k)=\omega ^k \end{aligned}$$

is equivalent to the inclusion

$$\begin{aligned} {\text {supp}}_n(\omega ^{\gamma _0}+\cdots +\omega ^{\gamma _{m-1}})=\{\gamma _0,\ldots ,\gamma _{m-1}\}\subseteq k. \end{aligned}$$

It may be instructive to observe that $D(\alpha ):=\alpha +1$ can be extended into a dilator but not into a normal one (by the following results). Let us check that normal dilators preserve inclusions, as promised above (cf. [13, Corollary 2.9]):

Lemma 2.8

Assume that D and $\mu :I\Rightarrow D$ form a normal pre-dilator. If $\iota :k\rightarrow n$ is an inclusion map, then so is $D(\iota ):D(k)\rightarrow D(n)$.

Proof

If we have $k=n$, then $\iota$ is the identity. Since D is a functor, it follows that $D(\iota )$ is the identity on $D(k)=D(n)$, which yields the claim. In the following we thus assume $k<n$. To establish $D(\iota )(\gamma )=\gamma$ for $\gamma <D(k)$, it suffices to show that the range of $D(\iota )$ is an initial segment of D(n). Indeed, if $\gamma$ was a minimal counterexample, we would necessarily have $D(\iota )(\gamma )>\gamma$ (note that D(n) is well founded and that $D(\iota )$ is strictly increasing, by the definition of pre-dilator). But then the range of $D(\iota )$ could not include $\gamma$, while it would include the larger element $D(\iota )(\gamma )$. To complete the proof, we show

$$\begin{aligned} {\text {rng}}(D(\iota ))=\{\sigma \in D(n)\,|\,\sigma <\mu _n(k)\}. \end{aligned}$$

By the support condition and its converse (see Definition 2.1 and the paragraph that follows it), this equation reduces to the claim that

$$\begin{aligned} {\text {supp}}_n(\sigma )\subseteq {\text {rng}}(\iota )=k\quad \Leftrightarrow \quad \sigma <\mu _n(k) \end{aligned}$$

holds for all $\sigma \in D(n)$, which is nothing but the normality condition. $\square$

We want to show that a normal pre-dilator induces analogous structure on its class-sized extension. The following is a preparation (cf. [13, Lemma 2.11]).

Lemma 2.9

If D and $\mu$ form a normal pre-dilator, then ${\text {supp}}_n(\mu _n(k))=\{k\}$ holds for all $k<n$.

Proof

As in the paragraph after Definition 2.7, we get $\mu _n(k)\in {\text {rng}}(D(f))$ for the function $f:1\rightarrow n$ with $f(0)=k$. By the converse support property (see the previous proof), this entails ${\text {supp}}_n(\mu _n(k))\subseteq {\text {rng}}(f)=\{k\}$. So it suffices to exclude ${\text {supp}}_n(\mu _n(k))=\emptyset$. The latter would yield $\mu _n(k)<\mu _n(k)$, by the normality condition in Definition 2.7. $\square$

In particular, the lemma yields $(\mu _1(0),1)\in {\text {Tr}}(D)$, as needed to justify the construction of $\overline{\mu }$ in the following (cf. the definition of $\overline{D}(\alpha )$ above). The last sentence of the following definition refers to the class-sized extension of D (cf. Definition 2.5). Even though $\mu _\alpha$ is already defined for $\alpha =n\in \textsf {Nat}$, no conflict arises, because the isomorphism $D(n)\cong \overline{D}(n)$ from [13, Lemma 2.6] sends $\mu _n(k)$ to $(\mu _1(0);k;n)_D$.

Definition 2.10

Consider a normal pre-dilator $D=(D,\mu )$. For each ordinal $\alpha$ we define a function $\overline{\mu }_\alpha :\alpha \rightarrow \overline{D}(\alpha )$ by

$$\begin{aligned} \overline{\mu }_\alpha (\gamma ):=(\mu _1(0);\gamma ;\alpha )_D. \end{aligned}$$

If D is a normal dilator, we also define $\mu _\alpha :\alpha \rightarrow D(\alpha )$ by stipulating $\eta _\alpha \circ \mu _\alpha =\overline{\mu }_\alpha$.

As promised, the extension $\overline{\mu }$ inherits relevant properties of $\mu$.

Proposition 2.11

Let us assume that $(D,\mu )$ is a normal pre-dilator. Then the functions $\overline{\mu }_\alpha :\alpha \rightarrow \overline{D}(\alpha )$ are strictly increasing and natural, i. e., we have

$$\begin{aligned} \overline{\mu }_\beta \circ f=\overline{D}(f)\circ \overline{\mu }_\alpha \end{aligned}$$

for strictly increasing $f:\alpha \rightarrow \beta$. Furthermore, the extended normality condition

$$\begin{aligned} (\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D<_{\overline{D}(\alpha )}\overline{\mu }_\alpha (\delta )\quad \Leftrightarrow \quad \gamma _i<\delta \text { for all }i<n \end{aligned}$$

holds for all ordinals $\delta <\alpha$ and any element $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ of $\overline{D}(\alpha )$. In the case where D is a dilator, the functions $\mu :\alpha \rightarrow D(\alpha )$ are strictly increasing and natural, and we get normality in the sense that

$$\begin{aligned} \gamma <\mu _\alpha (\delta )\quad \Leftrightarrow \quad {\text {supp}}_\alpha (\gamma )\subseteq \delta \end{aligned}$$

holds for all $\gamma <D(\alpha )$ and $\delta <\alpha$.

Proof

The claims about $\overline{D}$ coincide with [13, Proposition 2.13], to which we refer for a proof. To obtain the corresponding claims for a normal dilator D, it suffices to invoke Definition 2.5 and the last sentence of Definition 2.10. $\square$

We can derive the following result of Aczel [1, 2] (see also [13, Proposition 2.14]).

Corollary 2.12

If D is a normal dilator, then the function $\alpha \mapsto D(\alpha )$ on ordinals is normal in the usual sense, i. e., it is strictly increasing and

$$\begin{aligned} D(\lambda )=\sup \{D(\alpha )\,|\,\alpha <\lambda \} \end{aligned}$$

holds for any limit ordinal $\lambda$.

Proof

Write $\mu$ for the natural transformation that comes with the normal dilator D. For any ordinals $\alpha <\beta$, the inclusion $\iota :\alpha \hookrightarrow \beta$ gives rise to a strictly increasing function $D(\iota ):D(\alpha )\rightarrow D(\beta )$. Based on Proposition 2.11, the proof of Lemma 2.8 shows that we have

$$\begin{aligned} {\text {rng}}(D(\iota ))=\{\gamma \in D(\beta )\,|\,\gamma <\mu _\beta (\alpha )\}, \end{aligned}$$

as well as $D(\iota )(\gamma )=\gamma$ for all $\gamma <D(\alpha )$. We thus obtain $D(\alpha )=\mu _\beta (\alpha )<D(\beta )$. Intuitively, this means that we can view $\mu$ as an internal version of D. To conclude that D is continuous at any limit $\lambda$, we show that the range of $\mu _\lambda :\lambda \rightarrow D(\lambda )$ is cofinal. For any $\gamma <D(\lambda )$ we may pick an $\alpha <\lambda$ with ${\text {supp}}_\lambda (\gamma )\subseteq \alpha$, as the given support is a finite subset of $\lambda$. By Proposition 2.11 we get $\gamma <\mu _\lambda (\alpha )=D(\alpha )$. $\square$

For our purpose, the next consequence of normality is particularly important:

Lemma 2.13

If D is a normal dilator, then we have

$$\begin{aligned} \eta _\alpha (\gamma )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D\quad \Leftrightarrow \quad \eta _\beta (\gamma )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\beta )_D \end{aligned}$$

for arbitrary ordinals $\alpha <\beta$ and any $\gamma <D(\alpha )$.

Proof

In view of Definition 2.5 we have $\eta _\beta \circ D(\iota )=\overline{D}(\iota )\circ \eta _\alpha$, where $\iota :\alpha \hookrightarrow \beta$ is the inclusion. In the proof of Corollary 2.12 we have seen that $D(\iota )(\gamma )=\gamma$ holds for $\gamma <D(\alpha )$. Assuming the left part of the equivalence in the lemma, we thus get

$$\begin{aligned} \eta _\beta (\gamma )&=\eta _\beta \circ D(\iota )(\gamma )=\overline{D}(\iota )\circ \eta _\alpha (\gamma )=\overline{D}(\iota )((\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D)\\ {}&=(\sigma ;\iota (\gamma _0),\dots ,\iota (\gamma _{n-1});\beta )_D =(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\beta )_D, \end{aligned}$$

where the penultimate equality relies on Definition 2.3. The converse implication follows immediately, as its failure would lead to two different values for $\eta _\beta (\gamma )$. $\square$

Motivated by the lemma, we introduce the following terminology.

Definition 2.14

Consider a normal dilator D. If $\eta _\alpha (\gamma )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ holds for some (or equivalently every) ordinal $\alpha$ with $\gamma <D(\alpha )$, then we write

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D \end{aligned}$$

and call the right side the representation of $\gamma$.

Speaking of the representation is justified in view of the following.

Proposition 2.15

Assume that D is a normal dilator. Then any ordinal $\gamma$ has a unique representation

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D, \end{aligned}$$

with $(\sigma ,n)\in {\text {Tr}}(D)$ and $\gamma _0<\dots <\gamma _{n-1}$. In terms of this representation, we have

$$\begin{aligned} \gamma<D(\alpha )\quad \Leftrightarrow \quad n=0\text { or }\gamma _{n-1}<\alpha \end{aligned}$$

for any ordinal $\alpha$.

Proof

We have already seen that $\alpha \mapsto D(\alpha )$ is strictly increasing and hence unbounded. To prove existence, pick an ordinal $\alpha$ with $\gamma <D(\alpha )$. The value $\eta _\alpha (\gamma )$ is an element of $\overline{D}(\alpha )$ and hence of the form $(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\alpha )_D$ with $(\sigma ,n)\in {\text {Tr}}(D)$ and $\gamma _0<\dots<\gamma _{n-1}<\alpha$. It follows that $\gamma$ has representation as in the proposition. To show uniqueness, consider a competitor $\gamma \simeq (\tau ;\gamma '_0,\dots ,\gamma '_{m-1})_D$ for the representation of $\gamma$. Then $\eta _\beta (\gamma )=(\tau ;\gamma '_0,\dots ,\gamma '_{m-1};\beta )_D$ holds for some $\beta$ with $\gamma <D(\beta )$. By Lemma 2.13 we get

$$\begin{aligned} (\tau ;\gamma '_0,\dots ,\gamma '_{m-1};\beta )_D=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\beta )_D, \end{aligned}$$

so that the two representations of $\gamma$ coincide after all. The direction “$\Rightarrow$” of the equivalence in the proposition was shown in our proof of existence. For the converse implication, write $\eta _\beta (\gamma )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1};\beta )_D$ with $\gamma <D(\beta )$ and $\alpha <\beta$. If the right side of the desired equivalence holds, then we have

$$\begin{aligned} {\text {supp}}_\beta (\gamma )=\{\gamma _0,\dots ,\gamma _{n-1}\}\subseteq \alpha . \end{aligned}$$

We now get $\gamma <\mu _\beta (\alpha )=D(\alpha )$ by Proposition 2.11. $\square$

The definition of $\le _1^D$ from the introduction can now be made official. Given a normal dilator D, let $\mathcal {L}_D$ be the language that consists of two binary relation symbols $\le$ and $\le _1^D$, as well as an $(n+1)$-ary relation symbol $\gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D$ for each element $(\sigma ,n)\in {\text {Tr}}(D)$ (considered as a relation in $\gamma$ and $\gamma _0,\dots ,\gamma _{n-1}$). We will only interpret $\mathcal {L}_D$ in structures that have a set of ordinals as universe. The symbol $\le$ is always interpreted as the usual inequality between ordinals. Note that we do not need a symbol for equality, as $\alpha =\beta$ is equivalent to the conjunction of $\alpha \le \beta$ and $\beta \le \alpha$. The relation symbols $\gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D$ are always interpreted according to Definition 2.14. In particular, the given relation can only hold when we have $\gamma _0<\dots <\gamma _{n-1}$. As usual, a bijection $f:X\rightarrow Y$ between $\mathcal {L}_D$-structures is an $\mathcal {L}_D$-isomorphism if we have

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D\quad \Leftrightarrow \quad f(\gamma )\simeq (\sigma ;f(\gamma _0),\dots ,f(\gamma _{n-1}))_D \end{aligned}$$

for all $(\sigma ,n)\in {\text {Tr}}(D)$ and $\gamma ,\gamma _0,\dots ,\gamma _{n-1}\in X$, and if analogous equivalences hold with respect to $\le$ and $\le _1^D$. Concerning the interpretation of $\le _1^D$, we adopt the following as our official definition. In Proposition 2.17 below, we will show that it coincides with the more familiar formulation in terms of $\Sigma _1$-elementarity. Note that this is not entirely obvious, as our language can be infinite (depending on D).

Definition 2.16

Invoking recursion on $\beta$, we declare that $\alpha \le _1^D\beta$ is equivalent to the conjunction of $\alpha \le \beta$ and the following: for all finite sets $X\subseteq \alpha$ and $Y\subseteq \beta \backslash \alpha$, there is a finite $\widetilde{Y}\subseteq \alpha$ and an $\mathcal {L}_D$-isomorphism $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ that fixes X.

Let us briefly explain how our base theory $\textsf {ATR}_0^{\textsf {set}}$ accommodates this definition: The idea is to define $\le _1^D\!\restriction \!(\beta \times \beta )$ by primitive recursion (cf. [19, 22]). This is obstructed by the fact that $\delta \mapsto D(\delta )$ may not be primitive recursive, as we have noted above. To resolve this issue, we restrict attention to ordinals $\beta$ below a fixed (but of course arbitrary) bound $\delta$. As we have seen in the context of Definition 2.5, axiom beta allows us to consider the isomorphism $\eta _\delta :D(\delta )\rightarrow \overline{D}(\delta )$. Using the latter as a parameter, a primitive recursive set function can decide

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D \end{aligned}$$

for all $\gamma$ and $\gamma _0,\dots ,\gamma _{n-1}$ below $\delta \le D(\delta )$. Concerning the definition of $\le _1^D$, it follows that the recursion step for $\beta <\delta$ is primitive recursive (still with $\eta _\delta$ as parameter). This shows that $\le _1^D$ can be defined as a binary relation on the class of ordinals, and that each of the restrictions $\le _1^D\!\restriction \!(\beta \times \beta )$ exists as a set. In the proof of Proposition 4.6 we will see that the class function $(D,\beta )\mapsto {\le _1^D\!\restriction \!(\beta \times \beta )}$ is $\Sigma$-definable and total in admissible sets.

As the final result of this section, we show that the given definition of $\le _1^D$ is equivalent to one in terms of $\Sigma _1$-elementarity. To be precise, we state that our $\Sigma _1$-formulas may begin with a string of existential quantifiers, followed by a quantifier-free formula. Each set of ordinals gives rise to a canonical $\mathcal {L}_D$-structure, in which the relation symbols are interpreted as specified above. The relation $\vDash$ of satisfaction in an $\mathcal {L}_D$-structure is readily formalized in terms of primitive recursive set functions (cf. e. g. [7, Section 1.3]). In fact, the equivalence with (ii) below is not needed for any of the technical arguments in this paper (and the proof of (i)$\Leftrightarrow$(iii) stands on its own). So if the reader is happy with Definition 2.16 as characterization of $\le _1^D$, they may avoid the notion of satisfaction altogether. The equivalence with (iii) shows that certain equivalences in the definition of $\mathcal {L}_D$-isomorphism can be reduced to implications (provided we quantify over all finite substructures).

Proposition 2.17

The following are equivalent for each normal dilator D and all ordinal numbers $\alpha \le \beta$:

• (i) we have $\alpha \le _1^D\beta$ (according to Definition 2.16),

• (ii) the $\mathcal {L}_D$-structure $\alpha$ is a $\Sigma _1$-elementary substructure of $\beta$, i. e., we have

  $$\begin{aligned} \beta \vDash \varphi (\alpha _1,\dots ,\alpha _n)\quad \Rightarrow \quad \alpha \vDash \varphi (\alpha _1,\dots ,\alpha _n) \end{aligned}$$

  for any $\Sigma _1$-formula $\varphi$ of $\mathcal {L}_D$ and all parameters $\alpha _1,\dots ,\alpha _n<\alpha$,

• (iii) for all finite sets $X\subseteq \alpha$ and $Y\subseteq \beta \backslash \alpha$, there is a finite $\widetilde{Y}\subseteq \alpha$ and an $\{\le ,\le _1^D\}$-isomorphism $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ that fixes X, such that we have

  $$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D\quad \Rightarrow \quad f(\gamma )\simeq (\sigma ;f(\gamma _0),\dots ,f(\gamma _{n-1}))_D \end{aligned}$$

  for all $(\sigma ,n)\in {\text {Tr}}(D)$ and $\gamma ,\gamma _0,\dots ,\gamma _{n-1}\in X\cup Y$.

Proof

Concerning (i)$\Rightarrow$(ii), the premise of the implication in (ii) entails that we have $Z\vDash \varphi (\alpha _1,\dots ,\alpha _n)$ for some finite subset $Z\supseteq \{\alpha _1,\dots ,\alpha _n\}$ of $\beta$, since $\varphi$ is existential and the language contains no function symbols. Write $Z=X\cup Y$ with $X\subseteq \alpha$ and $Y\subseteq \beta \backslash \alpha$. From (i) we get a finite set $\widetilde{Y}\subseteq \alpha$ and an $\mathcal {L}_D$-isomorphism $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ that fixes X. This yields $X\cup \widetilde{Y}\vDash \varphi (f(\alpha _1),\dots ,f(\alpha _n))$ and then $\alpha \vDash \varphi (\alpha _1,\dots ,\alpha _n)$, as f fixes $X=Z\cap \alpha \supseteq \{\alpha _1,\dots ,\alpha _n\}$ and as $\Sigma _1$-formulas are preserved upwards. To show that (ii) implies (iii), we consider arbitrary sets $X=\{\alpha _1,\dots ,\alpha _m\}\subseteq \alpha$ and $Y=\{\beta _1,\dots ,\beta _n\}\subseteq \beta \backslash \alpha$. The restrictions of $\le$ and $\le _1^D$ to $X\cup Y$ can be fully described by a quantifier-free $\mathcal {L}_D$-formula $\theta _0$, such that $\theta _0(\gamma _1,\dots ,\gamma _m,\delta _1,\dots ,\delta _n)$ holds precisely when $f(\alpha _i)=\gamma _i$ and $f(\beta _j)=\delta _j$ determines a $\{\le ,\le _1^D\}$-isomorphism $f:X\cup Y\rightarrow {\text {rng}}(f)$. Furthermore, there are only finitely many true statements

$$\begin{aligned} \zeta \simeq (\sigma ;\zeta _0,\dots ,\zeta _{k-1})_D \end{aligned}$$

with $\{\zeta \}\cup \{\zeta _0,\dots ,\zeta _{k-1}\}\subseteq X\cup Y$, by the uniqueness part of Proposition 2.15. It is straightforward to specify a quantifier-free $\mathcal {L}_D$-formula $\theta _1$ that guarantees these statements, in the sense that we have $\theta _1(\gamma _1,\dots ,\gamma _m,\delta _1,\dots ,\delta _n)$ precisely when the implications in (iii) hold for $f:X\cup Y\rightarrow {\text {rng}}(f)$ with $f(\alpha _i)=\gamma _i$ and $f(\beta _j)=\delta _j$. Now let $\varphi (\alpha _1,\dots ,\alpha _m)$ be the $\Sigma _1$-formula

$$\begin{aligned} \exists y_1,\dots ,y_n[\theta _0(\alpha _1,\dots ,\alpha _m,y_1,\dots ,y_n)\wedge \theta _1(\alpha _1,\dots ,\alpha _m,y_1,\dots ,y_n)]. \end{aligned}$$

The assignment $y_i:=\beta _i$ witnesses $\beta \vDash \varphi (\alpha _1,\dots ,\alpha _m)$. Invoking (ii), we learn that there are ordinals $\delta _1,\dots ,\delta _n<\alpha$ such that we have

$$\begin{aligned} \theta _0(\alpha _1,\dots ,\alpha _m,\delta _1,\dots ,\delta _n)\wedge \theta _1(\alpha _1,\dots ,\alpha _m,\delta _1,\dots ,\delta _n). \end{aligned}$$

Set $\widetilde{Y}:=\{\delta _1,\dots ,\delta _n\}$, and define $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ by $f(\alpha _i):=\alpha _i$ and $f(\beta _j):=\delta _j$. By construction, f is an $\{\le ,\le _1^D\}$-isomorphism, fixes the set $X=\{\alpha _1,\dots ,\alpha _m\}$, and validates the implications in (iii). Finally, we show that (iii) implies (i). For the duration of this argument, let us say that a set $Z\subseteq \beta$ is closed if we have

$$\begin{aligned} Z\ni \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D\quad \Rightarrow \quad \{\gamma _0,\dots ,\gamma _{n-1}\}\subseteq Z, \end{aligned}$$

for all $\gamma <\beta$. If $X\cup Y$ is closed, then the implications in (iii) will automatically upgrade to equivalences. Indeed, assume that we have

$$\begin{aligned} f(\gamma )\simeq (\sigma ;f(\gamma _0),\dots ,f(\gamma _{n-1}))_D \end{aligned}$$

with $\gamma \in X\cup Y$. By the existence part of Proposition 2.15, we obtain a representation $\gamma \simeq (\tau ;\gamma '_0,\dots ,\gamma '_{m-1})_D$. As $X\cup Y$ is closed, we get $\{\gamma '_0,\dots ,\gamma '_{m-1}\}\subseteq X\cup Y$. Hence one of the implications in (iii) yields

$$\begin{aligned} f(\gamma )\simeq (\tau ;f(\gamma '_0),\dots ,f(\gamma '_{m-1}))_D. \end{aligned}$$

Invoking the uniqueness part of Proposition 2.15, we can now conclude that we have $\sigma =\tau$ and $f(\gamma _i)=f(\gamma '_i)$ for all $i<m=n$. Given that f is an $\{\le ,\le _1^D\}$-isomorphism and hence injective, we obtain $\gamma _i=\gamma '_i$ and thus

$$\begin{aligned} \gamma \simeq (\tau ;\gamma '_0,\dots ,\gamma '_{m-1})_D=(\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D, \end{aligned}$$

as needed for the converse of our implication from (iii). As preparation for the final part of the argument, we show that any finite set $Z\subseteq \beta$ is contained in a finite closed set ${\text {Cl}}(Z)\subseteq \beta$. In view of $\gamma <D(\gamma +1)$ we get

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D\quad \Rightarrow \quad \{\gamma _0,\dots ,\gamma _{n-1}\}\subseteq \gamma +1, \end{aligned}$$

using the equivalence from Proposition 2.15. By recursion on $\gamma <\beta$ we now define

$$\begin{aligned} {\text {cl}}(\gamma ):=\{\gamma \}\cup \bigcup \{{\text {cl}}(\gamma _i)\,|\,i<n\text { and }\gamma _i<\gamma \}\quad \text {for}\quad \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_D. \end{aligned}$$

This amounts to a primitive recursion with $\eta _\beta :D(\beta )\rightarrow \overline{D}(\beta )$ as parameter, where the latter allows us to compute the representations of ordinals $\gamma <\beta \le D(\beta )$ (cf. the paragraph after Definition 2.16). A straightforward induction on $\gamma$ shows that ${\text {cl}}(\gamma )\subseteq \gamma +1$ is finite and closed. The desired closure of a finite set $Z\subseteq \beta$ can thus be given by ${\text {Cl}}(Z):=\bigcup \{{\text {cl}}(\gamma )\,|\,\gamma \in Z\}\subseteq \beta$. We now have all ingredients to deduce (i) from (iii). In view of Definition 2.16, we consider finite sets $X\subseteq \alpha$ and $Y\subseteq \beta \backslash \alpha$. Write ${\text {Cl}}(X\cup Y)=X'\cup Y'$ with $X\subseteq X'\subseteq \alpha$ and $Y\subseteq Y'\subseteq \beta \backslash \alpha$. Let us consider $\widetilde{Y}'\subseteq \alpha$ and $f:X'\cup Y'\rightarrow X'\cup \widetilde{Y}'$ as provided by (iii). Since $X'\cup Y'$ is closed, the implications in (iii) upgrade to equivalences, as we have seen above. Thus f is an $\mathcal {L}_D$-isomorphism, and so is its restriction $f':X\cup Y\rightarrow {\text {rng}}(f')$. As f fixes $X'$, its restriction $f'$ fixes $X\subseteq X'$ and has range $X\cup \widetilde{Y}$ for some $\widetilde{Y}\subseteq \alpha$. In view of Definition 2.16 this yields $\alpha \le _1^D\beta$, as asserted by (i). $\square$

3 From $\Sigma _1$-elementarity to Bachmann-Howard fixed points

Recall that a function $\vartheta :D(\alpha )\rightarrow \alpha$ is a Bachmann-Howard collapse of a given dilator D if conditions (a) and (b) from Theorem 2.6 are satisfied. In this section we show how to transform D into a normal dilator $\Sigma D$, such that a Bachmann-Howard collapse of D can be constructed if we have $\alpha \le _1^{\Sigma D}\Sigma D(\alpha +1)$.

The restriction to normal dilators is important for our approach to patterns of resemblance, because normality is required for Lemma 2.13. On the other hand, the notion of Bachmann-Howard collapse is most interesting for dilators that are not normal, as the following remark shows. This explains why the aforementioned transformation of D into $\Sigma D$ is necessary.

Remark 3.1

It is rather straightforward to construct a Bachmann-Howard fixed point of a normal dilator D. In the previous section we have seen that $\alpha \mapsto D(\alpha )$ is a normal function in the usual sense. We may thus pick a limit ordinal $\lambda =D(\lambda )$. Let us define $\vartheta :D(\lambda )\rightarrow \lambda$ by setting $\vartheta (\gamma ):=D(\gamma +1)<D(\lambda )=\lambda$ for $\gamma <\lambda =D(\lambda )$. Condition (a) from Theorem 2.6 is immediate since $\vartheta$ is fully order preserving. Invoking Proposition 2.11 and the proof of Corollary 2.12, we can also conclude that $\gamma <D(\gamma +1)=\mu _\lambda (\gamma +1)$ entails ${\text {supp}}_\lambda (\gamma )\subseteq \gamma +1\le \vartheta (\gamma )$, as required for (b). As explained in the introduction, this means that the full strength of Bachmann-Howard fixed points can only be exhausted by dilators that are not normal.

Our dilators are defined as functors on natural numbers (cf. Definition 2.1), even though they can be extended to arbitrary ordinals (via Definitions 2.3 and 2.5). With this in mind, we define the normal variant of a given dilator as follows.

Definition 3.2

Let $D:\textsf {Nat}\rightarrow \textsf {Ord}$ be a pre-dilator. For $n\in \textsf {Nat}$ we define

$$\begin{aligned} \Sigma D(n):=\Sigma _{k<n}1+D(k)=(1+D(0))+\dots +(1+D(n-1)), \end{aligned}$$

where the right side refers to the usual operations of ordinal arithmetic. Each $\alpha <\Sigma D(n)$ can be uniquely written as $\alpha =\Sigma D(k)+\beta$ with $k<n$ and $\beta <1+D(k)$. Given a morphism $f:m\rightarrow n$ of $\textsf {Nat}$, we define $\Sigma D(f):\Sigma D(m)\rightarrow \Sigma D(n)$ by

$$\begin{aligned}&\Sigma D(f)(\alpha ) := {\left\{ \begin{array}{ll} \Sigma D(f(k)) &{} \text {if}\,\alpha =\Sigma D(k)\,\text { with}\, k<m,\\ \Sigma D(f(k))+1+D(f\!\restriction \!k)(\beta ) &{} \text {if}\, \alpha =\Sigma D(k)+1+\beta \,\text { with}\, \beta <D(k), \end{array}\right. } \end{aligned}$$

where $f\!\restriction \!k:k\rightarrow f(k)$ is the restriction of f. Let us write ${\text {supp}}^D:D\Rightarrow [\cdot ]^{<\omega }$ for the natural transformation that comes with the pre-dilator D. We put

$$\begin{aligned} {\text {supp}}^{\Sigma D}_n(\alpha ):={\left\{ \begin{array}{ll} \{k\} &{} \text {if}\, \alpha =\Sigma D(k)\, \text {with}\, k<n,\\ \{k\}\cup {\text {supp}}^D_k(\beta ) &{} \text {if}\, \alpha =\Sigma D(k)+1+\beta \, \text {with}\, \beta <D(k), \end{array}\right. } \end{aligned}$$

to define a family of functions ${\text {supp}}^{\Sigma D}_n:\Sigma D(n)\rightarrow [n]^{<\omega }$. Finally, we construct functions $\mu _n:n\rightarrow \Sigma D(n)$ by setting $\mu _n(k):=\Sigma D(k)$ for $k<n$.

It is straightforward to verify that $\Sigma D$ is a normal pre-dilator (cf. the proof of [13, Proposition 3.7]). To decide whether it is a dilator, we need to consider the orders $\overline{\Sigma D}(\alpha )$ for infinite ordinals $\alpha$. This is done as part of the following result, which will be fundamental for our construction of Bachmann-Howard fixed points.

Proposition 3.3

Assume that D is a dilator. Then $\Sigma D$ is a normal dilator. For each ordinal $\alpha$, we have an order isomorphism

$$\begin{aligned} \xi _\alpha :D(\alpha )\rightarrow \{\delta \in \textsf {Ord}\,|\,\Sigma D(\alpha )<\delta <\Sigma D(\alpha +1)\}, \end{aligned}$$

such that ${\text {supp}}^{\Sigma D}_{\alpha +1}(\xi _\alpha (\gamma ))=\{\alpha \}\cup {\text {supp}}^D_\alpha (\gamma )$ holds for all $\gamma <D(\alpha )$.

Proof

We will first construct functions $\overline{\xi }_\alpha :\overline{D}(\alpha )\rightarrow \overline{\Sigma D}(\alpha +1)$ with analogous properties. The point is that these can be defined even when $\overline{\Sigma D}(\alpha +1)$ is not well founded, while $\Sigma D(\alpha +1)$ is undefined in that case (cf. Definitions 2.3 and 2.5). Using properties of $\overline{\xi }_\alpha$, we will be able to confirm that $\overline{\Sigma D}(\alpha +1)$ is well founded after all. Based on this fact, it will be easy to see that $\overline{\xi }_\alpha$ induces $\xi _\alpha$ as in the proposition. To describe the construction of $\overline{\xi }_\alpha$, we recall that elements of $\overline{D}(\alpha )$ have the form $(\sigma ;\alpha _0,\dots ,\alpha _{n-1};\alpha )_D$ with $\alpha _0<\dots<\alpha _{n-1}<\alpha$ and $(\sigma ,n)\in {\text {Tr}}(D)$. The last condition is the conjunction of $\sigma \in D(n)$ and ${\text {supp}}^D_n(\sigma )=n$. We can conclude $\Sigma D(n)+1+\sigma \in \Sigma D(n+1)$ and

$$\begin{aligned} {\text {supp}}^{\Sigma D}_{n+1}(\Sigma D(n)+1+\sigma )=\{n\}\cup {\text {supp}}^D_n(\sigma )=\{0,\dots ,n\}=n+1, \end{aligned}$$

which amounts to $(\Sigma D(n)+1+\sigma ,n+1)\in {\text {Tr}}(\Sigma D)$. This allows us to set

$$\begin{aligned} \overline{\xi }_\alpha \left( (\sigma ;\alpha _0,\dots ,\alpha _{n-1};\alpha )_D\right) :=(\Sigma D(n)+1+\sigma ;\alpha _0,\dots ,\alpha _{n-1},\alpha ;\alpha +1)_{\Sigma D}. \end{aligned}$$

It is straightforward but somewhat tedious to show that $\overline{\xi }_\alpha$ is strictly increasing: Consider an inequality

$$\begin{aligned} (\sigma ;\alpha _0,\dots ,\alpha _{m-1};\alpha )_D<_{\overline{D}(\alpha )}(\tau ;\beta _0,\dots ,\beta _{n-1};\alpha )_D. \end{aligned}$$

In view of Definition 2.3 and the paragraph that precedes it, we have

$$\begin{aligned} D(|\iota _a^{a\cup b}|)(\sigma )<_{D(|a\cup b|)}D(|\iota _b^{a\cup b}|)(\tau ) \end{aligned}$$

with $a=\{\alpha _0,\dots ,\alpha _{m-1}\}$ and $b=\{\beta _0,\dots ,\beta _{n-1}\}$. Set $c:=a\cup \{\alpha \}$ and $d:=b\cup \{\alpha \}$. We then have $|c|=|a|+1$, and the strictly increasing enumeration ${\text {en}}_c:|c|\rightarrow c$ can be characterized by

$$\begin{aligned} {\text {en}}_c(i)={\left\{ \begin{array}{ll} {\text {en}}_a(i) &{} \text {if}\, i<|a|,\\ \alpha &{} \text {if}\, i=|a|. \end{array}\right. } \end{aligned}$$

An analogous description is available for ${\text {en}}_{c\cup d}:|c\cup d|=|a\cup b|+1\rightarrow c\cup d$. Now consider the function $h:|c|\rightarrow |c\cup d|$ with

$$\begin{aligned} h(i):={\left\{ \begin{array}{ll} |\iota _a^{a\cup b}|(i) &{} \text {if}\, i<|a|,\\ |a\cup b| &{} \text {if}\, i=|a|. \end{array}\right. } \end{aligned}$$

For $i<|a|$ we can compute

$$\begin{aligned} {\text {en}}_{c\cup d}\circ h(i)={\text {en}}_{c\cup d}\circ \underbrace{|\iota _a^{a\cup b}|(i)}_{<|a\cup b|}={\text {en}}_{a\cup b}\circ |\iota _a^{a\cup b}|(i)=\iota _a^{a\cup b}\circ {\text {en}}_a(i)=\iota _c^{c\cup d}\circ {\text {en}}_c(i). \end{aligned}$$

The equation between the outermost expressions does also hold for $i=|a|$ (where both are equal to $\alpha$). It follows that h is equal to $|\iota _c^{c\cup d}|$, which is uniquely characterized by the equation that we have established. In other words, we have

$$\begin{aligned} |\iota _c^{c\cup d}|(|a|)=|a\cup b|\quad \text {and}\quad |\iota _c^{c\cup d}|\!\restriction \!|a|=|\iota _a^{a\cup b}|:|a|\rightarrow |a\cup b|. \end{aligned}$$

This remains valid when we replace $\iota _c^{c\cup d}$ by $\iota _d^{c\cup d}$ and |a| by |b| and $\iota _a^{a\cup b}$ by $\iota _b^{a\cup b}$. By Definition 3.2 (with $m=|a|$ and $n=|b|$) and the inequality from above we get

$$\begin{aligned}&\Sigma D(|\iota _c^{c\cup d}|)(\Sigma D(m)+1+\sigma )=\Sigma D(|a\cup b|)+1+D(|\iota _a^{a\cup b}|)(\sigma )<\\&\quad <\Sigma D(|a\cup b|)+1+D(|\iota _b^{a\cup b}|)(\tau )=\Sigma D(|\iota _d^{c\cup d}|)(\Sigma D(n)+1+\tau ). \end{aligned}$$

In view of Definition 2.3 this yields

$$\begin{aligned} \overline{\xi }_\alpha \left( (\sigma ;\alpha _0,\dots ,\alpha _{m-1};\alpha )_D\right) <_{\overline{\Sigma D}(\alpha +1)}\overline{\xi }_\alpha \left( (\tau ;\beta _0,\dots ,\beta _{n-1};\alpha )_D\right) , \end{aligned}$$

as desired. In particular, $\overline{\xi }_\alpha$ is injective. According to Definition 2.10, the natural transformation $\mu :I\Rightarrow \Sigma D$ induces functions $\overline{\mu }_\gamma :\gamma \rightarrow \overline{\Sigma D}(\gamma )$. We now show

$$\begin{aligned} {\text {rng}}(\overline{\xi }_\alpha )=\{\rho \in \overline{\Sigma D}(\alpha +1)\,|\,\overline{\mu }_{\alpha +1}(\alpha )<_{\overline{\Sigma D}(\alpha +1)}\rho \}. \end{aligned}$$

For $\subseteq$ we use Proposition 2.11 to get $\overline{\mu }_{\alpha +1}(\alpha )\le _{\overline{\Sigma D}(\alpha +1)}\overline{\xi }_\alpha (\pi )$ for any $\pi \in \overline{D}(\alpha )$ (the point is that values of $\overline{\xi }_\alpha$ have the form $(\,\cdot \,;\,\cdot \,,\ldots ,\,\cdot \,,\alpha ;\alpha +1)_{\Sigma D}$ with component $\alpha$). It remains to show $\overline{\mu }_{\alpha +1}(\alpha )\ne \overline{\xi }_\alpha (\pi )$. This holds because we have

$$\begin{aligned} \overline{\mu }_{\alpha +1}(\alpha )=(\mu _1(0);\alpha ;\alpha +1)_{\Sigma D}=(\Sigma D(0);\alpha ;\alpha +1)_{\Sigma D}, \end{aligned}$$

while values of $\overline{\xi }_\alpha$ have first entries of the form $\Sigma D(n)+1+\sigma \ne \Sigma D(0)$. To establish the implication $\supseteq$ of the equality above, we consider an arbitrary element

$$\begin{aligned} \rho =(\rho _0;\alpha _0,\dots ,\alpha _{k-1};\alpha +1)_{\Sigma D}\in \overline{\Sigma D}(\alpha +1). \end{aligned}$$

Assuming $\overline{\mu }_{\alpha +1}(\alpha )<_{\overline{\Sigma D}(\alpha +1)}\rho$, we can once again invoke Proposition 2.11 to get $k>0$ and $\alpha _{k-1}=\alpha$. Let us observe that $\rho _0$ cannot be of the form $\Sigma D(n)$, since this would yield $(\Sigma D(n),k)\in {\text {Tr}}(\Sigma D)$, hence $k={\text {supp}}^{\Sigma D}_k(\Sigma D(n))=\{n\}$, then $n=0$ and $k=1$, and finally $\rho =(\Sigma D(0);\alpha ;\alpha +1)_D=\overline{\mu }_{\alpha +1}(\alpha )$. This means that we must have $\rho _0=\Sigma D(n)+1+\rho _1$ for some $n<k$ and $\rho _1\in D(n)$. We again get

$$\begin{aligned} k={\text {supp}}^{\Sigma D}_k(\Sigma D(n)+1+\rho _1)=\{n\}\cup {\text {supp}}^D_n(\rho _1), \end{aligned}$$

which entails $k=n+1$ and ${\text {supp}}^D_n(\rho _1)=n$, so that we have $(\rho _1,n)\in {\text {Tr}}(D)$. Due to the latter, we may consider

$$\begin{aligned} \rho ':=(\rho _1;\alpha _0,\dots ,\alpha _{n-1};\alpha )_D\in \overline{D}(\alpha ). \end{aligned}$$

By construction we have $\rho =\overline{\xi }_\alpha (\rho ')\in {\text {rng}}(\overline{\xi }_\alpha )$, as desired. Assuming that D is a dilator, we can now show that the same holds for $\Sigma D$. Towards a contradiction we assume that $f:\mathbb {N}\rightarrow \overline{\Sigma D}(\beta )$ is strictly decreasing, for some $\beta \in \textsf {Ord}$. Note that we must have $\beta >0$ (as $\overline{\Sigma D}(0)\cong \Sigma D(0)=0$), and that $\overline{\mu }_\beta (0)=(\Sigma D(0);0;\beta )_{\Sigma D}$ is the smallest element of $\overline{\Sigma D}(\beta )$ (using Definition 2.3). We may thus consider the minimal $\alpha <\beta$ such that $\overline{\mu }_\beta (\alpha )\le _{\overline{\Sigma D}(\beta )}f(n)$ holds for all $n\in \mathbb {N}$. Since f is strictly decreasing, we must have

$$\begin{aligned} \overline{\mu }_\beta (\alpha )<_{\overline{\Sigma D}(\beta )}f(n)<_{\overline{\Sigma D}(\beta )}\overline{\mu }_\beta (\alpha +1) \end{aligned}$$

for all sufficiently large n (where the second inequality is dropped in case $\beta =\alpha +1$). Possibly after shifting f, we may assume that these inequalities hold for all $n\in \mathbb {N}$. If $\iota :\alpha +1\hookrightarrow \beta$ is the inclusion, then $\overline{\Sigma D}(\iota ):\overline{\Sigma D}(\alpha +1)\rightarrow \overline{\Sigma D}(\beta )$ has range

$$\begin{aligned} {\text {rng}}(\overline{\Sigma D}(\iota ))=\{\rho \in \overline{\Sigma D}(\beta )\,|\,\rho <_{\overline{\Sigma D}(\beta )}\overline{\mu }_\beta (\alpha +1)\}, \end{aligned}$$

by Proposition 2.11 in conjunction with Definition 2.3. We thus get a strictly decreasing function $g:\mathbb {N}\rightarrow \overline{\Sigma D}(\alpha +1)$ with $\overline{\Sigma D}(\iota )\circ g=f$. In view of

$$\begin{aligned}&\overline{\Sigma D}(\iota )(\overline{\mu }_{\alpha +1}(\alpha ))=\overline{\Sigma D}(\iota )((\Sigma D(0);\alpha ;\alpha +1)_{\Sigma D})\\&\quad =(\Sigma D(0);\iota (\alpha );\beta )_{\Sigma D}=(\Sigma D(0);\alpha ;\beta )_{\Sigma D}=\overline{\mu }_\beta (\alpha ) \end{aligned}$$

we have $\overline{\mu }_{\alpha +1}(\alpha )<_{\overline{\Sigma D}(\alpha +1)}g(n)$ for all $n\in \mathbb {N}$. Now the above allows us to specify a strictly decreasing function $h:\mathbb {N}\rightarrow \overline{D}(\alpha )$ by stipulating $\overline{\xi }_\alpha \circ h=g$. This contradicts the assumption that D is a dilator. Once we know that D and $\Sigma D$ are dilators, we can consider the isomorphisms $\eta ^D_\gamma :D(\gamma )\rightarrow \overline{D}(\gamma )$ and $\eta ^{\Sigma D}_\gamma :\Sigma D(\gamma )\rightarrow \overline{\Sigma D}(\gamma )$ from Definition 2.5, where $D(\gamma )$ and $\Sigma D(\gamma )$ are ordinals. Let $\xi _\alpha :D(\alpha )\rightarrow \Sigma D(\alpha +1)$ be determined by $\eta ^{\Sigma D}_{\alpha +1}\circ \xi _\alpha =\overline{\xi }_\alpha \circ \eta ^D_\alpha$. The claim that we have

$$\begin{aligned} {\text {rng}}(\xi _\alpha )=\{\delta \in \textsf {Ord}\,|\,\Sigma D(\alpha )<\delta <\Sigma D(\alpha +1)\} \end{aligned}$$

can be derived from the corresponding result about $\overline{\xi }_\alpha$, using $\eta ^{\Sigma D}_{\alpha +1}\circ \mu _{\alpha +1}=\overline{\mu }_{\alpha +1}$ (by Definition 2.10) and $\mu _{\alpha +1}(\alpha )=\Sigma D(\alpha )$ (by the proof of Corollary 2.12). Finally, for $\gamma <D(\alpha )$ with $\eta ^D_\alpha (\gamma )=(\sigma ;\alpha _0,\dots ,\alpha _{n-1};\alpha )_D$ we have

$$\begin{aligned} \eta ^{\Sigma D}_\alpha (\xi _\alpha (\gamma ))=\overline{\xi }_\alpha (\eta ^D_\alpha (\gamma ))=(\Sigma D(n)+1+\sigma ;\alpha _0,\dots ,\alpha _{n-1},\alpha ;\alpha +1)_{\Sigma D}. \end{aligned}$$

By Definition 2.5 we obtain

$$\begin{aligned} {\text {supp}}^{\Sigma D}_\alpha (\xi _\alpha (\gamma ))=\{\alpha _0,\dots ,\alpha _{n-1}\}\cup \{\alpha \}={\text {supp}}^D_\alpha (\gamma )\cup \{\alpha \}, \end{aligned}$$

as claimed in the proposition. $\square$

Given a normal dilator E, Definition 2.14 and Proposition 2.15 provide unique representations $\gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1})_E$ of all ordinals. We point out that $\gamma \ge E(0)$ is equivalent to $n>0$, by the same proposition. In the present section we only consider $E=\Sigma D$, where $\Sigma D(0)=0\le \gamma$ is automatic. The general case will be needed in the next section.

Definition 3.4

Let E be a normal dilator. Given an ordinal $\gamma \ge E(0)$, we define

$$\begin{aligned} \gamma ^*:=\sup \{\gamma _i+1\,|\,i<n\}\quad \text {for }\gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _n)_E. \end{aligned}$$

If we have $\delta \ge \gamma ^*$, then we define $\gamma [\delta ]\in \textsf {Ord}$ by stipulating

$$\begin{aligned} \gamma [\delta ]\simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1},\delta )_E, \end{aligned}$$

where we still assume $\gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _n)_E$.

Parts (a) and (d) of the following are used in our construction of a Bachmann-Howard collapse (cf. Theorem 3.7). The other parts are needed for the next section.

Lemma 3.5

The following holds for any normal dilator E and all $\beta ,\gamma \ge E(0)$:

• (a) We have $E(\delta )\le \gamma [\delta ]<E(\delta +1)$ for any ordinal $\delta \ge \gamma ^*$.

• (b) From $E(\delta )\le \gamma <E(\delta +1)$ we can infer $\delta \ge \gamma ^*$ and $\gamma [\delta ]=\gamma$.

• (c) For $\delta ,\rho \ge \gamma ^*$ we have $\gamma [\delta ]^*=\gamma ^*$ and $\gamma [\delta ][\rho ]=\gamma [\rho ]$.

• (d) If we have $\delta \ge \max \{\beta ^*,\gamma ^*\}$ and $E(\rho )\le \beta ,\gamma <E(\rho +1)$ for some $\rho$, then

  $$\begin{aligned} \beta<\gamma \quad \Leftrightarrow \quad \beta [\delta ]<\gamma [\delta ]. \end{aligned}$$

• (e) If we have $E(\rho )\le \gamma<\gamma +1<E(\rho +1)$ with $\rho \ge \delta \ge \max \{\gamma ^*,(\gamma +1)^*\}$, then we have $(\gamma +1)[\delta ]=\gamma [\delta ]+1$.

• (f) We have $E(\rho )^*=0$ and $E(\rho )[\delta ]=E(\delta )$, for arbitrary ordinals $\rho$ and $\delta$.

• (g) Assume that we have $E(\rho )<\gamma <E(\rho +1)$ with $\rho \ge \delta \ge \gamma ^*$. If $\gamma$ and $\delta$ are limit ordinals, then so is $\gamma [\delta ]$.

Proof

Parts (a) to (c) are easy consequences of Proposition 2.15 and Definition 3.4.

(d) Choose an additively closed ordinal number $\pi >\max \{\delta ,\rho \}$, consider the isomorphism $\eta _\pi :E(\pi )\rightarrow \overline{E}(\pi )$ from Definition 2.5, and write

$$\begin{aligned} \eta _\pi (\beta )=(\sigma ;\beta _0,\dots ,\beta _m;\pi )_E\quad \text {and}\quad \eta _\pi (\gamma )=(\tau ;\gamma _0,\dots ,\gamma _n;\pi )_E. \end{aligned}$$

In view of Definition 2.14 and Proposition 2.15 we have $\beta _m=\rho =\gamma _n$. Also note

$$\begin{aligned} \eta _\pi (\beta [\delta ])=(\sigma ;\beta _0,\dots ,\beta _{m-1},\delta ;\pi )_E\quad \text {and}\quad \eta _\pi (\gamma [\delta ])=(\tau ;\gamma _0,\dots ,\gamma _{n-1},\delta ;\pi )_E. \end{aligned}$$

Assume $\delta \le \rho$ (the case $\rho <\delta$ being analogous), and define $f:\pi \rightarrow \pi$ by

$$\begin{aligned} f(\alpha ):={\left\{ \begin{array}{ll} \alpha &{} \text {if}\, \alpha<\delta ,\\ \rho +\beta &{} \text {if}\, \alpha =\delta +\beta <\pi . \end{array}\right. } \end{aligned}$$

In view of Definition 2.3 we get

$$\begin{aligned} \overline{E}(f)\left( \eta _\pi (\beta [\delta ])\right) =\eta _\pi (\beta )\quad \text {and}\quad \overline{E}(f)\left( \eta _\pi (\gamma [\delta ])\right) =\eta _\pi (\gamma ). \end{aligned}$$

Now the claim follows since $\overline{E}(f)$ is an order embedding (cf. [10, Lemma 2.2]).

(e) Part (d) yields $\gamma [\delta ]+1\le (\gamma +1)[\delta ]$. We thus have $\eta :=\gamma [\delta ]+1<E(\delta +1)$ and hence $\eta ^*\le \delta \le \rho$, by part (b). By the latter and part (c) we get $\eta =\eta [\delta ]=\eta [\rho ][\delta ]$. We now derive a contradiction from $\gamma [\delta ]+1<(\gamma +1)[\delta ]$. The latter yields

$$\begin{aligned} \gamma [\delta ]<\eta [\rho ][\delta ]<(\gamma +1)[\delta ]. \end{aligned}$$

As (a) provides $E(\rho )\le \eta [\rho ]<E(\rho +1)$, we can invoke (d) to get $\gamma<\eta [\rho ]<\gamma +1$, which is indeed impossible.

(f) Recall that E comes with a natural transformation $\mu :I\Rightarrow E$ that induces a function $\mu _{\rho +1}:\rho +1\rightarrow E(\rho +1)$ with $\mu _{\rho +1}(\rho )=E(\rho )$, by Definition 2.10 and the proposition that follows it. We compute

$$\begin{aligned} \eta _{\rho +1}(E(\rho ))=\eta _{\rho +1}(\mu _{\rho +1}(\rho ))=\overline{\mu }_{\rho +1}(\rho )=(\mu _1(0);\rho ;\rho +1)_E. \end{aligned}$$

This yields $E(\rho )\simeq (\mu _1(0);\rho )_E$, which makes the claims obvious.

(g) By the previous parts we get $E(\delta )=E(\rho )[\delta ]<\gamma [\delta ]<E(\delta +1)$. Aiming at a contradiction, assume that we have $\gamma [\delta ]=\alpha +1$ with $E(\delta )\le \alpha <E(\delta +1)$. The latter yields $\alpha ^*\le \delta$, then $\alpha [\rho ][\delta ]=\alpha [\delta ]=\alpha <\gamma [\delta ]$, and finally $\alpha [\rho ]<\gamma$. Now the assumption that $\gamma$ is a limit allows us to pick an ordinal $\beta$ with $\alpha [\rho ]<\beta <\gamma$. Since $\delta$ is a limit, we have $\xi :=\max \{\alpha ^*,\gamma ^*\}<\delta$. Write $\beta \simeq (\sigma ;\beta _0,\dots ,\beta _{n-1},\rho )_E$, and let $i\le n$ be such that $\beta _{i-1}<\xi \le \beta _i$ (where $\beta _{-1}:=-1<\xi$ and $\beta _n:=\rho >\xi$). Now set $\zeta :=\xi +n-i<\delta$, and define a strictly increasing $f:\zeta +1\rightarrow \rho +1$ by

$$\begin{aligned} f(\alpha ):={\left\{ \begin{array}{ll} \alpha &{} \text {if}\, \alpha<\xi ,\\ \beta _{i+j} &{} \text {if}\, \alpha =\xi +j\,\text { with}\, j<n-i,\\ \rho &{} \text {if}\, \alpha =\xi +n-i=\zeta . \end{array}\right. } \end{aligned}$$

For $\eta _{\zeta +1}:E(\zeta +1)\rightarrow \overline{E}(\zeta +1)$ as in Definition 2.5, we define $\beta '<E(\zeta +1)$ by

$$\begin{aligned} \eta _{\zeta +1}(\beta ')=(\sigma ;\beta _0,\dots ,\beta _{i-1},\xi +i-i,\dots ,\xi +n-i;\zeta +1)_E. \end{aligned}$$

It is straightforward to verify $E(f)(\beta ')=\beta$ (use $\eta _{\rho +1}\circ E(f)=\overline{E}(f)\circ \eta _{\zeta +1}$). In view of $\alpha ^*,\gamma ^*\le \xi$ we also get $E(f)(\alpha [\zeta ])=\alpha [\rho ]$ and $E(f)(\gamma [\zeta ])=\gamma$. Since E(f) is an order embedding, we can conclude $\alpha [\zeta ]<\beta '<\gamma [\zeta ]$ and then

$$\begin{aligned} \alpha =\alpha [\delta ]=\alpha [\zeta ][\delta ]<\beta '[\delta ]<\gamma [\zeta ][\delta ]=\gamma [\delta ], \end{aligned}$$

which is the desired contradiction with $\gamma [\delta ]=\alpha +1$. $\square$

Let us also relate the new notation to the functions $\xi _\alpha :D(\alpha )\rightarrow \Sigma D(\alpha +1)$ from Proposition 3.3. We note that $\xi _\alpha (\gamma )^*$ is computed with respect to $E=\Sigma D$.

Lemma 3.6

For each $\gamma <D(\alpha )$ we have $\xi _\alpha (\gamma )^*=\min \{\delta \in \textsf {Ord}\,|\,{\text {supp}}^D_\alpha (\gamma )\subseteq \delta \}$.

Proof

In view of $\Sigma D(\alpha )<\xi _\alpha (\gamma )<\Sigma D(\alpha +1)$ we get

$$\begin{aligned} \eta ^{\Sigma D}_{\alpha +1}(\xi _\alpha (\gamma ))=(\sigma ;\gamma _0,\dots ,\gamma _n;\alpha +1)_{\Sigma D} \end{aligned}$$

with $\gamma _0<\cdots <\gamma _n=\alpha$ (cf. Proposition 2.15). According to Definition 2.5 we have

$$\begin{aligned} {\text {supp}}^{\Sigma D}_{\alpha +1}(\xi _\alpha (\gamma ))=\{\gamma _0,\dots ,\gamma _n\}=\{\gamma _0,\dots ,\gamma _{n-1}\}\cup \{\alpha \}. \end{aligned}$$

By Proposition 3.3 we get ${\text {supp}}^D_\alpha (\gamma )=\{\gamma _0,\dots ,\gamma _{n-1}\}$, so that the claim follows from the definition of $\xi _\alpha (\gamma )^*$. $\square$

Finally, we establish the promised connection between patterns of resemblance and Bachmann-Howard fixed points. Recall that an ordinal $\alpha$ is such a fixed point if there is a function $\vartheta :D(\alpha )\rightarrow \alpha$ as in statement (i) from Theorem 2.6.

Theorem 3.7

Let D be a dilator. If we have $\alpha \le _1^{\Sigma D}\Sigma D(\alpha +1)$, then $\alpha$ is a Bachmann-Howard fixed point of D.

Proof

In order to construct a Bachmann-Howard collapse $\vartheta :D(\alpha )\rightarrow \alpha$, we consider an arbitrary ordinal $\gamma <D(\alpha )$. Let $\xi _\alpha :D(\alpha )\rightarrow \Sigma D(\alpha +1)$ be the function from Proposition 3.3. Due to $\Sigma D(\alpha )<\xi _\alpha (\gamma )<\Sigma D(\alpha +1)$, Proposition 2.15 yields a representation of the form

$$\begin{aligned} \xi _\alpha (\gamma )\simeq (\sigma ;\gamma _0,\dots ,\gamma _n)_{\Sigma D}\quad \text {with }\gamma _0<\ldots <\gamma _n=\alpha . \end{aligned}$$

By $\alpha \le _1^{\Sigma D}\Sigma D(\alpha +1)$ and $\alpha \le \Sigma D(\alpha )<\xi _\alpha (\gamma )<\Sigma D(\alpha +1)$ we get $\alpha \le _1^{\Sigma D}\xi _\alpha (\gamma )$, as a glance at Definition 2.16 reveals. We apply the latter to $\alpha \le _1^{\Sigma D}\Sigma D(\alpha +1)$ and the sets $X=\{\gamma _0,\dots ,\gamma _{n-1}\}\subseteq \alpha$ and $Y=\{\alpha ,\xi _\alpha (\gamma )\}\subseteq \Sigma D(\alpha +1)\backslash \alpha$. This yields a set $\widetilde{Y}=\{\delta ,\eta \}\subseteq \alpha$ such that we have

$$\begin{aligned} \eta \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1},\delta )_{\Sigma D}\quad \text {and}\quad \delta \le _1^{\Sigma D}\eta . \end{aligned}$$

The first conjunct does, in particular, entail $\{\gamma _0,\dots ,\gamma _{n-1}\}\subseteq \delta$. In the notation from Definition 3.4 we have $\delta \ge \xi _\alpha (\gamma )^*$ and $\eta =\xi _\alpha (\gamma )[\delta ]$. We can thus set

$$\begin{aligned} \vartheta (\gamma ):=\min \{\delta <\alpha \,|\,\delta \ge \xi _\alpha (\gamma )^*\text { and }\delta \le _1^{\Sigma D}\xi _\alpha (\gamma )[\delta ]\}. \end{aligned}$$

Concerning the implementation in our base theory $\textsf {ATR}_0^{\textsf {set}}$, we point out that $\xi _\alpha (\gamma )^*$ and $\xi _\alpha (\gamma )[\delta ]$ can be computed with parameter $\eta ^{\Sigma D}_{\alpha +1}:\Sigma D(\alpha +1)\rightarrow \overline{\Sigma D}(\alpha +1)$ (which is needed to determine representations). It remains to verify conditions (a) and (b) from Theorem 2.6. By Lemma 3.6 and the definition of $\vartheta$ we get

$$\begin{aligned} {\text {supp}}^D_\alpha (\gamma )\subseteq \xi _\alpha (\gamma )^*\le \vartheta (\gamma ), \end{aligned}$$

which is condition (b). To establish condition (a), consider ordinals $\gamma<\gamma '<D(\alpha )$ with ${\text {supp}}^D_\alpha (\gamma )\subseteq \vartheta (\gamma ')$. The latter yields $\vartheta (\gamma ')\ge \xi _\alpha (\gamma )^*$, again by Lemma 3.6. Due to the definition of $\vartheta$, we also have $\vartheta (\gamma ')\ge \xi _\alpha (\gamma ')^*$. Using properties of $\xi _\alpha$, we can derive $\Sigma D(\alpha )<\xi _\alpha (\gamma )<\xi _\alpha (\gamma ')<\Sigma D(\alpha +1)$ and then

$$\begin{aligned} \vartheta (\gamma ')\le \Sigma D(\vartheta (\gamma '))\le \xi _\alpha (\gamma )[\vartheta (\gamma ')]<\xi _\alpha (\gamma ')[\vartheta (\gamma ')], \end{aligned}$$

by Lemma 3.5. Also by the definition of $\vartheta$, we get $\vartheta (\gamma ')\le _1^{\Sigma D}\xi _\alpha (\gamma ')[\vartheta (\gamma ')]$ and then $\vartheta (\gamma ')\le _1^{\Sigma D}\xi _\alpha (\gamma )[\vartheta (\gamma ')]$. Let us write the representation of $\xi _\alpha (\gamma )$ as above, so that we have

$$\begin{aligned} \xi _\alpha (\gamma )[\vartheta (\gamma ')]\simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1},\vartheta (\gamma '))_{\Sigma D}. \end{aligned}$$

We now apply Definition 2.16 to the relation $\vartheta (\gamma ')\le _1^{\Sigma D}\xi _\alpha (\gamma ')[\vartheta (\gamma ')]$ and the sets $X=\{\gamma _0,\dots ,\gamma _{n-1}\}$ and $Y=\{\vartheta (\gamma '),\xi _\alpha (\gamma )[\vartheta (\gamma ')]\}$. This yields a $\widetilde{Y}=\{\delta ,\eta \}\subseteq \vartheta (\gamma ')$ with $\eta \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1},\delta )_{\Sigma D}$ and $\delta \le _1^{\Sigma D}\eta$. Once again we have $\delta \ge \xi _\alpha (\gamma )^*$ as well as $\eta =\xi _\alpha (\gamma )[\delta ]$. Minimality yields $\vartheta (\gamma )\le \delta <\vartheta (\gamma ')$, as condition (a) demands. $\square$

4 From admissible sets to $\Sigma _1$-elementarity

In this section we show that $\Omega \le _1^D D(\Omega +1)$ holds when $\Omega$ is the ordinal height of an admissible set that contains the normal dilator D. Together with the result from the previous section (and the result of [8]), this will allow us to establish Theorem 1.1 from the introduction (see the proof at the end of this section).

Throughout the following we fix a normal dilator D. The crucial idea is to consider the classes

$$\begin{aligned} C_D(\gamma ):=\{\delta \in \textsf {Ord}\,|\,\delta \ge \gamma ^*\text { and }\delta \le _1^D\gamma [\delta ]\}, \end{aligned}$$

for $\gamma \ge D(0)$ (using the notation from Definition 3.4). For $\Omega$ as in the previous paragraph, we will show that $C_D(\gamma )\cap \Omega$ is closed and unbounded (club) in $\Omega$, by induction from $\gamma =\Omega =D(\Omega )$ up to arbitrary $\gamma <D(\Omega +1)$. The following yields the base case, as the fixed points of the normal function $\alpha \mapsto D(\alpha )$ do form a club.

Lemma 4.1

If $\gamma =D(\rho )$ holds for some $\rho$, we have $C_D(\gamma )=\{\delta \in \textsf {Ord}\,|\,D(\delta )=\delta \}$.

Proof

By Lemma 3.5 we have $\gamma ^*=0$ and $\gamma [\delta ]=D(\delta )$. It thus remains to show that $D(\delta )=\delta$ is equivalent to $\delta \le _1^D D(\delta )$. For the direction from left to right, it suffices to observe that $\le _1^D$ is reflexive. To establish the other direction, we derive a contradiction from the assumption that we have $\delta \le _1^D D(\delta )$ and $\delta <D(\delta )$. In view of the latter, Proposition 2.15 provides a representation

$$\begin{aligned} \delta \simeq (\sigma ;\delta _0,\dots ,\delta _{n-1})_D\quad \text {with }\delta _0<\ldots<\delta _{n-1}<\delta . \end{aligned}$$

Let us now apply Definition 2.16 to $\delta \le _1^D D(\delta )$ and the sets $X=\{\delta _0,\dots ,\delta _{n-1}\}\subseteq \delta$ and $Y=\{\delta \}\subseteq D(\delta )\backslash \delta$ (invoking $\delta <D(\delta )$ again). This yields a $\widetilde{Y}=\{\delta '\}\subseteq \delta$ with $\delta '\simeq (\sigma ;\delta _0,\dots ,\delta _{n-1})_D$, contradicting the uniqueness part of Proposition 2.15. $\square$

The following result (essentially an abstract version of [25, Lemma 3.11]) is needed for the successor case. Let us recall that $\delta >0$ is a limit point of a class $C\subseteq \textsf {Ord}$ if any $\beta <\delta$ admits a $\gamma \in C\cap \delta$ with $\beta <\gamma$. The assumption $\delta \in C_D(\gamma )$ in the following result is in fact automatic, by Corollary 4.3 below.

Proposition 4.2

Consider an ordinal $\gamma \ge D(0)$. If $\delta$ is an element and a limit point of $C_D(\gamma )$, then we have $\delta \le _1^D\gamma [\delta ]+1$.

If the assumption of Lemma 3.5(e) is satisfied, then we have $\gamma [\delta ]+1=(\gamma +1)[\delta ]$, so that the proposition yields $\delta \in C_D(\gamma +1)$.

Proof

In order to show $\delta \le _1^D\gamma [\delta ]+1$, we will apply the criterion from part (c) of Theorem 2.17. To this end, let us consider finite sets $X\subseteq \delta$ and $Y\subseteq (\gamma [\delta ]+1)\backslash \delta$. If $\delta$ is a limit of ordinals $\beta$ with $\alpha \le _1^D\beta$, then we also have $\alpha \le _1^D\delta$, as a glance at Definition 2.16 reveals. For each $\alpha \in X$ with $\alpha \not \le _1^D\delta$, we may thus pick an $\alpha '>\alpha$ with $\alpha \not \le _1^D\alpha '<\delta$. Let us set

$$\begin{aligned} X':=\{\alpha '\,|\,\alpha \in X\text { and }\alpha \not \le _1^D\delta \}\subseteq \delta . \end{aligned}$$

From $\delta \in C_D(\gamma )$ we can derive $\delta \le _1^D D(\delta )\le \gamma [\delta ]$ and then $D(\delta )=\delta$, as in the proof of Lemma 4.1. In particular we have $\beta >D(0)$ for any ordinal $\beta \in Y$. Due to $D(\delta )=\delta \le \beta \le \gamma [\delta ]<D(\delta +1)$ we get $\beta ^*\le \delta$, by Lemma 3.5. In fact, we even obtain $\beta ^*<\delta$, as $\beta ^*$ is never a limit (cf. Definition 3.4). Using the assumption of the proposition, we now choose an ordinal $\eta$ with

$$\begin{aligned} X\cup X'\cup \{\beta ^*\,|\,\beta \in Y\}\subseteq \eta \in C_D(\gamma )\cap \delta . \end{aligned}$$

Put $\widetilde{Y}:=\{\beta [\eta ]\,|\,\beta \in Y\}$, and define $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ by

$$\begin{aligned} f(\beta ):={\left\{ \begin{array}{ll} \beta &{} \text {if}\, \beta \in X,\\ \beta [\eta ] &{} \text {if}\,\beta \in Y. \end{array}\right. } \end{aligned}$$

It remains to verify the conditions from part (c) of Theorem 2.17. First observe that the elements of $\widetilde{Y}$ satisfy $\beta [\eta ]<D(\eta +1)\le D(\delta )=\delta$. We now show

$$\begin{aligned} \alpha \le \beta \quad \Leftrightarrow \quad f(\alpha )\le f(\beta ) \end{aligned}$$

for $\alpha ,\beta \in X\cup Y$. If we have $\alpha \in X$ and $\beta \in Y$, the left side holds and we have

$$\begin{aligned} f(\alpha )=\alpha <\eta \le D(\eta )\le \beta [\eta ]=f(\beta ). \end{aligned}$$

The case of $\alpha \in Y$ and $\beta \in X$ is covered by essentially the same argument. It remains to consider $\alpha ,\beta \in Y$. Here we have $D(\delta )=\delta \le \alpha ,\beta \le \gamma [\delta ]<D(\delta +1)$. From Lemma 3.5 we learn that $\alpha <\beta$ is equivalent to $\alpha [\eta ]<\beta [\eta ]$. The same equivalence holds when both occurrences of < are replace by $\le$, as we are concerned with a linear order. Next, we establish

$$\begin{aligned} \alpha \le _1^D\beta \quad \Leftrightarrow \quad f(\alpha )\le _1^D f(\beta ). \end{aligned}$$

We may focus on the case of $\alpha <\beta$, as we have seen that f is an order isomorphism. Let us first assume $\alpha \in X$ and $\beta \in Y$. Then $\alpha \le _1^D\beta$ implies $f(\alpha )=\alpha \le _1^D f(\beta )$, as we have $\alpha<f(\beta )<\beta$. In the converse direction, $f(\alpha )\le _1^D f(\beta )=\beta [\eta ]$ and $\alpha =f(\alpha )<\eta \le \beta [\eta ]$ yield $\alpha \le _1^D\eta$. The latter entails $\alpha \le _1^D\delta$, since $\alpha \not \le _1^D\delta$ would lead to $\alpha \not \le _1^D\alpha '<\eta$. From the assumption $\delta \in C_D(\gamma )$ we also get $\delta \le _1^D\beta \le \gamma [\delta ]$. It is straightforward to see that $\le ^D_1$ is transitive. The previous inequalities can thus be combined into $\alpha \le _1^D\beta$, as required. For $\alpha ,\beta \in Y$ (still with $\alpha <\beta$) we show

$$\begin{aligned} \alpha \le _1^D\beta \quad \Leftrightarrow \quad \alpha =\delta \quad \Leftrightarrow \quad \alpha [\eta ]=\eta \quad \Leftrightarrow \quad \alpha [\eta ]\le _1^D\beta [\eta ]. \end{aligned}$$

Concerning the middle equivalence, we observe that $D(\delta )=\delta$ and Lemma 3.5(f) yield $\delta ^*=0$ and $\delta [\eta ]=D(\eta )=\eta$ (where the last equation follows from $\eta \in C_D(\gamma )$). This also shows that $\delta <\alpha$ implies $\eta <\alpha [\eta ]$, as needed for the converse implication. The first equivalence is similar to the third, so we only provide details for the latter: From $D(\delta )=\delta \le \alpha<\beta \le \gamma [\delta ]<D(\rho +1)$ we get $\alpha [\eta ]<\beta [\eta ]\le \gamma [\delta ][\eta ]=\gamma [\eta ]$, once again by Lemma 3.5. If we have $\alpha [\eta ]=\eta$, we can thus invoke $\eta \in C_D(\gamma )$ to get $\eta \le _1^D\gamma [\eta ]$ and then $\alpha [\eta ]\le _1^D\beta [\eta ]$. To establish the converse implication, we derive a contradiction from the assumption that we have $\eta <\alpha [\eta ]\le _1^D\beta [\eta ]$. Write $\alpha [\eta ]\simeq (\sigma ;\alpha _0,\dots ,\alpha _n)_D$ with $\alpha _0<\ldots <\alpha _n=\eta$. Given $\eta<\alpha [\eta ]<\beta [\eta ]$, we can apply Definition 2.16 to $\alpha [\eta ]\le _1^D\beta [\eta ]$ and the sets $\{\alpha _0,\dots ,\alpha _n\}\subseteq \alpha [\eta ]$ and $\{\alpha [\eta ]\}\subseteq \beta [\eta ]\backslash \alpha [\eta ]$. This yields an $\widetilde{\alpha }<\alpha [\eta ]$ with $\widetilde{\alpha }\simeq (\sigma ;\alpha _0,\dots ,\alpha _n)_D$, which contradicts the uniqueness part of Proposition 2.15. Finally, we establish

$$\begin{aligned} \alpha \simeq (\sigma ;\alpha _0,\dots ,\alpha _{n-1})_D\quad \Rightarrow \quad f(\alpha )\simeq (\sigma ;f(\alpha _0),\dots ,f(\alpha _{n-1}))_D \end{aligned}$$

for arbitrary $\alpha ,\alpha _0,\dots ,\alpha _{n-1}\in X\cup Y$. Note that the criterion from Theorem 2.17(c) does not require us to verify the converse implication (as the latter is automatic when $X\cup Y$ has suitable closure properties). In case $\{\alpha _0,\dots ,\alpha _{n-1}\}\subseteq \delta$ we have $\alpha <D(\delta )=\delta$ (by Proposition 2.15), so that $f:X\cup Y\rightarrow X\cup \widetilde{Y}$ does not move any of the relevant parameters. Also, $\alpha _{n-1}>\delta$ would entail $D(\delta +1)\le \alpha \notin X\cup Y$. The only interesting case is thus $\alpha _{n-1}=\delta$ (if $\delta \in Y$). Here we have $\alpha \in Y$ and

$$\begin{aligned} f(\alpha )=\alpha [\eta ]\simeq (\sigma ;\alpha _0,\dots ,\alpha _{n-2},\eta )_D. \end{aligned}$$

For $i<n-1$ we have $\alpha _i<\alpha _{n-1}=\delta$, thus $\alpha _i\in X$ and $f(\alpha _i)=\alpha _i$. It remains to show $f(\delta )=\eta$. Due to $\delta ,\eta \in C_D(\gamma )$ we have $D(\delta )=\delta$ and $D(\eta )=\eta$. By part (f) of Lemma 3.5 we now get $f(\delta )=\delta [\eta ]=D(\delta )[\eta ]=D(\eta )=\eta$, as needed. $\square$

As promised, we can derive the following. Let us recall that a class is called closed if it contains all its limit points.

Corollary 4.3

The class $C_D(\gamma )$ is closed for each $\gamma \ge D(0)$.

Proof

First observe that $\rho \in C_D(\gamma )$ entails $\rho \le _1^D D(\rho )\le \gamma [\rho ]$ and then $D(\rho )=\rho$, as in the proof of Lemma 4.1. Since $\alpha \mapsto D(\alpha )$ is a normal function, we obtain $D(\delta )=\delta$ for any given limit point $\delta$ of $C_D(\gamma )$. To conclude, we establish $\delta \le _1^D\eta$ by induction from $\eta =\delta$ up to $\eta =\gamma [\delta ]$. Base case and limit step are immediate by Definition 2.16. Let us now consider the step from $\eta$ to $\eta +1\le \gamma [\delta ]<D(\delta +1)$. In view of $D(\delta )=\delta \le \eta <D(\delta +1)$ we get $\delta \ge \eta ^*$ and $\eta [\delta ]=\eta$, by Lemma 3.5. For the induction step we must thus establish $\delta \le ^D_1\eta [\delta ]+1$. Due to Proposition 4.2, it suffices to show that $\delta$ is an element and a limit point of $C_D(\eta )$. In view of $\eta [\delta ]=\eta$ we get $\delta \in C_D(\eta )$ from the induction hypothesis . Now consider an arbitrary $\alpha <\delta$. We must find a $\beta \in C_D(\eta )$ with $\alpha<\beta <\delta$. As $\eta ^*$ cannot be a limit (cf. Definition 3.4), we must have $\eta ^*<\delta$. This allows us to pick a $\beta \supseteq \{\alpha ,\eta ^*\}$ in $C_D(\gamma )\cap \delta$, since $\delta$ was assumed to be a limit point of this set. Using Lemma 3.5, we see that $D(\delta )\le \eta<\gamma [\delta ]<D(\delta +1)$ entails $\eta [\beta ]<\gamma [\delta ][\beta ]=\gamma [\beta ]$. Since $\beta \in C_D(\gamma )$ provides $\beta \le _1^D\gamma [\beta ]$, we can now conclude $\beta \le _1^D\eta [\beta ]$, as needed for $\beta \in C_D(\eta )$. $\square$

To formulate the limit step, we fix an ordinal $\Omega \ge D(0)$. We will later assume that $\Omega$ is the height of an admissible set, but this is not required yet.

Proposition 4.4

Let us consider a limit ordinal $\gamma$ with $D(\Omega )<\gamma <D(\Omega +1)$. For each $\eta <\Omega$, we put

$$\begin{aligned} F_D(\gamma ,\eta ):=\bigcap \{C_D(\beta )\,|\,\Omega \le \beta <\gamma \text { and }\beta ^*\le \eta \}. \end{aligned}$$

We then have $\delta \in C_D(\gamma )$ for any limit ordinal $\delta$ that satisfies $\gamma ^*\le \delta =D(\delta )<\Omega$ as well as $\delta \in F_D(\gamma ,\eta )$ for all $\eta <\delta$.

Before we prove the proposition, we sketch how it fits into our inductive argument (see below for details): By induction hypothesis, each of the sets $C_D(\beta )\cap \Omega$ will be club in $\Omega$. The assumption $\beta ^*\le \eta$ ensures that $F_D(\gamma ,\eta )\cap \Omega$ is the intersection of less than $\Omega$ clubs, and hence club itself. From the proposition we learn that $C_D(\gamma )\cap \Omega$ contains (essentially) the diagonal intersection over the clubs $F_D(\gamma ,\eta )\cap \Omega$. Hence $C_D(\gamma )\cap \Omega$ is unbounded in $\Omega$, and club by Corollary 4.3.

Proof

From Lemma 3.5 we know that $\gamma [\delta ]$ is a limit. Hence the desired conclusion $\delta \le _1^D\gamma [\delta ]$ reduces to $\delta \le _1^D\alpha$ for $D(\delta )\le \alpha <\gamma [\delta ]$. For any such $\alpha$ we have $\delta \ge \alpha ^*$, which allows us to consider $\beta :=\alpha [\Omega ]\ge \Omega$. Using Lemma 3.5, we compute

$$\begin{aligned} \beta [\delta ]=\alpha [\Omega ][\delta ]=\alpha [\delta ]=\alpha <\gamma [\delta ] \end{aligned}$$

and infer $\beta <\gamma$. We also have $\beta ^*=\alpha ^*<\delta$ (since $\delta$ is a limit), so that we get

$$\begin{aligned} \delta \in F_D(\gamma ,\beta ^*)\subseteq C_D(\beta ). \end{aligned}$$

In view of $\beta [\delta ]=\alpha [\Omega ][\delta ]=\alpha [\delta ]=\alpha$ this yields $\delta \le _1^D\alpha$, as required. $\square$

As mentioned above, we want to use induction from $\gamma =\Omega =D(\Omega )$ up to arbitrary $\gamma <D(\Omega +1)$ to show that $C_D(\gamma )\cap \Omega$ is club in $\Omega$. If $\Omega$ was a regular cardinal, this would follow from the previous propositions and standard facts (the limit points of each club form another club, and clubs are closed under diagonal intersections). In the following we recover these facts under the assumption that $\Omega =\mathbb {A}\cap \textsf {Ord}$ is the height of an admissible set $\mathbb {A}\ni D$ (where $D:\textsf {Nat}\rightarrow \textsf {Ord}$ is the set-sized object from Definition 2.1, not its class-sized extension $D:\textsf {Ord}\rightarrow \textsf {Ord}$). For this purpose, we would like to have a $\Delta$-definition of $C_D(\gamma )\cap \Omega$ in $\mathbb {A}$, which should be uniform in $\gamma$. If we take this desideratum literally, then it is impossible to satisfy, simply because we are interested in ordinals $\gamma \notin \mathbb {A}$. However, we can get very close: The ordinals $\gamma \in D(\Omega +1)\backslash D(\Omega )$ are those with representations

$$\begin{aligned} \gamma \simeq (\sigma ;\gamma _0,\dots ,\gamma _{n-1},\Omega )_D \end{aligned}$$

that have last entry $\Omega$. Given that the latter is fixed, we can omit it and write

$$\begin{aligned} \gamma \sim \langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D. \end{aligned}$$

This yields a bijection between $D(\Omega +1)\backslash D(\Omega )$ and the collection of expressions that appear on the right, which we denote by

$$\begin{aligned} \mathbb {D}:=\{\langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D\,|\,(\sigma ,n+1)\in {\text {Tr}}(D)\text { and }\gamma _0<\ldots<\gamma _{n-1}<\Omega \}. \end{aligned}$$

We order $\mathbb {D}$ so that our bijection $\mathbb {D}\cong D(\Omega +1)\backslash D(\Omega )$ becomes an isomorphism. Membership in and the order relation on $\mathbb {D}$ can be decided by primitive recursive set functions with parameter D (cf. Definition 2.3 and the discussion in [10, Section 2]). In particular, we obtain a $\Delta$-definition of the order $\mathbb {D}\subseteq \mathbb {A}$ in the admissible set $\mathbb {A}$. This allows for an alternative approach to our club sets:

Definition 4.5

For each element $\rho =\langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D\in \mathbb {D}$, we define

$$\begin{aligned} \overline{C}_D(\rho ):=C_D(\gamma )\cap \Omega \quad \text {for }\gamma \sim \langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D. \end{aligned}$$

As promised, we get the following:

Proposition 4.6

If D is a normal dilator and $\mathbb {A}\ni D$ an admissible set, then

$$\begin{aligned} \{(\delta ,\rho )\in \Omega \times \mathbb {D}\,|\,\delta \in \overline{C}_D(\rho )\}\subseteq \mathbb {A}^2 \end{aligned}$$

is $\Delta$-definable in $\mathbb {A}$.

Proof

If $\rho \in \mathbb {D}$ and $\gamma \in D(\Omega +1)$ are related as in Definition 4.5, we set $\rho ^+:=\gamma ^*$ and $\rho \langle \delta \rangle :=\gamma [\delta ]$ for $\rho ^+\le \delta <\Omega$. Then $\delta \in \overline{C}_D(\rho )$ is equivalent to the conjunction of $\delta \ge \rho ^+$ and $\delta \le _1^D\rho \langle \delta \rangle$. In order to obtain the claim from the proposition, it suffices to show that the functions $\rho \mapsto \rho ^+$, $(\delta ,\rho )\mapsto \rho \langle \delta \rangle$ and $\beta \mapsto {\le _1^D\!\restriction \!(\beta \times \beta )}$ (with the obvious domains of definition) are $\Sigma$-definable and total in $\mathbb {A}$. For the first function this is obvious, as $\rho ^+=\sup \{\gamma _i+1\,|\,i<n\}$ can be read off from the expression $\rho =\langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D\in \mathbb {D}$. Concerning the second function, we observe that $\rho \langle \delta \rangle$ is characterized by

$$\begin{aligned} \eta _{\delta +1}(\rho \langle \delta \rangle )=(\sigma ;\gamma _0,\dots ,\gamma _{n-1},\delta ;\delta +1)_D, \end{aligned}$$

for the unique isomorphism $\eta _{\delta +1}:D(\delta +1)\rightarrow \overline{D}(\delta +1)$ (cf. Definitions 2.5 and 2.14). Crucially, the function that maps a well-ordered set X (in the sense of the universe) to its collapse $c:X\rightarrow \alpha$ onto an ordinal is $\Sigma$-definable and total in admissible sets (by [18, Theorem 4.6], cf. also [3, Exercise V.6.12]). Together with the fact that $\delta \mapsto \overline{D}(\delta )$ is primitive recursive, this entails that $\delta \mapsto \eta _\delta$ and in particular $\delta \mapsto D(\delta )$ is $\Sigma$-definable and total in $\mathbb {A}$. The same follows for the functions $(\delta ,\rho )\mapsto \rho \langle \delta \rangle$ and $\beta \mapsto {\le _1^D\!\restriction \!(\beta \times \beta )}$, by the paragraph after Definition 2.16 above. $\square$

The following theorem and its corollary are the main results of this section.

Theorem 4.7

Consider a normal dilator D and an admissible set $\mathbb {A}\ni D$ with height $\Omega =\textsf {Ord}\cap \mathbb {A}$. For each ordinal $\gamma \in D(\Omega +1)\backslash \Omega$, the set $C_D(\gamma )\cap \Omega$ is closed and unbounded in $\Omega$.

Proof

In the proof of Proposition 4.6 we have seen that $\mathbb {A}$ is closed under the operation $\alpha \mapsto D(\alpha )$. Due to the continuity of normal functions at limit ordinals, we can conclude $D(\Omega )=\Omega$. In particular, this yields $\gamma \ge D(0)$ for any $\gamma \ge \Omega$, which is needed to ensure that $\gamma ^*$ and $C_D(\gamma )$ are defined (cf. Definition 3.4). From Corollary 4.3 we know that the set $C_D(\gamma )\cap \Omega$ is closed in $\Omega$. To show that it is unbounded, we argue by induction from $\gamma =\Omega =D(\Omega )$ up to arbitrary $\gamma <D(\Omega +1)$. Let us point out that the induction statement is primitive recursive with the function $\eta _{\Omega +1}:D(\Omega +1)\rightarrow \overline{D}(\Omega +1)$ as parameter, by the proof of Proposition 4.6. In the base case of $\gamma =\Omega =D(\Omega )$, we invoke Lemma 4.1 to get

$$\begin{aligned} C_D(\Omega )\cap \Omega =\{\delta <\Omega \,|\,D(\delta )=\delta \}. \end{aligned}$$

The usual argument that normal functions have arbitrarily large fixed points can be accommodated in our setting: Given an arbitrary $\alpha _0<\Omega$, we set $\alpha _{n+1}:=D(\alpha _n)$ to get a function $\mathbb {N}\ni n\mapsto \alpha _n<\Omega$ that is $\Sigma$-definable in $\mathbb {A}$. We take $D\in \mathbb {A}$ to entail $\mathbb {N}\in \mathbb {A}$ (as D is a functor with domain $\textsf {Nat}$). By $\Sigma$-collection in $\mathbb {A}$ (cf. [3, Section I.4.4]) we then obtain $\alpha _\infty :=\sup \{\alpha _n\,|\,n\in \mathbb {N}\}<\Omega$. Unless we already have a fixed point $D(\alpha _n)=\alpha _n$ for some $n\in \mathbb {N}$, the ordinal $\alpha _\infty$ is a limit, so that we get

$$\begin{aligned} D(\alpha _\infty )=\sup \{D(\alpha _n)\,|\,n\in \mathbb {N}\}=\sup \{\alpha _{n+1}\,|\,n\in \mathbb {N}\}=\alpha _\infty \end{aligned}$$

by continuity of normal functions. For the successor step of our induction, we show

$$\begin{aligned} \{\delta <\Omega \,|\,\delta \ge (\gamma +1)^*\,\text { is a limit point of}\, C_D(\gamma )\}\subseteq C_D(\gamma +1)\cap \Omega . \end{aligned}$$

Given any element $\delta$ of the left side, Corollary 4.3 yields $\delta \in C_D(\gamma )$. We can apply Proposition 4.2 to get $\delta \le _1^D\gamma [\delta ]+1$. By Lemma 3.5 we have $\gamma [\delta ]+1=(\gamma +1)[\delta ]$, so that we obtain $\delta \in C_D(\gamma +1)$, as desired. Let us note that $\gamma +1<D(\Omega +1)$ entails $(\gamma +1)^*<\Omega$ (since $\Omega$ is a limit). To complete the successor step of our induction, we construct arbitrarily large limit points of $C_D(\gamma )\cap \Omega$, which is club by induction hypothesis. Crucially, Proposition 4.6 ensures that $C_D(\gamma )\cap \Omega$ (which is equal to $\overline{C}_D(\rho )$ for the appropriate $\rho \in \mathbb {D}$) is $\Delta$-definable in $\mathbb {A}$. Once this is known, we can rely on the usual construction: Given an arbitrary start value $\alpha _0<\Omega$, we inductively choose $\alpha _{n+1}>\alpha _n$ minimal with $\alpha _{n+1}\in C_D(\gamma )\cap \Omega$. Since this last set is $\Delta$-definable in $\mathbb {A}$, we obtain a $\Sigma$-definable function $\mathbb {N}\ni \alpha \mapsto \alpha _n<\Omega$. As above, we get $\alpha _\infty :=\sup \{\alpha _n\,|\,n\in \mathbb {N}\}<\Omega$ by $\Sigma$-collection in $\mathbb {A}$. The construction ensures that $\alpha _\infty$ is a limit point of $C_D(\gamma )$. It remains to consider the case of a limit ordinal $\gamma \in D(\Omega +1)\backslash (\Omega +1)$. By Proposition 4.4, the set $C_D(\gamma )$ contains the intersection of the $\Delta$-definable club $\{\delta <\Omega \,|\,\delta =D(\delta )\ge \gamma ^*\text { is limit}\}$ with the set

$$\begin{aligned} \{\delta<\Omega \,|\,\delta \in F_D(\gamma ,\eta )\text { for all }\eta <\delta \}. \end{aligned}$$

(2)

It suffices to show that the latter is a $\Delta$-definable club as well (since the intersection of two such clubs is easily seen to be club itself). Assume that $\gamma$ and $\rho \in \mathbb {D}$ are related as in Definition 4.5, and let $\mathbb {D}\ni \pi \mapsto \pi ^+\in \Omega$ be the function from the proof of Proposition 4.6. We then have

$$\begin{aligned} F_D(\gamma ,\eta )\cap \Omega =\bigcap \{\overline{C}_D(\pi )\,|\,\pi <_{\mathbb {D}}\rho \text { and }\pi ^+\le \eta \}. \end{aligned}$$

We write $\mathbb {D}(\eta ):=\{\pi \in \mathbb {D}\,|\,\pi ^+\le \eta \}$ and observe

$$\begin{aligned} \mathbb {D}(\eta )=\{\langle \sigma ;\gamma _0,\dots ,\gamma _{n-1}\rangle _D\,|\,(\sigma ,n+1)\in {\text {Tr}}(D)\text { and }\gamma _0<\ldots<\gamma _{n-1}<\eta \}. \end{aligned}$$

Hence $\eta \mapsto \mathbb {D}(\eta )$ is a primitive recursive set function (with parameter D), and in particular $\Sigma$-definable and total in $\mathbb {A}$. As $\delta \in F_D(\gamma ,\eta )\cap \Omega$ is equivalent to

$$\begin{aligned} \forall \pi \in \mathbb {D}(\eta )\,[\pi <_{\mathbb {D}}\rho \rightarrow \delta \in \overline{C}_D(\pi )], \end{aligned}$$

we can conclude that $\{(\delta ,\eta )\in \Omega ^2\,|\,\delta \in F_D(\gamma ,\eta )\}\subseteq \mathbb {A}^2$ and the collection in (2) are $\Delta$-definable. Let us now show that each of the sets $F_D(\gamma ,\eta )\cap \Omega$ is club, by adapting the usual argument to our setting: From the induction hypothesis we know that $\overline{C}_D(\pi )$ is club for all $\pi <_{\mathbb {D}}\rho$. Starting with an arbitrary $\alpha _0<\Omega$, we construct a $\Sigma$-definable function $\mathbb {N}\ni n\mapsto \alpha _n<\Omega$ as follows: In the recursion step, consider the function

$$\begin{aligned}&f_n:\{\pi \in \mathbb {D}(\eta )\,|\,\pi <_{\mathbb {D}}\rho \}\rightarrow \Omega ,\\&\quad f_n(\pi ):=\min \{\alpha >\alpha _n\,|\,\alpha \in \overline{C}_D(\pi )\}. \end{aligned}$$

By $\Delta$-separation and $\Sigma$-replacement (see [3, Theorems 4.5 and 4.6]) we get $f_n\in \mathbb {A}$. This allows us to set

$$\begin{aligned} \alpha _{n+1}:=\sup \{f_n(\pi )\,|\,\pi \in \mathbb {D}(\eta )\text { and }\pi<_{\mathbb {D}}\rho \}<\Omega . \end{aligned}$$

Another application of $\Sigma$-collection yields $\alpha _\infty :=\sup \{\alpha _n\,|\,n\in \mathbb {N}\}<\Omega$. To see that $\alpha _\infty$ is a limit point (and hence an element) of each set $\overline{C}_D(\pi )$, we consider an arbitrary ordinal $\alpha <\alpha _\infty$. We then have $\alpha \le \alpha _n$ for some $n\in \mathbb {N}$, so that we indeed get $\alpha <f_n(\pi )\in \overline{C}_D(\pi )\cap \alpha _{\infty }$. Finally, we deduce that the collection in (2) is club. As mentioned before, this collection is a diagonal intersection. The usual argument goes through in our setting: Start with an arbitrary $\alpha _0<\Omega$ and recursively set

$$\begin{aligned} \alpha _{n+1}:=\min \{\alpha <\Omega \,|\,\alpha >\alpha _n\text { and }\alpha \in F_D(\gamma ,\alpha _n)\}. \end{aligned}$$

This is possible because $F_D(\gamma ,\eta )\cap \Omega$ is club for $\eta <\Omega$, as shown above. Since the relation $\alpha \in F_D(\gamma ,\eta )$ is $\Delta$-definable, the resulting function $n\mapsto \alpha _n$ is $\Sigma$-definable in $\mathbb {A}$. Once again we obtain $\alpha _\infty :=\sup \{\alpha _n\,|\,n\in \mathbb {N}\}<\Omega$. In order to see that $\alpha _\infty$ is contained in the diagonal intersection (2), we consider an arbitrary $\eta <\alpha _\infty$. Pick an $n\in \mathbb {N}$ with $\eta \le \alpha _n$. For any $N>n$ we get $\alpha _N\in F_D(\gamma ,\alpha _{N-1})\subseteq F_D(\gamma ,\eta )$, where the inclusion is an easy consequence of $\eta \le \alpha _{N-1}$. This shows that $\alpha _\infty$ is a limit point and hence an element of $F_D(\gamma ,\eta )$, as needed. $\square$

It is straightforward to derive the following:

Corollary 4.8

Let D be a normal dilator. If $\Omega =\textsf {Ord}\cap \mathbb {A}$ is the ordinal height of an admissible set $\mathbb {A}\ni D$, then we have $\Omega \le _1^D D(\Omega +1)$.

Proof

As in the previous proof we get $\Omega =D(\Omega )$. It suffices to show that we have $\Omega \le _1^D\gamma +1$ whenever $D(\Omega )\le \gamma <D(\Omega +1)$, no matter if $D(\Omega +1)$ is a limit or not. From the previous theorem we learn that $\Omega$ is a limit point of $C_D(\gamma )$. By Corollary 4.3 this implies $\Omega \in C_D(\gamma )$, so that Proposition 4.2 yields $\Omega \le _1^D\gamma [\Omega ]+1$. To conclude, we note that $\gamma [\Omega ]=\gamma$ holds by Lemma 3.5. $\square$

Finally, we combine our results to establish the theorem from the introduction:

Proof of Theorem 1.1

To show that (i) implies (ii), we make use of Theorem 2.6 (originally proved in [7,8,9,10]). Aiming at statement (i) of that theorem, we consider an arbitrary dilator D. Form the normal dilator $\Sigma D$ from Definition 3.2. By statement (i) of Theorem 1.1 we get an ordinal $\Omega$ with $\Omega \le _1^{\Sigma D}\Sigma D(\Omega +1)$. From Theorem 3.7 we learn that $\Omega$ is a Bachmann-Howard fixed point of D, as needed to satisfy statement (i) of Theorem 2.6. To establish the implication from (ii) to (i) in Theorem 1.1, we consider a normal dilator D. Invoking (ii), we pick an admissible set $\mathbb {A}\ni D$ (where D denotes the set-sized object from Definition 2.1, rather than its class-sized extension due to Definition 2.5). By Corollary 4.8 we have $\Omega \le _1^D D(\Omega +1)$ for $\Omega =\textsf {Ord}\cap \mathbb {A}$, as required by statement (i) of Theorem 1.1. $\square$