Proof. For convenience, we assume $C=\emptyset $ since the result relativizes. Assume that A and B are hyperimmune, and fix a computable biarray $(\vec {E}, \vec {F})$ . By hyperimmunity of A applied to $\vec {E}$ , there is some n such that $E_n \subseteq \overline {A}$ . By hyperimmunity of B applied to $F_{n,0}, F_{n,1}, \dots $ , there is some m such that $F_{n,m} \subseteq \overline {B}$ . It follows that the biarray $(\vec {E}, \vec {F})$ meets $\mathcal {H}(A,B)$ .

Assume now that either A or B is not hyperimmune. Suppose first that A is not hyperimmune. Let $E_0, E_1, \dots $ be a computable array of finite sets such that $E_n> n$ and $E_n \cap A \neq \emptyset $ for every n. Then letting $F_{n,m} = \{m+1\}$ for every m, the computable biarray $(\vec {E}, \vec {F})$ does not meet $\mathcal {H}(A, B)$ . Suppose now that B is not hyperimmune. Let $D_0, D_1, \dots $ be a computable array of finite sets such that $D_n> n$ and $D_n \cap B \neq \emptyset $ for every n. Then letting $E_n = \{n+1\}$ and $F_{n,m} = D_m$ for every $m, n \in \omega $ , the computable biarray $(\vec {E}, \vec {F})$ does not meet $\mathcal {H}(A, B)$ . In both cases, $\mathcal {H}(A,B)$ is not 2-hyperimmune.⊣

Proof. Fix any stable linear order of order type $\omega + \omega ^{*}$ with no computable infinite ascending or descending subsequence. Let A and B be the $\omega $ and $\omega ^{*}$ part, respectively. By Lemma 41 in [Reference Patey16], A and B are hyperimmune. Therefore, by Lemma 2.4, $\mathcal {H}(A, B)$ is 2-hyperimmune. Any infinite ascending or descending sequence G is a subset of A or B, respectively. It follows that either A, or B is not G-hyperimmune, and by Lemma 2.4, $\mathcal {H}(A, B)$ is not G-2-hyperimmune. It follows that $\operatorname {\mathrm {\sf {SADS}}}$ does not preserve 2-hyperimmunity.⊣

Proof. Again, assume $C=\emptyset $ since the result relativizes. Fix a bifamily $\mathcal {H}$ , and a set G of hyperimmune-free degree such that $\mathcal {H}$ is not $ G$ -2-hyperimmune. We want to show that $\mathcal {H}$ is not 2-hyperimmune. Let $(\vec {E}, \vec {F})$ be a $ G$ -computable biarray which does not meet $\mathcal {H}$ . In particular, the function f defined by $f(n, m) = \max E_n, F_{n,m}$ is G-computable, and is therefore dominated by a computable function g. Define the computable biarray $(\vec {K}, \vec {L})$ by $K_n = \{n+1, \dots , g(n, 0) \}$ and $L_{n,m} = \{m+1, \dots , g(n, m) \}$ . It is easy to see that $E_n \subseteq K_n$ and $F_{n,m} \subseteq L_{n,m}$ for every $n, m \in \omega $ . Indeed, $E_n> n$ and $\max E_n \leq f(n, 0) \leq g(n,0)$ so $E_n \subseteq \{n+1, \dots , g(n, 0) \}$ . Similarly, $F_{n,m}> m$ and $\max F_{n,m} \leq f(n,m) \leq g(n,m)$ , so $F_{n,m} \subseteq \{m+1, \dots , g(n, m)\}$ . Since $(\vec {E}, \vec {F})$ does not meet $\mathcal {H}$ , $(E_n, F_{n,m}) \not \in \mathcal {H}$ , and by downward-closure of $\mathcal {H}$ under the subset relation, $(K_n, L_{n,m}) \not \in \mathcal {H}$ . It follows that $(\vec {K}, \vec {L})$ does not meet $\mathcal {H}$ and therefore that $\mathcal {H}$ is not 2-hyperimmune.⊣

Proof. Let $\mathcal {H}$ be a 2-hyperimmune family, and let T be an infinite computable binary tree. By the hyperimmune-free basis theorem [Reference Jockusch and Soare7], there is an infinite path $P \in [T]$ which is C-hyperimmune-free. By Lemma 2.6, $\mathcal {H}$ is $ P$ -2-hyperimmune.⊣

Proof. The members of $\mathcal {B}(\mathcal {H})$ are precisely the biarrays which fail meeting $\mathcal {H}$ . The equivalence follows immediately.⊣

Proof. Let $\mathcal {H}$ be a 2-hyperimmune family, and let $\vec {R} = R_0, R_1, \dots $ be an infinite computable sequenceFootnote ² of sets. By Lemma 2.8, $\mathcal {B}(\mathcal {H})$ has no computable member. By [Reference Patey13, Corollary 2.9], there is an $\vec {R}$ -cohesive set G such that $\mathcal {B}(\mathcal {H})$ has no $ G$ -computable member. By Lemma 2.8, $\mathcal {H}$ is $ G$ -2-hyperimmune.⊣

Proof. We build the coloring $f : [\omega ]^2 \to 3$ by a finite injury priority argument. For every $e \in \omega $ , we want to satisfy the following requirement:

(2.1) $$ \begin{align} \mathcal{R}_e: &\text{If}\ \Phi_e\ \text{is total, then there is some}\ n, m \in \omega\ \text{such that}\nonumber \\ &\Phi_e(n;1) \subseteq C_1(f), \Phi_e(n,m;2) \subseteq C_2(f)\ \text{and}\ \Phi_e(n;1) \to_0 \Phi_e(n,m;2). \end{align} $$

The requirements are given the usual priority ordering $\mathcal {R}_0 < \mathcal {R}_1 < \cdots $ Initially, the requirements are neither partially, nor fully satisfied.

1. (i) A requirement $\mathcal {R}_e$ requires a first attention at stage s if it is not partially satisfied and $\Phi _{e,s}(n;1) \downarrow = E$ for some set $E \subseteq \{e+1, \dots , s-1\}$ such that no element in E is restrained by a requirement of higher priority. If it receives attention, then it puts a restrain on E, commit the elements of E to be in $C_0(f)$ , and is declared partially satisfied.

2. (ii) A requirement $\mathcal {R}_e$ requires a second attention at stage s if it is not fully satisfied, and $\Phi _{e,s}(n;1) \downarrow = E$ and $\Phi _{e,s}(n,m;2) \downarrow = F$ for some sets $E, F \subseteq \{e+1, \dots , s-1\}$ such that $E \to _0 F$ and which are not restrained by a requirement of higher priority. If it receives attention, then it puts a restrain on $E \cup F$ , commit the elements of E to be in $C_1(f)$ , the elements of F to be in $C_2(f)$ , and is declared fully satisfied.

