Trees and Π⁰₁ classes · Computability Theory

Many problems of mathematics ask for an infinite object satisfying conditions that can each be refuted in finite time: a coloring of an infinite graph in which no two adjacent vertices share a color, a completion of a consistent theory, a separating set for two disjoint c.e. sets. The set of solutions of such a problem is a $\Pi^0_1$ class: the set of infinite paths through a computable binary tree. This lesson defines trees, the topology of Cantor space, and the $\Pi^0_1$ classes, and proves weak König’s lemma, which guarantees that an infinite binary tree has a path. The rest of the course studies how complex these paths must be.

1.1 Binary trees

We use the notation for strings of Computation relative to an oracle: $\sigma \preceq \tau$ is the prefix relation, $|\sigma|$ the length, and $[\sigma]$ the cylinder of the sequences extending $\sigma$ . We also write $2^n$ for the set of strings of length $n$ , and $2^{\leq n}$ for the set of strings of length at most $n$ .

Definition 1.1.#

A binary tree is a set $T \subseteq \bstr$ closed under prefixes: if $\tau \in T$ and $\sigma \preceq \tau$ , then $\sigma \in T$ . Its elements are nodes. A path through $T$ is a sequence $X \in \cs$ all of whose prefixes belong to $T$ ; the class of paths is written $[T]$ . A node $\sigma \in T$ is extendible if $[\sigma] \cap [T] \neq \emptyset$ , that is, if some path goes through it.

A binary tree. The dashed branches are finite: their nodes are in the tree but are not extendible. Every other node lies on an infinite path, one of which is highlighted.

Lemma 1.2 (Weak König’s lemma).#

Every infinite binary tree has a path.

Proof of Lemma 1.2.

Let $T$ be an infinite binary tree. Say that a node $\sigma \in T$ is large if infinitely many nodes of $T$ extend it. The root $\varepsilon$ is large, since $T$ is infinite. If $\sigma$ is large, then one of $\sigma 0$ and $\sigma 1$ is large: every node extending $\sigma$ other than $\sigma$ itself extends one of them, and they cannot both have finitely many extensions in $T$ . Define $X$ by induction: $X(n)$ is $0$ if $(X \uh n)\, 0$ is large, and $1$ otherwise. By induction, every $X \uh n$ is large, hence in $T$ , so $X \in [T]$ .

The proof chooses, at each step, a branch with infinitely many nodes above it, a question that cannot be decided by an algorithm in general. The course measures exactly how much computational power this choice requires.

1.2 The topology of Cantor space

Definition 1.3.#

A class $\mathcal U \subseteq \cs$ is open if it is a union of cylinders: $\mathcal U = \bigcup_{\sigma \in W} [\sigma]$ for some set of strings $W$ , written $\mathcal U = [W]^{\prec}$ . A class is closed if its complement is open.

These are the open and closed sets of the product topology on $\cs = \{0, 1\}^\nat$ . The cylinders $[\sigma]$ are both open and closed: the complement of $[\sigma]$ is the union of the cylinders $[\tau]$ with $|\tau| = |\sigma|$ , $\tau \neq \sigma$ .

Proposition 1.4.#

A class $\mathcal P \subseteq \cs$ is closed if and only if $\mathcal P = [T]$ for some binary tree $T$ . One can take $T = \{ X \uh n : X \in \mathcal P, n \in \nat \}$ , whose nodes are all extendible.

Proof of Proposition 1.4.

If $\mathcal P = [T]$ , its complement is the union of the cylinders $[\sigma]$ with $\sigma \notin T$ : a sequence is not a path exactly when one of its prefixes is not in $T$ . So $\mathcal P$ is closed. Conversely, let $\mathcal P$ be closed, with complement $[W]^{\prec}$ , and let $T = \{ X \uh n : X \in \mathcal P \}$ , a tree. Clearly $\mathcal P \subseteq [T]$ . If $Y \in [T] \setminus \mathcal P$ , then $Y \in [\sigma]$ for some $\sigma \in W$ ; but $\sigma \prec Y$ is in $T$ , so $\sigma = X \uh n$ for some $X \in \mathcal P$ , and $X \in [\sigma] \subseteq [W]^{\prec}$ , a contradiction.

Proposition 1.5 (Compactness).#

