Как найти мощность подмножества

Мо́щность, или кардина́льное число́, мно́жества (лат. cardinalis ← cardo «главное обстоятельство; основа; сердце») — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

В основе этого понятия лежат естественные представления о сравнении множеств:

1. любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция), содержат одинаковое количество элементов (имеют одинаковую мощность, равномощны);
2. обратно: равномощные множества должны допускать такое взаимно-однозначное соответствие;
3. часть множества не превосходит полного множества по мощности (то есть по количеству элементов).

До того, когда была построена теория мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.

Мощность множеств позволяет сравнивать бесконечные множества.
Например, счётные множества являются самыми «маленькими» бесконечными множествами.

Мощность множества обозначается через .
Иногда встречаются обозначения , и .

Определение[править | править код]

Если принять аксиому выбора, мощность множества формально будет определяться как наименьшее порядковое число , при котором между и можно установить биективное соответствие. Данное определение также называется распределением кардинальных чисел по фон Нейману.

Если не принимать аксиому выбора, то требуется иной подход. Самое первое определение мощности множества (оно неявно присутствует в работах Кантора и явным образом сформулировано у Фреге, а также в Principia Mathematica) представляет собой класс всех множеств, равномощных . В аксиоматических системах, основанных на теории ZFC, такое определение неприменимо, поскольку при непустом такая совокупность слишком велика, чтобы подходить под определение множества. Точнее, если , то существует инъективное отображение универсального множества в , при котором каждое множество переходит в , откуда, в силу аксиомы ограничения размера следует, что  — собственный класс. Данное определение можно использовать в теории типов и «новых основаниях»^[en], а также в связанных с ними аксиоматических системах. В случае ZFC определение можно использовать, если ограничить коллекцию равномощными множествами с наименьшим рангом (этот приём, предложенный Даной Скоттом, работает благодаря тому, что совокупность объектов, обладающих заданным рангом, является множеством).

Формальный порядок среди кардинальных чисел вводится следующим образом: означает, что множество можно инъективно отобразить на . Согласно теореме Кантора — Бернштейна, из пары неравенств и следует, что . Аксиома выбора эквивалентна утверждению о том, что для любых множеств и выполняется по крайней мере одно из неравенств или .

Множество называется бесконечным по Дедекинду^[en], если в нём существует такое собственное подмножество , что . В противном случае множество называется конечным по Дедекинду. Конечные кардинальные числа совпадают с обычными натуральными числами или нулём, — иначе говоря, множество конечно тогда и только тогда, когда при некотором натуральном или при (если множество пустое). Все остальные множества бесконечны. При соблюдении аксиомы выбора можно доказать, что определения по Дедекинду совпадают со стандартными. Кроме того, можно доказать, что мощность множества натуральных чисел (алеф-нуль, или алеф-0, — название образовано от первой буквы еврейского алфавита ) представляет собой наименьшее бесконечно большое кардинальное число, то есть в любом бесконечном множестве есть подмножество мощности . Следующее по порядку кардинальное число обозначается и так далее, число алефов бесконечно. Любому порядковому числу соответствует кардинальное число , причём таким образом можно описать любое бесконечно большое кардинальное число.

Связанные определения[править | править код]

• Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств и возможно только одно из трёх:
  1. , или и равномощны;
  2. , или мощнее , то есть содержит подмножество, равномощное , но и не равномощны;
  3. , или мощнее  — в этом случае содержит подмножество, равномощное , но и не равномощны.
• Множества и называются эквивалентными, если существует взаимно однозначное отображение множества на множество .^[1]

Примеры[править | править код]

• Множество называется счётным, если оно равномощно множеству всех натуральных чисел . Счётными множествами являются:

• Бесконечные множества, неравномощные множеству , называются несчётными. По теореме Кантора несчётным является множество всех возможных бесконечных последовательностей, составленных из цифр 0 и 1. Мощность этого множества называется континуум.

• Мощность множества вещественных чисел равна континууму.

Свойства[править | править код]

Арифметика кардинальных чисел[править | править код]

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

Следующее по порядку кардинальное число[править | править код]

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

Через обозначают предыдущее кардинальное число для числа если таковое существует; в противном случае, .

Сложение кардинальных чисел[править | править код]

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

Нейтральность нуля относительно сложения:

Ассоциативность:

Коммутативность:

Монотонность (неубывание) сложения по обоим аргументам:

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

Вычитание[править | править код]

При соблюдении аксиомы выбора для любого бесконечного кардинального числа и произвольного кардинального числа существование , при котором , эквивалентно неравенству . Такое единственно (и совпадает с ) тогда и только тогда, когда .

Умножение кардинальных чисел[править | править код]

Произведение двух кардинальных чисел выражается через декартово произведение множеств:

Свойства нуля:

Нейтральность единицы относительно умножения:

Ассоциативность:

Коммутативность:

Монотонность (неубывание) умножения по обоим аргументам:

Дистрибутивность умножения относительно сложения:

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

Деление[править | править код]

При соблюдении аксиомы выбора для любой пары кардинальных чисел и , где бесконечно, а не равно нулю, существование , при котором , эквивалентно неравенству . Такое единственно (и совпадает с ) тогда и только тогда, когда .

Возведение кардинальных чисел в степень[править | править код]

Возведение в степень определяется следующим образом:

,

где обозначает множество всех функций из в .

(в частности, ), см. «Пустая функция»

Монотонность:

Заметим, что представляет собой мощность булеана и, следовательно, для любого множества (см. Диагональный метод Кантора). Отсюда следует, что среди кардинальных чисел нет наибольшего (поскольку для любого кардинального числа можно указать большее число ). В действительности класс всех кардинальных чисел является собственным (хотя в некоторых системах аксиом теории множества этого доказать нельзя — к таковым, например, относится система «Новых оснований»^[en]).

Все последующие утверждения, приведённые в этом разделе, опираются на аксиому выбора.

Если и  — конечные числа, большие 1, а  — бесконечное кардинальное число, то
Если кардинальное число бесконечно, а конечно и отлично от нуля, то .

Если и , причём хотя бы одно из них бесконечно, то

.

Используя теорему Кёнига, можно доказать, что для любого бесконечного кардинального числа выполняются неравенства:

,

где обозначает конфинальность .

Извлечение корней[править | править код]

Если соблюдать аксиому выбора, то для любого бесконечного кардинала и конечного кардинала существует кардинальное число , при котором , причём .

Логарифмы[править | править код]

При соблюдении аксиомы выбора кардинальное число , удовлетворяющее условию , при заданном бесконечном и конечном , существует не всегда. Если же такое существует, то оно бесконечно и меньше , причём любое конечное кардинальное число также будет удовлетворять равенству .

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

Континуум-гипотеза[править | править код]

Согласно континуум-гипотезе, между и не существует других кардинальных чисел. Кардинальное число также обозначается и представляет собой мощность континуума (то есть множества вещественных чисел). В данном случае . Обобщённая континуум-гипотеза отрицает существование кардинальных чисел, заключённых строго между и , для любого бесконечного множества . Континуум-гипотеза является независимой от стандартной аксиоматизации теории множеств, то есть системы аксиом Цермело-Френкеля в сочетании с аксиомой выбора (см. Теория множеств Цермело-Френкеля).

См. также[править | править код]

• Порядковое число

Примечания[править | править код]

