Well-founded trees and Π¹₁ sets

If $T$ has a path $f$, then $f \uh 0 >_{\mathrm{KB}} f \uh 1 >_{\mathrm{KB}} \cdots$ is a descending sequence.

Suppose $T$ well-founded; we prove by induction on $\mathrm{rk}(T)$ that $(T, <_{\mathrm{KB}})$ is a well-ordering of type at least $\mathrm{rk}(T)$. If $T$ is empty, both are $0$. Otherwise, the nodes of $T$ other than the root are the sequences $\langle n \rangle \tau$ with $\tau \in T_{\langle n \rangle}$, and the ordering compares first the initial numbers $n$, then the sequences $\tau$ by the Kleene–Brouwer ordering; the root comes last. So $(T, <_{\mathrm{KB}})$ is the ordered sum of the orderings $(T_{\langle n \rangle}, <_{\mathrm{KB}})$ for $n = 0, 1, 2, \dots$ with $\langle n \rangle \in T$, followed by one element. Each summand is a well-ordering of type at least $\mathrm{rk}(T_{\langle n \rangle})$, by the induction hypothesis, and an ordered sum of well-orderings indexed by a well-ordering is a well-ordering. Its type is at least $\mathrm{rk}(T_{\langle n \rangle}) + 1$ for every $n$, hence at least $\mathrm{rk}(T)$.

($\Leftarrow$) $T_n$ is well-founded if and only if $\forall f\ \exists m\ f \uh m \notin T_n$, a $\Pi^1_1$ formula.

($\Rightarrow$) Write $n \in A \iff \forall f\, \varphi(n, f)$ with $\varphi$ arithmetic in prenex form. We first show, by induction on the number of number quantifiers, that every prenex arithmetic formula $\psi(f)$ is equivalent to a formula $\forall h\ \exists y\ \theta(f, h, y)$ with $\theta$ bounded.

• A bounded formula $\theta$ is equivalent to $\forall h\, \exists y\, \theta$, with dummy variables.
• If $\psi \equiv \forall x\, \chi(x)$ and $\chi(x) \equiv \forall h\, \exists y\, \theta(x, h, y)$, then $\psi \equiv \forall h'\, \exists y\, \theta(h'(0), h'', y)$, where $h''(i) = h'(i+1)$: the single function $h'$ codes both $x$ and $h$.
• If $\psi \equiv \exists x\, \chi(x)$ and $\chi(x) \equiv \forall h\, \exists y\, \theta(x, h, y)$, then $\psi \equiv \forall H\, \exists x\, \exists y\, \theta(x, H^{[x]}, y)$, where $H^{[x]}(i) = H(\langle x, i \rangle)$. Indeed, if $x_0$ witnesses $\psi$, then $\chi(x_0)$ applies to $H^{[x_0]}$. Conversely, if $\psi$ fails, choose for each $x$ a function $h_x$ with $\neg \exists y\, \theta(x, h_x, y)$, and let $H^{[x]} = h_x$; then $\exists x\, \exists y\, \theta(x, H^{[x]}, y)$ fails. The two existential quantifiers merge into one.

So $n \in A \iff \forall g\, \exists y\, \theta(n, g, y)$, where $g$ codes $f$ and the auxiliary function, and $\theta$ is bounded. The evaluation of the bounded formula $\theta(n, g, y)$ queries $g$ at finitely many arguments only. Let $R(n, \sigma)$ hold if for some $y < |\sigma|$, the evaluation of $\theta(n, g, y)$ with $\sigma$ in place of $g$ queries only arguments below $|\sigma|$ and returns true. Then $R$ is computable, and $\exists y\, \theta(n, g, y) \iff \exists m\, R(n, g \uh m)$: from left to right, take $m$ larger than $y$ and than every argument queried; from right to left, $g$ and $g \uh m$ agree on the queried arguments. Let $T_n = \{ \sigma : \neg R(n, \tau) \text{ for every } \tau \preceq \sigma \}$. Then $T_n$ is a tree, uniformly computable, and it has a path $g$ if and only if $\exists y\, \theta(n, g, y)$ fails for $g$, that is, if and only if $n \notin A$.

