Мощность множеств

Речь пойдет о том, как сравнивать между собой разные множества. Начнем с простого примера. Перед вами кучки болтов и гаек. Требуется ответить на вопрос: поровну ли деталей в этих кучках и если нет, то каких деталей больше? Первая пришедшая в голову процедура: пересчитать детали в обеих кучках. Это не очень хорошая идея: при подсчете легко ошибиться, к тому же не спрашивается, сколько деталей каждого вида. Можно предложить другую процедуру. Будем откладывать одновременно по детали из каждой кучки. Если они исчерпаются одновременно, то деталей поровну, если в какой-то момент одна кучка закончится, а другая нет, то ясно, каких деталей больше.

Фактически этой процедурой мы пытались установить взаимно однозначное соответствие между двумя конечными множествами. Для КОНЕЧНЫХ множеств условие существования взаимно однозначного соответствия очевидно, все же сформулируем его в виде утверждения.

ПРЕДЛОЖЕНИЕ. Для того, чтобы между конечными множествами A и B существовало взаимно однозначное соответствие, необходимо и достаточно выполнение условия | A|= | B |.

Доказательство. 1. Пусть | A|= | B |= n. Перенумеруем элементы этих множеств: A ={ a ₁, a ₂,…, a_n }, B ={ b ₁ b ₂,…, b_n }. Построим отображение
по правилу . Очевидно, оба свойства взаимно однозначного соответствия выполняются.

2. Пусть теперь - взаимно однозначное соответствие и A ={ a ₁, a ₂,…, a_n }. Присвоим элементу номер i. По определению взаимно однозначного соответствия каждый элемент приобретет какой-нибудь номер (в силу первого свойства), причем единственный (в силу второго свойства). Таким образом, | B |= n.

Отсюда следует, что не существует взаимно однозначного соответствия между конечным множеством A и его частью (так мы называем подмножество A, не совпадающее с самим множеством A). Иначе обстоит дело с бесконечными множествами.

Пример. Пусть B – множество четных натуральных чисел, которое является частью множества натуральных чисел N. Отображение , заданное правилом , является взаимно однозначным соответствием. Интригующий вопрос. Существуют ли бесконечные множества, между которыми нельзя установить взаимно однозначное соответствие? Этот вопрос приводит к очень глубокому исследованию. Сначала дадим

ОПРЕДЕЛЕНИЕ 12. Множества A называются равномощным множеству B, если существует взаимно однозначное соответствие .

Теорема 5. Отношение равномощности является отношением эквивалентности.

Доказательство. Проверим свойства из определения 5.

Рефлексивность. Проверим, что множество равномощно… самому себе. Отображение , очевидно, является взаимно однозначным соответствием (оба свойства из определения 11 выполняются).

Симметричность. Если - взаимно однозначное соответствие, то , как отмечалось ранее, также взаимно однозначное соответствие. Таким образом, если A равномощно B, то и B равномощно A. Поэтому можно говорить о равномощности пары множеств A и B, не выделяя первое.

Транзитивность. Пусть равномощны пары множеств A и B, B и C. Это означает, что существуют взаимно однозначные соответствия и . По предыдущему также взаимно однозначное соответствие, т.е. множества A и C также равномощны.

Теорема доказана.

По предыдущему, равномощность конечных множеств означает, что в них поровну элементов, равномощны также множества натуральных и четных натуральных чисел.

Равномощность обозначается следующим образом: | A|=|B|. Символ | A| ранее использовался для обозначения числа элементов конечного множества, так что противоречия не возникает.

По теореме 3 семейство множеств распадается на классы эквивалентности, каждый из которых состоит из равномощных множеств. Один класс составят множества, в которых, например, 6 элементов, другой – 10 элементов и т.д. Можно считать, что 6 или 10 это обозначения этих классов. Конечные и бесконечные множества входят в разные классы (они заведомо не равномощны). Предыдущий интригующий вопрос теперь можно сформулировать так: образуют ли бесконечные множества один класс эквивалентности?

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

ОПРЕДЕЛЕНИЕ 13. Мощность множестваA не превосходит мощности множества B, если существует подмножество B ₁Ì B, для которого | A |=| B ₁|.

Теорема 6. Введенное отношение является отношением нестрогого порядка на семействе классов эквивалентности множеств.

Доказательство. 1. Важно, что речь идет именно о классах эквивалентности. Это означает, что если мощность множества A не превосходит мощности множества B, то отношение сохраняется при замене множеств A и B на эквивалентные A¢ и B¢. Проверим это утверждение. Пусть B ₁Ì B – подмножество, о котором говорится в определении и - взаимно однозначное соответствие. Далее, пусть также взаимно однозначные соответствия. Определим множество . Отображение является взаимно однозначным соответствием, т.е. мощность множества A¢ не превосходит мощности множества B¢, что и требовалось.

2. Введенное отношение рефлексивно. Действительно, мощность А не превосходит мощности А, поскольку можно принять А ₁= А.

3. Симметричность. Она означает, что если мощность A не превосходит мощности B и мощность B не превосходит мощности A, то | A|=|B|. Это утверждение является весьма глубоким и называется теоремой Кантора-Бернштейна.

Докажем это утверждение. Пусть подмножества А ₁Ì А и B ₁Ì B таковы, что | A |=| B ₁|, | A ₁|=| B | и - соответствующие взаимно однозначные соответствия. Определим для каждого элемента b Î B следующую характеристику (индекс). Рассмотрим чередующуюся последовательность элементов из множеств B и А (по теореме 4 отображения f,g обратимы):

