Будь-яка множина, рівнопотужна множині всіх дійсних чисел з інтервалу (0,1), називається континуальною, або множиною потужності континуум.
З наведених вище прикладів 1.12 (3,4) і зауваження про рівнопотужність усіх інтервалів і відрізків дійсної прямої, а також твердження про рівнопотужність будь-якого відрізка і всієї дійсної прямої випливає, що всі ці множини точок будуть континуальними.
Теорема 1.6. Якщо M - незліченна множина, а A - скінченна або зліченна підмножина множини M, то множини M\A і M рівнопотужні, тобто
M \ A ~ M.
Доведення. Очевидно, що множина M \ A незліченна. Якби множина M'=M \ A була зліченною, то за теоремою 1.4 множина M = M' ÈA була б також зліченною, що суперечило б умові теореми. Тоді за теоремою 1.2 множина M' містить зліченну підмножину B (BÍM \ A). Позначимо C=(M\A)\B, тоді маємо M \ A=BÈC і M=(AÈB)ÈC. Множина AÈB зліченна. Тоді з рівнопотужностей B~(AÈB) і C ~ C, а також того, що CÇB=Æ і CÇ(AÈB)=Æ, випливає співвідношення BÈC~(AÈB)ÈC, тобто M \ A ~ M.
Сформулюємо декілька наслідків, які випливають із доведених теорем.
Наслідок 1.6.1. Якщо M - нескінченна множина, а множина A - скінченна або зліченна, то MÈA ~ M.
Будемо вважати, що MÇA=Æ. Якщо MÇA¹Æ, то у доведенні можна використати скінченну або зліченну множину A' = A \ M таку, що MÈA=MÈA' і MÇA' =Æ.
Якщо M зліченна множина, то MÈA також зліченна множина (теорема 1.4), отже MÈA ~ M.
Якщо M незліченна множина, то MÈA також незліченна множина. Тоді за теоремою 1. 6 (MÈA) \ A ~ MÈA, тобто M ~ MÈA, оскільки (MÈA) \ A = M.
Наслідок 1.6.2. Множина всіх ірраціональних чисел континуальна.
Число, яке не є коренем жодного многочлена з раціональними коефіцієнтами, називається трансцендентним.
Наслідок 1.6.3. Множина всіх трансцендентних чисел континуальна.
Справедливість наслідків 1.6.2 і 1.6.3 випливає з континуальності множин R і C всіх дійсних і комплексних чисел відповідно, зліченності множин усіх раціональних і всіх алгебраїчних чисел та теореми 1.6.
Із доведених теорем випливає також рівнопотужність інтервалів (0,1) ~ [0,1) ~ (0,1] ~ [0,1].
Сформульована нижче теорема встановлює певний зв'язок між зліченними і континуальними множинами і у своєму доведенні знову використовує діагональний метод Кантора.
Теорема 1.7. Множина b(A) всіх підмножин зліченної множини A має потужність континуум.
Доведення. Оскільки всі зліченні множини рівнопотужні множині N натуральних чисел, то достатньо довести континуальність булеана b(N) множини N. Маючи взаємно однозначну відповідність між множиною N і деякою множиною A, неважко побудувати взаємно однозначну відповідність між їхніми булеанами b(N) і b(A).
Проведемо доведення теореми методом від супротивного. Припустімо, що множина b(N) зліченна й існує нумерація всіх її елементів, тобто b(N)={M1,M2,...,Mk,...}, де MkÍN, k=1,2,.... Поставимо у відповідність кожній множині Mk послідовність tk з нулів і одиниць m1(k), m2(k),...,mi(k),... за таким законом
ì 1, якщо iÎMk,
mi(k) = í
î 0, якщо iÏMk.
Очевидно, ця відповідність є взаємно однозначною.
Розташуємо всі елементи множини b (N) і відповідні їм послідовності у порядку нумерації:
M1 - m1(1), m2(1),...,mk(1),...
M2 - m1(2), m2(2),...,mk(2),...
............................................
Mk - m1(k), m2(k),...,mk(k),...
............................................
Використовуючи діагональний метод Кантора, побудуємо нову послідовність L з нулів і одиниць l1,l2,..., lk,... таку, що lk¹mk(k), тобто
ì 1, якщо mk(k)=0,
lk = í
î 0, якщо mk(k)=1, k = 1,2,3,....
Послідовності L відповідає деяка підмножина MÍN, а саме M={ n | ln=1, n=1,2,...}. Очевидно, підмножина M не входить у вказаний перелік M1,M2,...,Mk,..., оскільки послідовність L відрізняється від кожної з послідовностей tk принаймні в одній k-й позиції. Отже, і множина M відрізняється від кожної з множин Mk, k=1,2,.... Ця суперечність означає, що не існує переліку для елементів множини b(N). Таким чином, множина b (N) незліченна.
Крім того, кожній послідовності tk можна поставити у відповідність нескінченний двійковий дріб 0,m1(k)m2(k)...mk(k)..., який зображує деяке дійсне число з інтервалу (0,1) у двійковій системі числення. I навпаки, будь-яке число з інтервалу (0,1) можна однозначно записати у вигляді нескінченного двійкового дробу. Виняток становлять числа зі зліченної множини раціональних чисел, які записуються за допомогою скінченних двійкових дробів і тому можуть мати дві різні форми зображення у вигляді нескінченних двійкових дробів - з періодом 0 і періодом 1.
Кожному з таких чисел відповідають дві різні послідовності t' і t'', а отже, і два різні елементи множини b(N): один - для зображення з періодом 0, другий - з періодом 1. Позначимо через T множину тих підмножин множини N, які при побудованій вище відповідності зіставляються нескінченним двійковим дробам із періодом, TÍb(N). Тоді існує взаємно однозначна відповідність між множиною всіх дійсних чисел з інтервалу (0,1) і множиною b(N) \ T. Однак, оскільки множина T зліченна, то за теоремою 1.6 маємо b(N) ~ b(N) \ T. Таким чином, множина b(N), а значить і множина b(A) для будь-якої зліченної множини A, мають потужність континуум.
10. Кардинальні числа
Нехай A - деяка множина і S = { B | B ~ A} - сукупність усіх множин, рівнопотужних множині A. Очевидно, що всі множини з S рівнопотужні. Кардинальним числом (позначається |A|, або CardA) будемо називати деякий об’єкт для позначення потужності будь-якої множини із сукупності S.
Зокрема, для скінченної множини A кардинальним числом |A| є натуральне число, яким позначається кількість елементів будь-якої з множин сукупності S. Таким чином, можна вважати, що кардинальне число є узагальненням поняття числа елементів.
Природно виникає питання про порівняння кардинальних чисел нескінченних множин.
Нехай A і B нескінченні множини, тоді логічно можливі такі чотири випадки:
1. Iснує взаємно однозначна відповідність між A і B, тобто A ~ B і |A|=|B|.
2. Існує взаємно однозначна відповідність між множиною A і деякою власною підмножиною B' множини B. Тоді кажуть, що потужність множини A не менша від потужності множини B і записують |A|£|B|.
3. Множина A рівнопотужна деякій підмножині множини B і, навпаки, множина B рівнопотужна деякій підмножині множини A, тобто A~B'ÍB і B~A'ÍA.
За теоремою Кантора-Бернштейна, доведення якої наведено нижче, у цьому випадку виконується A ~ B, тобто |A|=|B|.
4. Не існує взаємно однозначної відповідності між множиною A і жодною підмножиною множини B і, також, не існує взаємно однозначної відповідності між множиною B і жодною підмножиною множини A. З цієї ситуації випливало б, що потужності множин A і B непорівнювані між собою.
Однак більш глибокі дослідження в теорії множин показали, що, спираючись на аксіому вибору (див.розд.1.13), можна довести неможливість четвертого випадку.
Таким чином, потужності будь-яких двох множин A і B завжди порівнювані між собою. Отже, для кардинальних чисел |A| і |B| довільних множин A і B виконується одне з трьох співвідношень: |A|=|B|, |A|£|B| або |B|£|A|.
Якщо |A|£|B|, однак множина A нерівнопотужна множині B, то писатимемо |A|<|B|.
Теорема 1.8 (теорема Kантора-Бернштейна).
Якщо множина A рівнопотужна деякій підмножині B1 множини B, A~B1ÍB і, одночасно, множина B рівнопотужна деякій підмножині A1 множини A, B~A1ÍA, то множини A і B рівнопотужні.
Доведення. Зрозуміло, що роблячи припущення про існування таких підмножин B1ÍB і A1ÍA, що A1 ~ B і B1 ~ A, вважаємо, що A1 і B1 є власними підмножинами множин A і B відповідно. Якщо A1 = A або B1=B, то справедливість теореми очевидна.