Trees of strategies

The previous lesson reduced the minimal pair theorem to requirements $\mathcal N_e$, $\mathcal R_e$ and $\mathcal S_e$, and showed that the strategy for $\mathcal R_d$ below $\mathcal N_e$ depends on the outcome of $\mathcal N_e$, which the construction cannot compute. The tree method assigns to each requirement one strategy for each possible guess about the outcomes of the strategies above it. At every stage, the construction computes a current guess, a finite path through the tree, and only runs the strategies along it. The true path, the leftmost path visited infinitely often, consists of the strategies whose guesses are correct; the verification shows that they meet their requirements.

2.1 The tree and the priority order

Let $\Lambda = \{ \infty, \mathrm f \}$, ordered by $\infty < \mathrm f$. We list the requirements as $\mathcal N_0, \mathcal R_0, \mathcal S_0, \mathcal N_1, \mathcal R_1, \mathcal S_1, \dots$, so that the requirement of index $3e$ is $\mathcal N_e$, that of index $3e + 1$ is $\mathcal R_e$, and that of index $3e + 2$ is $\mathcal S_e$.

Definition 2.1.#

1. The tree of strategies is the set $\mathbb T$ of finite strings $\alpha \in \Lambda^{<\nat}$ such that $\alpha(n) = \mathrm f$ whenever $n$ is not a multiple of $3$. A string $\alpha \in \mathbb T$ is a node, and the node $\alpha$ works for the requirement of index $|\alpha|$: it is an $\mathcal N_e$-node if $|\alpha| = 3e$, and so on.
2. For nodes $\alpha$ and $\beta$, $\alpha$ is to the left of $\beta$, written $\alpha <_L \beta$, if there is $n$ with $\alpha \uh n = \beta \uh n$, $\alpha(n) = \infty$ and $\beta(n) = \mathrm f$.
3. $\alpha$ has higher priority than $\beta$ if $\alpha \prec \beta$ or $\alpha <_L \beta$.

The $\mathcal N$-nodes have two outcomes, the other nodes only the outcome $\mathrm f$. A node $\beta$ with $\alpha^\frown \infty \preceq \beta$ guesses that the $\mathcal N$-node $\alpha$ has infinitely many expansionary stages, and a node with $\alpha^\frown \mathrm f \preceq \beta$ that it has finitely many. For any two distinct nodes, either one is a prefix of the other, or one is to the left of the other; the priority order is a linear order on $\mathbb T$. Unlike the priority orders of finite injury arguments, it gives most nodes infinitely many nodes of higher priority: a node with the value $\mathrm f$ at some $\mathcal N$-level $n$ has to its left every extension of $(\alpha \uh n)^\frown \infty$.

2.2 The construction

Each node carries some data, which initializing the node resets.

• An $\mathcal N_e$-node $\alpha$ has a record $m_\alpha$, a number or undefined. Initialization makes it undefined.
• An $\mathcal R_e$-node or $\mathcal S_e$-node $\beta$ may have a follower $x_\beta$, and may be marked satisfied. Initialization cancels the follower and the mark.

A number is fresh at a stage if it is larger than the stage and than every number mentioned so far in the construction. Initially every node is initialized, and $A_0 = B_0 = \emptyset$.

Stage $s$. We define the current path $\sigma_s \in \mathbb T$, of length at most $s$, by visiting nodes one after the other, starting with the root; when a node $\alpha$ is visited with outcome $o$, the next node to visit is $\alpha^\frown o$. A node of length $s$ is not visited, and the stage also ends when a node acts. Let $\alpha$ be the node visited.

