Proof $(2) \implies (1)$ and $(2) \implies (3)$ are immediate. $(3) \implies (4)$ is Propositions 2.6 and 2.7. $(4) \implies (2)$ is Proposition 2.8. $(1) \implies (2)$ is Proposition 2.9.

Proof Let $T\subseteq 2^{<\mathbb {N}}$ be an infinite completely branching c.e. tree. By the statement ${\mathsf {CAC\ for\ c.e.\ binary\ trees}}$ , either there is an infinite antichain, or an infinite path P. In the former case, we are done. In the latter case, using the fact that T is completely branching, the set $\{\sigma \cdot (1-i)\mid \sigma \cdot i\prec P\}$ is an infinite antichain of T.

Proof Let $f:\mathbb {N}\to k$ be a coloring, there are two possibilities. Either $\exists i<k, \exists ^{\infty } x, f(x)=i$ , in which case there is an infinite computable f-homogeneous set. Otherwise $\forall i<k, \forall ^{\infty } x, f(x)\neq i$ , in which case we define an infinite binary $c.e.$ tree T, via a strictly increasing sequence of computable trees $(T_j)_{j\in \mathbb {N}}$ defined by $T_0 \mathrel {\mathop :}= \{0^i\mid i<k\}$ and $T_{s+1} \mathrel {\mathop :}= T_s\cup \{0^{f(s)}\cdot 1^{m+1}\}$ , where m is the number of $x<s$ such that $f(x)=f(s)$ .

Every antichain in T is of size at most k, thus, by ${\mathsf {CAC\ for\ c.e.\ binary\ trees}}$ , T must contain an infinite path, and so $\exists i<k, \exists ^{\infty } x, f(x)=i$ , which is a contradiction.

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite c.e. tree. We can deal with two cases directly: when T has a node with infinitely many immediate children, as they contain a computable infinite antichain; and when T has finitely many split nodes, in which case it has finitely many paths $P_0, \ldots , P_{k-1}$ , which are all computable. Moreover one of them is infinite, as otherwise they would all be finite, i.e., $\forall i<k, \exists s, \forall n>s, n\notin P_i$ , and thus their union would be finite since $\mathsf {B}\Pi ^0_1$ (which is equivalent to $\mathsf {B}\Sigma ^0_2$ ) yields $\exists b, \forall i<k, \exists s<b, \forall n>s, n\notin P_i$ . But since $T=\bigcup _{i<k} P_i$ , this would lead to a contradiction.

A split triple of T is a triple $(\mu , n_0, n_1)\in T\times \mathbb {N}\times \mathbb {N}$ such that $\mu , \mu \cdot n_0, \mu \cdot n_1 \in T$ . In particular, $\mu $ is a split node in T.

Idea. The general idea is to build greedily a completely branching c.e. tree S by looking for split triples in T, and mapping them to split nodes in S. This correspondence is witnessed by an injective function $f : S \to T$ that will be constructed alongside S. The main difficulty is that, since T is c.e., a split node $\rho $ can be discovered after $\mu $ even though $\rho \prec \mu $ , which means that we will not be able to ensure that S can be embedded in T. In particular, f will not be a tree morphism. However, the only property that needs to be ensured is that for every infinite antichain A of S, the set $f(A)$ will be an infinite antichain of T. To guarantee this, the function f needs to verify

(*) $$ \begin{align} \forall \sigma, \nu\in S, \sigma\bot\nu \implies f(\sigma)\bot f(\nu). \end{align} $$

During the construction, we are going to associate with each node $\sigma \in S$ a set $N_{\sigma } \subseteq T$ , which might decrease in size over time ( $N^0_{\sigma } \supseteq N^1_{\sigma } \supseteq \dots $ ), with the property that at every step s, the elements of $\{ N^s_{\sigma } : \sigma \in S\}$ are pairwise disjoint, and their union contains cofinitely many elements of T. The role of $N_{\sigma }$ is to indicate that “if a split triple is found in $N_{\sigma }$ , then the nodes in S, associated via f, must be above $\sigma $ .”

Construction. Initially, $N^0_{\varepsilon } \mathrel {\mathop :}= T$ , $S \mathrel {\mathop :}= \{\varepsilon \}$ and $f(\varepsilon ) \mathrel {\mathop :}= \varepsilon $ .

At step s, suppose we have defined a finite, completely branching binary tree $S \subseteq 2^{<\mathbb {N}}$ , and for every $\sigma \in S$ , a set $N^s_{\sigma } \subseteq T$ such that $\{N^s_{\sigma } : \sigma \in S\}$ forms a partition of T minus finitely many elements. Moreover, assume we have defined a mapping $f : S \to T$ .

Search for a split triple $(\mu , n_0, n_1)$ in $\bigcup _{\sigma \in S} N^s_{\sigma }$ . Let $\sigma \in S$ be such that $\mu \in N^s_{\sigma }$ . Let $\tau $ be any leaf of S such that $\tau \succeq \sigma $ (for example, pick the left-most successor of $\sigma $ ). Add $\tau \cdot 0$ and $\tau \cdot 1$ to S, and set $f(\tau \cdot i) = \mu \cdot n_i$ for each $i<2$ . Note that S is still completely branching.

Then, split $N^s_{\sigma }$ into three disjoint subsets $N^{s+1}_{\sigma }$ , $N^{s+1}_{\tau \cdot 0}$ , $N^{s+1}_{\tau \cdot 1}$ as follows: (for $i<2$ ) $N^{s+1}_{\tau \cdot i}\mathrel {\mathop :}= \{\rho \in N^s_{\sigma } \mid \rho \succcurlyeq \mu \cdot n_i\}$ and $N^{s+1}_{\sigma }\mathrel {\mathop :}= \{\rho \in N^s_{\tau } \mid \forall i<2, \rho \bot \mu \cdot n_i\}$ . Note that these sets do not form a partition of $N^s_{\sigma }$ as we missed the nodes in $\{\rho \in N^s_{\sigma } \mid \rho \preccurlyeq \mu \}$ , fortunately there are only finitely many of them. Lastly, set $N^{s+1}_{\nu }\mathrel {\mathop :}= N^s_{\nu }$ for every $\nu \in S - \{\sigma , \tau \cdot 0, \tau \cdot 1 \}$ .