Литература[править | править код]

• А. А. Болибрух, Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза Архивная копия от 3 июня 2004 на Wayback Machine, Библиотека «Математическое просвещение», Выпуск 2
• Р. Курант, Г. Роббинс, Что такое математика? Глава II, § 4.
• Факультативный курс по математике. 7-9 / Сост. И. Л. Никольская. — М.: Просвещение, 1991. — С. 109-110. — 383 с. — ISBN 5-09-001287-3.
• Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.

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

, ,.

Какое
из этих соотношений имеет место, можно
решить двумя способами. Можно пересчитать
число элементов каждого из множеств и
сравнить полученные числа. А можно
сравнить два множества путем установления
взаимно однозначного соответствия
между их элементами.

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

Обозначают:
.
Определенное нами бинарное отношение
эквивалентности между множествами
обладает свойствами:

1)
рефлексивность:
,

2)
симметричность:
из того, что
следует, что,

3)
транзитивность:
если
и,
то,
т.е. действительно являетсяэквивалентностью.

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

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

Например,
линейная функция
устанавливает взаимно однозначное
соответствие между точками интервалаи точками интерваладля любого.
Функцияустанавливает взаимно однозначное
соответствие между всеми точками
интервалаи точками прямой линии.

Замечание:
Понятие
мощности для конечного множества
совпадает с понятием числа элементов
этого множества. Кардинальное число –
это количество элементов во множестве.

Определение
2: Множества,
обладающие одинаковой мощностью,
называются равномощными
(эквивалентными).

Два
конечных множества будут равномощными,
если в них содержится одинаковое число
элементов. Если имеем дело с бесконечными
множествами, то вопросы, связанные с
мощностями, решаются путём установления
соответствия между элементами этих
множеств.

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

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

Теорема
1 (о
мощности промежуточного множества):
Пусть
,
причем,
тогда.

Т.е.
теорема утверждает, что, если мощности
крайних множеств одинаковы, то и мощность
среднего (промежуточного множества),
будет такой же.

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

,

таких,
что
,,,…

Кроме того, имеют
место следующие эквивалентности:

,

,

.

Обозначим
через
общую часть множеств.
Представим теперь множестваив виде сумм попарно непересекающихся
частей:

,

.

Эти
части эквивалентны, так как слагаемые
первой и второй строки либо совпадают,
либо эквивалентны. Что и требовалось
доказать.

Теорема
2
(Кантора-Бернштейна):
Если каждое из двух данных множеств
эквивалентно некоторой части другого
множества, то данные множества
эквивалентны.

Доказательство:Пусть даны
два множества
и,
причёми.
Частиипредполагаем собственными, т.к. иначе
теорема очевидна. Поставим элементы
множестваво взаимно однозначное соответствие
элементам множестваи назовем,
ту собственную часть множества,
которая составлена из элементов,
соответствующих элементам множества.
Тогда,
причем,,
следовательно, используя свойство
транзитивности отношения эквивалентности,
имеем:.
Согласно предыдущей теореме,,
но,
значит данные множества эквивалентны:.
Теорема доказана.

Следствие:
Таким
образом, при сравнении двух бесконечных
множеств возможны следующие случаи:

1)
между элементами множеств можно
установить взаимно однозначное
соответствие, тогда данные множества
равномощны;

2)
между элементами множеств нельзя
установить взаимно однозначное
соответствие, но можно установить
взаимно однозначное соответствие между
элементами одного из них и собственной
частью другого, тогда мощность одного
множества больше мощности другого.

Далее
рассмотрим наиболее распространенные
виды множеств в зависимости от их
мощности.

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

Доказательство:
Пусть дано
непустое множество
.
Обозначим множество всех его подмножеств.
Мы покажем, чтоне эквивалентнои что, кроме того,эквивалентно некоторой части множества.
Будем считать, что во множество подмножестввместе с другими входят несобственные
подмножества множества.
Докажем неэквивалентность множестви.
Доказательство проведём от противного.
Предположим, что.
Тогда каждому элементусоответствует некоторое подмножествотого же множества,
являющегося элементом множества.
В данной ситуации возможны два случая.
Либо элементпринадлежит тому подмножеству, которому
тот соответствует, либо нет. Разобьём
в соответствии с этим все элементы
множествана две категории: «включенные» элементы
и «не включенные». Обе категории не
пусты. Так, элемент множества,
соответствующий всему множествукак подмножеству, является включенным,
а элемент множества,
соответствующий его пустому подмножеству
– не включённым. Рассмотрим подмножествомножества,
составленное из всех не включённых
элементов. Пусть этому элементу множествасоответствует некоторый элемент.
Тогда окажется, чтоне может быть ни включенным, ни не
включенным элементом. В самом деле, если
он включенный, то,
что невозможно т.к.составлено из не включенных элементов.
Если– не включённый элемент, то он должен
принадлежать,
где собраны не включенные элементы, но
тогда он оказывается включенным. Значит,
и этот случай невозможен. Пришли к
противоречию, которое возникло из-за
неверного допущения. Тем самым доказано,
что множестваине эквивалентны.

Доказательство
того, что
,
где– собственное подмножество множества,
очень просто. Достаточно взять в качествевсе одноэлементные подмножества
множестваи поставить каждому из них в соответствие
тот
же элемент,
из которого это одноэлементное множество
состоит. Теорема доказана.

Следствие:
Из доказанной
теоремы следует, что для каждого
кардинального числа существует большее
кардинальное число.

В
последующих рассуждениях важное место
занимает множество натуральных чисел.

Определение
3: Множество,
эквивалентное множеству чисел натурального
ряда, называется счетным.

Натуральный
ряд чисел – это счётное множество. Все
множества, равномощные множеству
,
имеют такую же мощность.

Теорема
4: Для того
чтобы множество
было счетным, необходимо и достаточно,
чтобы его элементы можно было
«перенумеровать», т.е. представить в
форме последовательности:

. (1)

Доказательство:
Если
множество
представлено в форме (1), то достаточно
каждому элементупоставить в соответствие его индекс,
чтобы получить взаимно однозначное
соответствие между множествоми,
так что– счётно.

Обратно,
если
– счётно, то существует взаимно однозначное
соответствиемежду множествамии.
Обозначимчерези получим представление в форме (1).

Теорема
5: Из всякого
бесконечного множества
всегда можно выделить счётное подмножество.

Доказательство:
Пусть
– бесконечное множество. Возьмем в этом
множестве произвольный элемент.
Т.к.бесконечно, то в нём есть и другие
элементы. Можно выбрать элемент.
По тем же соображениям множествоне пусто и в нём можно выбрать элемент.
Ввиду бесконечности множестваэтот процесс можно продолжать
неограниченно. В результате получили
последовательность элементов:.
Эта выбранная последовательность и
образует счётное подмножество,
т. к. все элементы в ней перенумерованы.
Что и требовалось доказать.

Следствие:
Таким
образом, мощность счётного множества
наименьшая из всех мощностей бесконечных
множеств. Всем множествам, эквивалентным
множеству
,
ставится в соответствие одно и то же
кардинальное число.

Теорема
6: Всякое
бесконечное подмножество счётного
множества счётно.

