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

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

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

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

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

Потужність множини позначається через . Сам Кантор використовував позначення . Іноді використовують позначення або .

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

Якщо не приймати аксіому вибору, то потрібен інший підхід. Найперше визначення потужності множини (воно неявно присутнє в роботах Кантора і явно сформульоване у Фреге, а також у Principia Mathematica) являє собою клас усіх множин, рівнопотужних . В аксіоматичних системах, заснованих на теорії ZFC, таке визначення не підходить, оскільки за непорожньої така сукупність занадто велика, щоб підходити під визначення множини. Точніше, якщо , то існує ін'єктивне відображення універсальної множини в , за якого кожна множина переходить у , звідки, в силу випливає, що  — власний клас. Це визначення можна використовувати в теорії типів та , а також у пов'язаних з ними аксіоматичних системах. У разі ZFC визначення можна використовувати, якщо обмежити колекцію рівнопотужними множинами з найменшим рангом (цей прийом, запропонований Даною Скоттом, працює завдяки тому, що сукупність об'єктів, які мають заданий ранг, є множиною).

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

Множина називається , якщо в ній існує така власна підмножина , що . У протилежному випадку множину називають скінченною за Дедекіндом. Скінченні кардинальні числа збігаються зі звичайними натуральними числами — інакше кажучи, множина скінченна тоді й лише тоді, коли за деякого натурального . Всі інші множини нескінченні. За дотримання аксіоми вибору можна довести, що визначення за Дедекіндом збігаються зі стандартними. Крім того, можна довести, що потужність множини натуральних чисел (алеф-нуль, або алеф-0 — назва утворена від першої літери єврейської абетки ) являє собою найменше нескінченно велике кардинальне число, тобто в будь-якій нескінченній множині є підмножина потужності . Наступне за порядком кардинальне число позначається і так далі, число алефів нескінченне. Будь-якому порядковому числу відповідає кардинальне число , причому так можна описати будь-яке нескінченно велике кардинальне число.

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

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

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

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

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

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

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

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

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

Числа алеф Потужність множини натуральних чисел N позначається символом (алеф-нуль). Наступні кардинальні числа в порядку зростання позначають .

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

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

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

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

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

Властивості

Дві скінченні множини рівнопотужні тоді й тільки тоді, коли вони складаються з однакового числа елементів. Тобто для скінченної множини поняття потужності збігається із звичним поняттям кількості. Для нескінченних множин потужність може збігатись з потужністю своєї власної підмножини, наприклад . Більш того, множина нескінченна тоді і тільки тоді, коли вона містить рівнопотужну власну (тобто таку, що не збігається з основною множиною) підмножину. Теорема Кантора гарантує існування потужнішої множини для будь-якої даної: Множина всіх підмножин множини A має більшу потужність, ніж A, або . За допомогою канторового квадрата можна також довести наступне корисне твердження: Декартів добуток нескінченної множини A з самою собою рівнопотужний A. Потужність декартового добутку:

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

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

Література

А. А. Болибрух, Проблемы Гильберта (100 лет спустя), Глава 2 Первая проблема Гильберта: континуум-гипотеза , Библиотека «Математическое просвещение», Выпуск 2 Глава II, § 4.