At stage 0, we let $f = \emptyset $ . Suppose that at stage s, we have defined $f(x, y)$ for every $x < y < s$ . For every $x < s$ , if it is committed to be in some $C_i(f)$ , set $f(x, s) = i$ , and otherwise set $f(x, s) = 0$ . Let $\mathcal {R}_e$ be the requirement of highest priority which requires attention. If $\mathcal {R}_e$ requires a second attention, then execute the second procedure, otherwise execute the first one. In any case, reset all the requirements of lower priorities by setting them unsatisfied, releasing all their restrains, and go to the next stage. This completes the construction. On easily sees by induction that each requirement acts finitely often, and is eventually fully satisfied. This procedure also yields a stable coloring.⊣

Proof. Let f be the stable computable coloring of Proposition 2.10. Let $G = \{ x_0 < x_1 < \cdots \}$ be an infinite f-thin set. We claim that $\mathcal {H}(f)$ is not G-2-hyperimmune. Indeed, let $(\vec {E}, \vec {F})$ be the G-computable biarray defined by $E_n = \{x_n\}$ and $F_{n,m} = \{x_{n+m}\}$ . Fix any n. Suppose that $E_n \subseteq C_1(f)$ and $F_{n,m} \subseteq C_2(f)$ (if such $E_n,F_{n,m}$ does not exist then we are done). In other words, for every sufficiently large k, $f(x_n, x_k) = 1$ and $f(x_{n+m}, x_k) = 2$ . It follows that G must be f-thin for color 0Footnote ³ , therefore $E_n \not \to _0 F_{n,m}$ and so $(E_n, F_{n,m}) \not \in \mathcal {H}(f)$ . The G-computable biarray $(\vec {E}, \vec {F})$ does not meet $\mathcal {H}(f)$ , so $\mathcal {H}(f)$ is not G-2-hyperimmune.⊣

Proof. Let $f : [\omega ]^2\rightarrow 3$ be the stable computable coloring of Proposition 2.10. Let T be the stable computable tournament defined for every $x < y$ by $T(x, y)$ iff $f(x, y) = 1$ . Let $G = \{ x_0 < x_1 < \dots \}$ be an infinite transitive subtournament. We claim that $\mathcal {H}(f)$ is not G-2-hyperimmune. Indeed, let $(\vec {E}, \vec {F})$ be the G-computable biarray defined by $E_n = \{x_n\}$ and $F_{n,m} = \{x_{n+m}\}$ . Fix n. Suppose that $E_n \subseteq C_1(f)$ and $F_{n,m} \subseteq C_2(f)$ (if such $E_n,F_{n,m}$ does not exist then we are done). In other words, for every sufficiently large k, $f(x_n, x_k) = 1$ and $f(x_{n+m}, x_k) = 2$ , so $T(x_n, x_k)$ and $T(x_k, x_{n+m})$ will hold. By transitivity of G, $T(x_n, x_{n+m})$ must hold, so $f(x_n, x_{n+m}) = 1$ . It follows that $E_n \not \to _0 F_{n,m}$ and so $(E_n, F_{n,m}) \not \in \mathcal {H}(f)$ . The G-computable biarray $(\vec {E}, \vec {F})$ does not meet $\mathcal {H}(f)$ , so $\mathcal {H}(f)$ is not G-2-hyperimmune.⊣

Proof. Let $\mathcal {H}$ be a 2-hyperimmune family, and $f : [\omega ]^{n+1} \to k$ be a computable instance of $\operatorname {\mathrm {\sf {TS}}}^{n+1}_k$ . Let $\vec {R} = \langle R_{\sigma ,i} : \sigma \in [\omega ]^n, i < k \rangle $ be the computable family of sets defined for every $\sigma \in [\omega ]^n$ and $i < k$ by

$$ \begin{align*}R_{\sigma,i} = \{ x \in \omega : f(\sigma,x) = i \}. \end{align*} $$

Since $\operatorname {\mathrm {\sf {COH}}}$ preserves 2-hyperimmunity (Corollary 2.9), there is an $\vec {R}$ -cohesive set G such that $\mathcal {H}$ is G-2-hyperimmune. Let $g : [\omega ]^n \to k$ be the $\Delta ^{0,G}_2$ instance of $\operatorname {\mathrm {\sf {TS}}}^n_k$ defined for every $\sigma \in [\omega ]^n$ by

$$ \begin{align*}g(\sigma) = \lim_{x \in G} f(\sigma, x). \end{align*} $$

By strong preservation of $\operatorname {\mathrm {\sf {TS}}}^n_k$ , there is an infinite g-thin set H such that $\mathcal {H}$ is $ G \oplus H$ -2-hyperimmune. By thinning out the set H, we obtain an infinite $ G \oplus H$ -computable f-thin set $\tilde {H}$ . In particular, $\mathcal {H}$ is $ \tilde {H}$ -2-hyperimmune.⊣

Proof. For notational convenience, we will prove the non-relativized version, which extends by routine arguments. Let $\mathcal {H}$ be a 2-hyperimmune bifamily, and let $f:\omega \rightarrow 4$ be an arbitrary instance of $\operatorname {\mathrm {\sf {TS}}}^1_4$ . Without loss of generality, assume that there is no infinite subset H of $f^{-1}(i)$ such that $\mathcal {H}$ is $ H$ -2-hyperimmune (as otherwise we are done). We are going to

$$ \begin{align*}\nonumber \bullet\ \ &\text{build 4 infinite sets}\ (G_i:i<4)\ \text{such that}\ G_i\ \text{is}\ f\text{-thin for color}\ i\ \text{and}\\ \nonumber &\mathcal{H}\ \text{is} G_i\text{-2-hyperimmune for some}\ i < 4. \end{align*} $$

We are going to build the sets $G_i$ by a Mathias forcing whose conditions are tuples $(F_0, F_1, F_2, F_3, X)$ , where $(F_i,X) $ is a Mathias condition, $F_i$ is f-thin for color i and $\mathcal {H}$ is $ X$ -2-hyperimmune. A condition $d = (E_0, E_1, E_2, E_3, Y)$ extends $c = (F_0, F_1, F_2, F_3, X)$ (written $d \leq c$ ) if $(E_i, Y)$ Mathias extends $(F_i, X)$ for every $i < 4$ .

The first lemma ensures that every sufficiently generic filter for this notion of forcing will induce four infinite sets.

A 4-tuple of sets $G_0, G_1, G_2, G_3$ satisfies a condition $c = (F_0, F_1, F_2, F_3, X)$ if $G_i$ satisfies the Mathias condition $(F_i, X)$ for every $i < 4$ . A condition c forces a formula $\varphi (G_0, G_1, G_2, G_3)$ if the formula holds for every 4-tuple of sets $G_0, G_1, G_2, G_3$ satisfying c. Given any $e_0, e_1, e_2, e_3$ , we want to satisfy the following requirements:

$$ \begin{align*}\mathcal{R}_{e_0, e_1, e_2, e_3} \mbox{ : } \mathcal{R}^0_{e_0} \vee \mathcal{R}^1_{e_1} \vee \mathcal{R}^2_{e_2} \vee \mathcal{R}^3_{e_3}, \end{align*} $$

where $\mathcal {R}^i_e$ is the requirement:

$$ \begin{align*}\text{If}\ \Phi_e^{G_i}\ \text{is total, then it meets}\ \mathcal{H}.\end{align*} $$

