[FOM] Remedial mathematics?

Vaughan Pratt pratt at cs.stanford.edu
Wed May 25 02:52:25 EDT 2011

On 5/23/2011 8:57 AM, Timothy Y. Chow wrote:
> In not so many words, the
> lecturer or textbook writer for such a course is *proving the consistency
> of the axioms for a commutative ring*, and doing so by saying that the
> concrete example of Z satisfies all the axioms.  Notably, the *existence
> of Z is taken for granted*.

This part of your argument is not so convincing because you're comparing 
peanuts and pineapples.

1.  Commutative rings is an equational theory (abelian monoids in Ab), 
whereas PA is an elementary theory: "elementary" is a big step up from 

2.  Equational theories merely express term equivalence (and that of 
commutative rings is particularly simple), whereas PA expresses sets in 
the arithmetical hierarchy.

3.  Induction is not a single axiom but a scheme with an axiom for each 
elementary predicate in the language of PA.  Commutative rings in 
contrast is finitely axiomatized.

These three differences make PA a much more complex setup than 
commutative rings.

> Now let us consider PA, the axioms of first-order arithmetic.  Since it
> is standard mathematical practice to assume the existence of Z, and a
> fortiori the existence of N, the only question is whether N satisfies the
> axioms of PA.  The only axiom that could possibly create an issue is the
> induction axiom.  But it is clear that a first-order formula defines a
> precise property of N, on which we can of course perform induction.

Much better.  From a naive set theoretic standpoint the "properties of 
N" form the power set of N (or of N^k when there are k free variables in 
the formula at hand).  The meaning of a formula in prenex normal form is 
obtained by starting from the predicate defined by the matrix and 
alternately complementing and projecting out dimensions as you work up 
the stack of quantifiers.  It is an article of faith of naive set theory 
that the results of these operations are well-defined, ostensibly 
justifying your claim that "a first-order formula defines a precise 
property of N."

But what does all this naïveté rest on?

1.  We know from Skolem, Goedel, Cohen, etc. that this supposed 
precision is in mathematical actuality an illusion: all attempts to 
axiomatize set theory beyond finite sets are necessarily imprecise.

2.  Naive set theory (at least in the sense of Halmos's 1970 book of 
that title) is essentially based on Z, so you're proving Con(PA) from 
Con(Z).  Not as bad as proving it from Con(ZF), but still circular or worse.

3.  There's nothing finitistic or combinatorial about the power set of 
N, which has the cardinality of the continuum.

Gentzen's proof of Con(PA) suffers from none of these shortcomings.

1.  We can in principle explicitly exhibit every formula produced in the 
course of his procedure, with no question as to its mathematical identity.

2.  We do not assume Con(Z) or even Con(PA), only PRA (or even just 
elementary arithmetic) and ε_0 (and I have yet to understand Bill Tait's 
claim that the validity of induction up to epsilon_0 requires all of PA).

3.  Gentzen's normalization procedure always terminates so there is 
nothing infinite about what happens to the formulas in the argument.

And for those uncomfortable with all this metamathematics we have the 
collection of 16 undisputed mathematical facts Harvey just mentioned, 
the benefit of which is to reduce the proof of Con(PA) to ordinary 
mathematics (and put logicians out of a job?).

> In my view, skeptics of the consistency of PA should first of all explain
> why they are dissatisfied with the trivial proof [...]
> Some skeptics, like Nelson, of course have an answer---they don't believe
> in N.

That's a straw man argument.  A better answer is that closer examination 
reveals the supposedly trivial proof to have nontrivial support, thereby 
rendering it suspect.

Vaughan Pratt

More information about the FOM mailing list