Эта последовательность может продолжаться неограниченно, а может обрываться. Например, если b Î B \ B ₁, то эта последовательность состоит из одного элемента b. Множество B разбивается на три подмножества: B _¥ (входят те элементы, у которых последовательность неограниченная), B _о (последовательность конечная и содержит нечетное число элементов), B _е (последовательность конечная и содержит четное число элементов). Индексы – начальные буквы английских слов odd (нечетный) и even (четный). Аналогично можно определить индекс любого элемента a Î А, построив последовательность

и аналогично множество А разбивается на три подмножества: A _¥, A _о, A _е.

Проверим, что f (A _¥)= B _¥. Действительно, если b Î B _¥, то соответствующая последовательность продолжается неограниченно, а тогда это так и для элемента – удаление одного элемента из бесконечной последовательности не превращает ее в конечную! С другой стороны, если a Î A _¥, то последовательность для элемента f (a) получаем из последовательности для a добавлением одного элемента (f (a)), т.е. бесконечность сохраняется.

Проверим, что f (A _о)= B _е. Пусть b Î B _е, В последовательности, порожденной элементом b четное число элементов (не менее двух, поскольку она содержит хотя бы один элемент – b). Но тогда в последовательности, порожденной элементом элементов на один меньше, т.е. . Аналогично проверяется обратное: если a Î A _о, то f (a)Î B _е.

Аналогично проверяется, что .

Тем самым, отображение

является взаимно однозначным соответствием из A в B, поскольку таковы отображения на соответствующих подмножествах и эти подмножества образуют разбиения множеств A в B.

4. Транзитивность. Пусть мощность A не превосходит мощности B и мощность B не превосходит мощности C. Существуют подмножества B ₁Ì B и C ₁Ì C, для которых | A |=| B ₁|, | B |=| С ₁|, т.е. существуют взаимно однозначные соответствия . Рассмотрим множество C ₂= g (B ₁)Ì C ₁. Тогда отображения – взаимно однозначные соответствия (в последнем случае это ограничение исходного отображения на множество ). А потому таковым является и их композиция . Таким образом | A |=| C ₂|, т.е. по определению мощность A не превосходит мощности C. Теорема доказана.

Для этого отношения используется стандартный символ | A |≤| B |. Доказанная теорема показывает, что его использование не противоречит интуиции, связанной с использованием этого символа для чисел.

Замечание. Как следует из определения 13, если A Ì B, то | A |≤| B |.

Очень важным и глубоким является следующий результат, доказательство которого выходит за рамки данного курса.

Теорема 7. Любые множества A и B сравнимы по отношению ≤, т.е. имеет место хотя бы одно из двух соотношений: | A |≤| B |, | B |≤| A |.

Таким образом, введенное отношение порядка является линейным.

По отношению нестрогого порядка естественным образом строится отношение строгого порядка.

ОПРЕДЕЛЕНИЕ 14. Мощность множества A меньше мощности множестваB (| A |<| B |), если | A |≤| B | и при этом | A |¹| B |, т.е. множества не равномощны.

Вернемся к вопросу о бесконечных множествах. Великое открытие Георга Кантора состоит в том, что бесконечности могут быть разными. Прежде, чем формулировать и доказывать теорему Кантора, напомним понятие вещественного числа (мы будем их записывать в десятеричной системе счисления). Вещественное число состоит из знака (+ или -), целой части, после которой записывается запятая, а за ней бесконечная последовательность цифр 0, 1, …, 9. Числа, в вещественной части которых «хвосты» состоят из 0 и 9, равны (например, 0,879999…=0,88000…). Сравнение вещественных чисел осуществляется в соответствии с лексикографическим порядком. Теперь все готово для формулировки и доказательства следующего результата.

Теорема 8 (первая теорема Кантора). | N |<|[0,1]|. Здесь слева множество натуральных чисел, справа – множество вещественных чисел из отрезка [0,1].

Доказательство. Докажем сначала легкую часть: | N | ≤ |[0,1]|. Для этого выберем из отрезка [0,1] подмножество {0,100…; 0,1100…; 0,11100…; …} и сопоставим натуральному числу n тот элемент этого подмножества, в котором n единиц. Очевидно, что построено взаимно однозначное соответствие между множеством N и подмножеством отрезка [0,1], что и требовалось.

А теперь трудная часть. Докажем, что | N |¹|[0,1]|. При доказательстве используется замечательный диагональный метод Кантора, в результате трудная часть окажется не такой уж трудной! Доказательство проведем от противного. Пусть напротив | N |=|[0,1]|. Это означает, что существует взаимно однозначное соответствие . Таким образом,

Здесь a_ij – цифры. По предположению, в правых частях этих равенств перечислены ВСЕ числа из отрезка [0,1]. Приведем это предположение к противоречию, а именно, найдем на отрезке [0,1] такое число, которого нет в правых частях.

Пусть и b= 0, b ₁ b ₂… b_n ….

Числа b в правых частях нет! Действительно, число b не имеет хвоста из 0 или 9 и значит, записывается единственным образом. , поскольку у этих чисел разные первые цифры; , поскольку у этих чисел разные вторые цифры; … , поскольку у этих чисел разные n- е цифры;… Теорема доказана.

Итак, бесконечности бывают разные. Оказывается, бесконечность, которую представляет множество N, является, если можно так выразиться, самой мелкой.