Proving the Schroeder-Bernstein theorem

Question

I'm trying to figure it out a proof of Schroeder-Bernstein Theorem for myself, but i really don't know how to proceed, how to start investigating a proof. Can you help me with some tips or some motivation for the proof (i'm not asking to show me the proof, just a way, a tip or something). I prove it for finite sets but i don't think the same strategy would work for infinite ones (and adding the premise that the sets are infinite doesn't seem to help very much) Thanks in advance.

Obs. My attempt so far was to construct a bijective function using the fact that there's injectives functions from the two sets, but i don't know how to do it.

Answer 1

There are several proofs. I will give you a few hints for a reasonably intuitive one.

The first point to grasp is that you have somehow got to construct a bijection out of the two injections. So if the two sets are $A,B$ and the two injections are $f:A\to B$ and $g:B\to A$ you have to decide what subset $X\subset A$ to use for $f$; then you use $g^{-1}$ on $A\setminus X$. Think about that for a while.

One way is to "trace backwards". So start say with in $a_1\in A$ and then try to find $b_1\in B$ such that $g(b_1)=a_1$. If you can't, then you have to put $a_1$ into $X$. Similarly, if you cannot trace back from $b_1$, ie find $a_2\in A$ such that $f(a_2)=b_1$, then if $g(b_1)=a_3$ you must put $a_3$ into $A\setminus X$. One of three things must happen, either you can trace back indefinitely, or you end up stuck in one set or the other. If you end up stuck, then that determines how all the elements in that chain (up to getting stuck) must be treated. In the indefinite case you have a choice, but must treat the elements in the chain consistently.

Answer 2

The OP was looking to

construct a bijective function using the fact that there's injectives functions from the two sets

The OP was also asking for the motivation behind it all; I suggest that the following set theory problem is a good starting point.

Problem: Consider the injective function $\sigma: \Bbb N \to \Bbb N$ mapping

$\quad n \mapsto n + 1$

Show that there is exactly one subset of

$\quad \displaystyle \text{Graph}(\sigma) \cup {\big[\text{Graph}(\sigma)\big]}^{-1}$

that is a bijective correspondence of $\Bbb N$ with itself.

(if $\rho$ is a relation $\rho^{-1}$ is the converse relation)

---

For the above problem the two injections are $f = \sigma$ and $g = \sigma$,

$\quad f= \sigma: \Bbb N \to \Bbb N$

$\quad g = \sigma: \Bbb N \to \Bbb N$