I know there's something called "ultrafinitism" which is a very radical form of constructivism that I've heard said means people don't believe that really large integers actually exist. Could someone make this a little bit more precise? Are there good reasons for taking this point of view? Can you actually get math done from that perspective?
What is "ultrafinitism" and why do people believe it?
-
0Hm... does induction only work up to the amount of things I can prove before the death of the universe? =P – 2017-12-28
3 Answers
Ultrafinitism is basically resource-bounded constructivism: proofs have constructive content, and what you get out of these constructions isn't much more than you put in.
Looking at the universal and existential quantifier should help clarify things. Constructively, a universally quantified sentence means that if I am given a parameter, I can construct something that satisfies the quantified predicate. Ultrafinitistically, the thing you give back won't be much bigger: typically there will be a polynomial bound on the size of what you get back.
For existentially quantified statements, the constructive content is a pair of the value of the parameter, and the construction that satisfies the predicate. Here the resource is the size of the proof: the size of the parameter and construction will be related to the size of the proof of the existential.
Typically, addition and multiplication are total functions, but exponentiation is not. Self-verifying theories are more extreme: addition is total in the strongest of these theories, but multiplication cannot be. So the resource bound is linear for these theories, not polynomial.
A foundational problem with ultrafinitism is that there aren't nice ultrafinitist logics that support an attractive formulae-as-types correspondence in the way that intuitionistic logic does. This makes ultrafinitism a less comfy kind of constructivism than intuitionism.
Why do people believe it? For the same kinds of reasons people believe in constructivism: they want mathematical claims to be backed up by something they can regard as concrete. Just as an intuitionist might be bothered by the idea of cutting a ball into non-measurable pieces and putting them back together into two balls, so too an ultrafinitist might be concerned about the idea that towers of exponentials are meaningful ways of constructing numbers. Wittgenstein argued this point in his "Lectures on the Foundations of Mathematics".
Can you actually get math done from that perspective? Yes. If intuitionism is the mathematics of the computable, ultrafinitism is the mathematics of the feasibly computable. But the difference in ease of working with between ultrafinitism and intuitionism is much bigger than that between intuitionism and classical mathematics.
-
0@LIE: Indeed. I shall $f$ix the text. – 2011-02-09
The philosophy is explained in Doron Zeilberger's article. Basically, it's the belief that there is a largest natural number!
I've heard a funny story (on Scott Aaronson's blog) about someone who was an ultrafinitist.
-Do you believe in 1?
-Yes, he responded immediately
-Do you believe in 2?
-Yes, he responded after a brief pause
-Do you believe in 3? -Yes, he responded after a slightly longer pause -Do you believe in 4? -Yes, after several seconds
It soon become clear that he would take twice as long to answer the next question as the previous one. (I believe Alexander Esesin-Volpin was the person.)
-
2However, in a representation that lets us stack exponentials, you can make vastly larger numbers but the complexity is no longer monotonically related to the magnitude. So while there is still a "largest" number, it's less relevant. Instead, the natural numbers in that representation have a fractal structure with huge gaps of numbers too complex to represent that are nowhere near the "largest" number. For example, $2^{2^{2^{2^{1000}}}}$ is compactly represented, but there are huge swathes of numbers between it and $2^{2^{2^{2^{999}}}}$ that can't physically be represented in this way. (2/2) – 2017-12-18
Greg Egan has some fun with this idea in one of his best short stories, "Luminous" (published in the collection of the same name). A pair of researchers are exploring an apparent "defect" in mathematics:
"You still don't get it, do you, Bruno? You're still thinking like a Platonist. The universe has only been around for fifteen billion years. It hasn't had time to create infinities. The far side can't go on forever-because somewhere beyond the defect, there are theorems that don't belong to any system. Theorems that have never been touched, never been tested, never been rendered true or false."
Terrific stuff!
-
0@Tommy: To be fair the text does say "It hasn't had *time* to create infinities". Even if it started spatially infinite, no theorems at all might have been "tested" across that space initially. Not sure it's worth prodding too much at the cosmology of a scifi short story though. – 2018-09-17