8
$\begingroup$

I know that a similar question has been asked regarding finitism, but I'm interested in ultafinitism. That is, we define a set of numbers that has a specific upper limit. For argument's sake - let's say there are only 2 numbers: 0 and 1. So 1+1 is undefined because there is no number 2...

Does Gödel incompleteness theorem hold for these numbers? What about if the upper limit is higher - 100 or a googol?

So the question then is twofold - first, would an arithmetic limited to a sufficiently small subset of natural numbers be complete. And second, if so how high can we make that limit before it becomes incomplete?

$\endgroup$
  • 3
    $\begingroup$ I think the negative reception to this question is somewhat excessive, and have upvoted to compensate. $\endgroup$ – Noah Schweber Feb 21 at 17:07
  • 3
    $\begingroup$ I don't think that a specific upper limit is the right way to think about ultrafinitism. All ultrafinitists believe in two, because everybody can count that high; it's a googol that they doubt, because nobody can count that high. Still, ultrafinitists generally accept that, whenever $n$ exists, so does $n+1$. (In theory, you can prove that a googol exists using only this axiom, step by step. But in practice, this proof has about a googol steps, and you're not physically capable of producing it.) $\endgroup$ – Toby Bartels Feb 22 at 2:42
10
$\begingroup$

I'm not really sure what you're asking. Certainly for any natural number $n$, the structure $\mathbb{N}_n$ consisting of the natural numbers up to $n$ (with $+$ and $\cdot$ interpreted relationally in order to be a legitimate structure) is trivially decidable, so in that sense Godel doesn't apply to it(s theory).

But there's a huge issue here: checking whether a sentence of length $<n$ is true in $\mathbb{N}_n$ requires more than $n$ steps in general. So the decidability of $\mathbb{N}_n$ is not satisfying from an ultrafinitist standpoint, since the completeness itself isn't "justifiable within $\mathbb{N}_n$." Meanwhile, the non-ultrafinitist won't be impressed either since $\mathbb{N}_n$ is too limited a structure to treat even basic arithmetic. So this dodge doesn't seem satisfying from any perspective.


It's worth noting that Godel's second incompleteness theorem can be avoided non-trivially with a trick of arguably ultrafinitist spirit: there are theories which interpret a decent amount of arithmetic but which prove their own consistency, and a key component of such theories is that they do not prove that multiplication is total, so in a weak sense have ultrafinitistic flavor. These were first studied by Dan Willard; see here.

However, Godel's first incompleteness theorem still applies to these. Indeed, no theory which can prove each true quantifier-free sentence about $\mathbb{N}$ and, for each $k\in\mathbb{N}$, can prove $$Init_k:\quad\forall x(\underline{k}<x\vee\bigvee_{0\le i\le k}x=\underline{i})$$ (where "$\underline{m}$" denotes the numeral corresponding to $m$) is going to be complete, consistent, and computably axiomatizable (see e.g this paper of Ritter). Note that such theories are not required to prove that multiplication is total, or that $<$ is a linear ordering of the universe, or so on: they are truly quite weak.

$\endgroup$
  • $\begingroup$ The way out of Godel is second-order logic. $\endgroup$ – Joshua Feb 22 at 3:06
  • $\begingroup$ @Joshua Except second-order logic is far from usable (it's not even set-theoretically absolute). Going to second-order logic is in fact less workable than shifting to a non-computably-axiomatizable first-order theory. So it's not a "way out" in any remotely meaningful sense. $\endgroup$ – Noah Schweber Feb 22 at 3:13
  • $\begingroup$ On the other hand, General Relativity + Quantum Mechanics is not in first order. $\endgroup$ – Joshua Feb 24 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.