Мощность множества
Мо́щность мно́жества (кардина́льное число́, трансфини́тное число́, кардина́л мно́жества А; лат. cardinalis ← cardo «главное обстоятельство; основа; сердце») — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.
Что важно знать
| Мощность множества | |
|---|---|
| Область использования | Математика |
Предпосылки
В основе этого понятия лежат естественные представления о сравнении множеств:
- Любые два множества, между элементами которых может быть установлено взаимно-однозначное соответствие (биекция), содержат одинаковое количество элементов (имеют одинаковую мощность, равномощны).
- Обратно: равномощные множества должны допускать такое взаимно-однозначное соответствие.
- Часть множества не превосходит полного множества по мощности (то есть по количеству элементов).
До того, когда была построена теория мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.
Мощность множеств позволяет сравнивать бесконечные множества. Например, счётные множества являются самыми «маленькими» бесконечными множествами.
Определение
Кардинальное число (мощность по Кантору) — характеристика множества, которая не меняется при переходе от этого множества к любому другому равномощному ему множеству. При этом множества и равномощны, если существует взаимно однозначное соответствие : с областью определения и множеством значений .
Г. Кантор (1878) определял кардинальное число множества как такую его характеристику, которая получается после абстрагирования от природы элементов множества и от их порядка. Чтобы подчеркнуть этот двойной акт абстрагирования, Кантор для обозначения кардинального числа множества использовал символ . Из других обозначений кардинального числа множества наиболее употребительны символы и . Если — конечное множество, содержащее элементов, то . Если — множество всех натуральных чисел (оно является счётным множеством), то обозначается (алеф-нуль или алеф-0 — название образовано от первой буквы еврейского алфавита ). Если — множество всех действительных чисел (оно имеет мощность континуума), то обозначается . Предположение о том, что , называется континуум-гипотезой[1].
Пусть дано множество , элементами которого являются попарно не пересекающиеся непустые множества . Тогда существует множество , каждый элемент которого есть элемент некоторого множества и которое пересекается с каждым множеством лишь по одному элементу .
Другими словами, множество , существование которого постулируется этой аксиомой, состоит из элементов, «выбранных по одному» из каждого множества [2].
Если принять аксиому выбора, мощность множества формально будет определяться как наименьшее порядковое число , при котором между и можно установить биективное соответствие. Данное определение также называется распределением кардинальных чисел по фон Нейману.
Если не принимать аксиому выбора, то требуется иной подход. Самое первое определение мощности множества (оно неявно присутствует в работах Кантора и явным образом сформулировано у Фреге, а также в Principia Mathematica) представляет собой класс всех множеств, равномощных . В аксиоматических системах, основанных на теории ZFC, такое определение неприменимо, поскольку при непустом такая совокупность слишком велика, чтобы подходить под определение множества. Точнее, если , то существует инъективное отображение универсального множества в , при котором каждое множество переходит в , откуда, в силу аксиомы ограничения размера следует, что — собственный класс. Данное определение можно использовать в теории типов и «новых основаниях», а также в связанных с ними аксиоматических системах. В случае ZFC определение можно использовать, если ограничить коллекцию равномощными множествами с наименьшим рангом (этот приём, предложенный Даной Скоттом, работает благодаря тому, что совокупность объектов, обладающих заданным рангом, является множеством).
Формальный порядок среди кардинальных чисел вводится следующим образом: означает, что множество можно инъективно отобразить на . Согласно теореме Кантора — Бернштейна, из пары неравенств и следует, что . Аксиома выбора эквивалентна утверждению о том, что для любых множеств и выполняется по крайней мере одно из неравенств или .
Множество называется бесконечным по Дедекинду, если в нём существует такое собственное подмножество , что . В противном случае множество называется конечным по Дедекинду. Конечные кардинальные числа совпадают с обычными натуральными числами или нулём, — иначе говоря, множество конечно тогда и только тогда, когда при некотором натуральном или при (если множество пустое). Все остальные множества бесконечны. При соблюдении аксиомы выбора можно доказать, что определения по Дедекинду совпадают со стандартными. Кроме того, можно доказать, что мощность множества натуральных чисел представляет собой наименьшее бесконечно большое кардинальное число, то есть в любом бесконечном множестве есть подмножество мощности . Следующее по порядку кардинальное число обозначается и так далее, число алефов бесконечно. Любому порядковому числу соответствует кардинальное число , причём таким образом можно описать любое бесконечно большое кардинальное число.
Связанные теоремы
Эту теорему называют также теоремой Шрёдера — Бернштейна. Она является краеугольным камнем теории множеств[3].
Если множество равномощно некоторому подмножеству множества , а равномощно некоторому подмножеству множества , то множества и равномощны.
Г. Кантор формулирует эту теорему без доказательства в 1883 году, обещая: «К этому я ещё вернусь в одной более поздней работе и тогда выявлю своеобразный интерес этой общей теоремы»[4]. Однако этого обещания он не выполнил, и первые доказательства были даны Шрёдером (1896) и Бернштейном (1897). Как видно из работ и писем Кантора, он предполагал доказывать эту теорему одновременно с возможностью сравнить любые два множества[5].
Множество , состоящее из всех подмножеств множества , не равномощно ни самому , ни его подмножеству.
Идея доказательства этой теоремы, принадлежащая Г. Кантору (1878), получила название «канторова диагонального метода» и играет существенную роль в теории множеств. Из этой теоремы следует, что никакие два из множеств , , ,… не равномощны. Таким способом получается бесконечно много кардинальных чисел[6].
Кардинальное число можно отождествить с наименьшим порядковым числом мощности . В частности, соответствует порядковому числу , — порядковому числу , и т. д. Таким образом, шкала кардинальных чисел является подшкалой шкалы порядковых чисел. При этом ряд свойств порядковых чисел переносится на кардинальные числа. Эти же свойства можно определить «внутренним» способом[7]:
Если для каждого и , то .
Если в вышеприведённом неравенстве взять и , то .
Связанные понятия
Счётное множество — это такое множество , все элементы которого могут быть занумерованы в бесконечную последовательность: так, чтобы при этом каждый элемент получил лишь один номер и каждое натуральное число было бы в качестве номера дано одному и лишь одному элементу нашего множества. Бесконечное множество, не являющееся счётным, называется несчётным множеством[8].
Для каждого кардинального числа определяется кардинальное число — конфинальный характер , как наименьшее кардинальное число такое, что , если для всех и . Если , то называется регулярным. Кардинальное число, не являющееся регулярным, называется сингулярным.
- Кардинальное число называется предельным, если для любого кардинального числа существует кардинальное число такое, что . Регулярное и предельное кардинальное число называется слабо недостижимым.
- Кардинальное число называется доминантным, если для любого выполняется . Доминантное и регулярное кардинальное число называется сильно недостижимым.
- Классы недостижимых кардинальных чисел допускают дальнейшую классификацию, которая приводит к определению гипернедостижимых кардинальных чисел.
Множество всех действительных чисел имеет мощность континуума , оно несчётно[9]. Согласно континуум-гипотезе, между и не существует других кардинальных чисел. Обобщённая континуум-гипотеза отрицает существование кардинальных чисел, заключённых строго между и , для любого бесконечного множества . Континуум-гипотеза является независимой от стандартной аксиоматизации теории множеств, то есть системы аксиом Цермело — Френкеля в сочетании с аксиомой выбора (см. Теория множеств Цермело — Френкеля).
Примеры
- Множество называется конечным, если оно равномощно отрезку натурального ряда при некотором неотрицательном целом . Число выражает количество элементов конечного множества. При множество не содержит элементов (пустое множество). Если , то не существует инъективного отображения из в (принцип Дирихле), а значит, не существует и биекции между ними. Поэтому множества и имеют различную мощность.
- Счётными множествами являются:
- Множество при любом натуральном . Биективное соответствие, отображающее в : .
- Множество . Соответствие: .
- Множество целых чисел . Соответствие получается, если члены бесконечного ряда сопоставить его частичным суммам (члены ряда берутся без учёта знака).
- Множество пар натуральных чисел .
- Множество рациональных чисел инъективно отображается во множество (то есть любой несократимой дроби вида инъективно соответствует пара чисел ). Поэтому множество рациональных чисел не более чем счётно. Но так как оно содержит множество натуральных чисел, то оно и не менее чем счётно. Соответственно, по теореме Кантора — Бернштейна оно ровно счётно.
Свойства
- Множество называется бесконечным, если его мощность не меньше (мощности множества натуральных чисел). Таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются (где индекс пробегает все порядковые числа). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.
- Множества и называются эквивалентными, если существует взаимно однозначное отображение множества на множество .
- Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.
- Для бесконечных множеств мощность множества может совпадать с мощностью своего собственного (то есть не совпадающего с исходным множеством) подмножества, например .
- Более того, множество бесконечно тогда и только тогда, когда оно содержит равномощное собственное подмножество.
- Любое бесконечное множество равномощно множеству всех его конечных подмножеств[10].
- Мощность декартова произведения:
- .
- Формула включения-исключения для двух и трёх множеств:
- .
- Мощность симметрической разности двух и трёх множеств:
- .
Операции с кардинальными числами
Для кардинальных чисел определяются операции сложения, умножения, возведения в степень, взятие логарифма и извлечение корня[7].
Кардинальное число называется суммой кардинальных чисел и , если каждое множество мощности можно представить в виде объединения двух непересекающихся множеств и мощностей и соответственно.
Нейтральность нуля относительно сложения:
- .
- .
- .
Если аксиому выбора принять верной, то сумма двух бесконечных кардинальных чисел и определяется как .
При соблюдении аксиомы выбора для любого бесконечного кардинального числа и произвольного кардинального числа существование , при котором , эквивалентно неравенству . Такое единственно (и совпадает с ) тогда и только тогда, когда .
Кардинальное число называется произведением кардинальных чисел и , если является кардинальным числом декартова произведения , причём и .
Свойства нуля:
- ;
- .
Нейтральность единицы относительно умножения:
- .
- .
- .
Дистрибутивность умножения относительно сложения:
- ;
- .
По аналогии со сложением, произведение двух бесконечных кардинальных чисел можно легко вычислить при соблюдении аксиомы выбора. Если числа и отличны от нуля и хотя бы одно из них бесконечно, то .
Кардинальное число называется степенью с основанием и показателем , если каждое множество мощности равномощно множеству , где и .
- .
Все последующие утверждения, приведённые в этом разделе, опираются на аксиому выбора.
Если и — конечные числа, бо́льшие 1, а — бесконечное кардинальное число, то Если кардинальное число бесконечно, а конечно и отлично от нуля, то .
Если и , причём хотя бы одно из них бесконечно, то .
Кардинальное число не больше кардинального числа , , если каждое множество мощности равномощно некоторому подмножеству множества мощности . Если и , то (теорема Кантора — Берштейна), так что шкала кардинальных чисел линейно упорядочена.
Для любых множеств и существует одна из трёх возможностей:
- , или и равномощны.
- , или мощнее , то есть содержит подмножество, равномощное , но и не равномощны.
- , или мощнее — в этом случае содержит подмножество, равномощное , но и не равномощны.
- Ситуация, в которой и не равномощны и при этом ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
- Ситуация, в которой и , невозможна по теореме Кантора — Бернштейна.
Если для кардинального числа множество вполне упорядочено, то логарифм кардинального числа по основанию кардинального числа , есть наименьшее кардинальное число такое, что .
Если для каждого кардинального числа множество вполне упорядочено, то корень -й степени из кардинального числа , есть наименьшее кардинальное число такое, что .
Несмотря на то, что логарифмы бесконечно больших кардинальных чисел лишены некоторых свойств, характерных для логарифмов положительных вещественных чисел, они оказываются полезными в некоторых областях математики — в частности, при изучении кардинальных инвариантов топологических пространств.
Примечания
Литература
- Аксиоматические теории множеств / В. Г. Кановей // Большая российская энциклопедия : [в 35 т.] / гл. ред. Ю. С. Осипов. — М. : Большая российская энциклопедия, 2004—2017.
- Математическая энциклопедия (в 5 томах) / Гл. ред. И. М. Виноградов. — М.: Советская Энциклопедия, 1984.
- Александров П. С. Введение в теорию множеств и общую топологию: учебное пособие для вузов. — 3-е изд., стер.. — М.: Лань, 2025. — 368 с.
- Мельников О. В., Ремесленников В. Н., Романьков В. А. Общая алгебра / Под ред. Л. А. Скорнякова. — М.: Наука, 1990. — Т. 1. — 592 с.
- Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств. — 4-е изд., доп. — М.: МЦНМО, 2012. — 112 с.
- Н. Бурбаки. Основания математики. Логика. Теория множеств // Очерки по истории математики / И. Г. Башмакова (перевод с французского). — М.: Издательство иностранной литературы, 1963. — 292 с. — (Элементы математики).
- Г. Кантор. Труды по теории множеств. — М.: Наука, 1985. — 430 с. — (Классики науки).
- Ф. А. Медведев. Развитие теории множеств в XIX веке. — М.: Наука, 1965. — 232 с.


