5
$\begingroup$

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?

$\endgroup$

marked as duplicate by Asaf Karagila, Amzoti, Start wearing purple, Lord_Farin, TMM May 22 '13 at 23:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ Writing from my iPhone, an idea strikes me: Knaster-Tarski fixed point theorem. $\endgroup$ – Asaf Karagila Mar 5 '13 at 3:05
  • $\begingroup$ Excellent suggestion Asaf! I'd never heard of that result before. $\endgroup$ – Zev Chonoles Mar 5 '13 at 3:29
  • $\begingroup$ Wow. Thanks for the input, I'll read this over a few times. $\endgroup$ – ljdelight Mar 5 '13 at 4:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Mar 5 '13 at 6:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.