Материал: Ответы на экзаменационные вопросы по дискретной математике

Справедлива теорема Ф. Бернштейна «о трихотомии»: для любых двух множеств с мощностями и соответственно обязательно выполняется одно из 3 соотношений: (то есть любые два множества сравнимы по количеству их элементов).

Очевидно, что отношение эквивалентности множеств обладает всеми свойствами понятия эквивалентности:

1. .

2. Если , то .

3. Если и , то .

Счётные множества — множества, равномощные с натуральным рядом, то есть с множеством ; их мощность обычно обозначается символом . Иными словами, счётные множества — это те множества, элементы которых можно расположить в одной последовательности (индекс и есть то натуральное число, которое сопоставляется элементу счётного множества). Например, множество всех чётных чисел счётно; соответствующая биекция , или . Интересно, что множество всех рациональных чисел тоже счётно (напоминаем, что рациональным числом называется отношение двух целых чисел ). Иными словами, справедлива теорема: .

Доказательство. Запишем сначала все дроби, у которых сумма числителя и знаменателя равна 2 (такое число одно: ), затем те, у которых сумма числителя и знаменателя равна 3 (то есть ), затем те, у которых она равна 4 (), следующие 4 дроби таковы: , и так далее. В этой последовательности, очевидно, появятся все положительные дроби (так как у каждой дроби есть некоторая сумма числителя и знаменателя), но каждая дробь появится бесконечно много раз (некоторые дроби сократимы). Однако мы можем удалить из получившейся последовательности все сократимые дроби, и тогда получим последовательность всех положительных рациональных чисел, в которой каждое число встречается только один раз. Чтобы расположить в одну последовательность все рациональные числа — положительные, отрицательные и 0, составим из последовательности новую последовательность по правилу: . В последовательности расположены все рациональные числа, причём каждое — по одному разу, а это означает, что их множество счётно.

Кроме того, следуя следующим простым шагам, можно построить дерево из всех положительных рациональных дробей:

• Начинаем с в вершине дерева.

• Значение нижнего левого узла относительно текущего : .

• Значение нижнего правого узла относительно текущего : .

Рисунок 19

Мощность континуума — мощность множества всех вещественных чисел . Также термин «континуум» может обозначать само множество вещественных чисел , или даже любое континуальное множество (любое бесконечное множество, равномощное множеству действительных чисел).

Пример множества, имеющего мощность континуума: множество всех точек отрезка ; его мощность обозначается символом .

Теорема. , то есть множество точек отрезка несчётно, но имеет счётное подмножество (таким образом, точек на отрезке принципиально больше, чем натуральных чисел).

Доказательство. Предположим, что подмножество точек отрезка счётно. Осталось доказать, что не существует биекции этого отрезка на счётное множество. Предположим противное: что такая биекция отрезка существует, то есть все точки отрезка можно расположить в одну последовательность . Каждое число отрезка можно записать в виде бесконечной десятичной дроби, причём однозначно, если исключить записи, в которых после некоторой цифры все последующие цифры равны 9. Обозначим последовательные десятичные цифры числа через , то есть , где означает -ую цифру числа . Составим бесконечное десятичное число , каждая цифра которого отличается на 1 от соответствующего десятичного знака числа , то есть число (знак «» или «» перед единицей можно выбирать произвольно, если только соответствующая цифра не является нулём или девяткой). Это число принадлежит отрезку и поэтому должно совпадать с одним из чисел , например . Но оно не может совпадать с , так как десятичная цифра с номером у чисел и — разная (они отличаются на единицу по построению). Полученное противоречие доказывает, что предположение неверно, и теорема доказана.

Следствия.

1. Все отрезки имеют мощность континуума. Действительно, биекция между и задаётся формулой .

2. Любой интервал имеет мощность континуума. Для доказательства достаточно установить биекцию между и . Построим её так:

3. Множество точек любой окружности имеет мощность континуума: очевидна биекция между окружностью и полуоткрытым интервалом , а по предыдущему существует биекция между и .

4. Множество точек любой прямой имеет мощность континуума.

Соответствующая биекция: .

5. Множество точек квадрата , то есть точек, у которых тоже имеет мощность континуума, то есть справедливо:

Доказательство. Как и ранее, каждую точку отрезка запишем в виде бесконечной десятичной дроби: … Соответствующая биекция задаётся формулами: (например, точке отрезка биекция сопоставляет точку квадрата, координаты которой таковы: , ) и эта биекция доказывает теорему.

Замечание. Аналогично доказывается, что и трёхмерный, и четырёхмерный куб, и куб любой конечной размерности имеет мощность континуума. Отсюда следует, что множество всех точек плоскости , трёхмерного пространства и любого конечномерного пространства имеет мощность континуума. Может показаться, что множеств с большей мощностью, чем мощность континуума, не существует. Но это не так. Рассмотрим множество всех подмножеств данного множества мощности . Его мощность обозначается как . Это обозначение связано с тем, что если множество конечно и содержит элементов, то число всех его подмножеств (включая несобственные) равно . Действительно, если обозначить элементы данного множества через , то каждому подмножеству этого множества взаимно однозначно соответствует упорядоченный набор из нулей и единиц, в котором единицы соответствуют элементам, вошедшим в подмножество, а нули — тем, которые не вошли. Для наглядности перечислим все подмножеств множества , состоящего из трёх элементов:

Теорема. Каково бы ни было множество мощности , существует множество большей мощности, например, .

Доказательство. То, что данное множество эквивалентно некоторому набору своих подмножеств, очевидно: оно эквивалентно набору одноэлементных подмножеств. Поэтому надо доказать, что не существует биекции между данным множеством и множеством всех его подмножеств. Предположим противное, то есть что существует биекция , сопоставляющая каждому элементу данного множества некоторое его подмножество . Возможны два варианта: 1) элемент входит в множество , которое ему сопоставляет биекция , такие элементы будем называть «хорошими»; 2) элемент не входит в множество , которое ему сопоставляет биекция , такие элементы будем называть «плохими». Рассмотрим подмножество всех «плохих» элементов. Этому подмножеству биекция сопоставляет некоторый элемент данного множества. Он не может быть «хорошим», так как входит в подмножество всех «плохих» элементов, и значит, он — «плохой». Но он не может быть и «плохим», так как иначе (то есть если бы он был «плохим») он входил бы в то множество «плохих» элементов, которое ему сопоставляет биекция , и, следовательно, был бы «хорошим». Итак, элемент — не является ни «хорошим», ни «плохим». Но каждый элемент обязательно либо «хороший», либо «плохой». Получили противоречие. Значит, предположение неверно, и теорема доказана.

Утверждение 1. Мощность бесконечного множества не изменится, если его объединить со счётным множеством.

Доказательство. Пусть — бесконечное множество, значит у него найдётся счётное подмножество . Пусть — счётное множество, следовательно, — также счётное множество. По определению счётного множества между множеством и множеством натуральных чисел можно установить биекцию. Таким же образом установим биекцию между и . Композиция этих биекций будет биекцией множеств и . В рамках того же отображения переведём оставшиеся элементы множества сами в себя, то есть элементы станут соответствовать самим себе. В итоге получим биекцию множеств и (элементы отображаются сами в себя, в , также в ), следовательно, по определению, эти множества равномощны.