Primer napačne uporabe indukcije

Poišči kaj je narobe z naslednjim dokazom

Trditev

Vse krave so iste barve. 

Dokaz

Trditev dokažemo z indukcijo po moči množice.

Indukcija

• Baza indukcije

n=1 Očitno imajo v vsaki množici z eno kravo vse krave enako barvo

• Indukcijski korak

Predpostavimo, da za velja:

V vsaki množici krav moči n so vse krave iste barve.

Vzemimo poljubno množico krav M moči n+1 in izberimo poljubni dve kravi. Imenujmo ju Liska in Rjavka.

Množica A=M\{Liska} je moči n zato so po indukcijski predpostavki v njej vse krave iste barve npr. rjave. Označimo z B množico B=M\{Rjavka}. Velja ,zato so vse krave v rjave.

Prav tako so v B vse krave iste barve, torej iste barve kot v njeni podmnožici , torej iste barve kot v A. Ker je so tudi v M vse krave iste barve! Q.E.D.

Rešitev

Kaj je narobe z zgornjim dokazom. Da ne bi kolegom pokvarili veselja ob iskanju rešitve, je rešitev na drugi strani!