hendrik at topoi.pooq.com
Tue Feb 10 10:25:42 EST 2009
On Tue, Feb 10, 2009 at 05:36:00PM +0200, Alex Blum wrote:
> Jean Paul Van Bendegem presents a putative counterexample to a
> generalization of mathematical induction. He writes, in part:
> "(a) I can write down the numeral 0 (or 1, does not matter),
> (b) for all n, if I can write down n, I can write down n+1 (or the
> successor of n),
> hence, by mathematical induction,
> (c) I can write down all numerals."
> The properties of numbers in mathematical induction hold of numbers
> irrespective of how they are named. Since a number may be named in a
> notation which could never be completed, (b), even if true, need not
> be true, and thus the predicate 'I can write down the numeral' is
> inappropiate for mathematical induction.
In fact, there are well-known notation systems for numbers
(lambda-expressions for Church numerals, for example) which have
short names for unimaginably huge numbers, but have only unimaginably
huge notations for many much smaller numbers. "In principle", of
course, they could all be written down.
I suspect that Jean-Paul van Bendegem did not have such a notation in
mind, although it probably does satisfy the premisses of his
argument. But the huge swaths of numbers with only unimaginably large
notations do provide a formal analogue to the difference between what we
can imagine doing and what we can in fact do, which seems to be the
motivation behind ultrafinitism.
These huge swaths of infeasibility would seem to be are analogous to the
huge swaths of ordinals without notations at all in the more aggressive
ordinal notation systems.
More information about the FOM