Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Teoria mocy

Zadaniem teorii mocy, do której wstęp znajdą państwo w tym wykładzie, będzie uogólnienie pojęcia ilości elementów zbioru. Dla zbiorów skończonych powołaliśmy do życia liczby naturalne (patrz Wykład 7), przy pomocy których możemy rachować i opisywać ilościowe własności innych zbiorów. Niestety to nam nie wystarcza. Są zbiory, których liczbę elementów nie sposób opisać żadną liczbą naturalną. Zgodziliśmy się wszak, przyjmując aksjomat nieskończoności, na istnienie takich niezwykłych zbiorów . Aksjomat ten wraz z innymi, na przykład, aksjomatem zbioru potęgowego, będzie miał dla nas wiele niespodzianek. Powołamy do życia zbiory nieskończone, a co więcej pokażemy, że istnieją różne rodzaje nieskończoności. Jedne zbiory nieskończone będą bardziej nieskończone od innych. Aby umieć porównywać liczby elementów zbiorów nieskończonych, wprowadzimy podstawowe definicje. Z punktu widzenia tych definicji na całą teorię mocy można patrzeć jak na teorie bijekcji i iniekcji (lub dualnie surjekcji - patrz wykład 11, ćwiczenie 3.1).

Definicja 1.1

Zbiory i nazywamy równolicznymi, gdy istnieje bijekcja . Równoliczność zbiorów oznaczamy przez .

ma podobne własności do relacji równoważności.

Twierdzenie 1.2

Równoliczność ma własności:

  1. .
  2. jeżeli , to .
  3. jeżeli i , to .

Trywialne dowody tych faktów pozostawimy jako ćwiczenia.


Ćwiczenie 1.3

Udowodnij własności 1, 2, 3. z Twierdzenia 1.2.


Rozwiązanie

Twierdzenie 1.4

Podstawowe własności relacji równoliczności:

  1. i oraz , to .
  2. i , to .
  3. .
  4. .
  5. Gdy , to .
  6. .

Znowu dowody twierdzeń z 1.4 podamy jako ćwiczenia.


Ćwiczenie 1.5

Dowiedź Twierdzenia 1.4.


Wskazówka


Rozwiązanie

Definicja 1.6

Zbiór nazywamy skończonym, gdy , dla pewnej liczby naturalnej .

Zbiór nazywamy nieskończonym, gdy nie jest skończony.

Jako zadania podamy dwa następujące proste fakty:

Ćwiczenie 1.7

Podzbiór zbioru skończonego jest skończony. Obraz przez funkcje zbioru skończonego jest skończony.


Wskazówka


Rozwiązanie

Podamy twierdzenie, podobne do twierdzenia, które zobaczą państwo w wykładzie 11 (patrz Wykład 11, Twierdzenie 4.1). Wersja ogólniejsza będzie dotyczyła sytuacji, kiedy zbiór jest nieskończony, ale niekoniecznie jest podzbiorem . W takim wypadku do dowodu tego twierdzenia będzie potrzebny aksjomat wyboru. W uproszczonej wersji, która podana jest poniżej, aksjomat ten nie będzie nam potrzebny.

Twierdzenie 1.8

Jeżeli jest nieskończonym podzbiorem , to .

Dowód

Przy pomocy definiowania przez indukcję (patrz Wykład 7, Twierdzenie 6.1), zbudujmy bijekcję pomiędzy zbiorem a . Zbiór będąc nieskończonym jest niepusty, więc z zasady minimum (patrz Wykład 7, Twierdzenie 5.2) posiada element najmniejszy. Niech:

najmniejszy element w


najmniejszy element, który w jest istotnie większy niż .


Łatwo zauważyć, że dla obraz, dowolnej liczby naturalnej jest odcinkiem początkowym . Równocześnie, na mocy poprzedniego ćwiczenia, wiemy, że obraz ten jest skończony. Ponieważ zbiór jest nieskończony, więc zawsze istnieją w nim elementy poza . Elementy te muszą być większe od , co gwarantuje, że funkcja jest zdefiniowana dla całego . Funkcja jest oczywiście iniekcją, ponieważ dla mamy . Funkcja jest bijekcją, ponieważ łatwo możemy pokazać, że jeśli , to .

