Logika i teoria mnogości/Wykład 10: Zbiory uporządkowane. Zbiory liniowo uporządkowane. Pojęcia gęstości i ciągłości: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 803: Linia 803:
 
Wiemy, że porządek <math>\displaystyle (\mathbb R, \leq)</math> jest ciągły. Analogiczne rozumowanie do rozwiązania zadania 2.18 (patrz [[#cwiczenie_2_18|ćwiczenie 2.18.]]) prowadzi do udowodnienia nieciągłości <math>\displaystyle (\mathbb R\setminus \mathbb{Q}, \leq)</math> (w roli <math>\displaystyle \rho</math> tym razem bierzemy liczbą wymierną). Ponieważ ciągłość jest przenoszona przez podobieństwo to porządki te nie mogą być podobne.
 
Wiemy, że porządek <math>\displaystyle (\mathbb R, \leq)</math> jest ciągły. Analogiczne rozumowanie do rozwiązania zadania 2.18 (patrz [[#cwiczenie_2_18|ćwiczenie 2.18.]]) prowadzi do udowodnienia nieciągłości <math>\displaystyle (\mathbb R\setminus \mathbb{Q}, \leq)</math> (w roli <math>\displaystyle \rho</math> tym razem bierzemy liczbą wymierną). Ponieważ ciągłość jest przenoszona przez podobieństwo to porządki te nie mogą być podobne.
 
</div></div>
 
</div></div>
 
==Twierdzenie Bourbaki- Witt==
 
 
Rozdział ten jest poświęcony twierdzeniu z którego będziemy korzystali w wykładzie 11
 
dotyczącym dyskusji nad aksjomatem wyboru.
 
 
Wprowadzamy podstawowe definicje
 
 
{{definicja|3.1.||
 
 
Mówimy, że poset <math>\displaystyle (A,\sqsubseteq)</math> jest ''łańcuchowo zupełny'' jeśli każdy
 
łańcuch posiada supremum.
 
}}
 
 
{{definicja|3.2.||
 
 
Dla posetu <math>\displaystyle (A,\sqsubseteq)</math> funkcję <math>\displaystyle f</math> przeprowadzającą <math>\displaystyle A</math> w <math>\displaystyle A</math> i taka, że <math>\displaystyle x\sqsubseteq
 
f(x)</math> dla dowolnego <math>\displaystyle x\in A</math> nazywamy ''progresją''.
 
}}
 
 
{{twierdzenie|3.3. [Bourbaki-Witt]||
 
 
Każda progresja na łańcuchowo zupełnym posecie posiada punkt stały.
 
}}
 
 
Dowód:
 
 
W czasie tego dowodu zostaną pokazane dodatkowo dwa lematy 3.1 i 3.2 (patrz [[#lemat_3_1|lemat 3.1.]] i [[#lemat_3_2|lemat 3.2.]]). Są one częścią całego dowodu.
 
Ustalmy łańcuchowo zupełny poset
 
<math>\displaystyle (A,\sqsubseteq)</math> i progresję <math>\displaystyle f</math> operującą na nim. W dowodzie niezbędna jest
 
koncepcja zbiorów, które nazwiemy "miłymi". Ustalmy dowolny element <math>\displaystyle a\in A</math>. Zbiór
 
<math>\displaystyle B\subseteq A</math> jest miły jeśli spełnia wszystkie poniższe warunki:
 
* <math>\displaystyle a\in B</math>,
 
* jeśli <math>\displaystyle x\in B</math> to również <math>\displaystyle f(x)\in B</math> i
 
* jeśli <math>\displaystyle C\subseteq B</math> jest łańcuchem w <math>\displaystyle (A,\sqsubseteq)</math>, to <math>\displaystyle \bigvee C\in B</math>.
 
 
Bardzo łatwo zauważyć, że przecięcie dowolnej rodziny miłych pozdbiorów jest miłe.
 
Zdefiniujmy "najmilszy" podzbiór <math>\displaystyle B_0</math> jako
 
 
<center><math>\displaystyle B_0 = \bigcap\{B\subseteq A\,|\, \text{B jest miły}\},
 
</math></center>
 
 
wtedy <math>\displaystyle B_0</math> jest oczywiście miły. Równocześnie <math>\displaystyle B_0</math> jest podzbiorem każdego miłego
 
zbioru. Wykażmy parę własności elementów zbioru <math>\displaystyle B_0</math>.  Po pierwsze żaden element
 
istotnie mniejszy niż <math>\displaystyle a</math> nie jest elementem <math>\displaystyle B_0</math> - jest to oczywistą konsekwencją
 
faktu, że zbiór <math>\displaystyle \{x\in A\,|\, x\geq a\}</math> jest miły, więc jest nadzbiorem <math>\displaystyle B_0</math>.
 
 
Zdefiniujmy jeszcze mniejszy zbiór
 
 
<center><math>\displaystyle B_0' = \{x\in B_0\,|\, \forall y\in B_0\; y\sqsubset x  \implies f(y)\sqsubseteq x\}\subseteq
 
B_0
 
</math></center>
 
 
i wykażmy parę faktów o elementach <math>\displaystyle B_0'</math>.
 
 
<span id="lemat_3_1">{{lemat|3.1.||
 
 
Jeśli <math>\displaystyle x\in B_0'</math> to, dla każdego <math>\displaystyle y\in B_0</math> mamy <math>\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y</math>.
 
}}</span>
 
 
{{dowod|||
 
 
Ustalmy dowolny <math>\displaystyle x\in B_0'</math> i zdefiniujmy zbiór
 
 
<center><math>\displaystyle B_x = \{y\in B_0\,|\, y\sqsubseteq x\lor f(x)\sqsubseteq y \}.
 
</math></center>
 
 
Wykażemy, że zbiór <math>\displaystyle B_x</math> jest miły i, co za tym idzie, że <math>\displaystyle B_x = B_0</math>.
 
* <math>\displaystyle a\in B_x</math>, ponieważ wiemy, że <math>\displaystyle a\sqsubseteq x</math> dla dowolnego <math>\displaystyle x\in B_0</math>,
 
* Załóżmy teraz, że <math>\displaystyle y\in B_x</math> i wykażmy <math>\displaystyle f(y)\in B_x</math>. Jeśli <math>\displaystyle y\in B_x</math> na mocy <math>\displaystyle f(x)\sqsubseteq y</math>, to niewątpliwie <math>\displaystyle f(x)\sqsubseteq f(y)</math> co kończy ten przypadek. Jeśli natomiast <math>\displaystyle y\sqsubseteq x</math>, to albo <math>\displaystyle y=x</math> i wtedy <math>\displaystyle f(x)\sqsubseteq f(y)</math>, albo <math>\displaystyle y\sqsubset x</math> i wtedy, na mocy definicji <math>\displaystyle B_0'</math> mamy <math>\displaystyle f(y)\sqsubseteq x</math> co dowodzi, że również w tym przypadku <math>\displaystyle f(y)\in B_x</math>.
 
* Jeśli <math>\displaystyle C\subseteq B_x</math> jest łańcuchem i dla wszystkich <math>\displaystyle y\in C</math> zachodzi <math>\displaystyle y\sqsubseteq x</math>, to również <math>\displaystyle \bigvee C\sqsubseteq x</math> i <math>\displaystyle \bigvee C\in B_x</math>. Jeśli dla pewnego <math>\displaystyle y\in C</math>  mamy <math>\displaystyle f(x)\sqsubseteq y</math> to również <math>\displaystyle f(x)\sqsubseteq\bigvee C</math> co należało dowieść.
 
 
}}
 
 
W kolejnym lemacie dowodzimy, że zbiory <math>\displaystyle B_0'</math> i <math>\displaystyle B_0</math> są równe
 
 
<span id="lemat_3_2">{{lemat|3.2.||
 
 
Zbiór <math>\displaystyle B_0'</math> jest miły.
 
}}</span>
 
 
{{dowod|||
 
 
Wykażemy, że zbiór <math>\displaystyle B_0'</math> jest miły a więc
 
* <math>\displaystyle a\in B_0'</math>, ponieważ wykazaliśmy wcześniej, że <math>\displaystyle y\sqsubset a</math> nie zachodzi dla żadnego <math>\displaystyle y\in B_0</math>.
 
* Ustalmy <math>\displaystyle x\in B_0'</math>, żeby wykazać <math>\displaystyle f(x)\in B_0'</math> ustalmy <math>\displaystyle y\in B_0</math> takie, że <math>\displaystyle y\sqsubset f(x)</math>. Na mocy Lematu 3.1 (patrz [[#lemat_3_1|lemat 3.1.]]) dostajemy <math>\displaystyle y\sqsubseteq x\lor f(x)\sqsubseteq y</math>. Druga część alternatywy stoi w sprzeczności z założeniem, więc <math>\displaystyle y\sqsubseteq x</math> i albo <math>\displaystyle y=x</math>, więc <math>\displaystyle f(y)\sqsubseteq f(x)</math>, albo <math>\displaystyle y\sqsubset x</math> i na mocy założenia <math>\displaystyle f(y)\sqsubseteq x\sqsubseteq f(x)</math> co  należało pokazać.
 
* Ustalmy dowolny <math>\displaystyle C\subseteq B_0'</math> łańcuch w <math>\displaystyle (A,\sqsubseteq)</math>. Załóżmy, że <math>\displaystyle y\sqsubset \bigvee C</math>. Jeśli dla jakiegoś <math>\displaystyle x\in C</math> mamy <math>\displaystyle y\sqsubset x</math> wtedy <math>\displaystyle f(y)\sqsubseteq x\sqsubseteq \bigvee C</math>, co należało pokazać. Przeciwny przypadek jest niemożliwy na podstawie Lematu 3.1. (patrz [[#lemat_3_1|lemat 3.1.]]). Mielibyśmy wtedy dla każdego <math>\displaystyle x\in C</math> prawdziwe <math>\displaystyle x=y</math> lub <math>\displaystyle x\sqsubseteq f(x)\sqsubseteq y</math> co jest sprzeczne z założeniem mówiącym, że <math>\displaystyle y\sqsubset \bigvee C</math>.
 
}}
 
 
Tak więc <math>\displaystyle B_0' = B_0</math>, czyli dla dowolnych <math>\displaystyle x</math> i <math>\displaystyle y</math> w <math>\displaystyle B_0</math> mamy, na podstawie
 
Lematu 3.1 (patrz [[#lemat_3_1|lemat 3.1.]]), <math>\displaystyle y\sqsubseteq x</math> lub <math>\displaystyle  x\sqsubseteq f(x)\sqsubseteq y</math>. Wnioskujemy, że <math>\displaystyle B_0</math> jest
 
uporządkowany liniowo, czyli jest łańcuchem. Niewątplwie <math>\displaystyle \bigvee B_0 \in B_0</math>&nbsp;(na
 
podstawie definicji zbiorów miłych) i <math>\displaystyle f(\bigvee B_0)\in B_0</math>&nbsp;(na podstawie tej samej
 
definicji), więc <math>\displaystyle f(\bigvee B_0) = \bigvee B_0</math> co dowodzi istnienia punktu stałego
 
odwzorowania <math>\displaystyle f</math>.
 

Wersja z 14:51, 16 wrz 2006

Zbiory uporządkowane

Definicja 1.1.

Porządkiem (w wielu podręcznikach jest używana jest również nazwa poset, pochodząca od angielskiego skrótu - partially ordered set) nazywamy parę gdzie jest zbiorem a jest relacją

  1. zwrotną
  2. przechodnią
  3. antysymetryczną, to znaczy jeżeli oraz , to .

Jeżeli dodatkowo relacja jest spójna (to znaczy taka, że lub ) to porządek nazywamy liniowym.

Często oznaczamy relacje porządkującą jako . Oznaczamy też gdy , oraz .

Definicja 1.2.

Element nazywamy maksymalnym w porządku gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x\in X} \;\; a\leq x \hspace*{0.1mm} \Rightarrow a=x}

Element nazywamy minimalnym w porządku gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x\in X} \;\; x \leq a \hspace*{0.1mm} \Rightarrow a=x}

Element nazywamy największym w porządku gdy

Element nazywamy najmniejszym w porządku gdy

Definicja 1.3.

Niech oraz . Mówimy że jest majorantą zbioru gdy .

Niech oraz . Mówimy że jest minorantą zbioru gdy .

Definicja 1.4.

. Element nazywamy supremum zbioru gdy:

  1. Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (\forall_{a\in A} \;\; a \leq b) \hspace*{0.1mm} \Rightarrow a_0 \leq b}

Łatwo zauważyć, że supremum o ile istnieje jest jedyne i jest najmniejszą z majorant. Jeżeli istnieje supremum dla będziemy go oznaczać .

Definicja 1.5.

. Element nazywamy infimum zbioru gdy:

  1. Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle (\forall_{a \in A} \;\; b \leq a )\hspace*{0.1mm} \Rightarrow b \leq b_0}

Tak jak w przypadku supremum infimum o ile istnieje jest jedyne i jest największą z minorant zbioru. Jeżeli istnieje infimum dla będziemy go oznaczać .

Ćwiczenie 1.6

Niech będzie ustalonym zbiorem i niech . Zdefiniujmy relację następująco

Udowodnij, że jest zbiorem uporządkowanym.

Rozwiązanie
Uwaga 1.7.

Nadużywając notacji będziemy czasem używać symbolu dla oznaczenia relacji zdefiniowanej w poprzednim ćwiczeniu. Zwracamy przy tym uwagę, że nie ma czegoś takiego jak relacja , gdyż musiałaby ona być określona w zbiorze wszystkich zbiorów, który nie istnieje. W przypadku jednak gdy rozważamy jedynie podzbiory ustalonego zbioru możemy mówić o relacji bycia podzbiorem. Czasem dla podkreślenia, że mówimy o podzbiorach ustalonego zbioru będziemy pisać .

Ćwiczenie 1.8

{{{3}}}
Rozwiązanie

Ćwiczenie 1.9

W zbiorze liczb naturalnych zdefiniujemy relację następująco

Udowodnij, że relacja ta porządkuje zbiór . Czy w tak uporządkowanym zbiorze istnieją elementy najmniejszy i największy?

Rozwiązanie

Ćwiczenie 1.10

W zbiorze funkcji z w (czyli ) zdefiniujmy relację następująco

Wskazówka
Rozwiązanie

Ćwiczenie 1.11

Niech . W zbiorze zdefiniujemy relację następująco

Sprawdź, czy relacja jest zwrotna, przechodnia i antysymetryczna.

Wskazówka
Rozwiązanie

Ćwiczenie 1.12

Niech . W zbiorze zdefiniujemy relację następująco

Udowodnij, że relacja porządkuje zbiór . Czy w porządku istnieją elementy najmniejszy i największy?

Rozwiązanie

Ćwiczenie 1.13

Podaj przykład przeliczalnego porządku w którym istnieje element najmniejszy i największy.

Rozwiązanie

Ćwiczenie 1.14

Podaj przykład porządku w którym istnieje element maksymalny, który nie jest elementem największym. Czy istnieje taki porządek, żeby element maksymalny był jedyny?

Rozwiązanie

Ćwiczenie 1.15

Podaj przykład zbioru liniowo uporządkowanego w którym istnieje podzbiór nie mający supremum.

Rozwiązanie

Ćwiczenie 1.16

Udowodnij, że zbiorze uporządkowanym istnieje wtedy i tylko wtedy gdy w istnieje element najmniejszy.

Rozwiązanie

Ćwiczenie 1.17

Udowodnij, że zbiorze uporządkowanym jeśli każdy podzbiór ma supremum to każdy podzbiór ma infimum.

Rozwiązanie

Ćwiczenie 1.18

Podaj przykład porządku takiego, że podzbiór ma supremum wtedy i tylko wtedy gdy jest skończony.

Rozwiązanie

Definicja 1.19

jest łańcuchem w porządku gdy każde dwa elementy są porównywalne w sensie . Oznacza to, że porządek indukowany na zbiorze czyli jest porządkiem liniowym.

Definicja 1.20.

Zbiór jest antyłańcuchem w porządku , gdy żadne dwa różne elementy nie są porównywalne w sensie . Formalnie, jeśli następująca formuła jest prawdziwa

Ćwiczenie 1.21

Sprawdź, czy suma antyłańcuchów musi być antyłańcychem oraz czy suma łańcuchów musi być łańcuchem.

Rozwiązanie

Ćwiczenie 1.22

Czy antyłańcuch może być łańcuchem?

Rozwiązanie

Dla każdego porządku , zarówno zbiór jego łańcuchów jak i zbiór jego antyłańcuchów są uporządkowane przez inkluzję. Możemy więc mówić o największym (maksymalnym) ze względu na inkluzję łańcuchu (antyłańcuchu). Łatwo można pokazać, że zawsze istnieje najmniejszy łańcuch i antyłańcuch. Istnienie w każdym posecie maksymalnego łańcucha jest równoważne aksjomatowi wyboru. Tym zagadnieniem zajmujemy się w Wykładzie 11.

Ćwiczenie 1.23

Podaj przykład porządku w których nie istnieje największy w sensie inkluzji łańcuch, ani antyłańcuch.

Rozwiązanie

Ćwiczenie 1.24

Kiedy w porządku istnieje największy w sensie inkluzji łańcuch.

Rozwiązanie

Ćwiczenie 1.25

Kiedy w porządku istnieje największy w sensie inkluzji antyłańcuch.

Rozwiązanie

Ćwiczenie 1.26

Czy porządek w którym każdy łańcuch jest skończony musi być skończony? Czy taki porządek może zawierać łańcuchy o dowolnie dużej skończonej mocy?

Rozwiązanie

Ćwiczenie 1.27

Rozważmy zbiór uporządkowany relacją podzielności (czyli ). Wypisz wszystkie łańcuchy maksymalne w sensie inkluzji. Wypisz wszystkie antyłańcuchy maksymalne w sensie inkluzji.

Rozwiązanie

Zbiory liniowo uporządkowane

Definicja 2.1.

Porządki liniowe i nazywamy podobnymi gdy istnieje bijekcja rosnąca czyli taka że jeżeli to .

Ćwiczenie 2.2

Dla podobieństwa jeżeli to

Rozwiązanie

Definicja 2.3.

Porządek nazywamy gęstym gdy Parser nie mógł rozpoznać (nieznana funkcja „\hspace”): {\displaystyle \displaystyle \forall_{x,y\in X} \;\; x<y \hspace*{0.1mm} \Rightarrow \exists_{z\in X} \;\; x<z<y}

Ćwiczenie 2.4

Gęstość jest przenoszona przez podobieństwo.

Rozwiązanie

Ćwiczenie 2.5

W zbiorze rozważymy dwie relacje porządkujące zdefiniowane następująco

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned f \sqsubseteq_1 g \Leftrightarrow \forall_{n \in \mathbb{N}} f(n) \leq g(n),\\ f \sqsubseteq_2 g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n) < g(n)\wedge \forall_{n<n_0} f(n) =g(n))]. \endaligned}

Sprawdź, czy te porządki są podobne.

Wskazówka
Rozwiązanie

Definicja 2.6.

Niech będzie porządkiem liniowym. Przekrojem Dedekinda w nazywamy parę zbiorów taką że:

  1. .
  2. .
  3. .
  4. i .

Definicja 2.7.

Przekrój daje skok jeżeli ma element największy i ma element najmniejszy.

Ćwiczenie 2.8

Liniowy porządek jest gęsty wtedy i tylko wtedy gdy żaden przekrój nie daje skoku.

Rozwiązanie

Ćwiczenie 2.9

W zbiorze rozważymy relację porządkującą zdefiniowaną następująco

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned f \sqsubseteq g \Leftrightarrow [f=g \vee \exists_{n_0 \in \mathbb{N}} (f(n_0) < g(n_0)\wedge \forall_{n<n_0} f(n) =g(n))]. \endaligned}

Sprawdź, czy ten porządek jest gęsty.

Rozwiązanie

Definicja 2.10.

Przekrój daje lukę jeżeli nie ma elementu największego i nie ma elementu najmniejszego.

Definicja 2.11.

Porządek liniowy nazywamy ciągłym wtedy i tylko wtedy gdy żaden przekrój nie daje luki.

Twierdzenie 2.12.

W porządku ciągłym każdy niepusty zbiór ograniczony od góry ma supremum.

Dowód

Niech będzie zbiorem ograniczonym od góry. Łatwo zauważyć, że jeżeli jakieś ograniczenie zbioru należy do to jest jego supremum. Załóżmy zatem, że żadne ograniczenie do nie należy. Utwórzmy parę zbiorów: oraz . Pierwszy jest domknięciem w dół zbioru , czyli wraz z każdym jego elementem dołączamy do niego wszystkie mniejsze. Zatem . Do należą wszystkie ograniczenia górne zbioru więc musi on być niepusty. Z konstrukcji wynika . Korzystając z ciągłości otrzymujemy, że ma element największy lub ma element najmniejszy. Gdy posiada element największy to jest on supremum . Istotnie, element góruje nad więc tym bardziej nad . Gdy element góruje nad to góruje też nad , zatem jeżeli należy do musi być równy , gdy zaś należy do to . W drugim przypadku gdy w nie ma elementu największego, supremum jest najmniejszy element z . Istotnie, góruje nad . Jeżeli jakiś góruje nad to również nad . nie może należeć do bo w nie ma największego. Należy więc do , zatem . Proszę o zwrócenie uwagi na fakt, że możliwe jest aby zarówno miał element największy jak i miał element najmniejszy. Wtedy supremum jest ten pochodzący z .

End of proof.gif

Twierdzenie 2.13.

W porządek liniowym jeżeli każdy niepusty zbiór ograniczony od góry ma supremum to porządek jest ciągły.

Dowód

Weźmy przekrój Dedekinda . jest ograniczony od góry przez elementy z . ma więc supremum . Jeżeli to ma element największy. W przeciwnym przypadku . Gdyby dla pewnego to zbiór miałby mniejsze ograniczenie górne niż . To jest niemożliwe, musi więc być dla każdego . Zatem jest najmniejszy w .

End of proof.gif

Ćwiczenie 2.14

W porządku liniowym każdy niepusty zbiór ograniczony od dołu ma infimum wtedy i tylko wtedy gdy porządek jest ciągły.

Wskazówka

Ćwiczenie 2.15.

Udowodnij, że ciągłość jest przenoszona przez podobieństwo.

Wskazówka
Rozwiązanie

Ćwiczenie 2.16

Pokaż, że zbiór liczb naturalnych jest ciągły.

Wskazówka
Rozwiązanie

Ćwiczenie 2.17

Udowodnij, że dla dowolnych liczb rzeczywistych takich, że istnieje liczba wymierna taka, że .

Rozwiązanie

Ćwiczenie 2.18

Pokaż, że zbiór nie jest ciągły.

Wskazówka
Rozwiązanie

Twierdzenie 2.19.

jest ciągła.

Dowód

Przed przystąpieniem do dowodu przejrzyj dowód twierdzenia Cantora 2.9 z wykładu 9 o nieprzeliczalności . Niech będzie przekrojem w . Zbiory są niepuste. Wybierzmy dwie liczby wymierne w i w . (Sprawdź jako ćwiczenie, że z każdego przekroju da się wybrać liczby wymierne). Skonstruujmy dwa ciągi oraz zdefiniowane indukcyjnie. są zadane.

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 Cauchyego jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista zadana jednocześnie przez aproksymacje i czyli . Gdy to ma element największy. W przeciwnym wypadku i wtedy ma element najmniejszy.

End of proof.gif

Ćwiczenie 2.20

Udowodnij, że porządki i nie są podobne.

Rozwiązanie