So I was intrigued by the following articles by Edward Nelson, via Quomodocumque:
The belief that exponentiation, superexponentiation, and so forth, applied to numerals yield numerals is just that—a belief.
Completed versus Incomplete Infinities in Arithmetic is more rigorously mathematical but dives right into the issue at hand.
A completely un-rigorous summary of the argument is that mathematicians are fooling themselves by treating the natural numbers as a "completed" infinity--- i.e., a real object. Mathematical logic typically assumes that numbers are formed via a counting process. You could view them as unary strings, or as the sets 0={}, 1={0}, 2={1}, etc. But, do all mathematical operations produce numbers that are really "countable"? This seems an odd assertion to make (without recourse to Platonism) because we can easily specify mathematical operations that produce integers to which we cannot (in a very real sense!) count. Heck, I feel the same way about the real numbers.
Nelson's result (which relies on some heavy mathematical logic and is not actually included in the above papers) is to adjoin the traditional axioms of number theory with the notion of "countable" (and later "additionable", "multiplicable", and "exponentiable."). Then you can show that the operations of addition and multiplication are closed on counting numbers. But, the same is not true of exponentiation--- or, rather, it is not possible to prove that this is true. The Platonist assumption is that it is true.
The theorem is summarized as:
There does not exist a property p for which it is possible to prove that if p(x) then x is a counting number, and that if p(x) and p(z) then p(x^z).
(There must be some additional characterization of "property" to make this theorem true because otherwise it is falsified with the trivial property p(x) <=> x == 1.)
He quotes a further result of interest to computer science: "a function is a polynomial-time function if and only if it is constructed by predicative recursion", that is, if all recursions are over counting numbers only.
