Last time I defined ∃* _{n}* and ∀

*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}*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:

- ∃
and ∀_{n}means_{n}*n*alternating quantifier blocks, starting with ∃ or ∀. - ∃
_{0}=∀_{0}means quantifier-free for formulas (model theory); Σ_{0}=Π_{0}=Δ_{0}means recursive for relations on ℕ (recursion theory); Σ_{0}=Π_{0}=Δ_{0}means only bounded quantifiers (Peano Arithmetic). - Σ
means an ∃_{n}prefix applied to a Δ_{n}_{0}relation/formula; likewise for Πand ∀_{n}. And Δ_{n}means both Σ_{n}and Π_{n}._{n} - To classify a function
*f*, look at its graph, the relation*f*(*x*)=*y*. - Σ
(PA) means PA-provably equivalent to a Σ_{n}formula, likewise for Π_{n}(PA)._{n} - A relation on
*N*is Σ(_{n}*N*) if it can be defined by a Σformula, likewise Π_{n}(_{n}*N*). - By convention, Σ
_{n}_{+1}contains both Σand Π_{n}, likewise Π_{n}_{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. Δ_{0}=Δ_{1} 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}*, 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 ∀*

_{n}*x*(

*x*≠0 → ∃

*y*(

*y*+1=

*x*)) is ∀

_{2}(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 ∃

*formula. Then we say it’s ∃*

_{n}*(*

_{n}*T*). Likewise for ∀

*, and if*

_{n}*T*has a notion of bounded quantifiers, for Σ

*and Π*

_{n}*. My statement above that “Δ*

_{n}*means both Σ*

_{n}*and Π*

_{n}*” really should read, “Δ*

_{n}*(*

_{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 ∀*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 Σ_{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 Σ* _{n}*/Π

*classification is, in fact, a true hierarchy, both in recursion theory and PA model theory: for any*

_{n}*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 Σ

*(PA) and Π*

_{n}*(PA) formulas.*

_{n}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*<*z*∃*y*δ(*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 ∃*m*∀*x*<*z*∃*y*<*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 *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 ∃_{1} formulas are *persistent* (or *absolute*) *upwards*, and ∀_{1} 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 ∃_{1} formula, and dually for persistent downwards. (Equivalent means provably equivalent in *T*.)

You can axiomatize the theory Group using *only* ∀_{1} 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 ∀_{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 *A*_{1} ⊆ *A*_{2} ⊆ … 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.