On Martin’s pointed tree theorem

Abstract

We investigate the reverse mathematics strength of Martin’s pointed tree theorem ( $MPT$ ) and one of its variants, weak Martin’s pointed tree theorem ( $wMPT$ ).

Keywords

Reverse mathematics algorithmic randomness Martin’s pointed tree theorem weak Martin’s pointed tree theorem

1. Introduction

A set A of reals is cofinal if for every real x there is some $y \in A$ so that $y ⩾_{T} x$ . A pointed tree T is a perfect tree so that for every infinite path $x \in [T]$ , $T ⩽_{T} x$ . In 1968, Martin [9] proved the following theorem.

Theorem 1.1 (Martin [9]).

Assume that every game is determined. Then given any set $A \subseteq ω^{ω}$ , if A is cofinal, then there is a pointed tree $[T] \subseteq A$ .

Theorem 1.1 builds a significant connection between descriptive set theory and recursion theory. It has been a central goal in descriptive set theory to prove lower bounds on the consistency strength of some descriptive set theory theorems (see, for example, Harrington [4] or Koellner and Woodin [7]). Despite the seemingly simple form of Theorem 1.1, the proof of its consistency relative to $ZF$ requires the existence of infinitely many Woodin cardinals; which is far beyond the strength of $ZF$ . One of the reasons for the importance of Theorem 1.1 is that it was used by Slaman and Steel [18] as a critical tool in their study of Martin’s conjecture, one of the central open problems in recursion theory. We study a natural version of Martin’s theorem and a variant, $wMPT$ , before a recursion theory background.

Definition 1.2.
Martin’s pointed tree theorem, $MPT$ , states that given a tree $T \subseteq ω^{< ω}$ , if $[T]$ is cofinal, then T has a pointed subtree.
Definition 1.3.
Weak Martin’s pointed tree theorem, $wMPT$ , states that given a tree $T \subseteq ω^{< ω}$ , if $[T]$ is cofinal, then T has a perfect subtree.

In this paper, we are mainly interested in the reverse mathematical strengths of these statements.

Reverse mathematics is used to gauge the complexity of mathematical theorems by determining precisely which axioms are needed to prove a given theorem. For example, Martin and Steel [10] proved the conclusion of Theorem 1.1 under the hypothesis that there are infinitely many Woodin cardinals. A typical question in reverse mathematics would be whether this hypothesis is necessary for the proof of a given statement; and in the case of Theorem 1.1 it indeed is, as shown by Koellner and Woodin [7].

When studying reverse mathematics before a recursion theory background one often focuses on second-order arithmetical theories. In other words one focuses on the question of which theorems can be proven assuming only a certain subset of second-order arithmetical axioms. In this context, there exists a group of sets of axioms, the so-called big five (see Simpson [17]). These sets of axioms are distinguished from others in that most of the mathematical theorems whose reverse mathematical strength has been classified so far have turned out to be equivalent to one of these five. This is why most researchers in the area consider the big five systems to be of central importance for the subject, and why they have received much attention. In this paper, we use the big five to measure the strength of $MPT$ and $wMPT$ .

Based on Martin’s proof of Theorem 1.1, it seems that for a proof of $MPT$ we need $Δ_{4}^{0} - DET$ . However, using results from [5] and [12], we show that over ${ACA}_{0}$ we have that $MPT$ is equivalent to ${ATR}_{0}$ . As a consequence, the question arises whether we can prove the same equivalence over weaker axiom systems. We prove that, over ${RCA}_{0}$ , $MPT$ does not even imply ${WKL}_{0}$ . So $MPT$ can be viewed as a natural theorem incomparable with ${WKL}_{0}$ and ${ACA}_{0}$ but “joining” ${ACA}_{0}$ to ${ATR}_{0}$ . However, the question of whether the equivalence can be proven over ${WKL}_{0}$ remains open.

$wMPT$ is obviously implied by $MPT$ . It is also related to other classical results in descriptive set theory. The perfect set theorem ( $PST$ ) says that every uncountable set has a perfect subtree. In the reverse mathematics setting $PST$ corresponds to $RPST$ , the statement that every uncountable closed set has a perfect subset. A natural analogue of $wMPT$ in descriptive set theory is the statement that every cofinal set has a perfect subset ( $CPST$ ). It turns out (see Solovay [19] and Chong and Yu [2]) that $PST$ and $CPST$ have the same consistency strength. Obviously $RPST$ also implies $wMPT$ . Simpson [17] shows that, over ${ACA}_{0}$ , $RPST$ is equivalent to ${ATR}_{0}$ . However, we prove that $wMPT$ is strictly weaker than ${ATR}_{0}$ (and therefore than $RPST$ ) and incomparable with ${WKL}_{0}$ and ${ACA}_{0}$ . Hence we have two mathematical statements which have the same consistency strength but different reverse mathematics strength. Another interesting conclusion is that $wMPT$ can be viewed as a natural example of a theorem that is not equivalent to any of the big five.

We also would like to point out the interesting technique used to prove Theorem 4.2, which states that, over ${WKL}_{0}$ , $wMPT$ does not imply ${ACA}_{0}$ . It demonstrates a natural application of algorithmic randomness theory to reverse mathematics. In fact, in this article, in all proofs where genericity was used it could be replaced with randomness; we keep the genericity because it simplifies the proofs. However, the use of randomness in the proof of Theorem 4.2 seems necessary since no generic real can be hyperimmune-free.

