Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 · Countable and Uncountable Sets

The Continuum and the Real Numbers

Show that every interval has the same cardinality as the whole real line using tan and linear maps, and meet the cardinal of the continuum 2^ℵ₀.

We now know that ℝ is uncountable. The next question is how big it is. A natural guess is that a long interval must contain more points than a short one, and that the whole line must contain more than any interval. In fact all intervals, from a tiny (0, 0.001) to the entire line, have exactly the same cardinality.

That common cardinality is called the continuum and is written 𝔠. This lesson builds the bijections and explains why 𝔠 = 2^ℵ₀.

Any two open intervals match

Let (a, b) and (c, d) be open intervals with a < b and c < d. The linear function

Text
f(x) = c + (x - a) · (d - c) / (b - a)

stretches or shrinks (a, b) onto (c, d). It is increasing, so injective, and every y in (c, d) is hit by solving for x. Hence |(a, b)| = |(c, d)|. A centimeter of line has as many points as a kilometer.

An interval matches the whole line

The open interval (0, 1) and the entire real line ℝ also have the same cardinality. A nice bijection uses the tangent:

Text
g(x) = tan(π · (x - 1/2))     from (0, 1) onto ℝ

As x runs from just above 0 to just below 1, the angle π(x - 1/2) runs through (-π/2, π/2), where tan is increasing and takes every real value exactly once. The inverse is g⁻¹(y) = 1/2 + arctan(y)/π.

Python Match (0, 1) with all of ℝ

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.

So |(0, 1)| = |ℝ| = 𝔠. Also, with the linear maps, every open interval, every open ray (a, ∞), and the whole line have cardinality 𝔠.

Closed intervals: adding the endpoints

What about [0, 1], which includes its two endpoints? Schröder–Bernstein (earlier lesson) gives |[0, 1]| = |(0, 1)|. There is also a direct bijection, in the spirit of Hilbert's hotel. Take a countable sequence inside (0, 1), for instance 1/2, 1/3, 1/4, ..., and shift it along to make room for 0 and 1:

  • send 0 ↦ 1/2
  • send 1 ↦ 1/3
  • send 1/n ↦ 1/(n + 2) for n = 2, 3, 4, ...
  • send every other x to itself.
Python Move a countable set to make room for the endpoints

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.

Only a countable set of points moved, so the rest is untouched.

Why |ℝ| = 2^ℵ₀

We have a set P(ℕ) of cardinality 2^ℵ₀ and a set ℝ of cardinality 𝔠. Why are they equal?

Binary expansions. A real number in [0, 1) has a binary expansion 0.b₁b₂b₃... with bₙ ∈ {0, 1}, which is an infinite binary sequence, and an infinite binary sequence is a subset of ℕ. This gives a map from [0, 1) to P(ℕ) (choose the expansion that does not end in all 1s), which is injective. So 𝔠 ≤ 2^ℵ₀.

The other direction. Send a subset S ⊆ ℕ to the real number whose decimal digits are 1 at positions in S and 0 elsewhere (for example, S = {1, 3} gives 0.101000...). This is an injection P(ℕ) → ℝ. So 2^ℵ₀ ≤ 𝔠.

By Schröder–Bernstein, 𝔠 = 2^ℵ₀.

Python Encode subsets of N as real numbers

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.

The symbol 𝔠 is a Fraktur "c", short for "continuum". The statement 𝔠 = 2^ℵ₀ is a theorem. What is not settled by the usual axioms is whether 𝔠 is the next infinite cardinal after ℵ₀; see the continuum hypothesis.

Some other sets of size 𝔠

The plane ℝ², three-dimensional space ℝ³ and the set of all continuous functions ℝ → ℝ all have cardinality 𝔠. The set of all functions ℝ → ℝ, though, has cardinality 2^𝔠, which is larger by Cantor's theorem.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which function matches (0, 1) with the whole real line?

    The tangent maps (-π/2, π/2) one-to-one onto ℝ, and π(x - 1/2) takes (0, 1) to that interval.
  2. 2. Do (0, 1) and (0, 100) have the same cardinality?

    Linear scaling is a bijection between open intervals, so all open intervals have the same cardinality.
  3. 3. How do we show |P(ℕ)| = |ℝ|?

    Binary expansions inject [0, 1) into P(ℕ), and encoding subsets as decimal digits injects P(ℕ) into ℝ. Schröder–Bernstein gives a bijection.
  4. 4. What is 𝔠?

    𝔠 is the cardinality of the continuum, 2^ℵ₀. There is no largest cardinal.

Summary

  • All nonempty open intervals, open rays and the whole line ℝ have the same cardinality 𝔠.
  • x ↦ tan(π(x - 1/2)) is an explicit bijection (0, 1) → ℝ.
  • Closed intervals match open ones by shifting a countable sequence, or by Schröder–Bernstein.
  • |ℝ| = |P(ℕ)| = 2^ℵ₀, via binary expansions and an encoding of subsets as digits.
  • ℝ², ℝ³ and the continuous functions also have cardinality 𝔠; all functions ℝ → ℝ have 2^𝔠.

Next: Well-Ordered Sets