1. ## Counting 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.

2. ## Proof by induction and contradiction

Hello noles2188
Originally Posted by noles2188
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.
In fact, $B = \oslash$ is such a set (*see the Note below), so we must assume that $B \ne \oslash$.

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

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

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

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

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

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

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