# Statement equivalent to Induction Principle

How to prove that the following statement is equivalent to Induction principle?(I'v alredy done that IP $\Rightarrow$ Statement)

For every non empty $A\subset \mathbb{N}$ we have $A-s(A) \neq \emptyset$ where $s$ is the injective function in Peano Axioms($s(n)=n+1$)

-
What is your formulation of the induction principle? – lhf Jan 16 '12 at 18:44
If $1 \in A , n \in A \rightarrow s(n) \in A$ then $A = \mathbb{N}$ – Jr. Jan 16 '12 at 18:47

Assume the statement, and suppose that $1\in A$, $n\in A\to s(n)\in A$, and $A\ne\mathbb{N}$. Let $B=\mathbb{N}\setminus A$; clearly $B\ne\varnothing$, so $A\setminus s[A]\ne\varnothing$, so $B\setminus s[B]\ne\varnothing$. Fix $b\in B\setminus s[B]$.

You have as an axiom that $\mathbb{N}\setminus s[\mathbb{N}=\{1\}$, and $b\ne 1$ (since $1\in A=\mathbb{N}\setminus B$), so $b\in s[\mathbb{N}]$, i.e., $b=s(n)$ for some $n\in\mathbb{N}$. Now $b\notin s[B]$, so $n\notin B$, and therefore $n\in A$. But then the hypothesis on $A$ ensures that $s(n)\in A$, i.e., that $b=s(n)\in A\cap B=\varnothing$, which is absurd. This contradiction shows that in fact $A$ must be all of $\mathbb{N}$.

(Your book introduces the natural numbers in a somewhat unusual way, which accounts for the confusion in the answers and comments..)

-
Thanks Brian.What is the "usual" way to define the Natural Numbers? – Jr. Jan 18 '12 at 19:06
If it’s not done in a broader set-theoretic framework, it’s generally done with the Peano axioms in something like this form. One important difference for your problem is that as Henning said, the usual axioms don’t say that $0$ (or $1$) is the only non-successor; this fact, which is built into your version, has to be proved in the usual version, and the proof requires the induction axiom. – Brian M. Scott Jan 18 '12 at 19:19

It's not equivalent to the induction principle.

The induction principle essentially says that applying the successor function to the smallest natural number eventually produces every natural number; i.e., it says that $\mathbb{N}=\{0, s(0), s^2(0), s^3(0), \dots\}$. The statement you give, on the other hand, says that every nonempty subset $A \subset \mathbb{N}$ has an element that is not the successor of any element of $A$: $$A-s(A)\neq\emptyset \equiv \exists_{n\in A}[n \notin s(A)]\equiv\exists_{n\in A}\forall_{m\in A}[n\neq s(m)].$$ But this is strictly weaker than the induction principle. For instance, it still holds if you take $s(n)=n+2$, or indeed any increasing injection on the natural numbers. There will still be a smallest element (in the ordinary sense) in any nonempty $A\subset\mathbb{N}$, whose predecessor (in the sense of $s^{-1}$) will either not exist or not be in $A$. But if $s(n)=n+2$, the induction principle no longer holds.

-
I'm supposing the existence of the function $s$ and that $\mathbb{N} - s(\mathbb{N})=1$ – Jr. Jan 16 '12 at 19:51
@Jr, but how do you know that 0 (or 1, if you want) is the only natural number that is not a successor -- or in other words that every natural number is either 0 or a successor? Usually, this not an axiom, but a theorem which is itself proved by induction. So you cannot assume it as given when you're trying to derive the induction principle from something else. – Henning Makholm Jan 16 '12 at 20:10
@HenningMakholm in my book(Curso de Analise Real,E.Lages Lima),the Naturals are introduced in the form $(\mathbb{N},s)$ where $s$ is a injective function,and $\mathbb{N} - s(\mathbb{N})$ is one element(he called it '1'),and the Induction Principle holds – Jr. Jan 16 '12 at 23:20