# Math Help - induction by absurd

1. ## induction by absurd

here is a multipurpose pedagogic <<riddle>>

Proove That (P(1) and( P(n)=>P(n+1) for n<=1))=>(P(n) for all n natural integer)

Using this axiomatic property of N : Every subset of N admit a smallest element. (an element that belong to the subset and smaller than every element of the subset).

This is very trivial i know but this property can be used in many demonstration( x^3+y^3=z^3 as no integer solution by Fermat for exemple)

wont give the anwser!
By!

2. Originally Posted by SkyWatcher
here is a multipurpose pedagogic <<riddle>>

Proove That (P(1) and( P(n)=>P(n+1) for n<=1))=>(P(n) for all n natural integer)

Using this axiomatic property of N : Every subset of N admit a smallest element. (an element that belong to the subset and smaller than every element of the subset).

This is very trivial i know but this property can be used in many demonstration( x^3+y^3=z^3 as no integer solution by Fermat for exemple)

wont give the anwser!
By!
Suppose $P(1)$ is true, and that $P(n) \Rightarrow P(n+1)$.

Let $S \subset \mathbb{N}$ be the subset of $\mathbb{N}$ for which $P(n)$ is false.
Then by the axiom there is a smallest element $s$ of $S$,
and $s>1$ by assumption.

Then $P(s-1)$ is true and $P(s)$ is false, which is
a contradiction of the assumption that $P(n) \Rightarrow P(n+1)$.

Hence there is no such element $s$ and so there is no such
set $S$. And so $P(n)$is true for every $n \epsilon \mathbb{N}$.

(Note here we are taking $\mathbb{N}=\{ 1,2,..\}$ if we want to
use $\mathbb{N}=\{ 0,1,2,..\}$, we would have to start with $P(0)$
being true rather than $P(1)$ in our base case.)

QED.