1
$\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. . . .

$\endgroup$
  • 5
    $\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$ – dbx Jan 18 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$ – CyclotomicField Jan 18 at 17:31
  • $\begingroup$ The list of Peano axioms include that $\,S\,$ is injective. $\endgroup$ – Somos Jan 18 at 18:00
2
$\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 Piano 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$
  • $\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 Jan 19 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 Jan 19 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 Jan 19 at 4:58
2
$\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$
  • $\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 Jan 19 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 Jan 19 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 Jan 19 at 18:53
0
$\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$
  • $\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 Jan 27 at 20:03
  • $\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$ – Ross Millikan Jan 28 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 Jan 28 at 2:00
  • $\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$ – Ross Millikan Feb 11 at 5:11
-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$
  • 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$ – Ross Millikan Jan 28 at 3:10
  • $\begingroup$ Just updated it. $\endgroup$ – 147pm Feb 11 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$ – Ross Millikan Feb 11 at 5:04

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.