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

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

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

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

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

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

Мощность множества $A$ обозначается через $|A|$. Иногда встречаются обозначения $\overline{\stackrel{―}{A}}$, $\mathrm{\#}A$ и $\mathrm{card}(A)$.

Определение

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

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

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

Множество $X$ называется бесконечным по Дедекинду, если в нём существует такое собственное подмножество $Y$, что $|X|=|Y|$. В противном случае множество называется конечным по Дедекинду. Конечные кардинальные числа совпадают с обычными натуральными числами или нулём, — иначе говоря, множество $X$ конечно тогда и только тогда, когда $|X|=|n|=n$ при некотором натуральном $n$ или при $n=0$ (если множество пустое). Все остальные множества бесконечны. При соблюдении аксиомы выбора можно доказать, что определения по Дедекинду совпадают со стандартными. Кроме того, можно доказать, что мощность множества натуральных чисел ${\mathrm{\aleph }}_0$ (алеф-нуль, или алеф-0, — название образовано от первой буквы еврейского алфавита $\mathrm{\aleph }$) представляет собой наименьшее бесконечно большое кардинальное число, то есть в любом бесконечном множестве есть подмножество мощности ${\mathrm{\aleph }}_0$. Следующее по порядку кардинальное число обозначается ${\mathrm{\aleph }}_1$ и так далее, число алефов бесконечно. Любому порядковому числу $\alpha$ соответствует кардинальное число ${\mathrm{\aleph }}_{\alpha }$, причём таким образом можно описать любое бесконечно большое кардинальное число.

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

• Мощность множества натуральных чисел $\mathbb{N}$ обозначается символом ${\mathrm{\aleph }}_0$ («алеф-нуль»). Множество называется бесконечным, если его мощность не меньше ${\mathrm{\aleph }}_0$ (не меньше мощности множества натуральных чисел), таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются ${\mathrm{\aleph }}_1,{\mathrm{\aleph }}_2,\dots {\mathrm{\aleph }}_{\omega },{\mathrm{\aleph }}_{\omega +1},\dots {\mathrm{\aleph }}_{{\omega }_1},\dots$ (где индекс пробегает все порядковые числа). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.

• Про множества, равномощные множеству всех вещественных чисел, говорят, что они имеют мощность континуума, и мощность таких множеств обозначается символом $\mathfrak{c}$. Предположение о том, что $\mathfrak{c}={\mathrm{\aleph }}_1$, называется континуум-гипотезой.

• Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств $A$ и $B$ возможно только одно из трёх:
  1. $|A|=|B|$, или $A$ и $B$ равномощны;
  2. $|A|>|B|$, или $A$ мощнее $B$, то есть $A$ содержит подмножество, равномощное $B$, но $A$ и $B$ не равномощны;
  3. $|A|<|B|$, или $B$ мощнее $A$ — в этом случае $B$ содержит подмножество, равномощное $A$, но $A$ и $B$ не равномощны.
  • Ситуация, в которой $A$ и $B$ не равномощны и при этом ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
  • Ситуация, в которой $|A|>|B|$ и $|A|<|B|$, невозможна по теореме Кантора — Бернштейна.
• Множества $A$ и $B$ называются эквивалентными, если существует взаимно однозначное отображение множества $A$ на множество $B$.

Примеры

• Множество называется конечным, если оно равномощно отрезку натурального ряда $I_n=\{1,2,...,n\}$ при некотором неотрицательном целом $n$. Число $n$ выражает количество элементов конечного множества. При $n=0$ множество не содержит элементов (пустое множество). Если $m>n$, то не существует инъективного отображения из $I_m$ в $I_n$ (принцип Дирихле), а значит, не существует и биекции между ними. Поэтому множества $I_m$ и $I_n$ имеют различную мощность.

• Множество называется счётным, если оно равномощно множеству всех натуральных чисел $\mathbb{N}$. Счётными множествами являются:
  • Множество $\mathbb{N}\setminus I_k$ при любом натуральном $k$. Биективное соответствие, отображающее $\mathbb{N}$ в $\mathbb{N}\setminus I_k$: $n\to n+k$.
  • Множество $\mathbb{N}\cup \{0\}$. Соответствие: $n\to n-1$.
  • Множество целых чисел $\mathbb{Z}$. Соответствие получается, если члены бесконечного ряда $0+1-2+3-4+5-6+\dots$ сопоставить его частичным суммам (члены ряда берутся без учёта знака).
  • Множество пар натуральных чисел $\mathbb{N}\times \mathbb{N}$.
  • Множество рациональных чисел $\mathbb{Q}$ инъективно отображается во множество $\mathbb{Z}\times \mathbb{N}$ (то есть любой несократимой дроби вида $p/q$ инъективно соответствует пара чисел $(p,q)\in \mathbb{Z}\times \mathbb{N}$). Поэтому множество рациональных чисел не более чем счётно. Но так как оно содержит множество натуральных чисел, то оно и не менее чем счётно. Соответственно, по теореме Кантора — Бернштейна оно ровно счётно.

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

• Мощность множества вещественных чисел $\mathbb{R}$ равна континууму.

Свойства

• Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.
• Для бесконечных множеств мощность множества может совпадать с мощностью своего собственного (то есть не совпадающего с исходным множеством) подмножества, например $|\mathbb{N}|=|\mathbb{Z}|$.
• Более того, множество бесконечно тогда и только тогда, когда оно содержит равномощное собственное подмножество.
• Любое бесконечное множество $A$ равномощно множеству всех его конечных подмножеств.
• Теорема Кантора: булеан любого множества A имеет большую мощность, чем A, то есть $|2^A|>|A|$.
  • В частности, для любого множества существует множество мощнее.
• С помощью канторова квадрата можно также доказать следующее: декартово произведение бесконечного множества A с самим собой равномощно самому множеству A.
• Мощность декартова произведения:

  $|A\times B|=|A|\cdot |B|$

• Формула включения-исключения для двух и трёх множеств:

  $|A\cup B|+|A\cap B|=|A|+|B|$

  $|A\cup B\cup C|+|A\cap B|+|A\cap C|+|B\cap C|=|A|+|B|+|C|+|A\cap B\cap C|$

• Мощность симметрической разности двух и трёх множеств:

  $|A△B|+2\cdot |A\cap B|=|A|+|B|$

  $|A△B△C|+2|A\cap B|+2|A\cap C|+2|B\cap C|=|A|+|B|+|C|+3|A\cap B\cap C|$

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

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

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

Если принять аксиому выбора, то для каждого кардинального числа $\kappa$ можно определить следующее за ним число ${\kappa }^{+}>\kappa$, причём между $\kappa$ и ${\kappa }^{+}$ нет других кардинальных чисел. Если $\kappa$ конечно, то кардинальное число, следующее по порядку, совпадает с $\kappa +1$. В случае бесконечных $\kappa$ следующее кардинальное число отличается от следующего порядкового числа.

Через ${\kappa }^{-}$ обозначают предыдущее кардинальное число для числа $\kappa$ если таковое существует; в противном случае, ${\kappa }^{-}=\kappa$.

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

Если множества $X$ и $Y$ не имеют общих элементов, то сумма мощностей определяется мощностью их объединения. При наличии общих элементов исходные множества можно заменить непересекающимися множествами той же мощности — например, заменить $X$ на $X\times \{0\}$, а $Y$ на $Y\times \{1\}$.

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

$\kappa +0=0+\kappa =\kappa$

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

$(\kappa +\mu )+\nu =\kappa +(\mu +\nu )$

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

$\kappa +\mu =\mu +\kappa$

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

$\kappa \le \mu \to \kappa +\nu \le \mu +\nu .$

$\kappa \le \mu \to \nu +\kappa \le \nu +\mu .$

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

$\kappa +\mu =max\{\kappa ,\mu \}.$

Вычитание

При соблюдении аксиомы выбора для любого бесконечного кардинального числа $\sigma$ и произвольного кардинального числа $\mu$ существование $\kappa$, при котором $\mu +\kappa =\sigma$, эквивалентно неравенству $\mu \le \sigma$. Такое $\kappa$ единственно (и совпадает с $\sigma$) тогда и только тогда, когда $\mu <\sigma$.

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

Произведение двух кардинальных чисел выражается через декартово произведение множеств: $|X|\cdot |Y|=|X\times Y|$

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

$\kappa \cdot 0=0\cdot \kappa =0$

$\kappa \cdot \mu =0\to \kappa =0\vee \mu =0$

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

$\kappa \cdot 1=1\cdot \kappa =\kappa$

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

$(\kappa \cdot \mu )\cdot \nu =\kappa \cdot (\mu \cdot \nu )$

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

$\kappa \cdot \mu =\mu \cdot \kappa$

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

$\kappa \le \mu \to \kappa \cdot \nu \le \mu \cdot \nu .$

$\kappa \le \mu \to \nu \cdot \kappa \le \nu \cdot \mu .$

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

$\kappa \cdot (\mu +\nu )=\kappa \cdot \mu +\kappa \cdot \nu$

$(\mu +\nu )\cdot \kappa =\mu \cdot \kappa +\nu \cdot \kappa$

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

$\kappa \cdot \mu =max\{\kappa ,\mu \}.$

Деление

При соблюдении аксиомы выбора для любой пары кардинальных чисел $\pi$ и $\mu$, где $\pi$ бесконечно, а $\mu$ не равно нулю, существование $\kappa$, при котором $\mu \cdot \kappa =\pi$, эквивалентно неравенству $\mu \le \pi$. Такое $\kappa$ единственно (и совпадает с $\pi$) тогда и только тогда, когда $\mu <\pi$.

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

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

$|X{|}^{|Y|}=|X^Y|$,

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

${\kappa }^0=1$ (в частности, $0^0=1$), см. «Пустая функция»

$1\le \mu \to 0^{\mu }=0$

$1^{\mu }=1$

${\kappa }^1=\kappa$

${\kappa }^{\mu +\nu }={\kappa }^{\mu }\cdot {\kappa }^{\nu }$

${\kappa }^{\mu \cdot \nu }=({\kappa }^{\mu }{)}^{\nu }$

$(\kappa \cdot \mu {)}^{\nu }={\kappa }^{\nu }\cdot {\mu }^{\nu }$

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

$(1\le \nu \wedge \kappa \le \mu )\to {\nu }^{\kappa }\le {\nu }^{\mu }$

$\kappa \le \mu \to {\kappa }^{\nu }\le {\mu }^{\nu }$

Заметим, что $2^{|X|}$ представляет собой мощность булеана $X$ и, следовательно, $2^{|X|}>|X|$ для любого множества $X$ (см. Диагональный метод Кантора). Отсюда следует, что среди кардинальных чисел нет наибольшего (поскольку для любого кардинального числа $\kappa$ можно указать большее число $2^{\kappa }$). В действительности класс всех кардинальных чисел является собственным (хотя в некоторых системах аксиом теории множества этого доказать нельзя — к таковым, например, относится система «Новых оснований»).

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

Если $\kappa$ и $\mu$ — конечные числа, большие 1, а $\nu$ — бесконечное кардинальное число, то ${\kappa }^{\nu }={\mu }^{\nu }.$ Если кардинальное число $\kappa$ бесконечно, а $\mu$ конечно и отлично от нуля, то ${\kappa }^{\mu }=\kappa$.

Если $\kappa \ge 2$ и $\mu \ge 1$, причём хотя бы одно из них бесконечно, то

$max\{\kappa ,2^{\mu }\}\le {\kappa }^{\mu }\le max\{2^{\kappa },2^{\mu }\}$.

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

$\kappa <{\kappa }^{\mathrm{cf}(\kappa )}$

$\kappa <\mathrm{cf}(2^{\kappa })$,

где $\mathrm{cf}(\kappa )$ обозначает конфинальность $\kappa$.

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

Если соблюдать аксиому выбора, то для любого бесконечного кардинала $\kappa$ и конечного кардинала $\mu >0$ существует кардинальное число $\nu$, при котором ${\nu }^{\mu }=\kappa$, причём $\nu =\kappa$.

Логарифмы

При соблюдении аксиомы выбора кардинальное число $\lambda$, удовлетворяющее условию ${\mu }^{\lambda }=\kappa$, при заданном бесконечном $\kappa$ и конечном $\mu >1$, существует не всегда. Если же такое $\lambda$ существует, то оно бесконечно и меньше $\kappa$, причём любое конечное кардинальное число $\nu >1$ также будет удовлетворять равенству ${\nu }^{\lambda }=\kappa$.

Логарифмом бесконечного кардинального числа $\kappa$ называется наименьшее кардинальное число $\mu$, удовлетворяющее условию $\kappa \le 2^{\mu }$. Несмотря на то, что логарифмы бесконечно больших кардинальных чисел лишены некоторых свойств, характерных для логарифмов положительных вещественных чисел, они оказываются полезными в некоторых областях математики — в частности, при изучении кардинальных инвариантов топологических пространств.

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

Согласно континуум-гипотезе, между ${\mathrm{\aleph }}_0$ и $2^{{\mathrm{\aleph }}_0}$ не существует других кардинальных чисел. Кардинальное число $2^{{\mathrm{\aleph }}_0}$ также обозначается $\mathfrak{c}$ и представляет собой мощность континуума (то есть множества вещественных чисел). В данном случае $2^{{\mathrm{\aleph }}_0}={\mathrm{\aleph }}_1$. Обобщённая континуум-гипотеза отрицает существование кардинальных чисел, заключённых строго между $|X|$ и $2^{|X|}$, для любого бесконечного множества $X$. Континуум-гипотеза является независимой от стандартной аксиоматизации теории множеств, то есть системы аксиом Цермело-Френкеля в сочетании с аксиомой выбора (см. Теория множеств Цермело-Френкеля).

См. также

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

Литература

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