5

What are the axioms for ultrafinitary number theory? I have in the mind the school of thought that there is a largest number -- the width of the known universe as a multiple of the diameter of a hydrogen atom, or something like that.

I have been playing around with finite chains of elements with a beginning and an end, and trying to come up with something the equivalent of induction.

EDIT:

Brainstorming discussion at my thread, "The axioms for ultrafinitist number theory?" at the sci.math and sci.logic newsgroups.

See my tentative suggestions in my Follow-up below.

Dan Christensen
  • 14,529
  • And then it starts back at zero? – Michael Greinecker Mar 17 '14 at 21:26
  • You could simply negate the axiom of infinity. You could also say that there is a number without a successor. – Christopher King Mar 17 '14 at 21:26
  • 1
    I think the functions "successor", "plus", "times" have to be partial functions - kinda like "minus" in $\mathbb N$ – ljfa Mar 17 '14 at 21:27
  • @MichaelGreinecker That would be a loop. – Dan Christensen Mar 17 '14 at 21:27
  • My question is - what's the use of such a theory? Most arithmetic identities won't hold in such a setting... – fgp Mar 17 '14 at 21:30
  • @PyRulez I think you would need some equivalent of induction on the natural numbers. – Dan Christensen Mar 17 '14 at 21:30
  • @fgp I would usually say the same thing. Even basic arithmetic would be impossibly difficult. I was just wondering if you could attack the problem from a formalistic point of view. I suspect it is impossible to formalize such notions, that they can only ever be informal discussions with lots of hand waving, etc. But perhaps I am biased. – Dan Christensen Mar 17 '14 at 21:37
  • You could also just use modular arithmetic and the problem is solved. – Christopher King Mar 17 '14 at 21:41
  • 1
    @DanChristensen I don't know why people are implying it can't be done. I've never seen it done and I would like to. Someone I trust has told me it can be done. For what's it's worth, I remember first reading about it in Hilbert's article On the Infinite. – Git Gud Mar 17 '14 at 22:37
  • @DanChristensen I'm sure you can devise some axioms for such a structure. As PyRulez points out, modular arithmetic is one such theory. The question isn't whether you can axiomatize finitary arithmetic, but whether you can do so in a way that actually permits interesting theorems to be proven. That seems, at least to me, to require more than just saying "Well, sooner or later adding one just loops back to zero". – fgp Mar 18 '14 at 01:31
  • 2
    The keyword you might be looking for here might be “ultrafinitism”. – MJD Mar 18 '14 at 02:06
  • @MJD Yes, that is what I mean. I have edited my question accordingly. Thanks. – Dan Christensen Mar 18 '14 at 02:38
  • Sazonov's paper On Feasible Numbers may be of interest here. Also, this is a relevant MO thread. – MJD Mar 18 '14 at 02:43

2 Answers2

4

There is no firmly established set of axioms for ultrafinitary number theory. This is one of the main problems for the field. For example, intuitionism was originally viewed as confusing and mostly incomprehensible (and, to some extent, the program pursued by Brouwer did have those properties). But once good formalizations of intuitionistic logic were developed, so that it was more clear what was going on, things became much more understandable. Now the study of intuitionistic logic is a mainstream topic in mathematical logic, because it has important applications even to classical mathematics.

It is not clear, yet, whether any similarly successful formalization of ultrafinitism will be found. Part of the reason for this is methodological. In normal logic, we can work with a metatheory that is simply finitary, rather than ultrafinitary (see below). But if someone really wants to have an ultrafinitary system of number theory, presumably they also want an ultrafinitary metatheory. This means that they can no longer talk about proofs of arbitrary finite length, for example.

There are some additional comments on this at https://mathoverflow.net/questions/44208/is-there-any-formal-foundation-to-ultrafinitism

An important clarification: "finitary" number theory is usually used to mean systems such as primitive recursive arithmetic (PRA), in which the axioms are all in particularly concrete forms. Systems such as PRA still have infinitely many natural numbers, they simply limit the ability to use "infinitary" methods on them. PRA is the standard finitary system used in proof theory. "Ultrafinitary" number theory refers to systems in which the set of "natural numbers" is, in some sense, finite.

Community
  • 1
