Потужність множини

Припускаючи аксіому вибору істинною, потужність множини формально визначається як найменше порядкове число ${\displaystyle \alpha }$, за якого між ${\displaystyle X}$ і ${\displaystyle \alpha }$ можна встановити бієктивну відповідність. Це визначення також називають розподілом кардинальних чисел за фон Нейманом.

Якщо не приймати аксіому вибору, то потрібен інший підхід. Найперше визначення потужності множини ${\displaystyle X}$ (воно неявно присутнє в роботах Кантора і явно сформульоване у Фреге, а також у Principia Mathematica) являє собою клас ${\displaystyle [X]}$ усіх множин, рівнопотужних ${\displaystyle X}$. В аксіоматичних системах, заснованих на теорії ZFC, таке визначення не підходить, оскільки за непорожньої ${\displaystyle X}$ така сукупність занадто велика, щоб підходити під визначення множини. Точніше, якщо ${\displaystyle X\neq \varnothing }$, то існує ін'єктивне відображення універсальної множини в ${\displaystyle [X]}$, за якого кожна множина ${\displaystyle m}$ переходить у ${\displaystyle \{m\}\times X}$, звідки, в силу аксіоми обмеження розміру випливає, що ${\displaystyle [X]}$ — власний клас. Це визначення можна використовувати в теорії типів та «нових основах», а також у пов'язаних з ними аксіоматичних системах. У разі ZFC визначення можна використовувати, якщо обмежити колекцію ${\displaystyle [X]}$ рівнопотужними множинами з найменшим рангом (цей прийом, запропонований Даною Скоттом, працює завдяки тому, що сукупність об'єктів, які мають заданий ранг, є множиною).

Формальний порядок серед кардинальних чисел уводиться так: ${\displaystyle |X|\leq |Y|}$ означає, що множину ${\displaystyle X}$ можна ін'єктивно відобразити на ${\displaystyle Y}$. За теоремою Кантора — Бернштейна, з пари нерівностей ${\displaystyle |X|\leq |Y|}$ і ${\displaystyle |Y|\leq |X|}$ випливає, що ${\displaystyle |X|=|Y|}$. Аксіома вибору еквівалентна твердженням про те, що для будь-яких множин ${\displaystyle X}$ і ${\displaystyle Y}$ виконується, принаймні, одна з нерівностей ${\displaystyle |X|\leq |Y|}$ або ${\displaystyle |Y|\leq |X|}$.

Множина ${\displaystyle X}$ називається нескінченною за Дедекіндом, якщо в ній існує така власна підмножина ${\displaystyle Y}$, що ${\displaystyle |X|=|Y|}$. У протилежному випадку множину називають скінченною за Дедекіндом. Скінченні кардинальні числа збігаються зі звичайними натуральними числами — інакше кажучи, множина ${\displaystyle X}$ скінченна тоді й лише тоді, коли ${\displaystyle |X|=|n|=n}$ за деякого натурального ${\displaystyle n}$. Всі інші множини нескінченні. За дотримання аксіоми вибору можна довести, що визначення за Дедекіндом збігаються зі стандартними. Крім того, можна довести, що потужність множини натуральних чисел ${\displaystyle \aleph _{0}}$ (алеф-нуль, або алеф-0 — назва утворена від першої літери єврейської абетки ${\displaystyle \aleph }$) являє собою найменше нескінченно велике кардинальне число, тобто в будь-якій нескінченній множині є підмножина потужності ${\displaystyle \aleph _{0}}$. Наступне за порядком кардинальне число позначається ${\displaystyle \aleph _{1}}$ і так далі, число алефів нескінченне. Будь-якому порядковому числу ${\displaystyle \alpha }$ відповідає кардинальне число ${\displaystyle \aleph _{\alpha }}$, причому так можна описати будь-яке нескінченно велике кардинальне число.

Для множин зі скінченною кількістю елементів, потужність множини є фактично кількістю елементів цієї множини. Інакше можна сказати, що множина A є скінченною, якщо існує таке натуральне число n, що A ~ {k, k ∈ N∧ k ≤ n}. В іншому випадку, множина називається нескінченною.

Між двома скінченними множинами A і B існує взаємно однозначна відповідність тоді і тільки тоді, коли їхні потужності збігаються, тобто |A|=|B|.

Нехай A = {a₁,a₂,…,a_n} — скінченна множина з n елементів (|A|=n), тоді кількість усіх підмножин множини A дорівнює 2ⁿ, тобто 2^|A|.

Множину всіх підмножин деякої множини A (скінченної або нескінченної) часто позначають через β(A) (або B(A) чи 2^A) і називають булеаном множини A. Очевидно, що для скінченної множини A виконується |B(A)|= 2^|A|.

В загальному випадку, справедливому і для нескінченних множин, множини A та B є рівнопотужними, або мають однакову потужність, якщо можна встановити взаємно однозначну відповідність між елементами цих множин, тобто якщо існує бієкція f:A→B. Рівнопотужні множини позначаються як A ~ B.

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

Для нескінченних множин потужність множини може збігатися з потужністю її власної підмножини.

Приклади: Множина натуральних чисел N рівнопотужна множині S={1,4,9,16,…}, яка складається з квадратів натуральних чисел. Необхідна бієкція встановлюється за законом (n, n²), n∈N, n²∈S.

Множина Z всіх цілих чисел рівнопотужна множині P всіх парних чисел. Тут взаємно однозначна відповідність встановлюється таким чином: (n,2n), n∈Z, 2n∈P.

• Дві скінченні множини рівнопотужні тоді й тільки тоді, коли вони складаються з однакового числа елементів. Тобто для скінченної множини поняття потужності збігається із звичним поняттям кількості.
• Для нескінченних множин потужність може збігатись з потужністю своєї власної підмножини, наприклад ${\displaystyle |{\mathbb {N} }|=|\mathbb {Z} |}$.
  • Більш того, множина нескінченна тоді і тільки тоді, коли вона містить рівнопотужну власну (тобто таку, що не збігається з основною множиною) підмножину.
• Теорема Кантора гарантує існування потужнішої множини для будь-якої даної: Множина всіх підмножин множини A має більшу потужність, ніж A, або ${\displaystyle |2^{A}|>|A|}$.
• За допомогою канторового квадрата можна також довести наступне корисне твердження: Декартів добуток нескінченної множини A з самою собою рівнопотужний A.
• Потужність декартового добутку:

  ${\displaystyle |A\times B|=|A|\cdot |B|}$

• Формула включення-виключення в найпростішому виді:

  ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

• Порядкове число
• Рівнопотужність

• А. А. Болибрух, Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза, Библиотека «Математическое просвещение», Выпуск 2
• Р.Курант, Г.Роббинс, Что такое математика? Глава II, § 4.
• Факультативный курс по математике. 7-9 / Сост. И. Л. Никольская. — М : Просвещение, 1991. — С. 109-110. — ISBN 5-09-001287-3.