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

Визначимо відношення ~ на множині усіх множин U: A~В Û А та В рівнопотужні. Дане відношення рефлексивне (А~А), симетричне (якщо А~В, то існує деяке взаємно однозначне відображення F А на В, але тоді F^-1 є взаємно однозначне відображення В на А, отже, В~А), транзитивне (якщо А~В та В~С, то існують деякі взаємно однозначні відображення F:A®B та G:B®C, але тоді H=F*G – взаємно однозначне відображення А на С, отже, А~С). Таким чином, ~ є відношенням еквівалентності. Класи розбиття, що визначається відношенням ~, називаються кардинальними числами. Потужністю множини А (позначається |А|) назвемо кардинальне число [A]. Кардинальне числo виду [N_m] позначається m, кардинальне число [Æ] позначається 0. Множина, еквівалентна множині N_m для деякого m (mÎN⁺), називається скінченною.

Множина, еквівалентна множині N⁺, називається зліченною. Кардинальне число [N⁺] позначається À₀ (алеф-нуль).

Прикладом зліченної множини є множина Р усіх додатних парних чисел. Дійсно функція f(n)=2n задає взаємно однозначне відображення N⁺ на Р. Множина А={1,2,3} не є зліченною, оскільки будь-яке відображення N⁺ на А не є взаємно однозначним.

Сформулюємо деякі твердження про потужності множин.

1. Нехай А – скінченна множина й АÌВ. Тоді множини А та В не рівнопотужні.

2. Нехай А – нескінченна підмножина зліченної множини. Тоді А зліченна.

3. Об’єднання скінченної сукупності зліченних множин є зліченна множина.

4. Об’єднання зліченної сукупності зліченних множин є зліченна множина.

5. (Теорема Кантора). Множина усіх дійсних чисел інтервалу (0,1) незліченна.

6. Булеан зліченної множини є незліченна множина.

Множина, еквівалентна множині усіх дійсних чисел інтервалу (0,1), називається континуальною, або множиною потужності континууму.