1. If $\alpha$ is an $\mathcal N_e$-node, compute the length of agreement $l(e, s)$ of $\Phi^{A_s}_e$ and $\Phi^{B_s}_e$ (Definition 1.4). The stage $s$ is $\alpha$-expansionary if $m_\alpha$ is undefined or $l(e, s) > m_\alpha$. In that case, set $m_\alpha = l(e, s)$, and the outcome is $\infty$; otherwise the outcome is $\mathrm f$.
2. If $\alpha$ is an $\mathcal R_e$-node without a follower, it receives a fresh follower; the outcome is $\mathrm f$. If it has a follower $x$, is not marked satisfied, and $x \in W_{e,s}$, then $\alpha$ acts: $x$ is enumerated into $A$, $\alpha$ is marked satisfied, the stage ends, and $\sigma_s = \alpha^\frown \mathrm f$. Otherwise the outcome is $\mathrm f$.
3. $\mathcal S_e$-nodes are treated in the same way, with $B$ in place of $A$.

At the end of the stage, initialize every node $\beta$ with $\sigma_s <_L \beta$. Then $A_{s+1}$ and $B_{s+1}$ are $A_s$ and $B_s$ with the element enumerated at stage $s$, if any.

A node $\alpha$ is visited at stage $s$, and $s$ is an $\alpha$-stage, if $\alpha \prec \sigma_s$, strictly. At each stage, at most one number is enumerated, at the very end, after all the computations of the stage have been examined. The construction is computable, so $A$ and $B$ are c.e. Followers are fresh, so distinct followers are distinct numbers, and a follower enters $A$ or $B$ only through the action of its own node. In particular $A \cap B = \emptyset$.

The initialization rule replaces the explicit restraints of finite injury arguments. A node to the right of the current path has made a guess that the current stage refutes, at least for now: it loses its follower, and the next follower it receives is fresh, hence larger than every use of a computation examined so far.

2.3 The true path

Definition 2.2.#

The true path is the infinite sequence $P \in \Lambda^\nat$ defined by induction: $P(n)$ is the least $o \in \Lambda$ such that $(P \uh n)^\frown o$ is visited at infinitely many stages.

Lemma 2.3.#

For every $n$, the true path is defined at $n$, and the node $\alpha = P \uh n$ satisfies:

1. $\alpha$ is visited at infinitely many stages;
2. $\sigma_s <_L \alpha$ holds for only finitely many $s$; in particular $\alpha$ is initialized only finitely often;
3. if $\alpha$ is an $\mathcal R$- or $\mathcal S$-node, it acts only finitely often.

Proof of Lemma 2.3.

By induction on $n$. The root is visited at every stage $s \geq 1$, and no path is to its left.

Suppose that $\alpha = P \uh n$ satisfies items 1 and 2. The node $\alpha$ is initialized only at the end of a stage $s$ with $\sigma_s <_L \alpha$, so it is initialized finitely often. If $\alpha$ is an $\mathcal R$- or $\mathcal S$-node, then between two initializations it acts at most once, since it is then marked satisfied; this gives item 3. Let $s_0$ be a stage after which $\alpha$ never acts, nor is initialized, nor satisfies $\sigma_s <_L \alpha$.

Case 1: $\alpha$ is an $\mathcal R$- or $\mathcal S$-node. At every $\alpha$-stage $s > \max(s_0, n + 1)$, $\alpha$ does not act and $\alpha^\frown \mathrm f$ has length less than $s$, so $\alpha^\frown \mathrm f$ is visited. So $P(n) = \mathrm f$, and $\alpha^\frown \mathrm f$ satisfies item 1. A node to the left of $\alpha^\frown \mathrm f$ is to the left of $\alpha$, since no node has the value $\infty$ at position $n$; this gives item 2.

Case 2: $\alpha$ is an $\mathcal N$-node. At every $\alpha$-stage $s > n + 1$, $\alpha^\frown o$ is visited, where $o$ is the outcome of $\alpha$ at $s$. If the outcome $\infty$ occurs at infinitely many stages, $P(n) = \infty$, and a path to the left of $\alpha^\frown \infty$ is to the left of $\alpha$. Otherwise, $P(n) = \mathrm f$, the node $\alpha^\frown \mathrm f$ is visited at all $\alpha$-stages after the last $\alpha$-expansionary stage, and a path to the left of $\alpha^\frown \mathrm f$ is either to the left of $\alpha$ or extends $\alpha^\frown \infty$; both happen only finitely often.

