induction by absurd

• Jan 19th 2006, 09:16 AM
SkyWatcher
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!
• Jan 19th 2006, 09:48 AM
CaptainBlack
Quote:

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 $\displaystyle P(1)$ is true, and that $\displaystyle P(n) \Rightarrow P(n+1)$.

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

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

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

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

QED.