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
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
.
Obecněji lze lexikografické uspořádání zavést pro uspořádané n-tice z
, tj. na množině
pomocí vztahu
![[a_1,a_2,\ldots,a_n] \leq_{Le} [b_1,b_2,\ldots,b_n] \Leftrightarrow \,\!](../../../math/d/9/b/d9b3b3e2a6bcdfa09875bfefb7ff73b9.png)





[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ě
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:
![[1,2,4] \leq_{Le} [1,3,1] \,\!](../../../math/d/a/7/da772a1f7a2816efc7a4991fb8344b5c.png)
- 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í.
[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: |

