Is this proof of the Cantor–Bernstein theorem I wrote valid? Or did I make a mistake somewhere?

Question

Given any two disjoint sets $A$ and $B$ note if there exists two injections $f:A\to B$ and $g:B\to A$ then we can construct another injection $h:A\cup B\to A\cup B$ as follows:

$$h(x)=\begin{cases}f(x)&\text{ if }x\in A\\g(x)&\text{ if }x\in B\end{cases}$$

Now if we construct a digraph $D$ such that $V(D)=A\cup B$ and $E(D)=\{(x,h(x)):x\in A\cup B\}$ we see $D$ must be bipartite with parts $A$ and $B$ since the edges in $E(D)$ alternate between vertices that belong to $A$ and vertices that belong to $B$. Further if we let $\mathscr{C}$ be the set of all weakly connected components $C\subseteq D$ and define $\mathcal{A}=\{V(C)\cap A:C\in \mathscr{C}\}$ as well as $\mathcal{B}=\{V(C)\cap B:C\in \mathscr{C}\}$ then we see $\mathcal{A}$ is a partition of $A$ while $\mathcal{B}$ is a partition of $B$ thus if we can show for any $C\in \mathscr{C}$ that $|V(C)\cap A|=|V(C)\cap B|$ then this will prove $|A|=|B|$. To do this note note that since $D$ has no sink vertices and for any vertex $v\in V(D)$ we have $\text{deg}^{+}(v)=\text{deg}^{-}(v)=1$ this means that every weakly connected component $C\in\mathscr{C}$ must be either a cycle, an out-ray or a double-ray. However if any weakly connected component $C\in \mathscr{C}$ is a cycle then because $D$ is bipartite with parts $A$ and $B$ this means $C$ must have an even number of vertices, where half of them are in $A$ and half are in $B$ therefore $|V(C)\cap A|=|V(C)\cap B|$. Likewise if any weakly connected component $C\in\mathscr{C}$ is either an out-ray or a double-ray then since the arcs in $C$ alternate between vertices in $A$ and vertices in $B$ we have $|V(C)\cap A|=\aleph_0$ and $|V(C)\cap B|=\aleph_0$ therefore $|V(C)\cap A|=|V(C)\cap B|$ thus by our previous reasoning we must have that $|A|=|B|$.

---

So is the proof I wrote above correct? Or did I make a mistake somewhere? I don't see anything wrong with it, however its pretty short thus I feel like there could be an error.

Answer 1

It starts out well, but at

thus if we can show for any $C\in \mathscr{C}$ that $|V(C)\cap A|=|V(C)\cap B|$ then this will prove $|A|=|B|$

you're implicitly invoking the axiom of choice to assert that you can pick one bijection for each $C$ and union them all together to a bijection between $A$ and $B$. Since the Cantor-Bernstein theorem actually holds without the axiom of choice, this is at best untidy.

The standard proof gets around this by describing exactly one bijection between $C\cap A$ and $C\cap B$, depending on its shape. But your writeup stops just short of that in the case of cycle or a double-ray.

It's easy enough to fix that by saying, for example, that in those cases you always take the edges that come from $f$ rather than the edges that come from $g$. This will yield the standard proof in graph-theoretic language.