Homochromicty
Given
an operator C(m), a set Sn =
{s1, s2, �, sn}
is called homochromatic if C(si)
= C(sj) for any i
and j such that 1 � i, j � n.� si
and sj are said to be of
the same color, and it is an
identity that C(m) = C(m) for all m.
Example
Show
that the set Hn' = {h1', h2', �, hn' } of all horses is homochromatic.
Proof by Induction
Define
a set of horses Hm = {h1, h2, �, hm}
in Hn such that hm � Hn
for 1 � m < n, and consider
the case where m = 1 (the base
case).� Then Hm = H1
= {h1} and C(h1)
= C(h1).� Thus Hm is homochromatic for m = 1.
Assume, then, that Hm
is homochromatic for any m (the
inductive hypothesis).
Consider
now the sets Hm = {h1, h2, �, hm}
and Hn = {h2, h3, �, hm
+ 1} = {h2, h3, �, hn}.� These sets,
each with m elements, must also be
homochromatic by induction, since it has been shown that sets with m
elements are homochromatic.� Therefore
it remains only to show that C(h1) = C(hn).� But C(h1) = C(hi) = C(hn)
for all hi such that 2 � i � m (the
inductive step).� Thus, the entire set Hn must be homochromatic.� Since we may assume that there are a finite number of horses the
set Hn must contain the
set Hn' �of all horses, and all horses must be the same color.