Porządek leksykograficzny
W matematyce , o leksykograficzny kolejność jest zamówienie , które określamy na skończonych sekwencji pierwiastków w uporządkowanym zbiorze (lub w sposób równoważny, że wyrazy zbudowane na uporządkowanym zestawie). Jego definicja jest uogólnieniem kolejności słownika: uporządkowanym zestawem jest alfabet, słowa są rzeczywiście skończonymi sekwencjami liter alfabetu. Główną właściwością porządku leksykograficznego jest zachowanie całości pierwotnego porządku. W podobny sposób możemy zdefiniować porządek leksykograficzny na iloczynach kartezjańskich zbiorów uporządkowanych, których elementami są więc krotki, to znaczy, jeśli ktoś sobie życzy, skończone ciągi o ustalonej długości.
Porządek leksykograficzny na produkcie kartezjańskim
Chociaż porządek słownikowy jest obsługiwany w szkole podstawowej, zaczniemy formalizację od prostego przypadku, czyli iloczynu binarnego kartezjańskiego. Oznacza to, że słowa z naszego słownika będą początkowo składać się tylko z dwóch liter.
Zbiory ( A , ≤) i ( B , ≤) są uporządkowane, a kolejność zapisywana jest w ten sam sposób dla dwóch zbiorów, wolność, która nie powinna nikomu przeszkadzać. Porządek leksykograficzny na A × B , który ponownie oznaczamy przez ≤, jest zdefiniowany w następujący sposób dla ( a , b ) i ( a ' , b' ) dwóch par A × B :
( a , b ) ≤ ( a ' , b' ) wtedy i tylko wtedy, gdy [ a < a ' lub ( a = a' i b ≤ b ' )]i łatwo wydedukujemy analogiczną własność dla ścisłego porządku leksykograficznego:
( a , b ) <( a ' , b' ) wtedy i tylko wtedy, gdy [ a < a ' lub ( a = a' i b < b ' )].Taka jest rzeczywiście kolejność w słowniku, na przykład:
lu <ne, ponieważ l <n (patrzymy tylko na pierwszą literę) <lu, ponieważ e <u (pierwsze litery są identyczne, patrzymy na drugą).Wybór pierwszego składnika do rozpoczęcia porównania jest czysto arbitralny, ale, jak ilustruje poprzedni przykład alfabetyczny, jeśli porównanie rozpoczyna się od drugiego składnika, uzyskuje się inną kolejność.
Przykłady
- Porządek leksykograficzny na {0, 1} × {0, 1} zwykle uporządkowany daje (0, 0) <(0, 1) <(1, 0) <(1, 1).
- Ogólnie rzecz biorąc, porządek leksykograficzny na {0, 1,…, n - 1} × {0, 1,…, p - 1} jest zwykle porządkiem izomorficznym względem zwykłego porządku na liczbach całkowitych ściśle mniejszych niż np .
- Jeśli ( A , ≤) jest zbiorem uporządkowanym, porządek leksykograficzny na {0,1} × A sprowadza się do „zakończenia od końca” dwóch kopii A (pierwszy związany z pierwszym składnikiem 0, drugi z pierwszym składnikiem 1). Jeśli więc N jest zbiorem liczb naturalnych, zwykle uporządkowanych - nazywa się go ω - {0,1} × N uporządkowany leksykograficznie jest dobrym porządkiem, który nie jest izomorficzny do ω, ale do porządkowej ω + ω = ω2 . Będziemy mieli :
- N x {0,1} uporządkowane leksykograficznie jest dobrym stanie izomorficzna 2ω = ω, zwykle kolejność N .
- N × N uporządkowane leksykograficznie jest w dobrym porządku izomorficznym względem porządkowej ω 2 .
Nieruchomości
- Jeśli każda z początkowych relacji porządku (na A i B ) jest porządkiem całkowitym , to relacja porządku leksykograficznego na A × B jest porządkiem całkowitym.
- Jeśli ponadto każda relacja porządku początkowego jest dobrym porządkiem , to relacja porządku leksykograficznego na A × B jest również dobrym porządkiem.
Uogólnienie na skończone produkty kartezjańskie
Jeśli weźmiemy pod uwagę, że skończony produkt kartezjański A 1 ×… × A k , jest zdefiniowany za pomocą binarnego iloczynu kartezjańskiego przez:
A 1 × A 2 ×… × A k = A 1 × ( A 2 × (… × A k )…)(lub jeśli inaczej zdefiniowano, że między tymi dwoma zbiorami istnieje kanoniczny bijekcja), naturalnie uogólniamy, przez indukcję, porządek leksykograficzny na produkty skończone zbiorów uporządkowanych.
Załóżmy, że zdefiniowaliśmy porządek leksykograficzny iloczynów kartezjańskich k uporządkowanych zbiorów. Następnie, aby zdefiniować porządek leksykograficzny dla iloczynu k + 1 uporządkowanych zbiorów, niech A 1 , A 2 ,…, A k × A k + 1 , leksykograficznie uporządkujemy binarny iloczyn kartezjański A 1 i kartezjański iloczyn k ustawia A 2 ×… × A k × A k + 1 , przy czym ta ostatnia sama jest uporządkowana leksykograficznie. Oznacza to, że porządek leksykograficzny na iloczynie uporządkowanych zbiorów A 1 × A 2 ×… × A k + 1 jest w ten sposób zdefiniowany z porządku leksykograficznego A 2 ×… × A k + 1 (określamy ścisły porządek oznaczony <dla wszystkich zestawów w grze):
( a 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) wtedy i tylko wtedy, gdy: a 1 < b 1 lub [ a 1 = b 1 and ( a 2 ,…, a k + 1 ) <( b 2 ,…, b k + 1 )]Rozbijając iloczyn kartezjański „zaczynając od końca”, otrzymujemy ten sam porządek, to znaczy zachowując te same zapisy, które mamy:
( a 1 ,…, a k + 1 ) <( b 1 ,…, b k + 1 ) wtedy i tylko wtedy, gdy: ( a 1 ,…, a k ) <( b 1 ,…, b k ) lub [( a 1 ,…, a k ) = ( b 1 ,…, b k ) i a k + 1 < b k + 1 ].„Rozszerzając” definicję przez indukcję porządku leksykograficznego na A 1 × A 2 ×… × A k , przy każdym z tych uporządkowanych zbiorów, otrzymujemy:
( a 1 ,…, a k ) <( b 1 ,…, b k ) wtedy i tylko wtedy, gdy a 1 < b 1 lub ( a 1 = b 1 and a 2 < b 2 ) lub ( a 1 = b 1 and a 2 = b 2 and a 3 < b 3 ) lub …… lub ( a 1 = b 1 and a 2 = b 2 i ... oraz a k-1 = b k-1 i a k < b k )Przykłady
Jeśli uporządkujemy leksykograficznie N × N × N , z których każdy jest zwykle uporządkowany, otrzymamy dobry policzalny porządek odpowiadający porządkowi ω 3 , który nie jest ani równy ω, ani ω 2 .
Nieruchomości
Właściwości podane dla binarnych iloczynów kartezjańskich uogólniają się natychmiast przez indukcję: porządek leksykograficzny zdefiniowany na iloczynu kartezjańskim skończonym zbiorów całkowicie uporządkowanych jest porządkiem całkowitym, porządek leksykograficzny zdefiniowany na iloczynu kartezjańskim skończonym zbiorów uporządkowanych jest porządkiem dobrym.
Porządek leksykograficzny na skończonych ciągach
Jest to ten, który ma dla konkretnego przypadku kolejność używaną dla słowników. W przeciwieństwie do poprzednich przypadków, chcemy móc porównać skończone sekwencje o dowolnej długości. Na przykład w słowniku „dom” znajduje się przed „mama”, ponieważ „my” = „my” i „i” <„m”. Jednak „dom” ma 6 liter i „mama” 5. Wyrazy te nie mogą być traktowane jako elementy tego samego gotowego produktu kartezjańskiego, chyba że do alfabetu zostanie dodana litera, którą dowolnie uzupełniamy najwięcej słów. Nie jest to całkowicie nie do pomyślenia dla słownika, ponieważ słowa danego języka mają w praktyce maksymalną długość (przynajmniej te, które pojawiają się w słowniku…), ale byłyby bardzo sztuczne. Dlatego naturalne jest definiowanie porządku leksykograficznego na skończonych sekwencjach o dowolnej długości.
Niech więc ( E , ≤) będzie zbiorem uporządkowanym. Ustawiamy E * = , sumę wszystkich skończonych iloczynów kartezjańskich zbudowanych na E ( E 0 zawiera tylko pusty ciąg). Porządek leksykograficzny na E * definiujemy w następujący sposób. Niech a = ( a 1 ,…, a p ) i b = ( b 1 ,…, b q ) będą dowolnymi dwoma elementami z E * i niech m będzie najmniejszą z dwóch liczb całkowitych p i q . Wtedy a < b wtedy i tylko wtedy, gdy:
( a 1 ,…, a m ) <( b 1 ,…, b m ) (dla porządku leksykograficznego na E m ) lub ( 1 , ..., m ) = ( b 1 , ..., b m ) i m < q (to znaczy P < P ).
Nieruchomości
Można łatwo wykazać, że jeśli początkowy porządek na E jest całkowity, to porządek leksykograficzny na E *, zbiór skończonych ciągów elementów E , jest również całkowity.
Z drugiej strony właściwość dobrego porządku nie jest zachowywana (z wyjątkiem oczywiście przypadku, gdy E jest singletonem ). Na przykład {0, 1} jest dobrze uporządkowany, ale {0, 1} * nie jest, jak pokazuje malejąca nieskończona sekwencja:
(1)> (0, 1)> (0, 0, 1)> (0, 0, 0, 1)>…Dlatego musimy rozważyć inne metody, aby odpowiednio uporządkować skończone sekwencje dobrze uporządkowanego zbioru, na przykład najpierw porównać długości sekwencji.
Definicja uwzględniająca długości sekwencji
Baader i Nipkow definiują porządek leksykograficzny w następujący sposób. Jeśli (E,>) jest porządkiem ścisłym, to porządek leksykograficzny> * lex na E * jest zdefiniowany przez:
u> * lex v jeśli i tylko wtedy, gdy (| u |> | v | lub (| u | = | v | i u> | u | lex v)
gdzie | w | jest długością słowa w, a> | u | lex to porządek leksykograficzny na E | u | .
Jeśli> jest porządkiem ścisłym, to> * lex jest również porządkiem ścisłym. Jeśli kończy się>, kończy się> * lex .
Uwagi i odniesienia
- Franz Baader i Tobias Nipkow, Term Rewriting and All That , Cambridge University Press ,1999, 18–19 s. ( ISBN 978-0-521-77920-3 , czytaj online )
Zobacz też
- Bardziej ogólna definicja porządku leksykograficznego na iloczynu rodziny uporządkowanych zbiorów indeksowanych przez uporządkowany zbiór
- Porządek alfabetyczny