Рівнопотужність

Взаємно-однозначна відповідність множин

Визначення 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.
• Куратовский К., Мостовский А. Теория множеств / Перевод с английского М. И. Кратко под редакцией А. Д. Тайманова. — М. : Мир, 1970. — 416 с.
• Ященко И. В. Равномощность множеств / Парадоксы теории множеств. М.: Издательство Московского центра непрерывного математического образования, 2002.

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