porządek leksykograficzny w nLabie

Idea

Porządek leksykograficzny jest uogólnieniem kolejności, w jakiej wyrazy są wymieniane w słowniku, według kolejności liter, na które najpierw różni się pisownia dwóch wyrazów.

Definicja

Niech {L i} iâI{L_i}_{i w I} będzie dobrze uporządkowaną rodziną zbiorów liniowo uporządkowanych. Porządek leksykograficzny na iloczynie zbiorów L=â iâIL iL = ¨prod_{i ¨w I} L_i jest porządkiem liniowym zdefiniowanym następująco: jeśli x,yâLx, y â w L i xâ yx âneq y, to x<yx â iff x i<y ix_i â y_i gdzie ii jest najmniejszym elementem w zbiorze {jâI:x jâ y j} {j â w I: x_j âneq y_j}.

Pomimo, że pojęcie to jest najczęściej spotykane w przypadku porządków liniowych, można je zastosować również w odniesieniu do bardziej ogólnych relacji. Na przykład, można zastosować tę konstrukcję do zbiorów wyposażonych w relację przechodnią <, porzucając założenie o trychotomii.

Często pojęcie to rozszerza się również na podzbiory â iâIL i\prod_{i \in I} L_i. Na przykład, monoid swobodny S *S^ na liniowo uporządkowanym zbiorze SS może być osadzony w przeliczalnej potędze

i:S *âª(1+S) â=â nâ(1+S)i \colon S^\ast \hookrightarrow (1 + S)^mathbb{N} = \prod_{n \ w \mathbb{N} (1 + S)

gdzie 1+S1 + S jest wynikiem swobodnego dołączenia dolnego elementu ee do SS, a dla każdej skończonej listy (s 1,â¦,s k)(s_1, ˆldots, s_k) mamy

i(s 1,â¦,s k)=(s 1,s 2,â¦,s k,e,e,e,â¦).i(s_1, ¦,s_k) = (s_1, s_2, ¦,s_k, e, e, e, ¦).

Wtedy porządek leksykograficzny na S *S^ jest porządkiem odziedziczonym z jego osadzenia w leksykograficznie uporządkowanym zbiorze (1+S) â(1 + S)^mathbb{N}.

Uwaga

Decyzja o swobodnym dołączeniu dolnego elementu ee jest oczywiście czysto konwencjonalna, oparta na zwykłej konwencji słownikowej, że słowo Scrabble AAH powinno występować po AA. Alternatywnie moglibyśmy równie dobrze uznać, że ee jest swobodnie przylegającym elementem górnym, tak że AA przychodzi po AAH; można to nazwać konwencją âanti-dictionaryâ.

Korekurencyjna definicja

jeśli LL jest liniowo uporządkowane, a bazowy zbiór C=L âC = L^mathbb{N} jest uważany za terminalną koalgebrę dla funktora LÃâ:SetâSetL \times – \colon Set \to Set, o strukturze koalgebry â¨h,tâ©:CâLĂC ¨langle h, t ¨rangle ¨colon C ¨to L ¨times C, to porządek leksykograficzny na CC można zdefiniować corecursywnie:

c<câ²c ≥ c' if h(c)<h(câ²)h(c) ≥ h(c') lub (h(c)=h(câ²)h(c) = h(c') i t(c)<t(câ²)t(c) ≥ t(c')).

Dla szczególnego przypadku L=âL = ∙mathbb{N}, krańcowa coalgebra â â â â â ∙mathbb{N}^ ∙mathbb{N} z tym porządkiem leksykograficznym jest porządkowo-izomorficzna z przedziałem rzeczywistym [0,â)[0, ∙infty). Izomorfizm ten jest dokładniej opisany tutaj.

Heading