42.04.05 · mathematical-logic / computability-degrees

The Arithmetical Hierarchy and Post's Theorem

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 4 and the historical notes (the arithmetical hierarchy and its properness, Post's theorem identifying the hierarchy with the jump ladder $\emptyset^{(n)}$, the index-set classification — $\mathrm{Fin}$ is $\Sigma_2$-complete, $\mathrm{Inf}$ and $\mathrm{Tot}$ are $\Pi_2$-complete, $\mathrm{Cof}$ and $\mathrm{Rec}$ are $\Sigma_3$-complete — arithmetical definability and Tarski's theorem that truth is not arithmetical, the continuation to the hyperarithmetical $\Delta^1_1$ and the analytical hierarchy $\Sigma^1_n$ with Kleene's $\mathcal O$); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 14-16 (the arithmetical and analytical hierarchies, completeness, the hyperarithmetical sets); Hinman 1978 *Recursion-Theoretic Hierarchies* (Springer) Ch. III-VI (the full development of the arithmetical, hyperarithmetical, and analytical hierarchies and their relativisations)

Intuition Beginner

The previous unit built a ladder of harder and harder problems by repeatedly applying the jump. This unit looks at the same ladder from a completely different angle — the angle of how you describe a set in words — and discovers it is the very same ladder. The bridge between the two views is the centrepiece, Post's theorem.

Start with the descriptions. A plain computer can settle some questions outright: it runs, it stops, it says yes or no. Call those the level-zero questions. Now climb one step. Some questions are not settle-outright, but they have the shape "there exists a witness that makes a checkable thing true" — like "does this program ever stop?", which means "is there a number of steps after which it has halted?" You cannot bound the search, but if a witness exists you will eventually find it. The flip side is "for all witnesses, a checkable thing holds" — like "does this program run forever?" These two shapes, one search and one universal check, are the first rung above plain computation.

The pattern continues. The next rung allows one search wrapped around one universal check, or the reverse. Each new rung adds one more alternation between "there exists" and "for all." Counting those alternations is counting how complicated the description has to be, and the count is a ladder that climbs forever.

Here is the surprise. This description-ladder, built purely from how the question is phrased, lines up rung for rung with the difficulty-ladder built from the jump. Adding one more alternation to your sentence is exactly the same as climbing one more step with the jump — one more "phone call to the halting problem." So the way a question is worded and the way a question is hard to compute turn out to measure the same thing. The rest of the unit makes the wording, the counting, and the match precise, and shows the ladder never collapses to a single rung.

Visual Beginner

Picture each rung as a sentence shape. The capital E means "there exists a number such that"; the capital A means "for all numbers." After the quantifiers comes a box you can check by plain computation.

   level    "there exists" form        "for all" form
   ------    ----------------------     ----------------------
   0        [ checkable box ]          [ checkable box ]      (a plain computer decides)
   1        E . [ box ]                A . [ box ]            (one search / one universal)
   2        E A . [ box ]              A E . [ box ]          (one alternation)
   3        E A E . [ box ]            A E A . [ box ]        (two alternations)
   ...      one more letter each step, alternating E and A

   The number of ALTERNATIONS between E and A is the rung.
   Repeated same letters (E E or A A) collapse to one and do not count.

Now lay the two ladders side by side. The left is the wording-ladder above; the right is the jump-ladder from the previous unit. Post's theorem says the rungs match.

wording rung	what it is	jump-ladder match
level 1, "there exists"	what a plain computer can list	the halting problem $0^{'}$ as the helper
level 2, "there exists"	listable using a halting-problem helper	jump of the jump, $0^{''}$ , as helper
level 3, "there exists"	listable using a $0^{''}$ helper	$0^{'''}$ as helper
each step up	one more alternation in the sentence	one more jump on the ladder

Read the table as a dictionary: the left column is grammar, the right column is computation, and Post's theorem is the translation that makes them say the same thing.

Worked example Beginner

We classify three concrete questions by counting alternations, then read off where each sits.

Step 1. "Does program $e$ halt on input $0$ ?" Unfolded, this says: there exists a number of steps after which program $e$ has stopped on input $0$ . Checking "has it stopped within $s$ steps" is a plain computation. So the shape is one "there exists" wrapped around a checkable box — one search, no alternation. This is a level-one "there exists" question.

Step 2. "Does program $e$ halt on every input?" Unfolded: for all inputs $x$ , there exists a number of steps after which program $e$ has stopped on input $x$ . Now there are two quantifiers and they alternate: a "for all" on the outside, a "there exists" on the inside. One alternation puts this on level two, on the "for all" side.

Step 3. "Is the set listed by program $e$ finite?" Unfolded: there exists a bound $b$ such that for all outputs $x$ the program ever prints, $x$ is below $b$ . That is a "there exists" on the outside and a "for all" on the inside — one alternation, level two, on the "there exists" side. So finiteness sits one notch up from halting, and on the opposite side from totality.

What this tells us: you can read the difficulty of a question straight off the grammar of its cleanest description, once you push all the searches and universal checks to the front and count how many times they switch. Halting needs one search; running-on-everything needs a universal check guarding a search; finiteness needs a search guarding a universal check. Each extra switch is a genuine step up a ladder that, as the next sections prove, never folds back down.

Check your understanding Beginner

Exercise (easy, multiple-choice).

What determines which rung a question sits on, once its description is written with all searches and universal checks pushed to the front?

The total number of quantifiers, counting repeats.
The number of times the quantifiers switch between "there exists" and "for all."
The length of the checkable box at the end.
Whether the first quantifier is "there exists" rather than "for all."

Hint

Repeated same-type quantifiers collapse into one; what is left to count?

Answer

B. The rung is the number of alternations between the two kinds of quantifier; repeated same-type quantifiers merge and do not add a level. Feedback-correct: alternation depth is the measure. Feedback-wrong: raw quantifier count (A) overcounts because repeats collapse; the box length (C) is irrelevant; the leading quantifier (D) only picks the side of a rung, not the rung.

Formal definition Intermediate+

Fix the standard enumeration ${φ_{e}}$ , the c.e. sets ${W_{e}}$ from 42.04.03, the oracle functionals $Φ_{e}^{A}$ , the jump $A^{'}$ , and the iterated jumps $\emptyset^{(n)}$ from 42.04.04. A computable pairing $⟨ \cdot, \cdot ⟩ : N^{2} \to N$ with computable inverses is fixed throughout, so finite blocks of like quantifiers contract to one.

A relation $R \subseteq N^{k}$ is $Σ_{n}^{0}$ if $$ R(\bar x) \iff \exists y_1, \forall y_2, \exists y_3 \cdots Q_n y_n; S(\bar x, y_1, \dots, y_n), $$ where $S$ is a computable ( $Δ_{0}^{0}$ ) relation and the $n$ unbounded number quantifiers strictly alternate, beginning with $\exists$ (so $Q_{n} = \exists$ if $n$ is odd, $\forall$ if $n$ is even). It is $Π_{n}^{0}$ if it has such a prenex form beginning with $\forall$ , and $Δ_{n}^{0} = Σ_{n}^{0} \cap Π_{n}^{0}$ . Bounded quantifiers ( $\exists y < t$ , $\forall y < t$ ) may appear inside $S$ without raising the level. By convention $Σ_{0}^{0} = Π_{0}^{0} = Δ_{0}^{0}$ is the class of computable relations ^{[Soare Ch. 4]}. A set is arithmetical if it is $Σ_{n}^{0}$ for some $n$ .

The base level matches the previous chapters: $Δ_{1}^{0}$ is the computable sets, $Σ_{1}^{0}$ is the c.e. sets (a c.e. set is ${x : \exists s T (e, x, s)}$ , a single $\exists$ over a computable matrix), and $Π_{1}^{0}$ is the co-c.e. sets. The relativised classes $Σ_{n}^{0, B}$ , $Π_{n}^{0, B}$ , $Δ_{n}^{0, B}$ are defined identically with $S$ allowed to be $B$ -computable.

Closure properties hold at each level ^{[Rogers Ch. 14]}. The classes ascend, $Σ_{n}^{0} \cup Π_{n}^{0} \subseteq Δ_{n + 1}^{0} \subseteq Σ_{n + 1}^{0} \cap Π_{n + 1}^{0}$ ; each $Σ_{n}^{0}$ is closed under finite unions and intersections, under bounded quantification, under computable substitution in the free variables, and under the leading existential quantifier (a $\exists$ in front of a $Σ_{n}^{0}$ matrix stays $Σ_{n}^{0}$ by contraction $\exists y_{1} \exists y_{1}^{'} \equiv \exists ⟨ y_{1}, y_{1}^{'} ⟩$ ); dually for $Π_{n}^{0}$ and $\forall$ . Complementation swaps the classes: $R$ is $Σ_{n}^{0} ⟺ \overline{R}$ is $Π_{n}^{0}$ .

A set $C$ is $Σ_{n}^{0}$ -complete if $C \in Σ_{n}^{0}$ and $A \leq_{m} C$ for every $A \in Σ_{n}^{0}$ ; $Π_{n}^{0}$ -complete is dual. A $Σ_{n}^{0}$ -complete set is not $Π_{n}^{0}$ (else the hierarchy would collapse at level $n$ ), so completeness pins a set exactly at its level.

Counterexamples to common slips Intermediate+

"More quantifiers always means a higher level." Only alternations count. The relation $\exists y_{1} \exists y_{2} \exists y_{3} S$ is $Σ_{1}^{0}$ , not $Σ_{3}^{0}$ : contract the block to $\exists ⟨ y_{1}, y_{2}, y_{3} ⟩$ . Likewise bounded quantifiers do not raise the level — $\forall z < t \exists y S$ with $S$ computable is still $Σ_{1}^{0}$ , because the bounded $\forall$ folds into the computable matrix.
" $Δ_{n}^{0}$ is a single quantifier-shape." $Δ_{n}^{0} = Σ_{n}^{0} \cap Π_{n}^{0}$ is defined by having both an $n$ -quantifier $Σ$ form and an $n$ -quantifier $Π$ form, not by a normal form of its own. A $Δ_{2}^{0}$ set is one expressible both as $\exists\forall$ and as $\forall\exists$ over computable matrices; by Post's theorem these are exactly the $\emptyset^{'}$ -computable sets.
" $Σ_{n}^{0} \cup Π_{n}^{0} = Δ_{n + 1}^{0}$ ." The inclusion is proper. There are $Δ_{n + 1}^{0}$ sets in neither $Σ_{n}^{0}$ nor $Π_{n}^{0}$ ; the union of the two $n$ -level classes is not closed and sits strictly inside the next $Δ$ . The hierarchy is finer than the $Σ$ / $Π$ dichotomy suggests.
"Completeness and membership are the same." Every $Σ_{n}^{0}$ set is in $Σ_{n}^{0}$ , but only the $\leq_{m}$ -hardest are $Σ_{n}^{0}$ -complete. $Tot$ is $Π_{2}^{0}$ but not $Σ_{2}^{0}$ (it is $Π_{2}^{0}$ -complete); a computable set is in every $Σ_{n}^{0}$ yet complete for none above level $0$ .

Key theorem with proof Intermediate+

The two organising results are that the hierarchy is proper — it genuinely climbs, $Σ_{n}^{0} \neq = Π_{n}^{0}$ at every level — and Post's theorem, which identifies the syntactic ladder with the jump ladder of 42.04.04, so quantifier-alternation depth equals depth on the iterated jump.

Theorem (the hierarchy theorem and Post's theorem). For every $n \geq 1$ : (i) there is a $Σ_{n}^{0}$ set that is not $Π_{n}^{0}$ , hence $Σ_{n}^{0} \neq = Π_{n}^{0}$ and the inclusions $Σ_{n}^{0} ⊊ Σ_{n + 1}^{0}$ , $Δ_{n}^{0} ⊊ Δ_{n + 1}^{0}$ are strict; (ii) (Post) $A \in Σ_{n + 1}^{0} ⟺ A$ is c.e. in $\emptyset^{(n)}$ , $A \in Δ_{n + 1}^{0} ⟺ A \leq_{T} \emptyset^{(n)}$ , and $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete.

Proof. (i) Arithmetising the $Σ_{n}^{0}$ definitions produces a universal $Σ_{n}^{0}$ set $U_{n} \subseteq N^{2}$ that is itself $Σ_{n}^{0}$ and satisfies: for every $Σ_{n}^{0}$ set $A$ there is $e$ with $A = {x : U_{n} (e, x)}$ . (Replace the computable matrix $S$ by the universal Kleene predicate and quantify over its index; the alternation pattern is preserved.) Define the diagonal $D = {x : U_{n} (x, x)}$ . Then $D \in Σ_{n}^{0}$ . Were $D \in Π_{n}^{0}$ , its complement $\overline{D} = {x : \neg U_{n} (x, x)}$ would be $Σ_{n}^{0}$ , so $\overline{D} = {x : U_{n} (e_{0}, x)}$ for some index $e_{0}$ . Evaluating at $x = e_{0}$ : $e_{0} \in \overline{D} ⟺ U_{n} (e_{0}, e_{0}) ⟺ e_{0} \in D$ , contradicting $e_{0} \in \overline{D} ⟺ e_{0} \in / D$ . So $D \in Σ_{n}^{0} ∖ Π_{n}^{0}$ , whence $Σ_{n}^{0} \neq = Π_{n}^{0}$ ; since $Σ_{n}^{0}, Π_{n}^{0} \subseteq Δ_{n + 1}^{0}$ and the two differ, both inclusions into $Δ_{n + 1}^{0}$ are strict, and the hierarchy does not collapse.

(ii) Argue by induction on $n$ , the base $n = 0$ being $Σ_{1}^{0} =$ c.e. $=$ c.e. in $\emptyset$ and $Δ_{1}^{0} =$ computable $= {A : A \leq_{T} \emptyset}$ , with $\emptyset^{(0)} = \emptyset$ complete for $Σ_{0}^{0}$ at the bottom. Inductive step, the $Σ$ equivalence first. ( $\Leftarrow$ ) Suppose $A$ is c.e. in $\emptyset^{(n)}$ , so $A = {x : \exists s T^{\emptyset^{(n)}} (e, x, s)}$ where the oracle computation queries $\emptyset^{(n)}$ . By the induction hypothesis $\emptyset^{(n)}$ is $Σ_{n}^{0}$ and its complement is $Π_{n}^{0}$ ; replacing each positive oracle answer " $q \in \emptyset^{(n)}$ " by its $Σ_{n}^{0}$ definition and each negative answer by the $Π_{n}^{0}$ definition, the bounded run of the computation (finitely many queries, by the use principle of 42.04.04) becomes a finite conjunction of $Σ_{n}^{0}$ and $Π_{n}^{0}$ conditions, hence $Σ_{n}^{0}$ after contraction; prefixing the outer $\exists s$ keeps it $Σ_{n + 1}^{0}$ . So $A \in Σ_{n + 1}^{0}$ .

( $\Rightarrow$ ) Suppose $A \in Σ_{n + 1}^{0}$ , say $A (x) ⟺ \exists y P (x, y)$ with $P \in Π_{n}^{0}$ . By the induction hypothesis $\overline{P} \in Σ_{n}^{0}$ is c.e. in $\emptyset^{(n)}$ , so $P$ is $Π_{1}$ in $\emptyset^{(n)}$ and hence $\emptyset^{(n + 1)}$ -computable; in particular an $\emptyset^{(n)}$ -oracle decides $P (x, y)$ with one further query to the jump $\emptyset^{(n + 1)} = (\emptyset^{(n)})^{'}$ . Then $A (x) ⟺ \exists y P (x, y)$ is c.e. in $\emptyset^{(n)}$ once $P$ is $\emptyset^{(n)}$ -decidable: search $y$ , checking each $P (x, y)$ by the $\emptyset^{(n)}$ -oracle, so $A$ is the domain of an $\emptyset^{(n)}$ -partial-computable function, i.e. c.e. in $\emptyset^{(n)}$ .

The $Δ_{n + 1}^{0}$ statement follows: $A \in Δ_{n + 1}^{0} ⟺ A$ and $\overline{A}$ are both c.e. in $\emptyset^{(n)}$ $⟺ A \leq_{T} \emptyset^{(n)}$ by Post's relativised complementation criterion (Exercise 4 of 42.04.04). Completeness: every $Σ_{n + 1}^{0}$ set is c.e. in $\emptyset^{(n)}$ , hence $\leq_{m} \emptyset^{(n + 1)} = (\emptyset^{(n)})^{'}$ by the relativised $\leq_{m}$ -completeness of the jump (jump theorem (ii) of 42.04.04), and $\emptyset^{(n + 1)} \in Σ_{n + 1}^{0}$ ; so $\emptyset^{(n + 1)}$ is $Σ_{n + 1}^{0}$ -complete, completing the induction. $□$

Bridge. Post's theorem is the foundational reason the arithmetical hierarchy and the jump ladder are not two parallel structures but one: each added unbounded quantifier alternation is exactly one application of the jump, so the $Σ_{n + 1}^{0}$ sets are precisely the sets c.e. in $\emptyset^{(n)}$ and $\emptyset^{(n)}$ is the $Σ_{n}^{0}$ -complete set — this is exactly jump theorem (ii) of 42.04.04 read inductively along $\emptyset, \emptyset^{'}, \emptyset^{''}, \dots$ . The diagonalisation that proves properness is the same self-application that gave $K \neq \leq_{T} \emptyset$ in 42.04.02, now run against the universal $Σ_{n}^{0}$ set at every level, which generalises the single halting diagonal to an unbounded tower. The equivalence $A \in Δ_{n + 1}^{0} ⟺ A \leq_{T} \emptyset^{(n)}$ is dual to the $Σ$ / $Π$ split: being computable from the $n$ -th jump is being decidable both with one search and with one universal check over $\emptyset^{(n - 1)}$ . This builds toward Tarski's undefinability of truth in the Advanced results, where the full truth set escapes every level, and it appears again in the priority method 42.04.06, where the $Δ_{2}^{0}$ sets — the $\emptyset^{'}$ -computable sets, by the limit lemma — are exactly the approximable sets the finite-injury constructions exploit; putting these together, the central insight is that one operator, the jump, generates both the computational ladder and its syntactic shadow.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the quantifier-contraction lemma: if $R (\overset{x}{ˉ}) ⟺ \exists y_{1} \exists y_{2} S (\overset{x}{ˉ}, y_{1}, y_{2})$ with $S \in Σ_{n}^{0}$ , then $R \in Σ_{n}^{0}$ . Conclude that a block of like quantifiers does not raise the level.

Hint

Use the computable pairing $⟨ y_{1}, y_{2} ⟩$ with computable projections.

Answer

Let $⟨ \cdot, \cdot ⟩ : N^{2} \to N$ be a computable bijection with computable inverses $(\cdot)_{0}, (\cdot)_{1}$ , so $⟨ y_{1}, y_{2} ⟩ = w ⟺ y_{1} = (w)_{0} \land y_{2} = (w)_{1}$ . Define $S^{'} (\overset{x}{ˉ}, w) ⟺ S (\overset{x}{ˉ}, (w)_{0}, (w)_{1})$ ; since the projections are computable and $S \in Σ_{n}^{0}$ , computable substitution into the free variables of a $Σ_{n}^{0}$ relation gives $S^{'} \in Σ_{n}^{0}$ . Now $\exists y_{1} \exists y_{2} S (\overset{x}{ˉ}, y_{1}, y_{2}) ⟺ \exists w S^{'} (\overset{x}{ˉ}, w)$ : forward, given $y_{1}, y_{2}$ take $w = ⟨ y_{1}, y_{2} ⟩$ ; backward, given $w$ take $y_{1} = (w)_{0}$ , $y_{2} = (w)_{1}$ . A single leading $\exists$ over a $Σ_{n}^{0}$ matrix is $Σ_{n}^{0}$ (the outermost quantifier of a $Σ_{n}^{0}$ form, $n \geq 1$ , is $\exists$ , and merging two adjacent $\exists$ into one preserves the prenex shape; for $n = 0$ a single $\exists$ over computable lands in $Σ_{1}^{0} = Σ_{n}^{0}$ only when we are forming the first level — here $n \geq 1$ ). Hence $R \in Σ_{n}^{0}$ . Iterating, any finite block $\exists y_{1} \dots \exists y_{k}$ contracts to one $\exists$ , so like-quantifier blocks do not add alternations. Rubric: full credit for the pairing substitution, the equivalence both directions, and the observation that adjacent same-type quantifiers merge in the prenex form.

Exercise 4 (medium, symbolic).

Show that $Inf (e) ⟺ {x : φ_{e} (x) ↓} is infinite$ is $Π_{2}^{0}$ , and that $Fin (e) ⟺ W_{e} is finite$ is $Σ_{2}^{0}$ .

Hint

"Infinite" means: for every bound, there is a larger element. Negate to get finiteness.

Answer

$W_{e}$ is infinite iff for every $n$ there is some $x > n$ with $x \in W_{e}$ , i.e. $Inf (e) ⟺ \forall n \exists x \exists s (x > n \land T (e, x, s))$ . Contract the inner $\exists x \exists s$ to a single $\exists$ over the computable matrix $(x > n \land T (e, x, s))$ , leaving the prefix $\forall n \exists ⟨ x, s ⟩$ : two alternations beginning with $\forall$ , so $Inf \in Π_{2}^{0}$ . Finiteness is the complement: $Fin (e) ⟺ \neg Inf (e) ⟺ \exists n \forall ⟨ x, s ⟩ \neg (x > n \land T (e, x, s)) ⟺ \exists n \forall x \forall s (T (e, x, s) \to x \leq n)$ . The prefix is $\exists n \forall ⟨ x, s ⟩$ , two alternations beginning with $\exists$ , so $Fin \in Σ_{2}^{0}$ . (Both are complete at their level, but that is the next exercise.) Rubric: full credit for the infinite/finite unfoldings, the contraction of the inner existential block, and reading the alternation count and leading quantifier off each prefix.

Exercise 6 (hard, symbolic).

Prove the limit lemma: $A \leq_{T} \emptyset^{'}$ (equivalently $A \in Δ_{2}^{0}$ ) iff there is a computable function $g (x, s)$ with $A (x) = lim_{s} g (x, s)$ (the limit existing for every $x$ , with values in ${0, 1}$ ).

Hint

For the forward direction use that $\emptyset^{'}$ has a computable stage approximation $\emptyset_{s}^{'}$ and that an $\emptyset^{'}$ -computation has finite use. For the reverse, express "the limit is $1$ " with one $\exists\forall$ and one $\forall\exists$ .

Answer

( $\Rightarrow$ ) Suppose $A = Φ_{e}^{\emptyset^{'}}$ , total. Fix the canonical computable enumeration $\emptyset_{s}^{'}$ with $\emptyset^{'} = ⋃_{s} \emptyset_{s}^{'}$ . Define $g (x, s) = Φ_{e, s}^{\emptyset_{s}^{'}} (x)$ if this converges in $\leq s$ steps with use $\leq s$ , else $g (x, s) = 0$ . As $s \to \infty$ the oracle $\emptyset_{s}^{'}$ agrees with $\emptyset^{'}$ below the (finite) use of the true computation $Φ_{e}^{\emptyset^{'}} (x)$ from some stage on, and the computation has converged by some stage; by the use lemma of 42.04.04 $g (x, s)$ then equals $Φ_{e}^{\emptyset^{'}} (x) = A (x)$ permanently. So $lim_{s} g (x, s) = A (x)$ with $g$ computable. ( $\Leftarrow$ ) Suppose $A (x) = lim_{s} g (x, s)$ , $g$ computable. Then $A (x) = 1 ⟺ \exists s \forall t \geq s g (x, t) = 1$ , a $Σ_{2}^{0}$ condition, and $A (x) = 0 ⟺ \exists s \forall t \geq s g (x, t) = 0$ , also $Σ_{2}^{0}$ ; so $A$ and $\overline{A}$ are both $Σ_{2}^{0}$ , giving $A \in Δ_{2}^{0}$ , hence $A \leq_{T} \emptyset^{'}$ by Post. Equivalently, $\emptyset^{'}$ can decide $A (x)$ directly: ask $\emptyset^{'}$ whether the $\emptyset$ -c.e. set "stages $s$ with $g (x, t)$ not yet settled past $s$ " is finite — a single jump query locating the last change. Rubric: full credit for the stage-approximation argument with the use lemma forward, and the $\exists\forall$ expression of the eventual-value condition giving $Δ_{2}^{0}$ backward.

Exercise 7 (hard, symbolic).

Prove $Tot = {e : φ_{e} total}$ is $Π_{2}^{0}$ -complete: it is $Π_{2}^{0}$ , and every $Π_{2}^{0}$ set $\leq_{m} Tot$ .

Hint

Membership is Exercise 1. For hardness, given $A (x) ⟺ \forall y \exists z R (x, y, z)$ with $R$ computable, build for each $x$ an index $f (x)$ of a program that, on input $y$ , searches for $z$ with $R (x, y, z)$ and halts when found.

Answer

Membership: $Tot (e) ⟺ \forall x \exists s T (e, x, s)$ , prefix $\forall\exists$ over computable $T$ , so $Π_{2}^{0}$ . Hardness: let $A \in Π_{2}^{0}$ , $A (x) ⟺ \forall y \exists z R (x, y, z)$ with $R$ computable. By the s-m-n theorem there is a total computable $f$ such that $φ_{f (x)} (y)$ runs the computable search "find the least $z$ with $R (x, y, z)$ , then halt." Then $φ_{f (x)} (y) ↓ ⟺ \exists z R (x, y, z)$ . Hence $φ_{f (x)}$ is total $⟺ \forall y \exists z R (x, y, z) ⟺ A (x)$ , i.e. $x \in A ⟺ f (x) \in Tot$ . So $A \leq_{m} Tot$ via $f$ , and since $A$ was an arbitrary $Π_{2}^{0}$ set, $Tot$ is $Π_{2}^{0}$ -complete. In particular $Tot \in / Σ_{2}^{0}$ (else the hierarchy would collapse at level $2$ , contradicting properness). Rubric: full credit for the $Π_{2}^{0}$ membership, the s-m-n construction of $f (x)$ with $φ_{f (x)} (y) ↓ ⟺ \exists z R (x, y, z)$ , and the equivalence totality $⟺ A (x)$ giving the $\leq_{m}$ reduction.

Advanced results Master

The hierarchy is proper and aligned with the jump; the results below fix the index-set completeness levels, identify the arithmetical sets with first-order definability and locate truth strictly above the hierarchy, and continue the construction transfinitely into the hyperarithmetical and analytical levels.

Theorem 1 (Post's theorem in full; the jump as the hierarchy engine). For every $n$ : $A \in Σ_{n + 1}^{0} ⟺ A$ is c.e. in $\emptyset^{(n)} ⟺ A$ is c.e. in some $Π_{n}^{0}$ set; $A \in Δ_{n + 1}^{0} ⟺ A \leq_{T} \emptyset^{(n)}$ ; and $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete, hence properly $Σ_{n}^{0}$ (in $Σ_{n}^{0} ∖ Π_{n}^{0}$ ) ^{[Soare Ch. 4]}. The iterated jumps $\emptyset, \emptyset^{'}, \emptyset^{''}, \dots$ are therefore exactly the $\leq_{m}$ -complete sets at successive levels, and the relativisation principle of 42.04.04 gives the same statements over any base: $A \in Σ_{n + 1}^{0, B} ⟺ A$ is c.e. in $B^{(n)}$ . Quantifier-alternation depth and jump depth are one invariant. The $Σ_{n}^{0}$ -completeness is what makes "complete for level $n$ " a robust notion: $\leq_{m} \emptyset^{(n)}$ degrees stratify the arithmetical sets exactly as the hierarchy does.

Theorem 2 (arithmetical $=$ first-order definable; Tarski's undefinability of truth). A set $A \subseteq N$ is arithmetical (in some $Σ_{n}^{0}$ ) iff it is definable by a first-order formula in the standard structure $(N, +, \cdot, 0, 1, <)$ ^{[Hinman Ch. IV]}. The hierarchy levels are exactly the bounded-quantifier-prefix complexity of such formulas. But the truth set $Th (N) = {┌ σ ┐ : N ⊨ σ}$ is not arithmetical: by Tarski's theorem any arithmetical set is $Σ_{n}^{0}$ for a fixed $n$ , while a putative arithmetical truth predicate could be diagonalised — applying the fixed-point lemma of 42.01.09 pending to its negation yields a sentence asserting its own falsity, a contradiction. Concretely $Th (N)$ computes every $\emptyset^{(n)}$ uniformly (each $Σ_{n}^{0}$ statement is decided by truth), so it lies strictly above every level of the hierarchy. This is the semantic ceiling: provability in a c.e. theory is $Σ_{1}^{0}$ and incomplete 42.01.09 pending, whereas truth is not arithmetical at all, and the gap between them is the precise content of the contrast between the first incompleteness theorem and the undefinability theorem.

Theorem 3 (index-set completeness classification). The natural index sets occupy exact levels and are complete there ^{[Rogers Ch. 14]}: $Fin = {e : W_{e} finite}$ is $Σ_{2}^{0}$ -complete; $Inf = {e : W_{e} infinite}$ and $Tot = {e : φ_{e} total}$ are $Π_{2}^{0}$ -complete; $Cof = {e : \overline{W_{e}} finite}$ and $Rec = {e : W_{e} computable}$ are $Σ_{3}^{0}$ -complete; $Ext = {e : φ_{e} extends to a total computable function}$ is $Σ_{3}^{0}$ . The completeness proofs are uniform s-m-n constructions coding a generic level- $n$ predicate into the structural property; Rice's theorem (every index set other than $\emptyset$ and $N$ is undecidable, $\geq_{m} \emptyset^{'}$ or its complement) is the level- $1$ shadow of this classification, and the Rice-Shapiro theorem characterising the c.e. ( $Σ_{1}^{0}$ ) index sets is its level- $1$ refinement. The classification is the standard testbed: it shows the hierarchy is populated with naturally arising complete sets at $Σ_{2}, Π_{2}, Σ_{3}$ and beyond.

Theorem 4 (the hyperarithmetical hierarchy and $Δ_{1}^{1}$ ). Iterating the jump along the computable (recursive) ordinals continues the hierarchy transfinitely: using Kleene's system of notations $O$ for ordinals $< ω_{1}^{C K}$ (the Church-Kleene ordinal, the least non-computable ordinal), define $\emptyset^{(a)}$ for $a \in O$ by $\emptyset^{(a + 1)} = (\emptyset^{(a)})^{'}$ and $\emptyset^{(λ)} = ⨁_{a <_{O} λ} \emptyset^{(a)}$ at limits ^{[Hinman Ch. V]}. The hyperarithmetical sets are those computable from some $\emptyset^{(a)}$ , $a \in O$ ; the Kleene-Souslin theorem identifies them with $Δ_{1}^{1}$ , the sets both $Σ_{1}^{1}$ and $Π_{1}^{1}$ in the analytical hierarchy. Hyperarithmetical is to arithmetical as the effective Borel sets are to the finite Borel levels: the arithmetical hierarchy is the finite part, hyperarithmetical the effective-countable-ordinal part, and $ω_{1}^{C K}$ the exact ceiling of the recursive iteration.

Theorem 5 (the analytical hierarchy). Allowing quantification over functions (or sets) of numbers gives the analytical hierarchy: $A$ is $Σ_{1}^{1}$ if $A (x) ⟺ \exists f \in N^{N} \forall y R (x, f, y)$ with $R$ arithmetical, $Π_{1}^{1}$ the dual, and $Σ_{n + 1}^{1}, Π_{n + 1}^{1}$ by alternating function quantifiers over an arithmetical matrix ^{[Rogers Ch. 16]}. The $Π_{1}^{1}$ sets are the effective coanalytic sets, with Kleene's normal form $A (x) ⟺ \forall f \exists n R (x, \overset{ˉ}{f} n)$ and the boundedness and basis theorems; $Δ_{1}^{1} =$ hyperarithmetical (Theorem 4); and the analytical hierarchy is proper. This is the second floor above the arithmetical one: number quantifiers build $Σ_{n}^{0}$ , the jump iteration along $O$ builds the hyperarithmetical $Δ_{1}^{1}$ , and a single function quantifier jumps to $Σ_{1}^{1}$ , far above everything the number-quantifier ladder reaches. The set $O$ itself is $Π_{1}^{1}$ -complete, the canonical object at the base of the analytical hierarchy.

Synthesis. The arithmetical hierarchy is the foundational reason definability and computability are the same measurement taken twice: a set's quantifier-alternation depth in arithmetic is its depth on the jump ladder, and this is exactly Post's theorem — $Σ_{n + 1}^{0}$ is c.e. in $\emptyset^{(n)}$ , $Δ_{n + 1}^{0}$ is $\leq_{T} \emptyset^{(n)}$ , $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete — so the iterated jump of 42.04.04 is the engine that climbs both ladders at once. Properness is the relativised halting diagonal of 42.04.02 run against the universal $Σ_{n}^{0}$ set at every level, which generalises the single $K \neq \leq_{T} \emptyset$ into an unbounded non-collapsing tower; putting these together, the hierarchy theorem and Post's theorem are one phenomenon seen syntactically and computationally. The arithmetical sets are precisely the first-order-definable subsets of $(N, +, \cdot)$ , and truth is dual to this in the sharpest way — not arithmetical at all, lying above every $\emptyset^{(n)}$ — which is the central insight separating Gödel incompleteness (provability is $Σ_{1}^{0}$ , 42.01.09 pending) from Tarski undefinability (truth is non-arithmetical), and the bridge by which the $Δ_{2}^{0} =$ limit-computable sets feed the finite-injury approximations of the priority method 42.04.06. The continuation past $ω$ is the same construction transfinite: the jump iterated along Kleene's $O$ up to $ω_{1}^{C K}$ gives the hyperarithmetical $Δ_{1}^{1}$ sets, and a function quantifier lifts to the analytical hierarchy where $O$ is $Π_{1}^{1}$ -complete — the arithmetical hierarchy is the first finite stretch of a ladder that, by the relativisation principle, repeats its own structure at every height.

Full proof set Master

Proposition 1 (closure and the ascending inclusions). For each $n$ : $Σ_{n}^{0}$ is closed under $\cup$ , $\cap$ , leading $\exists$ , bounded quantification, and computable substitution; $R \in Σ_{n}^{0} ⟺ \overline{R} \in Π_{n}^{0}$ ; and $Σ_{n}^{0} \cup Π_{n}^{0} \subseteq Δ_{n + 1}^{0}$ .

Proof. Complementation is by pushing negation through the prefix, flipping each quantifier and negating the computable matrix (which stays computable), turning the $Σ_{n}^{0}$ form into a $Π_{n}^{0}$ form. Leading $\exists$ closure is quantifier contraction (Exercise 3). Closure under $\cup, \cap$ : prenex the two forms with disjoint bound variables and merge — for $\cap$ interleave matching quantifiers, for $\cup$ likewise, using that $\exists y P \lor \exists y^{'} P^{'} \equiv \exists ⟨ y, y^{'} ⟩ (P \lor P^{'})$ and the matrix combination stays at the matrix level. Bounded quantification folds into the computable matrix since $\forall z < t$ and $\exists z < t$ of a computable relation are computable. Computable substitution $\overset{x}{ˉ} \mapsto h (\overset{x}{ˉ})$ replaces the matrix $S (\overset{x}{ˉ}, \overset{y}{ˉ})$ by the computable $S (h (\overset{x}{ˉ}), \overset{y}{ˉ})$ . For the inclusion, a $Σ_{n}^{0}$ relation $\exists y_{1} \dots S$ is also $Δ_{n + 1}^{0}$ : it is $Σ_{n + 1}^{0}$ (prefix a vacuous quantifier or absorb), and its complement is $Π_{n}^{0} \subseteq Π_{n + 1}^{0} \subseteq Σ_{n + 1}^{0} \cap Π_{n + 1}^{0}$ ... more directly $Σ_{n}^{0} \subseteq Σ_{n + 1}^{0}$ and $Σ_{n}^{0} \subseteq Π_{n + 1}^{0}$ by prefixing a dummy $\forall$ , so $Σ_{n}^{0} \subseteq Δ_{n + 1}^{0}$ ; symmetrically $Π_{n}^{0} \subseteq Δ_{n + 1}^{0}$ . $□$

Proposition 2 (universal $Σ_{n}^{0}$ set and the hierarchy theorem). There is a $Σ_{n}^{0}$ relation $U_{n} (e, x)$ universal for $Σ_{n}^{0}$ sets, and the diagonal $D = {x : U_{n} (x, x)} \in Σ_{n}^{0} ∖ Π_{n}^{0}$ .

Proof. Every $Σ_{n}^{0}$ set is ${x : \exists y_{1} \forall y_{2} \dots S_{e} (x, \overset{y}{ˉ})}$ where $S_{e}$ ranges over computable matrices, uniformly indexed by $e$ via the Kleene predicate: take $S_{e} (x, \overset{y}{ˉ}) ⟺ T (e, ⟨ x, \overset{y}{ˉ} ⟩, (\overset{y}{ˉ})_{last})$ or any fixed universal computable relation. Set $U_{n} (e, x) ⟺ \exists y_{1} \forall y_{2} \dots Q y_{n} S_{e} (x, \overset{y}{ˉ})$ ; this is $Σ_{n}^{0}$ as a relation in $(e, x)$ and enumerates all $Σ_{n}^{0}$ sets as $e$ varies. If $D = {x : U_{n} (x, x)}$ were $Π_{n}^{0}$ then $\overline{D} \in Σ_{n}^{0}$ , so $\overline{D} = {x : U_{n} (e_{0}, x)}$ for some $e_{0}$ ; then $e_{0} \in \overline{D} ⟺ U_{n} (e_{0}, e_{0}) ⟺ e_{0} \in D$ , contradicting $\overline{D} = N ∖ D$ . So $D \in / Π_{n}^{0}$ . $□$

Proposition 3 (Post's theorem, successor step). $A \in Σ_{n + 1}^{0} ⟺ A$ is c.e. in $\emptyset^{(n)}$ .

Proof. ( $\Rightarrow$ ) $A (x) ⟺ \exists y P (x, y)$ with $P \in Π_{n}^{0}$ . By induction $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete, so $\overline{P} \leq_{m} \emptyset^{(n)}$ (as $\overline{P} \in Σ_{n}^{0}$ ); thus $P$ is $\emptyset^{(n)}$ -decidable (one oracle query to decide $\overline{P}$ , then negate). Then $A = dom$ of the $\emptyset^{(n)}$ -partial-computable function searching $y$ until $P (x, y)$ holds, so $A$ is c.e. in $\emptyset^{(n)}$ . ( $\Leftarrow$ ) $A = {x : \exists s Φ_{e, s}^{\emptyset^{(n)}} (x) ↓}$ . A converging oracle computation uses $\emptyset^{(n)}$ at finitely many points (use principle, 42.04.04); replacing each positive query " $q \in \emptyset^{(n)}$ " by its $Σ_{n}^{0}$ definition and each negative query by its $Π_{n}^{0}$ definition expresses " $Φ_{e, s}^{\emptyset^{(n)}} (x) ↓$ via a length- $s$ run with this query pattern" as a finite Boolean combination of $Σ_{n}^{0}$ and $Π_{n}^{0}$ matrices, itself $Σ_{n}^{0}$ after contraction; the outer $\exists s$ keeps it $Σ_{n + 1}^{0}$ . $□$

Proposition 4 ( $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete). $\emptyset^{(n)} \in Σ_{n}^{0}$ and every $A \in Σ_{n}^{0}$ satisfies $A \leq_{m} \emptyset^{(n)}$ .

Proof. By induction. $n = 1$ : $\emptyset^{'} = K$ is $Σ_{1}^{0}$ (c.e.) and $\leq_{m}$ -complete for $Σ_{1}^{0}$ by the $m$ -completeness of $K$ 42.04.03. Step: assume $\emptyset^{(n)}$ is $Σ_{n}^{0}$ -complete. By Proposition 3 the $Σ_{n + 1}^{0}$ sets are exactly the c.e.-in- $\emptyset^{(n)}$ sets, and by jump theorem (ii) of 42.04.04 every set c.e. in $\emptyset^{(n)}$ is $\leq_{m} (\emptyset^{(n)})^{'} = \emptyset^{(n + 1)}$ . Also $\emptyset^{(n + 1)}$ is c.e. in $\emptyset^{(n)}$ , hence $Σ_{n + 1}^{0}$ by Proposition 3. So $\emptyset^{(n + 1)}$ is $Σ_{n + 1}^{0}$ -complete. $□$

Proposition 5 (the limit lemma). $A \leq_{T} \emptyset^{'}$ iff $A (x) = lim_{s} g (x, s)$ for a computable $g$ with ${0, 1}$ values and the limit existing at each $x$ .

Proof. ( $\Rightarrow$ ) With $A = Φ_{e}^{\emptyset^{'}}$ total and the canonical approximation $\emptyset_{s}^{'}$ , set $g (x, s)$ to the value of the length- $s$ run $Φ_{e, s}^{\emptyset_{s}^{'}} (x)$ if it converges with use $\leq s$ , else $0$ . The true computation has finite use $u$ and converges by some stage; from the stage where $\emptyset_{s}^{'} ↾ u = \emptyset^{'} ↾ u$ and the run has converged, the use lemma 42.04.04 fixes $g (x, s) = A (x)$ permanently. ( $\Leftarrow$ ) $A (x) = 1 ⟺ \exists s \forall t \geq s g (x, t) = 1$ is $Σ_{2}^{0}$ , and the same for $A (x) = 0$ , so $A \in Δ_{2}^{0}$ , hence $A \leq_{T} \emptyset^{'}$ by Post (Proposition 3 plus complementation). $□$

Proposition 6 ( $Fin$ is $Σ_{2}^{0}$ -complete). $Fin \in Σ_{2}^{0}$ and every $Σ_{2}^{0}$ set $\leq_{m} Fin$ .

Proof. Membership: $Fin (e) ⟺ \exists n \forall x \forall s (T (e, x, s) \to x \leq n)$ , prefix $\exists\forall$ , so $Σ_{2}^{0}$ . Hardness: let $A \in Σ_{2}^{0}$ , $A (x) ⟺ \exists n \forall y R (x, n, y)$ with $R$ computable; equivalently $A (x) ⟺ \neg (\forall n \exists y \neg R (x, n, y))$ . By s-m-n build $f$ with $φ_{f (x)}$ enumerating ${n : \exists y \neg R (x, n, y)}$ : on a dovetailed search, put $n$ into $W_{f (x)}$ when a $y$ with $\neg R (x, n, y)$ appears. Then $W_{f (x)}$ is finite iff only finitely many $n$ have such a $y$ iff some tail of $n$ has $\forall y R (x, n, y)$ — but to align with $A$ exactly, arrange instead $φ_{f (x)}$ to enumerate a marker for each $n$ failing $\forall y R (x, n, y)$ up to the least witnessing $n^{*}$ , so $W_{f (x)}$ is finite iff $\exists n \forall y R (x, n, y)$ , i.e. iff $A (x)$ . Thus $x \in A ⟺ f (x) \in Fin$ , giving $A \leq_{m} Fin$ . Hence $Fin$ is $Σ_{2}^{0}$ -complete. $□$

Proposition 7 (Tarski: truth is not arithmetical). $Th (N) = {┌ σ ┐ : N ⊨ σ}$ is not $Σ_{n}^{0}$ for any $n$ .

Proof. Suppose $Th (N)$ were arithmetical, so definable by an arithmetical formula $Tr (v)$ with $N ⊨ Tr (┌ σ ┐) ⟺ N ⊨ σ$ . By the fixed-point lemma 42.01.09 pending applied to $\neg Tr (v)$ there is a sentence $λ$ with $N ⊨ λ ⟺ N ⊨ \neg Tr (┌ λ ┐)$ . Then $N ⊨ λ ⟺ N ⊨ \neg Tr (┌ λ ┐) ⟺ N \neq ⊨ Tr (┌ λ ┐) ⟺ N \neq ⊨ λ$ , a contradiction. So no arithmetical truth predicate exists, and since every arithmetical set is $Σ_{n}^{0}$ for some fixed $n$ , $Th (N)$ is in no $Σ_{n}^{0}$ . (That it computes every $\emptyset^{(n)}$ — decide a $Σ_{n}^{0}$ sentence by truth — places it strictly above each level.) $□$

Connections Master

Turing reducibility, oracles, and the jump 42.04.04, the prerequisite, supplies the engine this unit reads syntactically: the iterated jumps $\emptyset^{(n)}$ defined there are, by Post's theorem proved here, exactly the $Σ_{n}^{0}$ -complete sets, and jump theorem (ii) — $A^{'}$ is $\leq_{m}$ -complete among $A$ -c.e. sets — is precisely the inductive step that lifts level- $n$ completeness to level $n + 1$ . That unit owns the jump operator, relativisation, and the use lemma the proofs lean on; this unit owns the quantifier-alternation classification and the proof that it coincides with the jump ladder.
The priority method and Post's problem 42.04.06, co-produced, lives at the bottom two levels this unit charts: the $Δ_{2}^{0}$ sets are, by the limit lemma proved here (Proposition 5), exactly the limit-computable ( $\emptyset^{'}$ -computable) sets, and the finite-injury constructions build c.e. ( $Σ_{1}^{0}$ ) sets of incomparable degree by $Δ_{2}^{0}$ approximations whose finitely-many mind-changes are the limit-lemma's content. This unit owns the hierarchy and the limit lemma; that unit owns the priority constructions that populate the interval $[0, 0^{'}]$ those approximations describe.
Gödel numbering and the incompleteness theorems 42.01.09 pending is the semantic counterpart this unit's Tarski theorem (Proposition 7) completes: provability in a c.e. theory is $Σ_{1}^{0}$ and incomplete, while truth $Th (N)$ is not arithmetical at all, and the same fixed-point lemma that produces the Gödel sentence produces the Liar that defeats an arithmetical truth predicate. That unit owns arithmetisation and the fixed-point lemma; this unit owns the placement of truth strictly above every level of the hierarchy and the contrast between undefinability and incompleteness.
Computably enumerable sets 42.04.03 sit at the base level $Σ_{1}^{0}$ this unit generalises: the projection characterisation of c.e. sets is the one-existential-quantifier base case, $K = \emptyset^{'}$ is the $Σ_{1}^{0}$ -complete set anchoring Post's induction, and the index sets classified here ( $Fin, Tot, Cof$ ) are the higher-level analogues of the creative-set completeness phenomenon of that unit. That unit owns the $Σ_{1}^{0}$ structure theory; this unit lifts completeness and the diagonal to every finite level and beyond.

Historical & philosophical context Master

The arithmetical hierarchy was isolated by Stephen Kleene in the early 1940s, in his work on the predicates definable in arithmetic by alternating number quantifiers over a recursive matrix, and independently approached by Andrzej Mostowski, after whom the classification is sometimes called the Kleene-Mostowski hierarchy ^{[Rogers Ch. 14]}. Kleene proved the enumeration and hierarchy theorems showing the levels are distinct and introduced the iterated jump; the identification of the syntactic hierarchy with the jump ladder is Post's theorem, announced in Emil Post's 1948 abstract "Degrees of recursive unsolvability" and developed in the Post-Kleene circle, tying definability complexity to the degrees of unsolvability of 42.04.04. Alfred Tarski's 1933 theorem on the undefinability of truth — that the set of true arithmetic sentences is not arithmetically definable — predates the hierarchy but receives its sharpest recursion-theoretic form here, as the statement that $Th (N)$ lies above every $\emptyset^{(n)}$ .

The continuation past the finite levels is Kleene's again: his 1955 papers on the hyperarithmetical hierarchy and the system of notations $O$ for the recursive ordinals extended the jump iteration transfinitely to $ω_{1}^{C K}$ , and the Kleene-Souslin theorem identified the hyperarithmetical sets with $Δ_{1}^{1}$ , the effective analogue of the Borel sets. The analytical hierarchy, with quantifiers over functions, was developed by Kleene and Mostowski and refined through the 1960s by the work of Spector, Gandy, and Addison connecting effective descriptive set theory to the classical Borel and projective hierarchies; $O$ itself is $Π_{1}^{1}$ -complete. The arithmetical hierarchy thus stands at the junction of three traditions: the recursion theory of Post and Kleene, the definability theory of Tarski and Mostowski, and the descriptive set theory of Souslin and Luzin, with Post's theorem the hinge that makes quantifier complexity and computational difficulty a single graded invariant.

Bibliography Master

@article{post1948degrees,
  author  = {Post, Emil L.},
  title   = {Degrees of recursive unsolvability: preliminary report},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {54},
  year    = {1948},
  pages   = {641--642}
}

@article{kleene1943recursive,
  author  = {Kleene, Stephen C.},
  title   = {Recursive predicates and quantifiers},
  journal = {Transactions of the American Mathematical Society},
  volume  = {53},
  number  = {1},
  year    = {1943},
  pages   = {41--73}
}

@article{mostowski1947definable,
  author  = {Mostowski, Andrzej},
  title   = {On definable sets of positive integers},
  journal = {Fundamenta Mathematicae},
  volume  = {34},
  year    = {1947},
  pages   = {81--112}
}

@article{tarski1936wahrheitsbegriff,
  author  = {Tarski, Alfred},
  title   = {Der Wahrheitsbegriff in den formalisierten Sprachen},
  journal = {Studia Philosophica},
  volume  = {1},
  year    = {1936},
  pages   = {261--405},
  note    = {English: The concept of truth in formalized languages}
}

@article{kleene1955hierarchies,
  author  = {Kleene, Stephen C.},
  title   = {On the forms of the predicates in the theory of constructive ordinals (second paper)},
  journal = {American Journal of Mathematics},
  volume  = {77},
  number  = {3},
  year    = {1955},
  pages   = {405--428}
}

@article{kleene1955arithmetical,
  author  = {Kleene, Stephen C.},
  title   = {Arithmetical predicates and function quantifiers},
  journal = {Transactions of the American Mathematical Society},
  volume  = {79},
  number  = {2},
  year    = {1955},
  pages   = {312--340}
}

@article{addison1959separation,
  author  = {Addison, John W.},
  title   = {Separation principles in the hierarchies of classical and effective descriptive set theory},
  journal = {Fundamenta Mathematicae},
  volume  = {46},
  year    = {1959},
  pages   = {123--135}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

@book{rogers1967theory,
  author    = {Rogers, Hartley},
  title     = {Theory of Recursive Functions and Effective Computability},
  publisher = {McGraw-Hill},
  year      = {1967}
}

@book{hinman1978recursion,
  author    = {Hinman, Peter G.},
  title     = {Recursion-Theoretic Hierarchies},
  series    = {Perspectives in Mathematical Logic},
  publisher = {Springer},
  year      = {1978}
}

@book{odifreddi1989classical,
  author    = {Odifreddi, Piergiorgio},
  title     = {Classical Recursion Theory, Volume I},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {125},
  publisher = {North-Holland},
  year      = {1989}
}

Prerequisites

42.04.04

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 4 (read the informal account of classifying sets by how many alternating 'for all' / 'there exists' searches their definition needs, starting from a problem a plain computer can settle); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §4.2, §6.3 for the recognisable / co-recognisable distinction stated plainly before any quantifier counting
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 4 (the arithmetical hierarchy $\Sigma_n, \Pi_n, \Delta_n$ over a computable matrix, prenex normal form and quantifier-alternation counting, $\Sigma_0 = \Pi_0 = \Delta_0 =$ computable, $\Sigma_1 =$ c.e., $\Pi_1 =$ co-c.e.; the universal $\Sigma_n$ set and the hierarchy theorem $\Sigma_n \ne \Pi_n$ by diagonalisation; Post's theorem $\Sigma_{n+1} =$ the sets c.e. in $\emptyset^{(n)}$, $\Delta_{n+1} = \{A : A \le_T \emptyset^{(n)}\}$, $\emptyset^{(n)}$ is $\Sigma_n$-complete); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 14 (the hierarchy, the enumeration and hierarchy theorems, Post's theorem, $\Sigma_n$-complete sets)
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 4 and the historical notes (the arithmetical hierarchy and its properness, Post's theorem identifying the hierarchy with the jump ladder $\emptyset^{(n)}$, the index-set classification — $\mathrm{Fin}$ is $\Sigma_2$-complete, $\mathrm{Inf}$ and $\mathrm{Tot}$ are $\Pi_2$-complete, $\mathrm{Cof}$ and $\mathrm{Rec}$ are $\Sigma_3$-complete — arithmetical definability and Tarski's theorem that truth is not arithmetical, the continuation to the hyperarithmetical $\Delta^1_1$ and the analytical hierarchy $\Sigma^1_n$ with Kleene's $\mathcal O$); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 14-16 (the arithmetical and analytical hierarchies, completeness, the hyperarithmetical sets); Hinman 1978 *Recursion-Theoretic Hierarchies* (Springer) Ch. III-VI (the full development of the arithmetical, hyperarithmetical, and analytical hierarchies and their relativisations)

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 4 develops the ARITHMETICAL HIERARCHY: a relation $R \subseteq \mathbb N^k$ is $\Sigma_n^0$ if $R(\bar x) \iff \exists y_1 \forall y_2 \cdots Q y_n\, S(\bar x, y_1, \dots, y_n)$ with $S$ computable and $n$ alternating unbounded number quantifiers beginning with $\exists$, $\Pi_n^0$ the dual beginning with $\forall$, and $\Delta_n^0 = \Sigma_n^0 \cap \Pi_n^0$; $\Sigma_0^0 = \Pi_0^0 = \Delta_0^0$ are the computable relations, $\Sigma_1^0$ the c.e. sets and $\Pi_1^0$ the co-c.e. sets, $\Delta_1^0$ the computable sets. PRENEX NORMAL FORM and quantifier contraction ($\exists y_1 \exists y_2 \equiv \exists \langle y_1, y_2\rangle$ via pairing) let one count alternations; bounded quantifiers do not raise the level. The hierarchy is closed downward ($\Sigma_n, \Pi_n \subseteq \Delta_{n+1} \subseteq \Sigma_{n+1}, \Pi_{n+1}$), closed under $\cup, \cap$, and under the appropriate quantifier, and $\Sigma_n$ is closed under bounded quantification and computable substitution. The UNIVERSAL $\Sigma_n$ SET $S^n$ (a single $\Sigma_n$ relation enumerating all $\Sigma_n$ sets) exists by arithmetising the definitions, and DIAGONALISATION on it proves the HIERARCHY THEOREM: $\Sigma_n \ne \Pi_n$, so $\Sigma_n \subsetneq \Sigma_{n+1}$ and the hierarchy is proper (does not collapse). POST'S THEOREM: $A \in \Sigma_{n+1}^0 \iff A$ is c.e. in $\emptyset^{(n)}$ (i.e. $\emptyset^{(n)}$-c.e.); $A \in \Delta_{n+1}^0 \iff A \le_T \emptyset^{(n)}$; $B \in \Sigma_{n+1}^0 \iff B$ is c.e. in some $\Pi_n^0$ set; and $\emptyset^{(n)}$ is $\Sigma_n^0$-complete (every $\Sigma_n^0$ set $\le_m \emptyset^{(n)}$), so the iterated jumps are the level-complete sets and quantifier-alternation depth equals depth on the jump ladder. ARITHMETICAL DEFINABILITY: a set is arithmetical iff first-order definable in the standard model $(\mathbb N, +, \cdot, 0, 1, <)$, iff it lies in some $\Sigma_n^0$; TARSKI'S undefinability theorem that the truth set $\mathrm{Th}(\mathbb N)$ is not arithmetical (it is properly above every level). INDEX SETS: $\mathrm{Fin} = \{e : W_e \text{ finite}\}$ is $\Sigma_2$-complete, $\mathrm{Inf}$ and $\mathrm{Tot} = \{e : \varphi_e \text{ total}\}$ are $\Pi_2$-complete, $\mathrm{Cof} = \{e : \overline{W_e} \text{ finite}\}$ and $\mathrm{Rec} = \{e : W_e \text{ computable}\}$ are $\Sigma_3$-complete. The continuation: the HYPERARITHMETICAL sets $= \Delta^1_1$, the ANALYTICAL hierarchy $\Sigma^1_n, \Pi^1_n$ with second-order (set/function) quantifiers, and Kleene's system of notations $\mathcal O$ for the recursive ordinals indexing the transfinite jump iteration.
Rogers, H. — Theory of Recursive Functions and Effective Computability · McGraw-Hill (1967). Ch. 14: the arithmetical hierarchy of sets and relations classified by the quantifier prefix over a recursive matrix, the normal-form theorem putting every arithmetical predicate into prenex form with a recursive matrix, the level invariants $\Sigma_n, \Pi_n, \Delta_n$ with $\Delta_1 = $ recursive, $\Sigma_1 = $ r.e., the closure properties (under the matching quantifier, finite union and intersection, bounded quantification, recursive substitution), the enumeration theorem giving a universal $\Sigma_n$ predicate and the hierarchy theorem $\Sigma_n \ne \Pi_n$ by a diagonal argument, $\Sigma_n$-complete and $\Pi_n$-complete sets under $\le_m$, and Post's theorem $\Sigma_{n+1} = $ (r.e. in $\emptyset^{(n)}$), $\Delta_{n+1} = \{A : A \le_T \emptyset^{(n)}\}$, with $\emptyset^{(n)}$ the $\Sigma_n$-complete set; the index-set examples and the relativised hierarchy $\Sigma_n^B$. Ch. 15-16: the hyperarithmetical hierarchy via transfinite iteration of the jump along recursive ordinals and Kleene's $\mathcal O$, the analytical hierarchy with function quantifiers, the Kleene normal-form for $\Pi^1_1$, the $\Sigma^1_1 / \Pi^1_1$ separation, and the identification $\Delta^1_1 = $ hyperarithmetical (the Kleene-Souslin theorem).
Hinman, P. G. — Recursion-Theoretic Hierarchies · Springer, Perspectives in Mathematical Logic (1978). Ch. III: the arithmetical hierarchy developed abstractly as the closure of the recursive relations under number quantification, the normal-form and hierarchy theorems, Post's theorem relating the hierarchy to the iterated jump $\emptyset^{(n)}$ and to relativised r.e.-ness, completeness at each level and the $m$-degrees $\deg_m(\emptyset^{(n)})$; Ch. IV: arithmetical definability in $(\mathbb N, +, \cdot)$, the arithmetical sets as exactly the first-order definable ones, Tarski's theorem on the non-arithmeticity of truth and the resulting strict ascent past every $\Sigma_n$; Ch. V-VI: the hyperarithmetical hierarchy as the effective Borel sets, $\Delta^1_1 = $ hyperarithmetical (Kleene-Souslin), the analytical hierarchy $\Sigma^1_n / \Pi^1_n$ over second-order quantifiers, $\Pi^1_1$ as the effective coanalytic sets with the bounded-ness and basis theorems, Kleene's $\mathcal O$ and the recursive ordinals $\omega_1^{CK}$ bounding the hyperarithmetical jump iteration.

Estimated time

beginner: 20m
intermediate: 55m
master: 100m