Перегляд вихідного коду сторінки Потужність множини

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

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

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

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

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

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

== Визначення ==
Припускаючи [[Аксіома вибору|аксіому вибору]] істинною, потужність множини формально визначається як найменше [[порядкове число]] <math>\alpha</math>, за якого між <math>X</math> і <math>\alpha</math> можна встановити [[Бієкція|бієктивну відповідність]]. Це визначення також називають розподілом кардинальних чисел за фон Нейманом.

Якщо не приймати аксіому вибору, то потрібен інший підхід. Найперше визначення потужності множини <math>X</math> (воно неявно присутнє в роботах Кантора і явно сформульоване у Фреге, а також у [[Principia Mathematica]]) являє собою клас <math>[X]</math> усіх множин, [[Рівнопотужність|рівнопотужних]] <math>X</math>. В [[Теорія множин|аксіоматичних системах]], заснованих на теорії [[Теорія множин Цермело — Френкеля|ZFC]], таке визначення не підходить, оскільки за непорожньої <math>X</math> така сукупність занадто велика, щоб підходити під визначення множини. Точніше, якщо <math>X \ne \varnothing</math>, то існує [[Ін'єкція (математика)|ін'єктивне відображення]] [[Універсальна множина|універсальної множини]] в <math>[X]</math>, за якого кожна множина <math>m</math> переходить у <math>\{m\} \times X</math>, звідки, в силу {{нп|Аксіома обмеження розміру|аксіоми обмеження розміру||Axiom of limitation of size}} випливає, що <math>[X]</math>&nbsp;— власний клас. Це визначення можна використовувати в [[Теорія типів|теорії типів]] та {{Не перекладено|Нові основи (математика)|«нових основах»|en|New Foundations}}, а також у пов'язаних з ними аксіоматичних системах. У разі ZFC визначення можна використовувати, якщо обмежити колекцію <math>[X]</math> рівнопотужними множинами з найменшим [[Ранг (теорія множин)|рангом]] (цей прийом, запропонований [[Дана Скотт|Даною Скоттом]], працює завдяки тому, що сукупність об'єктів, які мають заданий ранг, є множиною).

Формальний порядок серед кардинальних чисел уводиться так: <math>|X| \le |Y|</math> означає, що множину <math>X</math> можна [[Ін'єкція (математика)|ін'єктивно]] відобразити на <math>Y</math>. За [[Теорема Кантора — Бернштейна|теоремою Кантора&nbsp;— Бернштейна]], з пари нерівностей <math>|X| \le |Y|</math> і <math>|Y| \le |X|</math> випливає, що <math>|X| = |Y|</math>. Аксіома вибору еквівалентна твердженням про те, що для будь-яких множин <math>X</math> і <math>Y</math> виконується, принаймні, одна з нерівностей <math>|X| \le |Y|</math> або <math>|Y| \le |X|</math>.

Множина <math>X</math> називається {{Не перекладено|Множина, нескінченна за Дедекіндом|нескінченною за Дедекіндом|en|Dedekind-infinite set}}, якщо в ній існує така [[Підмножина|власна підмножина]] <math>Y</math>, що <math>|X| = |Y|</math>. У протилежному випадку множину називають скінченною за Дедекіндом. [[Скінченна множина|Скінченні]] кардинальні числа збігаються зі звичайними [[Натуральні числа|натуральними числами]]&nbsp;— інакше кажучи, множина <math>X</math> скінченна [[тоді й лише тоді]], коли <math>|X| = |n| = n</math> за деякого натурального <math>n</math>. Всі інші множини [[Нескінченна множина|нескінченні]]. За дотримання аксіоми вибору можна довести, що визначення за Дедекіндом збігаються зі стандартними. Крім того, можна довести, що потужність множини натуральних чисел <math>\aleph_0</math> ([[Числа алеф|алеф-нуль]], або алеф-0&nbsp;— назва утворена від першої літери [[Староєврейська абетка|єврейської абетки]] <math>\aleph</math>) являє собою найменше нескінченно велике кардинальне число, тобто в будь-якій нескінченній множині є підмножина потужності <math>\aleph_0</math>. Наступне за порядком кардинальне число позначається <math>\aleph_1</math> і так далі, [[Числа алеф|число алефів]] нескінченне. Будь-якому порядковому числу <math>\alpha</math> відповідає кардинальне число <math>\aleph_\alpha</math>, причому так можна описати будь-яке нескінченно велике кардинальне число.

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

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

