# Find the mistake in this proof.

I need help with finding the mistake in this proof.

Statement: All natural numbers are divisible by 3.

Proof: Suppose, for the sake of contradiction, the statement were false. Let X be the set of counterexamples, i.e., X = {x ∈ N | x is not divisible by 3}. The supposition that the statement is false means that X ≠ Ø. Since X is a non-empty set of natural numbers, it contains a least element x.

Note that 0 ∉ X because 0 is divisible by 3. So x ≠ 0. Now consider x - 3. Since x - 3 < x, it is not a counterexample to the statement. Therefore x - 3 is divisible by 3; that is, there is an integer a such that x - 3 = 3a. So x = 3a + 3 = 3(a + 1) and x is divisible by 3, contradicting x ∈ X.

• Is $x-3$ always a natural number? Oct 6, 2014 at 19:47
• @JyrkiLahtonen it doesn't specific whether it always is or not, so I'm assuming it is. Oct 6, 2014 at 19:49
• @user3434743 It was a rethorical question. The comment is a hint to make you see where the mistake is. Oct 6, 2014 at 19:50
• More specifically: $x$ has to be a natural number (that was given). Does that imply that $x-3$ is also a natural number? Under what conditions could that fail? Why is that important? Oct 6, 2014 at 19:51

In your proof, you switch between natural numbers and integers. You claim there must be a smallest element $x\in X$, since $X\subset\mathbb{N}$. However, this does not mean that $x-3\in\mathbb{N}$, because, in $\mathbb{N}$, $x-3$ does not necessarily exist.