Lineární uspořádání

Lineární 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".

Definice

Ř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í:

Předpokládejme, že máme relaci $R\,\!$ na množině $X\,\!$, a $a,b,c\in 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\land bRc\implies aRc\,\!$
2. antireflexivita: pro žádný prvek nesmí platit $aRa\,\!$
3. antisymetrie: $aRb\implies \neg bRa\,\!$
4. trichotomie: $aRb\vee bRa\vee a=b\,\!$

Příklady

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í lineární uspořádání celých kladných čísel - sice je tranzitivní, ale není antireflexivní (2 je násobek 2) a není trichotomická (není pravda aní "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.

Podívejte se také na

• Ostré uspořádání
• Binární relace
• Dobré uspořádání