[FOM] High Complexity without Infinity

Dmytro Taranovsky dmytro at MIT.EDU
Sun Jan 1 13:11:11 EST 2006

A long-standing question is what properties of numbers are definable
without using an actual infinity.  The conventional answers are the
recursive properties, or the arithmetic properties, or a mild iteration
of arithmetic properties.  As I found, however, even Pi-1-1 complete
properties can be defined without invoking an actual infinity.  

We do this through a new finite primitive, that of a sufficiently fast
growing sufficiently long finite sequence of natural numbers.
Sufficiently long is with respect to the rate of growth.  We eliminate
vagueness in the above by using particular sequences in computations
(with the first element larger than the input size) rather than the
predicate for such sequences.  Every sufficient sequence will lead to
the same results for the computations, so the results are
well-defined--as is Pi-1-1 truth, which can be computed in this way.

Details are in my paper,

Comments, questions, and readability suggestions are welcome.

The strongest extension described there reaches Sigma-1-2 truth.
However, it is unclear whether the given "finitistic" description of
Sigma-1-2 truth is too vague but for existence of an infinity-using
equivalent.  Fortunately, the weaker extensions are more secure.

Happy New Year to everyone!

Dmytro Taranovsky

More information about the FOM mailing list