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

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

В основі цього поняття лежать природні уявлення про порівняння множин:

1. Будь-які дві множини, між елементами яких може бути встановлено взаємно однозначну відповідність (бієкція), містять однакову кількість елементів (мають однакову потужність).
2. Зворотно: множини, рівні за потужністю, мусять допускати таку взаємно однозначну відповідність.
3. Частина множини не перевершує повної множини за потужністю (тобто за кількістю елементів).

До побудови теорії потужності множин, множини розрізнялися за ознаками: порожня/непорожня і скінченна/нескінченна, також скінченні множини розрізнялися за кількістю елементів. Нескінченні ж множини не можна було порівняти.

Потужність множин дозволяє порівнювати нескінченні множини. Наприклад зліченні множини є «найменшими» нескінченними множинами.

Потужність множини $A$ позначається через $|A|$. Сам Кантор використовував позначення ${\overline {\overline {A}}}$. Іноді використовують позначення $\#A$ або $\mathrm {card} (A)$.

Визначення

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

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

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

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

Числа алеф

Потужність множини натуральних чисел N позначається символом $\aleph _{0}$ (алеф-нуль). Наступні кардинальні числа в порядку зростання позначають $\aleph _{1},\aleph _{2},\dots$.

Зліченність та скінченність множин

Множина A називається зліченною, або зліченно-нескінченною, якщо |A| = |N|. В цьому випадку кажуть, що елементи такої множини можна занумерувати. Зліченними є множини цілих Z, натуральних N та раціональних Q чисел.

Множина, яка є скінченна, або зліченна, називається не більш ніж зліченною.

Нескінченна підмножина зліченної множини є зліченна. Також нескінченна множина містить зліченну підмножину.

Для незліченних множин, їхня потужність $\geq \aleph _{0}$. Тобто, зліченна множина в певному розумінні є «найменшою» з нескінченних множин. Незліченними є множини дійсних R та комплексних C чисел.

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

Про множини, рівнопотужні множині дійсних чисел [або дійсних чисел з інтервалу (0, 1)] кажуть, що вони мають потужність континууму, і потужність таких множин позначається символом c. Континуум-гіпотеза стверджує, що с=$\aleph _{1}$.

Властивості

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

  $|A\times B|=|A|\cdot |B|$

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

  $|A\cup B|=|A|+|B|-|A\cap B|$

Див. також

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

Література

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