Thread: 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!

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 is true, and that .

Let be the subset of for which is false.
Then by the axiom there is a smallest element of ,
and by assumption.

Then is true and is false, which is
a contradiction of the assumption that .

Hence there is no such element and so there is no such
set . And so is true for every .

(Note here we are taking if we want to
use , we would have to start with
being true rather than in our base case.)

QED.