Кардинальні числа
Нехай A - деяка множина і S = { B | B ~ A} - сукупність усіх множин, рівнопотужних множині A. Очевидно, що всі множини з S рівнопотужні. Кардинальним числом (позначається |A|, EMBED Equation.2 або Card A) будемо називати деякий об’єкт для позначення потужності будь-якої множини із сукупності 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. (теорема 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, то справедливість теореми очевидна.
Нехай 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. Якщо виконуються включення A2?A1?A і A2~A (|A2|=|A |), то A1 ~ A (|A1|=|A|).
Справедливість твердження випливає з того, що A ~ A2?A1 і A1~A1?A.
Наслідок 2. Якщо A?B, то |A| ? |B|.
Для кардинальних чисел зліченних і континуальних множин, враховуючи їхню поширеність і популярність в сучасній математиці, введені спеціальні позначення. Так кардинальне число множини N всіх натуральних чисел, а значить, і будь-якої зліченної множини позначають через ?0 (читається "алеф-нуль"). Кардинальне число континуальних множин позначають через c або ?1 ("алеф-один"). Якщо порівняти доведення теорем 1.1 і 1.7, то неважко помітити аналогію у встановленні взаємно однозначної відповідності між підмножинами множини A і двійковими послідовностями (скінченними в теоремі 1.1 і нескінченними в теоремі 1.7). Враховуючи цю аналогію, часто записують співвідношення |?(A)| =2|A| як для скінченних, так і для нескінченних множин. Зокрема, за теоремою 1.7 ?1 =2?0.
Наступне питання, яке виникло в теорії множин: чи існує найбільше кардинальне число, тобто, чи існує множина найбільшої потужності? Негативну відповідь на це питання дає наступна важлива теорема, доведення якої належить Г.Кантору.
Теорема 2. Потужність множини ?(A) підмножин будь-якої непорожньої множини A більша, ніж потужність даної множини A: | ?(A)| > |A|.
Доведення. Оскільки існує тривіальна взаємно однозначна відповідність f між множиною A і підмножиною множини ?(A): f = { (a,{a}) | a?A, {a}??(A)}, то достатньо довести, що множини A і ? (A) нерівнопотужні.
Доведення проведемо від супротивного. Припустимо, що існує взаємно однозначна відповідність g між множинами A і ?(A): g = { (b,B) | b?A і B??(A)}. У кожній парі відповідності перша координата b - це елемент множини A, а друга координата B - деяка підмножина множини A. Тому для кожної пари (b,B)?g виконується одне з двох співвідношень: або b?B, або b?B. Побудуємо нову множину K = { b | b?A і b?B для (b,B)?g }.
З того, що ??? (A) випливає, що K ??.
Оскільки K є підмножиною множини A (K??(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 і ?(A). Таким чином, |A| < | ? (A)|.
Наслідок 1.9.1. Не існує множини, яка має найбільшу потужність, тобто не існує найбільшого кардинального числа.
Справді, розглянувши множини N, ?(N), ?(?(N)),..., одержимо нескінченно зростаючу послідовність відповідних кардинальних чисел ?0 ,?1 =2?0,?2 =2?1, ...
На закінчення зупинимось ще на одній цікавій класичній проблемі теорії множин, сформульованій ще у 1884 році Г.Кантором:
гіпотеза континуума, яка стверджує, що не існує множини, кардинальне число ? якої розташоване між ?0 і ?1, тобто ?0 < ? < ?1.
Ця гіпотеза припускає узагальнення, яке носить назву узагальненої гіпотези континуума:
для довільного кардинального числа ? деякої нескінченної множини з нерівності ? ' > ? для будь-якого кардинального числа ? ' випливає ? ' > 2?.
Проблему гіпотези континуума майже вісім десятків років намагалися розв’язати найкращі математики світу. I лише у 1963 році тридцятирічний американський математик Пол Коен довів, що гіпотезу континуума не можна ні довести, ні спростувати, виходячи з аксіом теорії множин. Отже, прийняття або відхилення гіпотези континуума є однаково законними, що веде до можливості побудови двох різних несуперечливих теорій множин.