Множини і відношення, Детальна інформація

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, то справедливість теореми очевидна.

Нехай 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(....

Неважко переконатись, що