Lemmas 2.17, 2.29, 2.38 and 2.46 are main technical lemmas of Theorem 1.6 (where we prove a condition can be extended to force that a given Turing functional meets $\mathcal {H}$ ). We briefly explain one of the ideas of these lemmas (which also appears in the main Lemma 3.9 of Theorem 3.6) a generalization of Seetapun forcing to build weak solution. Usually, given an arbitrary instance f (of a problem), we want to build a solution G to f so that $\Phi ^G$ has a desired behaviour. Since f is not computable, we cannot search computably among initial segments F of solutions to f (call such F finite solution to f) such that $\Phi ^F$ has that behaviour. The idea of Seetapun forcing is to find sufficiently many F so that $\Phi ^F$ has that behaviour. By “sufficiently many,” it means whatever f looks like, one of F is, at least, a finite solution to f.

In our case, this means we want to find sufficiently many F such that $\Phi ^F(n;1)\downarrow $ and $\Phi ^F(n,m;2)\downarrow $ . But this is not quite enough. It only gives (by compactness) two sets $U_{n,m},V_{n,m}$ so that for every g, there is a finite solution F of g such that $\Phi ^F(n;1)\subseteq U_{n,m}\wedge \Phi ^F(n,m;2)\subseteq V_{n,m}$ . That is, $U_{n,m}$ depends on m. So one may want to try this: first, search for a sufficient collection $\mathcal {F}$ , so that $\Phi ^F(n;1)\downarrow $ for each $F\in \mathcal {F}$ ; second, search for a sufficient collection $\mathcal {E}$ each $E\in \mathcal {E}$ extends a member of $\mathcal {F}$ and $\Phi ^E(n,m;2)\downarrow $ . Let’s see what sufficiency notion $\mathcal {F}$ should satisfy. When $\mathcal {F}$ exists while $\mathcal {E}$ does not, we have that for some instance g,

(2.2) $$ \begin{align} &\text{there is no finite solution}\ E\ \text{of}\ g\ \text{such that}\ E\ \text{extends a member of}\ \mathcal{F} \nonumber\\ &\text{and}\ \Phi^E(n,m;2)\downarrow. \end{align} $$

We need to find an appropriate $F\in \mathcal {F}$ such that F is a finite solution to g and restrict G so that G extends F and G is a solution to g (because by (2.2), for such G, $\Phi ^G(n,m;2)\uparrow $ ). Here “appropriate” means: at least, F is a finite solution to f. The sufficiency notion for $\mathcal {F}$ should guarantee the existence of F. This gives the following sufficiency notion: for every two instances g and h, there is an $F\in \mathcal {F}$ such that F is a finite solution to both $g,h$ . This is exactly the sufficiency notion we use in Lemma 2.17. For more complex problems, F being a finite solution to f is not enough, but we must ensure that imposing the restriction of F does not cut the candidate space too much. This concern gives rise to the more complex sufficiency notion (Definitions 2.24 and 2.41 and Lemmas 2.42 and 2.25).

Proof. Fix $c = (F_0, F_1, F_2, F_3, X)$ . For notational convenience, we assume $X=\omega $ and $F_i = \emptyset $ . We define a partial computable biarray as follows. To obtain a desired extension of c, we take advantage of the failure of this biarray to meet $\mathcal {H}$ or its non-totality.

Defining $U_n$ . Given $n \in \omega $ , search computably for some finite set $U_n>n$ Footnote ⁴ (if it exists) such that for every pair of colorings $g,h:\omega \rightarrow 4$ , there are two colors $i_0 < i_1 < 4$ and two sets $E_{i_0}$ and $E_{i_1}$ such that for every $i \in \{i_0, i_1 \}$ , $E_i $ is both g-thin and h-thin for color i andFootnote ⁵

$$ \begin{align*}\Phi_{e_i}^{ E_i}(n;1) \downarrow \subseteq U_n. \end{align*} $$

Defining $V_{n,m}$ . Given $n, m \in \omega $ , search computably for some finite set $V_{n,m}>m$ (if it exists) such that for every coloring $g:\omega \rightarrow 4 $ , there is an $i < 4$ and a finite set $E_i g$ -thin for color i such that

$$ \begin{align*}\Phi_{e_i}^{ E_i}(n;1) \downarrow \subseteq U_n \wedge \Phi_{e_i}^{ E_i}(n, m;2) \downarrow \subseteq V_{n,m}. \end{align*} $$

We now have multiple outcomes, depending on which of $U_n$ and $V_{n,m}$ is found.

• • Case 1: $U_n$ is not found for some $n \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of pairs of colorings $g,h:\omega \rightarrow 4$ is nonempty: there are three indices $i_0 < i_1 < i_2 < 4$ such that for every $i \in \{i_0, i_1, i_2\}$ and every finite set $E_i$ being both g-thin and h-thin for color i, we have $\Phi _{e_i}^{E_i}(n;1) \uparrow $ .

  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $(g,h)$ of $\mathcal {P}$ such that $\mathcal {H}$ is $g\oplus h$ -2-hyperimmune. In particular, there are some $i_0 < i_1 < i_2 < 4$ such that for every $i \in \{i_0, i_1, i_2\}$ and every finite $E_i $ being g-thin and h-thin for color i, we have $\Phi _{e_i}^{E_i}(n;1) \uparrow $ . There must be an $i\in \{i_0,i_1,i_2\}$ such that the set $Y=\{x:g(x)\ne i,h(x)\ne i\}$ is infinite.Footnote ⁶ Then clearly $(F_0, F_1, F_2, F_3, Y)$ is an extension of c. For every G satisfying $(F_i,Y)$ , G is g-thin for color i. Thus $\Phi _{e_i}^G(n;1)\uparrow $ . That is, d forces $\Phi _{e_i}^G(n;1)\uparrow $ , hence $\mathcal {R}_{e_0, e_1, e_2, e_3}$ .

• • Case 2: $U_n$ is found, but not $V_{n,m}$ for some $n, m \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of colorings $g:\omega \rightarrow 4$ is nonempty: for every $i < 4$ and every finite set $E_i g$ -thin for color i,

  (2.3) $$ \begin{align} \Phi_{e_i}^{E_i}(n;1) \downarrow \subseteq U_n \Rightarrow \Phi_{e_i}^{ E_i}(n, m;2) \uparrow. \end{align} $$
  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $g $ of $\mathcal {P}$ such that $\mathcal {H}$ is g-2-hyperimmune. By definition of $U_n$ (where we take $h=f$ in the definition of $U_n$ ), there are some $i_0 < i_1 < 4$ and some finite sets $E_{i_0}$ and $E_{i_1}$ such that for every $i \in \{i_0, i_1\}$ , $E_i $ is both g-thin and f-thin for color i and
  $$ \begin{align*}\Phi_{e_i}^{ E_i}(n;1) \downarrow \subseteq U_n. \end{align*} $$
  In particular, there must be some $i \in \{i_0, i_1\}$ such that the set $Y= \{x :g(x)\ne i\}$ is infinite. Consider the extension $d = (D_0, D_1, D_2,D_3, Y)$ of c defined by $D_i = F_i \cup E_i$ and $D_j = F_j$ for each $j \neq i$ . To see d forces $\Phi _{e_i}^{ G_i}(n, m;2) \uparrow $ (hence forces $\mathcal {R}_{e_0, e_1, e_2, e_3}$ ), note that for every G satisfying $(D_i,Y)$ , G is g-thin for color i. But $\Phi _{e_i}^{D_i}(n;1)\downarrow \subseteq U_n$ . Thus, by definition of g (namely (2.3)), $\Phi _{e_i}^{ G}(n, m;2) \uparrow $ .

