Topics in Nonstandard Arithmetic 3: The Arithmetic Hierarchy (Part 2)

Prev TOC Next

Last time I defined ∃_n and ∀_n prefixes and formulas; Σ_n, Π_n , and Δ_n relations (and functions) on ℕ; Σ_n(PA), Π_n(PA), and Δ_n(PA) formulas in L(PA); and Σ_n(N), Π_n(N), and Δ_n(N) relations (and functions) on a model N of PA. I won’t repeat all that, but a few bullet points may help load it into working memory:

• ∃_n and ∀_n means n alternating quantifier blocks, starting with ∃ or ∀.
• ∃₀=∀₀ means quantifier-free for formulas (model theory); Σ₀=Π₀=Δ₀ means recursive for relations on ℕ (recursion theory); Σ₀=Π₀=Δ₀ means only bounded quantifiers (Peano Arithmetic).
• Σ_n means an ∃_n prefix applied to a Δ₀ relation/formula; likewise for Π_n and ∀_n. And Δ_n means both Σ_n and Π_n.
• To classify a function f, look at its graph, the relation f(x)=y.
• Σ_n(PA) means PA-provably equivalent to a Σ_n formula, likewise for Π_n(PA).
• A relation on N is Σ_n(N) if it can be defined by a Σ_n formula, likewise Π_n(N).
• By convention, Σ_n+1 contains both Σ_n and Π_n, likewise Π_n+1. (Thus Σ_n∪Π_n ⊆ Δ_n+1.)

All this by definition. A non-trivial theorem says that:

A relation on ℕ is recursively enumerable (r.e.) iff it can be defined by a Σ₁ formula of L(PA), and a relation on ℕ is recursive iff it can be defined by a Δ₁(PA) formula. Ditto for functions.

You may have noticed an incompatibility: Δ₀(ℕ) means “bounded-quantifiers” in PA model land, but means “recursive” according to recursion theory. Δ₀=Δ₁ in recursion theory, but not in PA model theory. Ah, history! To avoid confusion, I’ll always use Δ₀ in the model theory sense.

I should be more explicit about the meaning of ∃_n, ∀_n, Σ_n, Π_n, and Δ_n for formulas. Narrowly construed, these demand that the formula be in prenex normal form. It’s more convenient to carry these classifications over to logically equivalent formulas. For example, we say that ∀x(x≠0 → ∃y(y+1=x)) is ∀₂ (or ∀∃) because it is logically equivalent to ∀x∃y(x≠0→y+1=x). Building on this idea, suppose we have a theory T, and a formula is T-provably equivalent to an ∃_n formula. Then we say it’s ∃_n(T). Likewise for ∀_n, and if T has a notion of bounded quantifiers, for Σ_n and Π_n. My statement above that “Δ_n means both Σ_n and Π_n” really should read, “Δ_n(T) means both Σ_n(T) and Π_n(T)”.

I’d like next to cultivate some intuition for these concepts. For starters, let’s look at statements about ℕ. Σ₁(PA) statements are positively decidable. Example: “there exists an odd perfect number”. In other words, ∃n(odd-perfect(n)). If there is an odd perfect number, then (in principle) we can prove it with a computation. If there isn’t, we might never know. In contrast, “there are infinitely many prime pairs” is a Π₂(PA) statement: it has the form ∀n∃p>n(is-prime(p)∧is-prime(p+2)). It could be true or false without us ever knowing for sure. (By the way, ∃p>n is not a bounded quantifier.)

I said, “prove with a computation”; as it happens, this is equivalent to “prove in PA”. Another non-obvious theorem! But I hope plausible. Any Σ₁ sentence that is true for ℕ can be proven in PA. People call this the “Σ₁-completeness of PA”. (Kaye proves this, or actually something stronger, on p.25.)

