Proving $\Sigma_1$ Completeness of Peano Arithmetic

Question

Can we prove that PA is $\Sigma_1$-complete with PA, or do we need to use a stronger theory like ZFC?

In either case, what does the proof look like? What stops ZFC from being $\Sigma_1$-complete?

Answer 1

First let me describe, roughly, what $\Sigma_1$ means for PA and for ZFC.

It's provable, just from basic predicate logic, that any formula in a first-order theory is equivalent to one with all the quantifiers out front, followed by a quantifier-free part sometimes called the matrix. The quantifiers in front are called the prefix; the whole thing is called prenex normal form. For example: $$\forall x\exists y\forall z\forall u\;\varphi(x,y,z,u)$$ This is an example of an $\forall\exists\forall$ formula: a block of $\forall$'s, followed by a block of $\exists$'s, followed by a block of $\forall$'s. The number of alternations from one type of quantifier to another type turns out to be what really matters.

Example in PA: "There are an infinite number of primes", an $\forall\exists\forall$ formula: $$\forall n\exists p\forall d\forall e(p>n\wedge(de=p\Rightarrow(d=p\vee e=p)))$$ Now, those last two quantifiers are interesting from a computational point of view: we could have restricted $d$ and $e$ to be less or equal to $p$. So in terms of checking the statement, they are "finitely checkable". In the study of PA, logicians have recognized this and introduced something similar to prenex normal form: the matrix need not be quantifier free, but is allowed to have bounded quantifiers, like $\forall d\leq p$. A formula with only bounded quantifiers is said to be $\Delta_0$.

$\Sigma_n$ form, for PA, is something that starts with a block of existential quantifiers, and continues with $n-1$ more alternating blocks, followed by a $\Delta_0$ matrix. For $\Pi_n$, we start with a block of universal quantifiers. So "there exists infinitely many primes", or (for that matter), "there exists infinitely many prime pairs", are both $\Pi_2$ statements.

(By the way, these examples show that not being $\Sigma_1$ tells you nothing about whether something is provable in PA. We have of course Euclid's proof of the infinity of primes. The status of the prime pair conjecture is up in the air. It might be provable in PA, unprovable in PA but provable in ZF, and likewise for its negation. If it were undecidable in ZF, then its truth-value becomes a bit of a philosophical question. I suspect almost all mathematicians regard this last possibility as highly unlikely, but I don't know anyway to rule it out.)

Ok, switch to ZF. Same idea with the prefixes. But "bounded" is now given a different meaning. A bounded quantifier is something of the form $\exists x\in y$, or $\forall x\in y$. A $\Sigma_1$ formula consists of a block of existential quantifiers, followed by a matrix containing only bounded quantifiers and logical connectives and = and $\in$ symbols.

This ZF-boundedness is somewhat like PA-boundedness, in this sense: an unbounded quantifier ranges over the whole universe, which is all sets (or $V$) for ZF, but just all numbers (or $\mathbb{N}$) for PA.

ZF-boundedness does not entail finite checkability, unlike PA-boundedness. Example: the formula for "$x$ is uncountable" in ZF would be $$\forall f(f:\omega\to x\Rightarrow \exists y\in x\forall n\in\omega(f(n)\neq y))$$ This uses various defined terms, like $\omega$ and the function notations $f:\omega\to x$ and $f(n)$. Ignoring that, it looks like a $\Pi_1$ formula. You can take my word for it, in fact it is.

But now take a look at the part $\exists y\in x\forall n\in\omega(f(n)\neq y))$. This is not finitely checkable. Indeed, before you can even consider how you'd check this, you'd face difficult questions about how $x$ is described, in general.

In a specific case you might have a fairly concrete description of $x$, say "all subsets of $\omega$". But even with a concrete description of a specific $f$, looking at all $y\in x$, and for each of these checking that none of the $n\in\omega$ satisfies $f(n)=y$, is a "doubly infinite" task, so to speak.

So we have nothing like $\Sigma_1$ completeness for ZF. The notions nevertheless are roughly analogous. Indeed, there are $\Sigma_n/\Pi_n$ hierarchies in other branches of mathematics, sharing some but not all features with the PA and ZF uses.

You'll find a lot more on the PA hierarchy here (and a little bit about some of the others).

---

Oh, yes, your original question: can we prove that PA is $\Sigma_1$ complete in PA?

The answer is yes. The proof is usually done by, as one says, "vigorous handwaving". Basic idea: any finite combinatorial reasoning (or "elementary school arithmetic") can be formalized inside PA. If a $\Sigma_1$ sentence in PA is true in $\mathbb{N}$, then we just need to mechanically verify the $\Delta_0$ matrix for the "witness", that is, an $n$ for which the matrix holds.

This then boils down to looking at $\Delta_0$ formulas. You can prove things about them by "induction on complexity", that is, how they're built up using the logical connectives and the bounded quantifiers from atomic formulas. Even for the atomic formulas you have to do an induction on the complexity of the terms appearing in it. Of course you have to get into the nitty-gritty of the actual PA axioms. (You'll find a couple of choices for them here.)

Altogether a rather tedious exercise. I confess I've never gone through it in detail. But I have no doubt that I could, if (and only if) I absolutely had to.