Comparing Cardinalities: The Schröder-Bernstein Theorem

College Depth 55 in the knowledge graph I know this Set as goal
Unlocks 17 downstream topics
comparison order bijection

Core Idea

The Schröder-Bernstein theorem states: if there exist injections f: A → B and g: B → A, then there exists a bijection between A and B. This makes cardinality a total order: for any two sets A and B, either |A| < |B|, |A| = |B|, or |A| > |B|. It avoids needing explicit bijections.

Explainer

From your work on injections and bijections, you know that two sets have the same cardinality when there exists a bijection between them. But finding an explicit bijection can be surprisingly hard. The Schröder-Bernstein theorem (also called the Cantor-Schröder-Bernstein theorem) gives you a way around this: instead of one bijection, you provide two injections going in opposite directions, and the theorem guarantees a bijection must exist.

The theorem says: if f: A → B is an injection and g: B → A is an injection, then |A| = |B|. Intuitively, if A can fit inside B without collisions, and B can fit inside A without collisions, then they must be the same size. The proof constructs the bijection explicitly through a clever partitioning argument — elements are classified by whether their "ancestry chain" (repeatedly applying f and g backwards) terminates in A, terminates in B, or loops forever. This tri-partite structure lets you piece together a bijection from the two injections.

The theorem is most powerful when finding a direct bijection is difficult but finding two injections is easy. For example, proving |(0,1)| = |[0,1]| (the open and closed intervals have the same cardinality) directly is awkward because the endpoints of [0,1] have no obvious bijective image in (0,1). But injecting (0,1) → [0,1] is trivial (the identity works), and injecting [0,1] → (0,1) is easy (scale: x ↦ (x+1)/3 works). Two easy injections, and Schröder-Bernstein delivers the bijection.

This theorem establishes that cardinal comparison is a total order. We write |A| ≤ |B| if there exists an injection from A to B. Schröder-Bernstein shows this is antisymmetric: if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|. Combined with transitivity of injections, cardinality becomes a well-behaved ordering on sets. This is the foundation for comparing infinite cardinalities — the aleph hierarchy and cardinal arithmetic all build on this ordering, and Schröder-Bernstein is the essential tool that makes the ordering coherent.

Practice Questions 5 questions

Prerequisite Chain

Counting to 10Counting to 20Understanding ZeroThe Number ZeroCounting to FiveOne-to-One CorrespondenceCombining Small Groups Within 5Addition Within 10Addition Within 20Two-Digit Addition Without RegroupingTwo-Digit Addition with RegroupingAddition Within 100Repeated Addition as MultiplicationMultiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Two-Digit by One-Digit DivisionDivision with RemaindersRemainders and Quotients in DivisionDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueReading and Writing DecimalsComparing and Ordering DecimalsAdding and Subtracting DecimalsMultiplying DecimalsDividing DecimalsDividing FractionsMixed Number ArithmeticOrder of OperationsInteger Order of OperationsVariable ExpressionsThe Distributive PropertyVariables and Expressions ReviewIntroduction to PolynomialsAdding and Subtracting PolynomialsMultiplying PolynomialsFactorialPermutationsCombinationsCounting Principles: Addition and Multiplication RulesDefining Finite Sets RigorouslyCountable Sets and EnumerabilityCantor Pairing Functions and Product CountabilityUncountable Sets and Cantor's Diagonal ArgumentComparing Cardinalities: The Schröder-Bernstein Theorem

Longest path: 56 steps · 251 total prerequisite topics

Prerequisites (2)

Leads To (1)