The logical strength of minimal bad arrays

Given that partial rankings are well-founded, we find a well order $(\alpha,\preceq)$ and a bijection $o:Q\to\alpha$ such that $p\leq^{\prime}q$ entails $o(p)\preceq o(q)$. Let us note that the original proof by Pouzet, in which $\leq^{\prime}$ is the identity relation, is based on an arbitrary enumeration with $\alpha=\omega$. Following Pouzet, we stipulate

which amounts to a recursion over $o(p)$. It is immediate that this yields a well-founded partial order that is contained in $R$. Aiming at (i), we assume $p<^{\prime}q$. Given that $<^{\prime}$ is a partial ranking of $R$, we have $p\,R\,q$ and also $o(p)\prec o(q)$. To get $p<_{Q}q$, we show that $r<_{Q}p$ entails $r<_{Q}q$. We use induction on $o(r)$. Given $r<_{Q}p$, we have $o(r)\prec o(p)\prec o(q)$ as well as $r\,R\,p\,<^{\prime}q$. Crucially, the latter entails $r\,R\,q$, due to our definition of partial ranking for relations that are not quasi orders. For $r^{\prime}<_{Q}r<_{Q}p$ we get $r^{\prime}<_{Q}q$ by induction hypothesis, as needed to conclude $r<_{Q}q$. Let us now consider $f:[V]^{\omega}\to Q$ as in (ii). By the open Ramsey theorem, we first find $V^{\prime}\in[V]^{\omega}$ with $o(f(X))\preceq o(f(X^{-}))$ for all $X\in[V^{\prime}]^{\omega}$ (see Theorem 4.9 in conjunction with Lemma 3.1 of [9]). Consider the powerset $\mathcal{P}(Q)$ with the order that is induced by $\leq_{Q}$ as in the introduction. We look at the array

Let us note that the sets $h(X)$ are finite when we have $\alpha=\omega$, as in the original proof by Pouzet. For $W\in[V^{\prime}]^{\omega}$, the restriction of $h$ to $[W]^{\omega}$ cannot be bad. If it was, we could choose values $g(X)\in h(X)$ with $g(X)\not\leq_{Q}r$ for all $r\in h(X^{-})$, by the definition of the order on $\mathcal{P}(Q)$. In view of $g(X^{-})\in h(X^{-})$, the resulting array $g:[W]^{\omega}\to Q$ would be $\leq_{Q}$-bad. But we would also have $g(X)<_{Q}f(X)$ due to $g(X)\in h(X)$, against the minimality of $f$. Again by the open Ramsey theorem, we thus find a $W\in[V^{\prime}]^{\omega}$ such that $h(X)\leq_{\mathcal{P}(Q)}h(X^{-})$ holds for all $X\in[W]^{\omega}$. Given $r<_{Q}f(X)$ with $X\in[W]^{\omega}$, we can now argue that $r\in h(X)$ yields $r\leq_{Q}r^{\prime}$ for some $r^{\prime}\in h(X^{-})$, where we have $r^{\prime}<_{Q}f(X^{-})$ and hence $r<_{Q}f(X^{-})$. We can conclude that $f(X)\leq_{Q}f(X^{-})$ is equivalent to $f(X)\,R\,f(X^{-})$ for $X\in[W]^{\omega}$. Given that $f$ is $\leq_{Q}$-bad, it must thus be $R$-bad on $[W]^{\omega}$, as desired. ∎

Consider ${\leq_{Q}}\subseteq R$ as in the previous proposition. Given that $R$ is no better relation, we get a $\leq_{Q}$-bad array $f_{0}$. The minimal bad array lemma for quasi orders yields an array $f^{\prime}\leq_{Q}f_{0}$ that is $\leq_{Q}$-minimal $\leq_{Q}$-bad. By the previous proposition, we can restrict $f^{\prime}$ to an array $f$ that is $R$-bad. The latter must indeed be $\leq^{\prime}$-minimal $R$-bad, as an $R$-bad $g<^{\prime}f$ would be $\leq_{Q}$-bad with $g<_{Q}f\leq_{Q}f^{\prime}$. ∎

Given a $\Pi^{1}_{2}$-formula $\varphi(n)$, possibly with parameters, we consider sets $Q_{n}$ and reflexive relations $R_{n}$ as in Proposition 2.1. We need to form the set

Let $\omega^{*}$ be the order with underlying set $\mathbb{N}$ and order relation ${\leq^{*}}=\{(m,n)\,|\,m\geq n\}$. For each $n$, we consider the disjoint union $Q_{n}^{*}=Q_{n}\cup\omega^{*}$ with the relation

