# Given $f:S\to T$ and $g:T\to S$, prove $\exists A\subseteq S, B\subseteq T$ such that $f(A)=B$ and $g(T\setminus B)=S\setminus A$ [duplicate]

The question: Let $S$ and $T$ be sets and let $f: S \to T$ and $g: T \to S$ be arbitrary functions. Prove that there is a subset $A \subset S$ and $B \subset T$ such that $f \left( A \right) = B$ and $g \left( T \setminus B \right )= S \setminus A$

My issue is that I read the problem as a statement, not a proof. I tried writing it out but I'm still stuck: $\exists \left( A \subset S , B \subset T \right) \left( f \left( A \right) = B \wedge g \left( T \setminus B \right) = S \setminus A \right)$

How do I go about proving this thing?

## marked as duplicate by Asaf Karagila♦, Amzoti, Start wearing purple, Lord_Farin, TMMMay 22 '13 at 23:00

The functions $f:S\to T$ and $g:T\to S$ induce functions on the power sets of $S$ and $T$. That is, we can consider the maps $F:\mathcal{P}(S)\to\mathcal{P}(T)$ and $G:\mathcal{P}(T)\to\mathcal{P}(S)$ defined by $F(A)=f(A)$ and $G(B)=g(B)$.

For any set $Z$, the power set $\mathcal{P}(Z)$ is a complete lattice, with the partial order being containment (i.e., given $X,Y\in\mathcal{P}(Z)$, we say that $X\leq Y$ when $X\subseteq Y$), and the join and meet being union and intersection, respectively.

The functions $F$ and $G$ are clearly order-preserving, because for any $X,Y\in\mathcal{P}(S)$, if $X\leq Y$ (i.e. $X\subseteq Y$) then $F(X)\leq F(Y)$ (i.e. $f(X)\subseteq f(Y)$), and similarly for $G$.

For any set $Z$, the function $C_Z:\mathcal{P}(Z)\to\mathcal{P}(Z)$ which sends a subset of $Z$ to its complement, i.e. the function defined by $C_Z(X)=Z\setminus X$, is order-reversing.

Combining these observations, we have that the function $H:\mathcal{P}(S)\to\mathcal{P}(S)$, defined as the composition of $$\mathcal{P}(S)\xrightarrow{\;\; F\;\;}\mathcal{P}(T)\xrightarrow{\;\;C_T\;\;}\mathcal{P}(T)\xrightarrow{\;\;G\;\;} \mathcal{P}(S)\xrightarrow{\;\;C_S\;\;}\mathcal{P}(S)$$ is an order-preserving map from a complete lattice to itself.

The key step, suggested by Asaf Karagila, is to now apply the Knaster-Tarski theorem, which implies that $H$ has a fixed point. Thus, there is some $A\in\mathcal{P}(S)$ such that $$A=H(A)=S\setminus G(T\setminus F(A)).$$ Thus, letting $B=F(A)$, we have that $f(A)=B$ and $g(T\setminus B)=S\setminus A$.

• Writing from my iPhone, an idea strikes me: Knaster-Tarski fixed point theorem. – Asaf Karagila Mar 5 '13 at 3:05
• Excellent suggestion Asaf! I'd never heard of that result before. – Zev Chonoles Mar 5 '13 at 3:29
• Wow. Thanks for the input, I'll read this over a few times. – ljdelight Mar 5 '13 at 4:31
• Zev, when I was a freshman this was the way we were taught the Cantor-Bernstein theorem. I particularly remember because in the exam we had to prove the "dual" theorem, that is assume the function is order-reversing and prove it has a fixed point. – Asaf Karagila Mar 5 '13 at 6:33