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 736: Linia 736:
 
<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">   
 
 
Niewątpliwie <math>\displaystyle 2^{\mathbb{R}} \leq_m  \mathbb{R}^{\mathbb{R}}</math>, ponieważ <math>\displaystyle \{a,b\}^{\mathbb{R}}\subset \mathbb{R}^{\mathbb{R}}</math>, gdzie <math>\displaystyle a</math> jest liczbą rzeczywistą <math>\displaystyle 0</math>, a <math>\displaystyle b</math> liczbą rzeczywistą <math>\displaystyle 1</math>. Równocześnie <math>\displaystyle \mathbb{R}^{\mathbb{R}} \sim_m  {2^{\mathbb{N}}}^{\mathbb{R}}  \sim_m  2^{\mathbb{N}\times\mathbb{R}} \leq_m  2^{\mathbb{R}\times\mathbb{R}} \sim_m  2^{2^{\mathbb{N}}\times 2^{\mathbb{N}}} \sim_m  2^{2^{\mathbb{N}}} \sim_m  2^{\mathbb{R}}</math>, gdzie każde z przejść jest prostą konsekwencją faktów dowiedzionych na wykładzie. Korzystając z [[#twierdzenie_2_12|Twierdzenia 2.12 Cantora-Bernsteina]] wnioskujemy, że <math>\displaystyle \mathbb{R}^{\mathbb{R}} \sim_m  2^{\mathbb{R}}</math>.
+
Niewątpliwie <math>\displaystyle 2^{\mathbb{R}} \leq_m  \mathbb{R}^{\mathbb{R}}</math>, ponieważ <math>\displaystyle \{a,b\}^{\mathbb{R}}\subset \mathbb{R}^{\mathbb{R}}</math>, gdzie <math>\displaystyle a</math> jest liczbą rzeczywistą <math>\displaystyle 0</math>, a <math>\displaystyle b</math> liczbą rzeczywistą <math>\displaystyle 1</math>. Równocześnie <math>\displaystyle \mathbb{R}^{\mathbb{R}} \sim_m  {2^{\mathbb{N}}}^{\mathbb{R}}  \sim_m  2^{\mathbb{N}\times\mathbb{R}} \leq_m  2^{\mathbb{R}\times\mathbb{R}} \sim_m  2^{2^{\mathbb{N}}\times 2^{\mathbb{N}}} \sim_m  2^{2^{\mathbb{N}}} \sim_m  2^{\mathbb{R}}</math>, gdzie każde z przejść jest prostą konsekwencją faktów dowiedzionych na wykładzie. Korzystając z [[#twierdzenie_2_12|Twierdzenia 2.12 Cantora-Bernsteina]], wnioskujemy, że <math>\displaystyle \mathbb{R}^{\mathbb{R}} \sim_m  2^{\mathbb{R}}</math>.
 
</div></div>
 
</div></div>
  
Linia 773: Linia 773:
 
<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">   
 
 
Przykłady funkcji silnie rosnących ze skończoną, lub równoliczną <math>\displaystyle \mathbb{N}</math> liczbą punktów nieciągłości są trywialne. Aby wykazać, że dowolna, silnie rosnąca funkcja <math>\displaystyle f:\mathbb{R} \rightarrow \mathbb{R}</math> nie może mieć więcej niż przeliczalnie wiele punktów nieciągłości, stworzymy iniekcję, która każdemu punktowi nieciągłości przyporządkowuje jakiś element <math>\displaystyle \mathbb{Q}</math>. Ustalmy punkt nieciągłości <math>\displaystyle a</math>. Wtedy <math>\displaystyle \lim_{x\to a^-}f(x)</math> istnieje, ponieważ funkcja jest rosnąca i ograniczona z góry&nbsp;(przez np. <math>\displaystyle f(a+1)</math>). Podobnie istnieje <math>\displaystyle \lim_{x\to a^+}f(x)</math>. Ponieważ <math>\displaystyle a</math> jest punktem nieciągłości mamy <math>\displaystyle \lim_{x\to a^-}f(x) < \lim_{x\to a^+}f(x)</math>. Ponieważ <math>\displaystyle \mathbb{Q}</math> jest gęste w <math>\displaystyle \mathbb{R}</math> istnieje <math>\displaystyle r_a\in\mathbb{Q}</math> takie, że <math>\displaystyle \lim_{x\to a^-}f(x) < r_a < \lim_{x\to a^+}f(x)</math>. Pozostaje wykazać, że dla dwóch punktów nieciągłości <math>\displaystyle a</math> i <math>\displaystyle b</math>, jeśli <math>\displaystyle a\neq b</math>, to <math>\displaystyle r_a\neq r_b</math>. Ponieważ porządek na <math>\displaystyle \mathbb{R}</math> jest porządkiem liniowym mamy <math>\displaystyle a<b</math> lub <math>\displaystyle b<a</math>. Możemy, bez straty, ogólności założyć ten pierwszy przypadek i znaleźć <math>\displaystyle c\in\mathbb{R}</math> takie, że <math>\displaystyle a<c<b</math>. Wtedy <math>\displaystyle r_a<\lim_{x\to a^+}f(x) < f(c) <\lim_{x\to b^-}f(x) < r_b</math> co dowodzi, że funkcja <math>\displaystyle a\mapsto r_a</math> jest iniekcją jak twierdziliśmy.
+
Przykłady funkcji silnie rosnących ze skończoną lub równoliczną <math>\displaystyle \mathbb{N}</math> liczbą punktów nieciągłości są trywialne. Aby wykazać, że dowolna, silnie rosnąca funkcja <math>\displaystyle f:\mathbb{R} \rightarrow \mathbb{R}</math> nie może mieć więcej niż przeliczalnie wiele punktów nieciągłości, stworzymy iniekcję, która każdemu punktowi nieciągłości przyporządkowuje jakiś element <math>\displaystyle \mathbb{Q}</math>. Ustalmy punkt nieciągłości <math>\displaystyle a</math>. Wtedy <math>\displaystyle \lim_{x\to a^-}f(x)</math> istnieje, ponieważ funkcja jest rosnąca i ograniczona z góry&nbsp;(przez np. <math>\displaystyle f(a+1)</math>). Podobnie istnieje <math>\displaystyle \lim_{x\to a^+}f(x)</math>. Ponieważ <math>\displaystyle a</math> jest punktem nieciągłości mamy <math>\displaystyle \lim_{x\to a^-}f(x) < \lim_{x\to a^+}f(x)</math>. Ponieważ <math>\displaystyle \mathbb{Q}</math> jest gęste w <math>\displaystyle \mathbb{R}</math> istnieje <math>\displaystyle r_a\in\mathbb{Q}</math> takie, że <math>\displaystyle \lim_{x\to a^-}f(x) < r_a < \lim_{x\to a^+}f(x)</math>. Pozostaje wykazać, że dla dwóch punktów nieciągłości <math>\displaystyle a</math> i <math>\displaystyle b</math>, jeśli <math>\displaystyle a\neq b</math>, to <math>\displaystyle r_a\neq r_b</math>. Ponieważ porządek na <math>\displaystyle \mathbb{R}</math> jest porządkiem liniowym, mamy <math>\displaystyle a<b</math> lub <math>\displaystyle b<a</math>. Możemy, bez straty ogólności, założyć ten pierwszy przypadek i znaleźć <math>\displaystyle c\in\mathbb{R}</math> takie, że <math>\displaystyle a<c<b</math>. Wtedy <math>\displaystyle r_a<\lim_{x\to a^+}f(x) < f(c) <\lim_{x\to b^-}f(x) < r_b</math>, co dowodzi, że funkcja <math>\displaystyle a\mapsto r_a</math> jest iniekcją, jak twierdziliśmy.
 
</div></div>
 
</div></div>
  
Linia 788: Linia 788:
 
<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">   
 
 
Każda taka funkcja to podzbiór <math>\displaystyle \mathbb{N}\times\mathbb{N}</math>, a więc zbiór wszystkich takich funkcji jest podzbiorem <math>\displaystyle \mathcal{P}(\mathbb{N}\times\mathbb{N})</math>, który jest równoliczne z <math>\displaystyle \mathcal{P}(\mathbb{N}) \sim_m  2^{\mathbb{N}}</math>. Wykażemy, że tych funkcji jest dokładnie tyle, co <math>\displaystyle 2^{\mathbb{N}}</math> poprzez zdefiniowanie iniekcji z <math>\displaystyle 2^{\mathbb{N}}</math> w nasz zbiór. Dla dowolnego <math>\displaystyle f\in 2^{\mathbb{N}}</math> definiujemy <math>\displaystyle f':\mathbb{N}\rightarrow\mathbb{N}</math>  
+
Każda taka funkcja to podzbiór <math>\displaystyle \mathbb{N}\times\mathbb{N}</math>, a więc zbiór wszystkich takich funkcji jest podzbiorem <math>\displaystyle \mathcal{P}(\mathbb{N}\times\mathbb{N})</math>, który jest równoliczny z <math>\displaystyle \mathcal{P}(\mathbb{N}) \sim_m  2^{\mathbb{N}}</math>. Wykażemy, że tych funkcji jest dokładnie tyle, co <math>\displaystyle 2^{\mathbb{N}}</math> poprzez zdefiniowanie iniekcji z <math>\displaystyle 2^{\mathbb{N}}</math> w nasz zbiór. Dla dowolnego <math>\displaystyle f\in 2^{\mathbb{N}}</math> definiujemy <math>\displaystyle f':\mathbb{N}\rightarrow\mathbb{N}</math> następująco:
  
 
<center><math>\displaystyle f'(n) = 2n + f(n).
 
<center><math>\displaystyle f'(n) = 2n + f(n).
 
</math></center>
 
</math></center>
  
Zwróćmy uwagę, że funkcja <math>\displaystyle f'</math> jest silnie rosnąca, ponieważ dla <math>\displaystyle n<m</math> mamy <math>\displaystyle f'(n) = 2n+f(n) \leq 2n+1 < 2n+2 =2(n+1)\leq 2m\leq f'(m)</math>. Równocześnie, jeśli <math>\displaystyle f,g\in 2^{\mathbb{N}}</math> i <math>\displaystyle f\neq g</math>, to również <math>\displaystyle f'\neq g'</math>, ponieważ jeśli <math>\displaystyle f(n) \neq g(n)</math> dla pewnego <math>\displaystyle n\in\mathbb{N}</math>, to<math>\displaystyle f'(n) = 2n+f(n)\neq 2n + g(n) = g'(n)</math>. Zdefiniowane przekształcenie przyporządkowuje elementom <math>\displaystyle 2^{\mathbb{N}}</math> silnie rosnące funkcje z <math>\displaystyle \mathbb{N}</math> do <math>\displaystyle \mathbb{N}</math> dowodząc, że nasz zbiór jest większy na moc niż <math>\displaystyle 2^{\mathbb{N}}</math>. Twierdzenie Cantor-Bernstein gwarantuje, że funkcji tych jest dokładnie continuum.
+
Zwróćmy uwagę, że funkcja <math>\displaystyle f'</math> jest silnie rosnąca, ponieważ dla <math>\displaystyle n<m</math> mamy <math>\displaystyle f'(n) = 2n+f(n) \leq 2n+1 < 2n+2 =2(n+1)\leq 2m\leq f'(m)</math>. Równocześnie, jeśli <math>\displaystyle f,g\in 2^{\mathbb{N}}</math> i <math>\displaystyle f\neq g</math>, to również <math>\displaystyle f'\neq g'</math>, ponieważ jeśli <math>\displaystyle f(n) \neq g(n)</math>, dla pewnego <math>\displaystyle n\in\mathbb{N}</math>, to<math>\displaystyle f'(n) = 2n+f(n)\neq 2n + g(n) = g'(n)</math>. Zdefiniowane przekształcenie przyporządkowuje elementom <math>\displaystyle 2^{\mathbb{N}}</math> silnie rosnące funkcje z <math>\displaystyle \mathbb{N}</math> do <math>\displaystyle \mathbb{N}</math>, dowodząc, że nasz zbiór jest większy na moc niż <math>\displaystyle 2^{\mathbb{N}}</math>. Twierdzenie Cantora-Bernsteina gwarantuje, że funkcji tych jest dokładnie continuum.
 
</div></div>
 
</div></div>
  
Linia 800: Linia 800:
 
{{cwiczenie|4.5||
 
{{cwiczenie|4.5||
  
Czy na płaszczyźnie istniej okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną?
+
Czy na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną?
  
 
}}
 
}}
Linia 808: Linia 808:
 
<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">   
 
 
Zakładamy, niewprost, że okrąg taki nie istnieje. Wtedy, każdy okrąg ma przynajmniej jeden punkt posiadający obie współrzędne wymierne. Rozważmy wszystkie okręgi o środku w <math>\displaystyle (0,0)</math> -- jest ich continuum wiele i każde dwa mają puste przecięcie. Jeśli każdy z nich miałby punkt o obu współrzędnych wymiernych, to moglibyśmy stworzyć iniekcję z <math>\displaystyle \mathbb{R}</math> w <math>\displaystyle \mathbb{Q}\times\mathbb{Q}</math> dowodząc, że <math>\displaystyle \mathbb{R}</math> jest przeliczalny. Sprzeczność ta dowodzi, że na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną.
+
Zakładamy, niewprost, że okrąg taki nie istnieje. Wtedy, każdy okrąg ma przynajmniej jeden punkt posiadający obie współrzędne wymierne. Rozważmy wszystkie okręgi o środku w <math>\displaystyle (0,0)</math> -- jest ich continuum wiele i każde dwa mają puste przecięcie. Jeśli każdy z nich miałby punkt o obu współrzędnych wymiernych, to moglibyśmy stworzyć iniekcję z <math>\displaystyle \mathbb{R}</math> w <math>\displaystyle \mathbb{Q}\times\mathbb{Q}</math>, dowodząc, że <math>\displaystyle \mathbb{R}</math> jest przeliczalny. Sprzeczność ta dowodzi, że na płaszczyźnie istnieje okrąg taki, że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną.
 
</div></div>
 
</div></div>
  
Linia 815: Linia 815:
 
<span id="cwiczenie_4_6">{{cwiczenie|4.6||
 
<span id="cwiczenie_4_6">{{cwiczenie|4.6||
  
Zbiór <math>\displaystyle A\subset \mathbb{Q}</math> nazywamy wypukłym, jeśli, dla dowolnych <math>\displaystyle a,b\in A</math>, jeśli <math>\displaystyle c\in\mathbb{Q}</math> i <math>\displaystyle a<c<b</math>, to <math>\displaystyle c\in A</math>. Ile jest zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math>?
+
Zbiór <math>\displaystyle A\subset \mathbb{Q}</math> nazywamy wypukłym, jeśli dla dowolnych <math>\displaystyle a,b\in A</math>, jeśli <math>\displaystyle c\in\mathbb{Q}</math> i <math>\displaystyle a<c<b</math>, to <math>\displaystyle c\in A</math>. Ile jest zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math>?
  
 
}}</span>
 
}}</span>
Linia 823: Linia 823:
 
<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">   
 
 
Zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math> jest continuum. Oczywiście nie może ich być więcej niż continuum, ponieważ tyle jest wszystkich podzbiorów <math>\displaystyle \mathbb{Q}</math>. Aby wykazać, że nie ma ich mniej ustalmy iniekcję z przedziału <math>\displaystyle [0,1]</math> w liczbach rzeczywistych w zbiór wypukłych podzbiorów <math>\displaystyle \mathbb{Q}</math>. Dla dowolnej liczby rzeczywistej <math>\displaystyle r\in[0,1]</math> zdefiniujmy
+
Zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math> jest continuum. Oczywiście nie może ich być więcej niż continuum, ponieważ tyle jest wszystkich podzbiorów <math>\displaystyle \mathbb{Q}</math>. Aby wykazać, że nie ma ich mniej, ustalmy iniekcję z przedziału <math>\displaystyle [0,1]</math> w liczbach rzeczywistych w zbiór wypukłych podzbiorów <math>\displaystyle \mathbb{Q}</math>. Dla dowolnej liczby rzeczywistej <math>\displaystyle r\in[0,1]</math> zdefiniujmy:
  
 
<center><math>\displaystyle I_r = [0,r] \cap \mathbb{Q}.
 
<center><math>\displaystyle I_r = [0,r] \cap \mathbb{Q}.
 
</math></center>
 
</math></center>
  
Niewątpliwie każdy zbiór <math>\displaystyle I_r</math> jest wypukły, ponieważ jeśli <math>\displaystyle a<b\in I_r</math>, to <math>\displaystyle 0\leq a</math> i <math>\displaystyle b\leq r</math>, a więc dla każdego <math>\displaystyle c</math> takiego, że <math>\displaystyle a<c<b</math> zachodzi <math>\displaystyle 0\leq c \leq r</math>, czyli <math>\displaystyle c\in I_r</math>. Pozostaje wykazać, że funkcja <math>\displaystyle r\mapsto I_r</math> jest iniekcją. Ustalmy dwie liczby rzeczywiste <math>\displaystyle r\neq s</math>. Bez straty ogólności możemy założyć, że <math>\displaystyle r<s</math>. Istnieje wtedy liczba wymierna <math>\displaystyle t</math> taka, że <math>\displaystyle r<t<s</math> i mamy <math>\displaystyle t\in I_s</math> oraz <math>\displaystyle t\notin I_r</math> dowodząc, że <math>\displaystyle I_r\neq I_s</math>. Na mocy Twierdzenia Cantora-Bernsteina zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math> jest continuum.
+
Niewątpliwie każdy zbiór <math>\displaystyle I_r</math> jest wypukły, ponieważ jeśli <math>\displaystyle a<b\in I_r</math>, to <math>\displaystyle 0\leq a</math> i <math>\displaystyle b\leq r</math>, a więc dla każdego <math>\displaystyle c</math> takiego, że <math>\displaystyle a<c<b</math> zachodzi <math>\displaystyle 0\leq c \leq r</math>, czyli <math>\displaystyle c\in I_r</math>. Pozostaje wykazać, że funkcja <math>\displaystyle r\mapsto I_r</math> jest iniekcją. Ustalmy dwie liczby rzeczywiste <math>\displaystyle r\neq s</math>. Bez straty ogólności możemy założyć, że <math>\displaystyle r<s</math>. Istnieje wtedy liczba wymierna <math>\displaystyle t</math> taka, że <math>\displaystyle r<t<s</math> i mamy <math>\displaystyle t\in I_s</math> oraz <math>\displaystyle t\notin I_r</math>, dowodząc, że <math>\displaystyle I_r\neq I_s</math>. Na mocy Twierdzenia Cantora-Bernsteina zbiorów wypukłych w <math>\displaystyle \mathbb{Q}</math> jest continuum.
 
</div></div>
 
</div></div>
  
Linia 843: Linia 843:
 
<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">   
 
 
Łańcuch taki nie może posiadać więcej niż continuum elementów, ponieważ moc całego zbioru <math>\displaystyle \mathcal{P}(\mathbb{N})</math> jest continuum. Wykażemy, że istnieje w tym zbiorze częściowo uporządkowanym łańcuch o mocy continuum. Zamiast operować na zbiorze <math>\displaystyle \mathbb{N}</math> operować będzie na zbiorze mu równolicznym <math>\displaystyle \mathbb{Q}</math>. Zwróćmy uwagę, że zdefiniowane w [[#cwiczenie_4_6|Ćwiczeniu 4.6]] zbiory <math>\displaystyle I_r</math> są uporządkowane liniowo przez inkluzję, są podzbiorami <math>\displaystyle \mathbb{Q}</math> i jest ich continuum wiele. Zbiory te tworzą żądany łańcuch.
+
Łańcuch taki nie może posiadać więcej niż continuum elementów, ponieważ moc całego zbioru <math>\displaystyle \mathcal{P}(\mathbb{N})</math> jest continuum. Wykażemy, że istnieje w tym zbiorze częściowo uporządkowanym łańcuch o mocy continuum. Zamiast pracować na zbiorze <math>\displaystyle \mathbb{N}</math> będziemy pracować na zbiorze mu równolicznym <math>\displaystyle \mathbb{Q}</math>. Zwróćmy uwagę, że zdefiniowane w [[#cwiczenie_4_6|Ćwiczeniu 4.6]] zbiory <math>\displaystyle I_r</math> są uporządkowane liniowo przez inkluzję, są podzbiorami <math>\displaystyle \mathbb{Q}</math> i jest ich continuum wiele. Zbiory te tworzą żądany łańcuch.
 
</div></div>
 
</div></div>
  
Linia 858: Linia 858:
 
<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">   
 
 
Bijekcji tych, podobnie jak funkcji ściśle rosnących w [[#cwiczenie_4_4|Ćwiczeniu 4.4]] nie może być więcej niż continuum. Aby wykazać, że jest ich dokładnie tyle zdefiniujemy iniekcję, która każdemy elementowi <math>\displaystyle 2^{\mathbb{N}}</math> przyporządkowuje pewną bijekcję. Jeśli <math>\displaystyle f\in 2^{\mathbb{N}}</math>, to bijekcja <math>\displaystyle f'</math> działa następująco
+
Bijekcji tych, podobnie jak funkcji ściśle rosnących w [[#cwiczenie_4_4|Ćwiczeniu 4.4]], nie może być więcej niż continuum. Aby wykazać, że jest ich dokładnie tyle zdefiniujemy iniekcję, która każdemy elementowi <math>\displaystyle 2^{\mathbb{N}}</math> przyporządkowuje pewną bijekcję. Jeśli <math>\displaystyle f\in 2^{\mathbb{N}}</math>, to bijekcja <math>\displaystyle f'</math> działa następująco:
  
 
<center><math>\displaystyle f'(2n) = 2n </math>  oraz  <math>\displaystyle  f'(2n+1) = 2n+1  </math>  wtedy i tylko wtedy, kiedy  <math>\displaystyle  f(n)=0
 
<center><math>\displaystyle f'(2n) = 2n </math>  oraz  <math>\displaystyle  f'(2n+1) = 2n+1  </math>  wtedy i tylko wtedy, kiedy  <math>\displaystyle  f(n)=0
Linia 875: Linia 875:
 
{{cwiczenie|4.9||
 
{{cwiczenie|4.9||
  
Jakiej mocy jest zbiór porządków na <math>\displaystyle \mathbb{N}</math> które są równocześnie funkcjami <math>\displaystyle \mathbb{N}\rightarrow\mathbb{N}</math>?
+
Jakiej mocy jest zbiór porządków na <math>\displaystyle \mathbb{N}</math>, które są równocześnie funkcjami <math>\displaystyle \mathbb{N}\rightarrow\mathbb{N}</math>?
  
 
}}
 
}}
Linia 883: Linia 883:
 
<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">   
 
 
Zbiór ten jest jednoelementowy. Niewątpliwie funkcja identycznościowa jest porządkiem -- antyłańcuchem. Ustalmy dowolny, nieidentycznościowy porządek na <math>\displaystyle \mathbb{N}</math>. Założenie gwarantuje, że porządek ten zawiera parę <math>\displaystyle (n,m)</math> dla pewnego <math>\displaystyle n\neq m</math>. Równocześnie zwrotność gwarantuje, że zawiera on również parę <math>\displaystyle (n,n)</math> co przeczy definicji funkcji.
+
Zbiór ten jest jednoelementowy. Niewątpliwie funkcja identycznościowa jest porządkiem -- antyłańcuchem. Ustalmy dowolny, nieidentycznościowy porządek na <math>\displaystyle \mathbb{N}</math>. Założenie gwarantuje, że porządek ten zawiera parę <math>\displaystyle (n,m)</math>, dla pewnego <math>\displaystyle n\neq m</math>. Równocześnie zwrotność gwarantuje, że zawiera on również parę <math>\displaystyle (n,n)</math>, co przeczy definicji funkcji.
 
</div></div>
 
</div></div>
  
Linia 890: Linia 890:
 
{{cwiczenie|4.10||
 
{{cwiczenie|4.10||
  
Dowolna rodzina <math>\displaystyle X\subset \mathcal{P}(\mathbb{N})</math> taka, że dla dowolnych dwóch różnych elementów <math>\displaystyle X</math> ich przecięcie jest co najwyżej jednoelementowe jest przeliczalna.
+
Dowolna rodzina <math>\displaystyle X\subset \mathcal{P}(\mathbb{N})</math> taka, że dla dowolnych dwóch różnych elementów <math>\displaystyle X</math> ich przecięcie jest co najwyżej jednoelementowe, jest przeliczalna.
  
 
}}
 
}}
Linia 898: Linia 898:
 
<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">   
 
 
Aby to wykazać dzielimy rodzinę <math>\displaystyle X</math> na dwie części <math>\displaystyle X_1</math> i <math>\displaystyle X'</math>. Niech zbiór <math>\displaystyle X_1</math> zawiera wszystkie zero i jednoelementowe elementy <math>\displaystyle X</math> -- jest ich przeliczalnie wiele, bo każdy z nich jest podzbiorem <math>\displaystyle \mathbb{N}</math>. Pozostaje wykazać, że <math>\displaystyle X'</math> jest przeliczalny i wtedy <math>\displaystyle X</math> jako unia dwóch zbiorów przeliczalnych będzie również przeliczalny. Aby wykazać, że <math>\displaystyle X'</math> jest przeliczalny ustawmy funkcję <math>\displaystyle f:X'\to \mathbb{N}\times\mathbb{N}</math> taką, że
+
Aby to wykazać, dzielimy rodzinę <math>\displaystyle X</math> na dwie części: <math>\displaystyle X_1</math> i <math>\displaystyle X'</math>. Niech zbiór <math>\displaystyle X_1</math> zawiera wszystkie zero i jednoelementowe elementy <math>\displaystyle X</math> -- jest ich przeliczalnie wiele, bo każdy z nich jest podzbiorem <math>\displaystyle \mathbb{N}</math>. Pozostaje wykazać, że <math>\displaystyle X'</math> jest przeliczalny i wtedy <math>\displaystyle X</math> jako unia dwóch zbiorów przeliczalnych będzie również przeliczalny. Aby wykazać, że <math>\displaystyle X'</math> jest przeliczalny, ustawmy funkcję <math>\displaystyle f:X'\to \mathbb{N}\times\mathbb{N}</math> taką, że:
  
<center><math>\displaystyle f(x) = (n,m)  </math>  jeśli <math>\displaystyle n</math> jest najmniejszym elementem <math>\displaystyle x</math>, a <math>\displaystyle m</math> jest najmniejszym w <math>\displaystyle x\setminus\{n\}\displaystyle  .
+
<center><math>\displaystyle f(x) = (n,m), </math>  jeśli <math>\displaystyle n</math> jest najmniejszym elementem <math>\displaystyle x</math>, a <math>\displaystyle m</math> jest najmniejszym w <math>\displaystyle x\setminus\{n\}\displaystyle  .
 
</math></center>
 
</math></center>
  
Funkcja <math>\displaystyle f</math> jest dobrze zdefiniowana i prowadzi w zbiór przeliczalny. Pozostaje wykazać, że <math>\displaystyle f</math> jest iniekcją. Jeśli <math>\displaystyle f(x) = (n,m)=f(x')</math>, to <math>\displaystyle x\cap x' \supset \{ n,m\}</math> gdzie <math>\displaystyle n\neq m</math>. Wnioskujemy, że przecięcie <math>\displaystyle x</math> i <math>\displaystyle x'</math> jest co najmniej dwuelementowe, czyli, że <math>\displaystyle x=x'</math> i funkcja <math>\displaystyle f</math> jest iniekcją, co należało wykazać.
+
Funkcja <math>\displaystyle f</math> jest dobrze zdefiniowana i prowadzi w zbiór przeliczalny. Pozostaje wykazać, że <math>\displaystyle f</math> jest iniekcją. Jeśli <math>\displaystyle f(x) = (n,m)=f(x')</math>, to <math>\displaystyle x\cap x' \supset \{ n,m\}</math>, gdzie <math>\displaystyle n\neq m</math>. Wnioskujemy, że przecięcie <math>\displaystyle x</math> i <math>\displaystyle x'</math> jest co najmniej dwuelementowe, czyli, że <math>\displaystyle x=x'</math> i funkcja <math>\displaystyle f</math> jest iniekcją, co należało wykazać.
 
</div></div>
 
</div></div>

Wersja z 19:04, 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 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