马皆同色问题

数学归纳法是作为数学公理在 佩亚诺（Peano）自然数定义中的第五条性质，但是它原本的历史远远要比佩氏公里体系提出的时间更早——但是这一点都不奇怪，毕竟公理化的定义常常是对过去的总结。
另一套公理体系中(ZFC)，归纳法是良序原理的一个推论。

良序原理: 自然数集的每个非空子集都有个最小元素，即自然数在其通常意义上的大小序关系下构成一良序集

归纳法的基本叙述
命题 P 对整个数系 成立,如果

• P(0) 成立
• 如果P(n)成立，那么P(n + 1)成立

第一条表示起点，命题成立
第二条表示从当前推到演绎到下一个这个过程是成立

类似多米诺骨牌一样，只要牌被推一下，能压倒另一张牌，每两张牌之间都是这个机制，并且你可以推倒第一张牌，那么整个骨牌都能被推倒。

马皆同色问题是一个关于错误使用数学归纳法的例子，大概叙述如下

如果每匹马有一种颜色，那么断言所有马的颜色都是一样的。
证明：如果马只有一匹，显然命题成立，因为马有一种颜色。假设命题对于 n 匹马的情形是成立的，那么对于 n + 1 的情形，我们用序号将这些马标记 {1, 2, 3, ..., n, n + 1}，将这组序号分成两部分：{1,2,3,..., n} 及 {2,3,4, ..., n + 1}, 分别有 n 匹马，由归纳假设，它们是同色的，又，有两组序号存在公共部分, 即有交集{2,3,..., n} 所以整个 {1,2,3, ..., n, n + 1}必定是同色的。

乍看这个推理好像是顺理成章，没毛病，能引起普通人注意的是，这是一个明显错误的结论，如果不细致地审查，就会导致“归纳法失效”，“数学大厦崩溃”等等民科论断。设想如果命题不是那么明显的对错，这种隐秘的推证错误会引起很多“民科”错误，甚至专业数学工作者也触犯。

上述的推证过程，我标记黑色加重部分的陈述是存在问题的，乍看没问题，实则如果 n = 1，上面讨论 n + 1 即 2的情况的时候，这么分割并没有出现公共部分，它是两个不相交的集合{1}和{2} 因而不能得到后面的结论，相当于多米骨牌推到第二步就推不动。

如何让这个“骨牌”可以推下去？ 简单的做法就是对第二步做文章，让它能推下去，于是要假设{1}, {2}同色, 那么可以加一个前提：任何两匹马的颜色都是相同的，那么所有马的颜色相同。这个结论没毛病——甚至有点太显然，以至于像一句废话。

为什么这么叙述不对：如果前两匹马的颜色相同，那么所有马颜色相同。