[FOM] Query for Martin Davis. was:truth and consistency

[Robin Adams]

On Mon, 2 Jun 2003, Vladimir Sazonov wrote:

> I ABSOLUTELY do not understand what does it mean and by which
> way it is possible to assert what was cited above. For me, just
> vice versa, N is rather vague concept. Only by fixing things
> in the form of a formalism like PA (or some sufficiently formal
> simple rules of reasoning on natural numbers like those which we
> studied at school) we are coming to a sufficiently solid
> ground which is a basis for our illusions that we have some
> "crystal-clear" N.

Suppose I propose the following formalism.  Define the formal system N as
follows.

The set of terms is defined thus:

1) 0 is a term.
2) If t is a term, then t+1 is a term.

and the usual rubric about the set of terms being the smallest set closed
under these two clauses.

The definition of this system is simpler than the definition of PA; in
fact, N is a subsytem of PA.  If you accept PA as clearly defined, N must
be just as clear, if not more so.

Now, we can start to define syntactic operations on the terms of N.  We
can define addition and multiplication as operations on these terms.  I
could just write down the recursive definitions, and I think I would be
entitled to do so; but, to stress the syntactic nature of the operations,
I'm going to write them like this.  Let t and u be any terms of N.

1) t + u is defined to be the result of substituting t for the sole
occurrence of 0 in u.
2) t * u is defined to be the result of substituting t for each occurrence
of 1 in u, then removing every instance of `+0' in the result.

These definitions are not more problematic than the definitions we make
when reasoning about systems such as PA.

Now, we can start to study the metatheory of this system.  We can make
definitions like:

A term t is prime if t is not 0+1, and the only terms u_1, u_2 such that t
is identical with u_1 * u_2 are u_1 = 0+1, u_2 = t or vice versa.

prove results such as:

For every term t other than 0 and 0+1, there is a sequence of prime terms
t_1, ..., t_n such that t = t_1 * ... * t_n.

and ask questions such as:

Do there exist terms t, u_1, u_2, u_3 such that 0+1+1 is a subterm of t
and (u_1 ^ t) + (u_2 ^ t) = (u_3 ^ t).

(Alright, I can't write a definition of exponentiation in the style I did
addition and multiplication; I would have to just write the recursive
definition.  But I see no reason I should not be allowed to do so if I can
define (say) the relativisation of a formula to a predicate in PA.)

The point I am (at length) making is N is no more problematic as PA; or,
equivalently, formal systems such as PA are just as abstract as the set N.
(PA has infinitely many variables, infinitely many axioms, its formulas
are unbounded in length, etc.; is it really that concrete?)  And the forms
of reasoning in number theory are no more problematic than those used in
studying PA; or, contrapositively, the forms of reasoning used in the
metatheory of formal systems are just as abstract as those of number
theory.

If you accept PA as a well-defined object, I have given you an object that
must be just as well-defined; and I don't think anyone would protest too
much if I called it the standard model for the natural numbers.

I'd like to end with a specific challenge.  You seem to accept the reality
of PA, but you have said that there is a sense in which you do not accept
the reality of 10^10^10^10.  Consider the following formula:

x_1 = x_1 & x_2 = x_2 & ... & x_(10^10^10^10) = x_(10^10^10^10)

where x_1, x_2, ..., x_(10^10^10^10) are distinct variables.  I claim that
this is a formula of PA, and is provable in PA.  Do you agree.  If so,
what is its length?  And what is the length of its proof?

If you cannot answer these questions, how does this square with your
belief in the reality of PA?  If you can, how do you reconcile this with
your problems with the existence of 10^10^10^10.

--
Robin Adams