Lineární uspořádání

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Lineární uspořádání (někdy také úplné uspořádání) je pojem z teorie uspořádání, který formálně zachycuje intuitivní představu o prvcích množiny, které jsou seřazeny „jeden za druhým“. To mimo jiné znamená, že každé dva prvky lineárně uspořádané množiny jsou porovnatelné.

Definice[editovat | editovat zdroj]

Řekneme, že uspořádání (ať již ostré nebo neostré) je lineární, pokud se (kromě ostatních vlastností požadovaných definicí uspořádání) jedná o trichotomickou relaci.

Rozepišme si podrobněji, co všechno musí být splněno, na příkladu ostrého lineárního uspořádání (pro neostré lineární uspořádání musí být antireflexivita nahrazena reflexivitou):

Předpokládejme, že máme relaci  R \,\! na množině  X \,\! , a  a,b,c \isin X \,\! jsou nějaké její libovolné prvky. Abychom mohli prohlásit tuto relaci za lineární uspořádání množiny  X \,\! , musí být splněny tyto podmínky:

  1. tranzitivita:  aRb \and bRc \implies aRc \,\!
  2. (slabá) antisymetrie:  aRb \and bRa \implies a = b \,\!
  3. trichotomie:  aRb \vee bRa \vee a = b \,\!

Příklady[editovat | editovat zdroj]

Relace  < \,\! je lineární uspořádání na množině přirozených čísel i reálných čísel.


Relace „číslo a je násobek čísla b“ není neostré lineární uspořádání celých kladných čísel - sice je tranzitivní a reflexivní, ale není trichotomická (není pravda ani „2 je násobek 3“, ani „3 je násobek 2“, ani „2 = 3“).


Uvažujme o pětiprvkové množině X = {a,b,c,d,e} a relaci R = {[a,c],[a,d],[a,e],[b,c],[b,d],[c,d]}. Tato relace je tranzitivní, antireflexivní i antisymetrická. Není však trichotomická, protože například d a e jsou dva různé neporovnatelné prvky.

Související články[editovat | editovat zdroj]