Verification. First, let us prove that at any step s, $\bigcup _{\sigma \in S} N^s_{\sigma }$ contains infinitely many split triples, which ensures that the search always terminates. Note that $T-\bigcup _{\sigma \in S} N^s_{\sigma }$ is a c.e. subset of $\bigcup _{\sigma \in S} \{\rho \mid \rho \preceq \sigma \}$ , hence exists by bounded $\Sigma _1$ comprehension, which follows from $\mathsf {RCA}_0$ . Moreover, by assumption, T is a finitely branching c.e. tree, which means that every $\rho \in T-\bigcup _{\sigma \in S} N^s_{\sigma }$ belongs to a bounded number of split triples of T. By $\mathsf {B}\Sigma ^0_1$ (which follows from $\mathsf {RCA}_0$ ), the number of split triples in T which involve a node from $T-\bigcup _{\sigma \in S} N^s_{\sigma }$ is bounded. Since by assumption, T contains infinitely many split triples, $T-\bigcup _{\sigma \in S} N^s_{\sigma }$ must contain infinitely many of them.

Second, we prove by induction on s that $\forall s\in \mathbb {N}, \forall \sigma \neq \nu \in S, N_{\sigma }^s\bot N_{\nu }^s$ , i.e., $\forall \mu \in N_{\sigma }^s, \forall \rho \in N_{\nu }^s, \mu \bot \rho $ . At step 0, the assertion is trivially verified. At step s, suppose we found the split triple $(\mu , n_0, n_1)$ in the set $N_{\sigma }^s$ , and that $\forall i<2, f(\tau \cdot i)=\mu \cdot n_i$ where $\tau \succcurlyeq \sigma $ . Since $\mu $ was found in $N_{\sigma }^s$ , the latter is split into $N_{\tau \cdot 0}^{s+1}$ , $N_{\tau \cdot 1}^{s+1}$ and $N_{\sigma }^{s+1}$ , the other sets remain identical. By construction, and because they are all subsets of $N_{\sigma }^s$ , the assertion holds.

We now prove (*), consider $\sigma , \nu \in S$ such that $\sigma \bot \nu $ . WLOG suppose $\nu $ was added to S sooner than $\sigma $ , more precisely $f(\nu )$ appeared (as child in a split triple) at step s in some set $N_{-}^s$ , so $N_{\nu }^{s+1}$ contains $f(\nu )$ by construction. Since $\sigma $ was added to S after $\nu $ , there exists $\rho \in S$ such that $f(\sigma )\in N_{\rho }^{s+1}$ . By contradiction $\rho \neq \sigma $ holds, as otherwise $f(\sigma )\in N_{\tau }^{s+1}$ , and so $\sigma $ would extend $\tau $ by construction of S. Thus by using the previous assertion, we deduce $f(\sigma )\bot f(\nu )$ .

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be a c.e. tree. We define the computable tree $S\subseteq \mathbb {N}^{<\mathbb {N}}$ by $\langle n_0, s_0\rangle \cdot \ldots \cdot \langle n_{k-1}, s_{k-1}\rangle \in S$ if and only if for all $j<k$ , $s_j$ is the smallest integer such that $n_0\cdot \ldots \cdot n_j\in T[s_j]$ , where $T[s_j]$ is the approximation of T at stage $s_j$ .

By ${\mathsf {CAC\ for\ trees}}$ , there is an infinite chain (resp. antichain) in S, and by forgetting the second component of each string, we obtain an infinite chain (resp. antichain) in T.

Proof $\mathsf {SAC} \implies \mathsf {TAC}$ . Let $T \subseteq 2^{<\mathbb {N}}$ be an infinite, completely branching c.e. tree. Let $S \subseteq T$ be an infinite computable, completely branching set. By $\mathsf {SAC}$ , there is an infinite antichain $A \subseteq X$ . In particular, A is an antichain for T.

$\mathsf {SAC} \impliedby \mathsf {TAC}$ . Let $S \subseteq 2^{<\mathbb {N}}$ be an infinite computable, completely branching set. One can define an infinite computable tree $T \subseteq \mathbb {N}^{<\mathbb {N}}$ by letting $\sigma \in T$ iff for every $n < |\sigma |$ , $\sigma (n)$ codes for a binary string $\tau _n \in S$ , such that for every $n < |\sigma |-1$ , $\tau _{n} \prec \tau _{n+1}$ , and there is no string in S strictly between $\tau _n$ and $\tau _{n+1}$ . The tree T is such that every chain in T codes for a chain in S, and every antichain in T codes for an antichain in S. We can see T as an instance of ${\mathsf {CAC\ for\ trees}}$ . Moreover, since S is completely branching, then T has infinitely many split triples, so the proof of Proposition 2.8 applied to this instance T of ${\mathsf {CAC\ for\ trees}}$ does not use $\mathsf {B}\Sigma ^0_2$ . Thus there is either an infinite chain for T, or an infinite antichain for S. With the appropriate decoding, we obtain an infinite antichain for S.

Proof By finite Ramsey’s theorem for pairs and two colors (which holds in $\mathsf {RCA}_0$ ), there exists some $p \in \mathbb {N}$ such that for every 2-coloring of $[p]^2$ , there exists a homogeneous set of size n. Since S is infinite, there exists a subset $P \subseteq S$ of size p. By choice of p, there exists a subset $Q \subseteq P$ of size n such that either Q is a chain, or an antichain. In the latter case, we are done. In the former case, since S is completely branching, the set $\{\hat {\sigma }\mid \sigma \in Q \} \subseteq S$ is an antichain, where $\hat {\sigma }$ is the string obtained from $\sigma $ by flipping its last bit.

Proof First, since $S \subseteq 2^{<\mathbb {N}}$ completely branching, then for every $\sigma \in 2^{<\mathbb {N}}$ , the set $S_{\sigma }$ is completely branching. Suppose for the sake of contradiction that there exists two strings $\sigma , \rho \in A$ such that $S_{\sigma }$ and $S_{\rho }$ are both finite. Then pick any $\tau \in S - (S_{\sigma } \cup S_{\rho })$ with $|\tau |> \max (|\sigma |, |\rho |)$ . It follows that $\sigma \prec \tau $ and $\rho \prec \tau $ , and thus that $\sigma $ and $\rho $ are comparable, contradicting the fact that A is an antichain.

Proof Let $S \subseteq 2^{<\mathbb {N}}$ be an infinite computably branching set. We are going to build a decreasing sequence of infinite completely branching sets of strings $S_0 \supseteq S_1 \supseteq \dots $ , with $S_0\mathrel {\mathop :}= S$ , together with finite antichains $A_i\subseteq S_i$ (for $i\in \mathbb {N}$ ), in order to have an infinite antichain $A\mathrel {\mathop :}=\{\sigma _i\mid i\in \mathbb {N}\}$ where $\sigma _i\in A_i$ .

This construction will work with positive probability, and since the class of oracles computing a solution to the instance S is invariant under Turing equivalence, this implies that this class has measure 1. Indeed, by Kolmogorov’s 0-1 law, every measurable Turing-invariant class has either measure 0 or 1.