The article is organized as follows: In Section 2 we review some background knowledge; in Section 3 we investigate $MPT$ and $wMPT$ over ${RCA}_{0}$ ; in Section 4 we investigate them over ${WKL}_{0}$ ; and in Section 5 over ${ACA}_{0}$ .
2. Preliminaries

2.1. General notations

For every real $x \in ω^{ω}$ , let x be the Turing degree of x.

If Φ is a Turing functional, then we use $Φ^{x ↾ n} [m]$ to denote the finite string computed from oracle x at stage m with use n.

If $x ⩽_{T} y$ via a total Turing functional, then we write $x ⩽_{tt} y$ and say that x is truth-table reducible to y.

We refer the reader to Lerman [8] and Odifreddi [15] for more recursion theoretical background.

Given a tree T, we use $[T]$ to denote the collection of the infinite paths through T. For a finite string σ, let $[σ]$ denote the collection of reals extending σ.

A set $D \subseteq 2^{< ω}$ is dense if for every $σ \in 2^{< ω}$ there is some $τ \in D$ so that $τ ≻ σ$ , i.e., τ is an extension of σ.

A real $g \in 2^{ω}$ is arithmetically generic, if for every arithmetical dense set $D \subseteq 2^{< ω}$ there is some n so that either

$g ↾ n \in D$ , or

$\forall σ (σ ≻ g ↾ n \to σ \notin D)$ .

A real x is hyperimmune-free if every x-recursive function is dominated by a recursive function. It is obvious that if x is hyperimmune-free and

y ⩽_{T} x

, then

y ⩽_{tt} x

. By Jockusch and Soare’s hyperimmune-free basis theorem [6], every nonempty

Π_{1}^{0}

subset of

2^{ω}

contains a hyperimmune-free real.

We say that $x ≫ y$ if there is a real $z ⩽_{T} x$ in $2^{ω}$ so that $\forall e (z (e) \neq Φ_{e}^{y} (e))$ . There is a nonempty $Π_{1}^{0}$ subset of $2^{ω}$ in which every real x has the property $x ≫ \emptyset$ . So by the hyperimmune-free basis theorem there is a hyperimmune-free real $x ≫ \emptyset$ .

A partial function $p : ω \to ω$ is recursively bounded if there is a recursive function $f : ω \to ω$ so that for every n, $p (n) ↓ \to p (n) < f (n)$ . The following result should be well known.

Proposition 2.1 (Folklore).

If $x ≫ \emptyset$ , then for every partial recursive function $Ψ : ω \to ω$ which is recursively bounded, there is a total x-recursive function g extending Ψ .