Item 2 is the reason why the priority order puts every node to the left of $\alpha$ above it. A node $\beta$ to the right of the true path may be initialized infinitely often, and act infinitely often, each time with a new follower: if $\beta$ extends $\alpha^\frown \mathrm f$ while the true outcome of $\alpha$ is $\infty$, $\beta$ is initialized at every $\alpha$-expansionary stage. This is the infinite injury. It is harmless, because the requirement of $\beta$ is met by the node of the same level on the true path, and because the actions of $\beta$ only enumerate fresh numbers.

2.4 Verification

Lemma 2.4.#

Every requirement $\mathcal R_e$ and $\mathcal S_e$ is met.

Proof of Lemma 2.4.

Let $\beta = P \uh (3e + 1)$, the $\mathcal R_e$-node on the true path. By Lemma 2.3, $\beta$ is initialized finitely often and visited infinitely often. At its first visit after its last initialization, it receives a follower $x$, which it keeps forever. If $x \in W_e$, at the first $\beta$-stage $s$ with $x \in W_{e,s}$, $\beta$ is not yet marked satisfied, so it acts, and $x \in A \cap W_e$. If $x \notin W_e$, then $\beta$ never enumerates $x$, no other node does, and $x \in \overline A \setminus W_e$. In both cases $W_e \neq \overline A$. The argument for $\mathcal S_e$ is the same.

The main lemma checks condition 2 of Lemma 1.6 for the $\mathcal N$-nodes of the true path.

Lemma 2.5.#

Let $\alpha = P \uh 3e$, and let $s^*$ be a stage larger than $|\alpha| + 1$ such that, for $s \geq s^*$, $\sigma_s \not<_L \alpha$ and no proper prefix of $\alpha$ acts at stage $s$. If $s^* \leq s < t$ are consecutive $\alpha$-expansionary stages, then $A_t \uh s = A_s \uh s$ or $B_t \uh s = B_s \uh s$.

Proof of Lemma 2.5.

Let $u$ be a stage with $s \leq u < t$ at which some node $\gamma$ acts, so that $\sigma_u = \gamma^\frown \mathrm f$. We consider the position of $\gamma$ relative to $\alpha$.

• $\gamma$ is a proper prefix of $\alpha$, or $\gamma <_L \alpha$: excluded by the choice of $s^*$, since then $\sigma_u <_L \alpha$ in the second case.
• $\gamma = \alpha$: impossible, since $\mathcal N$-nodes do not act.
• $\alpha^\frown \infty \preceq \gamma$: then $\alpha$ is visited at $u$ with outcome $\infty$, so $u$ is $\alpha$-expansionary, and $u = s$.
• $\alpha^\frown \mathrm f \preceq \gamma$ or $\alpha <_L \gamma$: since $s$ is $\alpha$-expansionary, $\alpha^\frown \infty \preceq \sigma_s$, so $\sigma_s <_L \gamma$, and $\gamma$ is initialized at the end of stage $s$. In particular $u > s$, and the follower enumerated by $\gamma$ was received after stage $s$; it is fresh, hence larger than $s$.

So the only number below $s$ that may be enumerated during the stages $s, \dots, t - 1$ is the follower of the node acting at stage $s$, if any. It enters $A$ or $B$, not both, and the other side does not change below $s$.

Lemma 2.6.#

Every requirement $\mathcal N_e$ is met.

Proof of Lemma 2.6.

Let $\alpha = P \uh 3e$. By Lemma 2.3, the prefixes of $\alpha$ act finitely often, and $\sigma_s <_L \alpha$ for finitely many $s$; so a stage $s^*$ as in Lemma 2.5 exists, and $\alpha$ is not initialized after $s^*$. Suppose that $\Phi^A_e = \Phi^B_e$ is total. By Proposition 1.5, applied to the infinite set of $\alpha$-stages after the last initialization of $\alpha$, there are infinitely many $\alpha$-expansionary stages. List those larger than $s^*$ as $s_0 < s_1 < \cdots$. The sequence is computable: run the construction and list the $\alpha$-expansionary stages after $s^*$. Condition 1 of Lemma 1.6 holds since the record increases, and condition 2 by Lemma 2.5. By Corollary 1.7, $\Phi^A_e$ is computable.

