Alla hästar har samma färg

Hästparadoxen är en paradox i form av påståendet alla hästar har samma färg. Resonemanget användes av George Pólya för att visa hur subtila fel kan uppstå i induktionsresonemang.

Paradoxen

Som en utgångspunkt, notera att i en mängd innehållandes en häst, har uppenbarligen alla hästar samma färg. Antag nu att påståendet gäller för alla mängder med ett antal n hästar.

Låt det finnas n + 1 hästar i en mängd. Avlägsna den första hästen för att få n hästar. Med hjälp av induktionen kan man konstatera att alla hästar i denna mängd har samma färg.

Vad som återstår är att visa att även den avlägsnade hästen har samma färg. Detta är enkelt: lägg tillbaka hästen, avlägsna en annan häst och använd induktionsprincipen på den här mängden av n hästar. Följaktligen har alla hästar i vilken mängd n + 1 som helst, samma färg. Genom induktionsprincipen har vi visat att alla hästar har samma färg.

Förklaring

Resonemanget hänger på att de två delmängderna av hästar som används har samma färg, vilket inte gäller för en mängd bestående av två hästar. Säg att vi har en mängd bestående av häst A och häst B. Om vi tar bort häst A har vi bara häst B kvar i mängden och då har uppenbarligen alla hästar i mängden samma färg. Samma sak gäller om vi tar bort häst B. Men de två mängderna innehållandes endast häst A och häst B har inga gemensamma element, så vi kan inte vara säkra på att häst A och häst B har samma färg.

För mängder med n hästar, där n är strikt större än 2, håller dock resonemanget om det är givet att det är sant för n - 1 hästar.

Referenser

• Enumerative Combinatorics av George E. Martin, ISBN 0-387-95225-X