Равномощность

Взаимно-однозначное соответствие множеств

Определение 1. Функция ${\displaystyle f,}$ определённая на множестве ${\displaystyle A}$ и принимающая значения во множестве ${\displaystyle B,}$ называется взаимно-однозначным соответствием[1], если:

• разным элементам ${\displaystyle A}$ соответствуют разные элементы ${\displaystyle B;}$
• каждый элемент ${\displaystyle B}$ поставлен в соответствие некоторому элементу ${\displaystyle A}$.

Легко видеть, что взаимно-однозначное соответствие как функция имеет (однозначную) обратную функцию, определённую на всём множестве ${\displaystyle B.}$

Определение 2. Два множества называют равномощными, если между ними можно установить взаимно-однозначное соответствие[2]. Варианты терминологии: равномощные множества «имеют одинаковую мощность» или «одинаковое кардинальное число».

В указанном соответствии любому элементу каждого из равномощных множеств соответствует ровно один элемент другого множества.

Разные авторы предлагали разные символы для обозначения равномощности множеств ${\displaystyle A,B}$:

${\displaystyle A\sim B}$

${\displaystyle |A|=|B|}$

${\displaystyle A\approx B}$

${\displaystyle {\bar {\bar {A}}}={\bar {\bar {B}}}}$ (обозначение Кантора)

${\displaystyle Eq(A,B)}$ (обозначение Бурбаки)

#${\displaystyle A}$ = #${\displaystyle B}$

${\displaystyle \mathrm {card} (A)=\mathrm {card} (B)}$

Далее в данной статье используется первое обозначение.

Множество натуральных чисел ${\displaystyle \mathbb {N} }$ и множество чётных чисел равномощны, так как каждому натуральному числу ${\displaystyle n}$ взаимно-однозначно соответствует чётное число ${\displaystyle 2n.}$ Все множества, равномощные ${\displaystyle \mathbb {N} ,}$ называются счётными. Любое бесконечное подмножество ${\displaystyle \mathbb {N} }$ счётно — например, множество простых чисел.

Множество рациональных чисел счётно, однако множество вещественных чисел ${\displaystyle \mathbb {R} }$ уже несчётно.

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

Изложенный подход часто используется, чтобы определить понятие бесконечного множества «по Дедекинду»: множество ${\displaystyle A}$ называется бесконечным, если оно равномощно своему собственному подмножеству (то есть подмножеству, не совпадающему со всем ${\displaystyle A}$)[3].

Отношение равномощности является отношением эквивалентности:

1. Каждое множество равномощно самому себе.
2. Если ${\displaystyle A\sim B,}$ то ${\displaystyle B\sim A.}$
3. Если ${\displaystyle A\sim B}$ и ${\displaystyle B\sim C,}$ то ${\displaystyle A\sim C.}$

Следовательно, отношение равномощности разбивает множества на непересекающиеся классы равномощных множеств. Это разбиение позволило Кантору определить понятие мощности множества как одного из таких классов (в аксиоматической теории множеств понятие мощности вводится несколько иначе, см. подробности в статье о мощности множества).

Из теоремы Кантора вытекает, что никакое множество не может быть равномощно множеству своих подмножеств (которое всегда имеет бо́льшую мощность)[4].

Теорема Кантора — Бернштейна: если из двух множеств А и В каждое эквивалентно части другого, то эти два множества равномощны.

В 1877 году Кантор обнаружил ряд необычных следствий своей теории[5].

• Конечный отрезок прямой равномощен всей бесконечной прямой.
• Вся плоскость, любой квадрат на ней и отрезок прямой равномощны.

Отношение равномощности согласовано (с некоторыми ограничениями) с теоретико-множественными операциями[6].

• (Декартово произведение): ${\displaystyle A\times B\sim B\times A;\ (A\times B)\times C\sim A\times (B\times C)}$
• Если ${\displaystyle A_{1}\sim B_{1}}$ и ${\displaystyle A_{2}\sim B_{2},}$ то ${\displaystyle (A_{1}\times A_{2})\sim (B_{1}\times B_{2})}$
• (Объединение) Пусть ${\displaystyle A_{1}\sim B_{1},A_{2}\sim B_{2},}$ причём ${\displaystyle A_{1}}$ не пересекается с ${\displaystyle A_{2},B_{1}}$ не пересекается с ${\displaystyle B_{2}.}$ Тогда ${\displaystyle (A_{1}\cup A_{2})\sim (B_{1}\cup B_{2})}$

• Верещагин Н. К., Шень А. Начала теории множеств. — М.: МЦНМО, 2012. — ISBN 978-5-4439-0012-4.
• Кудрявцев Л. Д. Взаимно однозначное соответствие // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1977. — Т. 1. — С. 690. — 1152 с.
• Куратовский К., Мостовский А. Теория множеств / Перевод с английского М. И. Кратко под редакцией А. Д. Тайманова. — М.: Мир, 1970. — 416 с.
• Ященко И. В. Равномощность множеств / Парадоксы теории множеств. М.: Издательство Московского центра непрерывного математического образования, 2002.

• Мощность множеств // Дискретная математика, ВШЭ, факультет компьютерных наук, 2014
• Равномощные множества /Введение в теорию множеств, МГУ, 2007
• Yiannis Moschovakis. CHAPTER 2 EQUINUMEROSITY // Notes on Set Theory, Springer, 2005. ISBN 9780387287225 pp. 7-18  (англ.)