2
$\begingroup$

Going with this explanation of Peano's Axioms, I cannot understand how/where the successor function is definitively stated to be the very next number in the case of natural numbers. In this treatment, it says

The successor of $x$ is sometimes denoted $S⁢x$ instead of $x′$. We then have $1=S⁢0$, $2=S⁢1=S⁢S⁢0$, and so on.

Again, I don't see from the axioms how very next is guaranteed. Neither further on when addition is defined "based on the axioms." It seems a successor function could map "nextness" in many ways, e.g. $Sx$ could be $x+56$, or whatever as long as $Sx$ was something "further up the natural number line." So yes, I know I'm missing something here. . . .

Update

I finally returned to this issue after stumbling across some other sources. Basically, the whole issue of $S$ "jumping around" and not being a strict "next one up the number chain" can be attacked from exposing and forbidding "loop" situations.

Loop situation

By allowing a successor with $x_3$ circling back to $x_1$, we have with such an $S$ created a "fixed-point" for $S$

$$S(S(S(x_1))) = x_1$$

which is not allowed by the injectivity axiom. See this discussion, which demonstrates a $S(x_k) = x_k$ situation. My example is the same situation, only two extra mappings.

Still, the proof in the proofwiki relies on a hard contradiction backed up by the Peano Induction axiom -- which leaves me a bit pale. Does any sort of $S$ definition with any "fixed point"/loop truly force -- with the induction and injectivity axioms -- "very next one?" Intuitively I can see that any "doubling back" makes for a fixed-point, but....

$\endgroup$
4
  • 6
    $\begingroup$ What you're missing is that the very idea of 'next' is defined by the successor function. The number 56 doesn't exist except that it's the name we give the successor to the number which we have previously named 55. $\endgroup$ Commented Jan 18, 2019 at 17:15
  • 1
    $\begingroup$ Note that the axioms state there is exactly one successor to any natural number. No other number will do except the exact successor. There is no ambiguity here. $\endgroup$ Commented Jan 18, 2019 at 17:31
  • $\begingroup$ The list of Peano axioms include that $\,S\,$ is injective. $\endgroup$
    – Somos
    Commented Jan 18, 2019 at 18:00
  • $\begingroup$ Does this answer your question? How does Peano Postulates construct Natural numbers only? $\endgroup$
    – MJD
    Commented Mar 11, 2022 at 18:41

5 Answers 5

4
$\begingroup$

You're right, it's not obvious. There are a number of interlocking issues.

First let's consider the situation you suggested, where $S(n) = n+57$. We have a couple of choices here. One is to say that the natural numbers are $0, 57, 114, 171, \ldots$, and nothing else is a natural number. Thhis works, but what we get is identical to the regular natural numbers, with different names for the numbers. This system still has $1,2,$ etc., but we are calling them $57, 114$, etc.

Now suppose instead we say that $S(n)=n+57$ and $2, 3,$ etc. are still considered natural numbers. But this fails to satisfy the Peano axioms, specifically the axiom of induction. For suppose $P(n)$ is the statement “$n$ is a multiple of 57”. Certainly $P(0)$ is true, and we can show that if $P(n)$ is true then so is $P(S(n))$. The axiom of induction then says that $P$ is true for all natural numbers. But it's not true for $2$, which contradicts the axiom.

Now let's suppose that it's only $S(0) =57$ and the other numbers have their usual successors. This time the axiom that is violated is the one that says that different numbers have different successors. We have $S(0)=S(56)$ but $0≠56$. We can patch this up by deleting $56$. (Or, equivalently, by agreeing that $56$ is not a natural number.) But now the axiom is violated that says that every number has a successor: what's the successor of $55$?

You can try to patch this up too, but you'll get into trouble some other way. You should think about it and see what happens.

Now let's go the other way: every number has its usual successor, but there's also a natural number $\beta$ between $3$ and $4$. But what is $S(\beta)$? No matter what you try, something breaks.

Does that help?

$\endgroup$
3
  • $\begingroup$ Your arguments assume we know about $\N$ and that its integers are $0, 1, 2 . . .$. And no I wouldn't set up a multiple situation like your first example. And it seems your second example could be indeed "patched up" to have $S$ send us anywhere on the natural number line as long as $S$ stays consistent, i.e., $S(0) = 57$ and $S(56) = 1,002$. It would be a merry chase, but it does seem we could play that game infinitely -- unless I'm missing something here. Is there anything saying a $S(n)$ couldn't even jump backwards? $\endgroup$
    – 147pm
    Commented Jan 19, 2019 at 4:34
  • $\begingroup$ . . . actually, the Axiom 3 -- $0$ is not the successor of any natural number -- that might finally blow up my crazy jumping successor function, since some $S(x)$ will have no other number remaining, no place left to go other than back to $0$, which is not allowed. Crazy stuff. Peano wants to be like dominoes lined up and each one knocking over the next -- not one magically jumping up and knocking a domino seventy ahead of it. $\endgroup$
    – 147pm
    Commented Jan 19, 2019 at 4:46
  • $\begingroup$ . . . would this be an example of "set closure," i.e., "closed under $S$", and the Peano Axiom of Induction (5) working together? $\endgroup$
    – 147pm
    Commented Jan 19, 2019 at 4:58
