3. Мощность множества. Теорема Кантора.

Определение 1. Говорим, что множество A равномощно множеству B и пишем A ∼ B, если существует биекция F: A → B множества A на множество B. Так как обратное к биекции отображение суть также биекция, то из того, что A ∼ B вытекает, что B ∼ A. Из определения вытекает, что в случае конечных множеств A и B имеем A ∼ B ⇔ множества A и B состоят из одного и того же количества элементов. В случае бесконечных множеств это также в определенном смысле верно. Однако, возникает естественный вопрос: может быть все бесконечные множества равномощны? Ответ на этот вопрос дает следующая теорема.

Теорема 1 (теорема Кантора). Совокупность Z всех подмножеств множества X образует множество не равномощное X.

Доказательство. Доказательство проведём от противного. Пусть такая биекция F: X → Z существует. Построим множество D = {x ∈Х: x (/∈) F(x)}. Очевидно, D ∈ Z. Тогда существует x₀ ∈ X: F(x₀) = D. Поскольку D = F(x₀), то x₀ (/∈) D. Однако, тогда, по определению множества D получим, что x₀ ∈ D, противоречие.

Следствие 1. Будем говорить, что мощность множества A строго меньше мощности множества B, если существует инъекция из A в B, но не существует инъекции из B в A. Из теоремы Кантора вытекает, что существуют множества как угодно большой мощности. Множество, равномощное множеству натуральных чисел, будем называть счётным множеством. Множество назовем не более чем счетным, если оно конечно или счетно. Пусть E – счетное множество. Существует биекция F: N → E. Положим x_i = F(i). Таким образом, если E счетно, то его элементы можно записать в виде E = {x₁.x₂,...} или, другими словами, мы можем занумеровать элементы E c помощью множества натуральных чисел.

4. Счетные и не более чем счетные множества. Несчетность множества вещественных чисел и счетность множества рациональных чисел.

Следствие 1. Будем говорить, что мощность множества A строго меньше мощности множества B, если существует инъекция из A в B, но не существует инъекции из B в A. Из теоремы Кантора вытекает, что существуют множества как угодно большой мощности. Множество, равномощное множеству натуральных чисел, будем называть счётным множеством. Множество назовем не более чем счетным, если оно конечно или счетно. Пусть E – счетное множество. Существует биекция F: N → E. Положим x_i = F(i). Таким образом, если E счетно, то его элементы можно записать в виде E = {x₁.x₂,...} или, другими словами, мы можем занумеровать элементы E c помощью множества натуральных чисел.

Лемма 1. Любая часть не более чем счетного множества E не более чем счетна.

Доказательство. Если E конечно, то утверждение очевидно. Пусть E счетно и M ⊂ E. Занумеруем элементы E. Тогда E = {x₁,x₂,...}. Выберем в M элемент с наименьшим номером. Обозначим его через y₁. Последовательно выбираем элемент с наименьшим номером y_n из множества M \ {y₁,y₂,...,y_n−1}. Очевидно, что за конечное число шагов мы дойдем до произвольного наперед заданного элемента M и значит, мы можем перенумеровать элементы M, т.е. M счетно. Ч.т.д.

Теорема 2. Объединение не более чем счетного числа не более чем счетных множеств не более чем счетно. Доказательство. Пусть E_i = {x_i1,x_i2,x_i3,...} – набор не более чем счетных множеств и E = ∪∞ i=1E_i. Нумеруем элементы E в соответствии со схемой

пропуская на каждом шаге те элементы, которые были занумерованы ранее. Очевидно, что мы дойдем до каждого элемента объединения за конечное число шагов и таким образом занумеруем все множество E.

Следствие 2. Множество целых чисел и множество рациональных чисел счетны.

Доказательство. Множество целых чисел есть объединение N∪(−N)∪{0} и значит счетно. Положим E1 = {1/q: q ∈ N}, E2 = {−1/q: q ∈ N}, E3 = {2/q: q ∈ N}, E4 = {−2/q: q ∈ N}, .... Множество рациональных чисел есть счетное объединение множеств E_k, каждое из которых счетно и значит само является счетным.

Теорема 3. Множество вещественных чисел не счетно.

Доказательство. В силу леммы 1 достаточно доказать, что отрезок (0,1) не счетное множество. Предположим противное, что это счетное множество. Тогда его можно занумеровать: (0,1) = {x₁,x₂,...,}. Запишем каждое из чисел xi в виде десятичной дроби: x_i = 0.x_i1 x_i2 x_i3 .... Для каждого n найдем число a_n: 0 < a_n < 9, a_n 6= x_nn. Это очевидно возможно. Построим число a = 0.a₁ a₂ a₃ .... Оно принадлежит интервалу (0,1) и значит совпадает с каким-то из чисел x_i, т.е. найдется i₀: x_i0 = a. Но тогда x_i0i0 = a_i0, противоречие. Ч.т.д.