następny punkt »


1. Relacje porządkujące

Definicja 5.1

Relację binarną á w zbiorze X nazywamy relacją porządku częściowego lub krótko relacją porządku wtedy i tylko wtedy, gdy jest ona zwrotna, antysymetryczna i przechodnia, tzn. dla wszystkich x, y, z Î X,

  1. x á x,
  2. x á y i y á x implikuje x = y,
  3. x á y i y á z implikuje x á z.

Relacje porządku zwykle będziemy oznaczać symbolem á . Zbiór, w którym określona jest relacja porządku nazywamy uporządkowanym, co zapisujemy <X, á >. Jeśli chcemy zaznaczyć, że relacja á zachodzi między elementami x i y, ale są one różne, to piszemy x á y, podobnie jak to czynimy w przypadku relacji £ w zbiorze R.

Rys. 5.1 Przykłady zbiorów częściowo uporządkowanych.

Na rysunku 5.1 przedstawiliśmy przykłady grafów ilustrujących pewne zbiory uporządkowane. Graf na rysunku 5.1a przedstawia relację porządku częściowego. Jest to oczywiście relacja zwrotna, ale jest też antysymetryczna i przechodnia. Nie zachodzi dla żadnej pary różnych elementów, czyli poprzedniki w implikacjach (2) i (3) definicji 5.1 nigdy nie są spełnione a zatem implikacje (2), (3) są prawdziwe. Graf na rysunku 5.1b przedstawia relacje porządku z tych samych powodów. Tu jednak, w przeciwieństwie do 5.1a, potrafimy porównać niektóre różne elementy: a á b i a á c. Relacja przedstawiona na rysunku 5.1c, pozwala ustawić wszystkie elementy w ciąg a á c á b. Podobnie w przypadku grafu 5.1d, gdzie każde dwa elementy można ze sobą porównać.

Pytanie 1: Czy graf pełny jest ilustracją zbioru uporządkowanego?

Zobacz odpowiedź

Przykład 5.1

  1. Jako pierwszy przykład relacji porządku weźmy relację £ w zbiorze liczb rzeczywistych. Oczywiście dla dowolnych liczb rzeczywistych x, y, z Î R mamy x £ x, jeśli x £ y i y £ x, to x = y, jeśli x £ y i y £ z, to x £ z. Wynika stąd również, że zbiory liczb naturalnych N, liczb wymiernych Q, liczb całkowitych Z są uporządkowane przez relację £ .
  2. Relacja á określona w zbiorze wszystkich funkcji z R w R, RR, taka że dla f, gÎ RR
    f á g wttw dla dowolnego xÎ R, f(x) £ g(x),
    jest relacją porządku w RR. Rzeczywiście, f(x) £ f(x) dla dowolnego xÎ R, czyli á jest zwrotna. Niech f á g i g á f i niech x będzie ustaloną liczbą rzeczywistą. Ponieważ, na mocy pierwszego założenia, f(x) £ g(x) oraz g(x) £ f(x) na mocy drugiego założenia, to z antysymetrii relacji £ mamy f(x)=g(x). Rozumowanie to można powtórzyć dla wszystkich x Î R, dowodząc tym samym, że dla każdego xÎ R, f(x) = g(x). Czyli f = g. Dla dowodu przechodniości relacji á załóżmy, że f á g i g á h. Weźmy dowolną liczbę rzeczywistą x. Na mocy założeń mamy f(x) £ g(x) i g(x) £ h(x). Korzystając teraz z przechodniości relacji £ , otrzymujemy f(x) £ h(x). Powtarzając to samo rozumowanie dla wszystkich xÎ R dojdziemy do wniosku, że f á h.
    Zatem relacja á jest przechodnia, co kończy dowód, że á jest również relacją porządku.
  3. Relacja przedstawiona w poprzednim przykładzie wykorzystywała w istotny sposób własności relacji £ w zbiorze liczb rzeczywistych. Może się wydawać, że użycie relacji £ w definicji wystarcza aby nowa relacja była porządkiem. Tak jednak nie jest. Rozważmy relację r określoną w zbiorze funkcji R+N, taką że
    f r g wttw istnieją dodatnie stałe c i n0, że f(n) £ c*g(n) dla n > n0.
    Zgodnie z naszą definicją, funkcje f i g są w relacji r, jeśli f = O(g), tzn. g szacuje z góry funkcję f (por. punkt 3.6). Tak zdefiniowana relacja jest zwrotna i przechodnia, ale nie jest antysytmetryczna. Niech f(n) = 2n i g(n) = 5n. Wtedy dla wszystkich n mamy f(n) £ g(n) oraz dla wszystkich nÎ N, g(n) £ 5 f(n). Wynika stąd, że f = O(g) i g = O(f), mimo że f i g nie są równe (f ¹ g).

Pytanie 2: Czy relacja mniejszości < w zbiorze liczb rzeczywistych jest relacją porządku?


 następny punkt »