2
$\begingroup$

First, let me state what I understand to be the first-order rendition of Peano's 5th axiom: the axiom of induction. For all natural numbers, for any relation/property/predicate $R$...

$$(R(0) \land \forall x[R(x) \rightarrow R(S(x))]) \rightarrow \forall x(R(x))$$

(first question: is this a correct formalization of this axiom or not?)

How does this axiom prevent elements of natural numbers that have '$S$-loops' that is:

\begin{align} S(a) = b && \text{and} && S(b) = a \end{align} (edited for clarity)

$\endgroup$
  • 2
    $\begingroup$ This axiom does not, but the third Peano Axiom.says that if $S(n)=S(m)$, then $n=m$. If $S(x_9)=x_8$, then $S(x_9)=S(x_7)$, so $x_7=x_9$, which eventually leads to $0=S(x_2)$, which is forbidden by the Fourth Axiom (or peharps by a different number axiom depending on how you formalize them). $\endgroup$ – Arturo Magidin Mar 7 at 21:37
  • $\begingroup$ ' then 𝑆(𝑥9)=𝑆(𝑥7)...' is not true. As defined above, $S(x_9) = x_8$. I've change the nomenclature to 'a' and 'b' to be more clear. In this sense S(a) = b and S(b) = a are completely possible given axioms 1-4. $\endgroup$ – C Shreve Mar 8 at 2:41
  • $\begingroup$ It’s not that “it’s not true”. It’s that you’ve changed your statement. When you wrote $x_8$, I of course assumed that you meant the result of applying $S$ to $0$ eight times. And, no it is still not possible, and yes, you still need the other axioms; induction alone doesn’t do it, though induction does come into play in the general statement. If $a=0$, then you are violating the axiom that says that $0$ is not a successor. If $a\neq 0$, then from induction you get that $a$ is a descendant of $0$, so you still get that $a=x_n$ and go from there. $\endgroup$ – Arturo Magidin Mar 8 at 10:36
  • $\begingroup$ I would prefer brackets enclosing everything to the left of the 2nd "$\implies$" in your statement of Axiom 5. In contrast, putting brackets around everything to the right of "$\land$" gives a different (wrong) meaning. $\endgroup$ – DanielWainfleet Mar 9 at 18:28
2
$\begingroup$

Using Peano's axioms

\begin{align} \forall m \, S(m) \neq 0 &&&\text{(}0\text{ is not the successor of anyone)} \\ \forall m \forall n \, (S(m) = S(n) \to m = n) &&&\text{(injectivity of }S\text{)} \end{align}

and Peano's principle of induction, it is easy to prove that the "double-successor" does not have any fixed point, i.e. \begin{align} \forall m \, S(S(m)) \neq m \end{align}

A rigorous proof of this property is below. It is analogous to the one you can find here to prove that the successor has no fixed point.

Now, this property excludes the possibility of $S$-loops. Indeed, if there were $m$ and $n$ such that \begin{align} S(m) &= n & S(n) &= m \end{align} then we would have $S(S(m)) = m$ (replace $n$ with $S(m)$ in the second identity), which is impossible.


We want to prove that, in Peano arithmetic, \begin{align} \forall x \, S(S(x)) \neq x &&&\text{(i.e. } \forall x \, R(x) \text{ where } R(x) \text{ is the formula } S(S(x)) \neq x\text{).} \end{align}

To prove this we apply Peano's induction principle, thus we have to prove two facts:

  1. Base case, i.e. $S(S(0)) \neq 0$. This holds because it is just an instance (take $x = S(0)$) of Peano's axiom \begin{align} \forall x \, S(x) \neq 0 &&&\text{($0$ is not the successor of anyone).} \end{align}

  2. Inductive case, i.e. $\forall x \, \big(S(S(x)) \neq x \to S(S(S(x))) \neq S(x) \big)$. So, given $x$, we suppose $S(S(x)) \neq x$ and we have to show that $S(S(S(x))) \neq S(x)$. Aiming for a contradiction, suppose $S(S(S(x))) = S(x)$. According to Peano's axiom \begin{align} \forall m \forall n \, (S(m) = S(n) \to m = n) &&&\text{(injectivity of }S\text{)} \end{align} instantiated with $m = S(S(x))$ and $n = x$, we have that $S(S(x)) = x$, which is impossible. Therefore, $S(S(S(x))) \neq S(x)$.

This ends the proof that $\forall x \, S(S(x)) \neq x$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I think your formalization is correct.

The axiom of induction doesn't prevent by itself S loops. Consider, a two elements set $\{0,1\}$ with $S(0) = 1$ and $S(1) = 0$

To prevent S loops you need axioms

4."Two numbers of which the successors are equal are themselves equal."

$$ \forall a,b \; . \; S(a) = S(b) \Rightarrow a = b $$

3."$0$ is not a succesors"

$$ \forall a\;.\;S(a)\neq0 $$

Informally, if you have a loop from combination of (5) and (4) it follows that loop need to involve all predecessors of a looped element. And with this (3) provides a contradiction, as by (5) every element has $0$ as a predecessor.

The more formal proof can look like this.

