1.3 Well Ordering Principle

A Bogus Well Ordering Principle Proof


The Fibonacci numbers

\(0, 1, 1, 2, 3, 5, 8, 13, \ldots \)

are defined as follows. Let \(F(n)\) be the \(n^{th}\) Fibonacci number. Then

  • \(F(0) ::= 0\)
  • \(F(1) ::= 1\)
  • \(F(n) ::= F(n-1) + F(n-2), \;\; \text{ for } n \geq 2 \text{ } (\star)\)


Identify which step(s) contain the logical error!

Bogus Claim: Every Fibonacci number is even.

Exercise 1

Steps 1 through 10 contain no logical errors. The fatal flaw is in the final step 11. The proof only shows that there is a minimum \(m\) in \(C\) and it is not 0. The assumption that \(m \geq 2\) leads to a contradiction; it leaves the case \(m = 1\) unexamined, while in fact, \(1 \in C\). (The supposition that "\(m \geq 2\) so the definition (*) of \(F(m)\) applies" is no excuse for ignoring the case \(m = 1\).)

If you said that step 7 contains a logical error, you were on the right track. The natural place to handle the case \(F(1)\) would have been right after step 6. But the the proof explicitly avoided the case \(m = 1\), by saying, "suppose \(m \geq 2\)." However, there is no logical error in line 7: it is simply the beginning of a proof for the case when \(m \geq 2\). On the other hand, it's reasonable to say that line 7 is the place where the proof makes an organizational, or perhaps strategic, error because it skips the \(m = 1\) case.