Доказательство:
Пусть
– счетное множество, а– его бесконечное подмножество. Так как
множество– счётно, то все его элементы можно
перенумеровать, т. е. представить в виде
последовательности:.
Будем перебирать один за другим элементы
множествав порядке возрастания их номеров. При
этом нам будут встречаться элементы
множества.
Соотнося каждому элементу множестваномер «встречи» с ним, мы перенумеруем
множество,
причём, в силу бесконечности,
на его нумерацию пойдут все натуральные
числа.

Следствие:
Если из счётного множества удалить
конечное подмножество, то оставшееся
множество будет счётным.

Перечислим ещё
некоторые свойства счётных множеств.

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

Сумма
конечного или счетного числа попарно
не пересекающихся счетных множеств
есть счётное множество. Покажем
схематически, как можно занумеровать
полученную сумму для конечного числа
слагаемых:,
где множестваимеют следующий вид:

,

,

.

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

Далее
рассмотрим сумму (объединение) счётного
числа попарно не пересекающихся счётных
множеств:
.

На
рисунке показана примерная схема
нумерации элементов данных множеств.
Пользуясь рассмотренными свойствами
счётных множеств, можно всех целых чисел– счётно:

.

.

Это
множество – есть объединение конечного
числа счётных множеств, следовательно,
оно является счётным.

Также
схематически можно показать, что
множество всех точек плоскости с
целочисленными координатами счетно.
Отсюда нетрудно вывести, что множество
всех рациональных чисел также счетно.

Ниже рассмотрим
множества, мощность которых отлична от
мощности счётного множества.

Теорема
7: Множество
всех последовательностей из нулей и
единиц не счетно.

Доказательство:
Рассматриваемое
множество, очевидно, является бесконечным.
Поэтому достаточно доказать, что не
существует взаимно однозначного
отображения множества натуральных
чисел на множество двоичных
последовательностей. Докажем это
утверждение методом от противного.
Предположим, что множество всех двоичных
последовательностей можно перенумеровать,
т.е. любой последовательности из нулей
и единиц можно поставить в соответствие
некоторый натуральный номер. Схематически
это соответствие можно представить
следующим образом:

,

,

,

. . . . . . . . . . . . .
. . . . . . ,

,

. . . . . . . . . . . . .
. . . . . . ,

Где
– это элементы двоичных последовательностей,
т. е. 0 или 1.

Покажем,
что существует двоичная последовательность,
которая при этом не получит номера.
Построим такую последовательность
следующим образом. Выберем первый её
элемент(если,
то;
если,
то).
Аналогично выбираем остальные элементы:,,…,и т.д. Тем самым, для всех индексовбудет выбран элемент(если,
то;
если,
то).
Тогда построенная последовательностьне совпадает с первой последовательностью,
так как.
Она не совпадает со второй последовательностью,
т.к.и т.д. Последовательностьне совпадает с последовательностью,
получившей номер,
т.к.и т.д. Таким образом, последовательностьне
может получить номера вопреки
предположению. Это означает, что множество
всех двоичных последовательностей не
эквивалентно множеству натуральных
чисел. Тем самым доказано, что множество
двоичных последовательностей нечетно.

Замечание:
Метод доказательства, примененный в
теореме 7, называют Канторовым
диагональным методом.
Его можно использовать при решении
задач и при доказательстве подобных
утверждений.

Применяя
Канторов диагональный метод, можно,
например, доказать, что множество всех
точек отрезка
несчетно.

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

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

На
протяжении трех лет (с 1871 по 1874г.)
основатель теории множеств Георг Кантор
искал доказательство того, что взаимно
однозначное соответствие между точками
отрезка и точками квадрата невозможно.
Неожиданно ему удались построить
соответствие, которое он считал
невозможным! Математику Дедекинду он
писал: «И вижу это, но не верю». Но интуиция
подвела и здесь.

Дадим
эскиз доказательства Кантора. Каждую
точку квадрата можно задать её координатамии.
Эти числа можно записать, как бесконечные
десятичные дроби, т.к.и.
не больше 1.

Пусть
,(для простоты мы взяли внутренние точки
квадрата). Выпишем число,
десятичные знаки которого получаются
«перемешиванием» десятичных знаков
чиселиследующим образом:.

Точка
принадлежит отрезку,
причем соответствиеявляется взаимно однозначным. Таким
образом, установлено взаимно однозначное
соответствие между всеми точками
квадрата и частью точек отрезка.
Это показывает, что множество, точек
квадрата имеет не большую мощность, чем
множества точек отрезка. Но его мощность
и не меньшее, а потому эти мощности
совпадают. Не только квадрат, но и куб,
и вообще любая геометрическая фигура,
содержащая хотя бы одну лини, имеет
столько же точек и отрезок. Такие
множества назовёммножествами
мощности континуум
(от латинского слова continuum
– непрерывный).

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

Возникает
вопрос, существует ли множество, мощность
которого больше мощности счетного
множества и меньше, чем континуум. Эта
задача получила название проблемы
континуума.
Над этой проблемой думали многие
выдающиеся математики, начиная с Г.
Кантора, но до 60-х годов XX века эта
проблема оставалась нерешенной. В
течение многих лет думал над этой
проблемой один из крупнейших математиков
Н.Н. Лузин. Правда, в ходе размышлений
над проблемой континуума Н.Н Лузин решил
целый ряд труднейших задач теории
множеств и создал целый раздел математики
– дескриптивную теорию множеств.

Неудачи
попыток решить проблему континуума не
были случайными. Оказалось, что положение
дел здесь напоминает историю постулата
параллельных прямых. Этот постулат
пытались на протяжении двух тысячелетий
вывести из остальных аксиом евклидовой
геометрии. После работ Лобачевского,
Гильберта и ряда других ученых выяснилось,
что пятый постулат не противоречит
остальным аксиомам, но и не может быть
выведен из них. Точно так же после работ
К. Гёделя, П. С. Новикова, Дж. Коэна и
других выяснилось, что утверждение об
отсутствии множества промежуточной
мощности является аксиомой теории
множеств. Не существует мощности,
большей, чем мощность счётного множества,
и меньшей мощности континуум. Если
множество имеет мощность, большую
мощности счётного множества, то данное
множество имеет мощность континуум.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Введение в теорию множеств

Концепция бесконечности идеологически далека от обычной математической терминологии — ни одна другая тема не выходит за пределы математики так, что превращается из практического, аналитического инструмента в явление мифического порядка. Понятие бесконечности на короткой ноге с такими культурными темами, как религия и философия, и окутана загадочной аурой божественности.

Когда-то давным давно во всех академических дисциплинах было заложено фундаментальное убеждение — существует единственная бесконечность.

Но 1874 году довольно малоизвестный математик провёл серию революционных наблюдений, подвергавших сомнению это всеми принятое и глубоко укоренившееся убеждение. Георг Кантор в своей (теперь уже ставшей легендарной) публикации On a Property of the Collection of All Real Algebraic Numbers доказал, что множество вещественных чисел «более многочисленно», чем множество алгебраических чисел. Так он впервые показал, что существуют бесконечные множества разных размеров (не волнуйтесь — для прояснения этого мы вскоре подробно изучим его статью).

«Множество — это большое количество, которое позволяет воспринимать себя как одно» — Георг Кантор

С 1874 по 1897 год Кантор неистово публиковал статью за статьёй, разворачивая свою теорию абстрактных множеств в расцветающую дисциплину. Однако она была встречена упорным сопротивлением и критикой; многие педанты считали, что его теории перешли в область философии и нарушили принцип религии.

