Skip to content

Cantor–Schröder–Bernstein: two injections make a bijection

Level: 201 · for anyone who has read that |A| ≤ |B| and |B| ≤ |A| give |A| = |B| and wondered why that needs a theorem

One line: An injection each way between two sets does not hand you a bijection, since neither map need be onto, but tracing every element's ancestors back through the two maps sorts the elements into three kinds, and sending one kind backwards and the other two forwards is a bijection; the proof is an algorithm, the program runs it, and what it buys is that "no bigger than" on sizes is antisymmetric without the axiom of choice.

The claim

Sizes are compared by maps, as cardinality says: |A| ≤ |B| when some one-to-one map f sends A into B. Suppose also g sends B one-to-one into A. Each map may miss part of its target: f(n) = 2n sends ℕ into the even numbers only, and g(n) = 3n into the multiples of 3. The theorem, stated by Cantor, proved by Dedekind in 1887 and by Bernstein in 1897, published by Schröder with a gap (dates from memory), says a bijection h: A → B exists all the same. Hrbacek and Jech prove it in chapter 4, André in chapter 21, Jech in chapter 3.

The construction

Take a ∈ A and trace its ancestry backwards. Is a in the image of g? If a = g(b), is b in the image of f? If b = f(a′), continue from a′. Three things can happen: the chain stops at an element of A that is not g of anything, it stops at an element of B that is not f of anything, or it never stops, which includes running in a circle. Define h(a) = f(a) when a's chain stops in A or never stops, and h(a) = g⁻¹(a) when it stops in B. Then h is one-to-one, because f and g⁻¹ are and the two kinds of element never meet, and h is onto, because every b ∈ B is either f of an element whose chain stops in A or never stops, or has g(b) with a chain stopping in B, from which g⁻¹ returns to b. Section 1 of the program runs the recipe on all 576 pairs of injections between two four-element sets and section 2 on ℕ with f(n) = 2n and g(n) = 3n, printing each element's chain, where it stops, and the h it gets; every chain here shrinks its number, so all stop except 0, which circles. The classic textbook example is [0, 1] against (0, 1): the identity injects one way and x ↦ x/2 + 1/4 the other, and the recipe names the countably many points that have to be shifted.

What it buys

"No bigger than" on cardinals is reflexive, antisymmetric by this theorem, and transitive, so it is a partial order, and none of that uses the axiom of choice. That any two sizes are comparable, which would make the order linear, is a different matter: it is equivalent to the axiom of choice. In practice the theorem is how equinumerosity is proved: finding a bijection between ℝ and the set of infinite 0/1 sequences by hand is fiddly because of the double decimal expansions, and two easy injections settle it.

What the program prints

Verified output of schroeder_bernstein.py — regenerated by tools/run_examples.py, never hand-typed.

1. THE CONSTRUCTION ON EVERY PAIR OF INJECTIONS BETWEEN TWO 4-SETS
   576 pairs (f, g); h is a bijection every time: True; h differs from f in 0 of them.
   On finite sets of equal size every injection is already a bijection, so the
   finite check only shows the recipe never breaks; the infinite case is the point.

2. N WITH f(n) = 2n AND g(n) = 3n: NEITHER IS ONTO, h IS
   trace a back: a = g(b)? only if 3 | a;  b = f(a')? only if b is even; and so on.
      a chain                              stops in  h(a)
      0 0                                  cycle     0
      1 1                                  A         2
      2 2                                  A         4
      3 3 = g(1)                           B         1
      6 6 = g(2) = f(1)                    A         12
      9 9 = g(3)                           B         3
     12 12 = g(4) = f(2)                   A         24
     18 18 = g(6) = f(3) = g(1)            B         6
     36 36 = g(12) = f(6) = g(2) = f(1)    A         72
     54 54 = g(18) = f(9) = g(3)           B         18
   h one-to-one on 0..399: True;  every b in 0..79 is h(a) for some a: True.
   Where the chain stops in A or never stops, h = f; where it stops in B, h = g⁻¹,
   the division by 3. Every b is reached: by f if b's own chain stops in A or
   never, by g⁻¹ from g(b) if it stops in B, and never twice.

3. WHAT IT BUYS: ≤ ON SIZES IS ANTISYMMETRIC, WITHOUT THE AXIOM OF CHOICE
   |A| ≤ |B| means an injection A -> B exists. The theorem says |A| ≤ |B| and
   |B| ≤ |A| give |A| = |B|, so ≤ on cardinals is reflexive, antisymmetric and
   transitive: a partial order. That any two cardinals are comparable, making it
   linear, is equivalent to the axiom of choice; this theorem needs none of it.
   Classic use: [0, 1] and (0, 1). x -> x injects (0, 1) into [0, 1] and
   x -> x/2 + 1/4 injects [0, 1] into (0, 1); so the two intervals are equinumerous,
   and the recipe above says which countably many points have to shift to show it.

Po polsku, w skrócie

Twierdzenie Cantora–Schrödera–Bernsteina: jeśli istnieją funkcje różnowartościowe f: A → B i g: B → A, to istnieje bijekcja A → B, więc |A| ≤ |B| i |B| ≤ |A| dają |A| = |B|. Dowód jest algorytmem: każdy element a śledzi się wstecz (a = g(b)? b = f(a′)? …), aż łańcuch urwie się w A, urwie się w B albo nie urwie się nigdy; h(a) = f(a) w pierwszym i trzecim przypadku, h(a) = g⁻¹(a) w drugim. Program uruchamia przepis na wszystkich 576 parach funkcji między dwoma zbiorami czteroelementowymi i na ℕ z f(n) = 2n, g(n) = 3n, gdzie żadna z funkcji nie jest „na", a h jest. Wniosek: relacja „nie większy niż" na mocach zbiorów jest antysymetryczna, czyli jest porządkiem częściowym, bez pewnika wyboru; że każde dwie moce są porównywalne, to już równoważnik pewnika wyboru.

Auf Deutsch: Stichwörter

Satz von Cantor–Schröder–Bernstein: zwei Injektionen in beide Richtungen ergeben eine Bijektion, konstruiert über Ketten.

Stichwörter: Satz von Cantor–Schröder–Bernstein, Injektion, Bijektion, Kettenkonstruktion, gleichmächtig, Antisymmetrie der Mächtigkeit.

Run it yourself

From the root of your clone of this repository:

python3 04_Sets/schroeder_bernstein/examples/schroeder_bernstein.py

See also