Lexikografické uspořádání

Lexikografické uspořádání neboli slovníkové řazení 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.

Definice

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

Obecněji lze lexikografické uspořádání zavést pro uspořádané n-tice z ${\displaystyle X\,\!}$, tj. na množině ${\displaystyle X^{n}=\{[a_{1},a_{2},\ldots ,a_{n}]:a_{i}\in X\}\,\!}$ pomocí vztahu

${\displaystyle [a_{1},a_{2},\ldots ,a_{n}]\leq _{Le}[b_{1},b_{2},\ldots ,b_{n}]\Leftrightarrow \,\!}$
${\displaystyle (a_{1}<_{R}b_{1})\vee \,\!}$
${\displaystyle (a_{1}=b_{1}\land a_{2}<_{R}b_{2})\vee \,\!}$
${\displaystyle (a_{1}=b_{1}\land a_{2}=b_{2}\land a_{3}<_{R}b_{3})\vee \,\!}$
${\displaystyle \dots \,\!}$
${\displaystyle (a_{1}=b_{1}\land a_{2}=b_{2}\land \ldots \land a_{n-1}=b_{n-1}\land a_{n}\leq _{R}b_{n})\,\!}$

Vlastnosti

Lexikografické uspořádání není přes svou nepřehlednou definici nic záhadného - odpovídá přesně tomu, čemu 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ě ${\displaystyle X=\{1,2,3,4\}\,\!}$ a jejím uspořádání ${\displaystyle 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 ${\displaystyle X^{3}=X\times X\times X\,\!}$ .
Protože prvky 1 a 2 nejsou porovnatelné podle ${\displaystyle R\,\!}$, dostáváme následující vztahy:

• ${\displaystyle [1,2,4]\leq _{Le}[1,3,1]\,\!}$
• trojice ${\displaystyle [1,1,1]\,\!}$ a ${\displaystyle [2,4,4]\,\!}$ nejsou v lexikografickém uspořádání podle ${\displaystyle 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í.

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.

Související články

• Ordinální aritmetika
• Lineární uspořádání
• Částečné uspořádání
• Uspořádání