Однако когда начали находиться практические применения математического анализа, отношение к теории изменилось, а идеи и результаты Кантора начали получать признание. К первому десятилению 20-го века его наблюдения, теории и публикации достигли своей кульминации — признания современной теории множеств новой, совершенно уникальной областью математики:

Теория множеств — это математическая теория о точно определённых наборах (множествах) отдельных объектов, называемых членами или элементами множества.

Сколько чисел есть между 0 и 1?

Первая публикация Кантора, состоящая из четырёх с половиной страниц, является великолепным примером краткости. Она разделена на два отдельных доказательства, совместно приводящих к выводу о существовании по крайней мере двух уникальных видов множеств.

В первой части теории исследуется множество вещественных алгебраических чисел и доказывается, что это бесконечное счётное множество. Здесь не стоит путать — «счётное» не обязательно значит, что счёт ведётся строго в целых числах; в контексте теории множеств «счётное» означает, что множество, пусть даже состоящее из бесконечного числа элементов, можно описать повторяющимся рядом, например упорядоченной многочленной функцией. Кантор назвал это свойство бесконечного набора чисел соответствия «один к одному» с рядом, наличием взаимно однозначного соответствия.

Если говорить вкратце, то набор, или множество всех вещественных алгебраических чисел можно вывести с помощью какого-то теоретического ряда многочленов с различными степенями и коэффициентами; следовательно, множество всех вещественных алгебраических чисел является бесконечным счётным множеством.

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

Затем Кантор указывает, что в любом замкнутом интервале [a,b] существует хотя бы одно транцендентное число, которое никогда нельзя будет подсчитать в бесконечном счётном множестве. Поскольку одно такое число существует, то предполагается, что в семействе вещественных чисел существует бесконечное количество транцендентных чисел.

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

Далее: запись и операции

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

Стоит также поделиться интересным наблюдением: большинство людей, использующих теорию множеств на практике, ценят скорее не эту конкретную теорему, а заданный ею обобщённый язык. Благодаря своей абстрактной природе теория множеств скрытно влияет на множество областей математики. В математическом анализе, который требует дифференциального и интегрального исчисления, необходимо понимание пределов и непрерывности функций, окончательно закреплённых в теории множеств. В алгебре логики логические операции «и», «или» и «не» соответствуют операциям пересечения, объединения и разности в теории множеств. И последнее, но не менее важное — теория множеств закладывает основы топологии — исследования геометрических свойств и пространственных отношений.

Вооружившись базовым пониманием истории множеств и совершив кратковременное погружение в глубины его влияния, мы можем приступать к знакомству с основами системы обозначений теории множеств.

Часть вторая. Краткий обзор операций, обозначений и диаграмм Венна.

Как сказано в предыдущей части, одно из фундаментальных преимуществ теории множеств произрастает не из какой-то конкретной теории, а из созданного ею языка. Именно поэтому основная часть этого раздела будет посвящена обозначениям, операциям и визуальному представлению теории множеств. Давайте начнём с объяснения базовых символов обозначения множества — соответствующих ему элементов. В таблице ниже показан пример одного множества A с тремя элементами:

A — это множество с элементами «1», «2» и «3»

«1» — элемент множества A

В первой строке показано множество A с тремя отдельными элементами (A = {1,2,3}); во второй строке показан правильный способ обозначения отдельного конкретного элемента 1, принадлежащего множеству A. Пока всё довольно просто, но теория множеств становится существенно интереснее, когда мы добавляем второе множество — начинается путешествие по стандартным операциям.

Для показанной выше таблицы давайте введём два дополнительных множества B и C, содержащие следующие элементы: B = {3,A,B,C,D,E}, C = {1,2}. Хоть мы и создали три множества (A,B и C), в показанных ниже примерах операции выполняются одновременно только с двумя множествами, поэтому внимательно следите за тем, какие множества указаны в самом левом столбце. В показанной ниже таблице представлено пять самых распространённых операндов множеств:

Операции: пересечение (intersection) — множество элементов, принадлежащих множеству A и множеству B;

объединение (union) — множество элементов, принадлежащих множеству A или множеству B;

подмножество (subset) — C является подмножеством A, множество C включено во множество A;

собственное (истинное) подмножество — C является подмножеством A, но C не равно A;

относительное дополнение (relative complement) — множество элементов, принадлежащих к A и не к B.

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

Ещё раз взгляните на последнюю строку, относительное дополнение — какое необычное сочетание слов, правда? Относительное к чему? Если относительное дополнение A — B определяется как A и не B, то как нам обозначить всё, что не является B?

Универсальное множество — пустое множество

Оказывается, если мы хотим получить значимый ответ, то для начала нужно предоставить генеральной совокупности нашей задачи множеств некий контекст. Он часто явным образом задаётся в начале задачи, когда допустимые элементы множества ограничиваются некоторым фиксированным классом объектов, в котором существует универсальное множество, являющееся общим множеством, содержащим все элементы для этой конкретной задачи. Например, если мы хотели бы работать со множествами только из букв английского алфавита, то наше универсальное множество U состояло бы из 26 букв алфавита.

Для любого подмножества A множества U дополнение множества A (обозначаемое A′ или U − A) определяется как множество всех элементов в генеральной совокупности U, которое не находится в A. Если вернуться к поставленному выше вопросу, то дополнением множества B является всё в пределах универсального множества, что не принадлежит B, в том числе и A.

Прежде чем мы двинемся дальше, надо упомянуть ещё одно принципиальное множество, которое достаточно важно для базового понимания: нулевое или пустое множество. Учтите, что существует единственное пустое множество, поэтому никогда не говорят «пустые множества». Хотя мы не будем рассматривать в этой статье эквивалентность, основная теория гласит, что два множества эквивалентны, если они имеют одинаковые элементы; следовательно, может быть только одно множество без элементов. Поэтому существует единственное пустое множество.

Диаграммы Венна и остальное

Диаграммы Венна, официально изобретённые в 1880 году Джоном Венном, являются именно тем, что вы и представляете, хотя их научное определение звучит примерно так:

Схематичное изображение всех возможных отношений нескольких множеств

Ниже показано изображение шести самых распространённых диаграмм Венна, и почти во всех показаны недавно изученные нами операнды:

Объединение (union), пересечение (intersection), относительное дополнение (relative complement), симметрическая разность (symmetric difference), собственное множество (proper subset), абсолютное дополнение (universal дополнение).

Начав с очень простых обозначений множества и его элементов, мы узнали затем о базовых операциях, позволивших нарисовать эту визуальную подсказку. Мы рассмотрели все операции, за исключением симметрической разности (внизу слева). Чтобы не оставлять пробелов в знаниях, скажем, что симметрическая разность, также называемая дизъюнктивным объединением — это просто множество элементов, которые находятся в любом из множеств, но не входят в их пересечение.

Закончим мы этот раздел введением понятия мощности (кардинального числа). Мощность множества, обозначаемая символом абсолютного значения — это просто количество уникальных элементов, содержащихся в определённом множестве. Для показанного выше примера мощность трёх множеств равна: |A| = 3, |B| =6, |C| = 2.

Прежде чем двигаться дальше, дам вам пищу для размышлений — какова связь между мощностью и количеством возможных подмножеств?

