« poprzedni punkt  następny punkt »


2. Diagramy Hasse

Relacje porządku, tak jak inne relacje, można ilustrować przy pomocy grafów. Jednak zwykle duża liczba krawędzi i występujące pętle (jako konsekwencja zwrotności i przechodniości) sprawiają, że rysunek taki nie zawsze jest czytelny. Wygodnym sposobem przedstawiania porządku są natomiast diagramy Hassego.

Definicja 5.2

Diagramem Hassego relacji porządku á w zbiorze X nazywamy graf niezorientowany G = <X, E>, którego zbiorem wierzchołków jest zbiór X , a krawędzie są określone następująco

(x,y) Î E wttw x á y i nie istnieje zÎ X, że z¹ x, y¹ x i x á z i z á y

Jeśli para (x,y) tworzy krawędź, to mówimy, że y jest bezpośrednim następnikiem x.

Zwykle, zamiast strzałek łączących wierzchołki w grafie zorientowanym, w diagramach Hassego krawędzie zaznaczamy odcinkami, w taki sposób, by koniec krawędzi znajdował się na rysunku powyżej początku krawędzi.

Rys. 5.2 Diagram Hassego

  1. relacji inkluzji w zbiorze wszystkich podzbiorów zbioru{R, G, B},
  2. relacji podzielności w zbiorze {1,2,3...9}.

Przykład 5.2

(1) Relacja Í inkluzji w zbiorze wszystkich podzbiorów pewnego zbioru X jest relacją porządku częściowego. Oczywiście jest zwrotna, bo AÍ A. Jest też antysymetryczna, ponieważ A Í B i B Í A implikuje A=B. Relacja jest też przechodnia, bo z założeń A Í B i B Í C wynika natychmiast A Í C (por. punkt 1.2).

Zauważmy, że nie wszystkie zbiory należące do P(X) dają się porównać przy pomocy relacji Í . Jeśli x i y są różnymi elementami zbioru X, to mamy {x}Î P(X), {y}Î P(X), ale ani nie zachodzi {x}Í {y}, ani nie zachodzi {y}Í {x}.

Diagram Hassego relacji Í w przypadku, gdy X = {R,G,B} przedstawiono na rysunku 5.2a.

(2) Relacja podzielności | określona w zbiorze liczb naturalnych

x|y wttw x jest dzielnikiem y

jest relacją porządku. Rzeczywiście, relacja podzielności (por. przykład 2.7) jest zwrotna, antysymetryczna i przechodnia. Na rysunku 2.6b przedstawiono graf tej relacji ograniczonej tylko do zbioru {1, 2, 3, ...9}. Rysunek 5.2b przedstawia diagram Hassego tej relacji. Podobnie jak w poprzednim przykładzie, istnieją takie liczby naturalne, których nie możemy porównać przy pomocy |. Na przykład 2 nie jest dzielnikiem 3 i 3 nie jest dzielnikiem 2.

(3) Niech S = {0, 1}. W zbiorze S* zdefiniujemy relację á następująco:

w á w' wttw istnieje słowo w" Î S*, że ww" = w'.

Słowo ww "zostało utworzone ze słowa w przez dopisanie na jego końcu słowa w". Taką operacje na słowach nazywamy konkatenacją. Na przykład, konkatenacja słów "para" i "lotnia" daje słowo "paralotnia".

Jeżeli w' á w, to mówimy, że w' jest segmentem początkowym lub prefiksem słowa w. Relacja á w zbiorze {0,1}* definiuje porządek częściowy. Diagram Hassego tego porządku, z konieczności ograniczyliśmy do kilkunastu elementów, por Rys.5.3. Sam zbiór {0,1}* jest przecież nieskończony.

Rys. 5.3 Diagram Hassego relacji częściowego porządku w zbiorze słów na alfabetem {0,1}, por. przykład 5.2(3).

Uwaga.

  1. Każdy skończony zbiór częściowo uporządkowany ma diagram Hassego.

  2. Nie każdy zbiór częściowo uporządkowany ma diagram Hassego. Przykładem takiego zbioru jest <R,£ >. Żadna para liczb rzeczywistych (x,y) nie może tworzyć krawędzi w diagramie Hasse relacji £ w zbiorze R, bo między dowolnymi dwoma różnymi liczbami rzeczywistymi zawsze można znaleźć inną od nich liczbę rzeczywistą (np. (x+y)/2).

Pytanie 3: Czy istnieje diagram Hasse dla zbioru uporządkowanego <Q, £ >?

Zobacz odpowiedź


« poprzedni punkt  następny punkt »