First, let $S_0\mathrel {\mathop :}= S$ . At step k, assume the sets $S_0 \supseteq S_1\supseteq \cdots \supseteq S_k$ and $A_0, \ldots , A_{k-1}$ have been defined, as well as the finite antichain $\{\sigma _0, \ldots , \sigma _{k-1}\}$ , such that $\forall \tau \in S_k, \forall i<k, \sigma _i\bot \tau $ .

Search computably for a finite antichain $A_k\subseteq S_k$ of size $2^{k+2}$ . If found, pick an element $\sigma _k\in A_k$ at random. Then define $S_{k+1}\mathrel {\mathop :}= \{\tau \in S_k\mid \sigma _k\bot \tau \mbox { and } |\tau |> |\sigma _k| \}$ for the next step.

If the procedure never stops, it yields an infinite antichain $A\mathrel {\mathop :}= \{\sigma _i\mid i\in \mathbb {N}\}$ thanks to the definition of the sets $(S_i)_{i<k}$ . Assuming that $S_k$ is an infinite completely branching set, Lemma 3.1 ensures that $A_k$ will be found.

However, if at any point, $S_k$ is not an infinite completely branching set, then at some point t we will not be able to find a large enough $A_t$ in it. If this happens, since $S_{k+1}$ is completely determined by $S_k$ and $\sigma _k$ , it means that we have chosen some “bad” $\sigma _k \in A_k$ . Luckily, by Lemma 3.2, there is at most one element of this kind in $A_k$ . Thus, if we pick $\sigma _k$ at random in $A_k$ , we have at most $\frac {1}{|A_k|}=\frac {1}{2^{k+2}}$ chances for this case to happen. So the overall probability that this procedure fails is less than $\sum _{k\geqslant 0} \frac {1}{2^{k+2}}=\frac {1}{2}$ . Hence we found an antichain with positive probability.

Proof These three statements have a computable instance such that the measure of the oracles computing a solution is 0 (see [Reference Astor, Bienvenu, Dzhafarov, Patey, Shafer, Solomon and Westrick1]).

Proof For every n, consider the construction of Proposition 3.3, where the antichain $A_k$ is of size $2^{n+k+1}$ instead of $2^{k+2}$ . For each k, let $\sigma _k \in A_k$ be the unique “bad” choice (if it exists), that is, which makes the set $S_{k+1}$ finite, and let $\tau _k$ be the string of length $n+k+1$ corresponding to the binary representation of the rank of $\sigma _k$ in $A_k$ for some fixed order on binary strings. Then one can compute $\sigma _k$ from $\tau _k$ and the finite set $A_k$ . Note that $\tau _k$ is undefined when $\sigma _k$ does not exist.

Consider the $\Sigma ^0_2$ class $\mathcal {U}_n \mathrel {\mathop :}= \{ X \in 2^{\mathbb {N}}\mid \exists k, \tau _k \prec X \}=\bigcup _k [\tau _k]$ . It verifies

$$ \begin{align*}\mu(\mathcal{U}_n) \leqslant \sum_{{k \geqslant 0}\atop {\sigma_k \text{exists}}} \mu\big([\tau_k]\big) \leqslant \sum_{k \geqslant 0} \frac{1}{2^{n+k+1}} = 2^{-n}.\end{align*} $$

Let $T_n$ be a $\Pi ^0_2$ tree such that $[T_n] = 2^{\mathbb {N}} - \mathcal {U}_n$ . We can now consider the sequence of trees $(T_n)_{n\in \mathbb {N}}$ . By $2\mbox {-}\mathsf {RAN}$ , there is some n and some $X \in [T_n]$ . For any instance of $\mathsf {SAC}$ , find a solution by running the construction given in Proposition 3.3 with the help of X to avoid the potential “bad” choice in each $A_k$ .

Proof Slaman [unpublished] proved that $2\mbox {-}\mathsf {RAN}$ does not imply $\mathsf {B}\Sigma ^0_2$ over $\mathsf {RCA}_0$ . The result can also be found in [Reference Belanger, Chong, Li, Wang and Yang2]. The corollary follows from $\mathsf {RCA}_0 \vdash \mathsf {SAC} \implies \mathsf {TAC}$ (Lemma 2.12) and $\mathsf {RCA}_0 \vdash \mathsf {TAC}+\mathsf {B}\Sigma ^0_2 \iff {\mathsf {CAC\ for\ trees}}$ (Theorem 2.5).

Proof $(2)\implies (1)$ . Let $i:\mathbb {N}\to \mathbb {N}$ be a computable (primitive recursive) function such that for any $e\in \mathbb {N}$ and $B\subseteq \mathbb {N}$ we have $\Phi ^B_{i(e)}(x)\downarrow \iff x=\Phi _e^B(e)$ . Thus,

$$\begin{align*}W_{i(e)}^B=\begin{cases} \{\Phi_e^B(e)\},&\text{if }e\in B',\\ \varnothing,&\text{otherwise.} \end{cases}\end{align*}$$

From there, define the A-computable function $f:\mathbb {N}\to \mathbb {N}$ by $f:e\mapsto g(i(e), 1)$ . It is $\mathsf {DNC}(X)$ because $g(i(e), 1)\notin W_{i(e)}^X$ since $|W_{i(e)}^X|\leqslant 1$ . Moreover, f is dominated by the computable function $e\mapsto b(i(e), 1)$ , because b computably dominates g.

$(1)\implies (2)$ . Let f be a $\mathsf {DNC}_h(X)$ function computed by A. Given the pair $e, n$ , we describe the process that defines $g(e, n)$ .

Construction. For each $i<n$ , we compute the code $u(e, i)$ of the X-computable function which, on any input, looks for the $i{\text {th}}$ element of $W_e^{X}$ . If it finds such an element, then it interprets it as an n-tuple $\langle k_0, \ldots , k_{n-1}\rangle $ and returns the value $k_i$ . If it never finds such an element, then the function diverges. Finally we define $g:e, n\mapsto \langle f(u(e, 0)), \ldots , f(u(e, n-1))\rangle .$

Verification. First, since f is dominated by h, and since the function $\langle -,\ldots , -\rangle $ computing an n-tuple is increasing on each variable, we can dominate g with the computable function

$$ \begin{align*}b:e, n\mapsto \langle h(u(e, 0)), \ldots, h(u(e, n-1))\rangle.\end{align*} $$