Часть 3. Мощность и показательные множества

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

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

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

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

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

Количество возможных подмножеств в C= 2^|C|

Давайте подробно рассмотрим показанный ниже пример. Однако для начала поразмыслим над формулой. Представим мощность как общее количество «позиций», которое представляет множество. При создании некоторого подмножества для каждой возможной позиции принимается булево решение (да/нет). Это означает, что каждый уникальный элемент, добавляемый к множеству (то есть увеличивающий мощность на единицу) увеличивает количество возможных подмножеств на множитель два. Если вы программист или учёный, то можете уяснить эту логику немного глубже, если поймёте, что все подмножества множества можно вычислить с помощью таблицы двоичных чисел.

Показательное множество (булеан)

Прежде чем мы вычислим все подмножества для примера множества C, я хотел бы ввести последнее понятие — булеан.

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

Для удобства форматирования я убрал запятые между множествами***

Чем может быть полезен булеан? На самом деле, вы скорее всего много раз интуитивно использовали булеаны, даже об этом не догадываясь. Каждый раз, когда вы выбираете подмножество элементов из более крупного множества, вы выбираете элемент булеана. Например ребёнок внимательно изучающий кондитерский магазин с купюрой в 5 долларов — какой элемент булеана множества всех доступных сладостей он выберет? Или если взять более технический пример: вам, как разработчику ПО может потребоваться запросить всех возможных пользователей базы данных, также обладающих свойством X и Y — ещё один случай, в котором одно подмножество выбирается из всех возможных подмножеств.

Эквивалентность и биективная функция

Теперь мы понимаем, что такое мощность множества, почему оно важно, и его связь с булеаном. Поэтому вернёмся ненадолго к тому, что упоминали в самом начале: что конкретно определяет эквивалентность в теории множеств?

Очевидно, что два множества с одинаковой мощностью имеют некое общее свойство, но на этом сходства заканчиваются — что если в одном из множеств есть многократно повторяющийся элемент? Что если два множества имеют одинаковую мощность и количество элементов? Нельзя отрицать, что они в какой-то степени «эквивалентны», но даже в этом случае всё равно есть возможность различий, потому что каждое множество может иметь разные элементы, повторяющиеся одинаковое количество раз. Смысл здесь в том, что концепция эквивалентности в теории множеств немного чужда другим областям математики. Установление эквивалентности в этом мире требует знакомства с этой концепцией и нового языка. В последней части этой статьи мы введём понятие эквивалентности, а также таких базисных свойств, как инъективные, биективные и сюръективные функции.

Часть 4. Функции.

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

Функция в мире теории множеств — это просто соответствие некоторых (или всех) элементов из Множества A некоторым (или всем) элементам Множества B. В показанном выше примере набор всех возможных элементов A называется областью определения; элементы A, используемые в качестве входных значений, в частности называются аргументами. Справа набор всех возможных выходных значений (называющихся в других областях математики «областью значений»), называется кообластью; набор настоящих выходных элементов B, соответствующих A, называется образом.

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

Инъекции, сюръекции и биекции

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

• Функция является инъективной (или «один к одному»), если каждый элемент в кообласти отображается не более чем на один элемент в области определения.
• Функция является сюръективной, если каждый элемент в кообласти отображается не менее чем на один элемент в области определения. (то есть образ и кообласть функции эквивалентны.)
• Функция является биективной, если каждый элемент кообласти отображается ровно на один элемент области определения.

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

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

Биекция (инъекция + сюръекция), инъекция (инъекция + не-сюръекция), сюръекция (не-инъекция + сюръеция), без классификации (не-инъекция + не-сюръекция)

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

Фундаментальные основы теории множеств — ключ к пониманию более высокоуровневых областей математики. Чтобы продолжить наше движение вверх, к этим различным областям, далее нужно будет, пользуясь своими знаниями о теории множеств, уяснить одну из самых революционных теорий в истории математики: систему аксиом Цермело-Френкеля.

Некоторые сведения о мощности множества приведены в [I].
Здесь мы рассмотрим это понятие более подробно.

Множество А равномощно множеству И, если существует
биекцил f:A→B.

Из того, что существует биекция f:A→B, следует, что
соответствие f^-1 есть биекция В на А (см. 1,4). Поэтому если
А равномощно В, то и В равномощно A, и мы можем говорить,
что множества АиВ равномощны.

Факт равномощности множеств А и В будем записывать
так: А~В.

Из определения равномощности и свойств биекции также
следует, что для любого множества А имеет место А ~ А
(тождественное отображение есть биекция множества А на
себя); а для любых множеств А, В, С из А~В и В~С следует
А~С (композиция биекций есть биекция).

Таким образом, отношение равномощности множеств есть
отношение эквивалентности*, заданное на „множестве всех
множеств” (на самом деле на множестве всех подмножеств
некоторого универсального множества).

*Зачастую в литературе по теории множеств равномощные множества
и называют „эквивалентными множествами”. Однако следует различать
общее понятие отношения эквивалентности и его частный случаи —
эквивалентность, или равномощность, множеств.

Если мы обозначим через |А| класс эквивалентности
множества А по отношению ~, то утверждение о равномощности
множеств Аи В можно записать так: |А| = |В|.

Этот класс эквивалентности |А| называют мощностью
множества А.

Конечные множества А = {а₁,.., а_n} и В = {b₁ ,…, b_n} равномощны тогда и только тогда, когда множества А и В состоят
из одного и того же числа элементов, т.е. n = m. Отсюда, в
частности, следует, что конечное множество не является
номощным никакому своему собственному подмножеству. Это
свойство конечных множеств можно сформулировать так.

Теорема 1.8. Если А — конечное множество и f:A→B
→ А — инъекция, то она является сюръекцией и, следовательно,
биекцией. #

В силу приведенных выше соображений мощностью
конечного множества А = {а₁,.., а_n} можно считать натуральное
число n, так как, задавая такое число, мы задаем и класс всех
(попарно равномощных) множеств вида {а₁,.., а_n}. Обратно,
каждый такой класс однозначно определяет натуральное число
п как число элементов в каждом множестве данного класса.
Естественно считается, что мощность пустого множества
равна нулю.

Перейдем теперь к исследованию мощности бесконечных
множеств. Таковы хорошо известные нам числовые множества
ℕ, ℤ, ℚ, ℝ и ℂ.

Любое множество, равномощное множеству всех
натуральных чисел, называют счетным. Мощность счетного множества
обозначают ℵ₀ (читается „алеф нуль”).

Любую биекцию v: ℕ → М называют нумерацией
счетного множества М; если элемент М есть v(n) для некоторого
n ∈ ℕ, то этот элемент М обозначаем через a_n, называя
туральное число n номером элемента a_n относительно данной
нумерации v.

Таким образом, элементы счетного множества можно
перенумеровать, записав их в виде последовательности а₁,.., а_n, … или {a_n}_n∈ℕ Другими словами, счетное множество есть
область значений некоторой функции натурального аргумента.

Пример 1.21. а. Множество всех нечетных натуральных
чисел счетно. Нумерацию v можно задать так: v(n) = 2n — 1,

