8

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".

abo
  • 1,844
James Propp
  • 19,363
  • 2
    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. – LSpice Jan 20 '23 at 18:35
  • 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). – abo Jan 21 '23 at 11:52
  • 1
    @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? – Kevin Jan 22 '23 at 09:56
  • 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?) – James Propp Jan 22 '23 at 12:43
  • 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..." – abo Jan 22 '23 at 13:11
  • @abo, exactly as you point out, there cannot be a statement that is true in all initial segments that implies infinitude of primes. My condition, for example, like the Bertrand's-postulate analogue proposed by the asker, is true in any initial segment of the natural numbers, and implies infinitude of the primes when the successor (and hence the product) operation is total. As to my being more knowledgeable—if at all, then not in this domain! – LSpice Jan 22 '23 at 23:54

3 Answers3

14

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.

Joel David Hamkins
  • 224,022
  • 3
    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. – Emil Jeřábek Jan 20 '23 at 21:49
  • Thanks Emil. We've seen some hints of that, but clearly haven't been looking in the right place. – Joel David Hamkins Jan 20 '23 at 21:53
  • 1
    @EmilJeřábek If you have a good reference, I shall add it to the post. – Joel David Hamkins Jan 20 '23 at 23:19
  • I’ll look up something. But checking references is very time consuming, and I likely won’t be able to do it during weekend. – Emil Jeřábek Jan 21 '23 at 09:48
  • No problem, take your time. – Joel David Hamkins Jan 21 '23 at 09:59
  • @EmilJeřábek. If this is an abuse of your good services, then please ignore it. Is there a simple example of a statement unprovable in first-order fPA but provable in second-order fPA (i.e. with comprehension)? $\forall x \exists y Sx,y \rightarrow Cons(PA)$, where S is the successorship relationship and Cons(PA) is an arithmetical statement of the consistency of first-order PA, would if I'm not mistaken be an example, but I'm interested in a natural example. Is e.g. even Euclid's Lemma ($p|ab \rightarrow p|a \lor p|b$) provable in fPA? fPA just seems to be very weak, but perhaps I err... – abo Jan 22 '23 at 13:28
  • @abo The second-order version is true only in standard finite models, and so any $\Pi_1$ statement that is independent of PA (and there are many) will be unprovable in fPA but provable in the second-order version. e.g. all true consistency statements, and more. – Joel David Hamkins Jan 22 '23 at 14:00
  • @JoelDavidHamkins. Thanks very much! I'm really looking for natural examples, the more basic the better, so not examples independent of PA. E.g. Euclid's Lemma. (Or Bertrand's Postulate.) – abo Jan 22 '23 at 14:44
  • Both of those will be provable in the second-order theory. For Bertrand, take the statement for every n, there is a prime between n and 2n. You interpret the numbers up to 2n using digit representation as in my answer. This is a valid consequence of PA2top because it is true in standard finite segments. Similarly with Euclid's lemma. What I am saying is that any true statement expressible in the PAtop language will be valid in PA2top. The difficult cases occur with fast-growing functions that are out of reach of the interpretability methods, making the statements themselves not expressible. – Joel David Hamkins Jan 22 '23 at 14:56
  • It is problematic to speak of "provable" in a second-order theory, since we don't have a sound & complete proof system for second-order logic. – Joel David Hamkins Jan 22 '23 at 14:59
  • I'm asking if they (Euclid's Lemma, Bertrand's Postulate) are provable in the first-order theory from the usual axioms for successor, addition, and multiplication (minus the axiom that every number has a successor). Are they? – abo Jan 22 '23 at 15:20
  • Ah, I thought you were asking about the second order theory. Huge difference. Since the models of the first-order theory are exactly the cut-offs of models of $I\Delta_0$, as I explain in my answer, the question is whether those theorems are provable in $I\Delta_0$, and there are many open questions about that. For example, pigeon-hole principle scheme is open. – Joel David Hamkins Jan 22 '23 at 15:54
  • One should think of it as a very weak theory, in which even exponentiation is problematic and induction is possible only for very local phenomena. – Joel David Hamkins Jan 22 '23 at 16:04
  • 2
    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$. – Emil Jeřábek Jan 22 '23 at 17:29
  • 1
    @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 https://mathoverflow.net/a/120106 for more details). – Emil Jeřábek Jan 22 '23 at 18:18
  • Ah, that is helpful. – Joel David Hamkins Jan 22 '23 at 18:54
  • Thanks Emil. My question is does the 1st order theory with the usual axioms for successor, +, and $\times$, minus the axiom that every number has a successor (and so the other axioms suitably adjusted) prove EL. Call this theory $T$. $T$ provability is different from $I \Delta_0$ provability because $I \Delta_0$ proves $\forall x \exists y (y = x+1)$ but $T$ doesn't (right??). Is there an operation * (e.g. bounding the quantifiers??) s.t. $T$ proves $\phi$ iff $I \Delta_0$ proves $\phi^*$? In any case my question is whether $T$ proves EL. Sorry for being stupid so early in the morning ... – abo Jan 23 '23 at 09:02
  • 1
    @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). – Emil Jeřábek Jan 23 '23 at 12:15
  • 1
    @Joel Concerning references, you already got an answer from Ali. The result that every model of $\mathrm{PA^{top}}$ is an initial interval of a model of $I\Delta_0$ is also proved in Hájek&Pudlák (Theorem IV.2.2), again attributed to Paris. Let me add that some interesting properties of variants of $\mathrm{PA^{top}}$ related to the weak pigeonhole principle are in Neil Thapen’s Ph.D. thesis. – Emil Jeřábek Jan 23 '23 at 12:21
  • @abo Oh, and yes: if $\phi$ is any arithmetical sentence (in a relational language where the arithmetical operations are not necessarily total), then $T\vdash\phi$ iff $I\Delta_0\vdash\forall x,\phi^{\le x}$ and $\mathrm{PA}\vdash\phi$, where $\phi^{\le x}$ is $\phi$ with all quantifiers bounded by $x$. – Emil Jeřábek Jan 23 '23 at 12:27
  • @EmilJeřábek. Thank you Emil. Very clear and helpful as always. – abo Jan 24 '23 at 09:08
10

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?

abo
  • 1,844
7

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).

Ali Enayat
  • 17,058