Мощностью множества X будем называть совокупность всех множеств Y таких, что |X| = |Y|. Обозначим мощность тем же символом |X|. Эта совокупность не является множеством, тем не менее, можно доказать, что из неё можно выбрать канонический представитель и взять его за определение мощности.

Множество X называется конечным, если существует n Î w такое, что |X| = |n|. Множество X называется счетным, если |X| = |w|. Например, множество {0, 3, 5} конечно, а множество всех четных натуральных чисел {0, 2, 4, …} счётно.

Упражнение 1

Доказать, что множество положительных рациональных чисел Q⁺ – счётно.

Указание. Каждое положительное рациональное число можно представить как несократимую дробь m/n. Отсюда существует инъекция Q⁺ à w ´ w, сопоставляющая дроби m/n пару (m, n), и, значит, |Q⁺| £ |w ´ w|. Счётность множества w ´ w доказывается стандартным способом:

Пары (m, n) располагаем в таблицу:

(0, 0)      (1, 0)      (2, 0)      (3, 0)      …

(0, 1)      (1, 1)      (2, 1)      (3, 1)      …

(0, 2)      (1, 2)      (2, 2)      (3, 2)      …

  …          …          …          …

Затем их выстраиваем в последовательность: (0, 0), (1, 0), (0, 1), (0, 2), (1, 1), (2, 0), (3, 0), (2,1), (1,2), … Сопоставляя каждому  n Îw   n-й член этой последовательности, получаем биекцию между w и w ´ w. Поскольку каждое бесконечное подмножество из w счётно, отсюда получаем счётность Q⁺.

Упражнение 2

Доказать, что объединение двух счётных множеств счётно.

Упражнение 3

Пользуясь решениями предыдущих упражнений 2 и 1, доказать счётность всех рациональных чисел.

По теореме Кантора, |w| < |P(w)|, поэтому P(w) – несчётно.

Упражнение 4

Доказать, что множество действительных чисел 0 < x < 1 несчётно.

Доказательство провести методом диагонализации. Каждое число представляем в виде бесконечной десятичной дроби: 0.a₁a₂a₃,… состоящей из цифр и не имеющей в периоде 9. Предположим, что множество таких дробей счётно. Тогда их можно расположить в виде списка строк:

0 . a₁₁ a₁₂ a₁₃ a₁₄…

0 . a₂₁ a₂₂ a₂₃ a₂₄…

0 . a₃₁ a₃₂ a₃₃ a₃₄…

…

Рассмотрим последовательность цифр: b₁ ¹ a₁₁, b₂ ¹ a₂₂, b₃ ¹ a₃₃, …, не равных 9. Тогда число  0.b₁b₂b₃ …    не содержится в списке, хотя находится в интервале (0, 1). Значит, все действительные числа из этого интервала невозможно занумеровать с помощью натуральных чисел.