Carl Mummert
  • 81,604
3

If you want another perspective on the thing, consider a nonstandard model of Peano arithmetic.

The usual intuition of such things is that a nonstandard model contains the ordinary natural numbers along with a bunch of strange infinite numbers, but nonetheless still manage to just like the ordinary natural numbers, even satisfying the axiom of induction... provided you limit yourself to internal statements: i.e. statements that can be expressed in the language of Peano arithmetic.

You can flip that around, though -- you can imagine the nonstandard model to be the ordinary natural numbers, and the standard model to be some weird smaller collection of natural numbers that is somehow bounded, but yet somehow manages to consistently obey the axioms of Peano arithmetic, so long as you stick to internal, small statements.

My intention, of course, is that the small natural numbers -- i.e. the ones contained in the standard model -- now corresponds more closely to "the subclass natural numbers accessible to humans". And you have added features; e.g. this arrangement doesn't require there to exist a largest small natural number. "Small" isn't part of the language of Peano arithmetic, so the usual inductive proof that you would have to have such a thing doesn't apply.

Interestingly, I believe it is possible, in such a setup, to develop an "infinite set theory of small sets". As the first step, you can use large sets as a proxy for proper classes; two large sets represent the same class iff they have the same small elements. Then, you can use proper classes as objects and go up to the next order. I'm not entirely sure how far you can get with such a programme.

Alas, the only sort of axiomatization of this sort of thing I've seen is "internal set theory", which is based on ZFC rather than Peano arithmetic, but it may still appeal to you.

Writing this answer has really helped me clarify my opinions on ultrafinitsm. I want to say that the "human-accessible" numbers already Peano axioms directly; no need to try and come up with a new axiomatization.

What we need instead is a larger theory that lets us talk about the possibility that there are numbers inaccessible to humans. Thus, my focus on embedding the human-accessible numbers as a standard model inside a larger non-standard model (or maybe I should coin new terminology: to embed the human-accessible natural numbers as a substandard model of the natural numbers). And I want to do this in a way that defeats the usual 'weirdness' arguments, such as "there must be a smallest number that is human-inacessible".

But as a caveat, most of my knowledge of ultrafinitism comes from the popular controversial accounts, which may have been more focused on claims of the deficiency of standard mathematics rather than exposition about what ultrafinitism actually is.

  • I say "small" but I'm not sure it actually has to be a size-based thing: i.e. I'm not sure you can prove that if $x < y$ and $y$ is "small" then $x$ is also "small". –  Mar 18 '14 at 00:56
  • I should caveat that when I say "usual intuition", it's not my intuition, but how I have inferred others think about these things. I actually prefer a third, more formalist intuition about nonstandard models. –  Mar 18 '14 at 01:07
  • I would think that the statement $\bigl(\mathrm{small}(y))\wedge (x\lt y)\bigr)\implies \mathrm{small}(x)$ is a reasonable thing to take as an axiom of the theory, somewhat akin to Separation in ZF... – Steven Stadnicki Mar 18 '14 at 01:18
  • @Steven: It could be, but I think not having that theorem is a feature if you want to keep the analogy of "small = human accessible". e.g. most numbers between $2^{2^{1023}}$ and $2^{2^{1024}}$ couldn't be written down by a human. –  Mar 18 '14 at 01:21
  • That makes some sense. It sounds like your notion of small is roughly analagous to 'of (possibly resource-bounded) Komolgorov complexity less than $C$' for some 'reasonable-sized' $C$? – Steven Stadnicki Mar 18 '14 at 01:26
  • Yes, something like that. My rationale for that feature is to be able to express the idea that we can 'formally' write down natural numbers that are 'too big to compute with'. Rather than try to banish those from the concept of 'number' (and deal with the consequent difficulties with semantics), I'd rather have a model that can retain them as number, but still be able to express that the numbers we can write are still 'too big' -- e.g. maybe we can define "$x$ is not too big to compute with" to mean "every number less than $x$ is standard". –  Mar 18 '14 at 03:40
  • This question has an affirmative answer to my conjecture. The accepted answer also points out some more interesting things we can arrange to happen. (and ping @Steven since I forgot) –  Mar 18 '14 at 10:27