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

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

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

Визначення

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

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

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

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

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

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

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

$A\sim B$

$|A|=|B|$

$A\approx B$

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

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

#$A$ = #$B$

$\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(A)=\mathrm{c}\mathrm{a}\mathrm{r}\mathrm{d}(B)$

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

Приклади

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

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

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

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

Властивості

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

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

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

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

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

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

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

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

• (Декартів добуток): $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)$

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Ященко И. В. Равномощность множеств / Парадоксы теории множеств. М.: Издательство Московского центра непрерывного математического образования, 2002.

Посилання

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