Взаимно однозначные соответствия и мощности множеств

Если между конечными множествами А и В существует взаимно однозначное соответствие, то |А|=|В|. Действительно, если это не так, то либо |A|>|B|, и тогда, поскольку отображение всюду определено, в А найдутся два элемента, которым соответствует один и тот же элемент b  В (нарушится единственность образа), либо |A|<|B|, и тогда, поскольку отображение сюръективно, в В найдутся два элемента, соответствующих одному и тому же
a A (нарушится единственность прообраза).

Этот факт, во-первых, позволяет установить равенство мощностей двух множеств, не вычисляя этих мощностей, а во-вторых, часто дает возможность вычислить мощности множества, установив его взаимно однозначное соответствие с множеством, мощность которого известна или легко вычисляется. В качестве иллюстрации этого приема докажем важную теорему о числе подмножеств конечного множества.

Теорема 3.2. Если для конечного множества А |A| = n, то число всех подмножеств А равно 2ⁿ, т. е. 2^|A|.

Занумеруем элементы А номерами от 1 до п: А ={a₁, a₂, …, a_n} и рассмотрим множество B_n двоичных векторов из нулей и единиц длины п. Каждому подмножеству A*ÎA поставим в соответствие вектор v = (v₁, v₂, …, v_n) B_n следующим образом:

Например, если A={а, b, с, d, e}, то подмножеству {a,c,d} соответствует вектор (1, 0, 1, 1, 0), а подмножеству {b} соответствует вектор (0, 1, 0, 0, 0). Пустому подмножеству любого А соответствует вектор из одних нулей, а самому А – вектор из одних единиц. Очевидно, что установленное соответствие между множеством всех подмножеств А и двоичными векторами длины п является взаимно однозначным и число подмножеств А равно |В_n|. Так как B_n является прямым произведением п двухэлементных множеств {0, 1}, то в силу следствия из теоремы 3.1 |B_n| =2ⁿ.

Множества равномощны, если между их элементами можно установить взаимно-однозначное соответствие. Для конечных множеств это утверждение доказывается, что и было сделано ранее. Для бесконечных множеств оно является определением равномощности. Множества, равномощные N, называются счетными. Вообще любое бесконечное подмножество N счетно. Действительно, пусть N'Ì N. Выберем в N' наименьший элемент и обозначим его n₁; в N'{n₁} выберем наименьший элемент и обозначим его n₂; наименьший элемент N' {n₁,n₂} обозначим n₃ и т. д. Поскольку для всякого натурального числа имеется лишь конечное множество меньших натуральных чисел, то любой элемент N' рано или поздно получит свой номер. Эта нумерация, т. e. соответствие (n_i, i), и есть взаимно-однозначное соответствие между N' и N.

Множество N² счетно. Нумерацию N² можно устроить следующим образом. Разобьем N² на классы. К первому классу N²₁ отнесем все пары чисел с минимальной суммой. Такая пара всегда одна: (1,1). Ко второму классу N²₂ отнесем все пары чисел с суммой 3: N ²₂ = {(1, 2), (2, 1)}. В общем случае
N²_i = {(a,b)| a + b = i + 1}. Каждый класс N²_i  содержит ровно i пар. Упорядочим теперь классы по возрастанию индексов i, а пары внутри класса – по возрастанию первого элемента и занумеруем получившуюся последовательность пар номерами 1, 2, 3... . Легко видеть, что если a + b = i + 1, то пара (a,b) получит номер 1+2+…+(i – 1) + a. Эта нумерация и доказывает счетность N², из которой, в свою очередь, непосредственно следует счетность множества Р положительных рациональных чисел, т.e. дробей вида а/b, где а и b – натуральные числа. На примере множества Р видно, что нумерация числового множества может не иметь ничего общего с упорядочением его элементов по величине. В множестве Р нет ни наименьшего элемента, ни двух соседних по величине элементов (для любых двух дробей p₁ и p₂ всегда найдется дробь, лежащая между ними, например (p₁ + p₂)/2), однако есть элемент с наименьшим номером и элементы с соседними номерами. Аналогично доказывается счетность N³ и вообще N^k для любого натурального k.

Нетрудно понять, что объединение конечного числа счетных множеств M₁, M₂, …, M_k счетно. Действительно, перенумеруем сначала все первые элементы множеств, затем все вторые и т. д. Объединение счетного множества конечных множеств также счетно (сначала нумеруем все элементы первого множества, затем все элементы второго множества и т. д.). Из последнего утверждения следует, что множество всех слов в любом конечном алфавите счетно. Менее очевидно, что счетно и объединение счетного множества счетных множеств.

Множество всех действительных чисел отрезка [0, 1] не является счетным (теорема Кантора). Действительно, предположим, что оно счетно и существует его нумерация. Расположим все числа, изображенные бесконечными десятичными дробями, в порядке этой нумерации:

Рассмотрим любую бесконечную десятичную дробь 0, b₁ b₂ b₃ … такую, что b₁¹a₁₁, b₂¹a₂₂, b₃¹a₃₃ и т. д. Эта дробь не может войти в указанную последовательность, так как от первого числа она отличается первой цифрой, от второго числа – второй цифрой и т. д. Следовательно, все числа из отрезка [0, 1] не могут быть пронумерованы, и множество всех действительных чисел отрезка [0, 1] несчетно. Его мощность называется континуум; множества такой мощности называются континуальными. Метод, использованный при доказательстве, называется диагональным методом Кантора.

Множество всех подмножеств счетного множества континуально. Это становится ясным, если воспользоваться, как и в теореме 1.2, представлением подмножества в виде последовательности (но теперь уже бесконечной) нулей и единиц: на i-м месте стоит 1, если i-й элемент множества входит в данное подмножество, и 0 в противном случае. Получаем взаимно однозначное соответствие между подмножествами счетного множества и правильными двоичными дробями, которые, в свою очередь, взаимно однозначно соответствуют множеству чисел отрезка [0, 1]. Как показывается в теории множеств (с помощью метода, аналогичного диагональному), для множества любой мощности множество его подмножеств имеет более высокую мощность. Поэтому не существует множества максимальной мощности. Парадокс Кантора как раз и заключается в том, что «множество всех множеств» должно содержать все множества и, следовательно, иметь максимальную мощность, что противоречит результатам теории множеств.