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

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

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

Визначення

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

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

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

Визначення 2. Дві множини називають рівнопотужними, якщо між ними можна встановити взаємно-однозначну відповідність^[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$ )^[3].

Властивості

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

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

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

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

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

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

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

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

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

[FOOTNOTEМатематическая_энциклопедия1977-1] Математическая энциклопедия, 1977.

[FOOTNOTEВерещагин,_Шень201212-2] Верещагин, Шень, 2012, с. 12.

[FOOTNOTEВерещагин,_Шень201217-3] Верещагин, Шень, 2012, с. 17.

[FOOTNOTEВерещагин,_Шень201228-4] Верещагин, Шень, 2012, с. 28.

[FOOTNOTEВерещагин,_Шень201218-5] Верещагин, Шень, 2012, с. 18.

[FOOTNOTEКуратовский,_Мостовский1970177-6] Куратовский, Мостовский, 1970, с. 177.

[1]

[2]

[3]

[4]

[5]

[6]