Lineární uspořádání: Porovnání verzí
m robot: stylistické, typografické a kódové korekce a náhrady přesměrování podle specifikace |
m oprava odkazu na rozcestník nebo redirect, Tranzitivní relace → Transitivní relace |
||
| Řádek 7: | Řádek 7: | ||
Předpokládejme, že máme relaci <math> R \,\! </math> na [[Množina|množině]] <math> X \,\! </math>, a <math> a,b,c \isin X \,\! </math> jsou nějaké její libovolné prvky. Abychom mohli prohlásit tuto relaci za lineární uspořádání množiny <math> X \,\! </math>, musí být splněny tyto podmínky: |
Předpokládejme, že máme relaci <math> R \,\! </math> na [[Množina|množině]] <math> X \,\! </math>, a <math> a,b,c \isin X \,\! </math> jsou nějaké její libovolné prvky. Abychom mohli prohlásit tuto relaci za lineární uspořádání množiny <math> X \,\! </math>, musí být splněny tyto podmínky: |
||
# [[ |
# [[Transitivní relace|tranzitivita]]: <math> aRb \and bRc \implies aRc \,\! </math> |
||
# [[Antireflexivní relace|antireflexivita]]: pro žádný prvek nesmí platit <math> aRa \,\! </math> |
# [[Antireflexivní relace|antireflexivita]]: pro žádný prvek nesmí platit <math> aRa \,\! </math> |
||
# [[Antisymetrická relace|antisymetrie]]: <math> aRb \implies \neg bRa \,\! </math> |
# [[Antisymetrická relace|antisymetrie]]: <math> aRb \implies \neg bRa \,\! </math> |
||
Verze z 15. 1. 2007, 03:37
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
Ř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 na množině , a jsou nějaké její libovolné prvky. Abychom mohli prohlásit tuto relaci za lineární uspořádání množiny , musí být splněny tyto podmínky:
- tranzitivita:
- antireflexivita: pro žádný prvek nesmí platit
- antisymetrie:
- trichotomie:
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í neostré lineární uspořádání celých kladných čísel - sice je tranzitivní a reflexivní, ale 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.