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

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 ∀.
• 0=∀0 means quantifier-free for formulas (model theory); Σ000 means recursive for relations on ℕ (recursion theory); Σ000 means only bounded quantifiers (Peano Arithmetic).
• Σn means an ∃n prefix applied to a Δ0 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 Σ1 formula of L(PA), and a relation on ℕ is recursive iff it can be defined by a Δ1(PA) formula. Ditto for functions.

You may have noticed an incompatibility: Δ0(ℕ) means “bounded-quantifiers” in PA model land, but means “recursive” according to recursion theory. Δ01 in recursion theory, but not in PA model theory. Ah, history! To avoid confusion, I’ll always use Δ0 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 ∀2 (or ∀∃) because it is logically equivalent to ∀xy(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 ℕ. Σ1(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 Π2(PA) statement: it has the form ∀np>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 Σ1 sentence that is true for ℕ can be proven in PA. People call this the “Σ1-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 Π1 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 Π1 sentence that’s not Σ1(PA). The Σnn 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  Δ1(PA) formulas with recursive predicates is a boon to handwaving. For example, I claimed above that “∃n(odd-perfect(n))” is Σ1(PA). Is “odd-perfect(n)” Δ0? I don’t know! Determining if a predicate is Δ0 can involve cleverness and (sometimes) tricky number theory. But it’s obviously computable, i.e., recursive, therefore Δ1(PA). Sticking an existential quantifier in front of a Δ1(PA) predicate gives a Σ1(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<zyδ(x,y), where z is a free variable and δ(x,y) is Δ0. 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 ∃mx<zy<mδ(x,y) is also true. That’s a Σ1 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 aA and φ(x) is a formula of T, then A⊧φ(a) if and only if B⊧φ(a); likewise for multiple elements, say $\vec{a}=(a_1,\ldots,a_n)$. (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 $A\models\exists x\varphi(\vec{a},x)$, then $B\models\exists x\varphi(\vec{a},x)$, with A, B, and $\vec{a}$ as before. Dually, if $B\models\forall x\varphi(\vec{a},x)$, then $A\models\forall x\varphi(\vec{a},x)$. People say that ∃1 formulas are persistent (or absolute) upwards, and ∀1 formulas are persistent downwards. Example: if aA 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 ∃1 formula, and dually for persistent downwards. (Equivalent means provably equivalent in T.)

You can axiomatize the theory Group using only1 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 ∀xy(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 ∀1 formulas iff substructures are always submodels.

Next level up: what about theories that can be axiomatized entirely with ∀2 sentences? The Chang-Łoś-Suzko theorem says that this is equivalent to persistence under unions of chains: if A1A2 ⊆ … is an ascending chain of models of T, then the union ⋃An 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.