Cardinals · Definition

Schröder–Bernstein theorem

set theorycardinals

Before you start you need to know

Is it enough to fit each set inside the other to conclude they have the same size, without building an exact correspondence?

Definition

The Schröder-Bernstein theorem states that if there are injections from \(A\) into \(B\) and from \(B\) into \(A\), then there is a bijection between \(A\) and \(B\).

\[|A| \le |B| \land |B| \le |A| \Rightarrow |A| = |B|\]

If \(f\colon A\to B\) and \(g\colon B\to A\) are injective, the theorem does not require building a bijection by hand. Its proof splits \(A\) and \(B\) into chains formed by alternately applying \(f\) and \(g\), and on each chain it uses \(f\) or the inverse of \(g\) as appropriate. It is a theorem of ZF, without the axiom of choice, so it holds for any pair of sets.

Let \(A=\mathbb{N}\) and \(B=\mathbb{Z}\). The inclusion \(f(n)=n\) is an injection from \(\mathbb{N}\) into \(\mathbb{Z}\), and \(g(z)=2z\) if \(z\ge 0\), \(g(z)=-2z-1\) if \(z<0\), is an injection from \(\mathbb{Z}\) into \(\mathbb{N}\). By the theorem, there is a bijection between \(\mathbb{N}\) and \(\mathbb{Z}\), so \(|\mathbb{Z}|=\aleph_0\).

A common mistake is to think the two injections must be inverses of each other. They do not have to be: the bijection is built by combining them along chains. Another mistake is to think one injection is enough: the theorem requires injections in both directions.

Think about it

Why do \(f\) and \(g\) not need to be inverses of each other?

Because the bijection is built by combining them along chains; each only needs to be injective.

Exercises 10

  1. What hypothesis does the Schröder-Bernstein theorem require?
  2. What does the Schröder-Bernstein theorem conclude?
  3. If there is an injection from \(A\) into \(B\), what cardinal relation follows?
  4. What does it mean for \(f\colon A\to B\) to be injective?
  5. Which of these functions is a bijection from \(\mathbb{N}\) onto the even numbers?
  6. If \(|A|\le|B|\) and \(|B|\le|A|\), what follows?
  7. Let \(g\colon \mathbb{Z}\to\mathbb{N}\) be given by \(g(z)=2z\) if \(z\ge 0\) and \(g(z)=-2z-1\) if \(z<0\). What is \(g(-2)\)?
  8. If \(|A|=5\) and \(|B|=4\), can there be an injection from \(A\) into \(B\)?
  9. If \(\mathbb{N}\subseteq\mathbb{Q}\) and there is an injection from \(\mathbb{Q}\) into \(\mathbb{N}\), what is the conclusion?
  10. Which of the following statements is false?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.