1
$\begingroup$

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

I'm asking about part (a) of the problem:

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

$ ....,\, f^{(-1)}(g^{(-1)}(x)),\, g^{(-1)}(x),\,x,\,f(x), g(f(x)),\,f(g(f(x))),\,.... $

Explain why the (distinct) number of elements to the left of $x$ in the above chain may be zero, finite, or infinite.


Since the functions are 1-1, say $x$ map to a distinct $y$ in $Y$. So evaluating the chain (the $x$ in bold separates the left and right sides of the chain), you get: $ ....x,\, y,\, \textbf{x},\, y,\, x,\, y,\, ... $ The left side of the chain is obviously composed of the $x$ and $y$ predefined above. I don't really understand what the question means. My interpretation is that the left side of the chain is finite because the functions, being 1-1, map a distinct $x$ to a distinct $y$, so those are finitely many elements (2 in this case). But I'm not sure if I'm right. Any input? Thanks.

Edit: Sorry I didn't mention that g^(-1) is also a 1-1 function, defined g^(-1): g(X)->Y

  • 0
    See my answer...2012-10-03

1 Answers 1

0

You've already shown a case when the number of interest is finite, in particular 2: when $f(x)=g^{-1}(x)$, so that $f^{-1}g^{-1}(x)=x$ and the chain oscillates between $x$ and $f^{-1}(x)$. In the comments we've seen a case of $0$ elements to the left as well, when $x$ isn't in $g(Y)$. For the infinite case, consider something like $X=Y=\mathbb{Z}, f=g, f(n)=n+1$.

  • 0
    I see. Thank you for your help!2012-10-03