1
$\begingroup$

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

  • 0
    If $1 \in A , n \in A \rightarrow s(n) \in A$ then $A = \mathbb{N}$2012-01-16

2 Answers 2

2

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

  • 0
    If it’s not done in a broader set-theoretic framework, it’s generally done with the Peano axioms in something like [this form](http://en.wikipedia.org/wiki/Peano_axioms?banner=none#The_axioms). 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.2012-01-18
0

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.

  • 0
    @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 holds2012-01-16