Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem A. 464. (November 2008)

A. 464. Let H a set and denote by P(H) the family of all subsets of H. Suppose that f and g are P(H)\toP(H) maps such that f(X)\subsetf(Y)\subsetH and g(X)\subsetg(Y)\subsetH whenever X\subsetY\subsetH. Prove that there exist sets A,B\subsetH for which f(A)=H\B and g(B)=H\A.

(5 pont)

Deadline expired on December 15, 2008.


Solution. For every X\subsetH, let h(X)=H\g(H\f(X)). Our goal is to construct a set A\subsetH for which h(A)=A,

The function the function h s nondecreasing, i.e. h(X)\subseth(Y) whenever X\subsetY\subsetH.

Call a set X\subsetH "nice" if X\subseth(X) and let A be the union of all nice sets:

 A = \bigcup_{X\subset H: ~ X\subset h(X)} X.

We will show that h(A)=A. Let A'=h(A).

For every nice set X we have X\subsetA and thus X\subseth(X)\subseth(A). Then

 
A = \bigcup_{X\subset H: ~ X\subset h(X)} X \subset
\bigcup_{X\subset H: ~ X\subset h(X)} h(X) \subset
\bigcup_{X\subset H: ~ X\subset h(X)} h(A) = h(A).

Therefore, the set A is nice, A\subseth(A).

Since h is nondecreasing, the set A' is nice as well; A'=h(A)\subseth(A'). On the othe hand, A is the union of all nice sets, so A'=h(A) is a subset of A.

Hence, A\subseth(A) and h(A)\subsetA. Therefore A=h(A).


Statistics:

9 students sent a solution.
5 points:Backhausz Tibor, Bodor Bertalan, Éles András, Tomon István, Tossenberger Anna.
2 points:2 students.
0 point:2 students.

Problems in Mathematics of KöMaL, November 2008