Proof.
Let a partial recursive function $Ψ : ω \to ω$ with a recursive bound f be given. Define a partial recursive function $Ξ : ω^{2} \to 2$ so that $\begin{matrix} Ξ (e, ⟨ n, m ⟩) = \{\begin{matrix} 1 & Ψ (n) ↓ = m, \\ 0 & \exists k < f (n) (k \neq m \land Ψ (n) ↓ = k), \\ ↑ & otherwise . \end{matrix} \end{matrix}$ By the $s - m - n$ -theorem, there is a recursive function h so that $\begin{matrix} Ξ (e, ⟨ n, m ⟩) = Φ_{h (⟨ n, m ⟩)} (e) . \end{matrix}$ Let $z ⩽_{T} x$ be in $2^{ω}$ so that $\forall e (z (e) \neq Φ_{e} (e))$ . Define $g (n) = m$ if m is the least number $< f (n)$ so that $z (h (⟨ n, m ⟩)) = 0$ if any; otherwise let $g (n) = 0$ . Obviously g is a total x-recursive function extending Ψ. □

Note that for every recursive tree $T \subseteq 2^{< ω}$ and real $x ≫ \emptyset$ , if $[T]$ is not empty, then there must be some $y ⩽_{T} x$ such that $y \in [T]$ .

We need the following technical lemma to build a perfect tree by projection. For $σ, τ \in ω^{n}$ we define the notation $σ \oplus τ$ as $σ (0) τ (0) σ (1) τ (1) \dots σ (n) τ (n)$ . The motivation behind this lemma and notation is that we will later work with game-theoretic trees, for games with two players making moves alternately. Lemma 2.2.
Suppose that T is a perfect tree so that for every $f_{0} \oplus g_{0}, f_{1} \oplus g_{1} \in [T]$ , if $g_{0} = g_{1}$ , then $f_{0} = f_{1}$ . Then there is a perfect tree $S_{1} ⩽_{T} T$ so that for every infinite path $g \in [S_{1}]$ , there is some f so that $f \oplus g \in [T]$ .
Proof.
Fix a tree T as in the assumption. We T-recursively build a helper tree $S_{0}$ and the desired tree $S_{1}$ stage by stage.

At stage 0, let $ε \oplus ε = ε \in S_{0}$ and $ε \in S_{1}$ .

We assume that at stage n, for every $σ \oplus τ \in S_{0}$ , there are $τ_{0} | τ_{1}$ extending τ so that there are $σ_{0}$ , $σ_{1}$ extending σ so that $σ_{0} \oplus τ_{0}, σ_{1} \oplus τ_{1} \in T$ .

We claim that the assumption holds at stage 0. Since T is perfect, there must exist two distinct paths $f_{0} \oplus g_{0}$ , $f_{1} \oplus g_{1} \in [T]$ . If we always have $g_{0} = g_{1}$ then, by the assumption on T, $f_{0}$ must be equal to $f_{1}$ , which is a contradiction to the fact that T is perfect. So fix $g_{0}$ , $g_{1}$ and some n such that $g_{0} (n) \neq g_{1} (n)$ . Write $τ_{0} = g_{0} ↾ n + 1$ , $τ_{1} = g_{1} ↾ n + 1$ , $σ_{0} = f_{0} ↾ n + 1$ and $σ_{1} = f_{1} ↾ n + 1$ .

At stage $n + 1$ , for every leaf $σ \oplus τ \in S_{0}$ , select $σ_{0} \oplus τ_{0}, σ_{1} \oplus τ_{1} \in T$ as defined above and put them into $S_{0}$ . Also put $τ_{0}$ , $τ_{1}$ into $S_{1}$ . With the same argument as above for stage 0 the assumption remains true at stage $n + 1$ .

Now it is clear that $S_{1}$ is a perfect tree. Suppose that $g \in [S_{1}]$ , then there must be $σ_{0} \oplus τ_{0} ≺ σ_{1} \oplus τ_{1} ≺ \dots$ constructed at stages $0, 1, \dots$ , respectively, so that $τ_{0} ≺ τ_{1} ≺ \dots ≺ g$ . Let $f = ⋃_{i \in ω} σ_{i}$ . Then $f \oplus g \in [T]$ . Thus $S_{1}$ is as required. □

2.2. Reverse mathematics

We refer to Simpson [17] for the background on reverse mathematics. We recall that ${RCA}_{0}$ is the most basic axiom system for the second-order arithmetical theory. The axioms in the stronger system ${WKL}_{0}$ state that every infinite binary tree has an infinite path. The even stronger system ${ACA}_{0}$ includes all arithmetical comprehension axioms, and ${ATR}_{0}$ ensures that arithmetical transfinite recursion is allowed. Together with $Π_{1}^{1} - {CA}_{0}$ , these systems form the famous big five hierarchy.

Given a theory T and a proposition φ, to show that $T ⊬ φ$ , we will use model-theoretical arguments. A model $M$ for the second-order arithmetical language has the form $(N, M, 0, 1, +, \times, <, \in)$ , which is a two-sorted model. The first sort N contains the natural numbers, and the second sort M is the family of subsets of N that exist in the model at hand. In this paper, we will always have $N = ω$ and $M \subseteq 2^{ω}$ , that is, we only focus on so-called ω-models.

2.3. Game theory

We recall the basic game theoretical notions used in this article, and refer to Moschovakis [13] for more details.

Given a set $A \subseteq ω^{ω}$ , we define an infinite game $G_{A}$ with perfect information as follows: The game has two players labelled I and II. The game is played by letting the players choose natural numbers alternately for ω-many steps. Each game generates a real $x = (n_{0}, m_{0}, \dots, n_{i}, m_{i}, \dots) \in ω^{ω}$ where $n_{i}$ and $m_{i}$ are the numbers played by I and II, respectively, at their ith move. If $x \in A$ , then I wins the game. Otherwise, II wins.

A strategy is a function $h : ω^{< ω} \to ω$ . For a set $A \subseteq ω^{ω}$ and the corresponding game $G_{A}$ , if h is I’s strategy and II plays g, then as usual $h * g$ denotes the outcome generated by h and g. If h is II’s strategy and I plays f, then $f * h$ denotes the outcome generated by h and f.

I has a winning strategy h for the game $G_{A}$ if for every $g \in ω^{ω}$ , the real $h * g \in A$ . II has a winning strategy h for the game $G_{A}$ if for every $f \in ω^{ω}$ , the real $f * h \notin A$ .

A game $G_{A}$ is determined if either I or II has a winning strategy. Given a class $Γ \subseteq P (ω^{ω})$ , $Γ - DET$ says that $G_{A}$ is determined for every $A \in Γ$ .

The following remarkable connection between game theory and recursion theory was established by Martin. Call a set A of reals Turing-invariant if for every $x \in A$ , $y \equiv_{T} x$ implies $y \in A$ .

Theorem 2.3 (Martin [9]).

Assume every set is determined. Then every set A of reals that is Turing-invariant and cofinal contains an upper cone with respect to Turing reducibility.

$Γ - TD$ says that if an $A \in Γ$ which is Turing-invariant is also cofinal, then it contains an upper cone of Turing degrees.

The connection between game theory and reverse mathematics was initiated by Blass and Steel.

Theorem 2.4 (Blass [1] and Steel [20]).

Over ${RCA}_{0}$ , ${ATR}_{0}$ implies $Π_{1}^{0} - DET$ .

2.4. Algorithmic randomness

In this article, the theory of algorithmic randomness will only serve as a tool. We refer the reader to Nies [14] and Downey and Hirschfeldt [3] for details on the topic.

Given a Turing machine M, define its Kolmogorov complexity function as $\begin{matrix} C_{M} (σ) = min {| τ | ∣ M (τ) = σ} . \end{matrix}$ The universal Turing machine U induces an optimal Kolmogorov complexity function up to a constant. That is, for every Turing machine M, there is a constant $c_{M}$ so that $\forall σ (C_{U} (σ) ⩽ C_{M} (σ) + c_{M})$ . Usually, U is fixed and the subscript omitted.

For the purposes of this article we use the following definition of randomness which, by a result of Miller and Yu [11], is equivalent to the classical definition of Martin-Löf randomness (see, e.g., Downey and Hirschfeldt [3]): A real $x \in 2^{ω}$ is random if for every recursive function $f : ω \to ω$ with $\begin{matrix} \sum_{n \in ω} 2^{- f (n)} < \infty, \end{matrix}$ there is a constant c so that for all n, $C (x ↾ n) ⩾ n - f (n) - c$ . In particular, if x is random, then there exists a c such that for all n, $C (x ↾ n) ⩾ \frac{n}{2} - c$ . There is a nonempty $Π_{1}^{0}$ set that only contains random reals. So if $x ≫ \emptyset$ , then x computes a random real.

3. Over ${RCA}_{0}$

Lemma 3.1.
Suppose that $T \subseteq ω^{< ω}$ is a recursive tree so that there is a nonrecursive infinite path $x \in [T]$ that is Turing-below some arithmetically generic real $g \in 2^{ω}$ . Then T has a recursive perfect subtree.
Proof.
Suppose that T is a recursive tree with a nonrecursive infinite path $x \in [T]$ so that $x = Φ^{g}$ for some arithmetically generic real g.

Let $D_{0} = {σ ∣ Φ^{σ} \notin T}$ . Clearly, $D_{0}$ is arithmetical. Since g is arithmetically generic and $Φ^{g} \in [T]$ , there must be some $n_{0}$ so that for every $σ ≻ g ↾ n_{0}$ , $σ \notin D_{0}$ and so $Φ^{σ} \in T$ . Let $\begin{matrix} D_{1} = \{σ | \begin{matrix} σ ≻ g ↾ n_{0} \land \exists n \forall m ⩾ n \forall τ_{0} ≻ σ \forall τ_{1} ≻ σ : \\ (Φ^{τ_{0}} (m) ↓ \land Φ^{τ_{1}} (m) ↓ \to Φ^{τ_{0}} (m) = Φ^{τ_{1}} (m)) \end{matrix}\} . \end{matrix}$ Since g is arithmetically generic and $Φ^{g}$ is not recursive, there must be some $n_{1} ⩾ n_{0}$ so that for every $σ ≻ g ↾ n_{1}$ , $σ \notin D_{1}$ . So for every $σ ≻ g ↾ n_{1}$ and n, there are $τ_{0} ≻ σ$ , $τ_{1} ≻ σ$ and $m > n$ so that $Φ^{τ_{0}} (m) \neq Φ^{τ_{1}} (m)$ .

Now, by using this property of $D_{1}$ , it is routine to construct a recursive perfect tree $S \subseteq [g ↾ n_{1}]$ so that the set $T_{1} = {Φ^{σ} ∣ σ \in S}$ is also a recursive perfect tree. By the property of $n_{0}$ , $T_{1} \subseteq T$ . □

To construct a model satisfying $MPT$ , we have to relativize Lemma 3.1 accordingly.

Given a tree $T \subseteq ω^{< ω}$ , a real z and an index i, let $H K_{i} (z, T)$ be a $z \oplus T$ -recursive tree so that $\begin{matrix} [H K_{i} (z, T)] = \{f \oplus g | \begin{matrix} g \in [T] \land \forall n (f (n) is the least m \\ with Φ_{i}^{g ↾ m} (n) [m] ↓ \land Φ_{i}^{g} (n) = z (n)) \end{matrix}\} . \end{matrix}$ The idea of $H K_{i} (z, T)$ originates from Harrington and Kechris [5].

Obviously $H K_{i} (z, T) ⩽_{T} T \oplus z$ . Note that if $Φ_{i}^{g}$ is undefined or different from z then no path of the form $f \oplus g$ can be contained in $H K_{i} (z, T)$ . As a consequence, if $z ⩾_{T} T$ , then it holds for every $f \oplus g \in [H K_{i} (z, T)]$ that $g \in [T]$ and $g ⩾_{T} z ⩾_{T} z \oplus T ⩾_{T} H K_{i} (z, T)$ .
Theorem 3.2.
Over ${RCA}_{0}$ , $MPT$ does not imply ${WKL}_{0}$ .
Proof.
Choose a sequence $g_{0}, g_{1}, g_{2}, \dots$ of elements of $2^{ω}$ such that $g_{0}$ is arithmetically generic and such that for all n, $g_{n + 1}$ is arithmetically generic relative to $g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n}$ . Let $M = (ω, M, \dots)$ , where $M = {x ∣ \exists n (x ⩽_{T} ⨁_{i ⩽ n} g_{i})}$ . Obviously $M ⊭ {WKL}_{0}$ , as ${WKL}_{0}$ would guarantee the existence of PA-complete sets, but no such sets can exist in $M$ as generics do not compute PA-complete sets (see, e.g., Downey and Hirschfeldt [3, Corollary 2.24.6]).