Now define $Q$ as the set of sequences $\sigma=\langle\sigma_{0},\ldots,\sigma_{l(\sigma)-1}\rangle$ with length $l(\sigma)$ and entries $\sigma_{i}\in Q_{i}^{*}$. To obtain a reflexive relation $R$ on $Q$, we stipulate

Then $R$ is no better relation. Indeed, we obtain $R_{i}^{*}$-bad arrays $f_{i}:[\mathbb{N}]^{\omega}\to Q_{i}^{*}$ by setting $f_{i}(X)=\min(X)\in\omega^{*}$. An $R$-bad $Q$-array is given by

For $\sigma,\tau\in Q$ we declare that $\sigma\leq^{\prime}\tau$ holds if we have $l(\sigma)=l(\tau)$ and either $\sigma_{i}=\tau_{i}$ or $\sigma_{i}\in Q_{i}$ and $\tau_{i}\in\omega^{*}$ for each $i<l(\sigma)$. It is straightforward to see that this yields a partial ranking of $R$. In view of the previous corollary, we may now consider an array $f:[V]^{\omega}\to Q$ that is $\leq^{\prime}$-minimal $R$-bad. As noted in the introduction, we can identify this array with a map $f:B\to Q$ on a block $B$ with base $V$. For $s,t\in B$, one writes $s\vartriangleleft t$ if there is an $X\in[V]^{\omega}$ with $s\sqsubset X$ and $t\sqsubset X^{-}$. That $f$ is bad means that $f(s)\,R\,f(t)$ fails for any $s\vartriangleleft t$. We show

Here $f(s)_{i}$ refers to the $i$-th entry of the sequence $f(s)\in Q$. Once the equivalence is established, the aforementioned set $X$ can be formed by arithmetic comprehension. Let us first assume that $R_{i}$ is a better relation on $Q_{i}$. Towards a contradiction, we assume that $f(s)_{i}\in Q_{i}$ holds for some $s\in B$ with $i<l(f(s))$. Let $B/s$ be the block of all $t\in B$ such that the largest number in $s$ lies strictly below the smallest number in $t$. Given $t\in B/s$, we find $r^{i}\in B$ with $s=r^{0}\vartriangleleft\ldots\vartriangleleft r^{n}=t$ (consider some $X\in[V]^{\omega}$ with $s\cup t\sqsubset X$). Since $f(r^{j})\,R\,f(r^{j+1})$ must fail for all $j<n$, we obtain $l(f(r^{j}))<l(f(r^{j+1}))$ and inductively $f(r^{j})_{i}\in Q_{i}$. Hence we have $i<l(f(s))<l(f(t))$ and $f(t)_{i}\in Q_{i}$. But then the array $B/s\ni t\mapsto f(t)_{i}\in Q_{i}$ is $R_{i}$-bad, against our assumption. For the other direction of our equivalence, we assume $f(s)_{i}\in\omega^{*}$ holds for all $s\in B$ with $i<l(f(s))$. Pick $r^{0}\vartriangleleft\ldots\vartriangleleft r^{i}$ in $B$. As above, we inductively get $j\leq l(f(r^{j}))$ and hence $i<l(f(s))$ for all $s\in B/r^{i}$. In other words, if $V^{\prime}\in[V]^{\omega}$ is the base of $B/r^{i}$, we have $i<l(f(X))$ and $f(X)_{i}\in\omega^{*}$ for all $X\in[V^{\prime}]^{\omega}$. Towards a contradiction, we now assume that $R_{i}$ is not better. Let $h:[W]^{\omega}\to Q_{i}$ be an $R_{i}$-bad array. We may assume $W\subseteq V^{\prime}$. In order to define $g:[W]^{\omega}\to Q$, we stipulate that we have $l(g(X))=l(f(X))$ as well as

This yields an $R$-bad array $g<^{\prime}f$, against minimality. ∎

Given a bad $Q$-array $f_{0}$, Laver’s version yields a bad $f\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{\prime}f_{0}$ that admits no bad $g\lessdot^{\prime}f$. One readily derives $f\leq^{\prime}f_{0}$ according to Definition 1.2. To conclude that Simpson’s version holds, we assume that $g<^{\prime}f$ is bad and derive a contradiction. Write $f:B\to Q$ and $g:C\to Q$ for blocks $B$ and $C$, where we have $\bigcup C\subseteq\bigcup B$. Let us note that we do not immediately get the contradictory $g\lessdot^{\prime}f$, unless each $t\in C$ admits an $s\in B$ with $s\sqsubset t$. For $X\subseteq\mathbb{N}$ and $s\in[\mathbb{N}]^{<\omega}$, let $X/s$ be the set of all numbers in $X$ that are larger than all elements of $s$. We write $s^{\frown}n=s\cup\{n\}$ when we have $n\in\mathbb{N}/s$. Let us now put

It is straightforward to see that $C^{\prime}$ is a block with $\bigcup C^{\prime}=\bigcup C$. We consider

Let us note that $g$ and $g^{\prime}$ induce the same continuous function from $[{\bigcup C}]^{\omega}$ to $Q$. In particular, $g^{\prime}$ is bad. To reach the desired contradiction, we verify $g^{\prime}\lessdot^{\prime}f$. First note that we have $C^{\prime}\lessdot B$ as well as $B\cap C^{\prime}=\emptyset$. Given $B\ni s\sqsubset t\in C^{\prime}$, we pick a set $X\in[{\bigcup C}]^{\omega}$ with $t\sqsubset X$. By considering the induced continuous functions, we see that $g<^{\prime}f$ entails

just as Definition 3.1 requires. ∎

We start by showing that $D$ is a block. It is clear that $\bigcup D\supseteq\bigcup C$ is infinite. Towards a contradiction, we assume that we have $t\sqsubset s$ with $s,t\in D$. Then $s$ and $t$ are not both from $C$ and not both from $E(C,B,n)\subseteq B$. For $t\in E(C,B,n)$ we would get $s\supset t\not\subseteq\bigcup C$ and hence $s\notin C$. In the remaining case, we have $t\in C$ and $s\in E(C,B,n)$. Due to $C\lessdot B$, we then find an $s^{\prime}\in B$ with $s^{\prime}\sqsubseteq t\sqsubset s\in B$, against the assumption that $B$ is a block. Thus $D$ is a $\sqsubseteq$-antichain. Now consider an infinite set $X\subseteq\bigcup D$. We want to prove that $X$ has an initial segment in $D$. In view of $X\subseteq\textstyle\bigcup B$, we may pick a $t\in B$ that validates $t\sqsubset X$. First assume that we have $t\not\subseteq\bigcup C$. By the definition of $E(C,B,n)$, all elements of $\bigcup D\backslash\bigcup C$ are bounded by $n$. Hence we have $t\subseteq[0,n]\cup\bigcup C$, so that we get $t\in E(C,B,n)\subseteq D$. Now assume we have $t\subseteq\bigcup C$. If we have $t\in C\subseteq D$, then we are done. So let us assume $t\notin C$. The latter entails $n\leq m(C,B)\leq\max t$. Due to $\bigcup D\subseteq[0,n]\cup\bigcup C$, we get $X\subseteq t\cup\bigcup C\subseteq\bigcup C$. As $C$ is a block, we find an $s\in C\subseteq D$ with $s\sqsubset X$.

It is straightforward to see that $C\lessdot B$ entails $C\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}D\lessdot B$. To complete the proof, we show $M(C,B)=M(D,B)$. For $\max t\in M(C,B)$ with $t\in B\backslash C$ but $t\subseteq\bigcup C$, we obtain $t\notin E(C,B,n)$ and hence $t\notin D$ but $t\subseteq\bigcup D$, which yields $\max t\in M(D,B)$. Conversely, consider $\max s\in M(D,B)$ with $s\in B\backslash D$ but $s\subseteq\bigcup D\subseteq[0,n]\cup\bigcup C$. As $s\not\subseteq\bigcup C$ would entail $s\in E(C,B,n)\subseteq D$, we must have $s\subseteq\bigcup C$. Since we also have $s\not\in D\supseteq C$, we obtain $\max s\in M(C,B)$. ∎

Recall that $\Pi^{1}_{2}$-comprehension is equivalent to the principle that any subset of $\mathbb{N}$ is contained in a countable coded $\beta_{2}$-model (see Theorems VII.6.9 and VII.7.4 of [19]). Here a $\beta_{2}$-model is an $\omega$-model for which $\Pi^{1}_{2}$-statements are absolute. With the help of $\beta_{2}$-models, it is straightforward to formalize the proof of the minimal bad array lemma that is given by Fraïssé [2, 7.3.5]. We provide details for the convenience of the reader and also to verify that the argument applies to general reflexive relations rather than just to quasi orders.

For a partial ranking $\leq^{\prime}$ of a reflexive binary relation $R$ on a set $Q$, we consider an $R$-bad array $f_{0}:B_{0}\to Q$ on a block. Let us pick a $\beta_{2}$-model $\mathcal{M}$ that contains $f_{0}$. The statement that a given array $g$ is minimal $R$-bad has complexity $\Pi^{1}_{2}$, as it takes a $\Pi^{1}_{1}$-formula to assert that the domain of a potential $f\lessdot^{\prime}g$ is a block. Assuming that the minimal bad array lemma fails, any $R$-bad array $g\in\mathcal{M}$ with $g\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{\prime}f_{0}$ will thus admit an $R$-bad array $f\lessdot^{\prime}g$ with $f\in\mathcal{M}$. We intend to build a sequence of $R$-bad arrays $f_{i}\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{\prime}f_{0}$ with $f_{i+1}\lessdot^{\prime}f_{i}$ such that the following additional properties hold, where we write $B_{i}$ for the block on which $f_{i}$ is defined:

1. (i)

   for any $n\in\bigcup B_{i}$ with $n\leq m(B_{i+1},B_{i})$ we have $n\in\bigcup B_{i+1}$,

2. (ii)

   for any $R$-bad $g:C\to Q$ with $g\lessdot^{\prime}f_{i}$ we have $m(B_{i+1},B_{i})\leq m(C,B_{i})$.

The indicated relation between $f_{i}$ and $f_{i+1}$ has complexity $\Pi^{1}_{2}$, by the same consideration as above. Now $\Pi^{1}_{2}$-comprehension entails $\Sigma^{1}_{2}$-dependent choice but not $\Pi^{1}_{2}$-choice (see Theorem VII.6.9 and Remark VII.6.3 of [19]). We will soon show that any $f_{i}\in\mathcal{M}$ admits an $f_{i+1}\in\mathcal{M}$ with the given properties. Once this is achieved, we can lower the quantifier complexity of our $\Pi^{1}_{2}$-condition by evaluating it in the $\beta_{2}$-model $\mathcal{M}$. Then $\Sigma^{1}_{2}$-dependent choice is more than sufficient to obtain the desired sequence of arrays $f_{i}$. To be more economical, one can pick the smallest indices that represent suitable $f_{i}$ in the coded model $\mathcal{M}$.

As promised, we now show that each $R$-bad $f_{i}\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{\prime}f_{0}$ in $\mathcal{M}$ admits an $f_{i+1}\in\mathcal{M}$ with the properties above. We have already observed that $\mathcal{M}$ contains an $R$-bad array $f:B\to Q$ with $f\lessdot^{\prime}f_{i}$, at least if there is no minimal $R$-bad array below $f_{0}$. We pick such an $f$ with $m(B,B_{i})$ as small as possible, in the sense that $\mathcal{M}$ contains no $R$-bad array $g:C\to Q$ with $g\lessdot^{\prime}f_{i}$ and $m(C,B_{i})<m(B,B_{i})$. This minimality condition extends to $g$ that do not lie in $\mathcal{M}$, by $\Pi^{1}_{2}$-absoluteness. So $f$ validates (ii) but possibly not (i). To satisfy the latter, we modify $f$. The challenge is that (ii) needs to be preserved. We will see that this holds for $f_{i+1}:B_{i+1}\to Q$ with

Let us first note that $f_{i+1}$ lies in $\mathcal{M}$ by absoluteness, since it is arithmetically definable from $f$ and $f_{i}$. By the previous lemma, $B_{i+1}$ is a block with $B\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}B_{i+1}\lessdot B_{i}$ and $m:=m(B_{i+1},B_{i})=m(B,B_{i})$. Due to this last equality, (ii) remains valid. To see that we get $f_{i+1}\lessdot^{\prime}f_{i}$, we note that $B_{i}\ni s\sqsubset t\in B_{i+1}$ forces $t\in B$, since we have $E(B,B_{i},m)\subseteq B_{i}$. It remains to show that $f_{i+1}$ is $R$-bad and validates (i).

To show that $f_{i+1}$ is $R$-bad, we argue by contradiction. Assume that we have $s,t\in B_{i+1}$ with $s\vartriangleleft t$ and $f_{i+1}(s)\,R\,f_{i+1}(t)$. Since $f$ and $f_{i}$ are bad, we cannot have $s,t\in B$ or $s,t\in B_{i}$. Concerning the two other cases, we first assume $s\in B$ and $t\in E(B,B_{i},m)\subseteq B_{i}$. Given that we have $B\lessdot B_{i}$ and $B\cap E(B,B_{i},m)=\emptyset$, we find an $s^{\prime}\in B_{i}$ with $s^{\prime}\sqsubset s$. We can conclude $m\leq\max s^{\prime}$ due to the definition of $m=m(B,B_{i})$. From $t\subseteq[0,m]\cup\bigcup B$ and $s^{\prime}\subseteq s\subseteq\bigcup B$ we now get $t\subseteq\bigcup B$ and hence $t\notin E(B,B_{i},m)$, against our assumption. Let us now assume that we have $s\in E(B,B_{i},m)\subseteq B_{i}$ and $t\in B$. We find a $t^{\prime}\in B_{i}$ with $t^{\prime}\sqsubseteq t$ and thus $s\vartriangleleft t^{\prime}$. In view of $f\lessdot^{\prime}f_{i}$, we obtain