Now, by contradiction, suppose g does not satisfy (2), i.e., suppose there exists $e, n$ such that $|W_e^X|\leqslant n$ but $g(e, n)\in W_e^X$ . Because $W_e^X$ has fewer than n elements, we can suppose $g(e, n)$ is the $i{\text {th}}$ one for a some $i<n$ . Thus the function $\Phi _{u(e, i)}^X$ is constantly equal to $k_i$ where $g(e, n)=\langle k_0, \ldots , k_{n-1}\rangle $ , in particular $\Phi _{u(e, i)}^X(u(e, i))=k_i$ . But we also have

$$ \begin{align*}g(e, n)=\langle f(u(e, 0)), \ldots, f(u(e, n-1))\rangle\end{align*} $$

implying $f(u(e, i))=k_i=\Phi _{u(e, i)}^X(u(e, i))$ , which is impossible as f is supposed to be $\mathsf {DNC}_h(X)$ .

Proof First, since X is of degree $\mathsf {DNC}_h$ for a computable function h, by Lemma 3.10, it computes a function $g:\mathbb {N}^2\to \mathbb {N}$ such that $\forall e, n, |W_e^{\emptyset '}|\leqslant n\implies g(e, n)\notin W_e^{\emptyset '}$ and which is dominated by a computable function $b:\mathbb {N}^2\to \mathbb {N}$ .

The idea of this proof is the same as in Proposition 3.3, but this time we are going to use g to avoid selecting the potential “bad” element in each finite antichain, i.e., the element which is incompatible with only finitely many strings. For any finite set $A\subseteq S$ , let $\psi _A : \mathbb {N} \to S$ be a bijection such that .

The procedure is the following. Initially, $S_0\mathrel {\mathop :}= S$ . At step k, assume $S_k \subseteq S$ has been defined. To find the desired antichain $A_k$ we use the fixed point theorem to find an index $e_k$ such that $\Phi _{e_k}^{\emptyset '}(n)$ is the procedure that halts if it finds an antichain $A\subseteq S_k$ whose size is greater than $b(e_k, 1)$ and $\psi _A(n)\in A$ , and finds (using $\emptyset '$ ) an integer m such that $\forall \ell>m, \psi _A(\ell )\succ \psi _A(n)$ .

Define $A_k\mathrel {\mathop :}= A$ . By choice of A and $e_k$ ,

