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

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.

1. 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.

1. 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.

• I'm too lazy to read the details, but offhand this looks like the "ancestor-descendant" proof, which seems to be the most popular way to prove the Cantor–Bernstein theorem. I didn't know it was Julius König's invention.
– bof
Apr 23, 2018 at 0:44
• @bof i found this reference from wikipedia. I'm not sure if it's correct or not :) Apr 23, 2018 at 0:49
• Seems about right! I always thought Tarski's proof (actually I don't know if he proved it but the lemma used is the Tarski Fixed point for morphism of complete lattices) was shorter and simpler to understand. Have you studied it? Apr 23, 2018 at 2:45
• @LeoLerena I have read Tarski's proof too, but it's good to see different approaches and therefore have a wider view of what's going on :) Apr 23, 2018 at 3:15
• @user170039. On the topic of different proofs: The first chapter of the book "Prime Number Records" consists of about 23 different proofs that there is no largest prime, including a topological proof. Sep 15, 2018 at 16:10

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)

• Let me explain my reasoning behind the statement It suffices to generate bijection for each sequence as follows ^^ Sep 15, 2018 at 15:51
• @LeAnhDung sorry, I am not quite sure what did you mean in that comment
– ℋolo
Sep 15, 2018 at 15:58
• I'm sorry! I'm typing a comment. Sep 15, 2018 at 15:59
• In the proof, I defined three bijections $h:A_1 \to B_1$, $k:B_2 \to A_2$, and $t:A_3 \to B_3$. At the first of the proof, I reasoned that $\{A_1,A_2,A_3\}$ is a partition of $A$ and $\{B_1,B_2,B_3\}$ is a partition of $B$. So $h\cup k\cup t$ is a bijection from $A$ to $B$. Sep 15, 2018 at 16:03
• @LeAnhDung but this is wrong, that is possible that there are hundred separate A-stoppers, or $\aleph_{\aleph_1}$ separate Doubly infinite, what will you do then?
– ℋolo
Sep 15, 2018 at 16:04