End of proof.gif

Zbiory przeliczalne

Podamy poniżej dwie równoważne, jak się okaże, definicje przeliczalności.

Definicja 2.1

Zbiór jest przeliczalny, gdy , dla pewnego .

Definicja 2.2

Zbiór daje się ustawić w ciąg, gdy istnieje surjekcja .

Twierdzenie 2.3

Niepusty zbiór daje się ustawić w ciąg wtedy i tylko wtedy, gdy jest przeliczalny.

Dowód

Jeśli jest przeliczalny przy bijekcji , to niewątpliwie daje się ustawić w ciąg - uzupełniamy bijekcje jednym elementem wyjętym z niepustego . Jeśli daje sie ustawić w ciąg przy użyciu funkcji , to z surjektywności mamy, że jest niepusty dla każdego . Zdefiniujmy funkcje jako . Funkcja ta wybiera najmniejsze elementy z przeciwobrazów elementów , jest zatem iniekcją, a więc bijekcja pomiędzy a podzbiorem .

End of proof.gif

Znowu, tak jak w przypadku Twierdzenia 1.8, radziłbym zapoznać sie z wykładem 11 (patrz Wykład 11) dotyczącym aksjomatu wyboru i jego konsekwencji. W szczególności pożyteczne byłoby przeczytanie podrozdziału 3.1 Twierdzenia dotyczące zbiorów i zawartego w nim Ćwiczenia 3.1. Znajdą tam państwo uogólnienie poprzedniego twierdzenia na sytuacje, gdzie nie zakłada się przeliczalności zbioru .

Twierdzenie 2.4

jest przeliczalny wtedy i tylko wtedy, gdy jest skończony lub równoliczny z .

Proponuję dowód wykonać jako proste ćwiczenie.


Ćwiczenie 2.5

Dowiedź Twierdzenia 2.4.


Wskazówka


Rozwiązanie

Lemat 2.6

Własności zbiorów przeliczalnych:

  1. Podzbiór przeliczalnego zbioru jest przeliczalny.
  2. Suma zbiorów przeliczalnych jest przeliczalna.
  3. jest przeliczalny.
  4. Iloczyn kartezjański zbiorów przeliczalnych jest przeliczalny.
  5. dla jest przeliczalny.
  6. Niech będzie skończoną rodziną zbiorów przeliczalnych. Wtedy jest przeliczalny.
  7. Jeżeli przeliczalny oraz jest rozkładem, to jest przeliczalny.

Twierdzenie jest proste i dlatego proponuję wykonać dowody samodzielnie jako ćwiczenie.

Ćwiczenie 2.7

Dowiedź Lematu 2.6.

Wskazówka


Rozwiązanie

Twierdzenie 2.8

Zbiory liczb całkowitych i wymiernych są przeliczalne.

Dowód

Jest to prosta konsekwencja punktu 7 Lematu 2.6. Zbiór oraz zbiór są rozkładami zbiorów przeliczalnych.

End of proof.gif

Dla kontrastu udowodnimy, że zbiór liczb rzeczywistych przeliczalny nie jest.

Twierdzenie 2.9 [Cantora]

Zbiór liczb rzeczywistych nie jest przeliczalny.

Dowód

Podany poniżej dowód pochodzi od Georga Cantora. Pokażemy, że odcinek liczb rzeczywistych nie jest przeliczalny. Cały zbiór jako większy też nie może być przeliczalny. Dla dowodu niewprost przypuśćmy, że jest przeciwnie. Załóżmy zatem, że istnieje surjektywny ciąg . Zdefiniujemy indukcyjnie dwa ciągi punktów i odcinka o własności tak, aby -ty element ciągu nie należał do odcinka domkniętego . Tak więc kładziemy początkowo i . Przypuśćmy, że zdefiniowane są już obydwa ciągi, dla . Odcinek dzielimy na trzy równe części i za i wybieramy końce tego spośród nich, do którego nie należy element ciągu .

Jako ćwiczenie podamy sprawdzenie następujących własności ciągów i :

  1. Ciąg jest słabo rosnący, czyli .
  2. Ciąg jest słabo malejący, czyli .
  3. .
  4. .
  5. .