б. Множество всех натуральных чисел, делящихся на
заданное число k ≥ 2, счетно. Нумерацию v можно задать так:
v(n) = kn, n∈ℕ. В частности, при k = 2 получаем, что
множество всех четных чисел счетно. Этот и предыдущий
примеры показывают, что бесконечное (счетное) множество может
иметь собственное равномощное ему подмножество.

в. Множество ℤ всех целых чисел счетно. Нумерацию
можно установить так:

Рассмотрим свойства счетных множеств.

Теорема 1.9. Любое бесконечное множество содержит
счетное подмножество.

◀ Пусть М₀ — бесконечное множество. Значит, оно не пусто
и существует элемент а₁ ∈ М₀. Положим М₁ = М₀ {a₁}.
Множество М₁ не пусто, так как в противном случае имело бы
место равенство М₀ = {a_i}, что противоречит предположению
о бесконечности М₀. Выберем элемент а₂ ∈ М₁ и положим
М₂ = М₁ {а₂} = М₀ {a₁, а₂}. Множество М₂ также не пусто,
поскольку иначе мы бы имели М₀ = {a₁, а₂} и множество
было бы конечным.

Методом математической индукции можно показать, что
для любого n ≥ 1 множество М_n = M₀ {a₁,…, a_n}, где а₁ ∈ М₀, …, a_n ∈ М_n-1, не пусто. Тогда существует элемент
a_n+1 ∈ М_n и a_n+1 ∉ M_n+1 = М_n {а_n+1}. Таким образом, все
элементы a_n, n ∈ ℕ, попарно различны и множество {а_n:n ∈ ℕ}
счетно, а его нумерация может быть задана так: v(n) = а_n.

Теорема 1.10. В любом бесконечном множестве можно
выделить два не пересекающихся между собой счетных
подмножества.

◀ Разобьем множество натуральных чисел на два
подмножества: ℕ₁ = {n: n = 2k — 1, k ∈ ℕ} (множество нечетных чисел),
и ℕ₂ = {n: n = 2k, k ∈ ℕ} (множество четных чисел). Оба эти
множества счетны (см. пример 1.21).

Согласно теореме 1.9, бесконечное множество содержит
некоторое счетное подмножество А. Пусть установлена
некоторая его нумерация. Разобьем это подмножество на два
подмножества: всех элементов с четными и всех элементов с
нечетными номерами. По построению эти подмножества не
пересекаются и являются счетными, поскольку счетны множества
четных и нечетных чисел. >

Теорема 1.11. Любое подмножество счетного множества
конечно или счетно.

◀ Пустое подмножество конечно по определению. Пусть М —
счетное множество, а В — его некоторое непустое
подмножество. Поскольку множество М счетно, можно считать, что
задана некоторая его нумерация. Следовательно, каждый
элемент подмножества В имеет свой номер. Запишем номера
элементов множества В в порядке возрастания: i₁, …, i_n, …

Если среди них есть наибольший номер i_p, то подмножество
В конечно. В противном случае получим счетное
подмножество {a_i1, a_i2,…, a_in,…}, нумерация которого установлена так:
v(n) = a_in.

Если множество конечно или счетно, его называют не
более чем счетным. Семейство (А_i)_i∈I множеств называют
не более чем счетным, если множество (индексов) I не более
чем счетно.

Теорема 1.12. Объединение любого не более чем счетного
семейства счетных множеств счетно.

<4 Пусть (А_i)_i∈I — конечное или счетное семейство счетных
множеств. Рассмотрим сначала случай, когда множества А_i
попарно не пересекаются.

В этом случае нумерация объединения конечного семейства
счетных множеств может быть проведена по схеме,
изображенной на рис. 1.14, а нумерация объединения счетного семейства
счетных множеств — по схеме, приведенной на рис. 1.15.

Пусть теперь (А_n)_n∈ℕ — произвольное счетное семейство
счетных множеств, т.е. множества А_i могут пересекаться. В
этом случае, применяя указанные на рис. 1.14 и 1.15 схемы
нумерации к конечному или счетному объединению счетных
множеств, следует пропускать каждый раз элементы, которые
уже получили номера. >

Полезно отметить также и следующий факт.

Теорема 1.13. Объединение конечного и счетного
множеств счетно. #

Теорема 1.14. Пусть М — бесконечное множество, а N —
его не более чем счетное подмножество. Если множество MN
бесконечно, то оно равномощно множеству М.

◀ По теореме 1.10 в множестве MN, поскольку оно
бесконечно, можно выбрать счетное подмножество N’. Ясно, что
N∩N’ = ∅. Множество N∪N’ является счетным как
объединение двух счетных множеств или объединение счетного и
конечного множеств. Поэтому существует биекция f: N∪N’ → N’.
Поскольку (M(N∪N’))∪(N∪N’)=M, M (N∪N’)∪N’ =
= MN, то требуемую биекцию М на МN строим так: на
подмножестве М (N∪N’), общем для М N и М, эта биекция
совпадает с тождественным отображением; на подмножестве
N∪N’ эта биекция есть биекция f. ▶

Следствие 1.1. Если М — бесконечное множество, а N —
не более чем счетное множество, то М ~ М ∪ N.

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

Рассмотрим множество всех последовательностей нулей и
единиц, т.е. последовательностей вида {α₁,α₂, …,α_n,…}, где
α_i ∈ {0,1} для каждого i ≥ 1.

Обозначим множество таких „двоичных”
последовательностей через {0,1}^ω.

Теорема 1.15 (теорема Кантора). Множество {0,1}^ω
не есть счетное множество.

◀ Пусть множество {0,1}^ω счетное. Тогда существует биекция
φ: ℕ → {0,1}^ω. Выпишем все последовательности φ(n):

φ(1) = {α₁₁,α₁₂, …,α_1n,…},

φ(1) = {α₁₁,α₁₂, …,α_1n,…},

………………………………………………………

φ(n) = {α_n1,α_n2, …,α_nn,…},

………………………………………………………

Построим последовательность β = {β₁,…, β_n,…}: положим
β_i = 1, если α_ii = 0, и β_i = 0, если α_ii = 1. Ясно, что эта
последовательность не совпадает ни с одной из последовательностей
φ(n), а это противоречит допущению, что любая
последовательность из {0,1}^ω есть φ(k) для некоторого k.

Итак, ℕ не равномощно {0,1}^ω.

В то же время {0,1}^ω содержит подмножество
последовательностей, в каждой из которых только один член отличен
от нуля. Это подмножество равномощно множеству всех
одноэлементных подмножеств ℕ и, следовательно, самому ℕ.
Следовательно, множество {0,1}^ω бесконечно, но не равномощно
счетному множеству и потому не является счетным. ▶

Теорема 1.16. Множество 2^ℕ всех подмножеств множества
натуральных чисел и множество {0,1}^ω равномощны.

◀ Определим отображение φ множества 2^ℕ на множество
{0,1}^ω следующим образом: если X ⊆ ℕ, то φ(Х)_i = 1 при i ∈ X
и φ(Х)_i = 0 при i ∉ X.

Тем самым подмножеству X ставится в соответствие
последовательность φ(Х), i-й член которой равен единице тогда
и только тогда, когда число i есть элемент множества X.
Докажем, что φ — биекция 2^ℕ на {0,1}^ω.

