Logika i teoria mnogości/Wykład 9: Teoria mocy twierdzenie Cantora-Bernsteina, twierdzenie Cantora. Zbiory przeliczalne, zbiory mocy kontinuum: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 516: Linia 516:
 
}}
 
}}
  
==Zbiory mocy kontinuum==
+
==Zbiory mocy continuum==
  
 
{{definicja|3.1||
 
{{definicja|3.1||
  
Zbiór nazywamy  nieprzeliczalnym gdy nie jest przeliczalny.
+
Zbiór nazywamy  nieprzeliczalnym, gdy nie jest przeliczalny.
  
 
}}
 
}}
Linia 534: Linia 534:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
 
 
Dowód należy poprowadzić niewprost stosując metodę przekątniową. W pierwszym
+
Dowód należy poprowadzić niewprost, stosując metodę przekątniową. W pierwszym
 
przypadku rozważyć bijekcje <math>\displaystyle f: \mathbb N \rightarrow 2^\mathbb N</math>. Przy jej pomocy zbudować ciąg <math>\displaystyle g:
 
przypadku rozważyć bijekcje <math>\displaystyle f: \mathbb N \rightarrow 2^\mathbb N</math>. Przy jej pomocy zbudować ciąg <math>\displaystyle g:
 
\mathbb N \rightarrow \mathbb N</math> zadany wzorem <math>\displaystyle g(i) = 1- f(i)(i)</math>. Drugi fakt wynika z pierwszego.
 
\mathbb N \rightarrow \mathbb N</math> zadany wzorem <math>\displaystyle g(i) = 1- f(i)(i)</math>. Drugi fakt wynika z pierwszego.
Gdyby dowodzić go niezależnie należy tak jak poprzednio dla bijekcji <math>\displaystyle h:\mathbb N \rightarrow
+
Gdyby dowodzić go niezależnie, należy tak jak poprzednio dla bijekcji <math>\displaystyle h:\mathbb N \rightarrow
 
\mathbb N^\mathbb N</math> rozważyć przykładowo funkcje <math>\displaystyle n \rightarrow h(n)(n)+1</math>.
 
\mathbb N^\mathbb N</math> rozważyć przykładowo funkcje <math>\displaystyle n \rightarrow h(n)(n)+1</math>.
  
Linia 546: Linia 546:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
 
Dla dowodu niewprost ustalmy surjekcję <math>\displaystyle f:\mathbb{N} \rightarrow 2^{\mathbb{N}}</math>. Zdefiniujmy specjalny element zbioru <math>\displaystyle 2^{\mathbb{N}}</math> w następujący sposób
+
Dla dowodu niewprost ustalmy surjekcję <math>\displaystyle f:\mathbb{N} \rightarrow 2^{\mathbb{N}}</math>. Zdefiniujmy specjalny element zbioru <math>\displaystyle 2^{\mathbb{N}}</math> w następujący sposób:
  
<center><math>\displaystyle g(n) = \begin{cases} 0& \mbox{ jeśli }\displaystyle f(n)(n) = 1 \\
+
<center><math>\displaystyle g(n) = \begin{cases} 0,& \mbox{ jeśli }\displaystyle f(n)(n) = 1, \\
1& \mbox{ jeśli }\displaystyle  f(n)(n) =0.\end{cases}</math></center>
+
1,& \mbox{ jeśli }\displaystyle  f(n)(n) =0.\end{cases}</math></center>
  
Funkcja <math>\displaystyle g</math> różni się od obrazu liczby <math>\displaystyle n</math> względem <math>\displaystyle f</math> na <math>\displaystyle n</math>-tym miejscu. Ponieważ <math>\displaystyle f</math> jest bijekcją, to istnieje <math>\displaystyle n_0</math> takie, że <math>\displaystyle f(n_0)=g</math>, czyli <math>\displaystyle f(n_0)(n) = g(n)</math> dla każdego <math>\displaystyle n</math>. Z definicji <math>\displaystyle g</math> wynika, że <math>\displaystyle g(n_0)\neq f(n_0)(n_0)</math> co daje oczekiwaną sprzeczność.
+
Funkcja <math>\displaystyle g</math> różni się od obrazu liczby <math>\displaystyle n</math> względem <math>\displaystyle f</math> na <math>\displaystyle n</math>-tym miejscu. Ponieważ <math>\displaystyle f</math> jest bijekcją, to istnieje <math>\displaystyle n_0</math> takie, że <math>\displaystyle f(n_0)=g</math>, czyli <math>\displaystyle f(n_0)(n) = g(n)</math>, dla każdego <math>\displaystyle n</math>. Z definicji <math>\displaystyle g</math> wynika, że <math>\displaystyle g(n_0)\neq f(n_0)(n_0)</math>, co daje oczekiwaną sprzeczność.
  
