Нехай f0ÍB´A взаємно однозначна відповідність між B і A. Тоді з того, що B1ÍB випливає, що існує множина A2 = f0(B1)ÌA1 така, що f1ÍB1´A2ÌB´A1, f1Ìf0 і f1 є взаємно одозначною відповідністю між B1 і A2, тобто B1~A2. За умовою теореми A~B1, отже A~A2. Це означає, що існує взаємно однозначна відповідність f2 між множинами A і A2, f2ÍA´A2.
Образом f2(A1) підмножини A1ÌA при відповідності f2 буде деяка множина A3ÌA2. Відповідність f3ÍA1´A3, f3Ìf2 є взаємно однозначною, отже A1~A3. Аналогічно, образом f3(A2) підмножини A2ÌA1 при відповідності f3 буде деяка множина A4ÌA3, а відповідність f4ÍA2´A4, f4Ìf3 буде взаємно однозначною, тобто A2~A4.
Продовжуючи ці міркування, одержимо нескінченний ланцюг строгих включень AÉA1ÉA2ÉA3É...ÉAnÉ.... При цьому виконуються такі співвідношення:
A ~ A2 ~ A4 ~... ~ A2k~ A2k+2 ~...,
A1 ~ A3 ~ A5 ~... ~ A2k+1 ~ A2k+3 ~...,
f0Éf1Éf2Éf3É...ÉfnÉ...
Із наведених співвідношень випливає, що відповідності
f'2 = f2 \ f3Í (A \ A1 )´(A2 \ A3 ),
f'4 = f4 \ f5Í (A2 \ A3 )´(A4 \ A5 ),
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
f'2k+2 = f2k+2 \ f2k+3Í (A2k \ A2k+1 )´(A2k+2 \ A2k+3 ),
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
є взаємно однозначними.
Отже,
(A \ A1) ~ (A2 \ A3 ) ~ (A4 \ A5 ) ~...~ (A2k \ A2k+1) ~ (A2k+2 \ A2k+3) ~....
Оскільки рівнопотужні множини (A \ A1), (A2 \ A3 ), (A4 \ A5 ),..., (A2k \ A2k+1),... попарно не перетинаються, то множини
C1 = (A \ A1) È (A2 \ A3 ) È (A4 \ A5 ) È... È (A2k \ A2k+1)...,
C2 = (A2 \ A3 ) È (A4 \ A5 ) È (A6 \ A7 ) È... È (A2k+2 \ A2k+3)...
також рівнопотужні, тобто C1 ~ C2.
Позначимо через D = AÇA1ÇA2ÇA3Ç...ÇAnÇ....
Неважко переконатись, що
A = DÈ (A \ A1) È (A1 \ A2 ) È (A2 \ A3 ) È... È (An \ An+1)...,
A1 = DÈ (A1 \ A2 ) È (A2 \ A3 ) È... È (An \ An+1)...,
Нехай D0 = DÈ (A1 \ A2 ) È (A3 \ A4 ) È... È (A2k+1 \ A2k+2)...,
тоді попередні співвідношення можна подати у вигляді:
A = D0È [(A \ A1) È (A2 \ A3 ) È (A4 \ A5 ) È... È (A2k \ A2k+1)...] = D0ÈC1,
A = D0È [(A2 \ A3 ) È (A4 \ A5 ) È (A6 \ A7 ) È... È (A2k+2 \ A2k+3)...] = D0ÈC2.
Оскільки між множинами C1 і C2 існує взаємно однозначна відповідність g, а D0ÇC1=Æ і D0ÇC2=Æ, то iD0Èg є взаємно однозначною відповідністю між A і A1, отже, A~A1. Через iD0ÍD0´D0 позначено тотожню взаємно однозначну відповідність між елементами множини D0 : iD0 = { (d,d) | dÎD0 }.
З умови теореми B ~ A1, одержаного співвідношення A~A1 і властивостей симетричності і транзитивності відношення рівнопотужності маємо B ~ A.
Теорема доведена.
Наслідок 1.8.1. Якщо виконуються включення A2ÌA1ÌA і A2~A (|A2|=|A |), то
A1 ~ A (|A1|=|A|).
Справедливість твердження випливає з того, що A ~ A2ÌA1і A1~A1ÌA.
Наслідок 1.8.2. Якщо AÍB, то |A| £ |B|.
Для кардинальних чисел зліченних і континуальних множин, враховуючи їхню поширеність і популярність в сучасній математиці, введені спеціальні позначення. Так кардинальне число множини N всіх натуральних чисел, а значить, і будь-якої зліченної множини позначають через À0 (читається "алеф-нуль"). Кардинальне число континуальних множин позначають через c або À1 ("алеф-один"). Якщо порівняти доведення теорем 1.1 і 1.7, то неважко помітити аналогію у встановленні взаємно однозначної відповідності між підмножинами множини A і двійковими послідовностями (скінченними в теоремі 1.1 і нескінченними в теоремі 1.7). Враховуючи цю аналогію, часто записують співвідношення |b(A)| =2|A| як для скінченних, так і для нескінченних множин. Зокрема, за теоремою 1.7 À1 =2À0.
Наступне питання, яке виникло в теорії множин: чи існує найбільше кардинальне число, тобто, чи існує множина найбільшої потужності? Негативну відповідь на це питання дає наступна важлива теорема, доведення якої належить Г.Кантору.
Теорема 1.9. Потужність множини b(A) підмножин будь-якої непорожньої множини A більша, ніж потужність даної множини A: | b(A)| > |A|.
Доведення. Оскільки існує тривіальна взаємно однозначна відповідність f між множиною A і підмножиною множини b(A): f = { (a,{a}) | aÎA, {a}Îb(A)}, то достатньо довести, що множини A і b (A) нерівнопотужні.
Доведення проведемо від супротивного. Припустимо, що існує взаємно однозначна відповідність g між множинами A і b(A): g = { (b,B) | bÎA і BÎb(A)}. У кожній парі відповідності перша координата b - це елемент множини A, а друга координата B - деяка підмножина множини A. Тому для кожної пари (b,B)Îg виконується одне з двох співвідношень: або bÎB, або bÏB. Побудуємо нову множину K = { b | bÎA і bÏB для (b,B)Îg }.
З того, що ÆÎb (A) випливає, що K¹Æ.
Оскільки K є підмножиною множини A (KÎb(A)), то при взаємно однозначній відповідності g підмножина K відповідає деякому елементові kÎA, тобто існує пара (k,K)Îg. Тоді відносно елемента kÎA і підмножини KÍA можливі дві ситуації: або kÎK, або kÏK.
Нехай kÎK, тоді з умови (k,K)Îg і правила побудови множини K випливає, що kÏK.
З іншого боку, якщо припустити, що kÏK, то з (k,K)Îg і правила побудови множини K повинно виконуватись kÎK.
Одержана суперечність доводить неможливість встановлення взаємно однозначної відповідності між A і b(A). Таким чином, |A| < | b (A)|.
Наслідок 1.9.1. Не існує множини, яка має найбільшу потужність, тобто не існує найбільшого кардинального числа.
Справді, розглянувши множини N, b(N), b(b(N)),..., одержимо нескінченно зростаючу послідовність відповідних кардинальних чисел À0,À1 =2À0,À2 =2À1, ...
На закінчення зупинимось ще на одній цікавій класичній проблемі теорії множин, сформульованій ще у 1884 році Г.Кантором:
гіпотеза континуума, яка стверджує, що не існує множини, кардинальне число Àякої розташоване між À0і À1, тобто À0 < À< À1.
Ця гіпотеза припускає узагальнення, яке носить назву узагальненої гіпотези континуума:
для довільного кардинального числа Àдеякої нескінченної множини з нерівності À' > Àдля будь-якого кардинального числа À' випливає À' > 2À.
Проблему гіпотези континуума майже вісім десятків років намагалися розв’язати найкращі математики світу. I лише у 1963 році тридцятирічний американський математик Пол Коен довів, що гіпотезу континуума не можна ні довести, ні спростувати, виходячи з аксіом теорії множин. Отже, прийняття або відхилення гіпотези континуума є однаково законними, що веде до можливості побудови двох різних несуперечливих теорій множин.
11. Відношення. Властивості відношень
Підмножина R декартового степеня Mn деякої множини M називається n-місним або n-арним відношенням на множині M. Кажуть, що елементи a1,a2,...,anÎM знаходяться у відношенні R, якщо (a1,a2,...,an)ÎR.