Własności te implikują fakt, że zarówno jak i są ciągami Cauchy'ego; jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista zadana jednocześnie przez aproksymacje i , czyli . Ze względu na na 1. i 2. , dla każdego . To przeczy samej definicji wybierania odcinków, którą przeprowadzono tak, by elementy ciągu nie leżały w żadnym z nich. Zatem nie mógł być surjekcją.

End of proof.gif

Podamy poniżej definicje nierówności na mocach zbiorów.

Definicja 2.10

wtw istnieje iniekcja .

wtw i nieprawda, że .

Twierdzenie 2.11

Następujące warunki są równoważne:

  1. Dla dowolnych zbiorów zachodzi i , to .
  2. Dla dowolnych zbiorów zachodzi i , to .
  3. Dla dowolnych zbiorów zachodzi i , to .

Dowód

. Niech i . Niech iniekcja oraz niech . Mamy więc oraz . Stosując do , otrzymujemy , co wobec daje .

. Z założeń (3) mamy, że i . Można je osłabić, otrzymując i . Z przechodniości (co odpowiada składaniu iniekcji) otrzymujemy . Pozostaje dowieść, że nieprawdą jest . Gdyby , to mielibyśmy . Stosując dla , mielibyśmy , co przeczy .

. Niech i , co daje też . Gdyby nieprawdą było, że , to mielibyśmy zarówno jak i , co na mocy dawałoby sprzeczność .

End of proof.gif

W twierdzeniu powyżej pokazaliśmy równoważność trzech warunków, nie pokazując, czy którykolwiek z nich jest prawdziwy. Teraz pokażemy . Twierdzenie to znane jest pod nazwą twierdzenia Cantora-Bernsteina. Zatem twierdzenie to wyraża słabą antysymetrię relacji porządku na mocach zbiorów. Zobaczymy, że jest ono niezwykle przydatne do uzasadnienia wielu faktów teorii mocy, co bez tego twierdzenia często pociągałoby konieczność przeprowadzania długich i skomplikowanych dowodów.

Twierdzenie 2.12 [Cantora - Bernsteina]

Jeżeli i to .

Dowód

Przygotowania do tego dowodu zostały podjęte wcześniej. Służył do tego Wykład 6 poświęcony między innymi obrazom zbiorów przez funkcje. Nietrywialnym było dowiedzenie twierdzenia Knastera-Tarskiego, a przy jego pomocy lematu Banacha. Ten wysiłek zwróci się nam teraz (patrz Wykład 6). Niech zatem i będą iniekcjami. Na mocy lematu Banacha (patrz Wykład 6, Lemat Banacha), istnieją rozłączne zbiory wzajemnie uzupełniające się do jak i rozłączne zbiory wzajemnie uzupełniające się do takie, że i symetrycznie . Możemy zatem na rozłącznych zbiorach skleić dwie iniekcje i będące zawężeniami oryginalnych funkcji. Otrzymane sklejenie jest bijekcją.

End of proof.gif

Poniżej poznamy twierdzenie pochodzące od Cantora, pokazujące, że można budować zbiory o dowolnie wielkiej mocy. Z niego i z twierdzenia Cantora-Bernstaina pokażemy, że zbiorów jest tak dużo, że same nie tworzą zbioru. Fakt ten jest już nam znany (patrz Wykład 4, Fakt 10.1) i jest konsekwencja aksjomatu regularności. Niemniej przeprowadzimy prosty dowód, odwołujący się do faktów z teorii mocy. Dowód poniższy jest dowodem przekątniowym. W wykładach dotyczących teorii obliczeń i logiki znajdą państwo wiele takich dowodów.

Twierdzenie 2.13 [Cantora]

.

Dowód

Łatwo zauważyć, że istnieje iniekcja wkładająca w . Przykładowo możemy wziąć funkcje przypisującą elementowi zbioru singleton . Załóżmy, że istnieje bijekcja . Obrazami elementów ze zbioru są podzbiory . Utwórzmy zbiór . Ze względu na surjektywność musi istnieć taki element , że . Rozstrzygnijmy problem, czy . Jeżeli tak, to , a zatem sprzeczność. Jeżeli nie to, , a zatem , czyli sprzeczność.