4
$\begingroup$

If you just restrict yourself to the first axioms listed on that page, then indeed you could say that the expressions $0,S(0), S(S(0)), ...$ denote $0,2,1,4,3,6,5,....$ respectively. That would still satisfy the axioms. But you would still have a structure that is isomorphic to the natural numbers.

Also, if you define:

$$\forall x \forall y (x < y \leftrightarrow (y=S(x) \lor \exists z (y = S(z) \land x < z))$$

(which I would think captures the notion of $<$),

then using only those very first axioms, you can prove that:

$$\forall x \neg \exists y (x < y \land y < S(x))$$

i.e. that there is no number between any number and its successor ... and thus that the successor indeed gives you the very next number.

Finally, if you use the addition and multiplication axioms stated later on on that website, then you can prove some results that are certainly very suggestive of $S(0)$ working in a way consistent with our concept of the number $1$.

For example, it follows from the Peano Axioms that $$\forall x ( x · S(0) = x)$$ .... which would make sense if $S(0)$ would take the role we normally reserve for $1$ rather than, say, $56$

Likewise, you can prove from the Peano Axioms that $$\forall x ( x · S(S(0))= x + x)$$ ... again, that would square with the way we think about numbers if $S(S(0))$ is seen as $2$, rather than $117$.

$\endgroup$
3
  • $\begingroup$ I don't see how your first two examples are from the original Peano Axioms. Unless I'm mistaken, these come from a further "completion" of PA where addition and multiplication are defined recursively ( cs.toronto.edu/~sacook/csc438h/notes/page96.pdf ). Just intuitively $x + Sy = S(x + y)$ would kill any crazy jumping ahead/back $S$ wouldn't it? $\endgroup$
    – 147pm
    Commented Jan 19, 2019 at 5:13
  • $\begingroup$ @147pm You are right that the original Peano Axioms did not include any definitions of $+$ and $\times$, but the website you referred to in your original post did give those definitions (making it Peano Arithmetic) so I went with it. Anyway, you don't need the addition and multiplication axioms to see how the initial axioms just involving the successor function will force any model to be isomorphic with the natural numbers, and how you can never get a cycle, for example. $\endgroup$
    – Bram28
    Commented Jan 19, 2019 at 13:32
  • $\begingroup$ @147pm BTW: The linked website in your original post states: "Peano arithmetic consists of statements derived via these axioms. For instance, from these axioms we can define addition and multiplication on natural numbers." ... now that is indeed complete B.S. ...you don't derive or define addition and multiplication on the basis of the first few axioms ... So, if your gripe is with that, I completely agree. $\endgroup$
    – Bram28
    Commented Jan 19, 2019 at 18:53
1
$\begingroup$

From a formal point of view, PA is written with very few symbols. We are not given the natural numbers or the successor function except as they are defined by the axioms. We are told that there is an element called $0$ and there is a function called $S$ that can be applied to any element of the universe. This is enough to tell us that there is an element that is $SS0$. $2$ is not part of the language but it makes things easier to read and write if we define $2$ to represent $SS0$. We could as well give $SS0$ a name like John, but we choose $2$ because it behaves as the $2$ we learned about in grade school. We can prove from the axioms that $SS0+SS0=SSSS0$, which we would write informally as $2+2=4$.

The author of the axioms can write that he is thinking about $S$ as the successor function, but that is not part of the formal development. From the first two axioms we can show in the metatheory that the universe is infinite, but that is not a conclusion of PA.

$\endgroup$
4
  • $\begingroup$ Not sure what you mean by "not given the natural numbers." The PAs are based are establishing isomorphism with $\mathbb{N}$. What I'm niggling on about is whether we can nail down $S$ as increasing one integer at a time. I now realize I'm probably shaky on the middle paragraph in my answer, although my first and third are probably good. $\endgroup$
    – 147pm
    Commented Jan 27, 2019 at 20:03
  • 1
    $\begingroup$ What I mean by not being given the natural numbers is that we learn a lot about the natural numbers before we learn anything about axioms and careful derivation. We need to forget all that and start from the PA axioms. We have to derive all the rules of arithmetic we learned as kids. As such, $Sx$ is the next one after $x$ because it has one more $S$ in front of the $0$. We then have to show that $S0$ behaves as we expect $1$ to, that $SS0$ behaves like $2$, and so on. $\endgroup$ Commented Jan 28, 2019 at 0:08
  • $\begingroup$ I'd like you and others to review what I said in my "answer." As I'm saying, I'm not exactly comfortable with the whole treatment. $\endgroup$
    – 147pm
    Commented Jan 28, 2019 at 2:00
  • 1
    $\begingroup$ I think you are still thinking of the naturals as a structure outside of PA. You know $12$ is not the very next after $7$ because you know about the naturals and worry that PA might define $S7=12$. PA doesn't know about $7$ or $12$ or the naturals you are used to. Once we have the PA axioms we give names to various constructs because they are useful. We define $7=SSSSSSS0$ and $12=SSSSSSSSSSSSSSS0$. Now we can see that $12 \neq S7$ $\endgroup$ Commented Feb 11, 2019 at 5:11
1
$\begingroup$

I recently really struggled with the same question while studying Peano axioms, but finally, I think I got it. I will mostly repeat what a number of answers and comments said, but I think you still might be missing the idea behind them. It's counterintuitive, so it's hard to change the perspective once you are stuck in the wrong one.

The main point is that natural numbers are not ordered in any way until you define the successor function.

There is no inherent order in the set before you define $S(x)$, so it's misleading to prescribe its elements labels like 55, 56, etc. $S(x)$ can be defined absolutely arbitrary as long as it satisfies the axioms. Only after you defined $S(x)$ do the terms like 55 and 56 make sense. As @Ross Millikan wrote in his comment

We have defined 56 to be 𝑆𝑆𝑆…0 with 56 𝑆's

So you can't say that

𝑆𝑥 could be 𝑥+56

because as @Sort of Damocles wrote

The number 56 doesn't exist except that it's the name we give the successor to the number which we have previously named 55

Peano axioms build what we call natural numbers, not merely are built on top of them.

As @Ross Millikan wrote in his answer

2 is not part of the language but it makes things easier to read and write if we define 2 to represent 𝑆𝑆0. We could as well give 𝑆𝑆0 a name like John, but we choose 2 because it behaves as the 2 we learned about in grade school.

This means that labels 2, 55, 56, etc are needed only for convenience: 56 is much shorter to write than $SSS...S(0)$ with 56 $S$'s

$\endgroup$
-1
$\begingroup$

First, I am not alone in asking this question of "nextness." The following is from the Wikipedia treatment, Peano Axioms:

However, considering the notion of natural numbers as being defined by these axioms, axioms 1, 6, 7, 8 do not imply that the successor function generates all the natural numbers different from 0. Put differently, they do not guarantee that every natural number other than zero must succeed some other natural number.

...which goes on to use the often included axiom of induction to rework the successor function into implying nextness as always "one more." But then the article describes addition as defined recursively by two phantom Peanos:

\begin{align} a + 0 & = a \\ a + S(b) & = S(a + b) \end{align}

If the second expression is considered an axiom, then yes, $S$ would have to be consistently a "one more" successor. That is, there cannot be an $S(b) + a$ that is different from an $S(c)$ where $c = a+b$. However, these addition axioms are not really original to the PAs.

We might fall back on insisting that a successor function cannot from one application to the next behave differently, i.e., (allow me to switch successor notation) $m \succ m'$ implying $m'-m \geq 1$, and then $n \succ n'$ yielding $(n'-n) \neq (m'-m)$ is a violation of the spirit of the successor function and its brother induction.

It is true that $m=n \iff m'=n'$ implies uniqueness of the successor function only in the sense of injection (as pointed out in a comment by Somos). We might say a successor function must be an injective function producing distinct results, e.g., $n'$ is distinct from the successors which produced $1,...,n$, but I'm still doubtful this implies "one more," i.e., $n'$ to $n''$ proceeds one "very next thing" in a strict order at a time.

However, we might be rescued by Kleene's (Introduction to Metamathematics; p.20) example where he leverages the PA that $x' \neq 0$, or, $0$ is not the successor to any natural number. We might set up a contradiction: $$0''''=0''$$ but this would be true only if $$0'''=0'$$ Applying this logic again, $$0'''=0'$$ only if $$0''=0$$ So yes, this is a contradiction; hence, we have butted up against the lower boundary of the successor concept, which, therefore, implies a successor being greater than since we can run any successor-based induction of $\mathbb{N}$ backwards to $0$. Ironically, this is a sort of reverse-induction to prove that the Peano successor is consistently "one more" demanding some sort of $\mathbb{N}$-like order.

All in all, I'm still stuck on this....

$\endgroup$
3
  • 1
    $\begingroup$ Your first paragraph is completely off the mark. Once we define $1$ to be $S0$ we can show that $Sx=x+1$ from the axioms. I would view $S$ as more fundamental PA starts with successor. Wikipedia talks of PA, then adding addition and multiplication. $\endgroup$ Commented Jan 28, 2019 at 3:10
  • $\begingroup$ Just updated it. $\endgroup$
    – 147pm
    Commented Feb 11, 2019 at 4:51
  • $\begingroup$ You have it backwards. The successor function defines what is the very next. How do you define $x+56?$ We have defined $56$ to be $SSS\ldots 0$ with $56\ S$'s. Then the addition axioms make sure that $x+56$ is what we expect. The only way this can fail is if you think there is some structure defined in another way that gives you what is the very next. $\endgroup$ Commented Feb 11, 2019 at 5:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .