WEAK WELL ORDERS AND FRAÏSSÉ’S CONJECTURE

Abstract

The notion of countable well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with Fraïssé’s conjecture, which has been proved by Laver. We also fill a small gap in Shore’s proof that Fraïssé’s conjecture implies arithmetic transfinite recursion over $\mathbf {RCA}_0$, by giving a new proof of $\Sigma ^0_2$-induction.

1 Introduction

The study of well orders is of great importance to proof theory and offers a point of contact between the distinct approaches of ordinal analysis and reverse mathematics. The latter provides a well established framework to compare the axiomatic strength of theorems from various areas. A central idea is to prove equivalences between theorems and axioms over a weak base theory, such as the system ${ \mathbf {RCA}}_0$ of recursive comprehension. We refer to [6, 21] for further background. With respect to that framework, the subsystem ${ \mathbf {ATR}}_0$ appears to be the natural environment for the study of countable ordinals. As asserted by S. Simpson, “[ ${ \mathbf {ATR}}_0$ ] is the weakest set of axioms which permits the development of a decent theory of countable well orders” [21]. In particular, ${ \mathbf {ATR}}_0$ is equivalent to the statement that any two countable well orders can be compared [7, 21], in any of the following two ways. For linear orders X and Y, an embedding is an order preserving map $f:X\rightarrow Y$ . If such a map exists, we write $X\le _w Y$ . On the other hand, a strong embedding from X into Y is an isomorphism between X and an initial segment of Y, i. e., a set $I\subseteq Y$ such that we get $x\in I$ whenever we have $x<_Y y$ for some $y\in I$ . Thus, one obtains two quasi orderings over the class of linear orders, and assuming ${ \mathbf {ATR}}_0$ their restrictions to well orders coincide. In view of previous work on these two notions of embeddability (see [7, 9]), it seems natural to investigate whether initial segments can be employed to obtain a fruitful characterization of the notion of well order itself. The following is an obvious candidate for such a characterization. While this property has been investigated before [4], as far as the authors are aware it was never named.

Definition 1.1. A countable linear order X is called a weak well order if no initial segment $I\subseteq X$ can be embedded into a proper initial segment $I_0\subsetneq I$ .

Equivalently, X is a weak well order if there exists no decreasing self-embedding, i.e., no order preserving map $f:X\rightarrow X$ with $f(x)<x$ for at least one $x\in X$ . Below, we show that the property described by Definition 1.1 is equivalent to being a countable well order. To see how Definition 1.1 relates to the two notions of embeddability, observe that if a linear order X embeds into a well order Y, regardless of weakly or strongly, then X is also a well order. On the other hand, if Y is just a weak well order, we can still conclude that X is a weak well order when the embedding is strong. However, it is not immediate to reach this conclusion when the embedding is weak. Indeed, we will see that ${ \mathbf {ATR}}_0$ is equivalent to the principle that X is a weak well order whenever we have $X\leq _w Y$ for some weak well order Y (combine Lemma 3.6 with Theorem 3.5). This notion of well order is weaker than the usual one in another sense as well: Corollary 3.2 provides an example of a countable linear order that, in a weak enough theory, can be proved to be a weak well order but not a well order. Showing that countable well orders satisfy Definition 1.1 is straightforward.

Lemma 1.2 ( ${ \mathbf {RCA}}_0$ ).

If X is a well order, then it is a weak well order.

Proof Aiming to prove the contrapositive, suppose that for some linear order X there exist initial segments $I_0\subsetneq I\subseteq X$ and an embedding $f:I\rightarrow I_0$ . Take any $x\in I\setminus I_0$ , which is non-empty by assumption: then $x>f(x)>f(f(x))>$ …, so that X is not well founded.

On the other hand, the converse implication was first proved by Dushnik and Miller in [4]. An exposition of their proof can also be found in [19, Theorem 4.8]. We recall that our weak well orders are countable by definition.

Theorem 1.3 (Dushnik and Miller).

Any weak well order is a well order.

We remark that the restriction to countable linear orders is not merely an artifact of the framework of reverse mathematics. On the contrary, one can use a classical diagonalization argument to construe an ill founded order without decreasing self-embeddings that has size as small as the continuum. In fact, in [4] the authors find a dense suborder of the reals which admits no self-embedding other than the identity. On the other hand, one easily finds ill founded linear orders of arbitrary size that admit decreasing self-embeddings, such as the ordinals with inverse ordering and the very dense linear orders first studied by Hausdorff. The strength of Theorem 1.3 with respect to reverse mathematics has not been investigated before. Downey and Lempp have studied a similar statement, asserting that all countably infinite linear orders admit non-identical self-embeddings, and proved that it is equivalent to ${ \mathbf {ACA}}_0$ [3]. The focus on decreasing self-embeddings in Theorem 1.3, however, seems to complicate the matter considerably. Examining the proof given in [4], we see that to carry it out one needs $\Pi ^1_1$ -comprehension. Instead, a relatively straightforward proof can be obtained from the following statement:

1. (FRA) Any infinite sequence of countable (or more generally $\sigma $ -scattered) linear orders $L_0,L_1,\ldots $ admits $i<j$ with $L_i\leq _w L_j$ .

Proposition 1.4 ( ${ \mathbf {RCA}}_0$ ).

FRA entails that any weak well order is a well order.

Proof Aiming for the contrapositive, let $(x_i)_{i<\omega }$ be an infinite decreasing sequence inside an ill founded linear order X. Define $L_i$ as the initial segment of X consisting of all elements smaller than $x_i$ . By our hypothesis, there must be $i<j$ such that $I=L_i$ embeds into $I_0=L_j$ . Due to $x_i>x_j$ , we indeed have $L_j\subsetneq L_i$ .

Hence we obtain a proof of Theorem 1.3 in the system ${ \mathbf {RCA}}_0+$ FRA. The latter statement is commonly known as Fraïssé’s conjecture and was proved by Laver in 1971 [12], long after Dushnik and Miller’s original paper. The exact strength of Fraïssé’s conjecture is an important open problem in reverse mathematics. In [20], Shore proves that the restriction of the conjecture to well orders is equivalent to ${ \mathbf {ATR}}_0$ , over ${ \mathbf {RCA}}_0+\Sigma ^0_2\text {-induction}$ . He then argues that the base theory for the latter result can be lowered to just ${ \mathbf {RCA}}_0$ . However, the final step that eliminates $\Sigma ^0_2\text {-induction}$ uses that $\omega ^{\omega }$ is well founded, which ${ \mathbf {RCA}}_0$ cannot prove. A new proof that Fraïsse’s conjecture implies $\Sigma ^0_2$ -induction over ${ \mathbf {RCA}}_0$ will be given in the present paper (see, in particular, Section 4). Concerning the upper bound, Montalbán [15] has shown that Fraïssé’s conjecture is provable in the axiom system ${ \mathbf {\Pi ^1_1\mathbf {-CA}}}_0$ . Therefore, the system ${ \mathbf {RCA}}_0+$ FRA is weaker than ${ \mathbf {\Pi ^1_1\mathbf {-CA}}}_0$ , and in fact strictly so (see, for example, the introduction of [15]).

It is natural to ask whether the full strength of Fraïssé’s conjecture is needed for Proposition 1.4, or whether the implication there is wildly inefficient. As it turns out, neither is the case. Based on the following, we will be able to conclude that arithmetic transfinite recursion holds when any weak well order is a well order.

