# Peano axioms-Mathematical Induction

This is from the book we're using in my Analysis class:

The Peano Axioms of the set $\Bbb N$ are:

$1.$ Every natural number has a successor, i.e. $\forall n\in\Bbb N, \exists!s(n)\in\Bbb N$ and if $s(n)=s(m)$ then $n=m$

$2.$ There exists the first element of the set $\Bbb N$ denoted as $1$, i.e. $1\in\Bbb N$. That is the only element that is not the successor of a natural number.

$3.$ The axiom of Mathematical Induction is valid:

Let $S\subseteq\Bbb N$ such that

$1)$ $1\in S$

$2)$ $\forall n\in\Bbb N,n\in S\Rightarrow(s(n)\in S)$.

Then $S=\Bbb N$

I don't understand the third axiom. Doesn't it just repeat the first two axioms but for set $S$? What happens if we leave out the third axiom? Would that mean that there exists a set $\neq\Bbb N$ for which the first two axioms are true?

• The "axiom" of mathematical induction in reality is not an axiom, it is a scheme, i.e. a infinite collection of axioms. – Masacroso Oct 8 '16 at 10:59
• @Masacroso: Only in first order logic. – celtschk Oct 8 '16 at 11:55
• I don't want to disturb celtschk's post too much so if you want to know more let me know here and I'll add you to the Logic chat-room at chat.stackexchange.com/rooms/44058/logic where we can continue informal discussion. – user21820 Oct 8 '16 at 16:43
• @user21820 Yeah I want to know more. I understand what you said about isomorphic structures, but I still don't completely understand the Peano Axioms. – lmc Oct 8 '16 at 17:16
• I've added you to the chat-room. Let's continue there.. I should say that I don't have that much time to spare this few weeks, so I hope you don't mind waiting till next month. In the meantime, I'll say a bit about PA, and feel free to ask anything to clarify. – user21820 Oct 9 '16 at 5:58

Consider the set $\mathcal{N}$ of complex numbers with the following properties:

• Both the real part and the imaginary part are integer.

• The imaginary part is non-negative.

• If the imaginary part is $0$, the real part is positive. Otherwise, it's an arbitrary integer.

Further, be $s(n) = n+1$.

Claim: $\mathcal N$ fulfils the first two axioms,

Proof:

Axiom 1:

Assume $n\in\mathcal N$.

• $s(n)$ doesn't change the imaginary part. And $s(n)$ increases the real part by $1$, giving an integer again. So obviously $s(n)$ has real and imaginary part integer.

• Since the imaginary part is unchanged, it stays non-negative.

• If the real part of $n$ is positive, so is the real part of $n+1$. This especially holds for zero imaginary part.

Therefore $s(n)\in\mathcal N$.

Axiom 2:

• Clearly $1\in\mathcal N$. Furthermore, $0\notin\mathcal N$, therefore there is no element $k\in \mathcal N$ such that $s(k)=1$

• If $n\in\mathcal N$ and $n\ne 1$, then either its imaginary part is zero and the real part is larger than $1$, thus $n-1\in\mathcal N$. Or the imaginary part is positice, then again $n-1\in\mathcal N$ as $n-1$ of course again has an integer real part. But $s(n-1)=n$, therefore we have a $k\in\mathcal N$ such that $s(k)=n$, namely $k=n-1$.

So we see, $\mathcal N$ fulfils both axioms.

However, $\mathcal N$ does not fulfil the induction axiom. In particular, the subset $S=\{n\in\mathcal N|\Im n=0\}$ (which is easily seen to be the usual $\mathbb N$) fulfils the conditions of the axiom, as it contains the number $1$ and for each $n\in S$, also $s(n)\in S$, but clearly $S\ne\mathcal N$, as e.g. the imaginary unit $i\in\mathcal N$ but $i\notin S$.

• I just don't understand this part: But $s(n-1)=n$, therefore we have a $k\in\mathcal N$ such that $s(k)=n$, namely $k=n-1$. What does that show us? – lmc Oct 8 '16 at 13:45
• @Now_now_Draco_play_nicely: If shows us that$1$ is the only element of $\mathcal N$ that is not the successor of another element of $\mathcal N$. Which is part of the second axiom. – celtschk Oct 8 '16 at 14:20
• Sorry to bother you again, but your answer is not complete. The question is wrong in the first place because there are even structures that satisfy Peano's Axioms but are not the natural numbers! However, every such structure (with the second-order induction axiom and full second-order semantics) is isomorphic to the natural numbers, and that is the precise sense which we should be looking at. For your answer, you have therefore not shown what is needed; you need to show that your structure is not isomorphic to the natural numbers. – user21820 Oct 8 '16 at 14:32
• @Now_now_Draco_play_nicely: Two structures are isomorphic if you can find a one-to-one correspondence from everything in one to the other. For example if I have a structure whose objects are the strings "🍎", "🍎🍎", "🍎🍎🍎", ..., and whose successor function is defined as the operation of adding an extra "🍎" at the back, then my structure is isomorphic to the natural numbers ("isomorphic" means "equal form") even though they are technically two different things. The whole idea of axiomatization is to describe the abstract properties of structures and ignore the concrete forms they may have. – user21820 Oct 8 '16 at 16:33
• @Now_now_Draco_play_nicely: In this example the correspondence would map $1$ to "🍎" and $2$ to "🍎🍎" and so on, and you can check that the axioms hold for my structure in the same way it holds for the natural numbers. That is after all the original motivation of defining the natural numbers, to abstract out the process of counting. It is nice if the axiomatization essentially determines the structure, meaning that all structures satisfying the axioms are isomorphic. The second-order Peano axioms have this nice feature, but in general this may not be so and you should not expect it! – user21820 Oct 8 '16 at 16:40

With only your first two axioms (usually stated as four axioms), you may have one or more "junk terms" thrown in along with the natural numbers. Without your third axiom, you would not, for example, be able to rule out the possibility that, for some junk term $x\in N$, you might have $s(x)=x$. Your third axiom has the effect of filtering out these terms. Remaining would be only $1$ or those terms that can be reached by starting at $1$ and repeatedly going from one number to its immediate successor. (See "What is a number again?" at my math blog)