• • Case 3: $U_n$ and $V_{n,m}$ are found for every $n,m \in \omega $ . By 2-hyperimmunity of $\mathcal {H}$ , there is some $n, m \in \omega $ such that $(U_n, V_{n,m}) \in \mathcal {H}$ . In particular, by definition of $V_{n,m}$ (where we take $g=f$ in the definition of $V_{n,m}$ ), there is some $i < 4$ and some finite set $E_i $ such that $E_i$ is f-thin for color i and

  $$ \begin{align*}\Phi_{e_i}^{ E_i }(n;1) \downarrow \subseteq U_n \wedge \Phi_{e_i}^{ E_i }(n, m;2) \downarrow\subseteq V_{n,m}. \end{align*} $$
  The condition $(D_0, D_1, D_2, D_3, X)$ defined by $D_i = F_i \cup E_i$ and $D_j = F_j$ for each $j \neq i$ is an extension of c forcing $\mathcal {R}_{e_0, e_1, e_2, e_3}$ .

This completes the proof of Lemma 2.17.⊣

Let $\mathcal {F} = \{c_0, c_1, \dots \}$ be a sufficiently generic filter for this notion of forcing, where $c_s = (F_{0,s}, F_{1,s}, F_{2,s}, F_{3,s}, X_s)$ , and let $G_i = \bigcup _s F_{i,s}$ . By definition of a condition, for every $i < 4$ , $G_i $ is f-thin for color i. By Lemma 2.16, $G_i$ are all infinite, and by Lemma 2.17, there is some $i < 4$ such that $\mathcal {H}$ is $ G_i$ -2-hyperimmune. This completes the proof of Theorem 2.15.⊣

Question 2.18. Does $\mathsf {\operatorname {\mathrm {\sf {TS}}}^2_3}$ imply $\mathsf {EM}$ ?

Proof. For notational convenience, assume $X=\omega $ and $C = \emptyset $ . Our forcing conditions are Mathias conditions $(F, Y)$ where $\mathcal {H}$ is $ Y$ -2-hyperimmune. The first lemma shows that $\mathcal {H}$ will be $ G$ -2-hyperimmune for every sufficiently generic filter. Given e, let $\mathcal {R}_e$ be the requirement:

$$ \begin{align*}\nonumber \text{If}\ \Phi^{ G}_e\ \text{is total, then it meets}\ \mathcal{H}. \end{align*} $$

Proof. This simply follows by a finite extension argument. Again for notational convenience, assume $F=\emptyset $ and $Y=\omega $ . We define a partial computable biarray as follows.

Defining $U_n$ . Given $n \in \omega $ , search computably for some finite set $U_n>n$ (if it exists) and a finite set $E $ such that

$$ \begin{align*}\Phi_e^{ E}(n;1) \downarrow = U_n. \end{align*} $$

Defining $V_{n,m}$ . Given $n, m \in \omega $ , search computably for some finite set $V_{n,m}>m$ (if it exists) and a finite set $E $ such that

$$ \begin{align*}\Phi_e^{ E}(n;1) \downarrow = U_n \wedge \Phi_e^{ E}(n, m;2) \downarrow = V_{n,m}. \end{align*} $$

We now have multiple outcomes, depending on which $U_n$ and $V_{n,m}$ is found.

• • Case 1: $U_n$ is not found for some $n \in \omega $ . Then the condition $c = (F, Y)$ already forces $\Phi _e^{ G}(n;1) \uparrow $ and therefore forces $\mathcal {R}_e$ .

• • Case 2: $U_n$ is found, but not $V_{n,m}$ for some $n, m \in \omega $ . By definition of $U_n$ , there is a finite set $E $ such that

  $$ \begin{align*}\Phi_e^{ E }(n;1) \downarrow = U_n. \end{align*} $$
  The condition $d = ( E, Y)$ is an extension of c forcing $\Phi _e^{ G}(n,m; 2) \uparrow $ .

• • Case 3: $U_n$ and $V_{n,m}$ are found for every $n,m \in \omega $ . By 2-hyperimmunity of $\mathcal {H}$ , there is some $n, m \in \omega $ such that $(U_n, V_{n,m}) \in \mathcal {H}$ . In particular, by definition of $V_{n,m}$ , there is a finite set $E $ such that

  $$ \begin{align*}\Phi_e^{ E}(n;1) \downarrow = U_n \wedge \Phi_e^{ E}(n, m;2) \downarrow = V_{n,m}. \end{align*} $$
  The condition $d = ( E, Y )$ is an extension of c forcing $\Phi ^{ G}_e$ to meet $\mathcal {H}$ , and therefore forcing $\mathcal {R}_e$ .

This completes the proof of Lemma 2.20.⊣

Lemma 2.21. For every condition $(F, Y)$ and $\sigma \in [\omega ]^{<\omega }$ such that $0< \left | \sigma \right | < n$ , there is a finite set $I \subseteq \{0, \dots , k-1\}$ with $|I| \leq d_{n-|\sigma |}$ and an extension $(F, \tilde Y)$ such that

$$ \begin{align*}(\forall \tau \in [\tilde{X}]^{n-|\sigma|})f(\sigma, \tau) \in I. \end{align*} $$

Let $\mathcal {F} = \{c_0, c_1, \dots \}$ be a sufficiently generic filter containing $(\emptyset , \omega )$ , where $c_s = (F_s, X_s)$ . The filter $\mathcal {F}$ yields a unique infinite set $G = \bigcup _s F_s$ . By Lemma 2.20, $\mathcal {H}$ is $ G$ -2-hyperimmune. By Lemma 2.21, G satisfies the property of the theorem. This completes the proof of Proposition 2.19.⊣

Proof. We prove by induction over $n \geq 1$ that $\operatorname {\mathrm {\sf {TS}}}^n_{d_{n-1}+1}$ preserves 2-hyperimmunity, and that $\operatorname {\mathrm {\sf {TS}}}^n_{d_n+1}$ strongly preserves 2-hyperimmunity. If $n = 1$ , $\operatorname {\mathrm {\sf {TS}}}^1_2$ is a computably true statement, that is, every instance has a solution computable in the instance, so $\operatorname {\mathrm {\sf {TS}}}^1_2$ preserves 2-hyperimmunity. On the other hand, $\operatorname {\mathrm {\sf {TS}}}^1_4$ strongly preserves 2-hyperimmunity follow from Theorem 2.15. If $n> 1$ , then by the induction hypothesis, $\operatorname {\mathrm {\sf {TS}}}^{n-1}_{d_{n-1}+1}$ strongly preserves 2-hyperimmunity, so by Lemma 2.14, $\operatorname {\mathrm {\sf {TS}}}^n_{d_{n-1}+1}$ preserves 2-hyperimmunity. Assuming by the induction hypothesis that $\operatorname {\mathrm {\sf {TS}}}^s_{d_s+1}$ strongly preserves 2-hyperimmunity for every $0 < s < n$ , and that $\operatorname {\mathrm {\sf {TS}}}^n_{d_{n-1}+1}$ preserves 2-hyperimmunity, by Theorem 2.26, $\operatorname {\mathrm {\sf {TS}}}^n_{d_n+1}$ strongly preserves 2-hyperimmunity.⊣

Proof. For notational convenience, assume $C=\emptyset $ . Apply Proposition 2.19 to get an infinite set $X_0\subseteq X$ so that $\mathcal {H}$ is $X_0 $ -2-hyperimmune and for every $\sigma \in [\omega ]^{<\omega }$ with $0<|\sigma |<n$ , there is an $I_\sigma $ such that $|I_\sigma | \leq d_{n-|\sigma |}$ and

$$ \begin{align*}(\exists b)(\forall \tau \in [X_0 \cap (b, +\infty)]^{n-|\sigma|}) f(\sigma, \tau) \in I_\sigma. \end{align*} $$

For each $0<s<n$ and $\sigma \in [\omega ]^s$ , let $F_s(\sigma ) = I_\sigma $ . Since $\operatorname {\mathrm {\sf {TS}}}^s_{d_s+1}$ strongly preserves 2-hyperimmunity, for each $0<s<n$ , there is an infinite set $Y\subseteq X_0$ such that $\mathcal {H}$ is $Y $ -2-hyperimmune and such that $|F_s[Y]^s|\leq d_s$ for all $0<s<n$ . Let $\mathcal {I}_s = F_s[Y]^s$ for each $0<s<n$ , and let $I = \bigcup _{J\in \mathcal {I}_s, 0 < s < n} J$ . Then

$$ \begin{align*}|I| \leq \sum_{0 < s < n} d_s d_{n-s}. \end{align*} $$

We now check that the property is satisfied. Fix an $0<s<n$ , a $\sigma \in [Y]^s$ and let $b\in \omega $ be sufficiently large. Because $Y \subseteq X_0$ ,

$$ \begin{align*}(\forall \tau \in [Y \cap (b,+\infty)]^{n-s}) f(\sigma,\tau) \in I_\sigma. \end{align*} $$

So $F_s(\sigma ) = I_\sigma $ , but $\sigma \in [Y]^s$ , hence $I_\sigma \in \mathcal {I}_s$ . It follows that

$$ \begin{align*}(\forall \tau \in [Y \cap (b,+\infty)]^{n-s}) f(\sigma,\tau) \in I. \end{align*} $$

This completes the proof.⊣

Proof. Again, for notational convenience, assume $C=\emptyset $ . Let $E=\cup _{F\in \mathcal {F}_i,i<p}F$ . For every $s<n$ , every $\sigma \in [E]^s$ , let coloring $f_\sigma :[\omega ]^{n-s}\rightarrow d_n+1$ be defined as $f_\sigma (\tau ) = f(\sigma ,\tau )$ . By Lemma 2.14, $\operatorname {\mathrm {\sf {TS}}}^s_{d_{s-1}+1}$ admits preservation of 2-hyperimmunity for $0\leq s\leq n$ (set $d_{-1} = 1$ ), so there is an infinite set $Y\subseteq X$ with $\mathcal {H}$ being $Y $ -2-hyperimmune such that for every $0\leq s<n$ , every $\sigma \in [E]^s$ , there is a $I_\sigma $ with $|I_\sigma |\leq d_{n -s-1}$ such that

$$ \begin{align*}f_\sigma[Y]^{n-s}\subseteq I_\sigma.\end{align*} $$

For every $0\leq s<n$ and $j< d_{n-s-1}$ , let $f_{s,j}$ be the coloring on $[E]^s$ such that $f_{s,j}(\sigma ) $ is the jth element of $I_\sigma $ .

By n- $\operatorname {\mathrm {\sf {TS}}}$ -sufficient of $(\mathcal {F}_i:i<p)$ , there is a $i<p$ , an $F\in \mathcal {F}_i$ such that F is $f_{s,j}$ -thin for color i for all $0\leq s<n$ and $j<d_{n-s-1}$ . In particular, $i\notin I_\emptyset $ since F is $f_{0,j}$ -thin for color i (and $f_{0,j}\equiv $ the jth element of $I_\emptyset $ ). This means Y is f-thin for color i.

We show that $F\cup Y$ is f-thin for color i. To see this, let $\sigma \in [F]^{<\omega },\tau \in [Y]^{<\omega }$ with $|\sigma \cup \tau | = n$ . When $|\sigma |=n$ or $|\tau | = n$ , $ f(\sigma ,\tau )\ne i$ follows from f-thin for color i of F and Y respectively. When $|\sigma |=s$ with $0<s<n$ , since F is $f_{s,j}$ -thin for color i for all $j<d_{n-s-1}$ , we have $f_{s,j}(\sigma )\ne i$ for all $j<d_{n-s-1}$ . This means $i\notin I_\sigma $ . Thus $f(\sigma ,\tau )\ne i$ since $f(\sigma ,\tau )\in I_\sigma $ (by choice of Y).⊣

Proof. Fix a coloring $f : [\omega ]^n \to d_n+1$ , and a bifamily $\mathcal {H}$ which is 2-hyperimmune. Let $q = \sum _{0 < s < n} d_s d_{n-s}$ . By Lemma 2.23, we assume that there exists a finite set $I_f$ of cardinality q such that for every $0<s<n$ ,

(2.4) $$ \begin{align} (\forall \sigma \in [\omega]^s)(\exists b) (\forall \tau \in [ \omega\cap (b,+\infty)]^{n-s}) f(\sigma, \tau) \in I_f. \end{align} $$

Let $p = 1+2d_{n-1}+\sum _{0\leq s<n}d_{s-1}d_{n-s-1}$ , so $d_n= p+q-1$ . By renaming the colors of f, we can assume without loss of generality that $I_f = \{p, p+1, \dots , d_n\}$ . We will construct simultaneously p infinite sets $G_0, \dots , G_{p -1}$ such that $\mathcal {H}$ is $ G_i$ -2-hyperimmune for some $i < p$ . We furthermore ensure that for each $i < p$ , $G_i$ is f-thin for color i. We construct our sets $G_0, \dots , G_{p-1}$ by a Mathias forcing whose conditions are tuples $(F_0, \dots , F_{p-1}, X)$ , where $(F_i, X)$ is a Mathias condition for each $i < p$ and the following properties hold:

1. (a) $(\forall \sigma \in [F_i]^s) (\forall \tau \in [F_i \cup X]^{n-s}) f(\sigma , \tau ) \geq p$ for every $0<s<n$ .

2. (b) $F_i$ is f-thin for color i for every $i < p$ .

3. (c) $\mathcal {H}$ is $ X$ -2-hyperimmune.