Нехай ''A'' = {a<sub>1</sub>,a<sub>2</sub>,…,a<sub>n</sub>}&nbsp;— [[скінченна множина]] з ''n'' елементів (|A|=n), тоді кількість усіх [[підмножина|підмножин]] множини A дорівнює 2<sup>n</sup>, тобто 2<sup>|A|</sup>.

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

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

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

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

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

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

=== Числа алеф ===
Потужність множини натуральних чисел '''N''' позначається символом <math>\aleph_0</math> (алеф-нуль). Наступні кардинальні числа в порядку зростання позначають <math>\aleph_1, \aleph_2,\dots</math>.

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

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

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

Для незліченних множин, їхня потужність <math>\ge \aleph_0</math>. Тобто, зліченна множина в певному розумінні є «найменшою» з нескінченних множин. Незліченними є множини [[дійсні числа|дійсних]] '''R''' та [[комплексні числа|комплексних]] '''C''' чисел.

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

== Властивості ==

* Дві '''скінченні''' [[Множина|множини]] рівнопотужні тоді й тільки тоді, коли вони складаються з однакового числа [[Елемент множини|елементів]]. Тобто для скінченної множини поняття потужності збігається із звичним поняттям кількості.
* Для нескінченних множин потужність може збігатись з потужністю своєї власної підмножини, наприклад <math>|{\mathbb N}|=|\mathbb Z|</math>.
** Більш того, множина нескінченна тоді і тільки тоді, коли вона містить рівнопотужну власну (тобто таку, що не збігається з основною множиною) підмножину.
* [[Теорема Кантора]] гарантує існування потужнішої множини для будь-якої даної: ''[[Булеан|Множина всіх підмножин]] множини ''A'' має більшу потужність, ніж ''A'', або <math>|2^A| > |A|</math>.''
* За допомогою канторового квадрата можна також довести наступне корисне твердження: ''[[Декартів добуток множин|Декартів добуток]] нескінченної множини ''A'' з самою собою рівнопотужний ''A''.''
* Потужність декартового добутку:
*: <math>|A\times B|=|A|\cdot |B|</math>
* [[Формула включень-виключень|Формула включення-виключення]] в найпростішому виді:
*: <math>|A\cup B|=|A| + |B| - |A\cap B|</math>

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

== Література ==

* ''А.&nbsp;А.&nbsp;Болибрух,'' Проблемы Гильберта (100 лет спустя), Глава 2 [http://www.mccme.ru/mmmf-lectures/books/books/books.php?book=2&page=2 Первая проблема Гильберта: континуум-гипотеза] {{Webarchive|url=https://web.archive.org/web/20040603165414/http://www.mccme.ru/mmmf-lectures/books/books/books.php?book=2&page=2 |date=3 червня 2004 }}, Библиотека «Математическое просвещение», Выпуск 2
* {{Курант.Роббінс.Що таке математика?}}{{Webarchive|url=https://web.archive.org/web/20121213054413/http://www.mccme.ru/free-books/pdf/kurant.htm |date=13 грудня 2012 }} Глава II, §&nbsp;4.
* {{книга
|заголовок       = Факультативный курс по математике. 7-9
|відповідальний = Сост. И. Л. Никольская
|місце = М
|рік = 1991
|видавництво = Просвещение
|сторінки = 109-110
|isbn = 5-09-001287-3
|сторінок = 383
}}

{{Теорія множин}}
{{Математична логіка}}

[[Категорія:Потужність множин| ]]
[[Категорія:Основні поняття теорії нескінченних множин]]