Injection - Bijection function Question Suppose $A, B$ are two non-empty sets and let $$f:A\to B$$ and $$g:B\to A$$ be two injective (one to one) functions.
QUESTIONS:
1. Is there exist a bijective function from $A$ to $B$?
2. If so, how can we prove it?  
I think, there should be a such function. But I can not come up with an argument to prove it?
 A: There are several nice proofs of the result. The most intuitive I'm aware of is the following: We may as well assume that $A$ and $B$ are disjoint. Consider the directed graph whose set of vertices is $A\cup B$, in which you add an edge from $a$ to $b$ precisely if $a\in A$, $b\in B$, and $f(a)=b$, or $a\in B$, $b\in A$, and $g(a)=b$. 
Now consider the connected components of this graph. Check that the only options are: A cycle of even length, a chain that looks like the integers, or a chain that looks like $\mathbb N$. In all these cases, it is trivial to find a bijection between the elements of $A$ in the component and the elements of $B$ in the component. Putting all these partial bijections together gives you the desired bijection.
There are many other proofs. My favorite is not the argument above. Instead, one uses a theorem of Tarski and Knaster that if $L$ is a complete lattice and $\pi:L\to L$ is order preserving, then $\pi$ has a fixed point (this is itself a nice result, and there are several natural ways of verifying it). Now: For any set $A$, $\mathcal P(A)$ ordered by set inclusion is a complete lattice. We can define $\pi$ by setting $\pi(C)=A\setminus g[B\setminus f[C]]$ for all $C\subseteq A$. One easily checks that $\pi$ is order preserving, so it has a fixed point. That is, there is an $X\subseteq A$ such that 
 $$ X=A\setminus g[X\setminus f[X]] $$
or, equivalently, $A\setminus X=g[X\setminus f[X]]$. Very well, define the bijection as follows: If $a\in A$ is in $X$, map it to $f(a)$. If instead $a$ is in the complement of $X$, map it to the unique element $b\in B$ of the complement of $f[X]$ such that $g(b)=a$. (A few years ago I wrote a blog post where I link to a write-up of this proof with details.)
There are yet other arguments, in fact, there is a whole book devoted to discussing them. See

MR3026479. Arie Hinkis. Proofs of the Cantor-Bernstein theorem. A mathematical excursion. Science Networks. Historical Studies, 45. Birkhäuser/Springer, Heidelberg, 2013. xxiv+429 pp. ISBN: 978-3-0348-0223-9; 978-3-0348-0224-6 

(The first link is to the review at Mathematical Reviews. The second is to the Springer page for the book.)
The history of the result is also interesting. The book discusses this in good detail. 
A: I have seen 2 proofs, one complicated, and this one: For $x\in A$ the possible sequence $$x,\; f^{-1}(x),\; g^{-1}f^{-1}(x),\; f^{-1}g^{-1}f^{-1}(x),...$$ may have just one term (if $f^{-1}(x)$ doesn't exist), or 2 terms (if $f^{-1}(x)$ exists but $g^{-1}f^{-1}(x)$ does not), et cetera. 
Let $x\in E$ if the sequence stops after an even number of terms. Let $x\in O$ if the sequence stops after an odd number of terms. Let $x\in I$ if the sequence has no end.
Let $h(x)=f(x)$ if $x\in O.$ Let $h(x)=f^{-1}(x)$ if $x\in E\cup I.$ I will leave it to you to verify that $h:A\to B$ is a bijection.
I have seen this referred to in books as the Schroeder-Berstein Theorem, the Cantor-Bernstein theorem, and the C-S-B theorem.
A: Yes. Such a bijection must exists. This is the topic of the Cantor–Bernstein theorem.
