The Arithmetic Hierarchy and Computability

In this post you’ll learn about a deep connection between sentences of first order arithmetic and degrees of uncomputability. You’ll learn how to look at a logical sentence and determine the degree of uncomputability of the set of numbers that it defines. And you’ll learn much of the content of and intuitive justification for Post’s theorem, which is perhaps the most important result in computability theory.

The arithmetic hierarchy is a classification system for sets of natural numbers. It relates sentences of Peano arithmetic to degrees of uncomputability. There’s a level of the hierarchy for each natural number, and on each level there are three classes: Σ_n, Π_n, and Δ_n. Where on the hierarchy a set of naturals lies indicates the complexity of the formulas that define it. Here’s how that works:

Σ₀ = Π₀ = Δ₀

On the zeroth level are all the sets that are definable by a sentence in the language of first-order Peano arithmetic that has no unbounded quantifiers. Examples:

x = 0
(x = 0) ∨ (x = 3) ∨ (x = 200)
∃y < 200 (x = y)
∀y < x ∀z < y (y⋅z = x → z = 1)
∃y < x (x = y + y)

The first two examples have no quantifiers at all. The first, x = 0, is true of exactly one natural number (namely, 0), so the set that it defines is just {0}. The second is true of three natural numbers (0, 3, and 200), so the set it defines is {0, 3, 200}. Thus both {0} and {0, 3, 200} are on the zeroth level of the hierarchy. It should be clear that just by stringing together a long enough disjunction of sentences, we can define any finite set of natural numbers. So every finite set of natural numbers is on the zeroth level of the hierarchy.

The third example has a quantifier in it, but it’s a bounded quantifier. In that sentence, y only ranges over 200 different natural numbers. In some sense, this sentence could be expanded out and written as a long disjunction of the form (x = 0) ∨ (x = 1) ∨ … ∨ (x = 199). It should be easy to see that the set this defines is {0, 1, 2, … 199}.

The fourth example is a little more interesting, for two reasons. First of all, the quantifiers are now bound by variables, not numbers. This is okay, because no matter what value of x we’re looking at, we’re only checking finitely many values of y, and for each value of y, we only check finitely many values of z. Secondly, this formula can be translated as “x is a prime number.” This tells us that the set of primes {2, 3, 5, 7, 11, …} is on the zeroth level of the hierarchy, our first infinite set!

The fifth example also gives us an infinite set; work out which set this is for yourself before moving on!

Notice that each of the sets we’ve discussed so far can be decided by a Turing machine. For each set on the zeroth level, the defining sentence can be written without any quantifiers, involving just the basic arithmetic operations of Peano arithmetic (+, ⋅, and <), each of which is computable. So for instance, we can write an algorithm that decides prime membership for x by looking at the sentence defining the set of primes:

∀y < x ∀z < y (y⋅z = x → z = 1)

for y in range(x):
    for z in range(y):
        if (y⋅z == x) and (z != 1):
            return False
return True

Another example:

(x = 0) ∨ (x = 3) ∨ (x = 200)

if (x = 0) or (x = 3) or (x = 200):
    return True
else:
    return False

Every sentence with only bounded quantifiers can be converted in a similar way to an algorithm that decides membership in the set it defines. We just translate bounded quantifiers as for loops! Thus every set on the zeroth level is decidable. It turns out that every decidable set is also on the zeroth level. We can run the process backwards and, given an algorithm deciding membership in the set, convert it into a sentence of first-order Peano arithmetic with only bounded quantifiers.

On the zeroth level, the three classes Σ₀, Π₀, and Δ₀ are all equal. So every decidable set can be said to be in each of Σ₀, Π₀, and Δ₀. The reason for the three different names will become clear when we move on to the next level of the hierarchy.

Σ₁, Π₁, Δ₁

Entering into the first level, we’re now allowed to use unbounded quantifiers in our definitions of the set. But not just any pattern of unbounded quantifiers, they must all be the same type of quantifier, and must all appear as a block at the beginning of the sentence. For Σ₁ sets, the quantifiers up front must all be existential. For example:

∃y (y² + y + 1 = x)
∃y ∃z (y is prime ∧ z is prime ∧ x = y + z ∧ x is even)

The first defines the infinite set {1, 3, 7, 13, 21, 31, …}, and the second defines the set of all even numbers that can be written as the sum of two primes (whether this includes every even number is unknown!). The shorthand I’ve used in the second sentence is permitted, because we know from the previous section that the sentences “x is prime” and “x is even” can be written without unbounded quantifiers.

It so happens that each of these sets can also be defined by formulas on the zeroth level as well. One easy way to see how is that we can just bound each quantifier by x and everything is fine. But are there any Σ₁ sets that aren’t also Σ₀?

Yes, there are! Every decidable set is in Σ₀, so these examples won’t be as simple. To write them out, I’ll have to use some shorthand that I haven’t really justified:

∃y (the Turing machine encoded by x halts in y steps)
∃x (y Gödel-codes a proof from PA of the sentence Gödel-coded by x)

Both of these rely on the notion of numbers encoding other objects. In the first we encode Turing machines as numbers, and in the second we encode sentences of Peano arithmetic as numbers using Gödel numbering. In general, any finite object whatsoever can be encoded as a natural number, and properties of that object can be discussed as properties of numbers.

Let’s take a close look at the first sentence. The set defined by this sentence is the set of numbers that encode Turing machines that halt. (For readability, in the future I’ll just say “the set of Turing machines such that …” rather than “the set of natural numbers that encode Turing machines with the property …”.) This set is undecidable, by the standard proof of the undecidability of the halting problem. This tells us that the set cannot be defined without any quantifiers!

The second sentence defines the set of natural numbers that encode theorems of PA. Why is this set not decidable? Suppose that it were. Then we could ask “is 0=1 a theorem of PA?” and, assuming the consistency of PA, after a finite amount of time get back the answer “No.” This would allow us to prove the consistency of PA, and crucially, the Turing machine that we use to decide this set could be coded as a number and used by PA to prove the same thing! Then PA would prove its own consistency, making it inconsistent and contradicting our assumption. On the other hand, if PA is inconsistent, then this set actually is decidable, because everything is provable from the axioms of PA and the set of all sentences can be decided! So this is only a good example of “Σ₁ but not Σ₀” if you have faith in the consistency of PA.

The Σ₀ sets were the decidable sets, so what are the Σ₁ sets? They are the recursively enumerable sets (also called semi-decidable). These are the sets for which an algorithm exists that takes in an input N and returns True if N is in the set, and runs forever otherwise. And just like before, we can use the sentences of PA to construct such an algorithm! Let’s look at the first example:

∃y (y² + y + 1 = x)

y = 0
while True:
    if y**2 + y + 1 == x:
        return True
    y += 1

For each unbounded quantifier, we introduce a variable and a while loop that each step increases its value by 1. This program runs until it finds a “yes” answer, and if no such answer exists, it runs forever.

Another example:

∃y (the Turing machine encoded by x halts in y steps)

y = 0
while True:
    if TM(x) halts in y steps:
        return True
    y += 1

I made up some notation here on the fly; TM(x) is a function that when fed a natural number returns the Turing machine it encodes. So what this program does is run TM(x) for increasing lengths of time, returning True if TM(x) ever halts. If TM(x) never halts, then the program runs forever. So this program semi-decides the halting problem.

Moving on to Π₁ sets! Σ₁ sets were those defined by sentences that started with a block of existential quantifiers, and Π₁ sets are defined by sentences that start with a block of unbounded universal quantifiers. For example:

∀y ∀z (x = y⋅z → (y = 1 ∨ x = 1))
∀y > x ∃z < y (x⋅z = y)

The first example is hopefully clear enough. It defines the set of prime numbers in a similar way to before. The second is meant to be slightly deceiving. That first quantifier might look bounded, until you notice that the variable it supposedly binds ranges over infinitely many values. On the other hand, the second quantifier is genuinely bounded, as for any given y it only ranges over finitely many values. See if you can identify the set it defines.

