7
$\begingroup$

This is a little exercise I've been fiddling with for a while now.

Let $f\colon X\to Y$ and $g\colon Y\to X$ be functions. I want to show that there are subsets $A\subseteq X$ and $B\subseteq Y$ such that $f(A)=B$ and $g(Y-B)=X-A$.

Of course, if $f$ is surjective, then taking $A=X$, one has $f(A)=B=Y$ and $g(Y-Y)=g(\emptyset)=\emptyset=X-X=X-A$, and you're done. So I suppose $f$ is not surjective.

I tried to approach it by contradiction. It seems that for any $A\subseteq X$, there is obviously a $B\subseteq Y$ such that $f(A)=B$, so if the result is not the case, for each pair of subsets $A$ and $f(A)$, we must have $g(Y-f(A))\neq X-A$. Then for every $f(A)\subseteq Y$, there exists a $y\in Y-f(A)$ such that $g(y)\notin X-A$. This would imply $g(y)\notin X \lor g(y)\in A$, but since $g(y)\in X$, we must have $g(y)\in A$.

The only thing I can glean from this is that $g$ is surjective, since for any singleton $\{x\}\subseteq X$, we could then find a $y\in Y-\{f(x)\}$ such that $g(y)=x$. But I don't quite see how to get a contradiction. What direction should I head? I attempted to apply the fact that a monotone function on power sets has a fixed point, but that only seems to apply then the function maps from a power set into itself. Thanks!

  • 0
    @Stefan Walter, There is no mention of $f$ and $g$ being injective. Do you mind explaining how to do it in the case that they are? I'm curious to see that, perhaps it would be helpful.2011-02-18

1 Answers 1

4

There's a proof here (where "isotonic" means "order-preserving"). Theorem (F1) there is a corollary of the Knaster–Tarski theorem.

  • 0
    Never mind, I figured it out. Thank you again.2011-02-18