Введение

Математические отношения между двумя множествами

В математике два множества или класса A и B называются эквинумеро́зными, если между ними существует взаимно однозначное соответствие (или биекция), то есть если существует функция из A в B, такая, что для каждого элемента y из B существует ровно один элемент x из A, для которого f(x) = y. Изучение кардинальности часто называют эквинумеро́зией (равенством мощности). Вместо этого иногда используются термины эквипо́ллентность (равенство силы) и эквипоте́нтность (равенство мощности). Эквинумеро́зность обладает характеристическими свойствами отношения эквивалентности и говорят, что они имеют одинаковую кардинальность. Кардинальность множества X – это, по сути, мера количества элементов множества. Рефлексивность: для любого множества A тождественная функция на A является биекцией из A в себя, показывая, что каждое множество A эквинумеро́зно самому себе: A ~ A. Симметрия: для каждой биекции между двумя множествами A и B существует обратная функция, которая является биекцией между B и A, что означает, что если множество A эквинумеро́зно множеству B, то B также эквинумеро́зно множеству A: A ~ B влечет за собой B ~ A. Транзитивность: для трех множеств A, B и C с двумя биекциями f: A → B и g: B → C, композиция g ∘ f этих биекций является биекцией из A в C, поэтому если A и B эквинумеро́зны, а B и C эквинумеро́зны, то A и C эквинумеро́зны: A ~ B и B ~ C вместе влечет за собой A ~ C.

Попытка определить кардинальность множества как класс эквивалентности всех множеств, эквинумеро́зных ему, проблематична в теории множеств Цермело — Френкеля, стандартной форме аксиоматической теории множеств, поскольку класс эквивалентности любого непустого множества был бы слишком велик, чтобы быть множеством: это был бы собственный класс. В рамках теории множеств Цермело — Френкеля отношения по определению ограничены множествами (бинарное отношение на множестве A является подмножеством декартова произведения A × A), и в теории множеств Цермело — Френкеля нет множества всех множеств. В теории множеств Цермело — Френкеля вместо определения кардинальности множества как класса эквивалентности всех эквинумеро́зных ему множеств, пытаются назначить представительное множество каждому классу эквивалентности (кардинальное отображение). В некоторых других системах аксиоматической теории множеств, например, в теории множеств фон Неймана — Бернайса — Гёделя и теории множеств Морса — Келли, отношения расширяются на классы. Множество A считается имеющим кардинальность меньше или равную кардинальности множества B, если существует инъективная функция (вложение) из A в B. Это обозначается |A| ≤ |B|. Если A и B не эквинумеро́зны, то кардинальность A считается строго меньше кардинальности B. Это обозначается |A| < |B|. Если выполняется аксиома выбора, то закон трихотомии справедлив для кардинальных чисел, так что любые два множества либо эквинумеро́зны, либо одно имеет строго меньшую кардинальность, чем другое. Теорема Шрёдера — Бернштейна утверждает, что любые два множества A и B, для которых существуют две инъективные функции f: A → B и g: B → A, эквинумеро́зны: если |A| ≤ |B| и |B| ≤ |A|, то |A| = |B|. философии математики и отвергали идею о том, что числа могут образовывать актуальную, завершенную совокупность (актуальную бесконечность). Однако идеи Кантора защищали другие, например Рихард Дедекинд, и в конечном итоге они были в значительной степени приняты, получив сильную поддержку со стороны Давида Гильберта. Подробнее см. статью «Споры вокруг теории Кантора». В рамках теории множеств Цермело — Френкеля аксиома о множестве степеней гарантирует существование множества степеней любого данного множества. Кроме того, аксиома бесконечности гарантирует существование по крайней мере одного бесконечного множества, а именно множества, содержащего натуральные числа. Существуют альтернативные теории множеств, например, «общая теория множеств» (GST), теория множеств Крипке — Платека и теория карманных множеств (PST), которые намеренно опускают аксиому о множестве степеней и аксиому бесконечности и не позволяют определить бесконечную иерархию бесконечностей, предложенную Кантором. Кардинальности, соответствующие множествам N, P(N), P(P(N)), P(P(P(N))), являются числами бета , , , , , причем первое число бета равно (алеф-нуль), кардинальности любого счетно бесконечного множества, а второе число бета равно , кардинальности континуума.

Бесконечные множества

В некоторых случаях возможно, чтобы множество S и его собственное подмножество были равномощными. Например, множество чётных натуральных чисел равномощно множеству всех натуральных чисел. Множество, равномощное собственному подмножеству самого себя, называется бесконечным в смысле Дедекинда. Другие определения конечности и бесконечности множеств, отличные от определения Дедекинда, не требуют аксиомы выбора, см.

Категорическое определение

В теории категорий категория множеств, обозначаемая Set, — это категория, объекты которой — это все множества, а морфизмы — все функции между множествами, причем композиция морфизмов задается композицией функций. В Set изоморфизм между двумя множествами — это в точности биекция, а два множества равномощны тогда и только тогда, когда они изоморфны как объекты в Set.