Schröder-Bernstein Theorem

Set Theory · Axiom Academy

LESSON Schröder-Bernstein Theorem If two sets inject into each other, they have the same cardinality The Schröder-Bernstein Theorem provides a criterion for when two sets have the same cardinality based on the existence of injections between them. This is remarkable because we don't need to find a bijection directly. We only need to find injections in both directions, which is often much easier! 2. Proof Idea: Constructing the Bijection The proof constructs a bijection by partitioning set A into three parts based on the "ancestry" of elements under the inverse of the injection g. Given injections f: A → B and g: B → A, we trace elements backwards through g⁻¹. Each element in A has an "ancestry chain" that either: Terminates in A - the chain ends at an element with no predecessor in g(B) Terminates in B - the chain ends at an element of B \ g⁻¹(A) Never terminates - the chain continues infinitely backwards The bijection h: A → B is defined by using f on elements whose chains terminate in A or go on infinitely, and g⁻¹ on elements whose chains terminate in B. The animation illustrates how the bijection partitions A into regions based on ancestry chains. A₀ = elements whose chains terminate in A A₁ = elements whose chains terminate in B A∞ = elements whose chains never terminate This construction ensures h is both injective and surjective, hence a bijection. 4. Applications of the Theorem

This is the written version of the interactive lesson above. See the full Set Theory course.