Minimal Counterexamples

Minimal Counterexample

See the discussion on page 192.

Well ordering principle

Proposition: Suppose that \(X\) is a non-empty set of natural numbers. Then there exists \(x\in X\) such that, for all \(y\in X\), \(x\le y\). In other words, \(X\) has a minimal element.

Proof: We will prove that if \(X\) does not have a minimal element, then it is empty, by strong induction.

• Let \(P(n)\) be the statement \(n\not\in X\).
• Suppose that \(X\) does not have a minimal element. Then \(P(1)\) is true, because if \(1\in X\), then \(1\) would be a minimal element (there are no natural numbers smaller than \(1\)).
• Suppose that all of \(P(1),P(2),\ldots, P(n)\) are all true. This means that none of \(1,2,\ldots,n\) are in \(X\). But then \(n+1\not\in X\), since if it were, it would be a minimal element. Thus \(P(n+1)\) is true.
• We’ve proved by (strong) induction that \(P(n)\) is true for all \(n\). Therefore no element of \(\mathbb{N}\) belongs to \(X\), so \(X\) is empty.

This proposition is called The Well-Ordering Principle. It is equivalent to the axiom of induction. Can you prove the axiom of induction assuming the Well-ordering principle?