Кардинальні числа

Нехай A - деяка множина і S = { B | B ~ A} - сукупність усіх множин, рівнопотужних множині A. Очевидно, що всі множини з S рівнопотужні. Кардинальним числом (позначається |A|, або 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.... При цьому виконуються такі співвідношення: