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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 .

Element nazywamy minimalnym w porządku , gdy .

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. ,
  2. .

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

Definicja 1.5.

. Element nazywamy infimum zbioru , gdy:

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 je 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:

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

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 niemają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 jest uporządkowany 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

Ć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:

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:

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ądku 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 (patrz Wykład 9, Twierdzenie Cantora). 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 Cauchy'ego, jak i to, że są równoważne w sensie definicji liczb rzeczywistych. Zatem istnieje liczba rzeczywista zadana jednocześnie przez aproksymacje i , czyli . 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