Множество всех Платоновых тел состоит из 5 элементов. Таким образом, мощность равна 5 или, выражаясь символами, .
В математике мощность множества — это мера количества элементов множества . Например, множество содержит 3 элемента и, следовательно, имеет мощность 3. Начиная с конца 19 века это понятие было обобщено на бесконечные множества , что позволяет различать разные типы бесконечности и выполнять над ними арифметические действия . Существует два подхода к кардинальности: один сравнивает множества непосредственно с помощью биекций и инъекций , а другой использует кардинальные числа . [1]
Мощность набора также можно назвать его размером , если невозможна путаница с другими понятиями размера [2] .
Мощность набора обычно обозначается вертикальной чертой с каждой стороны; [3] это то же обозначение, что и абсолютное значение , и его значение зависит от контекста. Мощность набора альтернативно может обозначаться , , , или .
История
Грубое чувство кардинальности, осознание того, что группы вещей или событий сравниваются с другими группами, поскольку содержат больше, меньше или такое же количество экземпляров, наблюдается у множества современных видов животных, что позволяет предположить, что они произошли миллионы лет назад. . [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.
Если | А | ≤ | Б | и | Б | ≤ | А |, тогда | А | = | Б | (факт, известный как теорема Шрёдера–Бернштейна ). Аксиома выбора эквивалентна утверждению, что | А | ≤ | Б | или | Б | ≤ | А | для каждого А , Б. [11] [12]
Количественные числительные
В приведенном выше разделе «мощность» набора была определена функционально. Другими словами, он не был определен как конкретный объект. Однако такой объект можно определить следующим образом.
Отношение одинаковой мощности называется равномерностью , и это отношение эквивалентности на классе всех множеств. Тогда класс эквивалентности множества A по этому отношению состоит из всех тех множеств, которые имеют ту же мощность, что и A . Есть два способа определить «мощность набора»:
Мощность множества A определяется как его класс эквивалентности при равночисленности.
Мощность натуральных чисел обозначается алеф-нуль ( ), а мощность действительных чисел обозначается « » (строчная дробная буква «c») и также называется мощностью континуума . Кантор показал, используя диагональный аргумент , что . Мы можем показать , что это также мощность множества всех подмножеств натуральных чисел.
Гипотеза континуума утверждает, что , т.е. является наименьшим кардинальным числом, большим, чем , т.е. не существует множества, мощность которого находилась бы строго между мощностью целых и действительных чисел. Гипотеза континуума не зависит от ZFC , стандартной аксиоматизации теории множеств; то есть невозможно доказать гипотезу континуума или ее отрицание с помощью ZFC - при условии, что ZFC непротиворечив. Подробнее см. § Мощность континуума ниже. [13] [14] [15]
Конечные, счетные и несчетные множества.
Если аксиома выбора верна, закон трихотомии справедлив для мощности. Таким образом, мы можем дать следующие определения:
Любой набор X с мощностью меньше, чем у натуральных чисел , или | Х | < | N | называется конечным множеством .
Любой набор X , имеющий ту же мощность, что и набор натуральных чисел, или | Х | = | Н | = , называется счетным множеством. [10]
Любой набор X с мощностью большей, чем у натуральных чисел, или | Х | > | Н |, например | р | = > | N |, называется несчетным .
Бесконечные наборы
Наша интуиция, полученная при работе с конечными множествами, не работает, когда мы имеем дело с бесконечными множествами . В конце 19 века Георг Кантор , Готтлоб Фреге , Рихард Дедекинд и другие отвергли точку зрения, согласно которой целое не может быть того же размера, что и часть. [16] [ нужна цитата ] Одним из примеров этого является парадокс Гильберта о Гранд Отеле . Действительно, Дедекинд определил бесконечное множество как такое, которое может быть помещено во взаимно однозначное соответствие со строгим подмножеством (то есть имеющее тот же размер в смысле Кантора); это понятие бесконечности названо Дедекиндом бесконечным . Кантор ввел кардинальные числа и показал — согласно своему определению размера, основанному на биекции, — что некоторые бесконечные множества больше других. Наименьшая бесконечная мощность – это мощность натуральных чисел ( ).
Мощность континуума
Одним из наиболее важных результатов Кантора было то, что мощность континуума ( ) больше, чем мощность натуральных чисел ( ); то есть действительных чисел R больше, чем натуральных чисел N. А именно, Кантор показал, что (см. Бет ) удовлетворяет:
Однако эта гипотеза не может быть ни доказана, ни опровергнута в рамках широко принятой аксиоматической теории множеств ZFC , если ZFC непротиворечива.
Кардинальную арифметику можно использовать, чтобы показать не только то, что число точек на прямой с действительными числами равно числу точек на любом отрезке этой прямой, но и то, что оно равно числу точек на плоскости и, действительно, в любом конечномерном пространстве. Эти результаты весьма нелогичны, поскольку они подразумевают, что существуют собственные подмножества и правильные надмножества бесконечного множества S , которые имеют тот же размер, что и S , хотя S содержит элементы, которые не принадлежат его подмножествам, а надмножества S содержат элементы, которые в него не входят.
Второй результат был впервые продемонстрирован Кантором в 1878 году, но он стал более очевидным в 1890 году, когда Джузеппе Пеано ввел кривые, заполняющие пространство , изогнутые линии, которые скручиваются и поворачиваются достаточно, чтобы заполнить весь любой квадрат, куб или гиперкуб . или конечномерное пространство. Эти кривые не являются прямым доказательством того, что линия имеет то же количество точек, что и конечномерное пространство, но их можно использовать для получения такого доказательства .
Кантор также показал, что множества с мощностью строго больше существующих (см. его обобщенный диагональный аргумент и теорему ). К ним относятся, например:
набор всех подмножеств R , то есть набор мощности R , записанный P ( R ) или 2 R
Если X = { a , b , c } и Y = {яблоки, апельсины, персики}, где a , b и c различны, то | Х | = | Ю | потому что { ( a , яблоки), ( b , апельсины), ( c , персики)} является биекцией между множествами X и Y . Мощность каждого из X и Y равна 3.
Если | Х | ≤ | Y |, то существует Z такой, что | Х | = | Я | и Z ⊆ Y .
Если | Х | ≤ | Ю | и | Ю | ≤ | X |, тогда | Х | = | Ю |. Это справедливо даже для бесконечных кардиналов и известно как теорема Кантора – Бернштейна – Шредера .
^ Аллен, Дональд (2003). «История бесконечности» (PDF) . Техасская математика A&M . Архивировано из оригинала (PDF) 1 августа 2020 г. Проверено 15 ноября 2019 г.
^ Курт фон Фриц (1945). «Открытие несоизмеримости Гиппасом Метапонтумским». Анналы математики .
^ Георг Кантор (1891). «Ueber eine elementare Frage der Mannigfaltigkeitslehre» (PDF) . Jahresbericht der Deutschen Mathematiker-Vereinigung . 1 : 75–78.
^ ab «Бесконечные множества и мощность». Математика LibreTexts . 05.12.2019 . Проверено 23 августа 2020 г.
^ Феликс Хаусдорф (2002), Эгберт Брискорн ; Шришти Д. Чаттерджи; и другие. (ред.), Grundzüge der Mengenlehre (1-е изд.), Берлин/Гейдельберг: Springer, стр. 587, ISBN3-540-42224-2- Оригинальное издание (1914 г.)
↑ Коэн, Пол Дж. (15 декабря 1963 г.). «Независимость гипотезы континуума». Труды Национальной академии наук Соединенных Штатов Америки . 50 (6): 1143–1148. Бибкод : 1963PNAS...50.1143C. дои : 10.1073/pnas.50.6.1143 . JSTOR 71858. PMC 221287 . ПМИД 16578557.
↑ Коэн, Пол Дж. (15 января 1964 г.). «Независимость гипотезы континуума, II». Труды Национальной академии наук Соединенных Штатов Америки . 51 (1): 105–110. Бибкод : 1964PNAS...51..105C. дои : 10.1073/pnas.51.1.105 . JSTOR 72252. PMC 300611 . ПМИД 16591132.
^ Пенроуз, Р. (2005), Дорога к реальности: Полное руководство по законам Вселенной , Vintage Books, ISBN0-09-944068-7
^ Георг Кантор (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 внизу
^ Прикладная абстрактная алгебра, К. Х. Ким, Ф. В. Руш, серия Эллиса Хорвуда, 1983, ISBN 0-85312-612-7 (студенческое издание), ISBN 0-85312-563-5 (библиотечное издание)