Suppose $X,Y$ are sets, and $f:X\to Y$ and $g: Y \to X$. Then there are disjoint subsets $X\_1,X\_2 \subseteq X$ with $X\_1\cup X\_2= X$ and disjoint subsets $Y\_1,Y\_2 \subseteq Y$ with $Y\_1\cup Y\_2= Y$ such that


* $f(X\_1) = Y\_1$, and
* $g(Y\_2) = X\_2$.


(This curious result is a consequence of the [Knaster-Tarski fixed point theorem](https://en.wikipedia.org/wiki/Knaster%E2%80%93Tarski_theorem).)


Can this statement be generalized to partial functions, or even binary relations $R\_1, R\_2 \subseteq X\times Y$?



Curious decomposition between two sets
Yes, I think the exact same proof goes through for binary relations $R: X \nrightarrow Y$ and $S: Y \nrightarrow X$ (which of course includes the partial function case). Each induces a monotone operation between power sets, e.g. $\exists R: PX \to PY$ takes $A \subseteq X$ to $\{y: \exists\_{x \in A} R(x, y)\}$. Letting $\neg\_X$ denote complementation on subsets $A \subseteq X$, we obtain a covariant (i.e. monotone) operation 


$$\neg\_X \circ \exists S \circ \neg\_Y \circ \exists R: PX \to PX$$ 


which by the Knaster-Tarski theorem has a fixed point $X\_1 \in PX$. Put $Y\_1 = (\exists R)(X\_1)$ and $Y\_2 = \neg\_Y Y\_1$ and $X\_2 = (\exists S)(Y\_2)$. Then $X\_2 = \neg\_X X\_1$ by the fixed point equation. 


