Theorem. $M\sim N_1 \subseteq N \wedge N\sim M_1 \subseteq M \rightarrow M \sim N$

Proof. Another way of putting the theorem is: If there is an injective function from $M$ to $N$. And if there is an injective function from $N$ to $M$. Then there is a bijective function from M on N (whatever it may look like).

The proof rests on two major building blocks: one is setting up a mere correspondence b/w elements of $M$ and $N$ (which has no properties whatsoever but relating two objects) by giving two simple rules. The other is by defining two sets $A \subseteq M$ and $B \subseteq N$, which helps us deal with the missing elements in an injective mapping.

Let's start with the rule first. In absence of the necessity of explicitely formulating the bijection it's sufficient to give two rough principles for setting up the correspondence. These are (Bernstein 1897):

(i) If $m \in A$, the corresponding element in $N$ is exactly that which we would get from the injective mapping $f_M:M \rightarrow N$.
(ii) If $m \notin A$, or, more precisely, if $m \in M \setminus A$, the corresponding element in $N$ is exactly that which satisfies $f_N(n) = m$.

So much for the rules. Now to the definition of the sets $A$ and $B$:

$A$ is recursively defined:
$$ A_0 := M \setminus f_N(N), \qquad A_{\alpha+1} := f_N(f_M(A_{\alpha})), \qquad \alpha = 0,1,2,3,... $$ Similarly, we get for $B$: $$ B_{\alpha+1} := f_M(A_{\alpha}). $$ What happens next is analysing the properties of the correspondence according to (i) and (ii).

Given two elements $m_1$ and $m_2$ in $A$. According to rule (i) the corresponding element to $m_1$ is $n_1 = f_M(m_1)$ and the corresponding element of $m_2$ is $n_2 = f_M(m_2)$. Since $f_M$ is injective, we have $$ (\forall m_1, m_2 \in M) \: m_1 \neq m_2 \rightarrow f_M(m_1) \neq f_M(m_2). $$ Now given two elements $m_1$ and $m_2$ not in $A$, i.e. $m_1, m_2 \in M \setminus A$. According to rule (ii), the corresponding element to $m_1$ is the element in $N$ such that $f_N(n_1) = m_1$. While the corresponding element to $m_2$ is the element $n_2$ in $N$ such that $f_N(n_2) = m_2$. If $m_1$ and $m_2$ are distinct we have, from the definition of a function $$ (\forall n_1, n_2 \in N) \: f_N(n_1) \neq f_N(n_2) \rightarrow n_1 \neq n_2. $$ What if $m_1 \in A$ and $m_2 \in M \setminus A$?

From the definition of $B_{\beta}$ we have that $$ B \supseteq B_{\alpha + 1} := f_M(A_\alpha) = \{ f_M(m) : m \in A_{\alpha} \} \stackrel{(i)}{\ni} n_1$$ and since $m_1 \in A \rightarrow (\exists \alpha) \: m_1 \in A_{\alpha}$, it is true that there is a corresponding element $n_1$ to $m_1$ and it's in $B$. If, in turn, $m_2 \in M\setminus A$, the corresponding element $n_2$ in $N$ is, from rule (ii), exactly that element which maps on $m_2$: $f_N(n_2) = m_2$. By definition $A_{\alpha + 1} := f_N(B_{\alpha + 1})$, $f_N(N) \cap A_0 = \emptyset $ and $f_N$ being injective, $n_2$ must not be in $B$.

Having covered all the possible permutations of two elements $m_1, m_2 \in M$, we conclude that $$ (\forall m_1, m_2 \in M) \: m_1 \neq m_2 \rightarrow n_1 \neq n_2. $$ This requires the correspondence b/w $M$ and $N$, given by rule (i) and (ii), to be injective.

For the correspondence $(i) \wedge (ii)$ to be bijective, it needs to have surjective property as well. I.e. every element in $N$ needs to have a corresponding element in $M$. Given an arbitrary element $n \in B$, there will be a corresponding element in $A \subseteq M$ due to the injection $B_{\alpha + 1} := f_M(A_{\alpha})$ and (i). Now if $n \in N \setminus B$, according to rule (ii), there is a corresponding element $M\setminus A \ni m = f_N(N \setminus B)$ because of $A_{\alpha + 1} := f_N(B_{\alpha + 1})$ and $f_N$ being an injection.

This finally gives the correspondence $(i) \wedge (ii)$ the surjective property $$ (\forall n \in N)(\exists m \in M) \: n \text{ corresponds to } m. $$ $\Box$

• Back to menu
  

2015 FEB 01 (v1.0)
Contact me: m.herrmann followed by an -at- followed by blaetterundsterne.org.

This document created with the help of MathJax (Thank you guys!)