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
    "Then for every $f(A)\subseteq Y$, there exists a $y\in Y-f(A)$ such that $g(y)\notin X-A$" - That's wrong. To conclude this, you would need $g(Y-f(A))\not\subseteq X-A$ instead of $g(Y-f(A))\neq X-A$.2011-02-18
  • 1
    I know this exercise with the additional assumption that $f$ and $g$ are injective. Are you sure you didn't forget that part?2011-02-18
  • 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
    @awllower: The control sequence "\subsetex" isn't being recognized -- could you rewrite that please?2011-02-18
  • 0
    Sorry. It has been corrected.2011-02-18
  • 0
    I think we can actually find a fixed point such as the set {A$\in P(X)$|$A\subseteq h(A)$}.2011-02-18
  • 0
    Since the time to edit has passed, I have to post a new comment, apology for any inconvenience here.2011-02-18
  • 0
    And this may be found [here](http://books.google.com.tw/books?id=oEo_AQAAIAAJ&dq=foundations+of+higher+mathematics&hl=zh-TW&ei=VAFeTe-3DYKGvAPt8cnFDQ&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC4Q6AEwAA)2011-02-18
  • 0
    @awllower: That link seems to only lead to a listing of the book, not its content. I don't have that book. The statement makes no sense in that form. $h$ maps $P(X)$ to $P(X)$, so a fixed point of $h$ would have to be an element of $P(X)$, but the set you display is a subset of $P(X)$. Even if we interpret that to mean that this subset is mapped onto itself by $h$ (which I don't think would be relevant to the question), that's not true, since $\{\}$ is in that set but for $g$ not surjective $\{\}$ is not in the image of that set (since it is not in the image of $h$).2011-02-18
  • 0
    @joriki, thanks for that helpful link. I went through the proof, but I'm still unclear on one point. In (3), there is the equality $g(Y-f(A))=X-h(A)$. Why does this follow? Surely it can't be from $h(A)=X-g(Y-f(A))$?2011-02-18
  • 0
    Never mind, I figured it out. Thank you again.2011-02-18