Now assume we are given a tree T that is cofinal in M. Then there must be some $x \in [T]$ and some n so that $T ⩽_{T} g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n} <_{T} x$ . Let j be an index of the second reduction, that is, $Φ_{j}^{x} = g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n}$ . On the other hand there must exist some $m > 0$ so that $x ⩽_{T} ⨁_{i ⩽ m + n} g_{i}$ . Note that $⨁_{n < i ⩽ m + n} g_{i}$ is $⨁_{i ⩽ n} g_{i}$ -arithmetically generic. Then $H K_{j} (⨁_{i ⩽ n} g_{i}, T)$ is an $⨁_{i ⩽ n} g_{i}$ -recursive tree such that
for every $f \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ , $g \in [T]$ and $g ⩾_{T} ⨁_{i ⩽ n} g_{i} \oplus T ⩾_{T} H K_{j} (⨁_{i ⩽ n} g_{i}, T)$ ; and

there is an $f \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ , for example $f \oplus x$ for some f, so that $\begin{matrix} ⨁_{i ⩽ m + n} g_{i} ⩾_{T} f \oplus g >_{T} ⨁_{i ⩽ n} g_{i} ⩾_{T} H K_{j} (⨁_{i ⩽ n} g_{i}, T) . \end{matrix}$
Note that $⨁_{n < i ⩽ m + n} g_{i}$ is $[H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ -arithmetically generic. Relativizing Lemma 3.1 to $⨁_{i ⩽ n} g_{i}$ , we apply it to $[H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ to obtain a $⨁_{i ⩽ n} g_{i}$ -recursive perfect tree $S \subseteq H K_{j} (⨁_{i ⩽ n} g_{i}, T)$ . By the property (1) of $H K (⨁_{i ⩽ n} g_{i}, T)$ , S is pointed.

Note that it follows directly from the definition of $H K_{(\cdot)} (\cdot, \cdot)$ that if $f_{0} \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ and $f_{1} \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ then $f_{0} = f_{1}$ . In particular this is true for $f_{0} \oplus g$ and $f_{1} \oplus g \in S \subseteq H K_{j} (⨁_{i ⩽ n} g_{i}, T)$ . Since S is a perfect tree, by Lemma 2.2, there is an S-recursive perfect tree $T_{1}$ so that for every $g \in [T_{1}]$ , there is some f so that $f \oplus g \in [S]$ . Note that $T_{1} \subseteq T$ . Moreover, by property (1), for every $g \in [T_{1}]$ , $g ⩾_{T} S ⩾_{T} T_{1}$ . So $T_{1}$ is a pointed subtree of T. □

We prove that ${ACA}_{0}$ does not imply $wMPT$ .
Lemma 3.3.
There is a recursive tree T so that $[T]$ is countable and cofinal for the arithmetical reals, that is, for every arithmetical real x there exists some $y \in [T]$ with $y ⩾_{T} x$ .
Proof.
It is well known (see, for example, Sacks [16]) that there is a sequence of uniformly recursive trees ${T_{n}}_{n \in ω}$ so that for every n, $[T_{n}]$ contains a unique real $x_{n}$ of Turing degree $0^{(n)}$ . Let $T = ⋃_{n \in ω} n^{⌢} T_{n}$ . □
Proposition 3.4.
${ACA}_{0}$ does not imply $wMPT$ .
Proof.
Let $M = (ω, M, \dots)$ , where $M = {x ∣ \exists n (x ⩽_{T} \emptyset^{(n)})}$ . Obviously, $M ⊧ {ACA}_{0}$ . Let T be as in Lemma 3.3. Then T is cofinal in M. However, T has no perfect subtree. Hence $M ⊭ wMPT$ . □

By Corollary 5.8, over ${RCA}_{0}$ , $wMPT$ does not imply $MPT$ .
4. Over ${WKL}_{0}$

Lemma 4.1.
Suppose that $T \subseteq 2^{< ω}$ is a recursive tree and that $x \in [T]$ is a real so that there is some random real $y ⩽_{tt} x$ . Then for every real $z ≫ \emptyset$ , there must be some perfect tree $S \subseteq T$ so that $S ⩽_{T} z$ .
Proof.
Suppose that $Φ_{e}$ is a $tt$ -reduction so that $Φ_{e}^{x} = y$ . Let $c_{0}$ be such that for all n we have $C (y ↾ n) ⩾ \frac{n}{2} + c_{0}$ and let f be a recursive, increasing function such that for all n it holds that $Φ_{e}^{x ↾ f (n)} ↾ n [f (n)] = y ↾ n$ . Without loss of generality we assume that $f (n) > 2^{n}$ for all n.

Let $T_{1} \subseteq T$ be a recursive tree so that $\begin{matrix} [T_{1}] = {z \in 2^{ω} | z \in [T] \land \forall n (C (Φ_{e}^{z ↾ f (n)} ↾ n [f (n)]) ⩾ \frac{n}{2} - c_{0})} . \end{matrix}$ Note that the condition on the right-hand side is $Π_{1}^{0}$ , so that $T_{1}$ indeed exists. Note furthermore that $x \in [T_{1}]$ .

Let g be a recursive function so that $g (0) = 0$ and for every n, $g (n + 1) = f (f (g (n)))$ . Claim.
There is an $n_{0}$ so that for all $n > n_{0}$ and every $σ \in T_{1} \cap 2^{g (n)}$ with $[σ] \cap [T_{1}] \neq \emptyset$ , there are two different $σ_{0}, σ_{1} \in 2^{g (n + 1)} \cap T_{1}$ extending σ so that $[σ_{0}] \cap [T_{1}] \neq \emptyset$ and $[σ_{1}] \cap [T_{1}] \neq \emptyset$ .
Subproof.
If not, then for every m there is an $n ⩾ m$ and some $σ_{0} \in 2^{g (n)} \cap T_{1}$ with $[σ_{0}] \cap [T_{1}] \neq \emptyset$ , and a unique string σ in $g (n + 1)$ extending $σ_{0}$ such that $[σ] \cap [T_{1}] \neq \emptyset$ . Then we build a Turing machine M as follows: A pair $(ν_{1}, τ)$ is enumerated into M if and only if
$ν_{1} \in 2^{g (n)} \cap T_{1}$ and $| τ | = | f (g (n)) |$ for some n; and

there is a unique string $ν_{2} \in 2^{g (n + 1)} \cap T_{1}$ extending $ν_{1}$ such that for every $ν_{3} \in 2^{g (n + 1)} \cap T_{1}$ extending $ν_{1}$ with $ν_{3} \neq ν_{2}$ we have $[ν_{3}] \cap [T_{1}] = \emptyset$ ; and

for the $ν_{2}$ above we have $τ = Φ_{e}^{ν_{2} ↾ g (n + 1)} [g (n + 1)]$ .
Recall that $f (n) > 2^{n}$ for every n. So if $M (σ) = τ$ , then $C_{M} (τ) ⩽ log | τ |$ . Hence $C (τ) ⩽ log | τ | + c_{M}$ for some constant $c_{M}$ .

Then for every m, there is an $n > m$ and some $z \in [T_{1}]$ such that $\begin{matrix} C (Φ_{e}^{z ↾ g (n + 1)} ↾ f (g (n))) ⩽ log f (g (n)) + c_{M} . \end{matrix}$ This contradicts the choice of $T_{1}$ . □

Now define a partial recursive function $φ : 2^{< ω} \times ω \to 2^{< ω}$ as follows: For every n, $σ \in 2^{g (n)}$ and $m ⩽ 2^{g (n + 1)}$ let $φ (σ, m)$ be the mth finite string τ in $2^{g (n + 1)}$ for which we detect that $[τ] \cap [T_{1}] = \emptyset$ . By Proposition 2.1, there is a total z-recursive function f extending φ. For every $σ \in 2^{g (n)}$ , let $\begin{matrix} S_{σ} = {τ ≻ σ ∣ τ \in 2^{g (n + 1)}} ∖ {f (σ, m) ∣ m ⩽ 2^{g (n + 1) - g (n)} - 2} . \end{matrix}$ Then the sequence ${S_{σ}}_{σ \in 2^{< ω}}$ is z-recursive. By the claim, for every $n > n_{0}$ and $σ \in T_{1} \cap 2^{g (n)}$ with $[σ] \cap [T_{1}] \neq \emptyset$ ,
$| S_{σ} | ⩾ 2$ ; and

if $τ \in S_{σ}$ , then $[τ] \cap [T_{1}] \neq \emptyset$ ; and

any two different strings in $S_{σ}$ are incompatible.
Now, using these facts, it is easy to z-recursively construct a perfect tree $S \subseteq T_{1} \subseteq T$ . □
Theorem 4.2.
Over ${WKL}_{0}$ , $wMPT$ does not imply ${ACA}_{0}$ .
Proof.
Let $x_{0} = \emptyset ≪ x_{1} ≪ x_{2} ≪ \dots$ be a sequence of hyperimmune-free reals. We can see inductively that such a sequence exists, because we can at step n build an $x_{n - 1}$ -recursive tree $P_{n}$ such that all of its paths y have $y ≫ x_{n - 1}$ ; we can then apply the hyperimmune-free basis theorem relative to $x_{n - 1}$ to get $x_{n}$ .

Let $M = (ω, M, \dots)$ where $M = {y ∣ \exists n (y ⩽_{T} x_{n})}$ .

Obviously, $M ⊧ {WKL}_{0}$ but $M ⊭ {ACA}_{0}$ .

Let $T \subseteq ω^{< ω}$ be a tree that is cofinal in M. We code T into a tree $T_{1} \subseteq 2^{< ω}$ by letting $σ \in T_{1}$ if and only if there are a $τ \in T$ and a $k < ω$ such that $σ = 0^{τ (0)} 10^{τ (1)} \dots 0^{τ (| τ | - 1)} 10^{k}$ . Note that ${x ∣ x \in [T]} ∖ {x ∣ x \in [T_{1}]} = \emptyset$ , that is, the Turing degree spectrum of $T_{1}$ is at least as large as that of T. Furthermore note that $\begin{matrix} {x ∣ x \in [T_{1}]} ∖ {x ∣ x \in [T]} \subseteq {0}, \end{matrix}$ that is, the coding leaves the Turing degree spectrum of the tree unchanged, modulo the computable degree. Therefore $T_{1}$ is also cofinal in M.

${WKL}_{0}$ implies that a $T_{1}$ -random real y exists; since $T_{1}$ is cofinal, there must be some $x \in [T_{1}]$ with $x ⩾_{T} y$ in M. Since x is hyperimmune-free, in fact $y ⩽_{tt} x$ . Fix a number n so that $x_{n} ≫ T_{1}$ . Applying Lemma 4.1 by relativizing it to $T_{1}$ , there must be some $x_{n}$ -recursive perfect tree $S_{1} \subseteq T_{1}$ . Then it is easy to see that there must be some $x_{n}$ -recursive perfect tree $S \subseteq T$ . Thus $S \in M$ . □

Note that by Corollary 5.8, over ${WKL}_{0}$ , $wMPT$ does not imply $MPT$ . Question 4.3.
Over ${WKL}_{0}$ , does $MPT$ imply ${ACA}_{0}$ ?

5. Over ${ACA}_{0}$

The following lemma is easy.

Lemma 5.1.
Over ${RCA}_{0}$ , if T is a pointed tree, then for every real $x ⩾_{T} T$ , there is a $y \in [T]$ so that $x \equiv_{T} y$ .
Proof.
As T is in particular perfect, we can choose a path y such that y encodes x by branching in T according to the bits of x. Then $x ⩾_{T} x \oplus T ⩾_{T} y ⩾_{T} y \oplus T ⩾_{T} x$ . □

The following important theorem can be used to transfer results about $Σ_{3}^{0}$ sets to recursive trees.
Theorem 5.2 (Harrington and Kechris [5]).

Over ${RCA}_{0}$ , for every $Σ_{3}^{0}$ class A, there is a recursive tree T so that ${x ∣ x \in [T]} = {x ∣ x \in A}$ . Moreover, the proof can be relativized.

Recall the definition of $Γ - TD$ from p. 150. Montalbán and Shore proved the following theorem by combining Theorem 5.2 with a number of classical recursion theory results.

Theorem 5.3 (Montalbán and Shore [12]).

Over ${ACA}_{0}$ , $Σ_{3}^{0} - TD$ implies ${ATR}_{0}$ .

Now we are ready to show that $MPT$ implies ${ATR}_{0}$ .

Proposition 5.4.

Over ${ACA}_{0}$ , $MPT$ implies ${ATR}_{0}$ .

Proof.

By Theorem 5.3, it is sufficient to prove that $MPT$ implies $Σ_{3}^{0} - TD$ .

We only prove the lightface version. Given any $Σ_{3}^{0}$ , cofinal, and Turing-invariant set A, by Theorem 5.2, there is a recursive tree T so that ${x ∣ x \in [T]} = {x ∣ x \in A}$ . So $[T]$ is also cofinal. By $MPT$ , T has a pointed subtree $T_{1}$ . By Lemma 5.1, for every real $x ⩾_{T} T_{1}$ , there is a $y \in [T_{1}]$ so that $x \equiv_{T} y$ . Therefore A contains an upper cone of Turing degrees. □

Remark 5.5.

Note that, over ${RCA}_{0}$ , $Σ_{3}^{0} - TD$ does not imply $wMPT$ . This is because ${RCA}_{0}$ has a model $M$ that consists only of recursive reals. Then $M$ satisfies $Σ_{3}^{0} - TD$ vacuously, but it contains a recursive tree T consisting exactly of one recursive path. Such a T is then vacuously cofinal, but not perfect. So $M$ does not satisfy $wMPT$ .

In the following theorem we will show that ${ATR}_{0}$ implies $MPT$ . For this purpose, let $T \subseteq ω^{< ω}$ be any tree and define the T-recursive tree $H K (T)$ as follows, $\begin{matrix} [H K (T)] = \{(i^{⌢} f \oplus g) \oplus h | \begin{matrix} g \in [T] \land h = (i^{⌢} f \oplus g) \oplus Φ_{i}^{g} \land \\ \forall n (f (n) is the least m with Φ_{i}^{g ↾ m} (n) [m] ↓) \end{matrix}\} . \end{matrix}$ The idea for $H K (T)$ is again taken from Harrington and Kechris [5].

Theorem 5.6.

${ATR}_{0}$ implies $MPT$ .

Proof.

Given any cofinal tree T, $H K (T)$ is clearly also cofinal. By Theorem 2.4, $H K (T)$ is determined. It is well known (see Martin [9] or Montalbán and Shore [12]) that if $H K (T)$ is cofinal, then II cannot have a winning strategy. So I has a winning strategy, say w. Let $x \in 2^{ω}$ be a real with $x \equiv_{T} w$ .

Let S be a w-recursive tree so that $[S] = {w * (z \oplus x) ∣ z \in 2^{ω}}$ . Then

if $(i^{⌢} f_{0} \oplus g) \oplus (z_{0} \oplus x) \in [S]$ and $(i^{⌢} f_{1} \oplus g) \oplus (z_{1} \oplus x) \in [S]$ , then $f_{0} = f_{1}$ and $z_{0} = z_{1}$ . Together with Lemma 2.2 this implies that there is a w-recursive perfect tree $T_{1} \subseteq T$ ;

for every $(i^{⌢} f \oplus g) \oplus (z \oplus x) \in [S]$ , we have that $g \in [T]$ and $g ⩾_{T} z \oplus x ⩾_{T} w ⩾_{T} S$ . This implies that $T_{1}$ is pointed.

Thus

{ATR}_{0}

implies

MPT

. □

However, even over ${ACA}_{0}$ , $wMPT$ is strictly weaker than ${ATR}_{0}$ .

Theorem 5.7.

Over ${ACA}_{0}$ , $wMPT$ does not imply ${ATR}_{0}$ .

Proof.

Let $g_{0} \in 2^{ω}$ be arithmetically generic and for every n let $g_{n + 1} \in 2^{ω}$ be arithmetically generic relative to $g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n}$ . Let $M = (ω, M, \dots)$ , where $M = {x ∣ \exists n (x ⩽_{T} {(⨁_{i ⩽ n} g_{i})}^{(n)})}$ . Obviously $M ⊧ {ACA}_{0}$ , but $M ⊭ {ATR}_{0}$ as $\emptyset^{(ω)}$ is not in M.

Now let some tree $T \subseteq ω^{< ω}$ , which is cofinal in M, be given. Then there must be some real $x \in [T]$ and some n so that $T ⩽_{T} \emptyset^{(n)} \oplus g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n} <_{T} x$ and x is not arithmetical in $g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n}$ . Fix j such that $Φ_{j}^{x} = \emptyset^{(n)} \oplus g_{0} \oplus g_{1} \oplus g_{2} \oplus \dots \oplus g_{n}$ . On the other hand, there is some $m > 0$ so that $x ⩽_{T} \emptyset^{(m + n)} \oplus (⨁_{i ⩽ m + n} g_{i})$ . Note that $⨁_{n < i ⩽ m + n} g_{i}$ is $\emptyset^{(m + n)} \oplus (⨁_{i ⩽ n} g_{i})$ -arithmetically generic. Then $H K (⨁_{i ⩽ n} g_{i}, T)$ is a $\emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i})$ -recursive tree so that

