Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$)

share|cite|improve this question
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
up vote 2 down vote accepted

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..)

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.