 Solution

ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2008/b/7/3/solution

There is an injection from the power set of

ω

into the real numbers given by

S ⟼ x_{S} = \sum_{n = 0}^{\infty} \frac{2 1 _{S} ( n )}{3 ^{n + 1}} .

S

and

T

first differ at

k

, the contribution at

k

has magnitude

2/ 3^{k + 1}

, while the entire later tail has magnitude at most

\sum_{n > k} \frac{2}{3 ^{n + 1}} = \frac{1}{3 ^{k + 1}} .

Their real values are therefore different. This proves injectivity directly and avoids any ambiguity of numeral expansions.

x

to the set

{q \in Q : q < x}

. Distinct real numbers give distinct sets because the rational numbers are dense in the real line. Fixing a bijection between

ω

Q

turns this into an injection

R \to P (ω)

∣ R ∣ = 2^{ℵ_{0}} .

 New to topics? Read the docs here!