Мощность

Определение количества элементов в наборе

Множество всех Платоновых тел состоит из 5 элементов. Таким образом, мощность равна 5 или, выражаясь символами, . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle |S|=5}$

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

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

История

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

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

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

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

Биективная функция от 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 , ^[10] то есть функция от 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 всех действительных чисел . Доказательства см. в диагональном аргументе Кантора или в первом доказательстве несчетности Кантора .

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

Количественные числительные

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

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

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

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

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

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

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

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

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

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

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

Бесконечные наборы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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  |, тогда | Х  | = | Ю  |. Это справедливо даже для бесконечных кардиналов и известно как теорема Кантора – Бернштейна – Шредера .
• Наборы с мощностью континуума включают набор всех действительных чисел, набор всех иррациональных чисел и интервал . ${\displaystyle [0,1]}$

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

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

${\displaystyle \left\vert A\cup B\right\vert =\left\vert A\right\vert +\left\vert B\right\vert .}$

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

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

Смотрите также

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

Рекомендации

1. Вайсштейн, Эрик В. «Кардинальное число». Математический мир .
2. Например, длина и площадь в геометрии . – Линия конечной длины – это множество точек, имеющее бесконечную мощность.
3. "Кардинальность | Блестящая математическая и научная вики" . блестящий.орг . Проверено 23 августа 2020 г.
4. Цепелевич, Джордана: Животные считают и используют ноль. Как далеко заходит их чувство числа? , Кванта , 9 августа 2021 г.
5. «Ранние инструменты подсчета людей». Математическая временная шкала . Проверено 26 апреля 2018 г.
6. Дункан Дж. Мелвилл (2003). Хронология третьего тысячелетия. Архивировано 7 июля 2018 г. в Wayback Machine , Математика третьего тысячелетия . Университет Святого Лаврентия .
7. Аллен, Дональд (2003). «История бесконечности» (PDF) . Техасская математика A&M . Архивировано из оригинала (PDF) 1 августа 2020 г. Проверено 15 ноября 2019 г.
8. Курт фон Фриц (1945). «Открытие несоизмеримости Гиппасом Метапонтумским». Анналы математики .
9. Георг Кантор (1891). «Ueber eine elementare Frage der Mannigfaltigkeitslehre» (PDF) . Jahresbericht der Deutschen Mathematiker-Vereinigung . 1 : 75–78.
10. «Бесконечные множества и мощность». Математика LibreTexts . 05.12.2019 . Проверено 23 августа 2020 г.
11. Фридрих М. Хартогс (1915), Феликс Кляйн ; Вальтер фон Дейк ; Дэвид Хилберт ; Отто Блюменталь (ред.), «Über das Issue der Wohlordnung», Mathematische Annalen , Лейпциг: Б. Г. Тойбнер, 76 (4): 438–443, doi : 10.1007/bf01458215, ISSN  0025-5831, S2CID  121598654
12. Феликс Хаусдорф (2002), Эгберт Брискорн ; Шришти Д. Чаттерджи; и другие. (ред.), Grundzüge der Mengenlehre (1-е изд.), Берлин/Гейдельберг: Springer, стр. 587, ISBN 3-540-42224-2- Оригинальное издание (1914 г.)
13. Коэн, Пол Дж. (15 декабря 1963 г.). «Независимость гипотезы континуума». Труды Национальной академии наук Соединенных Штатов Америки . 50 (6): 1143–1148. Бибкод : 1963PNAS...50.1143C. дои : 10.1073/pnas.50.6.1143 . JSTOR  71858. PMC 221287 . ПМИД  16578557. 
14. Коэн, Пол Дж. (15 января 1964 г.). «Независимость гипотезы континуума, II». Труды Национальной академии наук Соединенных Штатов Америки . 51 (1): 105–110. Бибкод : 1964PNAS...51..105C. дои : 10.1073/pnas.51.1.105 . JSTOR  72252. PMC 300611 . ПМИД  16591132. 
15. Пенроуз, Р. (2005), Дорога к реальности: Полное руководство по законам Вселенной , Vintage Books, ISBN 0-09-944068-7
16. Георг Кантор (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und philosophische Kritik , 91 : 81–125
    Перепечатано в: Георг Кантор (1932), Адольф Френкель (Лебенслауф); Эрнст Цермело (ред.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Берлин: Springer, стр. 378–439.Здесь: стр.413 внизу
17. Прикладная абстрактная алгебра, К. Х. Ким, Ф. В. Руш, серия Эллиса Хорвуда, 1983, ISBN 0-85312-612-7 (студенческое издание), ISBN 0-85312-563-5 (библиотечное издание)