Let P be the set of all subsets of the plane. f : P → P satisfies f(X ∪ Y) ⊇ f( f(X) ) ∪ f(Y) ∪ Y for all X, Y ∈ P (*). Show that (1) f(X) ⊇ X, (2) f( f(X) ) = f(X) , (3) if X ⊇ Y, then f(X) ⊇ f(Y), for all X, Y ∈ P. Show conversely that if f : P → P satisfies (1), (2), (3), then f satisfies (*).
Solution
Taking Y = X in (*) gives immediately that f(X) = f(X ∪ Y) ⊇ f( f(X) ) ∪ f(X) ∪ X ⊇ X, which proves (1).
It also shows that f(X) ⊇ f( f(X) ). Now put Y = f(X) in (*). Then X ∪ Y = f(X) (by (1) ), so (*) gives f( f(X) ) ⊇ Y = f(X). So we have proved (2).
Finally, if X ⊇ Y, then X ∪ Y = X, so f(X) = f(X ∪ Y) ⊇ f(Y), which proves (3).
Now assume (1), (2) and (3) and take any X, Y. Then X ∪ Y ⊇ Y, so f(X ∪ Y) ⊇ f(Y) (using (3) ). But f(Y) ⊇ Y (using (1) ), so also f(X ∪ Y) ⊇ Y. Similarly, f(X ∪ Y) ⊇ f(X). But f(X) = f( f(X) ) (using (2) ), so f(X ∪ Y) ⊇ f( f(X) ), which establishes (*).
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999