8
$\begingroup$

One can consider a variant of the Dedekind-Peano axioms in which one replaces the assumption that every number has exactly one successor by the assumption that every number has at most one successor, leaving the other axioms the same (and in particular retaining the second-order induction axiom). The models of this theory are then the initial segments of the natural numbers. Call it a "size-neutral" version of the second-order Dedekind-Peano theory. My question is, to what extent can one prove analogues of standard theorems about the natural numbers in this theory?

For instance, what would serve as a size-neutral analogue of the proposition that the set of primes is infinite? Ideally it would be some proposition P with the property that if you assume that P is true, and you assume that every number has a successor, then the standard claim about the set of primes being infinite would follow without too much trouble (where "too much trouble" means "going back to the beginning and proving the infinitude of the primes in the usual way without invoking P at all").

I'm aware that even defining "prime" is problematic. To begin with, in a size-neutral theory, one cannot define addition or multiplication in the usual recursive way, or rather, if one does, the operations are not provably total; if one's model cuts off at n, then sums and products that exceed this bound are undefined. One could choose to remedy this with a definition that basically says "If a number has no successor, define it to be its own successor; now proceed using this new, enlarged notion of succession instead of the old one", and then sums and products that in ordinary arithmetic exceed n would now equal n -- though I'm not sure this is a good way to go.

This can't be a new line of thought, so I'd be happy with answers of the form "Go read X".

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Although multiplication isn't total, the notion of factorisation makes sense, right?, since one has a lower bound on size as witnessed by the number one is attempting to factor—and so primality should still make sense. One could encode an easy proof of infinitude of primes in the statement: if $S$ is the set of primes, then either the product of $S$ is not defined, or the product of $S$ does not have a successor. $\endgroup$
    – LSpice
    Jan 20, 2023 at 18:35
  • $\begingroup$ In a natural interpretation of "infinite," it is not possible to show there are an infinite number of primes in such a system, because it's not even true. For instance, if {0,1,2,3,4,5} are (all of) the natural numbers, then there are 3 prime numbers, and so the number of primes is a finite number (3). $\endgroup$
    – abo
    Jan 21, 2023 at 11:52
  • 1
    $\begingroup$ @abo: I think OP is aware of that, and is asking for a lemma that is provably true of {0, 1, 2, 3, 4, 5}, but which could also usefully contribute to a proof of the infinitude of the primes in standard arithmetic. LSpice's comment is probably what OP wants, I think? $\endgroup$
    – Kevin
    Jan 22, 2023 at 9:56
  • $\begingroup$ Kevin gets where I’m coming from. One such P would be Bertrand’s Postulate (“If 2k has a successor, then there’s a prime between k and 2k”). It’s true in all the finite models as well as the infinite one, and if one singles out the infinite model by adding the assumption that every number has a successor, then one can easily deduce that the set of primes is infinite. So in that sense Bertrand’s Postulate is exactly the sort of thing I meant by a “size-neutral analogue” of the infinitude of the primes. (Is my stance incoherent in some way that I’m not noticing?) $\endgroup$
    – James Propp
    Jan 22, 2023 at 12:43
  • $\begingroup$ I'm not making any claim of what someone knows or doesn't know, just a plea to be careful in a successorless world. For instance, LSpice (who is much more knowledgeable than me) doesn't seem to state a good infinitude condition, because the product of S = {top-1,top} is not defined and does not have a successor, but S is clearly finite. Also, Kevin's statement of Bertrand's Postulate is not the best, because whether 2k has a successor is neither here nor there, and the better condition is, "If 2k exists..." $\endgroup$
    – abo
    Jan 22, 2023 at 13:11

3 Answers 3

Reset to default
14
$\begingroup$

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

