[FOM] Infinity and the "Noble Lie"

[Harvey Friedman]

On 1/7/06 4:32 PM, "joeshipman at aol.com" <joeshipman at aol.com> wrote:

> Raatikainen:
> 
> I wonder whether everyone here is using the notion of "an axiom of
> infinity" in the same sense.
> 
> I reply:
> 
> I am using THE "Axiom of Infinity" in the specific formal system ZFC.
> 
> It is possible to express, and prove, the Paris-Harrington Theorem in
> many other formal systems, but any such proof will, I contend, at some
> point invoke an axiom which cannot be justified without reference to
> actually infinite sets, or structures of other types whose domain is
> necessarily infinite.
> 

The situation is deeper and more delicate than is indicated above.

PH = Paris/Harrington variant of the finite Ramsey theorem. It is Pi02.
PA = Peano Arithmetic.

PH can be proved in a system S very much like PA, where it can be argued
that the axiom of infinity does not appear in S in the same sense that the
axiom of infinity does not appear in PA.

Specifically, PA consists of

1. Axioms for successor.
2. Definitions of functions defined by primitive recursion. These functions
are used only as function symbols, and not as objects. So there are no
infinite objects treated in PA. We can also restrict ourselves to the two
particular primitive recursions for addition and multiplication.
3. Induction for all formulas in the language.

S consists of 

1. Axioms for successor.
2. Definitions of functions defined by recursion using formulas in the
language. These functions are used only as function symbols, and not as
objects. So there are no infinite objects treated in PA. We can also
restrict ourselves to a single (complicated) such recursion involving only
one quantifier. 
3. Induction for all formulas in the language.

PH is provable in S but not in PA.

On an entirely different note, there are many alternatives to PH that have
the exact same metamathematical properties, and are preferable from some
points of view. (In particular, they avoid the uncharacteristic double use
of a positive integer as an element and as a size). I published some in 1998
Annals of Mathematics, in the introductory material, but have developed some
more over the years (as well as a few other people). At some point, I will
try to make a comprehensive post on this topic.

Harvey Friedman