Consider the predicate $$NL(x) = \text{$x$ is not an element of any loop.} $$ By definition of the loop, if $a$ is in the loop, there must be $b$ in the loop, such that $a = S(b)$. So, $NL(0)$ holds by axiom (3). Now consider an element $a$ such that $NL(a)$ holds. If $S(a)$ is an element of the loop, then by the axiom (4) the element $a$ is also in the loop. This is a Contradiction! Thus, $NL(a) \Rightarrow NL(S(a))$ holds for any $a$. Now can apply axiom of induction to see that there is no element $a$, which can be looped.

So there are no loops in Natural numbers defined by Peano axioms. Note, however, that you need every axiom to prove it.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think your $a$ and $b$ in paragraph 2 are supposed to be $0$ and $1$.... $\endgroup$ – Arturo Magidin Mar 7 at 21:52
  • $\begingroup$ Thanks. You are correct. This was a typo. $\endgroup$ – Nik Pronko Mar 7 at 21:57
  • 1
    $\begingroup$ Indeed, with only the axiom of induction, the one-element set $\{0\}$ would also be a possibility. $\endgroup$ – Greg Martin Mar 7 at 22:21
  • 1
    $\begingroup$ But this is not necessarily true. The case you bring up is true because you have expressly chosen a specific set ({0,1}) where one member (ie 0) is identified by axiom 3. However, the set {0, 1, 2, ... a, b} with S(a)= b and S(b) = a could still exist given axioms 1-4. What is it about axiom 4 that eliminates 'a' and 'b'? $\endgroup$ – C Shreve Mar 8 at 2:48
  • $\begingroup$ @CShreve Say, $a = S(c)$, then by axiom 4 $b = c$. Repeating this procedure in so for we can, we will end up with a set $\{0,1\}$ as in example above. Of course, this works only with finite sets, and words "repeating procedure in so for" really is just a reference for the axiom of induction. I will add a more formal proof to the answer. $\endgroup$ – Nik Pronko Mar 8 at 10:34
0
$\begingroup$

In the general statement as you’ve now written, not a specific example as you had before, induction does come into play in the sense that one must prove, by induction, that if $x\in \mathbf{N}$, then either $x=0$, or there exists $k$ such that $x=S^k(0)$.

Indeed you let the property by “$x=0$ or $x$ is a descendant of $0$”; $0$ has the property, and if $n$ has the property, then so does $S(n)$.

Once you have that, from $S(a)=b$ and $S(b)=a$, you get that either $a=0$ and you violate the Axiom that says that $0$ is not a successor; or else that $a=S^k(0)$ for some $k$. Then $b=S^{k+1}(0)$, and you are now in essentially the same situation as before, when you had the specific example of $S(x_8)=x_9$ and $S(x_9)=x_8$. Now you have $S^{k+2}(0)=S^k(0)$. From that you get $S^{k+1}(0)=S^{k-1}(0)$, and so on until you get that $0$ is a successor, contradicting that axiom.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

@Taroccoesbrocco, so in the spirit of a 'double successor' implies contradiction, would a formalization of this look like:

  1. Let R(x) -> S(S(x)) = x (double successor relation)
  2. By Axiom 5 then R must also apply to $0$
  3. So $S(S(0)) = 0$
  4. Let $a = S(0)$
  5. By 4 and 3, $S(a) = 0$...which contradicts Peano Axiom 4
  6. Therefore relation R (ie...double successor) is not in the natural numbers.

Is there anything incorrect about the above line of reasoning?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ What you wrote is essentially meaningless. If you want to prove $\forall x \, S(S(x)) \neq x$ by contradiction, you have to suppose its negation, that is $\exists x \, S(S(x)) = x$. Now, you do not know who is the $x$ such that $S(S(x)) = x$, therefore you are not allowed to conclude that $S(S(0)) = 0$. $\endgroup$ – Taroccoesbrocco Mar 9 at 11:41
  • $\begingroup$ I edited my answer to include a proof of $\forall x \, S(S(x)) \neq x$. $\endgroup$ – Taroccoesbrocco Mar 9 at 11:43
  • $\begingroup$ The additional detail above are helpful. The intent in my reasoning above is to 1)assume a relation $R$ of the natural numbers then 2)show that the relation $R$ produces some contradiction against the Peano axioms. The reason $R$ can be applied to 0 is axiom 5 as any relation in the natural numbers must be applicable to 0 as well. $\endgroup$ – C Shreve Mar 9 at 19:50
  • 2
    $\begingroup$ What you proved is that $\exists x \, S(S(x)) \neq x$, more precisely that $S(S(0)) \neq 0$. But it is not enough, indeed you have to prove that $\forall x \, S(S(x)) \neq x$. $\endgroup$ – Taroccoesbrocco Mar 9 at 20:38
  • 2
    $\begingroup$ The fact that a property fails for some natural numbers does not imply that it fails for all natural numbers. You define the predicate $R(x)$ as $S(S(x)) = x$. With your argument you're are showing that $\forall x \, R(x)$ is not true, i.e. that $\exists x \, S(S(x)) \neq x$. But this is not what you need to prove the absence of $S$-loops. What you need to prove is that $\forall x \, S(S(x)) \neq x$. $\endgroup$ – Taroccoesbrocco Mar 10 at 6:25

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.