Otevřít hlavní menu

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.

DefiniceEditovat

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

 
 
 
 
 
 

VlastnostiEditovat

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:

  •  
  • 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í.

PoužitíEditovat

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ánkyEditovat