A precondition is a tuple of Mathias conditions satisfying (b) and (c). A precondition $d = (E_0, \dots , E_{p-1}, Y)$ extends a precondition $c = (F_0, \dots , F_{p-1}, X)$ (written $d \leq c$ ) if $(E_i, Y)$ Mathias extends $(F_i, X)$ for each $i < p$ . Obviously, $(\emptyset , \dots , \emptyset , \omega )$ is a condition. Therefore, the partial order is non-empty. We note the following simple properties of conditions.

The next lemma states that every sufficiently generic filter yields infinite sets $G_0, \dots , G_{p-1}$ .

A p-tuple of sets $G_0, \dots , G_{p-1}$ satisfies a condition $c = (F_0, \dots , F_{p-1}, X)$ if $G_i$ satisfies the Mathias condition $(F_i, X)$ . A condition c forces a formula $\varphi (G_0, \dots , G_{p-1})$ if the formula holds for every p-tuple of sets $G_0, \dots , G_{p-1}$ satisfying c. For every $e_0, \dots , e_{p-1} \in \omega $ , we want to satisfy the following requirement

$$ \begin{align*}\mathcal{R}_{e_0, \dots, e_{p-1}} : \mathcal{R}_{e_0} \vee \dots \vee \mathcal{R}_{e_{p-1}}, \end{align*} $$

where $\mathcal {R}_{e_i}$ is the requirement

$$ \begin{align*} \text{If}\ \Phi^{ G_i}_{e_i}\ \text{is a total, then}\ \Phi^{ G_i}_{e_i}\ \text{meets}\ \mathcal{H}. \end{align*} $$

Proof. Fix $c = (F_0, \dots , F_{p-1}, X)$ . By Lemma 2.27, for notational convenience, we assume $F_i=\emptyset $ and $X=\omega $ Footnote ⁸ . We define a partial computable biarray as follows.

Defining $U_n$ . Given $r \in \omega $ , search computably for some finite set $U_r>r$ (if it exists) such that for every pair of colorings $g, h : [\omega ]^n \to d_n+1$ , there is a n- $\operatorname {\mathrm {\sf {TS}}}$ -sufficient p-tuple $(\mathcal {E}_i:i<p) $ of finite collections of finite sets with $\mathcal {E}_i$ being g-thin, h-thin for color i such that for every $i<p$ , every $E\in \mathcal {E}_i$ , we have

$$ \begin{align*}\Phi_{e_i}^{ E }(r;1) \downarrow \subseteq U_r.\\[-15pt] \end{align*} $$

Defining $V_{r,m}$ . Given $r, m \in \omega $ , search computably for some finite set $V_{r,m}>m$ (if it exists) such that for every coloring $g : [\omega ]^n \to d_n+1$ , there is some $i < p$ and some $E_i $ g-thin for color i such that

$$ \begin{align*}\Phi_{e_i}^{ E_i }(r;1) \downarrow \subseteq U_r \wedge \Phi_{e_i}^{E_i }(r, m;2) \downarrow \subseteq V_{r,m}.\\[-15pt] \end{align*} $$

We now have multiple outcomes, depending on which $U_r$ and $V_{r,m}$ is found.

• • Case 1: $U_r$ is not found for some $r \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of pairs of colorings $g, h : [\omega ]^n \to d_n+1$ is nonempty: there is no n- $\operatorname {\mathrm {\sf {TS}}}$ -sufficient $(\mathcal {E}_i:i<p)$ finite collections of finite sets such that $\mathcal {E}_i$ is both g-thin, h-thin for color i and for every $i<p,E\in \mathcal {E}_i$ , we have $ \Phi _{e_i}^{ E}(r;1) \downarrow. $

  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $g, h $ of $\mathcal {P}$ such that $\mathcal {H}$ is $g \oplus h $ -2-hyperimmune. Unfolding the definition of n- $\operatorname {\mathrm {\sf {TS}}}$ -sufficient and using compactness, the following $\Pi _1^{0,g\oplus h}$ class $\mathcal {Q}$ of sequence $(f_{s,j}:[\omega ]^s\rightarrow d_n+1)_{0\leq s<n,j<d_{n-s-1}}$ of colorings is nonempty: for every $i<p$ , every finite set E which is both g-thin, h-thin for color i and is $f_{s,j}$ -thin for color i for all $0\leq s<n,j<d_{n-s-1}$ , we have $ \Phi _{e_i}^{ E}(r;1) \uparrow. $

  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $(f_{s,j}:0\leq s<n,j<d_{n-s-1})$ of $\mathcal {Q}$ such that $\mathcal {H}$ is $g\oplus h\oplus _{0\leq s<n,j<d_{n-s-1}}f_{s,j}$ -2-hyperimmune. Since $\operatorname {\mathrm {\sf {TS}}}^s_{d_{s-1}+1}$ preserves 2-hyperimmunity for all $0\leq s\leq n$ , there is an infinite set Y such that $|f_{s,j}[Y]^s|\leq d_{s-1}$ for all $0\leq s<n,j<d_{n-s-1}$ , $|g[Y]^s|,|h[Y]^s|\leq d_{n-1}$ and $\mathcal {H}$ is Y-2-hyperimmune. Since $p> 2d_{n-1}+\sum _{0\leq s<n}d_{s-1}d_{n-s-1}$ , there is an $i<p$ such that Y is $f_{s,j}$ -thin for color i for all $0\leq s<n,j<d_{n-s-1}$ and both g-thin, h-thin for color i.

  Clearly $d = (F_0, \dots , F_{p-1}, Y)$ is an extension of c Footnote ⁹ . We prove that d forces $\mathcal {R}_{e_0, \dots , e_{p-1}}$ . This is because if $G_i$ satisfies $(F_i,Y)$ , then $G_i$ is both g-thin and h-thin for color i and $f_{s,j}$ -thin for color i for all $0\leq s<n,j<d_{n-s-1}$ . Thus, by definition of $g,h,(f_{s,j}:0\leq s<n,j<d_{n-s-1}) $ , we have $\Phi _{e_i}^{ G_i}(r;1) \uparrow $ .

• • Case 2: $U_r$ is found, but not $V_{r,m}$ for some $r, m \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of colorings $g : [\omega ]^n \to d_n+1$ is nonempty: for every $i < p$ and every $E_i g$ -thin for color i,

  (2.5) $$ \begin{align} \Phi_{e_i}^{ E_i }(r;1) \downarrow \subseteq U_r \Rightarrow \Phi_{e_i}^{ E_i }(r, m;2) \uparrow. \end{align} $$
  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $g $ of $\mathcal {P}$ such that $\mathcal {H}$ is $g $ -2-hyperimmune. By definition of $U_r$ (where we take $h = f$ ), there is a n- $\operatorname {\mathrm {\sf {TS}}}$ -sufficient p-tuple $(\mathcal {E}_i:i<p)$ of finite collections of finite sets such that $\mathcal {E}_i$ is both g-thin and f-thin for color i and for every $i<p$ , every $ E\in \mathcal {E}_i$ , we have
  $$ \begin{align*}\Phi_{e_i}^{ E}(r;1) \downarrow \subseteq U_r. \\[-20pt]\nonumber \end{align*} $$
  By Lemma 2.25, there is an $i<p$ , $E\in \mathcal {E}_i$ and an infinite set Y such that $E\cup Y$ is g-thin for color i and $\mathcal {H}$ is Y-2-hyperimmune. Consider the precondition $(F_0,\dots ,F_{i-1},F_i\cup E,F_{i+1},\dots F_{p-1},Y)$ .

  It remains to show that d forces $\Phi _{e_i}^{G_i}(n,m;2)\uparrow $ . This is because if $G_i$ satisfies $(E, Y)$ , then $G_i$ is g-thin for color i. But $\Phi _{e_i}^{ E}(r;1) \downarrow \subseteq U_r$ . Thus, by definition of g (namely (2.5)), $\Phi _{e_i}^{G_i}(r,m;2) \uparrow $ .

• • Case 3: $U_r$ and $V_{r,m}$ are found for every $r,m \in \omega $ . By 2-hyperimmunity of $\mathcal {H}$ , there is some $r, m \in \omega $ such that $(U_r, V_{r,m}) \in \mathcal {H}$ . In particular, by definition of $V_{n,m}$ (where we take $g=f$ ), there is some $i < p$ and some $E_i f$ -thin for color i such that

  $$ \begin{align*}\Phi_{e_i}^{ E_i }(r;1) \downarrow \subseteq U_r \wedge \Phi_{e_i}^{E_i }(r, m;2) \downarrow \subseteq V_{r,m}. \end{align*} $$

  Since $i\notin f[E_i]^n$ , we have $d = (F_0, \dots , F_{i-1}, F_i \cup E_i, F_{i+1}, \dots , F_{p-1}, X)$ is an extension of c. Clearly d forces $\mathcal {R}_{e_0, \dots , e_{p-1}}$ .

This completes the proof of Lemma 2.29.⊣

Let $\mathcal {F} = \{c_0, c_1, \dots \}$ be a sufficiently generic filter for this notion of forcing, where $c_s = (F_{0,s}, \dots , F_{p-1,s}, X_s)$ , and let $G_i = \bigcup _s F_{i,s}$ for every $i < p$ . By property (b) of a condition, for every $i < p$ , $G_i$ is f-thin for color i. By Lemma 2.28, $G_0, \dots , G_{p-1}$ are all infinite, and by Lemma 2.29, there is some $i < p$ such that $\mathcal {H}$ is $ G_i$ -2-hyperimmune. This completes the proof of Theorem 2.26.⊣

Proof. Let $\mathcal {H}$ be a 2-hyperimmune family, and $f : [\omega ]^{n+1} \to \omega $ be a computable instance of $\operatorname {\mathrm {\sf {FS}}}^{n+1}$ . Let $\vec {R} = \langle R_{\sigma ,i} : \sigma \in [\omega ]^n, i \in \omega \rangle $ be the computable family of sets defined for every $\sigma \in [\omega ]^n$ and $i \in \omega $ by

$$ \begin{align*}R_{\sigma,i} = \{ x \in \omega : f(\sigma,x) = i \}. \end{align*} $$

Since $\operatorname {\mathrm {\sf {COH}}}$ preserves 2-hyperimmunity (Corollary 2.9), there is an $\vec {R}$ -cohesive set G Footnote ¹⁰ such that $\mathcal {H}$ is $ G$ -2-hyperimmune. Let $g : [\omega ]^n \to \omega $ be the instance of $\operatorname {\mathrm {\sf {FS}}}^n$ defined for every $\sigma \in [\omega ]^n$ by

