Lesson 2

Theorem (Cantor–Schröder–Bernstein theorem, 1897). If the cardinality of \(A\) is not greater than the cardinality of \(B\) and the cardinality of \(B\) is not greater than the cardinality of \(A\), then \(A\) and \(B\) are in bijection.

Proof. Assume that \(A\) and \(B\) do not intersect: if this is not the case, replace \(B\) with its copy. We construct a directed graph: \((a,b) \in E\) for \(a \in A, b \in B\), if \(b = f(a)\); \((b,a) \in E\) for \(a \in A, b \in B\), if \(a = g(b)\), where \(f \colon A \to B\) and \(g \colon B \to A\) are the corresponding injections. From each vertex, there is exactly one outgoing edge, and each vertex has at most one incoming edge. We divide it into connected components—cycles and paths, infinite in both or one direction (nothing else is possible because each vertex has at most one incoming edge). For each component, we can establish a one-to-one correspondence on its vertices:

• A cycle consists of an even number of edges (because in a cycle, edges of two different types alternate), so for a bijection, we can just take every second edge;


• In an infinite path in both directions, we can simply take every second edge;


• In an infinite path in one direction, we need to take every second edge, starting from its endpoint and going to infinity.