В математике два множества или класса A и B называются равновеликими , если между ними существует взаимно-однозначное соответствие (или биекция), то есть если существует функция из A в B такая, что для каждого элемента y из B существует ровно один элемент x из A с f ( x ) = y . [1] Говорят, что равновеликие множества имеют одинаковую мощность (число элементов). [2] Изучение мощности часто называют равновеликостью (equinumerosity , equalness -of-number ). Иногда вместо этого используются термины равносильность ( equipollence , equalness-of-strength , equalpowerence , equalness-of-power, equalness-of-power ).
Равночисленность имеет характерные свойства отношения эквивалентности . [1] Утверждение о том, что два множества A и B равночисленны, обычно обозначается
Определение равновеликости с использованием биекций может быть применено как к конечным , так и к бесконечным множествам и позволяет утверждать, имеют ли два множества одинаковый размер, даже если они бесконечны. Георг Кантор , изобретатель теории множеств , показал в 1874 году, что существует более одного вида бесконечности, в частности, что совокупность всех натуральных чисел и совокупность всех действительных чисел , хотя обе бесконечны, не являются равновеликими (см. первое доказательство несчетности Кантора ). В своей противоречивой статье 1878 года Кантор явно определил понятие «мощности» множеств и использовал его для доказательства того, что множество всех натуральных чисел и множество всех рациональных чисел равновелики (пример, когда собственное подмножество бесконечного множества равновелико исходному множеству), и что декартово произведение даже счетного бесконечного числа копий действительных чисел равновелико одной копии действительных чисел.
Теорема Кантора 1891 года подразумевает, что ни одно множество не равночисленно своему собственному множеству мощности (множеству всех своих подмножеств). [1] Это позволяет определять все большие и большие бесконечные множества, начиная с одного бесконечного множества.
Если аксиома выбора верна, то кардинальное число множества можно рассматривать как наименьшее порядковое число этой мощности (см. начальный порядковый номер ). В противном случае его можно рассматривать (по трюку Скотта ) как множество множеств минимального ранга, имеющих эту мощность. [1]
Утверждение о том, что любые два множества либо равновелики, либо одно из них имеет меньшую мощность, чем другое, эквивалентно аксиоме выбора . [3]
Равновеликие множества имеют взаимно-однозначное соответствие между собой, [4] и, как говорят, имеют одинаковую мощность . Мощность множества X по сути является мерой количества элементов множества. [1] Равновеликость имеет характерные свойства отношения эквивалентности ( рефлексивность , симметрия и транзитивность ): [1]
Попытка определить мощность множества как класс эквивалентности всех множеств, равночисленных ему, проблематична в теории множеств Цермело–Френкеля , стандартной форме аксиоматической теории множеств , поскольку класс эквивалентности любого непустого множества был бы слишком большим, чтобы быть множеством: это был бы собственный класс . В рамках теории множеств Цермело–Френкеля отношения по определению ограничены множествами (бинарное отношение на множестве A является подмножеством декартова произведения A × A ), и в теории множеств Цермело–Френкеля нет множества всех множеств . В теории множеств Цермело–Френкеля вместо определения мощности множества как класса эквивалентности всех множеств, равночисленных ему, пытаются назначить представительное множество каждому классу эквивалентности ( кардинальное назначение ). В некоторых других системах аксиоматической теории множеств, например, в теории множеств фон Неймана–Бернейса–Гёделя и теории множеств Морса–Келли , отношения распространяются на классы .
Говорят, что множество A имеет мощность, меньшую или равную мощности множества B , если существует однозначная функция (инъекция) из A в B. Это обозначается | A | ≤ | B |. Если A и B не равновелики, то говорят, что мощность A строго меньше мощности B. Это обозначается | A | < | B |. Если аксиома выбора выполняется, то закон трихотомии выполняется для кардинальных чисел , так что любые два множества либо равновелики, либо одно имеет строго меньшую мощность, чем другое. [1] Закон трихотомии для кардинальных чисел также подразумевает аксиому выбора . [3]
Теорема Шредера –Бернштейна утверждает, что любые два множества A и B, для которых существуют две взаимно-однозначные функции f : A → B и g : B → A, являются равночисленными: если | A | ≤ | B | и | B | ≤ | A |, то | A | = | B |. [1] [3] Эта теорема не опирается на аксиому выбора .
Теорема Кантора подразумевает, что ни одно множество не равночисленно своему множеству мощности (множеству всех его подмножеств ). [1] Это справедливо даже для бесконечных множеств . В частности, множество мощности счетно бесконечного множества является несчетным множеством .
Предположение о существовании бесконечного множества N, состоящего из всех натуральных чисел , и предположение о существовании множества мощности любого заданного множества позволяет определить последовательность N , P ( N ), P ( P ( N )), P ( P ( P ( N ))), … бесконечных множеств, где каждое множество является множеством мощности множества, предшествующего ему. По теореме Кантора мощность каждого множества в этой последовательности строго превышает мощность множества, предшествующего ему, что приводит к все большим и большим бесконечным множествам.
Работа Кантора подверглась резкой критике со стороны некоторых его современников, например, Леопольда Кронекера , который твердо придерживался финитистской [ 5] философии математики и отвергал идею о том, что числа могут образовывать актуальную, завершенную совокупность ( актуальную бесконечность ). Однако идеи Кантора защищались другими, например, Ричардом Дедекиндом , и в конечном итоге были в значительной степени приняты, решительно поддержанные Давидом Гильбертом . Подробнее см. в разделе «Споры о теории Кантора» .
В рамках теории множеств Цермело–Френкеля аксиома степенного множества гарантирует существование степенного множества любого заданного множества. Кроме того, аксиома бесконечности гарантирует существование по крайней мере одного бесконечного множества, а именно множества, содержащего натуральные числа. Существуют альтернативные теории множеств , например, « общая теория множеств » (GST), теория множеств Крипке–Платека и теория карманных множеств (PST), которые намеренно опускают аксиому степенного множества и аксиому бесконечности и не допускают определения бесконечной иерархии бесконечностей, предложенной Кантором.
Мощности, соответствующие множествам N , P ( N ), P ( P ( N )), P ( P ( P ( N ))), … , являются числами Бет , , , , …, причем первое число Бет равно ( алеф ноль ), мощности любого счетно бесконечного множества, а второе число Бет равно , мощности континуума .
В некоторых случаях множество S и его собственное подмножество могут быть равночисленными. Например, множество четных натуральных чисел равночисленно множеству всех натуральных чисел. Множество, равночисленное собственному подмножеству самого себя, называется бесконечным по Дедекинду . [1] [3]
Аксиома счетного выбора (AC ω ), слабый вариант аксиомы выбора (AC), нужна, чтобы показать, что множество, которое не является бесконечным по Дедекинду, на самом деле конечно . Аксиомы теории множеств Цермело–Френкеля без аксиомы выбора (ZF) недостаточно сильны, чтобы доказать, что каждое бесконечное множество является бесконечным по Дедекинду, но аксиомы теории множеств Цермело–Френкеля с аксиомой счетного выбора ( ZF + AC ω ) достаточно сильны. [6] Другие определения конечности и бесконечности множеств, отличные от данного Дедекиндом, не требуют для этого аксиомы выбора, см. Конечное множество § Необходимые и достаточные условия конечности . [1]
Равночисленность совместима с базовыми операциями над множествами таким образом, что позволяет определить кардинальную арифметику . [1] В частности, равночисленность совместима с непересекающимися объединениями : даны четыре множества A , B , C и D , где A и C с одной стороны, а B и D с другой стороны попарно непересекающиеся , и при этом A ~ B и C ~ D , тогда A ∪ C ~ B ∪ D. Это используется для обоснования определения кардинального сложения .
Кроме того, равночисленность совместима с декартовыми произведениями :
Эти свойства используются для обоснования кардинального умножения .
При наличии двух множеств X и Y множество всех функций из Y в X обозначается как X Y. Тогда справедливы следующие утверждения:
Эти свойства используются для обоснования кардинального возведения в степень .
Более того, множество мощности данного множества A (множество всех подмножеств A ) равночисленно множеству 2 A , множеству всех функций из множества A в множество, содержащее ровно два элемента.
В теории категорий категория множеств , обозначаемая как Set , — это категория, состоящая из совокупности всех множеств как объектов и совокупности всех функций между множествами как морфизмов , с композицией функций как композицией морфизмов. В Set изоморфизм между двумя множествами — это в точности биекция, и два множества равночисленны в точности, если они изоморфны как объекты в Set .