for every $f \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ , $g \in [T]$ and $g ⩾_{T} \emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i}) \oplus T ⩾_{T} H K_{j} (⨁_{i ⩽ n} g_{i}, T)$ ; and

there is an $f \oplus g \in [H K_{j} (⨁_{i ⩽ n} g_{i}, T)]$ , for example $f \oplus x$ for some f, so that $\begin{matrix} \emptyset^{(m + n)} \oplus (⨁_{i ⩽ m + n} g_{i}) ⩾_{T} f \oplus g >_{T} \emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i}) ⩾_{T} H K_{j} (⨁_{i ⩽ n} g_{i}, T) . \end{matrix}$

Note that

⨁_{n < i ⩽ m + n} g_{i}

[H K_{j} (\emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i}), T)]

-arithmetically generic. Relativizing Lemma 3.1 to

\emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i})

, and noting the fact that x is not arithmetical in

⨁_{i ⩽ n} g_{i}

, we apply it to

[H K_{j} (\emptyset^{(n)} \oplus (⨁_{i ⩽ n} g_{i}), T)]

and obtain that there exists a

\emptyset^{(m + n)} \oplus (⨁_{i ⩽ n} g_{i})

-recursive perfect tree

S \subseteq H K_{j} (⨁_{i ⩽ n} g_{i}, T)

Figure 1.

All arrows represent strict implications.

Note that $f_{0} \oplus g \in S \subseteq [H K (⨁_{i ⩽ n} g_{i}, T)]$ and $f_{1} \oplus g \in S \subseteq [H K (⨁_{i ⩽ n} g_{i}, T)]$ implies $f_{0} = f_{1}$ . Using the fact that S is a perfect tree, by Lemma 2.2, there is a $\emptyset^{(m + n)} \oplus (⨁_{i ⩽ n} g_{i})$ -recursive perfect tree $T_{1}$ so that for every $g \in [T_{1}]$ , there is some f so that $f \oplus g \in [S]$ . Note that $T_{1} \subseteq T$ . So T has a perfect subtree in M. Thus $M ⊧ wMPT$ . □

Corollary 5.8.

Over ${ACA}_{0}$ , $wMPT$ does not imply $MPT$ .

We remark that by a method similar as in the proof of Theorem 5.7 and by iterating the Turing jump through the recursive ordinals it can be shown that, even over $Δ_{1}^{1} - {CA}_{0}$ , $wMPT$ does not imply ${ATR}_{0}$ .

Figure 1 gives an overview of the obtained results.

Footnotes

Acknowledgements

Rupert Hölzl was supported by and Frank Stephan was partially supported by the Ministry of Education of Singapore through grant R146-000-184-112 (MOE2013-T2-1-062). Liang Yu was partially supported by the National Natural Science Fund of China through Grant 11322112.

