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

- Mar 8th 2009, 05: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.

- Mar 9th 2009, 02:38 AMGrandadProof by induction and contradiction
Hello noles2188In fact, $\displaystyle B = \oslash$

*is*such a set (*see the Note below), so we must assume that $\displaystyle B \ne \oslash$.

So, let us assume that $\displaystyle \exists B \subseteq \mathbb{N}, (B \ne \oslash)$, and $\displaystyle (n \in B) \Rightarrow (n-1) \in B$. (In other words, let's assume the opposite of what we want to prove.)

Then let $\displaystyle P(n)$ be the propositional function: $\displaystyle n \in B$

Then by hypothesis $\displaystyle P(n) \Rightarrow P(n-1)$

Now $\displaystyle B \ne \oslash \Rightarrow P(k)$ is true for some $\displaystyle k \in B$

So, by induction $\displaystyle P(n)$ is true $\displaystyle \forall n \le k, n \in \mathbb{Z}$

$\displaystyle \Rightarrow P(0)$ is true $\displaystyle \Rightarrow 0 \in B$. But $\displaystyle 0 \notin \mathbb{N}$. Contradiction. Therefore the original assumption is false.

Grandad

*Note: the proposition $\displaystyle (p \Rightarrow q)$ is true whenever $\displaystyle p$ is false. So if $\displaystyle B = \oslash$, the proposition $\displaystyle (n \in B \Rightarrow (n-1) \in B)$ is true, because $\displaystyle n \in B$ is always false. It seems a bit crazy at first sight, but it is OK!