Lexikografické uspořádání

Z Wikipedie, otevřené encyklopedie

Lexikografické uspořádání je matematický pojem z oboru teorie uspořádání, který formalizuje vlastnosti uspořádání „podle abecedy“ pro potřeby práce s uspořádanými množinami.

Obsah

[editovat] Definice

Předpokládejme, že množina X \,\! je uspořádána relací R \,\!.
Lexikografické uspořádání množiny všech uspořádaných dvojic z kartézského součinu X \times X = \{ [a,b] : a,b \isin X \} \,\! podle relace R \,\! je definováno vztahem
[a,b] \leq_{Le} [c,d] \Leftrightarrow ( a \leq_R c \vee (a = c \and b \leq_R d)) .

Obecněji lze lexikografické uspořádání zavést pro uspořádané n-tice z X \,\!, tj. na množině X^n = \{ [a_1,a_2,\ldots,a_n] : a_i \isin X \} \,\! pomocí vztahu

[a_1,a_2,\ldots,a_n] \leq_{Le} [b_1,b_2,\ldots,b_n] \Leftrightarrow \,\!
(a_1 \leq_R b_1) \vee \,\!
(a_1 = b_1 \and a_2 \leq_R b_2) \vee \,\!
(a_1 = b_1 \and a_2 = b_2 \and a_3 \leq_R b_3) \vee \,\!
\dots \,\!
(a_1 = b_1 \and a_2 = b_2 \and \ldots \and a_{n-1} = b_{n-1} \and a_n \leq_R b_n) \,\!

[editovat] Vlastnosti

Lexikografické uspořádání není přes svou nepřehlednou definici nic záhadného - odpovídá přesně tomu, co rozumíme pod pojmem „uspořádání podle abecedy“.
Pokud vezmeme jako množinu X seznam znaků nějaké abecedy a jako R uspořádání těchto znaků v abecedě, pak není lexikografické uspořádání nic jiného, než určení pořadí všech slov s nějakou určitou délkou. Pokud bychom navíc definovali způsob, jak porovnat dvě různě dlouhé uspořádané n-tice, můžeme rovnou začít řadit telefonní seznam.

Definice lexikografického uspořádání se ale neomezuje pouze na lineárně uspořádané podkladové množiny. Relace R může být v této definici jakékoliv uspořádání.
Uvažujme na chvilku o množině X = \{ 1,2,3,4 \} \,\! a jejím uspořádání R = \{ [1,1],[2,2],[3,3],[4,4],[1,3],[2,4],[1,4],[2,3] \} \,\!.
Relace R je uspořádání, takže k ní můžeme definovat lexikografické uspořádání množiny všech uspořádaných trojic z X^3 = X \times X \times X \,\! .
Protože prvky 1 a 2 nejsou porovnatelné podle R \,\!, dostáváme následující vztahy:

  • [1,2,4] \leq_{Le} [1,3,1] \,\!
  • trojice [1,1,1] \,\! a [2,4,4] \,\! nejsou v lexikografickém uspořádání podle R \,\! porovnatelné - stačí si dosadit do definice a vidíme, že není splněna ani jedna řádka, které podmiňují porovnatelnost v lexikografickém uspořádání.

[editovat] Použití

Při řešení mnoha matematických problémů se ukazuje jako potřebné „přenést“ uspořádání nějaké množiny i na uspořádané dvojice (nebo obecně n-tice) prvků z této množiny. Lexikografické uspořádání je jednou z možností (i když zdaleka ne vždy tou nejlepší), jak něco takového provést - dobrým příkladem je definice ordinálního součtu a ordinálního součinu.

[editovat] Podívejte se také na

Související články obsahuje:
 Portál Matematika