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

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

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

Визначення

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

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

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

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

Визначення 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}$).

Властивості

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

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

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

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

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

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

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

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

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

Примітки

1. Математическая энциклопедия, 1977.
2. Верещагин, Шень, 2012, с. 12.
3. Верещагин, Шень, 2012, с. 17.
4. Верещагин, Шень, 2012, с. 28.
5. Верещагин, Шень, 2012, с. 18.
6. Куратовский, Мостовский, 1970, с. 177.

Література

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

Посилання

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