Сравнение мощностей

Теорема 1 (Кантора-Бернштейна).Пусть для множеств А и В существуют множества А₁ ÍА и В₁ ÍВ такие, что множество А равномощно с В₁, а множество В с А₁, то множества А и В равномощны.

Доказательство. Пусть f - биекция В на А₁, а g - биекция А на В₁. Тогда f(В)=А₁ и f(В₁)=А₂ ÍА₁. Суперпозиция h=fog функций является также биекцией А на А₂. Тогда функция h отображает

А на А₂

А₁ Í А на А₃ Í А

А₂ Í А₁ на А₄ Í А₃

А₃ Í А₂ на А₅ Í А₆ и т.д.

Отсюда следует, что h является биекцией

из А – А₁ на А₂ – А₃

из А₁ – А₂ на А₃ – А₄

из А₂ – А₃ на А₄ – А₅ и т.д.

Зададим множества

Е = (А – А₁)È(А₂ – А₃)È(А₄ – А₅)È(А₆ – А₇)È ...

F = (А₂ – А₃)È(А₄ – А₅)È(А₆ – А₇)È ...

D = АÇА₁ÇА₂ÇА₃ÇА₄Ç...

G = (А₁ – А₂)È(А₃ – А₄)È(А₅ – А₆)È ...

Из замеченного выше следует, что h является биекцией E на F. Кроме того, справедливы равенства А = DÈGÈE и А = DÈGÈF. Следовательно отображение Т из А в А₁, определяемое соотношением

является биекцией А на А₁, т.е. множества А и А₁ равномощны. Последнее означает, что все четыре множества в теореме равномощны.

Теорема 2. Пусть Х и У два множества такие, что Х¹Æ, У¹Æ и в У не менее двух элементов. Тогда множество всех функций, действующих из Х в У является множеством, мощность которого больше мощности множества Х.

Доказательство. Обозначим множество функций, действующих из Х в У через У^Х. Доказательство разобьем на две части. Сперва покажем, что существует инъекция множества Х на часть множества У^Х. Пусть у₁ÎУ, у₂ÎУ, у₁ ¹ у₂ и х₀ÎХ. Построим функцию f[х₀] следующим образом: f[х₀](х₀) = у₁, а если х ¹ х₀, то f[х₀] (х) = у₂. При таком построении различным элементам в Х соответствуют различные функции. Например, если х₁ ¹ х₀, то f[х₁](х₀) = у₂. Таким образом, получаем инъекцию из Х в У^X.

Покажем теперь, что не существует биекции между Х и У^X. Предположим противное, что g является биекцией из Х на У^X и g(x) = f^x ÎУ^Х. Покажем, что существует fÎУ^Х такое, что f ¹ f^х для любого хÎХ. Пусть хÎХ и f^хÎУ^Х соответствующая функция. Определим f(х) = аÎУ из условия а ¹ f^х(x). Такой элемент а в У обязательно найдется, т.к. в У не менее двух элементов. Таким образом построенная функция f не будет совпадать ни с одной функцией f . Следовательно g не может быть биекцией.

Теорема 3. Множество всех подмножеств произвольного непустого множества Х имеет мощность большую, чем мощность множества Х.

Доказательство. Положим У={0,1}. Рассмотрим множество У^Х. Если fÎУ^Х, то f разбивает Х на два множества: Х₀(f) = {xÎX: f(x)=0} и Х₁(f) = {xÎX: f(x) = 1}. Таким образом, каждому fÎУ^X соответствует множество Х₁(f). Наоборот, если Х₁ - некоторое подмножество из Х, то полагая

получим fÎУ^Х. Этим мы построили биекцию между множеством всех подмножеств множества Х и множеством У^Х. Следовательно они равномощны и по теореме 2 мощность множества Х меньше мощности множества всех подмножеств.

Примеры равномощных множеств

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

Пример 1. Установить биекцию между отрезком [0, 1] и отрезком [а, в].

Решение. Легко устанавливается биективность линейного отображения x = (в – a)t + a отрезка [0, 1] на отрезок [а, в].

Пример 2. Установить биекцию между интервалом (0, 1) и интервалом (–¥, +¥).

Решение. Легко устанавливается биективность отображения x= ctg(pt) интервала (0, 1) на интервал (–¥, +¥).

Задача. Рассмотреть основные элементарные функции и найти промежутки, на которых они являются биективным отображением.

Пример 3. Построить биекцию между отрезком [0, 1] и интервалом (0, 1).

Решение. Решение этой задачи основано на несчетности рассматриваемых множеств и теореме 4 из параграфа 6. Идея решения состоит в том, что из интервала (0, 1) выделяют некоторое счетное множество А. Затем к нему добавляют две точки {0} и {1}. Вновь полученное множество (обозначим его В Ì [0, 1]), также является счетным. Следовательно, множества А и В равномощны и существует биекция f, отображающая B на A. Построим теперь биекцию отрезка [0, 1] на интервал (0, 1) следующим образом:

Пример 4. Построить биекцию между окружностью единичного радиуса и отрезком [0, 1].

Схема решения. Легко устанавливается биекция между точкой окружности и углом, соответствующим этой точке. Этим получается биекция окружности и полуотрезка [0, 2p). Затем по схеме примера 3 строится биекция полуотрезка [0, 2p) на отрезок [0, 1].

Пример 5. Доказать, что множество всех окружностей на плоскости, радиусы которых рациональные числа и координаты центра которых - рациональные числа, есть счетное множество.

Решение. Нетрудно видеть, что каждый элемент рассматриваемого множества может быть отождествлен с тройкой чисел (х, у, r), где (х, у) - координаты центра окружности, а r - ее радиус. Этим между множеством указанных окружностей и множеством Q´Q´Q устанавливается биекция. Но произведение счетных множеств счетно (см. задачу в 6 параграфе) и, следовательно, наше множество также счетно.

Пример 6. Доказать, что множество точек разрыва монотонной функции, заданной на отрезке [а, в], конечно или счетно.

Решение. Предположим, что рассматриваемая функция f(х) является возрастающей. Пусть х_a точка разрыва этой функции. В силу монотонности функции и ее ограниченности ( f(а) < f(х) < f(в) ) в точке х_a будет существовать как предел слева, так и предел справа: Таким образом, множество точек разрыва { х_a } может быть отождествлено с множеством отрезков{[A_a , B_a]}. При этом необходимо заметить, получаемые отрезки могут пересекаться лишь на концах и все они лежат на отрезке [f(а), f(в)]. Поставим каждому отрезку [А_a, В_a] в соответствие рациональное число у_a, выбрав в качестве такового произвольное рациональное число из интервала (А_a, В_a) (наличие такое числа гарантируется аксиомой непрерывности действительных чисел и тем, что А_a ¹ В_a). В силу отмеченного выше, построенное соответствие будет являться инъекцией. Следовательно, мы построили инъекцию множества точек разрыва монотонной функции на отрезке [а, в] в счетное множество рациональных точек отрезка [f(а), f(в)]. Это означает, что рассмотренное множество точек разрыва не более чем счетно.