Proof of Theorem 1.2.

The sets $A$ and $B$ are c.e. By Lemma 2.4, they are not computable, and $A$ is non-empty: for an index $e$ with $W_e = \nat$, the requirement $\mathcal R_e$ puts a number into $A$. Since $A \cap B = \emptyset$, we have $A \neq B$. By Lemma 2.6 and Lemma 1.3, every set computable in both $A$ and $B$ is computable.

2.5 Exercises

Exercise 2.7 ★.

Show that the true path is computable in $\emptyset''$.

Solution

Given $P \uh n$, if it is an $\mathcal N$-node, then $P(n) = \infty$ if and only if $(P \uh n)^\frown \infty$ is visited at infinitely many stages. The set of stages at which a node $\beta$ is visited is computable, uniformly in $\beta$, so it is $W_{g(\beta)}$ for a computable function $g$. Hence $\beta$ is visited at infinitely many stages if and only if $g(\beta) \in \mathrm{Inf}$, which $\emptyset''$ decides (Proposition 3.5 of “The Turing jump”). If $P \uh n$ is another node, $P(n) = \mathrm f$. By induction on $n$, $\emptyset''$ computes $P$.

Exercise 2.8 ★★.

Modify the construction so that $A$ and $B$ are, in addition, simple sets.

Solution

Put $0$ into $A$ at stage $0$, and replace $\mathcal R_e$ by the requirement “if $W_e$ is infinite, then $W_e \cap A \neq \emptyset$”. An $\mathcal R_e$-node $\beta$, visited at stage $s$, acts if $W_{e,s} \cap A_s = \emptyset$ and there is $x \in W_{e,s}$ with $x > 2e$ and $x$ larger than the last stage at which $\beta$ was initialized: it enumerates the least such $x$ into $A$, and the stage ends. Treat $\mathcal S_e$ in the same way for $B$, with numbers $x > 2e$ and $x > 0$, so that $0 \in A \setminus B$ and $A \neq B$.

A node $\gamma$ initialized at the end of stage $s$ only enumerates numbers larger than $s$ at its later actions, so Lemma 2.5 still holds, with the same proof; Lemma 2.6 and Lemma 1.3 then give the minimal pair property. If $W_e$ is infinite, the $\mathcal R_e$-node $\beta$ on the true path, after its last initialization at stage $s_0$, eventually sees an element of $W_e$ larger than $2e$ and $s_0$, and acts at the next $\beta$-stage unless $W_e \cap A \neq \emptyset$ already. Finally, once some element of $W_e$ is in $A$, no $\mathcal R_e$-node acts again, so each $e$ contributes at most one element to $A$, and that element is larger than $2e$. Hence $A \cap \{0, \dots, 2n\}$ has at most $n + 1$ elements, and $\overline A$ is infinite. The same holds for $B$.

2.6 Notes and references

The tree method was made explicit by Lachlan in the 1970s, and became the standard presentation of infinite injury arguments with Soare’s book; earlier proofs organized the same guesses implicitly, through the stages at which restraints are recomputed. Lempp’s lecture notes describe the hierarchy of priority arguments: finite injury arguments are $\mathbf 0'$-arguments, since $\emptyset'$ can follow them, the tree arguments of this course are $\mathbf 0''$-arguments, since the true path is computable in $\emptyset''$, and $\mathbf 0'''$-arguments use trees of strategies with more complex interactions.

• R. I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987, Chapters IX and XIV.
• S. Lempp, Priority arguments in computability theory, model theory, and complexity theory, lecture notes, University of Wisconsin, 2012.