Покажем, что отображение φ — инъекция. Пусть X и Y —
различные подмножества ℕ. Тогда найдется число i ∈ X Y или
число j ∈ YX. В первом случае в последовательности φ(Х) i-й
член будет равен единице, а в последовательности φ(Y) — нулю.
Таким образом, φ(Х) ≠ φ(Y). Во втором случае φ(Y)_j = 1,
φ(Х)_j = 0 и опять φ(Х) ≠ φ(Y). Следовательно, отображение
φ — инъекция.

Покажем, что φ — сюръекция. Возьмем произвольную
последовательность α ∈ {0,1}^ω. Образуем множество Х_α =
= {i: α_i = 1}. Ясно, что φ(Х_α) = α. Таким образом, для
любой последовательности α ∈ {0,1}^ω существует подмножество
Х_α ∈ 2^ℕ, такое, что φ(Х_α) = α. Следовательно, φ —
сюръекция.

Таким образом, мы показали, что φ — биекция, а множества
2^ℕ и {0,1}^ω равномощны. >

Мощность множества 2^ℕ обозначают с и называют
мощностью континуума, а любое множество, эквивалентное
множеству 2^ℕ, называют множеством мощности
континуума или континуальным множеством.

Теорема 1.17. Множество действительных чисел отрезка
[0,1] равномощно множеству всех последовательностей нулей и
единиц {0,1}^ω.

◀ Каждое действительное число из отрезка [0,1] представим в
виде бесконечной дроби в двоичной системе счисления. Число 1
представим в виде периодической дроби, содержащей
бесконечное число единиц — 0,1(1). Конечные рациональные дроби
представим как бесконечные, дополнив справа бесконечным
числом нулей. Таким образом, каждое число из [0,1] представлено
в виде последовательности нулей и единиц. Кроме этого,
выбросим счетное множество всех периодических дробей вида
O,α₀α₁…α_kO(1), поскольку каждая такая дробь представляет
то же самое число, что и дробь O,α₀α₁…α_k1(0), где α_i ∈ {0,1}
для всякого i = 1,k. Легко видеть, что полученное таким
образом множество двоичных дробей равномощно множеству
{0,1}^ω▶

Следствие 1.2. [0,1] ~ 2^ℕ.

◀ Выше была доказана равномощность множеств (0,1)^ω и 2^ℕ.
Тогда имеем [0,1] ~ {0,1}^ω ~ 2^ℕ. ▶

Теорема 1.18. Следующие множества равномощны:

1. множество действительных чисел отрезка [0,1];
2. множество действительных чисел интервала (0,1);
3. множество действительных чисел отрезка [а, b];
4. множество действительных чисел интервала (а, b);
5. множество действительных чисел (числовая ось) ℝ;
6. множество всех подмножеств множества натуральных
   чисел 2^ℕ.

◀ Покажем равномощность множеств [0,1] и (0,1). Из
множества действительных чисел отрезка [0,1] выделим
двухэлементное подмножество {0,1}. Разностью этих множеств будет
множество действительных чисел интервала (0,1), и, согласно
теореме 1.14, [0,1] ~ (0,1).

Отображение у = (b — a)х + а задает биекцию множества
[0,1] на множество [а, b]. Следовательно, эти множества
номощны. Заметим, что аналогично доказывается
равномощность (0,1) и (а, b).

Покажем, что (0,1) ~ ℝ. Биекцию можно установить,
например, с помощью функции у = 1/πarctgx + 1/2.

Поскольку равномощность [0,1] и 2^ℕ ранее доказана, имеем

[0,1] ~ (0,1) ~ [а, b] ~ (а, b) ~ ℝ ~ 2^ℕ. ▶

Замечание 1.7. Заметим, что если в условиях теоремы 1.14
множество М несчетно, а N — его счетное подмножество, то
множество MN бесконечно, ибо иначе получилось бы, что
множество М = (М N) U N счетно как объединение конечного
и счетного множеств.

Таким образом, можно утверждать, что для любого
несчетного множества М и его не более чем счетного подмножества
N имеет место равенство |М N| = |М|. #

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

Считают, что мощность множества А не превышает
мощность множества В (|А| ≤ |В|), если А равномощно некоторому
подмножеству множества В. Можно показать, что из
соотношений |A| ≤ |В| и |В| ≤ |А| следует, что |A| = |B|.

Мощность множества А считается строго меньшей
мощности множества В (|А| < |В|), если множества А и В
мощны и существует собственное подмножество С множества
В, равномощное множеству А, т.е. (А ≁ В) и (∃С ⊂ В)(А~С).

Можно доказать, что из |А| ≤ |В| и |В| ≤ |С| следует |А| ≤
|С|. Таким образом, на множестве всех мощностей (т.е.
на множестве всех классов эквивалентности по отношению ~)
установлено отношение порядка.

Из определения сразу следует, что мощность любого
конечного множества строго меньше мощности Но, а из
доказательства теоремы 1.15 вытекает, что ℵ₀ < с. Кроме того,
согласно теореме 1.9, мощность счетного множества ℵ₀
является наименьшей на множестве всех бесконечных мощностей (т.е.
мощностей бесконечных множеств). Можно сказать, что
всякое бесконечное множество не менее чем счетно.

Без доказательства приведем две важные теоремы.

Теорема 1.19 (теорема Кантора — Бернштейна).
Для любых двух множеств А и В имеет место в точности одно
из следующих трех условий: либо |А| < |B|, либо |В| < |А|, либо
|B| = |А| #

Таким образом, любые два множества сравнимы по
мощности. Другими словами, „шкала мощностей” линейно
упорядочена.

Теорема 1.20. Для любого множества А верно неравенство
|2^ℕ| > |А|. #

В силу теоремы 1.20 нет наибольшей мощности, так как для
любого множества А существует множество большей
мощности — его булеан. Заметим, что для счетного множества А
теорема 1.20 сводится к теореме Кантора 1.15.

Теорема 1.21 (теорема о квадрате). Для любого
бесконечного множества М его декартов квадрат М × М
мощен самому множеству М.

◀ Доказательство проведем для частных случаев счетного и
континуального множеств.

Сначала обратимся к счетному множеству. Для
доказательства утверждения достаточно показать, что ℕ × ℕ ~ ℕ, т.е.
задать на ℕ × ℕ некоторую нумерацию. Рассмотрим множество
A_i = {(i, j): j ∈ ℕ} упорядоченных пар. Это множество счетно
по построению. Легко видеть, что справедливо равенство

откуда, согласно теореме 1.12, вытекает счетность декартова
квадрата ℕ × ℕ множества ℕ как счетного объединения
счетных множеств.

Перейдем к континуальному множеству. Докажем, что
множество всех упорядоченных пар двоичных последовательностей
эквивалентно множеству всех таких последовательностей, т.е.
2^ℕ × 2^ℕ ~ 2^ℕ.

Паре последовательностей (α, β) поставим в соответствие
последовательность α₀, β₀, α₁, β₁, …, α_n, β_n, … Это
соответствие будет взаимно однозначным, т.е. установлена биекция
между 2^ℕ × 2^ℕ ~ 2^ℕ. ▶

Получается, что — как это ни удивительно — в квадрате
„столько же” точек, сколько и в каждой его стороне. Можно
обобщить это утверждение для произвольной конечной
декартовой степени множества М.

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