Gdyby istniała surjekcja <math>\displaystyle f</math> z <math>\displaystyle \mathbb{N}</math> w <math>\displaystyle \mathbb{N}^{\mathbb{N}}</math> to możemy zdefiniować <math>\displaystyle g</math> jako
+
Gdyby istniała surjekcja <math>\displaystyle f</math> z <math>\displaystyle \mathbb{N}</math> w <math>\displaystyle \mathbb{N}^{\mathbb{N}}</math>, to możemy zdefiniować <math>\displaystyle g</math> jako:
  
<center><math>\displaystyle g(n) = \begin{cases} f(n)& \mbox{ jeśli } \overrightarrow{f(n)} (\mathbb{N})\subset 2\\ z& \mbox { w przeciwnym przypadku } \displaystyle \end{cases}</math></center>
+
<center><math>\displaystyle g(n) = \begin{cases} f(n),& \mbox{ jeśli } \overrightarrow{f(n)} (\mathbb{N})\subset 2,\\ z,& \mbox { w przeciwnym przypadku, } \displaystyle \end{cases}</math></center>
  
gdzie <math>\displaystyle z:\mathbb{N} \rightarrow 2</math> jest funkcją stale równą zero. Funkcja <math>\displaystyle g</math> jest surjekcją z <math>\displaystyle \mathbb{N}</math> na <math>\displaystyle 2^{\mathbb{N}}</math> co jest sprzecznością z poprzednim faktem.
+
gdzie <math>\displaystyle z:\mathbb{N} \rightarrow 2</math> jest funkcją stale równą zero. Funkcja <math>\displaystyle g</math> jest surjekcją z <math>\displaystyle \mathbb{N}</math> na <math>\displaystyle 2^{\mathbb{N}}</math>, co jest sprzecznością z poprzednim faktem.
 
</div></div>
 
</div></div>
  
 
{{definicja|3.3||
 
{{definicja|3.3||
Mówimy że zbiór jest mocy continuum gdy jest równoliczny z <math>\displaystyle \mathbb{R}</math>.
+
Mówimy, że zbiór jest mocy continuum, gdy jest równoliczny z <math>\displaystyle \mathbb{R}</math>.
 
}}
 
}}
  
Linia 573: Linia 573:
 
rzeczywistych <math>\displaystyle (-1,1)</math> a <math>\displaystyle \mathbb R</math>. Bijekcją taką jest <math>\displaystyle x\rightarrow \frac{x}{1-x^2}</math>. (Jako
 
rzeczywistych <math>\displaystyle (-1,1)</math> a <math>\displaystyle \mathbb R</math>. Bijekcją taką jest <math>\displaystyle x\rightarrow \frac{x}{1-x^2}</math>. (Jako
 
ćwiczenie spróbuj narysować wykres tej funkcji.) Następnie łatwo zauważyć, że każde
 
ć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 funkcje liniową
+
dwa przedziały otwarte są równoliczne. (Jako ćwiczenie napisz wzór na funkcję liniową
 
pomiędzy dwoma zadanymi otwartymi przedziałami.)  
 
pomiędzy dwoma zadanymi otwartymi przedziałami.)  
 
}}
 
}}
Linia 579: Linia 579:
 
