0
$\begingroup$

Using Schröder-Bernstein Theorem. Assume there exists a 1-1 function $f:X\to Y$ and another 1-1 function $g:Y\to X$. If we define $f^{−1}(y)=x$, then $f^{−1}$ is a 1-1 function from $f(X)$ onto $X$, and similarly $g^{-1}$ is a function from $g(Y)$ onto $Y$. Follow the steps to show that there exists a 1-1, onto function $h:X\to Y$.

Let $x \in X$ be arbitrary. Let the chain $C_x$ be the set consisting of all elements of the form

$\dots,f^{−1}(g^{−1}(x)),g^{−1}(x),x,f(x),g(f(x)),f(g(f(x))),\dots$

Show that any two chains are either identical or completely disjoint.

I've been stuck on this problem for a while, can anyone give me a hint that will push me in the right direction?

Thanks.

2 Answers 2

1

It is not mentioned in the problem, but apparently $X$ and $Y$ are assumed to be disjoint. If they are not disjoint, the claim becomes false and distinct chains need not be disjoint.

We can define $h\colon X\cup Y\to X\cup Y$ by $h(x)=\begin{cases}f(x)&\text{if }x\in X\\g(x)&\text{if } x\in Y\end{cases}$ Then $Cx$ is simply the set of all $y\in X\cup Y$ such that $x=h^n(y)$ for some $n$ or $y=h^n(x)$ for some $n$. We conlude that by symmetry also $x\in Cy$ (where we now define $Cy$ also for the case $y\in Y$, not just $y\in X$). Hence the relation $xRy\iff y\in Cx$ is symmetric. It is also trivially reflexiv. Finally, it is trasitive: If $y\in Cx$ and $z\in Cy$ then $y=h^n(x)$ or $x=h^n(y)$ for some $n$ and also $z=h^m(y)$ or $y=h^m(z)$ for some $m$. We may assume wlog. that we have chosen $(y,n)$ such that $n$ is minimal.

  • If $y=h^n(x)$ and $z=h^m(y)$, we conclude $z=h^{m+n}(x)\in Cx$.
  • Similary, if $x=h^n(y)$ and $y=h^m(z)$, we conclude $x=h^{m+n}(z)$ and hence $z\in Cx$.
  • If $y=h^n(x)$ and $y=h^m(z)$. If $n>0$ and $m>0$, we conclude (using injectivity of $h$) that $y':=h^{n-1}(x)=h^{m-1}(z)$, contradicting minimality of $n$. Hence $n=0$ or $m=0$, i.e. $y=x$ or $y=z$, whence $xRz$.
  • If $x=h^n(y)$ and $z=h^m(y)$. If $n>0$ and $m>0$, we conclude that $x=h^{n-1}(h(y))$ and $z=h^{m-1}(h(y))$, that is $y':=h(y)\in Cx\cap Cx'$, thus again there is a contradiction to the minimality of $n$. Hence $n=0$ or $m=0$, i.e. $y=x$ or $y=z$, whence $xRz$.

Now that we have shown that $R$ is an equivalence relation, we observe that the chains are just the equivalence classes.

0

Say that $x$ is in two chains, $Ca$ and $Cb$. That means that, for example, $x$ is in the form $f(g(f(g(f(a)))))$ or something similar, since it's in $Ca$. But then $a$ is of the form $f^{-1}(g^{-1}(f^{-1}(g^{-1}(f^{-1}(x))))))$ so $a$ is in the chain generated by $x$. So is $b$, and so $Ca=Cx=Cb$.

  • 0
    Thanks, I don't understand how you're defining the chains though. For instance, what does it mean for x to be in Ca?2012-10-14