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[editovat | editovat zdroj]
Předpokládejme, že množina je uspořádána relací .
Lexikografické uspořádání množiny všech uspořádaných dvojic z kartézského součinu podle relace je definováno vztahem
.
![{\displaystyle X\times X=\{[a,b]:a,b\in X\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8203a7e9070408765b26889b1195e6043a0c67bf)
![{\displaystyle [a,b]\leq _{Le}[c,d]\Leftrightarrow (a<_{R}c\vee (a=c\land b\leq _{R}d))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25e549b5f6210fdff294839f0724c3830a987fbe)
Obecněji lze lexikografické uspořádání zavést pro uspořádané n-tice z , tj. na množině pomocí vztahu
![{\displaystyle X^{n}=\{[a_{1},a_{2},\ldots ,a_{n}]:a_{i}\in X\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ad65f227320d682b1b994d3837b125162ac8979)
![{\displaystyle [a_{1},a_{2},\ldots ,a_{n}]\leq _{Le}[b_{1},b_{2},\ldots ,b_{n}]\Leftrightarrow \,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e020f98ee69b98c31fc790a37ebdfff624b83fd8)
Vlastnosti[editovat | editovat zdroj]
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ě a jejím uspořádání .
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 .
Protože prvky 1 a 2 nejsou porovnatelné podle , dostáváme následující vztahy:
![{\displaystyle R=\{[1,1],[2,2],[3,3],[4,4],[1,3],[2,4],[1,4],[2,3]\}\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08fe7bc3156f03e0f6f0ff74dc37560382819afc)
- trojice a nejsou v lexikografickém uspořádání podle 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í.
![{\displaystyle [1,2,4]\leq _{Le}[1,3,1]\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3cd2bc451c707d447ba836c7ef0a806610f7b44a)
![{\displaystyle [1,1,1]\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4e74dfb52706f1b06de89684ca6496f72dcbe07)
![{\displaystyle [2,4,4]\,\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b76dea31deae86489fecd5f42d10556f296bc85)
Použití[editovat | editovat zdroj]
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.