Some “bugs” of induction

March 29, 2011

Fact: All sets of horses contain only white horses.
Proof (by induction on the size of the set): (Base) I see a white horse => Trivial. (Induction) Consider a set $A$ of horses, and any nontrivial set cover of $A$ (i.e. a set cover containing more than one set, and in which no set is $A$ itself): by induction, every set in the set cover contains only white horses, therefore, by transitivity, $A$ contains only white horses. Q.E.D

Fact: All sets of horses contain only horses with the same color of the mantel.
Proof (by induction on the size of the set):  (Base) Every set containing only one horse contains only horses with the same color of the mantel. (Induction) Use the same set-cover+transitivity argument as above. Q.E.D.

%d bloggers like this: