[FOM] A formalism for Ultrafinitism
Andrew Boucher
Helene.Boucher at wanadoo.fr
Tue May 25 00:59:13 EDT 2004
Recall the first-order system of Bill Taylor (Thu May 20). Call it W.
It might be preferable to have the exponential (and sequential,
additive, and multiplicative) operators possibly partial rather than
continually having to put the condition "x = Sx" in the axioms and many
theorems e.g. the Cancellation Laws.
The main drawback that I see of using FOL is that the existence of
sequences is not assured in W. In SOL big letters provide sequences
automatically , but in FOL they are provided by mechanisms such as the
Chinese Remainder Theorem, where a sequence of numbers n1,n2,....,nk
are coded by a much bigger number n. The existence of n, of course,
cannot be proven in W (knowing the existence of n1,n2,...,nk).
Without sequences it seems dubious that W can state and prove versions
of the Euclidean Algorithm or the Fundamental Theorem of Arithmetic
(existence and uniqueness of prime factorization). Propositions which
depend on them may thus be out of reach of W.
Indeed without sequences W does not even seem to have access to
recursion and e.g. is unable to define the exponentiation relationship
from addition and multiplication. Perhaps W just assumes
exponentiation as primitive? Or is there something else going on here
which I am misconstruing?
Finally, consider the following proposition:
(X) if a prime p divides xy, then p divides x or p divides y.
This is typically proven as follows. Suppose p does not divide x.
Then (we are working in the natural numbers, not the integers):
(Y) there exist s,t such that 1 = sp - xt.
Then y = spy - xty. Since p divides both terms on the RHS, it divides
y.
However (Y) cannot be provable in W, because sp might equal the top
number.
In SOL the proof can be repaired by appealing directly to the Euclidean
Algorithm or by using recursion, but these avenues may again not be
open in W.
So it would be interesting to would be to see whether one can prove (X)
in W and, if so, what the proof looks like.
I do agree with Bill's assessment that these approaches, by W or in
SOL, are more "honest" approaches to ultrafinitism.
More information about the FOM
mailing list