What is wrong with this cardinality-based proof of the Cantor–Schröder–Bernstein theorem?

Question

Let $A$ and $B$ be sets, not necessarily finite. Let $f: A\rightarrow B$ be injective, and let $g:B\rightarrow A$ be injective.

The Cantor–Schröder–Bernstein theorem then says there must be a bijection between $A$ and $B$.

I once got the proof of this assigned on a problem set, and when I presented the following proof, the TA said that it was insufficient. Take $\vert X\vert$ to be the cardinality of a set $X$.

$f$ injective $\implies \vert A\vert\le\vert B\vert$

$g$ injective $\implies \vert A\vert\ge\vert B\vert$

Therefore, $\vert A\vert=\vert B\vert$, and there is a bijection between $A$ and $B$. $\square$

I have never understood why this proof is insufficient but assume it has something to do with $\le$, $\ge$, and $=$ when it comes to comparing infinite cardinalities.

What is inadequate about that proof?

Answer 1

The main issue is that you are assuming that the comparison of cardinalities is an order (in particular, that it is antisymmetric). However, that is precisely what the Cantor-Bernstein-Schroeder Theorem establishes. So you are trying to prove the theorem by invoking the theorem sub silentio.

To be precise, the following are fairly common ways to define comparison of cardinalities:

Definition. We say two sets $A$ and $B$ are equipollent (roughly, "equally powerful") if and only if there exists a bijection $f\colon A\to B$. We denote this by writing $A\sim B$.

Equipollence is an equivalence relation. That is, it is (i) Symmetric: $A\sim A$ for all sets $A$. (ii) Reflexive: for all sets $A$ and $B$, if $A\sim B$ then $B\sim A$. And (iii) Transitive: for all sets $A$, $B$, and $C$, if $A\sim B$ and $B\sim C$, then $A\sim C$.

Then we define some weaker conditions:

Definition. For sets $A$ and $B$, we write $A\preceq B$ if and only if there exists an injection $i\colon A\to B$. We write $A\succeq B$ if and only if there exists a surjection $s\colon A\to B$. We write $A\prec B$ if and only if $A\preceq B$ and $A$ is not equipollent to $B$; and we write $A\succ B$ if and only if $A\succeq B$ and $A$ is not equipollent to $B$.

Now, we would like several things to be true:

1. We would like $\preceq$ to define a (partial) order; that is, it should be reflexive, transitive, and antisymmetric, which in this case means: if $A\preceq B$ and $B\preceq A$, then $A\sim B$.

2. We would like $\succeq$ to define a (partial) order.

3. We would like $A\succeq B$ to be equivalent to $B\preceq A$.

For 1, the only difficult thing is antisymmetry. That is precisely the Cantor-Bernstein-Schroeder Theorem. This is what you invoked in your argument, so it cannot be used to prove the Cantor-Bernstein-Schroeder Theorem. Cantor-Bernstein-Schroeder is a theorem of $\mathsf{ZF}$ set theory: you do not need the Axiom of Choice to prove it.

For 2, likewise, the only tricky part is antisymmetry. It turns out the Dual Cantor-Bernstein-Schroeder Theorem cannot be proven in $\mathsf{ZF}$: it implies that every infinite set has a countable subset, and this is known to be independent of $\mathsf{ZF}$. See for example this math.overflow post.

Point 3 is not even true in general for a tricky reason: it is easy to verify that $\varnothing\preceq X$ for every set $X$; but if $X$ is not empty, then it is not true that $X\succeq\varnothing$!

But even if we exclude the empty set, so that we say "for nonempty sets $A$ and $B$, $A\preceq B$ is equivalent to $B\succeq A$," then this is not provable in $\mathsf{ZF}$ set theory. (You gloss over this problem by using $\geq$ as meaning the same as $\leq$ but in the opposite order; one should not do that with cardinalities!). If $A\preceq B$ and $A\neq\varnothing$, then we can prove that $B\succeq A$: given $i\colon A\to B$ injective, let $a_0\in A$ be fixed, and define $s\colon B\to A$ by letting $s(b)=a$ if $b\in i(A)$ and $i(a)=b$, and defining $s(b)=a_0$ otherwise.

However, in general we cannot show that if there is a surjection $s\colon B\to A$, then there must be an injection $i\colon A\to B$ (that is, in general we cannot show that $B\succeq A$ implies $A\preceq B$). We need the Axiom of Choice for this to hold.

There is also the problem of whether any two sets can be compared: given two sets $A$ and $B$, must there always be an injection $i\colon A\to B$ or an injection $j\colon B\to A$? This is called "Bernstein's Theorem", and it is in fact equivalent to the Axiom of Choice.

Now, in $\mathsf{ZFC}$ set theory, with the Axiom of Choice, you can prove that every set can be bijected with a unique cardinal (which are defined as ordinals that cannot be bijected with any strictly smaller ordinal). Then $|A|$ represents the unique cardinal that $A$ can be bijected with. We define cardinal order by saying $\kappa\leq \lambda$ if and only if $\kappa=\lambda$ or $\kappa\in\lambda$ (the order of the ordinals), and then we can prove that $A\preceq B$ if and only if $|A|\leq|B|$.

Assuming all of that is overkill for Cantor-Bernstein-Schroeder. Which is why your argument is either secretly circular, or it actually assumes a lot of things that you were perhaps not aware of in trying to do a "simpler" proof.

Answer 2

You must prove that $|A| \le |B|$ and $|A| \ge |B|$ implies $|A| = |B|$. That is the whole point of the theorem. You cannot simply assume that because we use the symbol $\le$ that it has the properties we expect.