Нехай f0B A взаємно однозначна відповідність між B і A. Тоді з того, що B1B випливає, що існує множина A2 = f0(B1)A1 така, що f1B1A2BA1, f1f0 і f1 є взаємно одозначною відповідністю між B1 і A2, тобто B1~A2. За умовою теореми A~B1, отже A~A2. Це означає, що існує взаємно однозначна відповідність f2 між множинами A і A2, f2AA2.

Образом f2(A1) підмножини A1A при відповідності f2 буде деяка множина A3A2. Відповідність f3A1A3, f3f2 є взаємно однозначною, отже A1~A3. Аналогічно, образом f3(A2) підмножини A2A1 при відповідності f3 буде деяка множина A4A3, а відповідність f4A2A4, f4f3 буде взаємно однозначною, тобто A2~A4.

Продовжуючи ці міркування, одержимо нескінченний ланцюг строгих включень AA1A2A3...An.... При цьому виконуються такі співвідношення:

A ~ A2 ~ A4 ~... ~ A2k ~ A2k+2 ~...,

A1 ~ A3 ~ A5 ~... ~ A2k+1 ~ A2k+3 ~...,

f0f1f2f3... 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 = AA1A2A3...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, а D0C1= і D0C2=, то iD0 g є взаємно однозначною відповідністю між A і A1, отже, A~A1. Через iD0D0D0 позначено тотожню взаємно однозначну відповідність між елементами множини D0 : iD0 = { (d,d) | dD0 }.

З умови теореми B ~ A1, одержаного співвідношення A~A1 і властивостей симетричності і транзитивності відношення рівнопотужності маємо B ~ A.

Теорема доведена.

Наслідок 1.8.1. Якщо виконуються включення A2A1A і A2~A (|A2|=|A |), то
A1 ~ A (|A1|=|A|).

Справедливість твердження випливає з того, що A ~ A2A1 і A1~A1A.

Наслідок 1.8.2. Якщо AB, то |A| |B|.

Для кардинальних чисел зліченних і континуальних множин, враховуючи їхню поширеність і популярність в сучасній математиці, введені спеціальні позначення. Так кардинальне число множини N всіх натуральних чисел, а значить, і будь-якої зліченної множини позначають через 0 (читається "алеф-нуль"). Кардинальне число континуальних множин позначають через c або 1 ("алеф-один"). Якщо порівняти доведення теорем 1.1 і 1.7, то неважко помітити аналогію у встановленні взаємно однозначної відповідності між підмножинами множини A і двійковими послідовностями (скінченними в теоремі 1.1 і нескінченними в теоремі 1.7). Враховуючи цю аналогію, часто записують співвідношення |(A)||A| як для скінченних, так і для нескінченних множин. Зокрема, за теоремою 1.7 1 =20.

Наступне питання, яке виникло в теорії множин: чи існує найбільше кардинальне число, тобто, чи існує множина найбільшої потужності? Негативну відповідь на це питання дає наступна важлива теорема, доведення якої належить Г.Кантору.

Теорема 1.9. Потужність множини (A) підмножин будь-якої непорожньої множини A більша, ніж потужність даної множини A: | (A)| > |A|.

Доведення. Оскільки існує тривіальна взаємно однозначна відповідність f між множиною A і підмножиною множини (A): f = { (a,{a}) | aA, {a}(A)}, то достатньо довести, що множини A і (A) нерівнопотужні.

Доведення проведемо від супротивного. Припустимо, що існує взаємно однозначна відповідність g між множинами A і (A): g = { (b,B) | bA і B(A)}. У кожній парі відповідності перша координата b - це елемент множини A, а друга координата B - деяка підмножина множини A. Тому для кожної пари (b,B)g виконується одне з двох співвідношень: або bB, або bB. Побудуємо нову множину K = { b | bA і bB для (b,B)g }.

З того, що (A) випливає, що K .

Оскільки K є підмножиною множини A (K(A)), то при взаємно однозначній відповідності g