Proposition 1.5 ( ${ \mathbf {RCA}}_0$ ).

If every weak well order is a well order, then the restriction of Fraïssé’s conjecture to indecomposable well orders holds.

Before we give the proof, let us recall that a linear order X is indecomposable if, whenever $X=A+B$ holds for non-empty linear orders A and B, we have that X embeds into A or that X embeds into B. We say that X is indecomposable to the left if it always embeds into A, and that X is indecomposable to the right if it always embeds into B. In the special case where X is a well order, Lemma 1.2 implies that it can only be indecomposable to the right.

Proof Let $(X_i)_{i\in \omega }$ be an infinite sequence of indecomposable well orders: our aim is to find indices $i<j$ such that $X_i$ embeds into $X_j$ . We may assume that no $X_i$ is empty. By $\omega ^*$ we denote the order on $\mathbb N$ with order relation ${\leq ^*}=\{(m,n)\,|\,m\geq n\}$ . Consider the linear order $\sum _{i\in \omega ^*}X_i$ : it is ill founded, as any family of points $x_i\in X_i$ gives rise to a descending sequence. Given the assumption from the proposition, we can conclude that it is no weak well order. Hence we get an embedding f from an initial segment L into a shorter initial segment $L_0$ . We find an index j and a non-empty initial segment $I\subseteq X_j$ such that $L=\sum _{i<^*j}X_i+I$ . First we prove the thesis under the additional assumption that $L_0=\sum _{i<^*j}X_i$ , and then we show that this does not violate the generality. Under the additional assumption, $X_{j+1}\subseteq L$ must be embedded into $\sum _{i<^*j+1}X_i+J$ for some initial segment $J\subsetneq X_{j+1}$ . In fact, it embeds into $\sum _{i<^*j+1}X_i$ : if some final segment of $X_{j+1}$ did embed into J, then so would all of $X_{j+1}$ , against Lemma 1.2. Let $i>j+1$ be the smallest index such that for some $x\in X_{j+1}$ , we have $f(x)\in X_i$ . Then, a final segment of $X_{j+1}$ embeds into $X_{i}$ , and hence so does $X_{j+1}$ . Now, if $L_0$ is included in $\sum _{i<^*j}X_i$ , we can simply extend it. The only other possibility is that $L_0=\sum _{i<^*j}X_i+I_0$ holds for some $I_0\subsetneq I\subseteq X_j$ . We get that the range of $f\upharpoonright I$ is not contained in $I_0$ , since otherwise the well order $X_j$ would violate Lemma 1.2. Hence, there is a non-empty initial segment $I'\subseteq I$ such that $\operatorname {rng} (f\upharpoonright I')\subseteq L^{\prime }_0=\sum _{i<^*j}X_i$ . This means that we can replace $L_0$ with $L^{\prime }_0$ and L with $L'=\sum _{i<^*j}X_i+I'$ , to reduce to the special case that we have already treated.

By [20, Corollary 2.16], the conclusion of Proposition 1.5 implies Fraïssé’s conjecture for arbitrary well orders and thus ${ \mathbf { ATR}}_0$ over ${ \mathbf {ACA}}_0$ . Conversely, in Section 2 we adapt Montalbán’s [15] analysis of Fraïssé’s conjecture via signed trees in order to show that ${ \mathbf {ATR}}_0$ proves that any weak well order is a well order. In Section 3, we show that the latter implies ${ \mathbf {ACA}}_0$ and is therefore equivalent to arithmetic transfinite recursion over ${ \mathbf {RCA}}_0$ (see Theorem 3.5). In the same section, we will also see that, in sharp contrast, ${ \mathbf {RCA}}_0$ suffices to prove that any weak well order that is closed under (a syntactic version of) ordinal exponentiation must already be a well order. Hence the principle that weak well orders are well orders is strong in general but weak in an important class of cases. We will argue (see Remark 4.4) that this dichotomy gives some new insight into the idea of “natural” descriptions of linear orders and proof-theoretic ordinals.

2 Cantor normal form for weak well orders

In the present section, we show that ${ \mathbf {ATR}}_0$ proves Theorem 1.3. To do so, we adapt an argument from Montalbán’s analysis of Fraïssé’s conjecture, in which the notion of Hausdorff rank plays an important role.

A linear order X is called scattered if $\mathbb {Q}$ does not embed into it. Since every countable linear order embeds into $\mathbb {Q}$ , whenever X is non-scattered we can consider a pair of embeddings $(f,g)$ such that $f:X\rightarrow \mathbb {Q}$ and $g:\mathbb {Q}\rightarrow X$ . In general, if we can find such a pair of embeddings between two linear orders, we say that they are equimorphic. The fact below was observed by Dushnik and Miller as part of their original proof of Theorem 1.3. We verify that the proof can be carried out in ${ \mathbf {RCA}}_0$ with no difficulties.

Lemma 2.1 ( ${ \mathbf {RCA}}_0$ ).

Every weak well order is scattered.

Proof We prove the contrapositive. Let L be a non-scattered linear order and consider an equimorphism $(f,g)$ between L and $\mathbb {Q}$ . Take $x\in L$ with $x=g(q_0)$ for some $q_0\in \mathbb {Q}$ . Due to the fact that $\mathbb {Q}$ is indecomposable to the left, we can consider an embedding $h:\mathbb {Q}\rightarrow \{q\in \mathbb {Q}\,|\,q < q_0\}$ . Then $g\circ h\circ f$ is an embedding of L into the initial segment $\{y\in L\,|\,y<x\}$ , so L is not a weak well order.

As stated in the introduction, all linear orders in the following are assumed to be countable. The main result of this section is that, in ${ \mathbf {ATR}}_0$ , any scattered weak well order W has a Cantor normal form: that is to say, there is a well order $\alpha $ and a non-increasing sequence $\langle \sigma (0),\ldots ,\sigma (n-1)\rangle \in \alpha ^{<\omega }$ such that W is isomorphic to the order $\omega ^{\sigma (0)}+\cdots +\omega ^{\sigma (n-1)}$ . This can be explained as follows: given a linear order X, we define $\omega (X)$ as the order with underlying set

$$ \begin{align*} \omega(X)=\{\langle x_0,\ldots,x_{n-1}\rangle\,|\,x_i\in X\text{ and }x_0\geq_X\cdots\geq_X x_{n-1}\} \end{align*} $$

and lexicographic comparisons. To make things more precise, we write $l(\sigma )$ for the length and $\sigma _i$ for the entries of a sequence $\sigma =\langle \sigma _0,\ldots ,\sigma _{l(\sigma )-1}\rangle $ . For $\sigma ,\tau \in \omega (X)$ , we also denote $\sigma +\tau =\langle \sigma _0,\ldots ,\sigma _{i-1},\tau _0,\ldots ,\tau _{l(\tau )-1}\rangle $ where $i<l(\sigma )$ is minimal with $\sigma _i<\tau _0$ and $i=l(\sigma )$ if no such index exists. Observe that $\sigma \leq _{\omega (X)}\tau $ holds precisely if either we have $l(\sigma )\leq l(\tau )$ and $\sigma _i=\tau _i$ for all $i<l(\sigma )$ or there is some $j<\min \{l(\sigma ),l(\tau )\}$ with $\sigma _j<_X\tau _j$ and $\sigma _i=\tau _i$ for $i<j$ . Accordingly, the Cantor normal form of W can be defined as an element $\sigma \in \omega (\alpha )$ such that W is isomorphic to the initial segment $\{x\in \omega (\alpha )\,|\, x<_{\omega (\alpha )}\sigma \}$ , also denoted by $\sigma $ for short. In the special case where $\sigma =\langle \beta \rangle $ , we write the same initial segment as $\omega ^{\beta }$ instead.

