Мощность

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

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

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

Когда два множества, ⁠ ⁠ ${\displaystyle A}$ и ⁠ ⁠ ${\displaystyle B}$ , имеют одинаковую мощность, это обычно записывается как ; однако, если речь идет о кардинальном числе отдельного множества , оно обозначается просто , с вертикальной чертой с каждой стороны; ^[3] это то же самое обозначение, что и абсолютное значение , и значение зависит от контекста. Кардинальное число множества может также обозначаться как , , , или . ${\displaystyle |A|=|B|}$ ${\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 ; красный : n ∈ f ( n )\ T , синий : n ∈ T \ f ( n ).

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

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

Два множества имеют одинаковую мощность, если существует биекция (или взаимно-однозначное соответствие) от ⁠ ⁠ ${\displaystyle A}$ до ⁠ ⁠ ${\displaystyle B}$ , ^[10] то есть функция от ⁠ ⁠ ${\displaystyle A}$ до ⁠ ⁠ , ${\displaystyle B}$ которая является как инъективной , так и сюръективной . Такие множества называются равномощными , равнополномочными или равночисленными .

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

Для конечных множеств ⁠ ⁠ ${\displaystyle A}$ и ⁠ ⁠ ${\displaystyle B}$ , если существует некоторая биекция из ⁠ ⁠ ${\displaystyle A}$ в ⁠ ⁠ ${\displaystyle B}$ , то каждая инъективная или сюръективная функция из ⁠ ⁠ ${\displaystyle A}$ в ⁠ ⁠ ${\displaystyle B}$ является биекцией. Это больше не верно для бесконечных ⁠ ⁠ ${\displaystyle A}$ и ⁠ ⁠ ${\displaystyle B}$ . Например, функция ⁠ ⁠ ${\displaystyle g}$ from ⁠ ⁠ ${\displaystyle \mathbb {N} }$ to ⁠ ⁠ ${\displaystyle E}$ , определенная с помощью является инъективной, но не сюръективной, поскольку 2, например, не отображается в , а ⁠ ⁠ from ⁠ ⁠ to ⁠ ⁠ , определенная с помощью (см.: операция по модулю ), является сюръективной, но не инъективной, поскольку 0 и 1, например, оба отображаются в 0. Ни ⁠ ⁠ , ни ⁠ ⁠ не могут оспорить , что было установлено существованием ⁠ ⁠ . ${\displaystyle g(n)=4n}$ ${\displaystyle h}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle E}$ ${\displaystyle h(n)=n-(n{\text{ mod }}2)}$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle |E|=|\mathbb {N} |}$ ${\displaystyle f}$

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

⁠ ⁠ ${\displaystyle A}$ имеет мощность, меньшую или равную мощности ⁠ ⁠ ${\displaystyle B}$ , если существует инъективная функция из ⁠ ⁠ ${\displaystyle A}$ в ⁠ ⁠ ${\displaystyle B}$ .

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

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

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

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

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

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

Отношение наличия одинаковой мощности называется равновеликостью , и это отношение эквивалентности на классе всех множеств. Класс эквивалентности множества 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 , мощность которого меньше мощности натуральных чисел , или |  X  | < |  N  |, называется конечным множеством .
• Любое множество X , имеющее ту же мощность, что и множество натуральных чисел, или |  X  | = |  N  | = , называется счетно бесконечным множеством. ^[10] ${\displaystyle \aleph _{0}}$
• Любое множество X , мощность которого больше мощности натуральных чисел, или |  X  | > |  N  |, например |  R  | = > |  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 различны, то |  X  | = |  Y  |, поскольку {( a , яблоки), ( b , апельсины), ( c , персики)} является биекцией между множествами X и Y. Мощность каждого из X и Y равна 3.
• Если |  X  | ≤ |  Y  |, то существует Z такое, что |  X  | = |  Z  | и Z ⊆ Y .
• Если |  X  | ≤ |  Y  | и |  Y  | ≤ |  X  |, то |  X  | = |  Y  |. Это справедливо даже для бесконечных кардиналов и известно как теорема Кантора–Бернштейна–Шредера .
• Множества с мощностью континуума включают множество всех действительных чисел, множество всех иррациональных чисел и интервал . ${\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 .}$

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Столл, Роберт Р. Теория множеств и логика . Сан-Франциско, Калифорния: Dover Publications. ISBN 978-0-486-63829-4.
2. Вайсштейн, Эрик В. «Кардинальное число». MathWorld .
3. "Мощность | Brilliant Math & Science Wiki". brilliant.org . Получено 2020-08-23 .
4. Цепелевич, Джордана Животные считают и используют ноль. Насколько далеко простирается их чувство числа? , Quanta , 9 августа 2021 г.
5. "Ранние инструменты счета человека". Хронология математики . Получено 2018-04-26 .
6. Дункан Дж. Мелвилл (2003). Хронология третьего тысячелетия. Архивировано 2018-07-07 в Wayback Machine , Математика третьего тысячелетия . Университет Св. Лаврентия .
7. Аллен, Дональд (2003). «История бесконечности» (PDF) . Texas A&M Mathematics . Архивировано из оригинала (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. "Бесконечные множества и мощность". Mathematics LibreTexts . 2019-12-05 . Получено 2020-08-23 .
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. Bibcode : 1963PNAS...50.1143C. doi : 10.1073 /pnas.50.6.1143 . JSTOR  71858. PMC 221287. PMID  16578557. 
14. Коэн, Пол Дж. (15 января 1964 г.). «Независимость гипотезы континуума, II». Труды Национальной академии наук Соединенных Штатов Америки . 51 (1): 105–110. Bibcode :1964PNAS...51..105C. doi : 10.1073/pnas.51.1.105 . JSTOR  72252. PMC 300611 . PMID  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. Прикладная абстрактная алгебра, KH Kim, FW Roush, Ellis Horwood Series, 1983, ISBN 0-85312-612-7 (студенческое издание), ISBN 0-85312-563-5 (библиотечное издание)  

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