10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – bof Apr 23 '18 at 0:44
  • 1
    $\begingroup$ @bof i found this reference from wikipedia. I'm not sure if it's correct or not :) $\endgroup$ – Le Anh Dung Apr 23 '18 at 0:49
  • 1
    $\begingroup$ 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? $\endgroup$ – Leo Lerena Apr 23 '18 at 2:45
  • 1
    $\begingroup$ @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 :) $\endgroup$ – Le Anh Dung Apr 23 '18 at 3:15
  • 1
    $\begingroup$ @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. $\endgroup$ – DanielWainfleet Sep 15 '18 at 16:10
1
+50
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Let me explain my reasoning behind the statement It suffices to generate bijection for each sequence as follows ^^ $\endgroup$ – Le Anh Dung Sep 15 '18 at 15:51
  • $\begingroup$ @LeAnhDung sorry, I am not quite sure what did you mean in that comment $\endgroup$ – Holo Sep 15 '18 at 15:58
  • $\begingroup$ I'm sorry! I'm typing a comment. $\endgroup$ – Le Anh Dung Sep 15 '18 at 15:59
  • $\begingroup$ 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$. $\endgroup$ – Le Anh Dung Sep 15 '18 at 16:03
  • $\begingroup$ @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? $\endgroup$ – Holo Sep 15 '18 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.