{{lemat|3.5||
 
{{lemat|3.5||
 
Jeżeli <math>\displaystyle A \subset \mathbb{R}</math>
 
Jeżeli <math>\displaystyle A \subset \mathbb{R}</math>
i <math>\displaystyle A</math> zawiera pewien przedział otwarty to <math>\displaystyle A</math> jest mocy continuum.
+
i <math>\displaystyle A</math> zawiera pewien przedział otwarty, to <math>\displaystyle A</math> jest mocy continuum.
 
}}
 
}}
  
 
{{dowod|||
 
{{dowod|||
Prosta konsekwencja [[#twierdzenie_2_12|Twierdzenia 2.12 Cantora-Bernsteina]]
+
Prosta konsekwencja [[#twierdzenie_2_12|Twierdzenia 2.12 Cantora-Bernsteina.]]
 
}}
 
}}
  
 
Następne dwa lematy pokazują, że zbiory mocy kontinuum są odporne na dodawanie i
 
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
+
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
 
była. Proszę o zapoznanie się z prostymi dowodami tych lematów. Może to być pomocne w
 
rozwiązywaniu zadań.
 
rozwiązywaniu zadań.
Linia 593: Linia 593:
 
{{lemat|3.6||
 
{{lemat|3.6||
 
Jeżeli <math>\displaystyle B \subset
 
Jeżeli <math>\displaystyle B \subset
A</math> jest przeliczalnym podzbiorem zbioru <math>\displaystyle A</math> mocy continuum to
+
A</math> jest przeliczalnym podzbiorem zbioru <math>\displaystyle A</math> mocy continuum, to
<math>\displaystyle A \setminus B</math> jest mocy continuum }}
+
<math>\displaystyle A \setminus B</math> jest mocy continuum.}}
  
 
{{dowod|||
 
{{dowod|||
Linia 600: Linia 600:
 
nieprzeliczalny. Inaczej przeczyłoby to [[#twierdzenie_2_9|Twierdzeniu 2.9]] o
 
nieprzeliczalny. Inaczej przeczyłoby to [[#twierdzenie_2_9|Twierdzeniu 2.9]] o
 
nieprzeliczalności <math>\displaystyle \mathbb R</math>. W takim razie <math>\displaystyle A \setminus B</math> jest nieskończony. Można
 
nieprzeliczalności <math>\displaystyle \mathbb R</math>. W takim razie <math>\displaystyle A \setminus B</math> jest nieskończony. Można
zatem odnaleźć w nim na mocy twierdzenia [[#twierdzenie_2_15|Twierdzeniu 2.15]] (stosując aksjomat
+
zatem odnaleźć w nim na mocy [[#twierdzenie_2_15|Twierdzenia 2.15]] (stosując aksjomat
wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, rozdział 4,
+
wyboru, zapoznaj się z dowodem tego twierdzenie w wykładzie 11, patrz  [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady#twierdzenie_4_1|Wykład 11, Twierdzenie 4.1]]) nieskończony zbiór przeliczalny <math>\displaystyle B'</math>. Mamy więc <math>\displaystyle B \cup B'</math> jest
twierdzenie 4.1) nieskończony zbiór przeliczalny <math>\displaystyle B'</math>. Mamy więc <math>\displaystyle B \cup B'</math> jest
 
 
nieskończonym zbiorem przeliczalnym. Istnieje zatem bijekcja <math>\displaystyle f: B \cup B' \rightarrow B'</math>.
 
nieskończonym zbiorem przeliczalnym. Istnieje zatem bijekcja <math>\displaystyle f: B \cup B' \rightarrow B'</math>.
Mając ją możemy określić bijekcje <math>\displaystyle h: A \rightarrow A \setminus B</math> następująco:
+
Mając ją, możemy określić bijekcję <math>\displaystyle h: A \rightarrow A \setminus B</math> następująco:
  
 
<center><math>\displaystyle h(x) =
 
<center><math>\displaystyle h(x) =
 
\left\{
 
\left\{
 
\begin{array} {ll}
 
\begin{array} {ll}
f(x) , &  x \in B\cup B' \\
+
f(x) , &  x \in B\cup B', \\
x,    &  x \notin B\cup B'
+
x,    &  x \notin B\cup B'.
 
\end{array}  
 
\end{array}  
 
\right.
 
\right.
Linia 618: Linia 617:
  
 
<span id="lemat_3_7">{{lemat|3.7||
 
<span id="lemat_3_7">{{lemat|3.7||
Jeżeli <math>\displaystyle B</math> jest przeliczalnym a  <math>\displaystyle A</math> jest mocy
+
Jeżeli <math>\displaystyle B</math> jest przeliczalnym, a  <math>\displaystyle A</math> jest mocy
continuum to <math>\displaystyle A \cup B</math> jest mocy continuum.  
+
continuum, to <math>\displaystyle A \cup B</math> jest mocy continuum.  
 
}}</span>
 
}}</span>
  
Linia 626: Linia 625:
 
zbiór nieskończony przeliczalny <math>\displaystyle B_0</math>. Zbiór ten musi być równoliczny z <math>\displaystyle B\cup B_0</math>.
 
zbiór nieskończony przeliczalny <math>\displaystyle B_0</math>. Zbiór ten musi być równoliczny z <math>\displaystyle B\cup B_0</math>.
 
W takim razie można bijektywnie ''schować'' zbiór <math>\displaystyle B\cup B_0</math> w zbiorze <math>\displaystyle B_0</math>.
 
W takim razie można bijektywnie ''schować'' zbiór <math>\displaystyle B\cup B_0</math> w zbiorze <math>\displaystyle B_0</math>.
Następnie należy zdefiniować bijekcję między <math>\displaystyle A \cup B</math> a <math>\displaystyle A</math> tak aby na fragmencie z
+
Następnie należy zdefiniować bijekcję między <math>\displaystyle A \cup B</math> a <math>\displaystyle A</math> tak, aby na fragmencie z
poza <math>\displaystyle B_0</math> była identycznością a na <math>\displaystyle B \cup B_0</math> była poprzednią bijekcją. Sklejenie
+
poza <math>\displaystyle B_0</math> była identycznością, a na <math>\displaystyle B \cup B_0</math> była poprzednią bijekcją. Sklejenie
 
takich bijekcji na zbiorach rozłącznych jest bijekcją.
 
takich bijekcji na zbiorach rozłącznych jest bijekcją.
 
}}
 
}}
Linia 633: Linia 632:
 
Twierdzenie poniższe będzie mieć dla nas fundamentalne znaczenie. Porównuje ono moc
 
Twierdzenie poniższe będzie mieć dla nas fundamentalne znaczenie. Porównuje ono moc
 
dwóch podstawowych dla nas zbiorów <math>\displaystyle \mathbb N</math> i <math>\displaystyle \mathbb R</math>. Do dowodu posłużymy się konstrukcją
 
dwóch podstawowych dla nas zbiorów <math>\displaystyle \mathbb N</math> i <math>\displaystyle \mathbb R</math>. Do dowodu posłużymy się konstrukcją
rozwinięcia dwójkowego przeprowadzonego w twierdzeniu 3.15 rozdziału 3 wykładu 8.
+
rozwinięcia dwójkowego przeprowadzonego w Twierdzeniu 3.15 z Wykładu 8 (patrz [[Logika i teoria mnogości/Wykład 8: Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek#twierdzenie_3_15|Wykład 8, Twierdzenie 3.15]] ).
 
Twierdzenie 3.18 tego rozdziału pokazuje bijekcje pomiędzy pewnymi specjalnymi
 
Twierdzenie 3.18 tego rozdziału pokazuje bijekcje pomiędzy pewnymi specjalnymi
 
ciągami ze zbioru <math>\displaystyle 2^\mathbb N</math> a przedziałem <math>\displaystyle [0,1)</math>. Przed przeczytaniem tego dowodu
 
ciągami ze zbioru <math>\displaystyle 2^\mathbb N</math> a przedziałem <math>\displaystyle [0,1)</math>. Przed przeczytaniem tego dowodu
zapoznaj sie z twierdzeniami 3.15, 3.17, 3.18 wykładu 8.
+
zapoznaj sie z Twierdzeniami 3.15, 3.17, 3.18 z Wykładu 8 (patrz [[Logika i teoria mnogości/Wykład 8: Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek#twierdzenie_3_15|Wykład 8]]).
  
 
{{twierdzenie|3.8||
 
{{twierdzenie|3.8||
Linia 643: Linia 642:
  
 
{{dowod|||
 
{{dowod|||
Zbiór <math>\displaystyle 2^\mathbb N</math> rozbijmy na dwa rozłączne podzbiory. Zbiór <math>\displaystyle X</math> taki jak w twierdzeniu
+
Zbiór <math>\displaystyle 2^\mathbb N</math> rozbijmy na dwa rozłączne podzbiory. Zbiór <math>\displaystyle X</math> taki, jak w Twierdzeniu
 
3.18 wykładu 8 to znaczy <math>\displaystyle X= \left\{a\in 2^{\mathbb{N}}: \forall_{k} \;\; \exists_{n>k} \;\; a_n
 
3.18 wykładu 8 to znaczy <math>\displaystyle X= \left\{a\in 2^{\mathbb{N}}: \forall_{k} \;\; \exists_{n>k} \;\; a_n
 
= 0\right\}</math> oraz zbiór
 
= 0\right\}</math> oraz zbiór
 
<math>\displaystyle X' =  \left\{a \in 2^{\mathbb{N}}: \exists_{k} \;\; \forall_{n>k} \;\; a_n = 1\right\}</math> będący jego uzupełnieniem.
 
<math>\displaystyle X' =  \left\{a \in 2^{\mathbb{N}}: \exists_{k} \;\; \forall_{n>k} \;\; a_n = 1\right\}</math> będący jego uzupełnieniem.
Łatwo zauważyć, że <math>\displaystyle X'</math> jest przeliczalny bo można go przedstawić jako przeliczalną
+
Łatwo zauważyć, że <math>\displaystyle X'</math> jest przeliczalny, bo można go przedstawić jako przeliczalną
 
sumę zbiorów skończonych. <math>\displaystyle X'</math> składa się z ciągów, które od pewnego miejsca są stale
 
sumę zbiorów skończonych. <math>\displaystyle X'</math> składa się z ciągów, które od pewnego miejsca są stale
 
równe <math>\displaystyle 1</math>. Zauważmy, że jest jedynie <math>\displaystyle 2^{k_0}</math> takich ciągów, które od <math>\displaystyle k_0 +1</math>
 
równe <math>\displaystyle 1</math>. Zauważmy, że jest jedynie <math>\displaystyle 2^{k_0}</math> takich ciągów, które od <math>\displaystyle k_0 +1</math>
miejsca są stale równe <math>\displaystyle 1</math>. Zbiór <math>\displaystyle X</math> jak pokazaliśmy w twierdzeniu w 3.18 (wykład 8)
+
miejsca są stale równe <math>\displaystyle 1</math>. Zbiór <math>\displaystyle X</math>, jak pokazaliśmy w Twierdzeniu  3.18 w wykładzie 8,
jest równoliczny z przedziałem <math>\displaystyle [0,1)</math> a więc przeliczalny. Nasz zbiór <math>\displaystyle 2^\mathbb N = X
+
jest równoliczny z przedziałem <math>\displaystyle [0,1)</math>, a więc przeliczalny. Nasz zbiór <math>\displaystyle 2^\mathbb N = X
\cup X'</math> jako suma zbioru kontinuum i przeliczalnego na mocy [[#lemat_3_7|Lematu 3.7]] jest mocy kontinuum.
+
\cup X'</math> jako suma zbioru continuum i przeliczalnego na mocy [[#lemat_3_7|Lematu 3.7]] jest mocy continuum.
 
}}
 
}}
  
 
{{twierdzenie|3.9||
 
{{twierdzenie|3.9||
 
<math>\displaystyle \mathbb{N}  <_m  \mathcal{P} (\mathbb{N})  \sim_m  2^{\mathbb{N}}  \sim_m  
 
<math>\displaystyle \mathbb{N}  <_m  \mathcal{P} (\mathbb{N})  \sim_m  2^{\mathbb{N}}  \sim_m  
\mathbb{R}</math>  
+
\mathbb{R}.</math>  
 
}}
 
}}
  
 
Rodzi się naturalne pytanie. Czy istnieje taki zbiór, którego moc dałoby się ulokować
 
Rodzi się naturalne pytanie. Czy istnieje taki zbiór, którego moc dałoby się ulokować
pomiędzy mocą zbioru liczb naturalnych a mocą kontinuum. Czyli, czy istnieje <math>\displaystyle A</math>
+
pomiędzy mocą zbioru liczb naturalnych a mocą continuum. Czyli, czy istnieje <math>\displaystyle A</math>
 
takie, że
 
takie, że
  
Linia 669: Linia 668:
  
 
Cantor przypuszczał, że takiego zbioru (mocy) nie ma i że następnym w hierarchii mocy
 
Cantor przypuszczał, że takiego zbioru (mocy) nie ma i że następnym w hierarchii mocy
zbiorem po <math>\displaystyle \mathbb N</math> jest <math>\displaystyle \mathbb R</math>. Przypuszczenie Cantora nazywa się '''hipotezą kontinuum'''. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Goedel%2C_Kurt Kurt Gödel] pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w '''<u>hipotezie kontinuum</u>''' istnieje  i nie doprowadzi to teorii mnogości do sprzeczności o ile sama nie jest sprzeczna. W roku 1963 <u>'''Paul Joseph Cohen</u>''' pokazał niezależność hipotezy kontinuum 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.
+
zbiorem po <math>\displaystyle \mathbb N</math> jest <math>\displaystyle \mathbb R</math>. Przypuszczenie Cantora nazywa się '''hipotezą continuum'''. Hipoteza ta była intensywnie badana przez matematyków. W roku 1939 [http://osilek.mimuw.edu.pl/index.php?title=Biografia_Goedel%2C_Kurt Kurt Gödel] pokazał niesprzeczność tej hipotezy z aksjomatami teorii mnogości. Można zatem przyjąć, że taki zbiór jak w '''<u>hipotezie kontinuum</u>''' istnieje  i nie doprowadzi to teorii mnogości do sprzeczności, o ile sama nie jest sprzeczna. W roku 1963 <u>'''Paul Joseph Cohen</u>''' 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 nie odwołującą się do pojęcia
+
Na koniec podamy jako ćwiczenie inną bardzo elegancką i nieodwołującą się do pojęcia
 
liczb naturalnych definicję nieskończoności.
 
liczb naturalnych definicję nieskończoności.
  
 
{{definicja|3.10||
 
{{definicja|3.10||
 
(definicja nieskończoności
 
(definicja nieskończoności
Dedekinda) Zbiór <math>\displaystyle X</math> jest nieskończony w sensie Dedekinda gdy istnieje podzbiór
+
Dedekinda) Zbiór <math>\displaystyle X</math> jest nieskończony w sensie Dedekinda, gdy istnieje podzbiór
właściwy <math>\displaystyle X_0</math> zbioru <math>\displaystyle X</math> który jest z nim równoliczny. Zbiór jest skończony, w sensie Dedekinda, jeśli nie jest nieskończony w sensie Dedekinda.   
+
właściwy <math>\displaystyle X_0</math> zbioru <math>\displaystyle X</math>, który jest z nim równoliczny. Zbiór jest skończony, w sensie Dedekinda, jeśli nie jest nieskończony w sensie Dedekinda.   
 
}}
 
}}
 
 
Linia 683: Linia 682:
 
{{cwiczenie|3.11||
 
{{cwiczenie|3.11||
  
Pokaż, że zbiór jest nieskończony wtedy i tylko wtedy gdy jest nieskończony w sensie
+
Pokaż, że zbiór jest nieskończony wtedy i tylko wtedy, gdy jest nieskończony w sensie
 
Dedekinda.
 
Dedekinda.
  
Linia 700: Linia 699:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">   
 
 
Skorzystaj z <u>'''Twierdzenia 4.1 z Wykładu 11'''</u>.
+
Skorzystaj z [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady#twierdzenie_4_1|Twierdzenia 4.1 z Wykładu 11]].
  
 
</div></div>
 
</div></div>
Linia 708: Linia 707:
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">   
 
 
Implikacja w jedną stronę jest prosta. Jeśli zbiór jest skończony, to jest również skończony w sensie Dedekinda. Wykażemy najpierw, że jeśli z różnej od zera liczby naturalnej <math>\displaystyle n</math> usuniemy dowolny element to zbiór powstały będzie równoliczny z <math>\displaystyle n-1</math>. Usuńmy dowolny element z <math>\displaystyle n</math>. Jeśli usunęliśmy <math>\displaystyle n-1</math> to otrzymujemy liczbę <math>\displaystyle n-1</math>. Jeśli usunęliśmy <math>\displaystyle k\neq n-1</math> to możemy zdefiniować bijekcję pomiędzy <math>\displaystyle n\setminus\{k\}</math> a <math>\displaystyle n-1</math> poprzez
+
Implikacja w jedną stronę jest prosta. Jeśli zbiór jest skończony, to jest również skończony w sensie Dedekinda. Wykażemy najpierw, że jeśli z różnej od zera liczby naturalnej <math>\displaystyle n</math> usuniemy dowolny element, to zbiór powstały będzie równoliczny z <math>\displaystyle n-1</math>. Usuńmy dowolny element z <math>\displaystyle n</math>. Jeśli usunęliśmy <math>\displaystyle n-1</math>, to otrzymujemy liczbę <math>\displaystyle n-1</math>. Jeśli usunęliśmy <math>\displaystyle k\neq n-1</math>, to możemy zdefiniować bijekcję pomiędzy <math>\displaystyle n\setminus\{k\}</math> a <math>\displaystyle n-1</math> poprzez:
  
<center><math>\displaystyle f(m)= \begin{cases} m& \mbox{ jeśli }\displaystyle  m\neq n-1\\k& \mbox{ jeśli }\displaystyle m = n-1.\end{cases}</math></center>
+
<center><math>\displaystyle f(m)= \begin{cases} m,& \mbox{ jeśli }\displaystyle  m\neq n-1,\\k,& \mbox{ jeśli }\displaystyle m = n-1.\end{cases}</math></center>
  
Wybierzmy teraz najmniejszą liczbę <math>\displaystyle n</math> równoliczną z inną liczbą naturalną <math>\displaystyle m</math>. Niewątpliwie <math>\displaystyle n</math> i <math>\displaystyle m</math> są różne od zera i istnieje bijekcja <math>\displaystyle f:n\rightarrow m</math>. Jeśli bijekcję <math>\displaystyle f</math> zawężymy do <math>\displaystyle n-1</math> to obraz zawęzi się, na mocy udowodnionego wcześniej wniosku, do podzbioru <math>\displaystyle m</math> równolicznego <math>\displaystyle m-1</math>. Wykazaliśmy, że zbiór <math>\displaystyle n-1</math> jest równoliczny <math>\displaystyle m-1</math>, co jest sprzecznością z minimalnością <math>\displaystyle n</math>. Wykazaliśmy, że żadne dwie różne liczby naturalne nie są równoliczne. Ustalmy teraz dowolny skończony zbiór <math>\displaystyle X</math>. Istnieje bijekcja pomiędzy <math>\displaystyle X</math> i <math>\displaystyle n</math> dla pewnej liczby naturalnej <math>\displaystyle n</math>. Jeśli <math>\displaystyle X</math> byłby bijektywny ze swoim istotnym podzbiorem to również <math>\displaystyle n</math> byłoby bijektywne ze swoim istotnym podzbiorem, czyli ze zbiorem równolicznym liczbie naturalnej mniejszej o co najmniej <math>\displaystyle 1</math> -- jest to sprzecznością z wcześniej wykazanym faktem.
+
Wybierzmy teraz najmniejszą liczbę <math>\displaystyle n</math> równoliczną z inną liczbą naturalną <math>\displaystyle m</math>. Niewątpliwie <math>\displaystyle n</math> i <math>\displaystyle m</math> są różne od zera i istnieje bijekcja <math>\displaystyle f:n\rightarrow m</math>. Jeśli bijekcję <math>\displaystyle f</math> zawężymy do <math>\displaystyle n-1</math>, to obraz zawęzi się, na mocy udowodnionego wcześniej wniosku, do podzbioru <math>\displaystyle m</math> równolicznego <math>\displaystyle m-1</math>. Wykazaliśmy, że zbiór <math>\displaystyle n-1</math> jest równoliczny <math>\displaystyle m-1</math>, co jest sprzecznością z minimalnością <math>\displaystyle n</math>. Wykazaliśmy, że żadne dwie różne liczby naturalne nie są równoliczne. Ustalmy teraz dowolny skończony zbiór <math>\displaystyle X</math>. Istnieje bijekcja pomiędzy <math>\displaystyle X</math> i <math>\displaystyle n</math>, dla pewnej liczby naturalnej <math>\displaystyle n</math>. Jeśli <math>\displaystyle X</math> byłby bijektywny ze swoim istotnym podzbiorem, to również <math>\displaystyle n</math> byłoby bijektywne ze swoim istotnym podzbiorem, czyli ze zbiorem równolicznym liczbie naturalnej mniejszej o co najmniej <math>\displaystyle 1</math> -- jest to sprzecznością z wcześniej wykazanym faktem.
  
Dla dowodu implikacji w drugą stronę wykorzystamy <u>'''Twierdzenie 4.1 z Wykładu 11'''</u>. Mówi ono, że dla każdego nieskończonego zbioru istnieje iniekcja z <math>\displaystyle \mathbb{N}</math> w ten zbiór. Ustalmy dowolny nieskończony zbiór <math>\displaystyle X</math> i taką iniekcję <math>\displaystyle f:\mathbb{N}\rightarrow X</math>. Niech <math>\displaystyle Y\subset X</math> będzie obrazem <math>\displaystyle \mathbb{N}</math> względem <math>\displaystyle f</math> tak, że <math>\displaystyle f:\mathbb{N}\rightarrow Y</math> jest bijekcją. Zdefiniujmy funkcję <math>\displaystyle g:X\rightarrow X</math>
+
Dla dowodu implikacji w drugą stronę wykorzystamy [[Logika i teoria mnogości/Wykład 11: Zbiory dobrze uporządkowane. Lemat Kuratowskiego Zorna i twierdzenie Zermelo, przykłady#twierdzenie_4_1|Twierdzenia 4.1 z Wykładu 11]]. Mówi ono, że dla każdego nieskończonego zbioru istnieje iniekcja z <math>\displaystyle \mathbb{N}</math> w ten zbiór. Ustalmy dowolny nieskończony zbiór <math>\displaystyle X</math> i taką iniekcję <math>\displaystyle f:\mathbb{N}\rightarrow X</math>. Niech <math>\displaystyle Y\subset X</math> będzie obrazem <math>\displaystyle \mathbb{N}</math> względem <math>\displaystyle f</math> tak, że <math>\displaystyle f:\mathbb{N}\rightarrow Y</math> jest bijekcją. Zdefiniujmy funkcję <math>\displaystyle g:X\rightarrow X</math>:
  
 
<center><math>\displaystyle h(x) = \begin{cases} x& \mbox{ jeśli }\displaystyle x\notin Y \\ f(n+1)& \mbox{ jeśli }\displaystyle x=f(n)\in Y. \end{casses} \right </math></center>
 
<center><math>\displaystyle h(x) = \begin{cases} x& \mbox{ jeśli }\displaystyle x\notin Y \\ f(n+1)& \mbox{ jeśli }\displaystyle x=f(n)\in Y. \end{casses} \right </math></center>
  
Jak łatwo sprawdzić funkcja <math>\displaystyle h:X\rightarrow X\setminus\{f(0)\}</math> jest bijekcją, co dowodzi, że zbiór <math>\displaystyle X</math> jest równoliczny ze swoim istotnym podzbiorem, czyli, że jest nieskończony w sensie Dedekinda.
+
Jak łatwo sprawdzić funkcja <math>\displaystyle h:X\rightarrow X\setminus\{f(0)\}</math> jest bijekcją, co dowodzi, że zbiór <math>\displaystyle X</math> jest równoliczny ze swoim istotnym podzbiorem, czyli że jest nieskończony w sensie Dedekinda.
  
 
Wykazaliśmy, że zbiór skończony jest skończony w sensie Dedekinda i że zbiór nieskończony jest nieskończony w sensie Dedekinda co kończy ćwiczenie. Zwróćmy uwagę, że przy dowodzie tego faktu użyliśmy aksjomatu wyboru.
 
Wykazaliśmy, że zbiór skończony jest skończony w sensie Dedekinda i że zbiór nieskończony jest nieskończony w sensie Dedekinda co kończy ćwiczenie. Zwróćmy uwagę, że przy dowodzie tego faktu użyliśmy aksjomatu wyboru.

Wersja z 18:55, 17 wrz 2006

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

{{{3}}} 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

Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (2) \hspace*{0.1mm} \Rightarrow (1)} . Niech i . Niech iniekcja oraz niech . Mamy więc oraz . Stosując do , otrzymujemy , co wobec daje .

Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (1) \hspace*{0.1mm} \Rightarrow (3)} . 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 .

Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (3) \hspace*{0.1mm} \Rightarrow (2)} . 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 istniej 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