Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 38 · Cardinality

Comparing Sizes and the Schröder–Bernstein Theorem

Compare cardinalities with injections, learn why |A| ≤ |B| and |B| ≤ |A| imply |A| = |B|, and build the bijection step by step in Python.

Same size is one question; "at most as big" is another. Is the set of even numbers at least as big as the set of multiples of 3? Is a line segment at most as big as a square? With bijections as our only tool we need a way to say "A fits inside B", and then a theorem that tells us this ordering behaves sensibly.

Injections measure "at most"

We write |A| ≤ |B| when there is an injective function f: A → B. Picture it as putting every element of A into its own private slot in B, with possibly some slots left empty. If A is a subset of B, the inclusion function x ↦ x is an injection, so |A| ≤ |B| whenever A ⊆ B.

We write |A| < |B| when |A| ≤ |B| but there is no bijection between them. For finite sets this is ordinary "fewer than".

Two easy properties follow:

  • Reflexive: |A| ≤ |A| (the identity function).
  • Transitive: if |A| ≤ |B| and |B| ≤ |C|, then composing the two injections gives an injection A → C.

What is less obvious is the third property needed for a sensible ordering: antisymmetry. If |A| ≤ |B| and |B| ≤ |A|, do we get |A| = |B|?

The Schröder–Bernstein theorem

Theorem. If there is an injection f: A → B and an injection g: B → A, then there is a bijection h: A → B.

For finite sets this is obvious from counting. For infinite sets it is not, because a set can be matched into a part of itself. The theorem was conjectured by Cantor and proved independently by Felix Bernstein and Ernst Schröder (and earlier, though unpublished, by Richard Dedekind).

Why is it useful? Often it is much easier to find two injections than one bijection. Take (0, 1) and [0, 1]: the inclusion (0, 1) → [0, 1] is an injection, and x ↦ x/2 + 1/4 maps [0, 1] injectively into (0, 1). The theorem immediately gives |(0, 1)| = |[0, 1]|, with no need to design a bijection by hand (we will see one later anyway).

How the proof works: follow the chains

Take an element a of A. Try to step backward: if a = g(b) for some b in B, move to b. If b = f(a') for some a' in A, move to a'. Keep going. Because f and g are injective, each step back is unambiguous. There are three possibilities:

  1. The backward chain stops at an element of A (that element has no g-preimage).
  2. It stops at an element of B (that element has no f-preimage).
  3. It never stops (an infinite or looping chain).

Define h as follows:

  • if a's chain stops in A, or never stops, set h(a) = f(a);
  • if it stops in B, set h(a) = g⁻¹(a). This is defined, because the first step back from a exists.

You can check that h is both injective and surjective. The two kinds of chains never interfere, which is the key to the proof.

flowchart LR
  A1["a₀ (no preimage in B)"] -- "f" --> B1["b₁"]
  B1 -- "g" --> A2["a₁"]
  A2 -- "f" --> B2["b₂"]
  B0["b₀ (no preimage in A)"] -- "g" --> A3["a₂"]
  A3 -- "f" --> B3["b₃"]

Two chains: the top starts in A, the bottom starts in B. Elements on the top chain use f, those on the bottom chain use g⁻¹.

Building the bijection in code

Let A = B = {1, 2, 3, ...}, with f(n) = 2n and g(n) = 3n. Both are injective. We cannot have a finite check of surjectivity, but we can implement the chain rule and test it on a large window.

Python Build the Schröder–Bernstein bijection

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For this pair, an a with no factor 3 has a chain that starts in A, so h(a) = 2a. Others get divided by 3 on the way. The result is a bijection of the positive integers onto themselves that behaves in a mixed way, which no one would guess in advance.

Using the theorem: a worked example

Claim: the open interval (0, 1) and the half-open interval [0, 1) have the same cardinality.

  • Injection (0, 1) → [0, 1): inclusion.
  • Injection [0, 1) → (0, 1): x ↦ (x + 1)/3. For x in [0, 1) this lies between 1/3 and 2/3, strictly inside (0, 1), and it is injective since it is linear with nonzero slope.

By Schröder–Bernstein, |(0, 1)| = |[0, 1)|.

Python Check two injections numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Schröder–Bernstein does not need the axiom of choice. Other statements about cardinal ordering, like "any two sets are comparable", do. You will meet this in the axiom of choice.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does |A| ≤ |B| mean?

    An injection puts each element of A in its own slot in B. A subset is one special case, but the general definition uses any injection.
  2. 2. The Schröder–Bernstein theorem says that if A injects into B and B injects into A, then...

    The two injections combine into a bijection, so the sets have equal cardinality. They need not be the same set.
  3. 3. In the proof, an element a whose backward chain stops in B is sent to...

    Such an a has a g-preimage (the first step back), so h(a) = g⁻¹(a) is defined.
  4. 4. Which pair of injections shows that [0, 1] and (0, 1) have the same cardinality?

    The inclusion maps (0,1) into [0,1], and x/2 + 1/4 maps [0,1] into [1/4, 3/4], which lies inside (0,1).

Summary

  • |A| ≤ |B| means there is an injection A → B; it is reflexive and transitive.
  • The Schröder–Bernstein theorem: injections both ways give a bijection, so ≤ is antisymmetric.
  • The proof follows backward chains through f and g and chooses f or g⁻¹ by where each chain starts.
  • In practice it is usually easier to exhibit two injections than one bijection.

Next: Cardinal Arithmetic