Assume there exists a 11 function X Y and another 11 functio

Assume there exists a 1-1 function/: X -*Y and another 1-1 function g:Y rightarrow X. Follow the steps to show that there exists a 1-1. onto function h: X rightarrow Y and hence X Y. (a) The range of f is defined by f(X) = {y Y: y = f(x) for some x X}. Let y J(X). (Because f is not necessarily onto, the range f(X) may not be all of Y.) Explain why there exists a unique x X such that f(x) = y. Now define f^-1(y) = x, and show that f^-1 is a 1-1 function from f(X) onto X. In a similar way, we can also define the 1-1 function g^-1: g(X) rightarrow Y. (b) Let x X be arbitrary. Let the chain C_x be the set consisting of all elements of the form ..., f^-1 (^-1 (x)), g^-1(x), x, f(x), g(f(x)), f(g(f(x))), .... Explain why the number of elements to the left of x in the above chain may be zero, finite, or infinite. (c) Show that any two chains are either identical or completely disjoint. (d) Note that the terms of the chain in (1) alternate between elements of X and elements of Y. Given a chain C_x, we want to focus on C_x Y, which is just the part of the chain that sits in Y. Define the set A to be the union of all chains C_x satisfying C_x Y f(X). Let B consist of the union of the remaining chains not in A. Show that any chain contained in B must be of the form y, g(y), f(g(y)), g(f(g(y))), ..., where y is an element of Y that is not in f(X). (e) Let X_1 = A X, X_2 = B X, y_1 = A Y, and Y_2 = B Y. Show that f maps X_1 onto Y_1 and that g maps Y_2 onto X_2. Use this information to prove X ~ Y.

Solution

It is clear

By the definition of an onto function f , for y belongs to Y there exists x belongs to X such that f(x)=y