« poprzedni punkt |
Dowolny porządek á w zbiorze X pozwala zdefiniować relację porządku w zbiorze par, trójek, i ogólnie n-tek elementów z X. Przyjmijmy dla dowolnych x1, x2,...xn, y1, y2,...yn Î X,
(x1, x2,...xn ) á (y1, y2,...yn) wttw dla wszystkich i £ n , xi á yi.
Rzeczywiście, tak określona relacja jest porządkiem częściowym w Xn. Nazywamy ją porządkiem produktowym.
Pytanie 11 W porządku produktowym na S4, gdzie S oznacza alfabet języka polskiego, który z ciągów jest wcześniejszy (P,J,W,S,T,K) czy (U,W,W,U,U,W)?
W szczególnym przypadku, gdy jako X weźmiemy zbiór liczb naturalnych N z porządkiem £ oraz przyjmiemy n=3, relacja á porządkuje trójki liczb naturalnych. Fragment diagramu Hassego tej relacji przedstawiliśmy na rysunku 5.5.
Rys. 5.5 Fragment diagramu Hassego porządku produktowego w zbiorze N ´ N ´ N.
Jest oczywiste, że taki porządek nie jest liniowy: chociaż trójki (5,4,3) i (1,6,7) są różne, to nie zachodzi ani (5,4,2) á (2,3,8) ani (2,3,8) á (5,4,2).
Czy można, bazując na jakimś danym porządku liniowym w zbiorze X, określić porządek liniowy w zbiorze Xn ?
Wróćmy znów do liczb naturalnych. Gdy n=2, łatwo możemy określić porządek liniowy wśród par liczb naturalnych, wykorzystując funkcję pary f(n, m)= n + (n+m)*(m+n+1)/2 (por. przykład 3.4) oraz zwykły porządek £ w N następująco:
(n, m) á (x, y) wttw f(n, m) £ f(x, y).
Tak określona relacja jest spójna zwrotna i przechodnia, co wynika natychmiast z odpowiednich własności dla relacji £ w zbiorze liczb naturalnych. Antysymetria relacji á wynika z faktu, że f jest funkcją różnowartościową, tzn. (n, m) ¹ (x, y) implikuje f(n, m) ¹ f(x, y). Rzeczywiście, jeśli (n, m) á (x, y) i (x, y) á (m, m), to f(n, m) £ f(x, y) i f(x, y) £ f(n, m). W konsekwencji f(n, m) = f(x, y), a zatem z różnowartościowości funkcji f, (x, y) = (n, m).
Nie zawsze jednak mamy do czynienia z liczbami naturalnymi, co więcej, czasami chcemy uporządkować n-tki obiektów dla n>2. Często obiekty występujące w n-tce nie zależą do tego samego zbioru, np. jedne są liczbami, inne literami, a jeszcze inne słowami. Jak wówczas uporządkować liniowo taki zbiór? Odpowiedzią jest porządek leksykograficzny.
Definicja 5.9
Niech < Xi , á i > dla i =1,...,n, będą zbiorami uporządkowanymi. W produkcie X1 ´ X2 ´ X3 ... ´ Xn określimy relację binarną á * następująco
(x1, x2,...xn ) á * (y1, y2,...yn) wttw albo dla wszystkich i £ n , xi = yi
albo istnieje takie k>0, że dla i<k £ n, xi = yi oraz xk á k yk, xk ¹ yk
Tak zdefiniowana relacja, nazywa się porządkiem leksy słownikowym w X1 ´ X2 ´ ... ´ Xn.
Lemat 5.2
Jeżeli dla wszystkich iÎ I, < Xi, á i > jest zbiorem uporządkowanym, to á * jest porządkiem częściowym w produkcie X1 ´ X2 ´ ... ´ Xn. Jeśli wszystkie zbiory < Xi, á i > dla i Î I, są liniowo uporządkowane, to relacja á * liniowo porządkuje zbiór X1 ´ X2 ´ ... ´ Xn.
Przykład 5.7
Jeśli X1 = X3 = {1, 2,... 9}, X2 = {a, b, ...z} z naturalnymi relacjami liniowego porządku w zbiorze cyfr i zbiorze liter alfabetu, to relacja á * porządkuje liniowo trójki postaci (cyfra, litera, cyfra), w taki sposób że (3,b,2) á * (3,c,1) á * (5,a,2) itd.
Dla nikogo nie jest tajemnicą, że porządek liter w alfabecie pozwala zdefiniować porządek w zbiorze słów nad tym alfabetem: porządek taki spotykamy w każdym słowniku. Jeśli rozważymy tylko słowa o ustalonej długości, to porządek słów indukowany przez porządek alfabetyczny jest zgodny ze zdefiniowanym wyżej porządkiem á *:
kajak á * kojec á * kolec á * pokaz
Słowa występujące w słowniku mają na ogół różne długości. Aby móc je miedzy sobą porównywać wprowadzimy pewne rozszerzenie relacji á * , oznaczone symbolem á L.
Definicja 5.10
Niech S będzie ustalonym alfabetem uporządkowanym liniowo przez relację á . W zbiorze S * definiujemy relację á L , porządku leksykograficznego, następująco
(x1, x2,...xn ) á L (y1, y2,...ym) wttw albo n £ m i dla wszystkich i £ n , xi = yi albo istnieje takie k>0, że dla i < k £ min(n,m) xi = yi oraz xk á k yk , xk ¹ yk.
Lemat 5.3
Relacja porządku leksykograficznego á L, określona powyżej, jest liniowym porządkiem w S*.
Pytanie 12: Co jest wcześniejsze "kura" czy "jajko" w porządku leksykograficznym á L?
« poprzedni punkt |