◀ Каждому рациональному числу, представленному
несократимой дробью a/b, однозначно соответствует упорядоченная пара
(а, b), и, напротив, любая упорядоченная пара (а, b) взаимно
простых целых чисел а и b однозначно определяет
несократимую дробь a/b и значит, рациональное число. Следовательно,
множество ℚ эквивалентно некоторому бесконечному
подмножеству множества ℤ × ℤ. Поскольку множество ℤ × ℤ счетно,
из теоремы 1.11 вытекает, что любое его бесконечное
подмножество счетно. Таким образом, множество ℚ счетно. >

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

Теорема 1.22. Если М и N — конечные множества и
|М| = m, a |N| = n, то:

1. мощность множества всех отображений М в N равна n^m;
2. мощность множества всех биекций из N на себя равна P_n=n!;
3. мощность множества всех инъекций из М в N (m ≤ n) равна A^mn =       n!  (n-m)!      ;
4. мощность множества всех подмножеств множества N
   равна 2ⁿ;
5. мощность множества всех k-элементных подмножеств
   множества N равна C^kn =       n!  k!(n-k)!      ;
6. мощность прямого произведения М × N равна mn. #

Напомним [I], что в комбинаторике число Р_n называют
числом перестановок n элементов, число A^mn — числом
размещений без повторений из n элементов по m, число C^kn
(обозначаемое также (^nk )) — числом сочетаний из n элементов по k. Эти
числа называются также биномиальными коэффициентами, поскольку (формула бинома Ньютона).

Мо́щность мно́жества, кардина́льное число́ мно́жества (лат. cardinalis ← cardo «главное обстоятельство; стержень; сердцевина») — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.

В основе этого понятия лежат естественные представления о сравнении множеств:

1. Любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция), содержат одинаковое количество элементов (имеют одинаковую мощность).
2. Обратно: множества, равные по мощности, должны допускать такое взаимно-однозначное соответствие.
3. Часть множества не превосходит полного множества по мощности (то есть по количеству элементов).

До построения теории мощности множеств множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.

Мощность множеств позволяет сравнивать бесконечные множества.
Например, счётные множества являются самыми «маленькими» бесконечными множествами.

Мощность множества обозначается через .
Иногда встречаются обозначения , и .

Определение

При соблюдении аксиомы выбора мощность множества формально определяется как наименьшее порядковое число , при котором между и можно установить биективное соответствие. Данное определение также называется распределением кардинальных чисел по фон Нейману. Если мы не принимаем аксиому выбора, требуется иной подход. Самое первое определение мощности множества (оно неявно присутствует в работах Кантора и явным образом сформулировано у Фреге, а также в Principia Mathematica) представляет собой класс всех множеств, равномощных . В аксиоматических системах, основанных на теории ZFC, такое определение неприменимо, поскольку при непустом такая совокупность слишком велика, чтобы подходить под определение множества. Точнее, если , то существует инъективное отображение универсального множества в , при котором каждое множество переходит в , откуда, в силу аксиомы ограничения размера следует, что  — собственный класс. Данное определение можно использовать в теории типов и «новых основаниях», а также в связанных с ними аксиоматических системах. В случае ZFC определение можно использовать, если ограничить коллекцию равномощными множествами с наименьшим рангом (этот приём, предложенный Даной Скоттом, работает благодаря тому, что совокупность объектов, обладающих заданным рангом, является множеством).

Формальный порядок среди кардинальных чисел вводится следующим образом: означает, что множество можно инъективно отобразить на . Согласно теореме Кантора — Бернштейна, из пары неравенств и следует, что . Аксиома выбора эквивалентна утверждению о том, что для любых множеств и выполняется, по крайней мере, одно из неравенств или .

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

Связанные определения

• Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств и возможно только одно из трёх:
  1. , или и равномощны;
  2. , или мощнее , то есть содержит подмножество, равномощное , но и не равномощны;
  3. , или мощнее  — в этом случае содержит подмножество, равномощное , но и не равномощны.

Примеры

• Множество называется счётным, если оно равномощно множеству всех натуральных чисел . Счётными множествами являются:

• Бесконечные множества, неравномощные множеству , называются несчётными. По теореме Кантора несчётным является множество бесконечных последовательностей, составленных из цифр 0 и 1. Мощность этого множества называется континуум.

• Мощность множества вещественных чисел равна континууму.

Свойства

Арифметика кардинальных чисел

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

Следующее по порядку кардинальное число

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

Сложение кардинальных чисел

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

Нейтральность нуля относительно сложения:

Ассоциативность:

Коммутативность:

Монотонность (неубывание) сложения по обоим аргументам:

Сумму двух бесконечных кардинальных чисел можно легко вычислить при соблюдении аксиомы выбора. Если одно из чисел или бесконечно, то

Вычитание

При соблюдении аксиомы выбора для любого бесконечного кардинального числа и произвольного кардинального числа существование , при котором , эквивалентно неравенству . Такое единственно (и совпадает с ) тогда и только тогда, когда .

Умножение кардинальных чисел

Произведение двух кардинальных чисел выражается через декартово произведение множеств:

Свойства нуля:

Нейтральность единицы относительно умножения:

Ассоциативность:

Коммутативность:

Монотонность (неубывание) умножения по обоим аргументам:

Дистрибутивность умножения относительно сложения:

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

Деление

При соблюдении аксиомы выбора для любой пары кардинальных чисел и , где бесконечно, а не равно нулю, существование , при котором , эквивалентно неравенству . Такое единственно (и совпадает с ) тогда и только тогда, когда .

Возведение кардинальных чисел в степень

Возведение в степень определяется следующим образом:

,

где обозначает множество всех функций из в .

(в частности, ), см. Пустая функция

Монотонность:

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

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

Если и  — конечные числа, большие 1, а  — бесконечное кардинальное число, то
Если кардинальное число бесконечно, а конечно и отлично от нуля, то .

Если и , причём хотя бы одно из них бесконечно, то

.

Используя теорему Кёнига, можно доказать, что для любого бесконечного кардинального числа выполняются неравенства:

,

где обозначает конфинальность .

Извлечение корней

При условии соблюдения аксиомы выбора для любого бесконечного кардинала и конечного кардинала существует кардинальное число , при котором , причём .

Логарифмы

При соблюдении аксиомы выбора кардинальное число , удовлетворяющее условию , при заданном бесконечном и конечном , существует не всегда. Если же такое существует, то оно бесконечно и меньше , причём любое конечное кардинальное число также будет удовлетворять равенству .

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

Континуум-гипотеза

Согласно утверждению континуум-гипотезы, между и не существует других кардинальных чисел. Кардинальное число также обозначается и представляет собой мощность континуума (то есть множества вещественных чисел). В данном случае . Обобщённая континуум-гипотеза отрицает существование кардинальных чисел, заключённых строго между и , для любого бесконечного множества . Континуум-гипотеза является независимой от стандартной аксиоматизации теории множеств, то есть системы аксиом Цермело-Френкеля в сочетании с аксиомой выбора (см. Теория множеств Цермело-Френкеля).

См. также

• Порядковое число

Примечания

Литература

• А. А. Болибрух, Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза, Библиотека «Математическое просвещение», Выпуск 2
• Р. Курант, Г. Роббинс, Что такое математика? Глава II, § 4.
• Факультативный курс по математике. 7-9 / Сост. И. Л. Никольская. — М.: Просвещение, 1991. — С. 109-110. — 383 с. — ISBN 5-09-001287-3.
• Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.