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
    The chain as currently set up doesn't make sense: there's no reason $g^{-1}$ should be defined on $x$, because $x$ needn't be in the image of $g$.2012-10-03
  • 0
    Kevin- I edited my question, it is defined on x. Sorry about that.2012-10-03
  • 0
    OK, but you specifically said $x$ is an arbitrary element of $X$, while $g^{-1}$ is only defined on $g(Y)$, and it was not assumed that $g$ is surjective. How am I to interpret the chain for $x \notin g(Y)$?2012-10-03
  • 0
    I see what you mean, I neglected the arbitrary part and fixed an x and assumed it mapped to Y. So I evaluated my chain, incorrectly. But that leaves me more confused, how I am supposed to determine the elements of the chain? OR at least know if they finite, infinite, or zero?2012-10-03
  • 0
    The chain doesn't even exist as you've set it up-there is no such object as $g^{-1}(x)$ for arbitrary $x$.2012-10-03
  • 0
    I didn't set up the chain, it's in the book like that. Maybe that's the point of the question then: when I'm supposed to explain why the elements on the left side may be zero, finite, or infinite, I am supposed to explain each case separately? For example, in the case where x is not defined in g^(-1)(x), there wold be zero elements...does this seem correct?2012-10-03
  • 0
    Actually, yes, I guess so. Then you have cases where the chain is finite and oscillates, as in the example you display, and also ones in which it just stops being defined, along with those when it's always defined and never repeats.2012-10-03
  • 0
    Okay, that clarifies things. What would cause the last case though? It's defined and never repeats?2012-10-03
  • 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