References

Blass, Complexity of winning strategies, Discrete Mathematics 3 (1972), 295–300.

C.T.

Chong and

Yu, Maximal chains in the Turing degrees, The Journal of Symbolic Logic 72(4) (2007), 1219–1227.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.

L.A.

Harrington, Analytic determinacy and

0^{♯}

, The Journal of Symbolic Logic 43(4) (1978), 685–693.

L.A.

Harrington and

A.S.

Kechris, A basis result for

Σ_{3}^{0}

sets of reals with an application to minimal covers, Proceedings of the American Mathematical Society 53(2) (1975), 445–448.

C.G.

JockuschJr. and

R.I.

Soare,

Π_{1}^{0}

classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.

Koellner and

W.H.

Woodin, Large cardinals from determinacy, in: Handbook of Set Theory,

Foreman and

Kanamori, eds, Springer, Netherlands, 2010, pp. 1951–2119.

Lerman, Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer, Berlin, 1983.

D.A.

Martin, The axiom of determinateness and reduction principles in the analytical hierarchy, Bulletin of the American Mathematical Society 74 (1968), 687–689.

10.

D.A.

Martin and

J.R.

Steel, A proof of projective determinacy, Journal of the American Mathematical Society 2(1) (1989), 71–125.

11.

J.S.

Miller and

