1
$\begingroup$

$\def\N{\mathbf{N}}$ The peano axioms:

  1. $0\in\N$
  2. $n\in\N \implies S(n)\in\N$
  3. $\forall n\in\N, S(n)\neq0$
  4. $\forall n,m\in\N, n=m \iff S(n)=S(m)$
  5. $[(0\in X) \wedge(\forall n\in\N, n\in X \implies S(n)\in X)]\implies X\supseteq\mathbf{N}$
I understand how the first 4 axioms alone are not enough to specify the natural numbers "as we know them." But I have yet to see a proper proof that, with the help of the 5th axiom of induction, this locks us into one and only one set, i.e. "our" natural numbers.

In particular, say we have a set $A=\{0,S(0),S(S(0)),\ldots\} \cup \{\omega,S(\omega),S(S(\omega)),\ldots\}$ Where $\omega$ behaves like another zero, in that it has no predecessor. (and also $\omega\neq0$). Using all 5 axioms, prove that this cannot be the set of all natural numbers.

Proof attempt. $A$ has the property that $0\in A$ and $n\in A \implies S(n)\in A$. Then by axiom (5), we can say $A\supseteq\N$. In particular, $\omega\in\N,S(\omega)\in\N$ and so on. I don't see how we have reached a contradiction yet. And I don't know how to proceed.

All in all, I'm of the opinion that instead of axiom 5, this axiom is simpler and should be equivalent.

5*. Let $m\in\N$. If for all $n\in\N$, we have $S(n)\neq m$, then $m=0.$

In other words, $0$ is the only number without a predecessor. Shouldn't we able to derive induction from this? Also the proof from above becomes very simple with this axiom instead of the induction axiom, since the existence of $\omega$ contradicts this axiom directly.

The Question. Can Axiom 5* replace Axiom 5 as the fifth axiom? If it cannot, how do we prove that the set $A$ defined as above is not the natural numbers?

EDIT: User Akiva Weinberger has shown that we cannot replace axiom 5 with axiom 5* in their comment to this post. It thus remains to prove $A$ as defined above is not the natural numbers, using the axiom of induction.

$\endgroup$
3
  • $\begingroup$ This is Dedekind's categoricity theorem. $\endgroup$
    – Akiva Weinberger
    Nov 29, 2022 at 3:49
  • 2
    $\begingroup$ As for replacing Axiom 5 with Axiom 5*, consider the set $\{0,1,2,\dots,x-2,x-1,x,x+1,x+2,\dots\}$, that is, the natural numbers union all polynomials of the form $x+k$ for $k\in\Bbb Z$. This should satisfy your axioms. $\endgroup$
    – Akiva Weinberger
    Nov 29, 2022 at 3:50
  • $\begingroup$ Thank you @AkivaWeinberger for the counter-example. It thus remains to prove rigorously the above proposition using the induction axiom. I have edited the post in light of your comment. $\endgroup$
    – user1020500
    Nov 29, 2022 at 4:17

1 Answer 1

Reset to default
1
$\begingroup$

$5^*$ cannot replace 5, as shown in the comments. However, $5^*$ clearly follows from 5, as we can take $X = \{n \in \mathbb{N} \mid$ If $n$ has no predecessor, then $n = 0\}$. We see easily that $0 \in X$ and that for all $n \in X$, $S(n) \in X$. It follows from 5 that $X = \mathbb{N}$, and thus the only number without a predecessor is $0$.

This rules out your example.

It is well-known that there exists a unique model of the second-order Peano axioms up to unique isomorphism. So the Peano axioms describe the structure of the natural numbers as completely as possible.

$\endgroup$
5
  • $\begingroup$ Nice. To further ask, how does axiom 5 rule out Akiva Weinberger's example? i.e. $\{0,1,2,3\ldots\}\cup\{\ldots \omega-2,\omega-1,\omega,\omega+1,\omega+2\ldots\}$ where $\omega\notin\{0,1,2,3\ldots\}$. To go even further, how are we sure that no matter which counter-example I come up with, there will always be a way to prove via axiom 5 that it isn't the natural number set? $\endgroup$
    – user1020500
    Nov 29, 2022 at 10:35
  • $\begingroup$ @user1020500 In that instance, take $X = \{0, 1, 2, \ldots\}$. In general, if you try to add numbers to get a set $N’$ with $\mathbb{N} \subseteq N’$, $N’$ won’t satisfy 5, since we can take $X = \mathbb{N}$. $\endgroup$
    – Mark Saving
    Nov 29, 2022 at 16:34
  • $\begingroup$ @MarkSaving What if the set was $A = \{0,S(0),S(S(0)),...\} \cup \{a,b\}$ with $S(a) = b$ and $S(b) = a$. Would it be sufficient to show that $S = \{ n \in \mathbb{N} \mid S(n) \neq a\}$ is equal to $\mathbb{N}$? and thus that $A$ is not a subset of $\mathbb{N}$? Would such a proof rely on the assumption that $a \neq 0,S(0),....$? What about $A = \{0, S(0),S(S(0)),...\} \cup \{\star\}$ where $S(\star) = \star$? $\endgroup$
    – Promethèus
    Jul 18 at 15:23
  • 1
    $\begingroup$ @DiegoCimadom Suppose we have elements $a, b \in \mathbb{N}$ such that $a = S(b)$ and $b = S(a)$. Then show using 5 that $\mathbb{N} \subseteq \mathbb{N} \setminus \{a, b\}$. This is a contradiction. For your $\star$ example, apply the previous result with $a = b = \star$. $\endgroup$
    – Mark Saving
    Jul 18 at 20:59
  • $\begingroup$ @MarkSaving Thanks for the reply. I think this is clearer than what I had. However, I feel like we are still relying on the assumption that $\star \neq 0$ and no successor of zero is equal to $\star$. Should I state these as well or are they implicit in the set theoretic notation $A = \{0, S(0),S(S(0)),...\} \cup \{\star\}$? $\endgroup$
    – Promethèus
    Jul 19 at 10:04

You must log in to answer this question.

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