User:IssaRice/Faulty mathematical induction proof example

Problem statement

Consider the following "proof":

Proposition. Let $b,c$ be positive integers. Then $bc>b$.

Proof. We fix $b>0$ and induct on $c$. For the base case when $c=0$, the result is vacuously true. Now suppose inductively that we have the result for $c$. Then for $c+1$ we need $b(c+1)>b$. But $b(c+1)=bc+b>bc$ since $b>0$. Also, $bc>b$ by induction hypothesis. Therefore, $bc+b>bc>b$. This closes the induction.

This proposition is obviously false, since for $c=1>0$ we have $bc=b$, not $bc>b$. The problem is to figure out where the induction "proof" above goes wrong.

Diagnosis

The problem with the proof above is that we are inconsistently bringing in the hypothesis $c>0$. This means that we are "doing induction" but without a fixed predicate $P(c)$, which makes the proof invalid.

When proving the vacuous