Cantor space is compact: if $\cs = \bigcup_{\sigma \in W} [\sigma]$ , then already $\cs = \bigcup_{\sigma \in F} [\sigma]$ for a finite $F \subseteq W$ . More generally, every closed class is compact, and a decreasing sequence $\mathcal P_0 \supseteq \mathcal P_1 \supseteq \cdots$ of non-empty closed classes has a non-empty intersection.

Proof of Proposition 1.5.

Let $T$ be the set of strings having no prefix in $W$ , a tree. Its paths are the sequences not covered by $[W]^{\prec}$ , so $[T] = \emptyset$ , and $T$ is finite by Lemma 1.2. Let $n$ exceed the lengths of its nodes. Every string of length $n$ is then outside $T$ , so it has a prefix in $W$ , of length at most $n$ ; the finitely many such prefixes form $F$ . The same argument applies to a cover of a closed class $[S]$ , using the tree $S \cap T$ . For the last statement, if $\bigcap_n \mathcal P_n = \emptyset$ , the complements of the $\mathcal P_n$ form an open cover of $\mathcal P_0$ , so finitely many of them cover it, and since they increase, one of them does; then $\mathcal P_n = \emptyset$ for some $n$ .

1.3 Π⁰₁ classes

Definition 1.6.#

A class $\mathcal P \subseteq \cs$ is a $\Pi^0_1$ class if $\mathcal P = [T]$ for some computable binary tree $T$ . A $\Sigma^0_1$ class is a class $[W]^{\prec}$ with $W$ a c.e. set of strings. An index of a $\Pi^0_1$ class is an index of the characteristic function of such a tree $T$ .

Proposition 1.7.#

For $\mathcal P \subseteq \cs$ , the following are equivalent:

$\mathcal P$ is a $\Pi^0_1$ class;
$\mathcal P = [T]$ for some co-c.e. tree $T$ ;
$\mathcal P = \{ X : \forall n\ R(X \uh n) \}$ for some computable relation $R$ on strings;
$\mathcal P = \{ X : \Phi^X_e(0)\diverge \}$ for some $e$ ;
the complement of $\mathcal P$ is a $\Sigma^0_1$ class.

Moreover, the passages between these descriptions are uniform in indices.

Proof of Proposition 1.7.

(1 ⇒ 2) A computable tree is co-c.e.

(2 ⇒ 5) The complement of $[T]$ is $[\bstr \setminus T]^{\prec}$ , and $\bstr \setminus T$ is c.e.

(5 ⇒ 4) If the complement is $[W]^{\prec}$ with $W$ c.e., let $\Phi_e$ be the functional which, with oracle $X$ , enumerates $W$ and halts as soon as it finds a string $\sigma \in W$ with $\sigma \prec X$ . Then $\Phi^X_e(0)\converge$ if and only if $X \in [W]^{\prec}$ .

(4 ⇒ 3) Let $R(\sigma)$ be " $\Phi^\sigma_e(0)[|\sigma|]\diverge$ ". It is computable, and by Proposition 1.5 of “Computation relative to an oracle”, $\Phi^X_e(0)\diverge$ if and only if $R(X \uh n)$ for every $n$ .

(3 ⇒ 1) Let $T = \{ \sigma : \forall \tau \preceq \sigma\ R(\tau) \}$ . It is a computable tree, and $X \in [T]$ if and only if $R(X \uh n)$ for every $n$ .

All steps transform indices by computable functions.

Example 1.8.#

Let $A$ and $B$ be disjoint c.e. sets. The class $\mathcal S(A, B) = \{ X : A \subseteq X \text{ and } X \cap B = \emptyset \}$ of separating sets is $\Pi^0_1$ : $X \notin \mathcal S(A, B)$ if and only if some $n \in A$ has $X(n) = 0$ or some $n \in B$ has $X(n) = 1$ , a $\Sigma^0_1$ condition on prefixes of $X$ .
The class $\mathrm{DNC}_2 = \{ X : X(e) \neq \Phi_e(e) \text{ for every } e \text{ with } \Phi_e(e)\converge \}$ is $\Pi^0_1$ , by the same argument; its elements are the diagonally non-computable $\{0, 1\}$ -valued functions.
A singleton $\{ Y \}$ with $Y$ computable is a $\Pi^0_1$ class, with tree $\{ Y \uh n : n \in \nat \}$ .

