Σ⁰ₙ and Π⁰ₙ sets · Computability Theory

The c.e. sets are the sets defined by an existential quantifier over a computable relation (Theorem 4.3 of “Computably enumerable sets”). Allowing more quantifiers, alternating between $\exists$ and $\forall$ , gives a classification of sets by the complexity of their definitions: the arithmetic hierarchy, due to Kleene and Mostowski. The set $\mathrm{Tot}$ of indices of total functions, for instance, is defined by ” $\forall x\ \exists s$ , the computation $\Phi_e(x)$ converges at stage $s$ ”: a universal quantifier followed by an existential one, over a computable relation. This lesson defines the hierarchy and establishes the closure properties used to place sets in it. The next lesson relates it to the Turing jump.

1.1 Definition

Definition 1.1.#

Let $n \geq 1$ and $k \geq 1$ . A relation $A \subseteq \nat^k$ is

$\Sigma^0_n$ if there is a computable relation $R \subseteq \nat^{k + n}$ such that

\vec x \in A \iff \exists y_1\ \forall y_2\ \exists y_3 \cdots Q y_n\ \ R(\vec x, y_1, \dots, y_n),

with $n$ alternating quantifiers, the last one $Q$ being $\exists$ if $n$ is odd and $\forall$ if $n$ is even; 2. $\Pi^0_n$ if the same holds with the quantifiers $\forall y_1\ \exists y_2 \cdots$ , starting with a universal one; 3. $\Delta^0_n$ if it is both $\Sigma^0_n$ and $\Pi^0_n$ .

By convention, the $\Sigma^0_0$ , $\Pi^0_0$ and $\Delta^0_0$ relations are the computable relations. A relation is arithmetic if it is $\Sigma^0_n$ for some $n$ .

The superscript $0$ indicates that the quantifiers range over integers, that is, first-order objects; the analytic hierarchy $\Sigma^1_n$ , studied in the course on higher computability, quantifies over sets of integers. Some authors use $\Delta_0$ for the relations defined by formulas with bounded quantifiers only; these are particular computable relations.

Example 1.2.#

A set is $\Sigma^0_1$ if it is of the form $\{ x : \exists y\ R(x, y) \}$ with $R$ computable: these are exactly the c.e. sets (Theorem 4.3 of “Computably enumerable sets”).
$\mathrm{Tot} = \{ e : \forall x\ \exists s\ \Phi_e(x)[s]\converge \}$ is $\Pi^0_2$ , since the relation $\Phi_e(x)[s]\converge$ is computable (Proposition 1.4 of “Programs as numbers”).
$\mathrm{Fin} = \{ e : W_e \text{ is finite} \} = \{ e : \exists n\ \forall x\ \forall s\ (x > n \to \Phi_e(x)[s]\diverge) \}$ is $\Sigma^0_2$ , once the two universal quantifiers are merged (see below).
$\mathrm{Cof} = \{ e : W_e \text{ is cofinite} \} = \{ e : \exists n\ \forall x\ \exists s\ (x \leq n \vee \Phi_e(x)[s]\converge) \}$ is $\Sigma^0_3$ .

The first levels of the arithmetic hierarchy. Each level

\Delta^0_n

is contained in

\Sigma^0_n

and in

\Pi^0_n

, and both are contained in

\Delta^0_{n+1}

. All inclusions are strict, as shown in the next lesson.

1.2 Normal forms

Proposition 1.3.#

Let $n \geq 1$ .

A relation is $\Sigma^0_n$ if and only if its complement is $\Pi^0_n$ .
Every $\Sigma^0_n$ or $\Pi^0_n$ relation is $\Delta^0_{n+1}$ .
Contraction. If $\vec x \in A \iff \exists y_1 \exists y_2\ P(\vec x, y_1, y_2)$ with $P$ a $\Pi^0_{n-1}$ relation, then $\vec x \in A \iff \exists z\ P(\vec x, \pi_0(z), \pi_1(z))$ ; dually for universal quantifiers. Consequently, a relation defined by a prefix of quantifiers over a computable relation is $\Sigma^0_n$ if the prefix starts with $\exists$ and has $n$ blocks of quantifiers of the same kind, and $\Pi^0_n$ if it starts with $\forall$ and has $n$ blocks.

Proof of Proposition 1.3.

The negation of $\exists y_1\ \forall y_2 \cdots R$ is $\forall y_1\ \exists y_2 \cdots \neg R$ , and the complement of a computable relation is computable.
Add a dummy quantifier: if $\vec x \in A \iff \exists y_1 \cdots Q y_n\ R$ , then $\vec x \in A \iff \forall y_0\ \exists y_1 \cdots Q y_n\ R$ and $\vec x \in A \iff \exists y_1 \cdots Q y_n\ Q' y_{n+1}\ R$ , where $R$ does not depend on $y_0$ or $y_{n+1}$ . The first form is $\Pi^0_{n+1}$ , the second $\Sigma^0_{n+1}$ . The case of $\Pi^0_n$ relations is symmetric.
The pairing function is a bijection, so $\exists y_1 \exists y_2$ ranges over the same pairs as $\exists z$ with $(y_1, y_2) = (\pi_0(z), \pi_1(z))$ . The relation $P(\vec x, \pi_0(z), \pi_1(z))$ is $\Pi^0_{n-1}$ : substitute $\pi_0(z), \pi_1(z)$ for $y_1, y_2$ in the computable relation of a normal form of $P$ , which gives a computable relation, since $\pi_0$ and $\pi_1$ are computable. So merging two adjacent quantifiers of the same kind does not change the level. Applying this to the quantifiers of a prefix over a computable relation, which may stand anywhere in the prefix, merges each block into a single quantifier.

