Равномерность - Equinumerosity
В математике , двух множеств или классов и B являются equinumerous , если существует взаимно-однозначное соответствие (или взаимно однозначное соответствие ) между ними, то есть, если существует функция от A до B , что для любого элемента у из B , существует ровно один элемент х из А с F ( х ) = у . Говорят, что одинаковые множества имеют одинаковую мощность (количество элементов). Изучение мощности часто называют равнодоступностью ( равенством числа ). Термины равносильность ( equalness-из-силы ) и equipotence ( equalness-оф-мощности ) иногда используется вместо этого.
Равномерность обладает характерными свойствами отношения эквивалентности . Утверждение, что два множества A и B равносильны, обычно обозначают
- или , или
Определение равнодоступности с использованием биекций может применяться как к конечным, так и к бесконечным множествам , и позволяет указать, имеют ли два множества одинаковый размер, даже если они бесконечны. Георг Кантор , изобретатель теории множеств , показал в 1874 году, что существует более одного вида бесконечности, в частности, что совокупность всех натуральных чисел и совокупность всех действительных чисел , хотя и бесконечны, не равноправны (см . Первое несчетное число Кантора. доказательство ). В своей спорной статье 1878 года Кантор явно определил понятие «мощности» множеств и использовал его, чтобы доказать, что множество всех натуральных чисел и множество всех рациональных чисел равносильны (пример, когда собственное подмножество бесконечного множества равнозначны исходному набору), и что декартово произведение даже счетно бесконечного числа копий действительных чисел равно единственной копии действительных чисел.
Теорема Кантора 1891 г. подразумевает, что никакое множество не равнозначно своему собственному набору мощности (множеству всех его подмножеств). Это позволяет определять все большие и большие бесконечные множества, начиная с одного бесконечного множества.
Если выбранная аксиома верна, то количественное число набора можно рассматривать как наименьшее порядковое число этой мощности (см. Начальный порядковый номер ). В противном случае его можно рассматривать (с помощью уловки Скотта ) как множество множеств минимального ранга, имеющих эту мощность.
Утверждение, что любые два множества либо равноправны, либо одно имеет меньшую мощность, чем другое, эквивалентно выбранной аксиоме .
Мощность
Одинаковые множества имеют взаимно однозначное соответствие между собой и, как говорят, имеют одинаковую мощность . Мощность множества X - это мера «числа элементов множества». Равномерность обладает характерными свойствами отношения эквивалентности ( рефлексивность , симметрия и транзитивность ):
- Рефлексивность
- Учитывая множество , то функция тождества на А биекция от А к себе, показывая , что каждое множество является equinumerous к себе: \ .
- Симметрия
- Для каждой биекции между двумя наборами A и B существует обратная функция, которая является биекцией между B и A , что означает, что если множество A равно множеству B, то B также равно A : A ~ B влечет B ~ A .
- Транзитивность
- Принимая во внимание три набора , B и C с двумя биекций F : A → B и г : B → C , в составе г ∘ е из этих биекций биекция от А до С , так что если и B являются equinumerous и В и С являются equinumerous затем и С являются equinumerous: \ в и в \ С вместе означают A \ C .
Попытка определить мощность множества как класс эквивалентности всех равнодействующих множеств проблематична в теории множеств Цермело – Френкеля , стандартной форме аксиоматической теории множеств , поскольку класс эквивалентности любого непустого множества был бы слишком большим. быть набором: это был бы правильный класс . В рамках теории множеств Цермело-Френкеля, отношения по определению ограничивается множеств (бинарное отношение на множестве А является подмножеством из декартова произведения × A ), и не существует множество всех множеств Цермело-Френкеля набор теория. В теории множеств Цермело – Френкеля вместо определения мощности множества как класса эквивалентности всех равнодействующих множеств пытаются присвоить репрезентативное множество каждому классу эквивалентности ( кардинальное присвоение ). В некоторых других системах аксиоматической теории множеств, например в теории множеств Фон Неймана – Бернейса – Гёделя и теории множеств Морса – Келли , отношения распространяются на классы .
Множество называется имеют мощность , меньшую , чем или равна мощности множества B , если существует один-к-одному функции (инъекции) из A в B . Это обозначается | А | ≤ | B |, Если и В не являются equinumerous, то мощность А называется строго меньше мощности B . Это обозначается | А | <| B |, Если аксиома выбора верна, то закон трихотомии выполняется для кардинальных чисел , так что любые два набора либо равны, либо одно имеет строго меньшую мощность, чем другое. Закон трихотомии для кардинальных чисел также подразумевает аксиому выбора .
Теорема Шредера – Бернштейна утверждает, что любые два множества A и B, для которых существуют две взаимно однозначные функции f : A → B и g : B → A , равносильны: если | А | ≤ | B | и | B | ≤ | A |, то | А | = | B |, Эта теорема не опирается на аксиому выбора .
Теорема кантора
Теорема Кантора подразумевает, что никакое множество не равнозначно своему набору мощности (множеству всех его подмножеств ). Это верно даже для бесконечных множеств . В частности, набор мощности счетно бесконечного множества - это неисчислимый набор .
Предположение о существовании бесконечного множества N, состоящего из всех натуральных чисел, и предположение о существовании набора степеней любого заданного набора позволяет определить последовательность N , P ( N ), P ( P ( N )), P ( P ( P ( N ))),… бесконечных наборов, где каждый набор является набором мощности предшествующего ему набора. По теореме Кантора мощность каждого набора в этой последовательности строго превышает мощность набора, предшествующего ему, что приводит к все большим и большим бесконечным множествам.
Работа Кантора подверглась резкой критике со стороны некоторых его современников, например, Леопольда Кронекера , который твердо придерживался финитистской философии математики и отвергал идею о том, что числа могут образовывать реальную завершенную совокупность ( актуальную бесконечность ). Однако идеи Кантора защищали другие, например Ричард Дедекинд , и в конечном итоге были широко приняты и решительно поддержаны Дэвидом Гильбертом . См. Споры по теории Кантора для получения дополнительной информации.
В рамках теории множеств Цермело-Френкеля , то аксиома булеана гарантирует существование множества мощности любого заданного набора. Более того, аксиома бесконечности гарантирует существование по крайней мере одного бесконечного множества, а именно множества, содержащего натуральные числа. Есть альтернативные набор теорий , например , « общая теория множеств » (GST), теория множеств Крипке Platek и карманные теории множеств (PST), что сознательно не аксиомой булеана и аксиомы бесконечности и не допускают определение бесконечная иерархия бесконечностей, предложенная Кантором.
Мощности , соответствующие множества N , P ( N ), P ( P ( N )), Р ( Р ( Р ( Н ))), ... являются числа Beth , , , , ..., с первым номером Beth равны к ( алеф нуля ), мощность любого счетный бесконечного множества, а второе число Beth , равные , по мощности континуума .
Дедекиндово-бесконечные множества
В некоторых случаях набор S и его собственное подмножество могут быть равным числом. Например, множество четных натуральных чисел равно множеству всех натуральных чисел. Множество, равное количеству собственных подмножеств, называется дедекиндово-бесконечным .
Аксиома счетного выбора (AC со ), слабый вариант аксиомы выбора (AC), необходимо , чтобы показать , что множество, не Дедекинду бесконечна на самом деле конечна . В аксиомы из теории множеств Цермело-Френкеля без аксиомы выбора (ZF) не являются достаточно сильными , чтобы доказать , что каждое бесконечное множество является Дедекинду бесконечным, но аксиомы теории множеств Цермело-Френкеля с аксиомой счетного выбора ( ZF + AC ω ) достаточно сильны. Другие определения конечности и бесконечности множеств, кроме тех, что были даны Дедекиндом, не требуют аксиомы выбора для этого, см. Конечное множество § Необходимые и достаточные условия конечности .
Совместимость с набором операций
Эквивалентность совместима с основными операциями над множеством таким образом, что позволяет определять кардинальную арифметику . В частности, равнодоступность совместима с непересекающимися союзами : даны четыре набора A , B , C и D с A и C с одной стороны и B и D с другой стороны, попарно не пересекающимися, а с A ~ B и C ~ D тогда A ∪ C ~ B ∪ D . Это используется для обоснования определения кардинального сложения .
Кроме того, равноденствие совместимо с декартовыми произведениями :
- Если \ B и C \ D затем × C \ B × D .
- А × Б ~ Б × А
- ( A × B ) × C ~ A × ( B × C )
Эти свойства используются для обоснования количественного умножения .
Даны два множества X и Y , множество всех функций из Y в X обозначим через X Y . Тогда верны следующие утверждения:
- Если \ B и C \ D затем С \ B D .
- В ∪ С ~ В × С для непересекающихся B и C .
- ( A × B ) C ~ A C × B C
- ( А Б ) С ~ А В × С
Эти свойства используются для обоснования кардинального возведения в степень .
Кроме того, силовой агрегат данного множества А (множество всех подмножеств из А ) является equinumerous к множеству 2 А , множество всех функций из множества А до множества , содержащего ровно два элемента.
Категориальное определение
В теории категорий , то категория множеств , обозначаемое Set , является категорией , состоящая из совокупности всех множеств как объекты и совокупности всех функций между множествами как морфизмы , с композицией функций в композиции морфизмов. В комплекте , изоморфизм между двумя множествами именно биекция, и два набора equinumerous точно , если они изоморфны как объекты в Set .