Proposition 1.9.#

Given an index of a computable tree $T$ , the property $[T] = \emptyset$ is $\Sigma^0_1$ : $[T] = \emptyset$ if and only if $T$ has no node of some length $n$ . Consequently, the set of $e$ such that $\{ X : \Phi^X_e(0)\diverge \} = \emptyset$ is c.e., and the extendible nodes of a computable tree form a co-c.e. set.

Proof of Proposition 1.9.

By Lemma 1.2, $[T] = \emptyset$ if and only if $T$ is finite, if and only if some length $n$ has no node in $T$ , since $T$ is closed under prefixes. For a given $n$ , this is decided by testing the $2^n$ strings of length $n$ . For the class $\{ X : \Phi^X_e(0)\diverge \}$ , the tree $\{ \sigma : \forall \tau \preceq \sigma\ \Phi^\tau_e(0)[|\tau|]\diverge \}$ of Proposition 1.7 is computable, uniformly in $e$ , so its emptiness is a $\Sigma^0_1$ property of $e$ . (By contrast, the set of $e$ such that $\Phi_e$ is the characteristic function of a tree without paths is not c.e.: the set of indices of total functions reduces to it.) A node $\sigma$ is not extendible if and only if the computable tree $\{ \tau \in T : \tau \preceq \sigma \text{ or } \sigma \preceq \tau \}$ has no path, which is a $\Sigma^0_1$ condition, uniformly in $\sigma$ .

This is a consequence of compactness: emptiness of a $\Pi^0_1$ class, a priori a statement about all sequences $X$ , is in fact $\Sigma^0_1$ . Non-emptiness, which asks for an infinite path, is accordingly a $\Pi^0_1$ property: a finite amount of computation can show that a class is empty, never that it is non-empty.

1.4 Exercises

Exercise 1.10 ★.#

Show that the intersection of two $\Pi^0_1$ classes, and the union of two $\Pi^0_1$ classes, are $\Pi^0_1$ classes, uniformly in indices.

Solution

If $\mathcal P = [S]$ and $\mathcal Q = [T]$ with $S$ and $T$ computable trees, then $\mathcal P \cap \mathcal Q = [S \cap T]$ and $\mathcal P \cup \mathcal Q = [S \cup T]$ . The first equality is immediate. For the second, a path of $S \cup T$ that is not a path of $S$ has a prefix $\sigma \notin S$ ; all its longer prefixes are then outside $S$ , hence in $T$ , and its shorter prefixes are prefixes of nodes of $T$ , hence in $T$ ; so it is a path of $T$ .

Exercise 1.11 ★★.#

Show that a class $\mathcal P \subseteq \cs$ is $\Pi^0_1$ if and only if the set of strings $\sigma$ with $[\sigma] \cap \mathcal P = \emptyset$ is c.e., and $\mathcal P$ is closed.

Solution

If $\mathcal P = [T]$ with $T$ computable, then $[\sigma] \cap \mathcal P = \emptyset$ is the $\Sigma^0_1$ property of Proposition 1.9, uniformly in $\sigma$ . Conversely, if $\mathcal P$ is closed and $W = \{ \sigma : [\sigma] \cap \mathcal P = \emptyset \}$ is c.e., then the complement of $\mathcal P$ is $[W]^{\prec}$ : a sequence outside the closed class $\mathcal P$ has a cylinder neighborhood disjoint from $\mathcal P$ . So the complement is a $\Sigma^0_1$ class, and $\mathcal P$ is $\Pi^0_1$ by Proposition 1.7.

1.5 Notes and references

König’s lemma is due to Dénes Kőnig (1927). $\Pi^0_1$ classes were studied systematically from the 1950s, notably by Kleene, Kreisel and Shoenfield, and the theory of their members by Jockusch and Soare (1972). Cenzer and Remmel’s survey gives a broad account.

D. Kőnig, Über eine Schlussweise aus dem Endlichen ins Unendliche, Acta Scientiarum Mathematicarum (Szeged) 3 (1927), 121–130.
C. G. Jockusch and R. I. Soare, Π⁰₁ classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.
D. Cenzer and J. B. Remmel, Π⁰₁ classes in mathematics, in Handbook of Recursive Mathematics, Volume 2, Studies in Logic 139, North-Holland, 1998, 623–821.