$$ \begin{align*}g(\sigma) = \left\{\begin{array}{@{}ll} \lim_{x \in G} f(\sigma, x), & \mbox{if it exists, }\\ 0, & \mbox{otherwise.} \end{array}\right. \end{align*} $$

By strong preservation of $\operatorname {\mathrm {\sf {FS}}}^n$ , there is an infinite g-free set $H\subseteq G$ such that $\mathcal {H}$ is $ G \oplus H$ -2-hyperimmune. By thinning out the set H, we obtain an infinite $G \oplus H$ -computable f-free set $\tilde {H}\subseteq H$ . In particular, $\mathcal {H}$ is $\tilde {H}$ -2-hyperimmune.⊣

Proof. By Proposition 2.19 and since $\operatorname {\mathrm {\sf {TS}}}^s_{d_s+1}$ strongly preserves 2-hyper immunity for all $s\in \omega $ (Theorem 2.22), there exists a set $X_0\subseteq X $ with $\mathcal {H}$ being $ X_0$ -2-hyperimmune such that for all $\sigma \in [\omega ]^{<\omega }$ with $|\sigma |<n$ , there exists $I_\sigma $ with $|I_\sigma |\leq d_{n-|\sigma |}$ such that for every $x\notin I_\sigma $ ,

$$ \begin{align*}(\exists b)(\forall \tau\in [X_0\cap (b,\infty)]^{n-|\sigma|}) f(\sigma,\tau)\ne x. \end{align*} $$

For each $s < n$ and $i < d_{n-s}$ , let $f_{s,i} : [\omega ]^s \to \omega $ be the coloring such that $f_{s,i}(\sigma )$ is the ith element of $I_\sigma $ . By strong preservation of $\operatorname {\mathrm {\sf {FS}}}^s$ for each $0\leq s<n$ , there is an infinite set $Y\subseteq X_0$ such that Y is $f_{s,i}$ -free for all $0\leq s<n,i<d_{n-s}$ and $\mathcal {H}$ is Y-2-hyperimmune.

We prove that Y is the desired set. Fix $s < n$ , $\sigma \in [Y]^s$ and $x \in Y \smallsetminus \sigma $ . If $(\forall b)(\exists \tau \in [Y \cap (b, +\infty )]^{n - s})f(\sigma , \tau ) = x$ , then by choice of $X_0$ (and $Y\subseteq X_0$ ), there exists an $i < d_{n - s}$ such that $f_{s, i}(\sigma ) = x$ , contradicting $f_{s,i}$ -freeness of Y. So $(\exists b)(\forall \tau \in [Y \cap (b, +\infty )]^{n - s})f(\sigma , \tau ) \neq x$ .⊣

Proof. Fix some 2-hyperimmune bifamily $\mathcal {H}$ , and a left trapped coloring $f : \omega \to \omega $ . By Lemma 2.34, we assume

(2.6) $$ \begin{align} (\forall x \in\omega) (\exists b)(\forall y \in (b, +\infty))f(y) \neq x. \end{align} $$

We will construct an infinite f-free set G such that $\mathcal {H}$ is $G $ -2-hyperimmune by forcing. Our forcing conditions are Mathias conditions $(F, X)$ such that

1. (a) $\mathcal {H}$ is $X $ -2-hyperimmune.

2. (b) $(\forall x \in F \cup X) f(x) \not \in F \smallsetminus \{x\}$ .

A Mathias condition $(F,X)$ is a precondition if it satisfies (a) and F is f-free. Clearly $(\emptyset , \omega )$ is a condition. It’s easy to see that:

For every $e \in \omega $ , we want to satisfy the requirement

$$ \begin{align*} \mathcal{R}_e: \text{If}\ \Phi^{ G}_e\ \text{is total, then}\ \Phi^{ G}_e\ \text{meets}\ \mathcal{H}. \end{align*} $$

Proof. Fix a condition $c = (F, X)$ . By Lemma 2.36, for notational convenience, assume $F=\emptyset , X=\omega $ . We define a partial computable biarray as follows.

Defining $U_n$ . Given $n \in \omega $ , search computably for some finite set $U_n>n$ (if it exists) such that for every pair of left trapped colorings $g, h : \omega \to \omega $ , there is a pair of disjoint finite sets $E_0, E_1 $ which are both g-free and h-free such that for each $i < 2$ ,

$$ \begin{align*}\Phi_e^{ E_i }(n;1) \downarrow \subseteq U_n. \end{align*} $$

Defining $V_{n,m}$ . Given $n, m \in \omega $ , search computably for some finite set $V_{n,m}>m$ (if it exists) such that for every left trapped coloring $g : \omega \to \omega $ , there is some g-free finite set E such that

$$ \begin{align*}\Phi_e^{ E}(n;1) \downarrow \subseteq U_n \wedge \Phi_e^{ E}(n, m;2) \downarrow \subseteq V_{n,m}. \end{align*} $$

We now have multiple outcomes, depending on which $U_n$ and $V_{n,m}$ is found.

• • Case 1: $U_n$ is not found for some $n \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of pairs of left trapped colorings $g, h : \omega \to \omega $ is nonempty: for every pair of pairwise disjoint finite sets $E_0, E_1$ which are both g-free and h-free, there is some $i < 2$ such that $\Phi _e^{ E_i}(n;1) \uparrow $ .

  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member $g, h$ of $\mathcal {P}$ such that $\mathcal {H}$ is $g \oplus h $ -2-hyperimmune. There is an infinite $g\oplus h$ -computable set Y which is both g-free and h-free. Let $E_0 $ (if it exists) be g-free, h-free and $\Phi _e^{E_0}(n;1) \downarrow $ ; let $b = \max E_0$ (or $b=0$ if $E_0$ does not exist). Clearly condition $d = (F, Y \smallsetminus [0,b])$ is an extension of c. For every G satisfying d, G is both g-free and h-free, so $\Phi _e^G(n;1)\uparrow $ . Thus d forces $\mathcal {R}_e$ .

• • Case 2: $U_n$ is found, but not $V_{n,m}$ for some $n, m \in \omega $ . By compactness, the following $\Pi ^{0}_1$ class $\mathcal {P}$ of left trapped colorings $g : \omega \to \omega $ is nonempty: for every g-free set E,

  (2.7) $$ \begin{align} \Phi_e^{ E}(n;1) \downarrow \subseteq U_n \Rightarrow \Phi_e^{ E}(n, m;2) \uparrow. \end{align} $$
  As $\operatorname {\mathrm {\sf {WKL}}}$ preserves 2-hyperimmunity (Corollary 2.7), there is a member g of $\mathcal {P}$ such that $\mathcal {H}$ is g-2-hyperimmune. There is an infinite g-computable g-free set Y. By definition of $U_n$ (where we take $h = f$ ), there is a pair of disjoint finite sets $E_0, E_1 $ which are both g-free and f-free, and such that for every $i < 2$ ,
  $$ \begin{align*}\Phi_e^{E_i}(n;1) \downarrow \subseteq U_n. \end{align*} $$
  Consider the 2-partition $A_0\sqcup A_1$ of $\omega $ defined by $x\in A_i$ if $g(x)\in E_i$ and $x\in A_0$ if $g(x)\notin \cup _{i<2}E_i$ . Since $\operatorname {\mathrm {\sf {TS}}}^1_2$ is computably true, hence preserves 2-hyperimmunity, there is an $i < 2$ and an infinite set $E_i<\tilde Y \subseteq Y$ such that $\mathcal {H}$ is $\tilde Y $ -2-hyperimmune and $g(\tilde Y)\cap E_i=\emptyset $ . We claim that $E_i \cup \tilde Y$ is g-free. Indeed, $E_i$ and $\tilde Y$ are both g-free; since g is left trapped, $g(E_i) \cap \tilde Y = \emptyset $ ; and by choice of $\tilde Y$ , $g(\tilde Y) \cap E_i = \emptyset $ .

  By f-free of $E_i$ , $d=(E_i, \tilde Y )$ is a precondition extending c. We prove that the d forces $\Phi _e^{ G}(n,m;2) \uparrow $ . Because $\Phi _e^{E_i}(n;1)\downarrow \subseteq U_n$ and $E_i \cup \tilde Y$ is g-free (so every G satisfying $(E_i,\tilde Y)$ is g-free), by definition of g (namely (2.7)), d forces $\Phi _e^{ G}(n, m;2) \uparrow $ .

• • Case 3: $U_n$ and $V_{n,m}$ are found for every $n,m \in \omega $ . By 2-hyperimmunity of $\mathcal {H}$ , there is some $n, m \in \omega $ such that $(U_n, V_{n,m}) \in \mathcal {H}$ . In particular, by definition of $V_{n,m}$ (where we take $g = f$ ), there is some f-free finite set $E $ such that

  $$ \begin{align*}\Phi_e^{E}(n;1) \downarrow \subseteq U_n \wedge \Phi_e^{E}(n, m;2) \downarrow \subseteq V_{n,m}. \end{align*} $$

  Clearly $(E, X)$ is a precondition extending c and forcing $\mathcal {R}_e$ .

This completes the proof of Lemma 2.38.⊣

Let $\mathcal {F} = \{c_0, c_1, \dots \}$ be a sufficiently generic filter for this notion of forcing, where $c_s = (F_s, X_s)$ , and let $G = \bigcup _s F_s$ . By property (b) of a condition, G is f-free. By Lemma 2.37, G is infinite, and by Lemma 2.38, $\mathcal {H}$ is $ G$ -2-hyperimmune. This completes the proof of Theorem 2.35.⊣

Proof. We prove by induction over $n \geq 1$ that $\operatorname {\mathrm {\sf {FS}}}^n$ preserves and strongly preserves 2-hyperimmunity. If $n = 1$ , $\operatorname {\mathrm {\sf {FS}}}^1$ is a computably true statement, that is, every instance has a solution computable in the instance, so $\operatorname {\mathrm {\sf {FS}}}^1$ preserves 2-hyperimmunity. If $n> 1$ , then by the induction hypothesis, $\operatorname {\mathrm {\sf {FS}}}^{n-1}$ strongly preserves 2-hyperimmunity, so by Lemma 2.31, $\operatorname {\mathrm {\sf {FS}}}^n$ preserves 2-hyperimmunity. Assuming by the induction hypothesis that $\operatorname {\mathrm {\sf {FS}}}^t$ strongly preserves 2-hyperimmunity for every $t < n$ , and that $\operatorname {\mathrm {\sf {FS}}}^n$ preserves 2-hyperimmunity, then by Theorem 2.43, $\operatorname {\mathrm {\sf {FS}}}^n$ for left trapped functions strongly preserves 2-hyperimmunity. By Lemma 2.33, if $\operatorname {\mathrm {\sf {FS}}}^n$ for left trapped functions strongly preserves 2-hyperimmunity, so does $\operatorname {\mathrm {\sf {FS}}}^n$ . This completes the proof.⊣