1 Matematyka Dyskretna, G.Mirkowska PJWSTKWykład 5 Zbiory uporządkowane 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

2 Matematyka Dyskretna, G.Mirkowska PJWSTKx  x Definicja jeśli xy i yx, to x=y jeśli xy i yz, to x  z Relację binarną  w zbiorze X nazywamy porządkiem (częściowym porządkiem) wttw jest to relacja zwrotna, antysymetryczna i przechodnia. Zbiór X wraz z porządkiem  nazywamy zbiorem uporządkowanym. Ozn. Przykład 1. , 2.< P(X),  >, Uwaga Jeśli x  y i x  y, to piszemy x 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

3 Matematyka Dyskretna, G.Mirkowska PJWSTKDiagramy Hassego powrót Diagramem Hassego relacji porządku  w X nazywamy graf zorientowany (skierowany) G= , gdzie V=X oraz (x,y)E wttw x y oraz nie istnieje z, takie że z x i z y i x z  y ( y jest bezpośrednim następnikiem x w sensie relacji ). Konwencja Zwykle nie rysujemy strzałek i jeśli x  y i xy, to y znajduje się na grafie Hassego wyżej niż x. 7 8 9 4 2 1 3 5 Przykład Relacja | w zbiorze {1,2,...9} jest relacją porządku Diagram Hassego 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

4 Matematyka Dyskretna, G.Mirkowska PJWSTKDiagram Hassego relacji r w zbiorze S* Przykład Niech S ={0,1}. W zbiorze S * definiujemy relację w1 r w2 wttw istnieje zS *, że w1 z = w2 e Uwaga Niektóre zbiory częściowo uporządkowane nie mają diagramu Hassego, np.: . Każdy skończony zbiór częściowo uporządkowany ma diagram Hassego. 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

5 Matematyka Dyskretna, G.Mirkowska PJWSTKPrzykład Diagram Hassego pewnej relacji Z diagramu Hassego można odczytać pełną informację o opisanej relacji porządku. e f X={a,b,c,d,e,f} a  b a  c a  d b  e b  f c  f a  e a  f a  a b  b c  c d  d e  e f  f b c d a 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

6 Matematyka Dyskretna, G.Mirkowska PJWSTKMinima i maksima Niech  będzie relacją porządku w X. Element x nazywamy maksymalnym, jeżeli w X nie istnieje element y większy od x tzn. taki, że x < y. przykład Element x nazywamy minimalnym, jeżeli w X nie istnieje żaden element y taki, że y < x. Uwaga W diagramie Hassego relacji  elementy maksymalne znajdują się na górze a elementy minimalne na dole grafu. 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

7 Matematyka Dyskretna, G.Mirkowska PJWSTKDefinicje c.d. Jeżeli x  x0 dla wszystkich x X, to x0 nazywamy elementem największym zbioru X. Jeżeli x0  x dla wszystkich x X, to x0 nazywamy elementem najmniejszym zbioru X. Uwaga W zbiorze X może być więcej niż jeden element maksymalny lub minimalny ale jest co najwyżej jeden element największy i co najwyżej jeden element najmniejszy. 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

8 Matematyka Dyskretna, G.Mirkowska PJWSTKKresy Sup(A) Niech  będzie relacją porządku w X oraz niech A będzie podzbiorem X. Ograniczeniem górnym zbioru A w X nazywamy taki element x0  X, że x  x0 dla wszystkich x  A. Najmniejsze ograniczenie górne zbioru A nazywamy kresem górnym (supremum). Ograniczeniem dolnym zbioru A w X nazywamy taki element x0  X, że x0  x dla wszystkich x  A. Największe ograniczenie dolne zbioru A nazywamy kresem dolnym (infimum). Inf(A) 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

9 Przykład Rozważmy relacje  w N : x  y wttw x jest dzielnikiem y.Jest to relacja porządku. Sup(n,m)= najmniejsza wspólna wielokrotność liczb n, m Co jest kresem górnym zbioru {n,m}, tzn. sup{n,m}? Inf{n,m}= największy wspólny dzielnik A kres dolny? Tzn., inf{n,m} =? 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

10 Matematyka Dyskretna, G.Mirkowska PJWSTKPrzykład Sześcian kolorów RGB Krata RG RB GB Dla dowolnych dwóch elem. istnieje kres górny i kres dolny. R G B 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

11 Matematyka Dyskretna, G.Mirkowska PJWSTKPorządek liniowy łańcuch Relację binarną  w zbiorze X nazywamy porządkiem liniowym wttw  jest porządkiem częściowym oraz ma następującą własność spójności: dla dowolnych x, y  X, albo x  y albo y  x albo x = y Przykład Zbiór liczb wymiernych jest liniowo uporządkowany przez relację niewiększości  . Co więcej jest to zbiór liniowo uporządkowany gęsto. Twierdzenie W każdym niepustym zbiorze liniowo uporządkowanym i skończonym istnieje element najmniejszy (pierwszy) i element największy(ostatni). 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

12 Porządek leksykograficznyPrzykład Porządek leksykograficzny Niech będą zbiory (X1, 1), (X 2, 2), ..., (X n, n), liniowo uporządkowne. Definiujemy relację w  produkcie (X1  X 2 .... ,X n) następująco: (x1, x2,...xn)  (t1,..., tn) wttw istnieje takie i, że x1 = t1,...,x2 =t2,...xi-1 = ti-1, oraz xi i ti xi ti Przykład Xi ={0,1,...,9} dla i =1,2,...5 Wtedy 1234 5  23245 Tak zdefiniowana relacja jest relacją porządku liniowego w produkcie (X1  X 2 .... ,X n). 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

13 Matematyka Dyskretna, G.Mirkowska PJWSTKPorządek słownikowy Niech będzie dany alfabet S oraz pewna relacja  liniowego porządku w S. Rozważamy relację  w zbiorze słów S* zdefiniowaną następująco: a1a2...an  b1... bm wttw n kos  kosmita  kosmologia  kosmonauta  kosmos 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

14 Matematyka Dyskretna, G.Mirkowska PJWSTKLemat Kuratowski (1922) - Zorn(1935) Jeżeli w zbiorze uporządkowanym X dla każdego łańcucha istnieje ograniczenie górne, to w X istnieje element maksymalny. Gödel niesprzeczność Cohen1963 niezależność Aksjomat wyboru 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK

15 Matematyka Dyskretna, G.Mirkowska PJWSTKDobry porządek Relację binarną  w zbiorze X nazywamy dobrym porządkiem wttw  jest liniowym porządkiem oraz dla dowolnego niepustego podzbioru A zbioru X istnieje element minimalny. Przykłady (1) Zbiór jest dobrze uporządkowany przez relację niewiększości  . (2) Każdy zbiór skończony, liniowo uporządkowany jest dobrze uporządkowany. (3) Zbiór liczb rzeczywistych nie jest dobrze uporządkowany przez relację niewiększości . 31 października 2001 Matematyka Dyskretna, G.Mirkowska PJWSTK