End of proof.gif

Twierdzenie 2.14 [Cantora]

Nie istnieje zbiór wszystkich zbiorów.

Dowód

Gdyby taki zbiór istniał, mielibyśmy trudności z przypisaniem mu mocy. Mianowicie, niech ten zbiór nazywa się . W takim razie , bo każdy podzbiór jest zbiorem. Trywialnie mamy w drugą stronę . Zatem z twierdzenia Cantora-Bernsteina otrzymujemy , co jest sprzeczne z twierdzeniem Cantora.

End of proof.gif

Twierdzenie 2.15

Każdy zbiór nieskończony zawiera podzbiór przeliczalny równoliczny z .

Dowód

Dowód tego bardzo intuicyjnego faktu odwołuje się do aksjomatu wyboru. Proszę o zapoznanie się z dowodem tego twierdzenia w wykładzie 11, Twierdzenie 4.1, oraz o zapoznanie się z innymi faktami tego rozdziału, które wymagają aksjomatu wyboru (patrz Wykład 11, Twierdzenie 4.1).

End of proof.gif

Zbiory mocy continuum

Definicja 3.1

Zbiór nazywamy nieprzeliczalnym, gdy nie jest przeliczalny.

Ćwiczenie 3.2

Zbiory oraz nie są przeliczalne.


Wskazówka


Rozwiązanie

Definicja 3.3

Mówimy, że zbiór jest mocy continuum, gdy jest równoliczny z .

Lemat 3.4

Każdy przedział obustronnie otwarty jest mocy continuum.

Dowód

Na początku pokażemy, że istnieje bijekcja pomiędzy przedziałem otwartym liczb rzeczywistych a . Bijekcją taką jest . (Jako ćwiczenie spróbuj narysować wykres tej funkcji.) Następnie łatwo zauważyć, że każde dwa przedziały otwarte są równoliczne. (Jako ćwiczenie napisz wzór na funkcję liniową pomiędzy dwoma zadanymi otwartymi przedziałami.)

End of proof.gif

Lemat 3.5

Jeżeli i zawiera pewien przedział otwarty, to jest mocy continuum.

Dowód

Następne dwa lematy pokazują, że zbiory mocy kontinuum są odporne na dodawanie i ujmowanie zbiorów przeliczalnych. Po każdej takiej operacji moc zbioru jest taka, jak była. Proszę o zapoznanie się z prostymi dowodami tych lematów. Może to być pomocne w rozwiązywaniu zadań.

Lemat 3.6

Jeżeli jest przeliczalnym podzbiorem zbioru mocy continuum, to

jest mocy continuum.

Dowód

Załóżmy bez straty ogólności, że . Zauważmy, że jest nieprzeliczalny. Inaczej przeczyłoby to Twierdzeniu 2.9 o nieprzeliczalności . W takim razie jest nieskończony. Można zatem odnaleźć w nim na mocy Twierdzenia 2.15 (stosując aksjomat wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, patrz Wykład 11, Twierdzenie 4.1) nieskończony zbiór przeliczalny . Mamy więc jest nieskończonym zbiorem przeliczalnym. Istnieje zatem bijekcja . Mając ją, możemy określić bijekcję następująco:

End of proof.gif

Lemat 3.7

Jeżeli jest przeliczalnym, a jest mocy continuum, to jest mocy continuum.

Dowód

Opiszmy słowami dowód podobny do poprzedniego. Na początku należy odnaleźć w zbiór nieskończony przeliczalny . Zbiór ten musi być równoliczny z . W takim razie można bijektywnie schować zbiór w zbiorze . Następnie należy zdefiniować bijekcję między a tak, aby na fragmencie z poza była identycznością, a na była poprzednią bijekcją. Sklejenie takich bijekcji na zbiorach rozłącznych jest bijekcją.

End of proof.gif