Both of these sets are in fact also in Σ₀. Like with Σ₁ sets, it’s difficult to find simple examples of Π₁ sets that aren’t also Σ₀. Here’s a cheap example:

∀y (the Turing machine encoded by x doesn’t halt in y steps)

This defines the set of non-halting Turing machines. If we were to translate this into a program, it would look something like:

y = 0
while True:
    if TM(x) halts in y steps:
        return False
    y += 1

The difference between this and the earlier example is that this program can only successfully determine that natural numbers aren’t in the set, not that they are in the set. So we can only decide the “no” cases rather than the “yes” cases. Sets like this are called co-recursively enumerable.

So far we have that Σ₀ = Π₀ = Δ₀ = {decidable sets of naturals}, Σ₁ = {recursively enumerable sets of naturals}, and Π₁ = {co-recursively enumerable sets of naturals}. To finish off level one of the hierarchy, we need to discuss Δ₁.

A set is Δ₁ if it is both Σ₁ and Π₁. It can be defined by either type of sentence. In other words, if it is both recursively enumerable (can decide the True instances) and co-recursively enumerable (can decide the False instances). Thus a set is Δ₁ if and only if it’s decidable! So every Δ₁ set is also a Δ₀ set.

A diagram might help at this point to see what we’ve learned:

Σ₂, Π₂, Δ₂

We now enter the second level of the hierarchy. Having exhausted the recursively enumerable, co-RE, and decidable sets, we know that the new sets we encounter can no longer be semi-decided by any algorithms. We’ve thus entered a new realm of uncomputability.

