Мощность

Чтобы узнать о других значениях, см. Кардинальность (значения) .

Набор $S$из всех платоновых тел содержит 5 элементов. Таким образом, мощность $S$ равно 5 или, в символах, $|S|=5$.

В математике мощность множества — это мера количества элементов множества. Например, набор $A=\{2,4,6\}$ содержит 3 элемента, и поэтому $A$имеет мощность 3. Начиная с конца 19 века это понятие было обобщено на бесконечные множества , что позволяет различать разные типы бесконечности и выполнять над ними арифметические действия . Существует два подхода к кардинальности: один сравнивает множества напрямую с помощью биекций и инъекций , а другой использует кардинальные числа . Мощность множества можно также назвать его размером , если не путать его с другими понятиями размера. возможно.

Мощность множества $A$ обычно обозначается $|A|$, с вертикальной полосой с каждой стороны; это то же обозначение, что и абсолютное значение , и его значение зависит от контекста. Мощность множества $A$ альтернативно может быть обозначено $n(A)$, $A$, $\operatorname {card} (A)$, или $\#A$.

История

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

В трудах греческих философов, начиная с VI века до нашей эры, есть намеки на мощность бесконечных множеств. Хотя они рассматривали понятие бесконечности как бесконечную серию действий, таких как многократное добавление 1 к числу, они не считали размер бесконечного набора чисел чем-то существенным. Древнегреческое понятие бесконечности также считало деление вещей на части, повторяющееся без ограничений. соизмеримость В «Началах» Евклида описывалась как способность сравнивать длину двух отрезков прямой, a и b , как отношение, при условии, что существовал третий отрезок, каким бы маленьким он ни был, который можно было уложить встык. целое число раз как в a , так и в b . Но с открытием иррациональных чисел стало ясно, что даже бесконечного множества всех рациональных чисел недостаточно для описания длины каждого возможного отрезка прямой. Тем не менее, не существовало понятия бесконечных множеств как чего-то, обладающего мощностью.

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

Сравнение наборов

Биективная функция от N до множества E четных чисел . Хотя E является собственным подмножеством N , оба множества имеют одинаковую мощность.

N не имеет той же мощности, что и его набор степеней P ( N ): для каждой функции f от N до P ( N ) набор T = { n ∈ N : n ∉ f ( n )} не согласуется с каждым набором в диапазон f f , следовательно, не может быть сюръективным. На рисунке показан пример f и соответствующий T ; красный : п ∈ ж ( п ) \ Т , синий : п ∈ Т \ ж ( п ).

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

Определение 1: | А | = | Б |

Два множества A и B имеют одинаковую мощность, если существует биекция (то есть взаимно однозначное соответствие) от A к B , то есть функция от A до B , которая является одновременно инъективной и сюръективной . Такие множества называются равномощными , равносильными или равночисленными . обозначить A ≈ B или A ~ B. Эту связь также можно

Например, набор E = {0, 2, 4, 6, ...} неотрицательных четных чисел имеет ту же мощность, что и набор N = {0, 1, 2, 3, ...} натуральных чисел. числа , поскольку функция f ( n ) = 2 n является биекцией из N в E (см. рисунок).

Для конечных множеств A и B , если существует некоторая биекция из A в B , то каждая инъективная или сюръективная функция из A в B является биекцией. Это уже не так для A и B. бесконечных Например, функция g от N до E , определяемая формулой g ( n ) = 4 n, является инъективной, но не сюръективной, а функция h от N до E , определяемая формулой h ( n ) = n - ( n mod 2), является сюръективной. , но не инъективный. Ни g, ни h не могут бросить вызов | Е | = | N |, что было установлено существованием f .

Определение 2: | А | ≤ | Б |

Мощность A меньше или равна мощности B существует инъективная функция из A в B. , если

Определение 3: | А | < | Б |

Мощность A строго меньше мощности B , если существует инъективная функция, но нет биективной функции A до B. от