$$\begin{align*}W_{e_k}^{\emptyset'}=\begin{cases} \{\psi^{-1}_A(\rho)\},&\text{if } A_k \text{ has a bad element }\rho,\\ \varnothing,&\text{otherwise.} \end{cases}\end{align*}$$

Finally we can define $\sigma _k\mathrel {\mathop :}= \psi _A(g(e_k, 1))$ . Indeed since $|W_{e_k}^{\emptyset '}|\leqslant 1$ by construction, $g(e_k, 1)\notin W_{e_k}^{\emptyset '}$ . Moreover $\sigma _k\in A_k$ , because $g(e_k, 1)<b(e_k, 1)<|A_k|$ . This implies that $\sigma _k$ is not a bad element of $A_k$ , in other words the set $S_{k+1}\mathrel {\mathop :}= \{\tau \in S_k\mid \tau \bot \sigma _k \mbox { and } |\tau |> |\sigma _k| \}$ is infinite.

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite tree. Define the total order $<_0$ over T by $\sigma <_0\tau \iff \sigma \prec \tau \lor (\sigma \bot \tau \land \sigma (d)<_{\mathbb {N}}\tau (d))$ where $d\mathrel {\mathop :}= \min \{k\in \mathbb {N}\mid \sigma (k)\neq \tau (k)\}$ . By $\mathsf {ADS}$ , there is an infinite ascending or descending sequence $(\sigma _i)$ for $(T, <_0)$ .

If it is descending, there are two possibilities. Either , which means we eventually have an infinite $\prec $ -decreasing sequence of strings, which is impossible. Or $\exists ^{\infty } i, \sigma _i\bot \sigma _{i+1}$ , in which case we designate by $(h_k)$ the sequence $(\sigma _{\ell _k+1})_{k\in \mathbb {N}}$ of all such $\sigma _{i+1}$ , and we show that it is an antichain of T.

To do so, it suffices to prove by induction on m that . When $m=1$ , due to how $(\sigma _i)$ is structured, we have $\forall k, h_k\succcurlyeq \sigma _{\ell _k}\bot h_{k+1}$ . We now consider $h_k$ and $h_{k+(m+1)}$ . By induction hypothesis, and . Moreover since $h_k>_0 h_{k+m}>_0h_{k+(m+1)}$ , we know there are minima d and e such that $h_k(d)>h_{k+m}(d)$ and $h_{k+m}(e)>h_{k+(m+1)}(e)$ . Now $e\leqslant d$ implies $h_{k+(m+1)}(e)<h_{k+m}(e)=h_k(e)$ , and $e> d$ implies $h_{k+(m+1)}(d)=h_{k+m}(d)<h_k(d)$ ; in any case .

Now if the sequence $(\sigma _i)$ is ascending, we again distinguish two possibilities. Either , which means we eventually obtain an infinite path of the tree. Or $\exists ^{\infty } i, \sigma _i\bot \sigma _{i+1}$ , in which case we work in the same fashion as in the descending case (designate by $(h_k)$ the sequence $(\sigma _{\ell _k})_{k\in \mathbb {N}}$ of all such $\sigma _i$ , and show by induction on m that ).

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite tree. We first define a computable bijection $\psi :\mathbb {N}\to T$ . To do so, let $\varphi :\mathbb {N}^{<\mathbb {N}}\to \mathbb {N}$ be the bijection $ x_0\cdot \ldots \cdot x_{n-1}\mapsto p_0^{x_0}\times \cdots \times p_{n-1}^{x_{n-1}}-1 $ where $p_k$ is the $k{\text {th}}$ prime number. The elements of the sequence $(\varphi ^{-1}(n))_{n\in \mathbb {N}}$ that are in T form a subsequence denoted $(s_n)_{n\in \mathbb {N}}$ , and the function $\psi :\mathbb {N}\to T$ is defined by $n\mapsto s_n$ .

Note that, by construction, the range of $\psi $ is infinite and computable. Moreover, if $\sigma \prec \tau \in T$ , then $\varphi (\sigma ) < \varphi (\tau )$ , hence, $\psi ^{-1}(\sigma ) < \psi ^{-1}(\tau )$ . Also note that the range of $\psi $ is not necessarily a tree.

Let $f: [\mathbb {N}]^2 \to 2$ be the coloring defined by $f(\{x, y\}) = 1$ iff $x <_{\mathbb {N}} y$ and $\psi (x)\prec \psi (y)$ coincide. By $\mathsf {EM}$ , there is an infinite transitive set $S\subseteq \mathbb {N}$ , i.e., $\forall i<2, \forall x{<} y{<} z\in S, f(x, y)=f(y, z)=i\implies f(x, z)=i$

Note that if there are $x<y\in S$ such that $f(x, y)=0$ , then $\forall z>y\in S, f(x, z)=0$ . Indeed given $x<y<z\in S$ such that $f(x, y)=0$ , either $f(y, z)=0$ , and so by transitivity we have $f(x, z)=0$ ; or $f(y, z)=1$ , but in that case $f(x, z)\neq 1$ because it is impossible to simultaneously have $\psi (y)\prec \psi (z)$ , $\psi (x)\prec \psi (z)$ and $\psi (x)\bot \psi (y)$ .

Now two cases are possible. Either $\exists ^{\infty } j\in \mathbb {N}, f(s_j, s_{j+1})=0$ , so consider the infinite set A made of all such $s_j$ . Thanks to the previous property, A is f-homogeneous for the color $0$ , and so $\psi (A)$ is an infinite antichain. Or $\forall ^{\infty } j\in \mathbb {N}, f(s_j, s_{j+1})=1$ , so there is a large enough $k\in \mathbb {N}$ such that $\psi (s_k)\prec \psi (s_{k+1})\prec \ldots $ , i.e., we found an infinite path.

Proof First, for any n, let $e_n$ be the index of $A_n$ , i.e., $\Phi _{e_n}^{\emptyset '}=A_n$ . We also write $A_n[s]\mathrel {\mathop :}= \Phi _{e_n}^{\emptyset '[s]}[s]$ .

Idea. We are going to construct a tree $T\subseteq 2^{<\mathbb {N}}$ , such that for each $n\in \mathbb {N}$ , there is $\sigma _n\in A_n$ verifying $\sigma _n\notin T$ or $\sigma _n\in T\land \forall ^{\infty }\tau \in T, \sigma _n\prec \tau $ . These requirements are respectively denoted $\mathcal {R}_n$ and $\mathcal {S}_n$ , and $A_n$ cannot be an infinite antichain of T if one of them is met.

The sequence $(\sigma _n)$ is constructed via a movable marker procedure, with steps s and sub-steps $e<s$ . At each step s we are going to manipulate an approximation $\sigma _n^s$ of $\sigma _n$ , and variables $\widehat {\sigma }_n^s$ that will help us keep track of which requirement is satisfied by $\sigma _n^s$ .

Construction. At the beginning of each step s, let $T_s$ be the approximation of the tree T defined by $T_s\mathrel {\mathop :}= T_{s-1}\cup \{\tau _s\cdot 0, \tau _s\cdot 1\}$ , where $\tau _s$ is the leftmost (for example) leaf of $T_{s-1}$ such that $\tau _s\succcurlyeq \widehat {\sigma }_{s-1}^s$ . For $s=0$ , we let $T_0\mathrel {\mathop :}= \{\varepsilon \}$ .

At step s, sub-step e, let $\sigma _e^s$ be the string whose code is the smallest in the uniformly computable set $\{\tau \in A_e[s]{\upharpoonright }_{s}\mid (\tau \in T_s \land \tau \succcurlyeq \widehat {\sigma }_{e-1}^s) \lor \tau \notin T_s\}$ with $\widehat {\sigma }_{-1}^s \mathrel {\mathop :}= \varepsilon $ and $\sigma _e^s$ is undefined when the set is empty.

Besides, define $\widehat {\sigma }_e^s \mathrel {\mathop :}= \begin {cases} \sigma _e^s,& \text {if }\sigma _e^s\in T_s\text { (and therefore }\sigma _e^s\succcurlyeq \widehat {\sigma }_{e-1}^s),\\ \widehat {\sigma }_{e-1}^s,& \text {otherwise.} \end {cases}$

Verification. By induction on e, we prove that $\sigma _e\mathrel {\mathop :}= \lim _s\sigma _e^s$ exists and is an element of $A_e$ , also we prove $\widehat {\sigma }_e\mathrel {\mathop :}= \lim _s\widehat {\sigma }_e^s$ exists, and $\sigma _e$ satisfies $\mathcal {R}_e$ or $\mathcal {S}_e$ .

Suppose we reached a step r such that for all $e'<e$ the values of $\sigma _{e'}^r$ and $\widehat {\sigma }_{e'}^r$ have stabilized. And thus, for any step $s>r$ , as $\tau _s\succcurlyeq \widehat {\sigma }_{s-1}^s\succcurlyeq \widehat {\sigma }_{e-1}^s = \widehat {\sigma }_{e-1}$ , the tree will always be extended with nodes above $\widehat {\sigma }_{e-1}$ , implying only a finite part of the tree is not above $\widehat {\sigma }_{e-1}$ .

Now suppose k is the smallest code of a string $\tau $ such that $(\tau \in T\land \tau \succcurlyeq \widehat {\sigma }_{e-1})\lor \tau \notin T$ . Such a string exists because $A_e$ is infinite, whereas the set of strings in T that are below $\widehat {\sigma }_{e-1}$ is not. If $\tau \in T$ , then $\exists x, \forall y\geqslant x, \tau \in T_y$ , otherwise define $x\mathrel {\mathop :}= 0$ . Since $A_e$ is $\Delta _2^0$ , there exists $s\geqslant \max \{k+1, r, x\}$ such that $A_e[s]{\upharpoonright }_{k+1}$ has stabilized, i.e., $\forall t>s, A_e[t]{\upharpoonright }_{k+1}=A_e[s]{\upharpoonright }_{k+1}$ . Thus $\sigma _e^s=\tau $ because $\tau \in A_e{\upharpoonright }_{k+1}= A_e[s]{\upharpoonright }_{k+1}\subseteq A_e[s]{\upharpoonright }_s$ . This ensures that for any $t>s$ , $\sigma _e^t=\tau $ , i.e., $\sigma _e=\tau $ .

Finally, we distinguish two cases. Either $\sigma _e\in T$ and so $\exists t, \sigma _e^t\in T_t$ , thus $\forall u>t, \widehat {\sigma }_e^u=\sigma _e^u$ . So $\mathcal {S}_e$ is satisfied, as cofinitely many nodes of T will be above $\widehat {\sigma }_e=\sigma _e$ . Or $\sigma _e\notin T$ , in which case, either $\forall t, \sigma _e^t\notin T_t$ , implying $\forall t, \widehat {\sigma }_e^{\kern1pt t}\mathrel {\mathop :}= \widehat {\sigma }_{e-1}^{\kern1pt t}$ and thus $\mathcal {R}_e$ is satisfied.

Proof Since $P'\leqslant _T\emptyset '$ we can $\emptyset '$ -compute the function

$$\begin{align*}f(e, x)=\begin{cases} \Phi_e^P(x), &\text{ when }\forall y\leqslant x, \Phi_e^P(y)\downarrow\text{ and }\exists y>x, \Phi_e^P(y)\downarrow=1,\\ 1, &\text{ otherwise.} \end{cases}\end{align*}$$

Now let $A_e\mathrel {\mathop :}= \{f(e, x)\mid x\in \mathbb {N}\}$ . If $\Phi _e^P$ is total and infinite then $A_e$ is equal to it, so it is P-computable. Otherwise $A_e$ is cofinite, and in particular it is infinite and P-computable.

Proof Given P, we can use Lemma 5.2 to obtain a uniform sequence, on which we apply Theorem 5.1.

Proof It follows from the existence of a low $\mathsf {PA}$ degree by the low basis theorem (see [Reference Jockusch and Soare15, Corollary 2.2.]).

Proof By contraposition, suppose there exists a solution $(\sigma _n)_{n \in \mathbb {N}}$ such that $t_{T, (\sigma _n)_{n \in \mathbb {N}}}$ and $\ell _{(\sigma _n)_{n \in \mathbb {N}}}$ are computably dominated by t and $\ell $ respectively. Then the set

$$\begin{align*}\left\{(\tau_n)_{n \in \mathbb{N}} \;\middle| \begin{array}{l} (\tau_n)_{n \in \mathbb{N}}\text{ is an infinite antichain of }T\\ t_{T, (\tau_n)_{n \in \mathbb{N}}}\leqslant t\text{ and }\ell_{(\tau_n)_{n \in \mathbb{N}}}\leqslant\ell \end{array}\right\} \end{align*}$$

is a non-empty $\Pi _1^0$ class. It is non-empty because $(\sigma _n)_{n \in \mathbb {N}}$ belongs to it, and to show it is a $\Pi _1^0$ class, it can be written as

$$\begin{align*}\left\{(\tau_n)_{n \in \mathbb{N}}\;\middle|\ \forall n, \begin{array}{l} \forall m<n, \tau_n\bot\tau_m\\ \tau_n\in T[t(n)]\\ |\tau_n|\leqslant\ell(n) \end{array}\right\}.\end{align*}$$

Thanks to $\ell $ , the number of elements at each level n of the tree associated with this class is computably bounded by $2^{\ell (n)}$ , thus it can be coded by a $\Pi _1^0$ class of $2^{\mathbb {N}}$ . Finally since P is of $\mathsf {PA}$ degree, it computes an element of any $\Pi _1^0$ class of the Cantor space, hence the result.

Proof Let P be of low PA degree. By using Corollary 5.3 we get a computable instance T of $\mathsf {TAC}$ with no P-computable solution. Thus, by using Proposition 5.5 we deduce that, for any solution $(\sigma _n)$ , its function $t_{T, (\sigma _n)_{n \in \mathbb {N}}}$ or $\ell _{(\sigma _n)_{n \in \mathbb {N}}}$ is hyperimmune. And $(\sigma _n)_{n \in \mathbb {N}}$ computes both, since T is computable; meaning it is of hyperimmune degree.

Proof Let T be an instance of $\mathsf {TAC}$ whose solutions are all of hyperimmune degree, and let $(\sigma _n)_{n \in \mathbb {N}}$ be such a solution. By contradiction, if we suppose $t_{T, (\sigma _n)_{n \in \mathbb {N}}}$ and $\ell _{(\sigma _n)_{n \in \mathbb {N}}}$ are both computably dominated, then by Proposition 5.5, T has a P-computable solution. If we choose P to be computably dominated, then it cannot compute a solution of hyperimmune degree, hence a contradiction.

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite c.e. tree. First, let $\varphi :\mathbb {N}^{<\mathbb {N}}\to \mathbb {N}$ the bijection $ x_0\cdot \ldots \cdot x_{n-1}\mapsto p_0^{x_0}\times \cdots \times p_{n-1}^{x_{n-1}}-1 $ where $p_k$ is the $k{\text {th}}$ prime number. Define $\psi : \mathbb {N} \to T$ by letting $\psi (n)$ be the least $\sigma \in T$ (in order of apparition) such that $\phi (\sigma )$ is bigger than $\phi (\psi (0)), \phi (\psi (1)), \dots , \phi (\psi (n-1))$ . Note that, by construction, the range of $\psi $ is infinite and computable. Moreover, if $\sigma \prec \tau $ , then $\varphi (\sigma ) < \varphi (\tau )$ , hence $\psi ^{-1}(\sigma ) < \psi ^{-1}(\tau )$ . Also note that the range of $\psi $ is not necessarily a tree.

Let $f: [\mathbb {N}]^2 \to 2$ be the coloring defined by $f(\{x, y\}) = 1$ iff $x <_{\mathbb {N}} y$ and $\psi (x)\prec \psi (y)$ coincide. Let us show that f is semi-hereditary for the color 1. Suppose we have $x<y<z$ and that $f(x, z)=f(y, z)=1$ , i.e., letting $\sigma \mathrel {\mathop :}= \psi (x), \tau \mathrel {\mathop :}= \psi (y), \rho \mathrel {\mathop :}= \psi (z)$ then we have $\sigma \prec \rho $ and $\tau \prec \rho $ , thus either $\sigma \prec \tau $ or $\tau \prec \sigma $ . But since $x<y$ , i.e., $\psi ^{-1}(\sigma )<\psi ^{-1}(\tau )$ , only $\sigma \prec \tau $ can hold due to the above note, meaning $f(x, y)=1$ .

By $\mathsf {SHER}$ applied to f, there is an infinite f-homogeneous set H. If it is homogeneous for the color 0, then the set $\psi (H)$ corresponds to an infinite antichain of T. Likewise, if it is homogeneous for the color 1, then the set $\psi (H)$ is an infinite path of T.

Proof (Dorais)

We first show that any $a_j$ falls in one of these two categories:

1. 1. $\forall k>j, f(a_j, a_k)=i.$

2. 2.

Indeed, for any $\ell>j$ such that $f(a_j, a_{\ell })=i$ , by semi-heredity, $f(a_j, a_{\ell -1})=i$ . So with a finite induction we get .

There are now two possibilities. Either there are finitely many $a_j$ of type 2, and so by removing these elements, the resulting set is f-homogeneous for the color i. Otherwise there are infinitely many $a_j$ of type 2, in which case one can define an infinite f-homogeneous subset for color $1-i$ using $\mathsf {B}\Sigma _1^0(A)$ as follows: due to the observation above, “ $a_j$ is of type 2” is equivalent to the $\Sigma ^0_1(A)$ formula $\exists \ell>j, f(a_j, a_{\ell })=1-i$ . Thus, given a finite set of type 2 elements $\{a_{j_0}, \ldots , a_{j_{k-1}}\}$ , by $\mathsf {B}\Sigma _1^0(A)$ there is $b>\max \{j_0, \ldots , j_{k-1}\}$ , and so $j_k$ is defined as the smallest integer $j_k$ such that $j_k\geqslant b$ and $f(a_{j_{k-1}}, a_{j_k})=1-i$ .

Proof Let $f:[\mathbb {N}]^2\to 2$ be a semi-hereditary coloring for the color $i<2$ . We begin by constructing a tree $T\subseteq \mathbb {N}^{<\mathbb {N}}$ defined as $T\mathrel {\mathop :}= \{\sigma _n\mid n\in \mathbb {N}\}$ , where $\sigma _n$ is the unique string which is:

1. 1. strictly increasing (as a function), with last element $n;$

2. 2. weak-homogeneous for the color i, i.e., $\forall k<|\sigma _n|-1, f(\sigma _n(k), \sigma _n(k+1))=i;$

3. 3. maximal as a weak-homogeneous set, i.e., $\forall y < \sigma _n(0), f(y, \sigma _n(0))=1-i$ and

To ensure existence, unicity and that T is a tree, we prove $\sigma _n$ is obtained via the following effective procedure. Start with the string n. If the string $s_0\cdot \ldots \cdot s_m$ has been constructed, then look for the biggest integer $j<s_0$ such that $f\,(j, s_0)=i$ . If there is none, the process ends. Else, the process is repeated with the string $j\cdot s_0\cdot \ldots \cdot s_m$ .

The string obtained is maximal by construction. It is unique, because at each step, if there are two (or more) integers $j_0<j_1$ smaller than $s_0$ and such that $f\,(j_0, s_0)=f\,(j_1, s_0)=i$ , then by semi-heredity we have $f\,(j_0, j_1)=1$ . This means we will eventually add $j_0$ after $j_1$ . In particular, the string contains all the $j<n$ such that $f\,(j, n)=i$ . Moreover this shows that T is a tree, since the procedure is the same at any point during construction.

Now we can apply ${\mathsf {CAC\ for\ trees}}$ to T, leading to two possibilities. Either there is an infinite path, which is a weakly-homogeneous set for the color i thanks to condition 2. And so apply Lemma 6.5 to obtain a f-homogeneous set for the color i.

Or there is an infinite antichain, which is of the form $(\sigma _{n_j})_{j\in \mathbb {N}}$ . Let us show the set $H\mathrel {\mathop :}= \{n_j\mid j\in \mathbb {N}\}$ is f-homogeneous for the color $1-i$ . Indeed, if $f(n_s, n_t) = i$ for some $s < t$ , then $n_s \in \sigma _{n_t}$ , since $\sigma _{n_t}$ contains all the elements $y < n_t$ such that $f(y, n_t) = i$ . But then $\sigma _{n_s} \prec \sigma _{n_t}$ , contradicting the fact that $(\sigma _{n_j})_{j\in \mathbb {N}}$ is an antichain.

Proof Let A be a $\Delta _2^0$ set whose approximations are $(A_t)_{t\in \mathbb {N}}$ . We define the coloring $f(x, y)\mathrel {\mathop :}= \chi _{A_y}(x)$ , and use the statement of the proposition to obtain an infinite set B that has semi-ancestry for some color.

If B has semi-ancestry for the color 1, then $\forall x{<} y{<} z\in B, x\in A_y\land x\in A_z\implies y\in A_z$ . Now either $B\subseteq \overline {A}$ and we are done. Or $\exists x\in A\cap B$ , which means $\forall ^{\infty } y\in B, x\in A_y$ , implying that $\forall ^{\infty } y>x\in B, \forall z>y\in B, y\in A_z$ by semi-ancestry, i.e., $\forall ^{\infty } y>x\in B, y\in A$ . So we can compute a subset H of B which is infinite and such that $H\subseteq A$ .

This argument also works when B has semi-ancestry for the color 0, we just need to switch A and $\overline {A}$ , as well as $\in $ and $\notin $ , when needed.

Proof Immediate, since $\mathsf {RCA}_0\vdash \mathsf {D}_2^2\implies \mathsf {B}\Sigma ^0_2$ (see [Reference Chong, Lempp and Yang5, Theorem 1.4]).

Proof Let $f:[\mathbb {N}]^2\to 2$ be a coloring. We can apply the statement to obtain an infinite set A which has semi-ancestry for the color i, i.e., $\forall x{<} y{<} z\in A, f(x, y)=i\land f(x, z)=i\implies f(y, z)=i$ . There are two possibilities. Either there exists $a\in A$ such that $\exists ^{\infty } b>a\in A, f(a, b)=i$ , in which case all such elements b form an infinite f-homogeneous set due to the property of A. Otherwise any $a\in A$ verifies $\forall ^{\infty } b>a, f(a, b)=1-i$ , i.e., all the elements of A have a limit color equal to $1-i$ for the coloring $f{\upharpoonright }_{[A]^2}$ . Thus we can use $\mathsf {B}\Sigma ^0_2$ (Corollary 6.10) to compute an infinite homogeneous set (see [Reference Dzhafarov, Hirschfeldt and Reitzes9, Proposition 6.2]).

Proof Let $\mathcal {L} = (\mathbb {N}, <_{\mathcal {L}})$ be a linear order. Let $f: [\mathbb {N}]^2 \to 2$ be the coloring defined by $f(\{x, y\}) = 1$ iff $<_{\mathcal {L}}$ and $<_{\mathbb {N}}$ coincide on $\{x, y\}$ . By the statement of the proposition, there is an infinite set H on which the coloring is semi-hereditary for some color i.

Before continuing, note that if there is a pair $x<y\in H$ such that $f(x, y)=1-i$ then $\forall z>y\in H, f(x, z)=1-i$ . Indeed, either $f(y, z)=1-i$ , in which case by transitivity of $<_{\mathcal {L}}$ we have $f(x, z)=1-i$ . Or $f(y, z)=i$ , in which case by semi-heredity $f(x, z)=1-i$ , because otherwise it would imply that $f(x, y)=i$ .

Now if $\exists ^{\infty } x\in H, \exists y>x\in H, f(x, y)=1-i$ , then we construct an infinite decreasing sequence by induction. Suppose the sequence $x_0>_{\mathcal {L}} \ldots >_{\mathcal {L}} x_{n-1}$ has already be constructed, and we have $m\in H$ such that $f(x_{n-1}, m)=1-i$ , then we look for a $\{x<y\}$ such that $x>m$ and $f(x, y)=1-i$ . By the previous remark we have that $f(x_{n-1}, x)=1-i$ , i.e., $x_{n+1}>_{\mathcal {L}} x$ , so we extend the sequence with x and redefine $m\mathrel {\mathop :}= y$ .

Else $\forall ^{\infty } x\in H, \forall y>x\in H, f(x, y)=i$ , and so getting rid of finitely many elements yields an infinite increasing sequence.

Proof This comes from the fact that $\mathsf {RT}_2^2\iff S+\mathsf {SHER}$ by definition (with S denoting the statement in question). And we have $\mathsf {RCA}_0\vdash S\implies \mathsf {SHER}$ by using Propositions 4.1, 6.6, and 6.12.

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite c.e. tree which is stable.

Consider the total order $<_0$ , defined by $\sigma <_0\tau \iff \sigma \prec \tau \lor (\sigma \bot \tau \land \sigma (d)<\tau (d))$ where $d\mathrel {\mathop :}= \min \{y\mid \sigma (y)\neq \tau (y)\}$ . We show that it is of type $\omega +\omega ^*$ , i.e.,

$$\begin{align*}\forall\sigma\in T, (\forall^{\infty}\tau\in T \sigma<_0\tau)\;\lor\;(\forall^{\infty}\tau\in T, \tau<_0\sigma).\end{align*}$$

So let $\sigma \in T$ , there are two possibilities. Either , meaning we even have $\forall ^{\infty }\tau \in T, \sigma \prec \tau $ , which directly implies $\forall ^{\infty }\tau \in T, \sigma <_0\tau $ .

Or $\forall ^{\infty }\tau \in T, \sigma \bot \tau $ . In this case, we consider all the nodes $\tau $ successors of a prefix of $\sigma $ but not prefix of $\sigma $ , there are finitely many of them, because there are finitely many prefixes of $\sigma $ and no infinitely-branching node (WLOG, as otherwise there would be a computable infinite antichain). So we can apply the pigeon-hole principle, by using $\mathsf {B}\Sigma _2^0$ , to deduce that there is a certain $\tau $ which has infinitely many successors.

Moreover, by stability of T there cannot be another such node. Indeed, by contradiction, if there were two such nodes $\tau $ and $\tau '$ , then we would have that $\exists ^{\infty } \eta \in T, \eta \bot \tau $ , because the successors of $\tau '$ are incomparable to $\tau $ . And since $\tau $ already verifies $\exists ^{\infty } \eta \in T, \eta \succ \tau $ , contradicting the stability of T.

Therefore we have that $\forall ^{\infty } \eta \in T, \eta \succ \tau $ , and so depending on whether $\tau <_0\sigma $ or $\sigma <_0\tau $ , we obtain that $\forall ^{\infty }\eta \in T, \eta <_0\sigma $ or $\forall \eta \in T, \sigma <_0\eta $ , respectively. From there we can apply $\mathsf {SADS}$ and the proof is exactly like in Proposition 4.1.

Proof This comes from the fact that any instance of $\mathsf {SADS}$ has a low solution, as proven in [Reference Hirschfeldt and Shore13, Theorem 2.11].

Proof Let $f:\mathbb {N}\to k$ be a coloring. There are two possibilities: Either $\exists i<k, \exists ^{\infty } x, f(x)=i$ , in which case there is an infinite computable f-homogeneous set. Otherwise $\forall i<k, \forall ^{\infty } x, f(x)\neq i$ , in which case we consider the infinite tree

$$\begin{align*}T\mathrel{\mathop:}= \{\sigma\in\mathsf{Inc} \mid \forall y\leqslant \max\sigma, f(y)=f(\max\sigma)\implies y\in\mathsf{ran}\sigma\},\end{align*}$$

where $\mathsf {Inc}$ is the set of strictly increasing strings of $\mathbb {N}^{<\mathbb {N}}$ .

By hypothesis, for every node $\sigma \in T$ , $\forall ^{\infty } \tau \in T, \sigma \bot \tau $ , otherwise T would have an infinite T-computable path. Thus, T is stable. Moreover, every antichain is of size at most k, thus T is a stable tree with no infinite path and no infinite antichain, contradicting ${\mathsf {CAC\ for\ stable\ trees}}$ .

Proof Let $f:[\mathbb {N}]^2\to 2$ be a stable coloring, semi-hereditary for the color i. We distinguish two cases. Either there are finitely many integers with limit color i, meaning we can ignore them and use $\mathsf {B}\Sigma _2^0$ (Lemma 7.6) to compute an infinite homogeneous set (see [Reference Dzhafarov, Hirschfeldt and Reitzes9, Proposition 6.2]). Otherwise there are infinitely many integers whose limit color is i, in which case we use the same proof as in Proposition 6.6, but we must prove the tree T we construct is stable. So let $\sigma _n$ be a node of this tree.

Suppose first n has limit color i. Let p be sufficiently large so that $f(n, p) = i$ . As explained in Proposition 6.6, $\sigma _p$ contains all the integers $m < p$ such that $f(m, p) = i$ . It follows that $n \in \sigma _p$ . Moreover, if $n \in \sigma _p$ , then $\sigma _n \preceq \sigma _p$ . Thus, $\forall ^{\infty } p, \sigma _n\prec \sigma _p$ .

Suppose now n has limit color $1-i$ , then since there are infinitely many integers with limit color i, there is one such that $p>n$ . In particular, $\sigma _p$ verifies $\forall ^{\infty } \tau \in T, \sigma _p\prec \tau $ . Thus, if $\sigma _n\prec \sigma _p$ then $\forall ^{\infty } \tau \in T, \sigma _n\prec \tau $ , and if $\sigma _n\bot \sigma _p$ then $\forall ^{\infty } \tau \in T, \sigma _n\bot \tau $ .

Proof Let $T\subseteq \mathbb {N}^{<\mathbb {N}}$ be an infinite stable c.e. tree. The proof is the same as in Proposition 6.3, but we must verify that the coloring $f:[\mathbb {N}]^2\to 2$ defined is stable. Given $x\in \mathbb {N}$ , we claim that $\exists i<2, \forall ^{\infty } y f(x, y)=i$ . Since T is stable, either or $\forall ^{\infty } y, \psi (x)\bot \psi (y)$ holds. In the first case $\forall ^{\infty } y, f(x, y)=1$ , and in the second one $\forall ^{\infty } y, f(x, y)=0$ . Thus the coloring is stable, and the proof can be carried on.