Twierdzenie poniższe będzie mieć dla nas fundamentalne znaczenie. Porównuje ono moc dwóch podstawowych dla nas zbiorów i . Do dowodu posłużymy się konstrukcją rozwinięcia dwójkowego przeprowadzonego w Twierdzeniu 3.15 z Wykładu 8 (patrz Wykład 8, Twierdzenie 3.15 ). Twierdzenie 3.18 tego rozdziału pokazuje bijekcje pomiędzy pewnymi specjalnymi ciągami ze zbioru a przedziałem . Przed przeczytaniem tego dowodu zapoznaj sie z Twierdzeniami 3.15, 3.17, 3.18 z Wykładu 8 (patrz Wykład 8).

Twierdzenie 3.8

jest mocy continuum.

Dowód

Zbiór rozbijmy na dwa rozłączne podzbiory. Zbiór taki, jak w Twierdzeniu 3.18 wykładu 8 to znaczy oraz zbiór będący jego uzupełnieniem. Łatwo zauważyć, że jest przeliczalny, bo można go przedstawić jako przeliczalną sumę zbiorów skończonych. składa się z ciągów, które od pewnego miejsca są stale równe . Zauważmy, że jest jedynie takich ciągów, które od miejsca są stale równe . Zbiór , jak pokazaliśmy w Twierdzeniu 3.18 w wykładzie 8, jest równoliczny z przedziałem , a więc przeliczalny. Nasz zbiór jako suma zbioru continuum i przeliczalnego na mocy Lematu 3.7 jest mocy continuum.

End of proof.gif

Twierdzenie 3.9

Rodzi się naturalne pytanie. Czy istnieje taki zbiór, którego moc dałoby się ulokować pomiędzy mocą zbioru liczb naturalnych a mocą continuum. Czyli, czy istnieje takie, że

Cantor przypuszczał, że takiego zbioru (mocy) nie ma i że następnym w hierarchii mocy zbiorem po jest . Przypuszczenie Cantora nazywa się hipotezą continuum. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 Kurt Gödel pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w hipotezie kontinuum istnieje i nie doprowadzi to teorii mnogości do sprzeczności, o ile sama nie jest sprzeczna. W roku 1963 Paul Joseph Cohen pokazał niezależność hipotezy continuum od aksjomatów teorii mnogości. Oznacza to, że nie można hipotezy udowodnić na gruncie tej teorii, ale nie można też udowodnić jej zaprzeczenia.

Na koniec podamy jako ćwiczenie inną bardzo elegancką i nieodwołującą się do pojęcia liczb naturalnych definicję nieskończoności.

Definicja 3.10

(definicja nieskończoności Dedekinda) Zbiór jest nieskończony w sensie Dedekinda, gdy istnieje podzbiór właściwy zbioru , który jest z nim równoliczny. Zbiór jest skończony, w sensie Dedekinda, jeśli nie jest nieskończony w sensie Dedekinda.


Ćwiczenie 3.11

Pokaż, że zbiór jest nieskończony wtedy i tylko wtedy, gdy jest nieskończony w sensie Dedekinda.


Wskazówka


Wskazówka


Rozwiązanie

Ćwiczenia

Ćwiczenie 4.1

Wykaż, że jest równoliczne z .


Rozwiązanie


Ćwiczenie 4.2

Wykaż, że


Rozwiązanie


Ćwiczenie 4.3

Jakiej mocy może być zbiór punktów nieciągłości silnie rosnącej funkcji z do ?


Wskazówka


Rozwiązanie


Ćwiczenie 4.4

Jaka jest moc zbioru wszystkich silnie rosnących funkcji z w ?


Rozwiązanie


Ćwiczenie 4.5

Czy na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną?


Rozwiązanie


Ćwiczenie 4.6

Zbiór nazywamy wypukłym, jeśli dla dowolnych , jeśli i , to . Ile jest zbiorów wypukłych w ?


Rozwiązanie


Ćwiczenie 4.7

Ile elementów posiada największy, pod względem mocy, łańcuch w ?


Rozwiązanie


Ćwiczenie 4.8

Jaka jest moc zbioru bijekcji z do ?


Rozwiązanie


Ćwiczenie 4.9

Jakiej mocy jest zbiór porządków na , które są równocześnie funkcjami ?


Rozwiązanie


Ćwiczenie 4.10

Dowolna rodzina taka, że dla dowolnych dwóch różnych elementów ich przecięcie jest co najwyżej jednoelementowe, jest przeliczalna.


Rozwiązanie