Например, множество N всех натуральных чисел имеет мощность строго меньшую, чем его набор степеней P ( N ), потому что g ( n ) = { n } является инъективной функцией от N к P ( N ), и можно показать, что никакая функция от N до P ( N ) не может быть биективной (см. рисунок). По аналогичному рассуждению N имеет мощность строго меньшую, чем мощность множества R всех действительных чисел . Доказательства см. в диагональном аргументе Кантора или в первом доказательстве несчетности Кантора .

Если | А | ≤ | Б | и | Б | ≤ | А |, тогда | А | = | Б | (факт, известный как теорема Шрёдера–Бернштейна ). Аксиома выбора эквивалентна утверждению, что | А | ≤ | Б | или | Б | ≤ | А | для А , Б. каждого

Кардинальные числа

Основная статья: Кардинальное число

В приведенном выше разделе «мощность» набора была определена функционально. Другими словами, он не был определен как конкретный объект. Однако такой объект можно определить следующим образом.

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

1. Мощность множества A определяется как его класс эквивалентности при равночисленности.
2. набор репрезентативный Для каждого класса эквивалентности определяется . Наиболее распространенным выбором является начальный порядковый номер в этом классе . Обычно это принимается за определение кардинального числа в аксиоматической теории множеств .

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

$\aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots .$

Для каждого порядкового номера $\alpha$, $\aleph _{\alpha +1}$ наименьшее кардинальное число больше, чем $\aleph _{\alpha }$.

Мощность натуральных чисел обозначается алеф-нуль ( $\aleph _{0}$), а мощность действительных чисел обозначается " ${\mathfrak {c}}$» (строчная буква фрактур «c»), а также называется мощностью континуума . Кантор показал, используя диагональный аргумент , что ${\mathfrak {c}}>\aleph _{0}$. Мы можем показать это ${\mathfrak {c}}=2^{\aleph _{0}}$, это также мощность множества всех подмножеств натуральных чисел.

Гипотеза континуума утверждает, что $\aleph _{1}=2^{\aleph _{0}}$, то есть $2^{\aleph _{0}}$ наименьшее кардинальное число, большее, чем $\aleph _{0}$, т. е. не существует множества, мощность которого находилась бы строго между мощностью целых и действительных чисел. Гипотеза континуума не зависит от ZFC , стандартной аксиоматизации теории множеств; то есть невозможно доказать гипотезу континуума или ее отрицание с помощью ZFC - при условии, что ZFC непротиворечив. Подробнее см. § Мощность континуума ниже.

Конечные, счетные и несчетные множества

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

• Любой набор X с мощностью меньше, чем у натуральных чисел , или | Х | < | N | называется конечным множеством .
• Любой набор X , имеющий ту же мощность, что и набор натуральных чисел, или | Х | = | Н | "=" $\aleph _{0}$, называется счетным множеством.
• Любой набор X с мощностью большей, чем у натуральных чисел, или | Х | > | Н |, например | р | "=" ${\mathfrak {c}}$> | N |, называется несчетным .

Бесконечные множества

Наша интуиция, полученная при работе с конечными множествами, не работает, когда мы имеем дело с бесконечными множествами . В конце 19 века Георг Кантор , Готтлоб Фреге , Рихард Дедекинд и другие отвергли точку зрения, согласно которой целое не может быть того же размера, что и часть. Одним из примеров этого является парадокс Гильберта о Гранд-отеле . Действительно, Дедекинд определил бесконечное множество как такое, которое может быть помещено во взаимно однозначное соответствие со строгим подмножеством (то есть имеющее тот же размер в смысле Кантора); это понятие бесконечности названо Дедекиндом бесконечным . Кантор ввел кардинальные числа и показал — согласно своему определению размера, основанному на биекции, — что некоторые бесконечные множества больше других. Наименьшая бесконечная мощность — это мощность натуральных чисел ( $\aleph _{0}$).

Мощность континуума

Основная статья: Мощность континуума

Одним из наиболее важных результатов Кантора было то, что мощность континуума ( ${\mathfrak {c}}$) больше, чем у натуральных чисел ( $\aleph _{0}$); то есть действительных чисел R чем натуральных чисел N. больше , А именно, Кантор показал, что ${\mathfrak {c}}=2^{\aleph _{0}}=\beth _{1}$ (см. Бет ) удовлетворяет:

$2^{\aleph _{0}}>\aleph _{0}$

(см. диагональный аргумент Кантора или первое доказательство несчетности Кантора ).

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

$2^{\aleph _{0}}=\aleph _{1}$

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

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

Первый из этих результатов становится очевидным, если рассмотреть, например, функцию тангенса , которая обеспечивает взаимно однозначное соответствие между интервалом (-½π, ½π) и R (см. также парадокс Гильберта о Гранд-Отеле ).

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

Кантор также показал, что множества с мощностью строго большей, чем ${\mathfrak {c}}$существуют (см. его обобщенный диагональный аргумент и теорему ). К ним относятся, например:

• набор всех подмножеств R , то есть мощности набор R , записанный P ( R ) или 2 ^р
• набор Р ^р всех функций от R до R

Оба имеют мощность

$2^{\mathfrak {c}}=\beth _{2}>{\mathfrak {c}}$

(см. Бет два ).

Кардинальные равенства ${\mathfrak {c}}^{2}={\mathfrak {c}},$ ${\mathfrak {c}}^{\aleph _{0}}={\mathfrak {c}},$ и ${\mathfrak {c}}^{\mathfrak {c}}=2^{\mathfrak {c}}$ можно продемонстрировать с помощью кардинальной арифметики :

${\mathfrak {c}}^{2}=\left(2^{\aleph _{0}}\right)^{2}=2^{2\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\aleph _{0}}=\left(2^{\aleph _{0}}\right)^{\aleph _{0}}=2^{{\aleph _{0}}\times {\aleph _{0}}}=2^{\aleph _{0}}={\mathfrak {c}},$

${\mathfrak {c}}^{\mathfrak {c}}=\left(2^{\aleph _{0}}\right)^{\mathfrak {c}}=2^{{\mathfrak {c}}\times \aleph _{0}}=2^{\mathfrak {c}}.$

Примеры и свойства

• Если X = { a , b , c } и Y = {яблоки, апельсины, персики}, где a , b и c различны, то | Х | = | Ю | потому что { ( a , яблоки), ( b , апельсины), ( c , персики)} является биекцией между множествами X и Y . Мощность каждого из X и Y равна 3.
• Если | Х | ≤ | Y |, то существует Z такой, что | Х | = | Я | и Z ⊆ Y .
• Если | Х | ≤ | Ю | и | Ю | ≤ | X |, тогда | Х | = | Ю |. Это справедливо даже для бесконечных кардиналов и известно как теорема Кантора – Бернштейна – Шредера .
• Множества с мощностью континуума включают множество всех действительных чисел, множество всех иррациональных чисел и интервал $[0,1]$.

Союз и пересечение

Основная статья: Принцип включения-исключения

Если A и B — непересекающиеся множества , то

$\left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .$

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

$\left\vert C\cup D\right\vert +\left\vert C\cap D\right\vert =\left\vert C\right\vert +\left\vert D\right\vert .$

Определение мощности в теории классов ( НБГ или МК )

Здесь $V$ обозначают класс всех множеств, а ${\mbox{Ord}}$ обозначает класс всех порядковых чисел.

$|A|:={\mbox{Ord}}\cap \bigcap \{\alpha \in {\mbox{Ord}}|\exists (f:A\to \alpha ):(f{\mbox{ injective}})\}$

Мы используем пересечение класса, который определяется $(x\in \bigcap Q)\iff (\forall q\in Q:x\in q)$, поэтому $\bigcap \emptyset =V$. В этом случае

$(x\mapsto |x|):V\to {\mbox{Ord}}$.

Это определение позволяет также получить мощность любого собственного класса $P$, в частности

$|P|={\mbox{Ord}}$

Это определение естественно, поскольку оно согласуется с аксиомой ограничения размера, которая подразумевает биекцию между $V$ и любой подходящий класс.

См. также

• Число Алеф
• Число Бет
• Парадокс Кантора
• Теорема Кантора
• Счетное множество
• Подсчет
• Ординальность
• Принцип «ячейки»