[Update As explained by Emil Jeřábek in the comments below and in Ali Enayat's answer, this theory has been well studied in models of arithmetic and is known as $\text{PA}^{\text{top}}$. The observations below about $I\Delta_0$ are evidently due originally to Jeff Paris.]

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$, and using this number, we can interpret a larger model of fPA. Simply use quadruples of numbers $abcd$ to represent larger numbers in base $m$. We know how to add and multiply such numbers in that representation, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers from the original model now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express those notions entirely in the original model simply by using the base $m$ representation. Any concept that could be expressed in the context of the larger models can also be expressed in the original model.

Iterating. The further observation is that we can simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Improve this answer
$\endgroup$
21
  • 3
    $\begingroup$ The established name for the theory fPA plus the existence of a largest element is $\mathrm{PA^{top}}$. The fact that all its models are intervals of models of $I\Delta_0$ is well known. $\endgroup$
    – Emil Jeřábek
    Jan 20, 2023 at 21:49
  • 1
    $\begingroup$ @EmilJeřábek If you have a good reference, I shall add it to the post. $\endgroup$
    – Joel David Hamkins
    Jan 20, 2023 at 23:19
  • 2
    $\begingroup$ Euclid's lema is quite easy to prove in $I\Delta_0$ (or even its weak fragment $IE_1$). Whether $I\Delta_0$ proves Bertrand's postulate, or even just the unboundedness of primes, is a well known open problem; by a result of Woods, Bertrand's postulate (and the slightly stronger Sylvester's theorem) is provable in $I\Delta_0+WPHP(\Delta_0)$ (weak pigeonhole principle), which is included in $I\Delta_0+\Omega_1$. $\endgroup$
    – Emil Jeřábek
    Jan 22, 2023 at 17:29
  • 1
    $\begingroup$ @Joel If I recall correctly, the system abo works with is not a genuine second-order theory, but “axiomatic second-order”, i.e., a two-sorted first-order theory with full comprehension. Its models where the successor function is not total are intervals on models of $V^\infty$, or equivalently (up to the so-called RSUV isomorphism), intervals on models of $I\Delta_0+\Omega_1$ (where numbers represent sets, and logarithmically small numbers represent numbers; see mathoverflow.net/a/120106 for more details). $\endgroup$
    – Emil Jeřábek
    Jan 22, 2023 at 18:18
  • 1
    $\begingroup$ @abo Yes, it does. This follows from the fact that every model of $T$ has an end-extension to a model of $I\Delta_0$, as mentioned by Joel. Consequently, $T$ and $I\Delta_0$ prove the same $\Pi_1$ sentences (formulated so that only variables can be used to bound quantifiers). $\endgroup$
    – Emil Jeřábek
    Jan 23, 2023 at 12:15
10
$\begingroup$

I've looked at the system you've mentioned, where you assume these as mathematical axioms:

(1) Uniqueness of successoring

(2) Uniqueness of predecessoring

(3) 0 doesn't have a predecessor

(4) Induction

As Emil Jeřábek pointed out to me, the system has connections to certain well-known systems of weak arithmetics. (See the first MathOverflow question linked to below.)

In second-order logic, where one has access to predicates and relationships, there is no problem to define addition and multiplication relationships, although as you point out they will not be total. There is no problem in defining primality, as LSpice points out in comments.

In this system you can prove Quadratic Reciprocity and Bertand's Postulate and I imagine - although I have not checked in detail - the Prime Number Theorem. You might want to check these out:

https://www.researchgate.net/publication/351561089_Arithmetic_Without_the_Successor_Axiom

https://www.researchgate.net/publication/352796035_Proving_Bertrand's_Postulate

This paper looks at what happens when you assume even less:

https://www.researchgate.net/publication/352795952_General_Arithmetic

Variants of this system have appeared in these MathOverflow questions:

Provability in Second-Order Arithmetic without the Successor Axiom

Can FPA really prove its consistency?

Is an ultrafinitist Hilbert's program doomed?

When we count the same set, must the number always be the same?

Can this weakish system of arithmetic express multiplication for second-sort numbers?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Fantastic answer! Lots of links to follow. Thanks! $\endgroup$
    – James Propp
    Jan 21, 2023 at 13:20
7
$\begingroup$

As pointed out by Emil Jeřábek (in the comment to Joel Hamkins' answer), the system you are referring to is known as "Peano Arithmetic with a top". It has been studied for several decades. A good place to learn about it is the chapter written by Lawrence (Tin Lok) Wong, as part of his lecture notes for a course on models of arithmetic, available here.

Wong's chapter also includes the proof of the theorem (mentioned in Hamkins' answer) that connects models of this theory with models of $\mathrm{I}\Delta_0$, and credits this result to Jeff Paris (see Theorem 13.11 of the chapter).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks very much, Ali. $\endgroup$
    – Joel David Hamkins
    Jan 22, 2023 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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