Julius König's proof of Schröder–Bernstein theorem

Question

I found that Julius König's proof is short and simple to understand, but Wikipedia only provides a sketch and omits details. Here I present a proof with full detail.

Please have a check on it! Thank you so much!

Theorem:

Let $f:A \to B$ and $g:B \to A$ be injections. Then there exists a bijection from $A$ to $B$.

Proof:

Without loss of generality, we can safely assume that $A \cap B=\varnothing$.

For any $x \in A \cup B$, we can form a unique sequence by repeatedly applying $f$ and $g$ to go right, and $g^{-1}$ and $f^{-1}$ to go left whenever $g^{-1}(x)$ and $f^{-1}(x)$ are defined.

Such sequence looks like: $$\cdots \rightarrow f^{-1}(g^{-1}(x)) \rightarrow g^{-1}(x) \rightarrow x \rightarrow f(x) \rightarrow g(f(x)) \rightarrow \cdots$$

For any particular $x$, the sequence may terminate to the left or not, at a point when $f^{-1}$ or $g^{-1}$ is not defined. Since $f$ and $g$ are injective, each $x$ is in exactly one such sequence to within identity (if an element occurs in two sequences, all elements to the left and to the right must be the same in both. So these two sequences are identical). Therefore, the sequences form a partition of $A \cup B$.

Call a sequence an A-stopper if it stops at an element of $A$, or a B-stopper if it stops at an element of $B$. Otherwise, call it doubly infinite. It suffices to generate bijection for each sequence as follows.

1. A-stopper

Let $A_1$ be the set of its elements in $A$, $B_1$ be the set of its elements in $B$.

Let $h:A_1 \to B_1$ such that $h(a)=f(a)$ for all $a \in A_1$.

$h(a_1)=h(a_2) \implies f(a_1)=f(a_2) \implies a_1=a_2$ [Since $f$ is injective] $\implies h$ is injective.

For $b \in B_1$, there exists $x=f^{-1}(b) \in A_1$ [If not, this sequence will stop at $b \in B$, which contradicts to the fact that it is A-stopper). $h(x)=f(f^{-1}(b)=b \implies h$ is surjective.

Thus $h:A_1 \to B_1$ is bijective.

2. B-stopper

Let $A_2$ be the set of its elements in $A$, $B_2$ be the set of its elements in $B$.

Let $k:B_2 \to A_2$ such that $k(b)=g(b)$ for all $b \in B_2$.

$k(b_1)=k(b_2) \implies g(b_1)=g(b_2) \implies b_1=b_2$ [Since $g$ is injective] $\implies k$ is injective.

For $a \in A_2$, there exists $y=g^{-1}(a) \in B_2$ [If not, this sequence will stop at $a \in A$, which contradicts to the fact that it is B-stopper). $k(y)=g(g^{-1}(a)=a \implies k$ is surjective.

Thus $k:B_2 \to A_2$ is bijective. Then $k^{-1}:A_2 \to B_2$ is bijective.

3. Doubly infinite

Let $A_3$ be the set of its elements in $A$, $B_3$ be the set of its elements in $B$.

Let $t:A_3 \to B_3$ such that $t(a)=f(a)$ for all $a \in A_3$.

$t(a_1)=t(a_2) \implies f(a_1)=f(a_2) \implies a_1=a_2$ [Since $f$ is injective] $\implies t$ is injective.

For $b \in B_3$, there exists $x=f^{-1}(b) \in A_3$ [If not, this sequence will stop at $b \in B$, which contradicts to the fact that it is doubly infinite). $t(x)=f(f^{-1}(b)=b \implies t$ is surjective.

Thus $t:A_3 \to B_3$ is bijective.

Answer 1

There are few flaws that exists not because of a mistake, but because you were sloppy:

"...the sequences form a partition"

Should be

"...the range of the sequences form a partition"

Also

"It suffices to generate bijection for each sequence as follows"

This is correct but needs a proof:

Let $P$ be the partition, and let $$P_A=\{x\in\mathcal P(\bigcup P)\mid\forall a\in x(a\in A)\land(x\subseteq Q\subseteq\bigcup P\implies(\forall b\in Q\setminus x(b\notin A)))\}\\P_B=\{x\in\mathcal P( \bigcup P)\mid\forall a\in x(a\in B)\land(x\subseteq Q\subseteq\bigcup P\implies(\forall b\in Q\setminus x(b\notin B)))\}$$ in other words: you separate the partition to 2 partitions for $A,B$.

Now, let $f$ be bijective from $P_A$ to $P_B$ such that $f(x)=y\iff x\cup y\in P$, therefore there exists bijective $F_x: x\to f(x)$, thus $G: A\to B$ will be bijective defined as $\bigcup_{x\in P_A}F_x$.

---

Now, apart from this, the proof is good, but (in my opinion) it is easier to prove this theorem assuming $B\subseteq A$ instead of $A\cap B=\emptyset$(Although both are good)