Both definitions are $\Pi^1_1$: “for every $f$, $f$ is not a path”, and “for every $f$, $f$ is not a descending sequence”, together with the arithmetic conditions of being a tree or a linear order. If $A$ is $\Pi^1_1$, the normal form gives a computable function $n \mapsto$ an index of $T_n$, reducing $A$ to $\mathrm{WF}$. Composing with the computable map sending an index of a tree to an index of its Kleene–Brouwer ordering reduces $A$ to $\mathrm{WO}$, by Theorem 3.2.

For each $e$ and $n$, let $T_{e,n}$ be the set of sequences $\sigma$ such that no prefix $\tau \preceq \sigma$ satisfies $\Phi_e(\langle n, \tau \rangle)[|\sigma|]\converge = 0$. It is a tree, computable uniformly in $e$ and $n$, even when $\Phi_e$ is partial. Let $(T_n)$ be given by Theorem 3.4 for a $\Pi^1_1$ set $A$, with $T_n = \{ \sigma : \neg R(n, \tau) \text{ for all } \tau \preceq \sigma \}$, and let $\Phi_e$ compute the characteristic function of $R$, with value $0$ when $R$ holds. A path of $T_n$ is a path of $T_{e,n}$. Conversely, if $f$ is a path of $T_{e,n}$, then for each $k$ the computation $\Phi_e(\langle n, f \uh k \rangle)$ converges at some stage $s$, and $f \uh m \in T_{e,n}$ for $m \geq \max(s, k)$ shows that $R(n, f \uh k)$ fails; so $f$ is a path of $T_n$. Hence $T_{e,n}$ is well-founded if and only if $T_n$ is, and $U = \{ \langle e, n \rangle : T_{e,n} \text{ is well-founded} \}$ is a $\Pi^1_1$ set whose sections $U_e = \{ n : \langle e, n \rangle \in U \}$ include all the $\Pi^1_1$ sets.

Suppose that $U$ were $\Sigma^1_1$. Then its complement would be $\Pi^1_1$, and so would be $D = \{ n : \langle n, n \rangle \notin U \}$, its preimage under the computable map $n \mapsto \langle n, n \rangle$; hence $D = U_e$ for some $e$; then $e \in D \iff \langle e, e \rangle \notin U \iff e \notin U_e = D$, a contradiction. So $U$ is not $\Sigma^1_1$. Since $U$ reduces to $\mathrm{WF}$ and $\mathrm{WO}$, these are not $\Sigma^1_1$ either: $\Sigma^1_1$ sets are closed under computable preimages.

The supremum is at most $\omega_1^{\mathrm{CK}}$; suppose that it is equal to $\omega_1^{\mathrm{CK}}$. Then for every index $e$,

If $e \in \mathrm{WO}$, then $|L_e| < \omega_1^{\mathrm{CK}}$, so some $d \in A$ has $|L_d| \geq |L_e|$, and $L_e$ embeds into $L_d$ by the comparison theorem (Theorem 1.3). Conversely, a linear order that embeds into a well-ordering is a well-ordering, since a descending sequence would be mapped to a descending sequence. The right-hand side is $\Sigma^1_1$: "$d \in A$" is $\Sigma^1_1$, ”$h$ is an order-preserving injection” is arithmetic, and existential quantifiers combine. So $\mathrm{WO}$ would be $\Sigma^1_1$, contradicting Proposition 3.6.

1. Let $d$ be an index of a computable well-ordering of type $\alpha$. Then $e \in \mathrm{WO}_{<\alpha}$ if and only if $L_e$ is a linear order that embeds into a proper initial segment of $L_d$, a $\Sigma^1_1$ condition; and if and only if $e \in \mathrm{WO}$ and $L_d$ does not embed into $L_e$, a $\Pi^1_1$ condition, since ”$L_d$ embeds into $L_e$” is $\Sigma^1_1$.
2. Let $f$ be the total computable function of Proposition 2.6, which maps every $a \in \mathcal O$ to an index of a computable well-ordering of type $|a|$. If $\mathcal O$ were $\Sigma^1_1$, then $\{ e : \exists a\, (a \in \mathcal O \wedge f(a) = e) \}$ would be a $\Sigma^1_1$ subset of $\mathrm{WO}$ containing well-orderings of every computable type, by Corollary 2.10. This contradicts Theorem 3.7.