1.3 Closure properties

To place a set in the hierarchy, one writes a definition and counts alternations. This is justified by the following closure properties.

Proposition 1.4.#

Let $n \geq 1$ . The $\Sigma^0_n$ relations and the $\Pi^0_n$ relations are closed under:

finite unions and intersections;
substitution of total computable functions: if $A \subseteq \nat^m$ is $\Sigma^0_n$ and $g_1, \dots, g_m : \nat^k \to \nat$ are total computable, then $\{ \vec x : (g_1(\vec x), \dots, g_m(\vec x)) \in A \}$ is $\Sigma^0_n$ , and likewise for $\Pi^0_n$ ;
bounded quantifiers $\exists z < y$ and $\forall z < y$ .

Moreover, $\Sigma^0_n$ relations are closed under existential quantification $\exists y$ , and $\Pi^0_n$ relations under universal quantification $\forall y$ .

Proof of Proposition 1.4.

By induction on $n$ . For $n = 1$ , the $\Sigma^0_1$ relations are the c.e. relations, and their closure under finite unions and intersections, substitution (preimages under computable functions), projection and bounded universal quantification is Proposition 4.5 of “Computably enumerable sets”; bounded existential quantification $\exists z < y\ P$ is the projection $\exists z\ (z < y \wedge P)$ . The $\Pi^0_1$ case follows by complementation, using item 1 of Proposition 1.3.

Suppose the statement holds for $n$ , and let $A$ and $B$ be $\Sigma^0_{n+1}$ : $\vec x \in A \iff \exists y\ P(\vec x, y)$ and $\vec x \in B \iff \exists y\ Q(\vec x, y)$ , with $P$ and $Q$ in $\Pi^0_n$ (by definition, after grouping the quantifiers following the first one).

$\vec x \in A \cap B \iff \exists z\ \big(P(\vec x, \pi_0(z)) \wedge Q(\vec x, \pi_1(z))\big)$ , and $\vec x \in A \cup B \iff \exists y\ (P(\vec x, y) \vee Q(\vec x, y))$ . The relations inside are $\Pi^0_n$ by the induction hypothesis (substitution, then intersection or union).
$(g_1(\vec x), \dots) \in A \iff \exists y\ P(g_1(\vec x), \dots, y)$ , and the relation inside is $\Pi^0_n$ by the induction hypothesis.
$\exists z < w\ \exists y\ P(\vec x, z, y) \iff \exists u\ (\pi_0(u) < w \wedge P(\vec x, \pi_0(u), \pi_1(u)))$ , which is $\Sigma^0_{n+1}$ . For the bounded universal quantifier, the key equivalence is

\forall z < w\ \ \exists y\ P(\vec x, z, y) \iff \exists v\ \ \forall z < w\ \ \exists y < v\ \ P(\vec x, z, y).

From left to right, choose for each of the finitely many $z < w$ a witness $y_z$ , and let $v$ exceed all of them; the converse is clear. By the induction hypothesis, $\exists y < v\ P$ is $\Pi^0_n$ (bounded quantification), then $\forall z < w\ \exists y < v\ P$ is $\Pi^0_n$ (bounded quantification again), so the right-hand side is $\Sigma^0_{n+1}$ .

Existential quantification: $\exists u\ \exists y\ P(\vec x, u, y)$ is contracted to a single quantifier. The $\Pi^0_{n+1}$ case follows by complementation.

The equivalence used for the bounded universal quantifier is called collection: finitely many witnesses can be bounded by a single number. It fails for unbounded quantifiers, which is why $\forall z\ \exists y$ cannot in general be rewritten as $\exists v\ \forall z$ .

1.4 Relativization and reductions

Definition 1.5.#

For $X \in \cs$ , the classes $\Sigma^0_n(X)$ , $\Pi^0_n(X)$ and $\Delta^0_n(X)$ are defined as in Definition 1.1, with $X$ -computable relations in place of computable ones.

All the results above relativize. In particular, the $\Sigma^0_1(X)$ sets are the $X$ -c.e. sets, and the $\Delta^0_1(X)$ sets are the $X$ -computable sets.

Proposition 1.6.#

A set is $\Sigma^0_1$ if and only if it is c.e., and $\Delta^0_1$ if and only if it is computable.
If $A \leq_m B$ and $B$ is $\Sigma^0_n(X)$ , then $A$ is $\Sigma^0_n(X)$ ; likewise for $\Pi^0_n(X)$ and $\Delta^0_n(X)$ .

Proof of Proposition 1.6.

The first statement is Theorem 4.3 of “Computably enumerable sets”. A set is $\Delta^0_1$ if and only if it and its complement are c.e., that is, if and only if it is computable (Proposition 4.8 of “Computably enumerable sets”).
If $f$ reduces $A$ to $B$ , then $A = \{ x : f(x) \in B \}$ , and the result is the substitution property of Proposition 1.4, relativized to $X$ .

Many-one reducibility preserves the levels of the hierarchy, while Turing reducibility does not: every set is Turing equivalent to its complement, and the complement of a $\Sigma^0_1$ set that is not computable is not $\Sigma^0_1$ . This is why completeness at a level of the hierarchy is defined with many-one reductions.

Definition 1.7.#

A set $A$ is $\Sigma^0_n$ -complete if it is $\Sigma^0_n$ and $B \leq_m A$ for every $\Sigma^0_n$ set $B$ ; $\Pi^0_n$ -complete sets are defined similarly.

By Theorem 4.12 of “Computably enumerable sets”, $\emptyset'$ is $\Sigma^0_1$ -complete, and so its complement is $\Pi^0_1$ -complete, since $A \leq_m B$ if and only if $\nat \setminus A \leq_m \nat \setminus B$ . A $\Sigma^0_n$ -complete set is not $\Pi^0_n$ as soon as some $\Sigma^0_n$ set is not $\Pi^0_n$ ; the next lesson shows that this is always the case.

1.5 Exercises

Exercise 1.8 ★.

Show that $\{ e : W_e = \emptyset \}$ is $\Pi^0_1$ , that $\{ e : |W_e| \geq 2 \}$ is $\Sigma^0_1$ , and that $\{ e : |W_e| = 2 \}$ is $\Delta^0_2$ .

Solution

$W_e = \emptyset \iff \forall x\ \forall s\ \Phi_e(x)[s]\diverge$ . Next, $|W_e| \geq 2 \iff \exists x\ \exists x'\ \exists s\ (x \neq x' \wedge \Phi_e(x)[s]\converge \wedge \Phi_e(x')[s]\converge)$ . Finally, $|W_e| = 2$ is the intersection of $|W_e| \geq 2$ , which is $\Sigma^0_1$ , and of the complement of $|W_e| \geq 3$ , which is $\Pi^0_1$ by the same argument. Both are $\Delta^0_2$ , and $\Delta^0_2$ is closed under intersection.

Exercise 1.9 ★.

Show that for each $n$ there are only countably many $\Sigma^0_n$ sets, and deduce that the $\Sigma^0_n$ sets are not closed under arbitrary countable unions.

Solution

A $\Sigma^0_n$ set is determined by a computable relation, which has an index; so there are countably many. Hence some set $A$ is not arithmetic, by Cantor. But $A = \bigcup_{x \in A} \{ x \}$ is a countable union of finite sets, which are computable, hence $\Sigma^0_n$ . The closure under existential quantification only applies to uniform unions, $\bigcup_y \{ x : (x, y) \in B \}$ with $B$ a single $\Sigma^0_n$ relation.

Exercise 1.10 ★★.

Show that $\{ e : W_e \text{ is computable} \}$ is $\Sigma^0_3$ .

Solution

Let $E(e, i, x)$ be the relation

\big(x \in W_e \wedge \exists s\ \Phi_i(x)[s]\converge = 1\big) \vee \big(x \notin W_e \wedge \exists s\ \Phi_i(x)[s]\converge = 0\big).

Then $W_e$ is computable if and only if $\exists i\ \forall x\ E(e, i, x)$ : if $\forall x\ E(e, i, x)$ , then $\Phi_i$ is total with values in $\{0, 1\}$ and computes $W_e$ ; conversely, an index of the characteristic function of $W_e$ satisfies $\forall x\ E(e, i, x)$ . The relation $E$ is a Boolean combination of $\Sigma^0_1$ relations, hence $\Delta^0_2$ and in particular $\Pi^0_2$ . So $\forall x\ E$ is $\Pi^0_2$ , and $\exists i\ \forall x\ E$ is $\Sigma^0_3$ .

1.6 Notes and references

The arithmetic hierarchy was introduced independently by Kleene (1943) and Mostowski (1947). The notation $\Sigma^0_n$ , $\Pi^0_n$ is due to Addison, by analogy with the Borel hierarchy of descriptive set theory, of which it is the effective counterpart. Rogers’ and Soare’s textbooks treat the hierarchy in detail.

S. C. Kleene, Recursive predicates and quantifiers, Transactions of the American Mathematical Society 53 (1943), 41–73.
A. Mostowski, On definable sets of positive integers, Fundamenta Mathematicae 34 (1947), 81–112.
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
R. I. Soare, Recursively Enumerable Sets and Degrees, Springer, 1987.