ABSTRACT
Exercise 742: The proof is by induction on n. For n ≥ 1, let S(n) be the statement that if P([n]) is n-colored, there are sets A,B ∈ P([n]) monochromatic with A ( B. Base step: When n = 1, if P([1]) = {∅, {1}} is 1-colored, then ∅ and {1} are the same color and ∅{1}. Inductive step: Fix k ≥ 1, and suppose S(k) is true. Let
∆ : P([k + 1])→ [k + 1]
be a given (k + 1)-coloring. If for any A ( [k + 1], if ∆(A) = ∆([k + 1]), then B = [k + 1] are as needed. So suppose that all proper subsets of [k + 1] are colored differently from [k+1]; thus all proper subsets of [k+1] are k-colored. In particular, all subsets of [k] are k-colored by ∆, and so by induction hypothesis S(k), there exist two sets A,B ⊂ P([k]), A ( B, that are colored the same, and since P([k]) is contained in P([k + 1]), the statement S(k + 1) is again confirmed.