Of course, maybe someday someone will prove that there are no odd perfect numbers, or that there are infinitely many prime pairs. Gödel’s 2nd incompleteness theorem furnishes an example of a Π₁ sentence that we know PA cannot prove, even though it’s true: Con(PA). (If you suspect that PA is inconsistent, make that “know” and “true” with scare-quotes. I think an inconsistent PA is a little scary!) This has the form ∀p(p does not prove 1=0). So that’s a Π₁ sentence that’s not Σ₁(PA). The Σ_n/Π_n classification is, in fact, a true hierarchy, both in recursion theory and PA model theory: for any n>0, there are relations on ℕ that are in Σ_n but not in Π_n, with their negations in Π_n but not in  Σ_n. Likewise for Σ_n(PA) and Π_n(PA) formulas.

The theorem equating  Δ₁(PA) formulas with recursive predicates is a boon to handwaving. For example, I claimed above that “∃n(odd-perfect(n))” is Σ₁(PA). Is “odd-perfect(n)” Δ₀? I don’t know! Determining if a predicate is Δ₀ can involve cleverness and (sometimes) tricky number theory. But it’s obviously computable, i.e., recursive, therefore Δ₁(PA). Sticking an existential quantifier in front of a Δ₁(PA) predicate gives a Σ₁(PA) predicate, clearly.

Generalizing that last observation: prepending an ∃x to a Σ_n(PA) predicate gives a Σ_n(PA) predicate, likewise prepending a ∀x to a Π_n(PA) predicate. On the other hand, an ∃x in front of a Π_n(PA) predicate, or a ∀x in front of a Π_n(PA) predicate, ups the level by 1. (In general.) However: prepending a bounded quantifier to a Σ_n(PA) or Π_n(PA) predicate preserves the level, regardless of whether it’s ∃x or ∀x. Obvious? Maybe not. Here’s a simple example, over ℕ. Consider ∀x<z∃yδ(x,y), where z is a free variable and δ(x,y) is Δ₀. Suppose it’s true for some particular z. We go through the x’s less than z, picking a y for each; there has to be an m greater than all those y’s. So ∃m∀x<z∃y<mδ(x,y) is also true. That’s a Σ₁ formula! And conversely, if that formula is true, then the original formula is true.

Let’s turn to model theory in general. Suppose A and B are models of a theory T, and suppose that A is a submodel of B. (Say, a subgroup of a group.) Quantifier-free predicates have a nice property: they are absolute between A and B. That means that if a∈A and φ(x) is a formula of T, then A⊧φ(a) if and only if B⊧φ(a); likewise for multiple elements, say . (This fact is very nearly the definition of ‘submodel’.) Example: a and b commute in the subgroup A iff they commute in the group B.

Next level: if , then , with A, B, and as before. Dually, if , then . People say that ∃₁ formulas are persistent (or absolute) upwards, and ∀₁ formulas are persistent downwards. Example: if a∈A is in the center of B, i.e., B⊧∀x(ax=xa), then a is in the center of A.

A lovely theorem gives converses: a formula of a theory T is persistent upwards if and only if it is equivalent to an ∃₁ formula, and dually for persistent downwards. (Equivalent means provably equivalent in T.)

You can axiomatize the theory Group using only ∀₁ sentences: use a binary function symbol ·, a constant 1, and a unary function symbol ^–1. (The theory Group isn’t what a algebraist means by “the theory of groups”—it’s the first-order theory whose models are groups.) In that case, substructures are automatically submodels: if A is a subset of B containing the unit element and products and inverses, then it’s a subgroup. On the other hand, you could drop the function symbol for inverse, replacing it with an ∀∃ axiom ∀x∃y(x·y =1). In this case, a substructure can be a monoid and not a subgroup. General result: a first-order theory has an equivalent axiomatization (in the same language) with only ∀₁ formulas iff substructures are always submodels.

Next level up: what about theories that can be axiomatized entirely with ∀₂ sentences? The Chang-Łoś-Suzko theorem says that this is equivalent to persistence under unions of chains: if A₁ ⊆ A₂ ⊆ … is an ascending chain of models of T, then the union ⋃A_n is also a model of T. (True for most algebraic theories.) You can sense the DNA this shares with the ∀∃ “infinitely often” prefix!

Enough for this post, I think, but there’s still more to be said. However, the next Topics post will take a break from this topic.

Prev TOC Next