[FOM] Concerning Ultrafinitism.

[Rupert McCallum]

Have you read Edward Nelson's book "Predicative Arithmetic"? If you
read the details of when he regards induction as justifiable and when
he doesn't, you might get a better idea of where he's coming from.

Actually, Edward Nelson is a formalist, he even regards the consistency
of Robinson Arithmetic as an open problem. But let's pretend that the
theory he develops in "Predicative Arithmetic" embodies his stance. An
example of a sentence which this theory can't prove is one which might
be paraphrased as "exponentiation is total". Nelson gives a way of
interpreting a theory of finite sets in his theory, using a scheme of
coding which doesn't appeal to the totality of any function except just
a shade beyond polynomial. Then the theorem that says exponentiation is
total can be stated as: For every a and b, there exists a function f
defined on {0,...,b} such that f(0)=1 and f(i+1)=a.f(i). This theorem
cannot be proved because in Nelson's theory induction is only allowed
for formulas where the quantifiers are "bounded" using functions which
are either polynomial or slightly beyond, and in this context that
cannot be done, the code for the function grows too fast.

His justification for this stance is discussed in the opening chapter
called "The impredicativity of induction". Take a model M for Robinson
Arithmetic. Take an inductive formula phi. Then Nelson shows that we
can construct a formula phi', such that, if M' is the set of x in M
satisfying phi', then M' is a model for Robinson Arithmetic as well,
and every x in M' satisfies phi in the original model M. Now, if we can
also prove that every x in M' satisfies phi in M', then we can
interpret Q+"(Ax)phi(x)" in Q. Nelson regards induction as justified in
such an instance, since assuming induction in this case gives us a
theory which can be interpreted in Q. But when we cannot prove this, we
cannot give a syntactic proof that Q+"(Ax)phi(x)" can be interpreted in
Q. We can give a semantic proof that there is a submodel of our
original model which satisfies Q+"(Ax)phi(x)" as follows. Let M' be the
submodel of M consisting of all x which satisfy phi' in M, then let M''
be the submodel of M' consisting of all x which satisfy phi' in M', and
keep on going in this way, and take the intersection of all these
models. This might be thought to justify induction in general. But this
involves impredicative second-order reasoning, which Nelson rejects.
All the theories Nelson works with can be interpreted in Q.

So, Nelson rejects the idea that we have a clear understanding of the
distinction between the finite and the infinite. Every time we apply a
new instance of the principle of induction, we refine our understanding
of what a number is. We cannot assume that the natural number system is
given as something fixed once and for all. So we cannot justify
induction in general.


 
__________________________________________________________________________________________
Check out the New Yahoo! Mail - Fire up a more powerful email and get things done faster. 
(http://advision.webevents.yahoo.com/mailbeta)