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

Рівнопотужність — відношення двох довільних (скінченних або нескінченних) множин, що означає, нестрого кажучи, що одна з множин містить стільки ж елементів, як і інша. Скінченні множини рівнопотужні тоді й лише тоді, коли вони містять однакові кількості елементів. Наприклад, множина традиційних зодіакальних сузір'їв і множина ребер куба рівнопотужні, оскільки обидві містять по 12 елементів.

Поняття рівнопотужності, введене Георгом Кантором 1878 року, розширює це відношення на нескінченні множини, на нього спирається визначення центрального в теорії множин поняття потужності множини. Кантор також визначив порівняння потужностей — якщо дві множини не рівнопотужні, то потужність однієї з них більша, ніж іншої (у доведенні використовується аксіома вибору).

Визначення

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

Визначення 1. Функція $f,$ яка визначена на множині $A$ і набуває значень у множині $B,$ називається взаємно-однозначною відповідністю, якщо:

• різним елементам $A$ відповідають різні елементи $B;$
• кожен елемент $B$ поставлено у відповідність деякому елементу $A$.

Легко бачити, що взаємно-однозначна відповідність як функція має (однозначну) обернену функцію, визначену на всій множині $B.$

Визначення 2. Дві множини називають рівнопотужними, якщо між ними можна встановити взаємно-однозначну відповідність. Варіанти термінології: рівнопотужні множини «мають однакову потужність» або «однакове кардинальне число».

У зазначеній відповідності будь-якому елементу кожної з рівнопотужних множин відповідає рівно один елемент іншої множини.

Різні автори пропонували різні символи для позначення рівнопотужності множин $A,B$:

$A\sim B$

$|A|=|B|$

$A\approx B$

${\bar {\bar {A}}}={\bar {\bar {B}}}$ (позначення Кантора)

$Eq(A,B)$ (позначення Бурбакі)

#$A$ = #$B$

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

Далі в цій статті використовується перше позначення.

Приклади

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

Множина раціональних чисел зліченна, проте множина дійсних чисел $\mathbb {R}$ вже незліченна.

Всі кола рівнопотужні. Щоб переконатися в цьому, побудуємо для кожного кола полярну систему координат з початком у центрі кола і поставимо у відповідність точки з однаковим полярним кутом.

Викладений підхід часто використовується, щоб визначити поняття нескінченної множини «за Дедекіндом»: множина $A$ називається нескінченною, якщо вона рівнопотужна своїй власній підмножині (тобто підмножині, що не збігається з усією $A$).

Властивості

Відношення рівнопотужності є відношенням еквівалентності:

1. Кожна множина рівнопотужна сама собі.
2. Якщо $A\sim B,$ то $B\sim A.$
3. Якщо $A\sim B$ і $B\sim C,$ то $A\sim C.$

Отже, відношення рівнопотужності розбиває множини на неперетинні класи рівнопотужних множин. Це розбиття дозволило Кантору визначити поняття потужності множини як одного з таких класів (в аксіоматичній теорії множин поняття потужності вводиться трохи інакше, див. подробиці в статті про потужність множини).

З теореми Кантора випливає, що ніяка множина не може бути рівнопотужною множині своїх підмножин (яка завжди має більшу потужність).

Теорема Кантора — Бернштейна: якщо з двох множин А і В кожна еквівалентна частині іншої, то ці дві множини рівнопотужні.

1877 року Кантор виявив низку незвичайних наслідків своєї теорії.

• Скінченний відрізок прямої рівнопотужний всій нескінченній прямій.
• Вся площина, будь-який квадрат на ній і відрізок прямої рівнопотужні.

Відношення рівнопотужності узгоджене (з певними обмеженнями) з теоретико-множинними операціями.

• (Декартів добуток): $A\times B\sim B\times A;\ (A\times B)\times C\sim A\times (B\times C)$
• Якщо $A_{1}\sim B_{1}$ і $A_{2}\sim B_{2},$ то $(A_{1}\times A_{2})\sim (B_{1}\times B_{2})$
• (Об'єднання) Нехай $A_{1}\sim B_{1},A_{2}\sim B_{2},$ причому $A_{1}$ не перетинається з $A_{2},B_{1}$ не перетинається з $B_{2}.$ Тоді $(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 (англ.)