[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
"equational."
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