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.

  • 2
    $\begingroup$ Is $x-3$ always a natural number? $\endgroup$ Oct 6, 2014 at 19:47
  • $\begingroup$ @JyrkiLahtonen it doesn't specific whether it always is or not, so I'm assuming it is. $\endgroup$ Oct 6, 2014 at 19:49
  • 3
    $\begingroup$ @user3434743 It was a rethorical question. The comment is a hint to make you see where the mistake is. $\endgroup$
    – Git Gud
    Oct 6, 2014 at 19:50
  • $\begingroup$ 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? $\endgroup$ Oct 6, 2014 at 19:51

1 Answer 1


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.

Thus you actually use integers, where the proposition that every nonempty subset has a smallest element is false.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .