すべての馬は同じ色

すべての馬は同じ色（すべてのうまはおなじいろ）とは、推論に誤りがあることから生じるパラドックスのひとつ。一見して数学的帰納法により証明されているように見えるが、決定的な誤りを含むために、明らかにおかしな主張が得られている。数学的帰納法を用いて命題を証明しようとする際に起こり得る微妙な誤謬の例として、ジョージ・ポーヤが用いた。
概要.
この間違った論証とは、次のようなものである。
5頭の馬が常に同じ色であることを証明したいとする。4頭の馬は必ず同じ色であることが、すでに証明されているとしよう。すると、5頭の馬から任意の1頭を除けば、残りの4頭は同じ色である。それを2通りの方法で行うと、同じ色だとわかる4頭の馬の集合が2種類得られる。例えば、1頭目、2頭目、3頭目、4頭目は同じ色でなければならないし、2頭目、3頭目、4頭目、5頭目も同じ色でなければならない。したがって、5頭すべての馬が同じ色であるということになる。
ところで、4頭の馬が必ず同じ色であることをどのように証明すればよいだろうか。そのためには、同じ論法を繰り返し用いればよいだろう。4頭の馬から3頭の馬を取り、3頭の馬から2頭の馬を取り、といった風に。結局馬の数は1頭になるが、それならすべての馬が同じ色であるのは明らかだ。
この論法を用いると、馬の数を増やすこともできる。6頭の馬すべてが同じ色であることも証明できるし、あるいはそれ以上に有限であるすべての馬は同じ色でなければならなくなる。
解題.
上記の論証は、暗黙のうちに「馬の部分集合2組が共通の要素を持っている」という仮定を行っている。これは馬が2頭しかいない場合には正しくない。この2頭を、馬Aと馬Bとする。馬Aが除かれたならば、残っている馬は同じ色（ひとつの色）であるということは正しい（残っているのは馬Bだけである）。馬Bが除かれたならば、残っている馬Aが単色であることも正しい。しかし、ふたつの馬の組に共通の馬はいないので、馬Aと馬Bは同じ色かもしれないし、そうでないかもしれない。
上記の推論における問題は、2組の馬の部分集合が単色であるからといって、もとの馬の集合も単色であるとした点にある。2組の馬の集合には共通部分がないかもしれないから、和集合も単色であるかどうかは分からないはずである。このパラドックスは、一般的な主張を示すために、特殊な場合のみを考えると誤りになることがある、ということを教育的に示している。5頭でうまくいった議論が、何頭でもうまくいくと考えてしまったことが誤りだったのである。