- •Потужність множин
- •Як ми рахуємо....
- •Еквівалентні множини
- •Скінченні, зліченні, континуальні
- •Лема. Об’єнання зліченної та не більш ніж зліченної множин – є множина зліченна
- •Лема: Декартов квадрат зліченної множини є множина зліченна
- •Лема про зліченну підмножину
- •Лема про нескінченну підмножину
- •Лема про раціональні числа
- •Лема про об’єднання
- •Наслідки леми про об'єднання
- •Теорема про дійсні числа
- •Властивості континуальних множин
- •Потужність множин
- •Теорема Кантора
- •Доведення теореми Кантора
- •Теорема Кантора-Бернштейна
- •Доведення теореми Кантора-Бернштейна
- •Доведення теореми Кантора-Бернштейна
- •Продовження теореми
- •Наслідок теореми Кантора-Бернштейна
- •Континуум гіпотеза
- •Континуум гіпотеза
- •Континуум гіпотеза
Наслідки леми про об'єднання
[0,1] (0,1) [0,1] (0,1) {0,1}
Множина дійсних чисел еквівалентна множині всіх нескінчених цифрових послідовностей
(d1 , d 2 , d 3 , . . . )
(0,1) (0,1) (d1, d2 , d3 ,...) {(0, d1d2d3...)}
0,5(0) 0, 4(9) {0, d1d2d3...(9)} R
R нескінч. підмножина злічен. множини рац. чисел
(0,1) лема про об 'єднання (0,1) R
(0,1) R (d1, d2 , d3 ,...)
11
Теорема про дійсні числа
Множина дійсних чисел не є зліченною
r1,r2,r3,...rn,...
r1 |
|
(d1 |
, d1 |
, d1 |
,...) |
r2 |
|
1 |
2 |
3 |
|
|
(d12 |
, d22 |
, d32 ,...) |
.... .... |
..................... |
|
r |
(d1k , d2k , d3k ,...) |
|
k |
|
|
.... .... |
..................... |
ri (d1i , d2i ,...)
b (b1 ,b2 ,b3 ,...)
|
якщо |
k |
0 |
0 |
dk |
||
bk |
якщо |
dkk 0 |
|
1 |
|||
k b d k |
|
|
|
k |
k |
|
12 |
|
|
|
Властивості континуальних множин
A, B - континуальні
A B, A B, An континуальні
A (0;1), B (0;1) (1;2) A B (0;1) (1;2) лема про об єднання(0;1) {1} (1;2)(0;2) (0;1)
A×B={(a,b)} a=(a1,a2,…) b=(b1,b2,…)
ai,bi {0;1;2;…8;9} (a,b) (a1,b1,a2,b2,…) 13
Потужність множин
А |A|
|A|=|B| A B; | |=0; |{1,2,….n}|=n Потужність множини А менша або дорівнює потужності множини В
|A| |B| A B1 B Потужність множини А строго менша
потужності множини В |A| |B| A B1 B, A × B
14
Теорема Кантора
Потужність множини А строго менша за потужність множини(системи)
всіх підмножин множини А
|A| |B(A)|
a {a} - одноелементній підмножині A |
|
A {{a}} aA- множині всіх |
|
одноелементних підмножин A, |
|
A {{a}}aA B(A), |
|
значить |A| |B(A)| |
15 |
|
Доведення теореми Кантора
Припустимо, що A↔B(A)
Існує бієкція :a (a) A |
|
M={ a A a (a) } |
|
M A -1(M) = a0 |
|
M= (a0), a0 A |
|
Для a0 та M можливі 2 випадки: |
|
або a0 M, або a0 M |
|
a0 M = (a0) a0 M |
|
a0 M = (a0) a0 M |
16 |
|
Теорема Кантора-Бернштейна
Якщо
множина A еквівалентна підмножині B1 множини B, а множина B еквівалентна підмножині A1 множини A, то
множини A та B еквівалентні між собою.
A↔B1 B, B↔A1 A A↔B
|A| |B|, |B| |A| |A|=|B|
17
Доведення теореми Кантора-Бернштейна
Нехай f:A B1 та g:B A1 – бієкції між
відповідними множинами Позначимо A0=A, B0=B,
за умовою теореми f(A0)=B1, g(B0)=A1, і далі f(A1)=B2, g(B1)=A2, f(A2)=B3, g(B2)=A3, і т.д.
f(Aі)=Bі+1, g(Bі)=Aі+1
Випишемо послідовність перетворень множин A0 та B0 бієкціями f та g
A0 |
B1 |
A2 |
B3 |
|
A4 |
|
B5 |
|
A6 |
|
….. |
|
|
f |
g |
f |
g |
|
f |
|
g |
|
f |
|
|
A |
f B |
g A |
f B |
g A |
f B |
g A |
f ….. |
18 |
||||
0 |
0 |
1 |
2 |
|
3 |
|
4 |
|
5 |
|
|
Тобто A A , A A , A A , …….
Доведення теореми Кантора-Бернштейна
Ці ж послідовності можна виписати інакше:
B |
g A |
f B |
g A |
f B |
g A |
f B |
g ….. (1) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
|
|
|
A |
f B |
g A |
f B |
g A |
f B |
g ….. (2) |
|
0 |
1 |
2 |
3 |
4 |
5 |
|
Звідси маємо:
A0 A1, A2 A3, A4 A5, …….
об‘єднуючи з попереднім: A1 A2, A3 A4, A5 A6, …….
маємо: A0 A1 A2 A3 A4 A5 A6 A7 ………………………
Оскільки f та g бієкції, то всі множини в рядку (1) еквівалентні між собою, так
само і в рядку (2): Ak Ak+2
19
A4\A5
A3\A4
A2\A3
A1\A2
A0\A1
Продовження теореми Кантора-Бернштейна
A0 A1 A2 …… Ak Ak+1 …..
D= Ak
A0 |
A1 |
A |
2 |
A |
A |
4 |
A |
5 |
D |
|
|
|
3 |
|
|
|
20