A set is Σ₂ if it can be defined by a sentence with a block of ∃s, then a block of ∀s, and finally a Σ₀ sentence (free of unbounded quantifiers. Start with some simple examples:

∃y ∀z (y⋅z < x)
∃y ∃z ∀w ∀u ((y⋅w < x) ∨ ((z + u) > x))

As with any examples you can write as simply as that, the sets these define are also Σ₀. So what about sentences that define genuinely new sets that we haven’t seen before? Here’s one:

∃y ∀z (TM(x) doesn’t halt on input y after z steps)

This defines the set of Turing machines that compute partial functions (i.e. functions that run forever on some inputs).

Something funny happens when you start trying to translate this sentence into a program. We can start by translating the existential quantifier up front:

y = 0
while True:
    if ∀z (TM(x) doesn't halt on input y after z steps):
        return True
    y += 1

Now let’s see what it would look like to expand the universal quantifier:

z = 0
while True:
    if TM(x) halts on input y after z steps:
        return False
    z += 1

There’s a problem here. The first program only halts if the second one returns True. But the second one never returns “True”; it’s Π₁, co-recursively enumerable! We’ve mixed a recursively enumerable program with a co-recursively enumerable one, and as a result the program we wrote never halts on any input!

This is what happens when we go above the first level of the hierarchy. We’ve entered the realm of true uncomputability.

On the other hand, suppose that we had access to an oracle for the halting problem. In other words, suppose that we are allowed to make use of a function Halts(M, i) that decides for any Turing machine M and any input i, whether M halts on i. Now we could write the following program:

y = 0
while True:
    if not Halts(TM(x), i):
        return True
    y += 1

And just like that, we have a working program! Well, not quite. This program halts so long as its input x is actually in the set of numbers that encode TMs that compute partial functions. If x isn’t in that set, then the program runs forever. This is the equivalent of recursive enumerability, but for programs with access to an oracle for the halting problem!

This is what characterizes Σ₂ sets: they are recursively enumerable using a Turing machine with an oracle for the halting problem.

Perhaps predictably, Π₂ sets are those that are co-recursively enumerable using a Turing machine with an oracle for the halting problem. Equivalently, these are sets that are definable with a sentence that has a block of ∀s, then a block of ∃s, and finally a Σ₀ sentence. An example of such a set is the set of Turing machines that compute total functions. Another is the set of Busy Beaver numbers.

And just like on level one of the hierarchy, the Δ₂ sets are those that are both Σ₂ and Π₂. Such sets are both recursively enumerable and co-recursively enumerable with the help of an oracle for the halting problem. In other words, they are decidable using an oracle for the halting problem. (Notice that again, Δ₂ sets are “easier to decide” than Σ₂ and Π₂ sets.)

The Busy Beaver numbers are an example of a Δ₂ set. After all, if one had access to an oracle for the halting problem, they could compute the value of the nth Busy Beaver number. Simply list out all the n-state Turing machines, use your oracle to see which halt, and run all of those that do. Once they’ve all stopped, record the number of steps taken by the longest-running. With the ability to compute the nth Busy Beaver number, we do the following:

n = 1
while True:
    if x == BB(n):
        return True
    n += 1

This returns True for all inputs that are Busy Beaver numbers, but runs forever on those that aren’t. We can fix this with bounded quantifiers: since the Busy Beaver numbers are a strictly increasing sequence, once we’ve reached an n such that x < BB(n), we can return False. This gives us an algorithm that decides the set of Busy Beaver numbers!

In fact, the Busy Beaver numbers are even better than Δ₂; they’re Π₁, co-recursively enumerable! But that’s a tale for another time.

Σ_n, Π_n, Δ_n

Perhaps you’re now beginning to see the pattern.

Σ₃ sets are those that can be defined by a sentence that has a block of ∃s, then a block of ∀s, then a block of ∃s, and finally a Σ₀ sentence. We could more concisely say that Σ₃ sets are those that can be defined by a sentence that has a block of ∃s and then a Π₂ sentence.

Π₃ sets are those definable by a sentence that starts with a block of ∀s, then alternates twice between groups of quantifiers before ending in a sentence with only bound quantifiers.

And Δ₃ sets are those that are Σ₃ and Π₃. If you’ve picked up the pattern, you might guess that the Δ₃ sets are exactly those that are decidable with an oracle for the halting problem for Turing machines that have an oracle for the halting problem. The Σ₃ sets are those that are recursively enumerable with such an oracle, and the Π₃ sets are co-RE with the oracle.

And so on for every natural number.

Σ_n sets are definable by a sentence that looks like ∃x₁ ∃x₂ … ∃x_k φ(x, x₁, x₂, …, x_k), where φ is Π_n-1.
Π_n sets are definable by a sentence that looks like ∀x₁ ∀x₂ … ∀x_k φ(x, x₁, x₂, …, x_k), where φ is Σ_n-1.
And Δ_n sets are both Σ_n and Π_n.

At each level of the hierarchy, we introduce new oracle Turing machines with more powerful oracles. We’ll call the Turing machines encountered on the nth level TMⁿs.

Σ_n sets are recursively enumerable with an oracle for the halting problem for TMⁿs.
Π_n sets are co-recursively enumerable with an oracle for the halting problem for TMⁿs.
Δ_n sets are decidable with an oracle for the halting problem for TMⁿs.

One might reasonably wonder if at some stage we exhaust all the sets of natural numbers. Or do we keep finding higher and higher levels of uncomputability?

Yes, we do! For each n, Σ_n is a proper subset of Σ_n+1 and Π_n is a proper subset of Π_n+1. One easy argument to see why this must be the case is that there are an uncountable infinity of sets of naturals, and only countably many sets of naturals in each level of the hierarchy. (This is because each level of the hierarchy is equivalent to the sets that are computable/recursively enumerable/co-RE using a TM with a particular oracle, and each TM only computes countably many things.)

This tells us that the hierarchy doesn’t collapse at any finite stage. Each step up, we find new sets that are even harder to decide than all those we’ve encountered so far. But (and now prepare yourself for some wildness) we can make the same cardinality argument about the finite stages of the hierarchy to tell us that even these don’t exhaust all the sets. There are only countably many finite stages of the hierarchy, and each stage contains only countably many sets of naturals!

What this means is that even if we combined all the finite stages of the hierarchy to form one massive set of sets of naturals decidable with any number of oracles for halting problems for earlier levels, we would still have not made a dent in the set of all sets of naturals. To break free of the arithmetic hierarchy and talk about these even more uncomputable levels, we need to move on to talk about the set of Turing degrees, the structure of which is incredibly complex and beautiful.