Yu, On initial segment complexity and degrees of randomness, Transactions of the American Mathematical Society 360(6) (2008), 3193–3210.

12.

Montalbán and

Shore, The strength of Turing determinacy within second order arithmetic, Fundamenta Mathematicae, to appear.

13.

Y.N.

Moschovakis, Descriptive Set Theory, 2nd edn, Mathematical Surveys and Monographs, Vol. 155, American Mathematical Society, Providence, RI, 2009.

14.

Nies, Computability and Randomness, Oxford Logic Guides, Vol. 51, Oxford Univ. Press, Oxford, 2009.

15.

Odifreddi, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989.

16.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer, Berlin, 1990.

17.

S.G.

Simpson, Subsystems of Second Order Arithmetic, Perspectives in Logic, 2nd edn, Cambridge Univ. Press, Cambridge, 2009.

18.

T.A.

Slaman and

J.R.

Steel, Definable functions on degrees, in: Cabal Seminar 81–85, Lecture Notes in Mathematics, Vol. 1333, Springer, Berlin, 1988, pp. 37–55.

19.

R.M.

Solovay, A model of set-theory in which every set of reals is Lebesgue measurable, Annals of Mathematics 2(92) (1970), 1–56.

20.

Steel, Determinateness and subsystems of analysis, PhD thesis, University of California, Berkeley, 1976.

On Martin’s pointed tree theorem

Abstract

Keywords

1. Introduction

Theorem 1.1 (Martin [9]).

2.1. General notations

Proposition 2.1 (Folklore).

2.3. Game theory

Theorem 2.3 (Martin [9]).

Theorem 2.4 (Blass [1] and Steel [20]).

2.4. Algorithmic randomness

3. Over RCA 0

Theorem 5.3 (Montalbán and Shore [12]).

Footnotes

Acknowledgements

References

3. Over ${RCA}_{0}$