In [14], Montalbán uses the notion of Hausdorff rank, discussed below, to show that any scattered linear order can be decomposed into the sum of hereditarily indecomposable linear orders. Moreover, assuming a statement equivalent to Fraïssé’s conjecture, that sum is finite. Hereditarily indecomposable linear orders can be represented as well founded trees with labels from the set $\{+,-\}$ on each node. The order associated with such a tree T is called the linearization of T. The linearization is indecomposable to the left if the label on the root of T is $"-"$ , indecomposable to the right if the same label is $"+"$ , in the sense explained below Proposition 1.5. In the former case, the linearization is not a weak well order, since it embeds in any of its initial segments. Moreover, any subtree of T represents a convex subset of the linearization, i. e., a suborder A such that if $x,z\in A$ and $x<y<z$ then $y\in A$ . In general, the following relation holds between a weak well order and its convex subsets:

Remark 2.2. A linear order X is a weak well order if and only if the same is true for every convex subset $A\subseteq X$ . In fact, suppose that for some convex subset A we have an embedding $f:J\rightarrow J_0$ of initial segments $J_0\subsetneq J\subseteq A$ . Write X as $I+A+I'$ and consider $\operatorname {id}_I$ , the identity map on I. Then $I+J$ embeds into $I+J_0$ via $\operatorname {id}_I+f$ .

