TITLE: 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$
QUESTION [5 upvotes]: 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?

REPLY [5 votes]: 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$.
{"set_name": "stack_exchange", "score": 5, "question_id": 320965}