Prove by contradiction that there is no set B of counting numbers such that if n is an element of B, then (n-1) is an element of B.

Printable View

- March 8th 2009, 06:38 PMnoles2188Counting numbers/set proof
Prove by contradiction that there is no set B of counting numbers such that if n is an element of B, then (n-1) is an element of B.

- March 9th 2009, 03:38 AMGrandadProof by induction and contradiction
Hello noles2188In fact,

*is*such a set (*see the Note below), so we must assume that .

So, let us assume that , and . (In other words, let's assume the opposite of what we want to prove.)

Then let be the propositional function:

Then by hypothesis

Now is true for some

So, by induction is true

is true . But . Contradiction. Therefore the original assumption is false.

Grandad

*Note: the proposition is true whenever is false. So if , the proposition is true, because is always false. It seems a bit crazy at first sight, but it is OK!