The convex subsets associated with subtrees of T are themselves hereditarily indecomposable linear orders. In light of the previous remark, if T has at least one node with label $"-"$ its linearization is not a weak well order. Conversely, if all the nodes of T have label $"+"$ , the linearization of T is a suborder of the Kleene–Brouwer order on a well founded tree related to T, and hence ${ \mathbf {ACA}}_0$ proves that it is a well order. It follows by Lemma 1.2 that a hereditarily indecomposable linear order is a weak well order if and only if it is the linearization of a tree T with label $"+"$ on every node. Moreover, the linearization is isomorphic to $\omega ^{\operatorname {rank} (T)}$ if a rank function on T exists, and in particular when one assumes ${ \mathbf {ATR}}_0$ . Intuitively, this is the reason why in the case of weak well orders we are able to obtain a finite decomposition using only ${ \mathbf {ATR}}_0$ instead of $\text {Fra\"{i}ss\'{e}}$ ’s conjecture. Below, we prove this in detail.

First, we recall some known facts about scattered linear orders. Consider a linear order L and a well order $\alpha $ . We can assume that the field of L consists of natural numbers. We define by simultaneous transfinite recursion a subset $L_{\beta }\subseteq L$ and an equivalence relation $\sim _{\beta }$ on L for all $\beta <\alpha $ . We set $L_{\beta }=\{x\in L\,|\,x\le _{\mathbb {N}} y \text { for all }y\in L \text { with } x\sim _{\beta } y\}$ for all $\beta $ , and $\sim _0$ equal to the identity. Moreover, we declare that $a\sim _{\beta +1}b$ holds if there exist finitely many points $c_0\le _L\cdots \le _Lc_{n}$ in $L_{\beta }$ such that either $a\leq _L b$ and $a\sim _{\beta } c_0\wedge b\sim _{\beta } c_{n}$ or $b\le _L a$ and $b\sim _{\beta } c_0\wedge a\sim _{\beta } c_{n}$ , and also for all x between a and b there exists a unique $i\le n$ with $x\sim _{\beta } c_i$ . Finally, if $\lambda $ is a limit ordinal, let $a\sim _{\lambda } b$ hold if we have $a\sim _{\gamma } b$ for some successor ordinal $\gamma <\lambda $ . A posteriori, this approach shares some similarities with Dushnik and Miller’s original proof: in their argument, they identify two points $x,y\in L$ if the interval between x and y is a well order. This requires $\Pi ^1_1$ -comprehension, since the notion of well order is $\Pi ^1_1$ -complete. Now, note that $L_0=L$ and for all $\beta $ , if $x,y$ are distinct elements of $L_{\beta }$ then $x\not \sim _{\beta } y$ . The set $L_{\beta }$ is called the $\beta $ th Hausdorff derivative of L. If $a\sim _{\beta } b$ , we say that a and b are $\beta $ -neighbours. The $\beta $ -neighbourhood of a is defined as $N^{\beta }(a)=\{b\in L\,|\,b\sim _{\beta } a\}$ . It is easy to see that $\beta $ -neighbourhoods are convex. Moreover, if $b\sim _{\beta +1}a$ , we have that $N^{\beta }(b)\subseteq N^{\beta +1}(a)$ . Therefore, $N^{\beta +1}(a)$ may be written as $\sum _{b\in I}N^{\beta }(b)$ , where $I=N^{\beta +1}(a)\cap L_{\beta }$ . In ${ \mathbf {ATR}}_0$ we can define the sequences $(\sim _{\beta })_{\beta <\alpha }$ and $(L_{\beta })_{\beta <\alpha }$ , for any countable well order $\alpha $ .

Theorem 2.3 (Clote).

Assume ${ \mathbf {ATR}}_0$ and consider a scattered linear order L. Then there exists a countable well order $\alpha $ , an $a\in L$ and $\beta <\alpha $ such that $L_{\beta }=\{a\}$ .

For a proof we refer the reader to Lemmas 13 and 14 of [2]. Given $\beta $ and a as in the theorem, we get that $L=N^{\beta }(a)$ . In fact, if $b\in L$ and c has minimal code among the $x\in L$ with $x\sim _{\beta } b$ , it follows that $c\in L_{\beta }$ and hence $c=a$ . But then we have $b\in N^{\beta }(a)$ . The minimal ordinal $\beta $ such that $L_{\beta }=\{a\}$ holds for an appropriate $a\in L$ is called the Hausdorff rank of L. In the following we adapt the proof of [14, Lemma 3.4] to our needs.

Theorem 2.4 ( ${ \mathbf {ATR}}_0$ ).

Every weak well order L admits a Cantor normal form, i.e., there is a well order $\alpha $ and a $\sigma \in \omega (\alpha )$ such that L is isomorphic to the initial segment $\sigma $ .

Proof If L is a weak well order, it is scattered by Lemma 2.1. Therefore, we can use ${ \mathbf {ATR}}_0$ to define the sequences $(\sim _{\beta })_{\beta <\alpha }$ and $(L_{\beta })_{\beta <\alpha }$ for an $\alpha $ that satisfies Theorem 2.3. We aim to define, for all $\beta <\alpha $ and all $a\in L_{\beta }$ , a sequence $\sigma \in \omega (\beta +1)$ and an isomorphism between $N^{\beta }(a)$ and the initial segment $\sigma $ . Since Theorem 2.3 states that there exist $\beta <\alpha $ and $a\in L$ with $L=N^{\beta }(a)$ , the sequence $\sigma $ we find in that instance lists the exponents for the Cantor normal form of L.

We proceed by arithmetical transfinite recursion. Take a successor ordinal $\beta +1$ and assume we have defined all the desired sequences and isomorphisms up to level $\beta $ . Fix $a\in L_{\beta +1}$ and consider the $b\in L_{\beta }\cap N^{\beta +1}(a)$ : all of those b are separated from a, and hence from each other, by at most finitely many points of $L_{\beta }$ . Hence, they are enumerated by the indices in some $M\subseteq \mathbb {Z}$ , and we can write $N^{\beta +1}(a)=\sum _{i\in M}N^{\beta }(b_i)$ . Inductively, for each $i\in M$ we have a sequence $\sigma _i\in \omega (\beta +1)$ and an isomorphism $\phi _i$ between $N^{\beta }(b_i)$ and $\sigma _i$ . If M is finite, write it as $\{0,\ldots ,n\}$ . By summing the isomorphisms $\phi _i$ , we obtain an isomorphism between $N^{\beta +1}(a)$ and the initial segment $\sigma $ where the sequence $\sigma $ is equal to $\sigma _0+\cdots +\sigma _n$ .

Now suppose M is infinite. We claim that we have $M=\omega $ , modulo a change of indices. In fact, suppose that an initial segment $M'$ of M was an infinite descending sequence: in that case, the induction hypothesis would yield an initial segment of $N^{\beta +1}(a)$ isomorphic to $\sum _{i\in \omega ^*}\omega ^{X(i)}$ , where X is an infinite sequence of elements of $\beta +1$ obtained by juxtaposing to the left the finite sequences $\sigma _j$ for $j\in M'$ . We observe that there is an index J and an increasing map $h:[J,+\infty [\rightarrow [J+1,+\infty [$ with $X(i)\le _{\alpha } X(h(i))$ for all $i\ge J$ . In fact, if no such J and h did exist, for arbitrarily large i we would find that $X(i)$ is greater than $X(j)$ for all except finitely many j. But this would imply that $\beta +1$ is not well founded. We now see that $\sum _{i\le ^*J}\omega ^{X(i)}$ embeds into $\sum _{i\le ^*J+1}\omega ^{X(i)}$ . Since isomorphisms preserve weak well orders and convexity, we have that $N^{\beta +1}(a)$ contains a convex subset which is not a weak well order. But $N^{\beta +1}(a)$ is convex in L, which is a weak well order, so this contradicts Remark 2.2. This proves our claim that $M=\omega $ .

We now have that $N^{\beta +1}(a)\cap L_{\beta }$ consists of a sequence $\{b_j\,|\,j\in \omega \}$ and that each $N^{\beta }(b_j)$ is isomorphic to an appropriate $\sigma _j\in \omega (\beta +1)$ . Write an infinite sequence . By summing isomorphisms, we obtain that $N^{\beta +1}(a)$ is isomorphic to $\sum _{i\in \omega }\omega ^{Y(i)}$ . We distinguish two cases. First, suppose that there exists an index j such that, for all $k>j$ , we have $\beta \not \in \operatorname {rng}(\sigma _k)$ , and write . Observe that $\sup Y'=\beta $ . In fact, if there existed a $\gamma <\beta $ with $\gamma \ge \sup Y'$ , we would have that for all i, all the points in $\omega ^{Y'(i)}$ are $\gamma $ -neighbours. But then, the $\gamma $ th derivative of $\sum _{i\in \omega }\omega ^{Y'(i)}\cong \sum _{k>j}\sum _{n<\operatorname {lh}{\sigma _k}}\omega ^{\sigma _k(n)}$ would be $\omega $ , and hence all the points in the latter would be $\beta $ -neighbours. This contradicts the hypothesis that M is infinite. Since $\sup Y'=\beta $ , we can find an increasing sequence of indices $0=i_0,i_1,i_2,\ldots $ such that $\sup _{n\in \omega }Y'(i_n)=\beta $ and $Y'(i_n)>Y'(j)$ for all n and all $j<i_n$ . The well orders $\omega ^{Y'(i_n)}$ are indecomposable, so for all n we have an arithmetical isomorphism between $\omega ^{Y'(i_n+1)}+\omega ^{Y'(i_n+2)}+\cdots +\omega ^{Y'(i_{n+1})}$ and $\omega ^{Y'(i_{n+1})}$ . Thus, we obtain $\sum _{i<\omega }\omega ^{Y'(i)}\cong \sum _{n<\omega }\omega ^{Y'(i_n)}\cong \omega ^{\beta }$ . We then find the Cantor normal form of $N^{\beta +1}(a)$ as in the case where M is finite. In the other case, $\beta $ occurs infinitely often in Y. If so, we get that $N^{\beta +1}(a)$ is isomorphic to $\omega ^{\beta +1}$ , with a similar argument. This concludes the successor case.

Now consider a limit ordinal $\lambda $ and $a \in L_{\lambda }$ . Fix an increasing sequence of successor ordinals $\beta (i)<\lambda $ with $\lambda =\sup _{i\in \omega } \beta (i)$ . Then $N^{\lambda }(a)=\bigcup _{i<\omega }N^{\beta (i)}(a)$ , and each term of the union is isomorphic to $\sigma _i$ for an appropriate $\sigma _i\in \omega ({\beta (i)+1})$ . We claim that there exists an I such that $N^{\beta (I)}(a)$ is an initial segment of $N^{\lambda } (a)$ . Suppose not: then we find a strictly increasing subsequence of indices $i_n$ such that $N^{\beta (i_{n+1})}(a)$ extends $N^{\beta (i_n)}(a)$ to the left. In other words, we find convex subsets $C_n$ such that $C_n+N^{\beta (i_n)}(a)$ is an initial segment of $N^{\beta (i_{n+1})}(a)$ . Hence, $C_n$ is isomorphic to an initial segment of $\sigma _{i_{n+1}}\subseteq \omega ^{\beta (i_{n+1})+1}$ . On the other hand, that initial segment must have order type at least $\omega ^{\beta (i_n)}$ , for otherwise the points in $C_n$ would be $\beta {(i_n)}$ -neighbours of those in $N^{\beta (i_n)}(a)$ . Moreover, since all the sequences involved are strictly increasing, we can find a strictly increasing map $h:\mathbb {N}\rightarrow \mathbb {N}$ verifying $\beta (i_{n+1})+1\le \beta (i_{h(n)})$ for all n. We then get ${\operatorname {otp}(C_n)\le \omega ^{\beta (i_{n+1})+1}\le \operatorname {otp} (C_{h(n)})}$ , so that $C_n$ embeds into $C_{h(n)}$ . Thus, the convex subset $\sum _{n\in \omega ^*}C_n$ embeds into $\sum _{n\le ^*1}C_n$ , which contradicts Remark 2.2.

Still in the limit case, we now know that $N^{\beta (i)}{(a)}$ is an initial segment of $N^{\lambda }(a)$ for sufficiently large i. For large $i<j$ , the isomorphisms $N^{\beta (i)}(a)\cong \sigma _i\subseteq \sigma _j$ and $N^{\beta (j)}(a)\cong \sigma _j$ must thus agree on $N^{\beta (i)}(a)$ , since embeddings between initial segments of well orders are necessarily unique. We can thus glue them to get an isomorphism between $N^{\lambda }(a)$ and an initial segment of $\omega ^{\lambda }$ , which has the desired form $\sigma $ for a suitable sequence $\sigma \in \omega (\lambda +1)$ .

As explained above, we can conclude the following:

Corollary 2.5 ( ${ \mathbf {ATR}}_0$ ).

Every weak well order is a well order.

Conversely, one can of course infer Theorem 2.4 from the given corollary and the aforementioned result by Hirst [9]. At the same time, we find it interesting that our proof via Hausdorff ranks does directly yield Cantor normal forms.

3 Provable and unprovable cases of weak well foundedness

In this section, we prove the following result and draw several consequences. The definition of the transformation $X\mapsto \omega (X)$ was recalled in the previous section.

Theorem 3.1 ( ${ \mathbf {RCA}}_0$ ).

A linear order X is a well order precisely if $\omega (X)$ is a weak well order.

Proof First assume that X is no well order. We fix a sequence $x_0>x_1>\ldots $ in X. To show that $\omega (X)$ is no weak well order, we embed it into the proper initial segment below $\langle x_0\rangle $ . For $\omega ^*$ as in the proof of Proposition 1.5, we have an embedding

$$ \begin{align*} \omega(\omega^*)&\to\{\sigma\in\omega(X)\,|\,\sigma<_{\omega(X)}\langle x_0\rangle\},\\ \langle i(0),\ldots,i(n-1)\rangle&\mapsto\langle x_{1+i(0)},\ldots,x_{1+i(n-1)}\rangle. \end{align*} $$

We claim that $\omega (X)$ embeds into $\omega (\omega ^*)$ . Given that the orders considered in reverse mathematics are countable, it suffices to show that $Y:=\omega (\omega ^*)\backslash \{\langle \rangle \}$ is an (effectively) dense linear order without endpoints, i. e., isomorphic to $\mathbb Q$ (cf. Lemma 2.1). To see that an arbitrary $\sigma \in Y$ is no endpoint, we note

$$ \begin{align*} \langle\sigma_0+1\rangle<_Y\sigma<_Y\langle\sigma_0,\ldots,\sigma_{l(\sigma)-1},\sigma_{l(\sigma)-1}\rangle. \end{align*} $$

Now consider an inequality $\sigma <_Y\tau $ . If we have $\sigma _i=\tau _i$ for $i<l(\sigma )<l(\tau )$ , we get

$$ \begin{align*} \sigma<_Y\langle\sigma_0,\ldots,\sigma_{l(\sigma)-1},\tau_{l(\sigma)}+1\rangle<_Y\tau. \end{align*} $$

In the remaining case, we have a $j<\min \{l(\sigma ),l(\tau )\}$ with $\sigma _i=\tau _i$ for all $i<j$ as well as $\sigma _j<^*\tau _j$ (which means $\sigma _j>\tau _j$ in $\mathbb N$ ). Here we obtain

$$ \begin{align*} \sigma<_Y\langle\sigma_0,\ldots,\sigma_{l(\sigma)-1},\sigma_{l(\sigma)-1}\rangle<_Y\tau. \end{align*} $$

To prove the other direction of our theorem, we now assume that X is a well order. Let us define $\omega ^x\cdot n$ with $x\in X$ and $n\in \mathbb N$ as the element $\sigma \in \omega (X)$ with $\sigma _i=x$ for all $i<l(\sigma )=n$ . We write $\omega ^x$ in place of $\omega ^x\cdot 1$ . In the following, we use some basic ordinal arithmetic that is readily proved in our setting (cf. [10, 22]). To show that there are no embeddings into initial segments, we first consider the following special case:

Claim. There is no embedding $f:\omega ^x\to \omega ^y\cdot n$ for $x>_X y$ and $n\in \mathbb N$ .

Proof of the claim

Aiming at a contradiction, we assume that f is an embedding as in the claim. By the pigeonhole principle, we find $k,m<n$ with

$$ \begin{align*} \omega^y\cdot m\leq f(\omega^y\cdot k)<f(\omega^y\cdot(k+1))<\omega^y\cdot(m+1). \end{align*} $$

This allows us to write

$$ \begin{align*} f(\omega^y\cdot(k+1))=\omega^y\cdot m+\omega^{y'}\cdot n'+\sigma\quad\text{with}\ y'<y\ \text{and}\ \sigma<\omega^{y'}. \end{align*} $$

For future reference, we note that $y'$ and $n'$ can be computed from y and k relative to the given f. We now get a map

$$ \begin{align*} f':\omega^y\to\omega^{y'}\cdot(n'+1)\quad\text{with}\quad f(\omega^y\cdot k+\tau)=\omega^y\cdot m+f'(\tau). \end{align*} $$

The idea is to iterate the construction to find $y>y'>\ldots $ , against the assumption that X is well founded. To perform the iteration over ${ \mathbf {RCA}}_0$ , we do not form the sequence of functions $f,f',\ldots $ but use recursion to compute elements $y_i\in X$ and numbers $k_i,m_i$ that encode the relevant information. In the base of the recursion, we declare that $y_0,k_0,m_0$ coincide with $y,k,m$ from above. For the recursion step, we introduce the abbreviations

$$ \begin{align*} \eta_i=\omega^{y_0}\cdot m_0+\cdots+\omega^{y_{i-1}}\cdot m_{i-1}\quad\text{and}\quad\xi_i=\omega^{y_0}\cdot k_0+\cdots+\omega^{y_{i-1}}\cdot k_{i-1}. \end{align*} $$

Let us inductively assume that we have

$$ \begin{align*} \eta_i+\omega^{y_i}\cdot m_i\leq f(\xi_i+\omega^{y_i}\cdot k_i)<f(\xi_i+\omega^{y_i}\cdot(k_i+1))<\eta_i+\omega^{y_i}\cdot(m_i+1). \end{align*} $$

Note that we have already established that this holds for $i=0$ . As above, we now find $y_{i+1}<y_i$ and $n"\in \mathbb N$ with

$$ \begin{align*} f(\xi_i+\omega^{y_i}\cdot(k_i+1))<\eta_i+\omega^{y_i}\cdot m_i+\omega^{y_{i+1}}\cdot(n"+1). \end{align*} $$

For $\eta _{i+1}=\eta _i+\omega ^{y_i}\cdot m_i$ and $\xi _{i+1}=\xi _i+\omega ^{y_i}\cdot k_i$ , we learn that any $k\in \mathbb N$ validates

$$ \begin{align*} \eta_{i+1}\leq f(\xi_{i+1}+\omega^{y_{i+1}}\cdot k)<f(\xi_i+\omega^{y_i}\cdot(k_i+1))<\eta_{i+1}+\omega^{y_{i+1}}\cdot(n"+1). \end{align*} $$

By the pigeonhole principle, a bounded search will thus yield $k_{i+1},m_{i+1}\leq n"$ with

$$ \begin{align*} \eta_{i+1}+\omega^{y_{i+1}}\cdot m_{i+1}&\leq f(\xi_{i+1}+\omega^{y_{i+1}}\cdot k_{i+1})<{}\\ {}&<f(\xi_{i+1}+\omega^{y_{i+1}}\cdot(k_{i+1}+1))<\eta_{i+1}+\omega^{y_{i+1}}\cdot(m_{i+1}+1), \end{align*} $$

as needed to complete the recursion step.

More generally, we now derive a contradiction from the assumption that $f:I\to I_0$ is an embedding between initial segments $I_0\subsetneq I\subseteq \omega (X)$ . Pick a $\sigma \in I\backslash I_0$ and note that $f(\sigma )\in I_0$ entails $f(\sigma )<\sigma $ . For $j\leq l(\sigma )$ we write $\sigma [j]=\langle \sigma _0,\ldots ,\sigma _{j-1}\rangle $ . We use induction on j to prove $\sigma [j]\leq f(\sigma [j])$ . In view of $\sigma [l(\sigma )]=\sigma $ , this yields the desired contradiction when we reach $j=l(\sigma )$ . For $j=0$ we note that $\sigma [0]=\langle \rangle $ is the smallest element of $\omega (X)$ . In the induction step, we have $\sigma [j+1]=\sigma [j]+\omega ^{\sigma _j}$ . If we had $f(\sigma [j+1])<\sigma [j+1]$ , we would find $y<\sigma _j$ and $n\in \mathbb N$ with

$$ \begin{align*} \sigma[j]\leq f(\sigma[j])<f(\sigma[j]+\omega^{\sigma_j})<\sigma[j]+\omega^y\cdot n. \end{align*} $$

This would yield an embedding

$$ \begin{align*} f':\omega^{\sigma_j}\to\omega^y\cdot n\quad\text{with}\quad f(\sigma[j]+\tau)=\sigma[j]+f'(\tau), \end{align*} $$

against the claim that was proved above.

The following special case is interesting insofar as $\omega ^{\omega }=\omega (\omega )$ is the proof theoretic ordinal of ${ \mathbf {RCA}}_0$ , so that the latter cannot prove its well foundedness (cf. [11]).

Corollary 3.2 ( ${ \mathbf {RCA}}_0$ ).

The order $\omega ^{\omega }$ is a weak well order.

Our next result will be used in order to lower the base theory in Theorem 3.5, which will then supersede it.

Corollary 3.3 ( ${ \mathbf {RCA}}_0$ ).

Arithmetic comprehension follows from the statement that every weak well order is a well order.

Proof In view of Theorem 3.1, the given statement entails that $\omega (X)$ is a well order whenever the same holds for X. The latter entails arithmetic comprehension, as proved by Girard [8] and Hirst [9].

Together with Proposition 1.4, we obtain the following.

Corollary 3.4 ( ${ \mathbf {RCA}}_0$ ).

Fraïssé’s conjecture entails arithmetic comprehension.

The previous corollary fills a small gap in Shore’s proof that Fraïssé’s conjecture entails arithmetic transfinite recursion, which was mentioned in the introduction. Let us note that our argument uses Fraïssé’s conjecture for arbitrary linear orders, while Shore considers restricted versions of the conjecture for well orders. In the next section, we show how the aforementioned gap can be filled for these versions as well. We now complete the proof of the main result of this paper.

Theorem 3.5 ( ${ \mathbf {RCA}}_0$ ).

The following are equivalent $:$

1. (i) arithmetic transfinite recursion,

2. (ii) every weak well order is a well order.

Proof The forward implication holds by Corollary 2.5. For the other implication, Corollary 3.3 allows us to argue in ${ \mathbf {ACA}}_0$ . Over the latter, arithmetic transfinite recursion follows from Fraïssé’s conjecture for indecomposable well orders, by a previously mentioned result of Shore [20]. We can conclude by Proposition 1.5.

When we have $X\cong \omega (X)$ , Theorem 3.1 tells us that X is a well order precisely if it is a weak well order. We want to draw the same conclusion under the prima facie weaker assumption that $\omega (X)$ embeds into X. This is not a direct consequence of the cited theorem (though we will see that it is a consequence of its proof), because there is no elementary proof that weak well orders are preserved under embeddings (or suborders), as our next observation shows.

Lemma 3.6 ( ${ \mathbf {RCA}}_0$ ).

The following are equivalent $:$

1. (i) Every weak well order is a well order.

2. (ii) If $X\le _w Y$ and Y is a weak well order, then so is X.

Proof Assuming (i) and the premise of (ii), we learn that Y and hence X is a well order. By Lemma 1.2 it follows that X is a weak well order. We now assume (ii) and derive the contrapositive of (i). Suppose that X is ill founded: any descending sequence witnesses $\omega ^*\le _w X$ , and $\omega ^*\ni i\mapsto i+1$ is an embedding into a proper initial segment. So $\omega ^*$ is no weak well order, and by (ii) the same holds for X.

Concerning the following result, we note that the well orders with $\omega (X)\leq _w X$ are the $\varepsilon $ -numbers.

Proposition 3.7 ( ${ \mathbf {RCA}}_0$ ).

Consider a linear order X. If we have $\omega (X)\leq _w X$ , then X is a well order precisely if it is a weak well order.

Proof The forward implication holds by Lemma 1.2. For the converse direction, we assume that we have $\omega (X)\leq _w X$ and that X is ill founded. As in the proof of Theorem 3.1, we learn that $\mathbb Q$ embeds into $\omega (X)$ and hence into X. By Lemma 2.1 it follows that X is no weak well order.

One might have hoped that the approach from the proof of Corollary 3.3 could be extended. Specifically, Harvey Friedman has shown that arithmetic transfinite recursion is equivalent to the statement that $\varphi _X(0)$ is well founded for any well order X, again over ${ \mathbf {RCA}}_0$ (see [13, 18] for published proofs). Here $\varphi _X(0)$ is a notation system related to the Veblen hierarchy. In view of Proposition 1.5, it would seem conceivable that ${ \mathbf {RCA}}_0$ proves $\varphi _X(0)$ to be a weak well order for any well order X. Before Corollary 2.5 had been established, one might even have tried to give a proof that $\Gamma _0=\min \{\alpha \,|\,\varphi _{\alpha }(0)=\alpha \}$ is a weak well order, perhaps in ${ \mathbf { RCA}}_0$ but at least in ${ \mathbf {ATR}}_0$ , which has proof-theoretic ordinal $\Gamma _0$ . Parallel to Corollary 3.4, this would have lead to the spectacular result that ${ \mathbf {ATR}}_0$ does not prove Fraïssé’s conjecture. However, the following result shows that none of the indicated possibilities can materialize. This yields an interesting contrast with Corollary 3.2.

Corollary 3.8. The following holds with respect to the standard notation systems for proof-theoretic ordinals (see, e.g., [16]):

1. (a) In ${ \mathbf {ACA}}_0$ one cannot prove that $\varepsilon _0=\varphi _1(0)$ is a weak well order.

2. (b) In ${ \mathbf {ATR}}_0$ one cannot prove that $\Gamma _0$ is a weak well order.

Proof The point is that embeddings $\omega (\varepsilon _0)\leq _w\varepsilon _0$ and $\omega (\Gamma _0)\leq _w\Gamma _0$ are implicit in the standard notation systems. Hence by Proposition 3.7, the result reduces to the claim that ${ \mathbf {ACA}}_0$ and ${ \mathbf {ATR}}_0$ cannot prove the well foundedness of $\varepsilon _0$ and $\Gamma _0$ , respectively. This is true because the latter are the proof-theoretic ordinals of the indicated theories (see again [16]). Let us point out that we could have invoked Corollary 2.5 rather than Proposition 3.7 in order to prove (b).

4 Fraïssé’s conjecture and $\Sigma ^0_2$ -induction

In the present section, we show that Fraïssé’s conjecture for well orders entails $\Sigma ^0_2$ -induction over ${ \mathbf {RCA}}_0$ . More precisely, it will suffice to assume either of two consequences of Fraïssé’s conjecture, which assert that the countable well orders contain no infinitely descending sequences and no infinite antichains, respectively. As noted in the introduction, this fills a small gap in Shore’s [20] proof that Fraïssé’s conjecture implies arithmetic transfinite recursion over ${ \mathbf {RCA}}_0$ . The issue with this proof is that it uses the well foundedness of $\omega ^{\omega }$ , which ${ \mathbf {RCA}}_0$ cannot prove.

In the case of Fraïssé’s conjecture for arbitrary linear orders (not necessarily well founded), the aforementioned gap is filled by our Corollary 3.2 in conjunction with Proposition 1.4 (or by the stronger Corollary 3.4). To accommodate the restriction of Fraïssé’s conjecture to well orders, we give an argument that is similar to Shore’s but works with smaller ordinals. This will necessarily involve some new idea (which we explain after the proof), because Shore uses an infinite supply of indecomposable well orders, which cannot be bounded below $\omega ^{\omega }$ . We first consider Fraïssé’s conjecture for descending sequences of well orders, which Shore denotes ( $\mathcal {WF}1$ ).

Theorem 4.1 ( ${ \mathbf {RCA}}_0$ ).

The principle of $\Sigma ^0_2$ -induction is implied by the following restriction of Fraïssé’s conjecture $:$ for any infinite sequence of well orders $L_0,L_1,\ldots $ such that each $L_{n+1}$ embeds into $L_n$ , there are $i<j$ such that $L_i$ embeds into $L_j$ .

Let us note that we can get $j+1=i$ when we know that embeddability is transitive along finite chains of arbitrary length. However, the obvious proofs of this fact use a substantial amount of induction or choice. Alternatively, we could require the stronger condition that $L_k$ embeds into $L_m$ for all $m<k$ , which is satisfied in the following construction.

Proof Consider a $\Sigma ^0_2$ -formula $\psi (x)\equiv \exists u\forall v\,\phi (x,u,v)$ . For arbitrary $n\in \mathbb N$ , we will construct well orders $N_0,N_1,\ldots $ such that $N_k$ embeds into $N_m$ for all $m<k$ and any embedding $F:N_i\to N_j$ with $i<j$ allows us to compute a set $X\subseteq \mathbb N$ with

$$ \begin{align*} \forall x<n\big(\psi(x)\leftrightarrow x\in X\lor\exists u\leq i\forall v\,\phi(x,u,v)\big). \end{align*} $$

Here $\exists u\leq i\forall v\,\phi (x,u,v)$ is equivalent to $\forall w\exists u\leq i\forall v\leq w\,\phi (x,u,v)$ , by the principle of strong $\Sigma ^0_1$ -bounding (see Exercise II.3.14 of [21]). So induction for $\psi (x)$ up to n is reduced to an instance of $\Pi ^0_1$ -induction, which is available in ${ \mathbf {RCA}}_0$ .

We would like to have $N_i=\sum _{y<2n}1+M_{i,y}$ with $M_{i,2x+1}=\omega $ and

$$ \begin{align*} M_{i,2x}\cong\begin{cases} \max(0,u-i), & \text{if}\ \psi(x)\ \text{holds and}\ u\ \text{is minimal with}\ \forall v\,\phi(x,u,v),\\ \omega, & \text{if}\ \neg\psi(x)\ \text{holds}. \end{cases} \end{align*} $$

However, this characterization of $M_{i,2x}$ cannot serve as our definition, because the case distinction is undecidable. In order to resolve this issue, we first define a computable function $(x,u)\mapsto k_x(u)$ , which may be partial. When $k_x(u-1)$ is defined (where we read $k_x(-1)=0$ for the base case), we let $k_x(u)$ be the minimal $k>k_x(u-1)$ such that there is a $v\leq k$ with $\neg \phi (x,u,v)$ , if such a $v$ can be found. If there is no such $v$ or if $k_x(u-1)$ is undefined, then $k_x(u)$ is undefined. Note that $k_x(u)$ is undefined precisely if there is a $u'\leq u$ with $\forall v\,\phi (x,u',v)$ . While the latter is undecidable as a property of u, we can decide whether a given number has the form $k_x(u)$ , since we have $k_x(0)<k_x(1)<\ldots $ and hence $u\leq k_x(u)$ . This allows us to form

$$ \begin{align*} M_{i,2x}=\{k\in\mathbb N\,|\,\text{we have}\ k=k_x(u)\ \text{for some}\ u\geq i\}, \end{align*} $$

which we consider as a suborder of $\mathbb N$ . To confirm the characterization from above, we first assume that u is minimal with $\forall v\,\phi (x,u,v)$ . As noted above, this means that $k_x(u')$ is defined precisely for $u'<u$ , which clearly yields $M_{i,2x}\cong \min (0,u-i)$ . Now assume that we have $\neg \psi (x)$ . Then $k_x(u)$ is defined for all u, so that we indeed obtain $M_{i,2x}\cong \omega $ . In particular, it follows that $N_i=\sum _{y<2n}1+M_{i,y}$ is a well order. When we have $m<k$ , we clearly get $M_{k,2x}\subseteq M_{m,2x}$ for all $x<n$ , which entails that $N_k$ embeds into $N_m$ . Thus the given consequence of Fraïssé’s conjecture yields an embedding $F:N_i\to N_j$ for some $i<j$ .

To simplify the notation for elements of $N_l$ , we write $1+M_{l,2x}=\{0\}\cup M_{l,2x}$ and identify $1+M_{l,2x+1}=1+\omega $ with $\omega $ . Each $k\in 1+M_{l,y}$ yields an element $(y,k)$ in the yth summand of $N_l=\sum _{y<2n}1+M_{l,y}$ . One can establish $F(y,0)\geq (y,0)$ by induction on $y<2n$ , using that $M_{j,y}$ embeds into $M_{i,y}$ and that no well order embeds into a proper initial segment of itself. A crucial feature of our construction is that we also get $F(2x+1,k)<(2x+2,0)$ for all $k\in \mathbb N$ , which means that F maps $M_{i,2x+1}\cong \omega $ into $M_{j,2x+1}$ . Intuitively, this is true because $N_i$ and $N_j$ have the same number of summands $\omega $ . Formally, we argue by induction from $x=n-1$ down to $x=0$ , where we interpret $(2n,0)$ as an additional point above $N_j$ , so that the claim for $x=n-1$ is immediate. For the induction step, we derive a contradiction from the assumption that we have

$$ \begin{align*} (2x,0)\leq F(2x-1,k)\quad\text{and}\quad F(2x+1,0)<(2x+2,0). \end{align*} $$

These inequalities entail that F induces an embedding of $\omega +1+M_{i,2x}$ into a proper initial segment of $1+M_{j,2x}+\omega $ . It follows that $M_{j,2x}$ must be infinite, which can only hold if we have $\neg \psi (x)$ and hence $M_{i,2x}\cong \omega \cong M_{j,2x}$ . But then we have an embedding of $\omega +\omega $ into a proper initial segment of itself, which is impossible.

Let us note that F can map elements of $M_{i,2x}$ into $M_{j,2x+1}\cong \omega $ rather than $M_{j,2x}$ . To control this phenomenon, we form the set

$$ \begin{align*} X=\{x<n\,|\,\text{there is a}\ k\in M_{i,2x}\ \text{with}\ F(2x,k)\geq (2x+1,0)\}, \end{align*} $$

which relies on bounded $\Sigma ^0_1$ -comprehension in ${ \mathbf {RCA}}_0$ (see Theorem II.3.9 of [21]). If we have $x\in X$ , there is a nonempty final segment $S\subseteq M_{i,2x}$ such that F induces an embedding of $S+M_{i,2x+1}$ into $M_{j,2x+1}\cong \omega $ (recall $F(2x+1,k)<(2x+2,0)$ from above). But then $M_{i,2x}$ cannot be isomorphic to $\omega $ , which means that we must have $\psi (x)$ . To confirm the equivalence from the beginning of this proof, we now assume that we have $\psi (x)$ but $x\notin X$ . We may then consider the minimal u with $\forall v\,\phi (x,u,v)$ . From $x\notin X$ we can infer that F induces an embedding of $M_{i,2x}$ into $M_{j,2x}$ . We thus obtain

$$ \begin{align*} M_{i,2x}\cong\min(0,u-i)\leq\min(0,u-j)\cong M_{j,2x}. \end{align*} $$

Given that we have $i<j$ , this can only be true if we have $u\leq i$ . In other words, we can conclude $\exists u\leq i\forall v\,\phi (x,u,v)$ , as in the desired equivalence.

The original argument by Shore uses different indecomposable ordinals at the place of the summands $1+M_{i,2x}+\omega $ from the previous proof. Our main new idea is that one can use copies of $\omega $ as separators between the summands $1+M_{i,2x}$ if one employs a set X to recover information that is lost when a summand maps into a separator. We now consider Fraïssé’s conjecture for antichains of well orders, which Shore denotes ( $\mathcal {WF}2$ ). Our modifications have the nice side effect that the proofs for ( $\mathcal {WF}1$ ) and ( $\mathcal {WF}2$ ) become more similar than in Shore’s original paper.

Theorem 4.2 ( ${ \mathbf {RCA}}_0$ ).

The principle of $\Sigma ^0_2$ -induction is implied by the following restriction of Fraïssé’s conjecture $:$ for any infinite sequence of well orders $L_0,L_1,\ldots $ , there are $i\neq j$ such that $L_i$ embeds into $L_j$ .

Proof Fix a $\Sigma ^0_2$ -formula $\psi (x)\equiv \exists u\forall v\,\phi (x,u,v)$ and some $n\in \mathbb N$ . As in the previous proof, we find well orders $N^{\prime }_i=\sum _{y<4n}1+M^{\prime }_{i,y}$ with $M^{\prime }_{i,4x+1}=M^{\prime }_{i,4x+3}=\omega $ and

$$ \begin{align*} M^{\prime}_{i,4x}&\cong\begin{cases} \max(0,u-i), & \text{if}\ \psi(x)\ \text{holds and}\ u\ \text{is minimal with}\ \forall v\,\phi(x,u,v),\\ \omega, & \text{if}\ \neg\psi(x)\ \text{holds}, \end{cases}\\ M^{\prime}_{i,4x+2}&\cong\begin{cases} i+u, & \text{if}\ \psi(x)\ \text{holds and}\ u\ \text{is minimal with}\ \forall v\,\phi(x,u,v),\\ \omega, & \text{if}\ \neg\psi(x)\ \text{holds}. \end{cases} \end{align*} $$

We obtain an embedding $F':N^{\prime }_i\to N^{\prime }_j$ for some indices $i\neq j$ .

Once again, we write $1+M^{\prime }_{l,2y}=\{0\}\cup M^{\prime }_{l,2y}$ and identify $1+M^{\prime }_{l,2y+1}=1+\omega $ with $\omega $ . For each $y<2n$ , the orders $M^{\prime }_{i,2y}+\omega $ and $M^{\prime }_{j,2y}+\omega $ are isomorphic. We thus get $F'(2y,0)\geq (2y,0)$ by induction on y. In contrast to the previous proof, the inequality $F'(2y+1,0)\geq (2y+1,0)$ is only available for every other y, where the parity of the admissible y corresponds to the order between i and j. Nevertheless, we again get $F'(2y+1,k)<(2y+2,0)$ for any $y<2n$ and all $k\in \mathbb N$ .

In case we have $i<j$ , we can conclude as before. So now assume $i>j$ . We put

$$ \begin{align*} X':=\{x<n\,|\,\text{there is a}\ k\in M^{\prime}_{i,4x+2}\ \text{with}\ F'(4x+2,k)\geq(4x+3,0)\}. \end{align*} $$

It is still true that $x\in X'$ entails $\psi (x)$ . To complete the proof, we show that the converse implication holds for any $x<n$ . Aiming at a contradiction, we assume that we have $\psi (x)$ but also $x\notin X'$ . The latter entails that $F'$ induces an embedding of $M^{\prime }_{i,4x+2}$ into $M^{\prime }_{j,4x+2}$ . For the minimal u with $\forall v\,\phi (x,u,v)$ , we must thus have

$$ \begin{align*} M^{\prime}_{i,4x+2}\cong i+u\leq j+u\cong M^{\prime}_{j,4x+2}. \end{align*} $$

This, however, contradicts the assumption that we have $i>j$ .

We now reaffirm that the following result of Shore [20] holds with the indicated base theory. The result remains valid when Fraïssé’s conjecture for well orders is restricted to either of the principles ( $\mathcal {WF}1$ ) and ( $\mathcal {WF}2$ ) mentioned above. To see this for ( $\mathcal {WF}1$ ), one uses our Theorem 4.1 and Shore’s Theorem 1.2 to reach arithmetic comprehension. Given the latter, one can conclude by Shore’s proof of his Theorem 3.7 (see [20] for all cited results by Shore). For ( $\mathcal {WF}2$ ) one invokes the proof of Shore’s Theorem 3.8, where his Theorem 3.1(ii) is restored by our Theorem 4.2.

Theorem 4.3 (Shore [20]).

Over the theory ${ \mathbf {RCA}}_0$ , arithmetic transfinite recursion is equivalent to Fraïssé’s conjecture for well orders, i.e., to the statement that any infinite sequence of well orders $L_0,L_1,\ldots $ admits $i<j$ such that $L_i$ embeds into $L_j$ .

We conclude with a discussion of “natural” descriptions of orders.

Remark 4.4. Given an axiom system of arbitrary strength, one can produce a recursive index of an order isomorphic to $\omega $ such that the axiom system cannot prove that the index describes a well order, as noted by G. Kreisel (see, e. g., [17]). In proof theory, this has lead to a discussion about “natural” or “canonical” descriptions of well orders. While one may not expect a definitive explication of “natural”, it is possible to isolate relevant features and to argue that specific descriptions like the standard notation system for $\varepsilon _0$ are natural (cf. [5] or the more recent [1]). For finite orders, it should not be too controversial to assert that the positive integers provide canonical representatives. In the proof of Theorem 4.1, we did not use these representatives to define the orders $M_{i,2x}$ . It was indeed crucial to work with “nonstandard” descriptions, for which we could not decide whether the resulting orders were finite. Similar phenomena occur in other parts of Shore’s proof that Fraïssé’s conjecture entails arithmetic transfinite recursion. In view of this observation, one may wonder how much strength Fraïssé’s conjecture retains when we only admit “natural” descriptions of orders. It is not clear whether this question can be answered or even formulated in a fully satisfying way. At the same time, the positive and negative results of the previous section seem to yield some relevant insights. On the positive side, the proof of the forward direction in Theorem 3.1 is based on natural properties of ordinal exponentiation. As this direction was the crucial step towards Corollary 3.4, it seems justified to conclude that arithmetic comprehension follows from Fraïssé’s conjecture for “natural” linear orders. On the negative side, the given line of argument cannot be extended beyond arithmetic comprehension, as shown by Corollary 3.8. The crucial property behind this corollary is closure under exponentiation (cf. Proposition 3.7), which can be seen as a minimal condition on natural notations for larger proof-theoretic ordinals.