Lineární uspořádání: Porovnání verzí
m Podívejte se také na - husté uspořádání |
m robot: stylistické, typografické a kódové korekce a náhrady přesměrování podle specifikace |
||
Řádek 1: | Řádek 1: | ||
'''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". |
'''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== |
== Definice == |
||
Řekneme, že [[uspořádání]] (ať již [[ostré uspořádání|ostré]] nebo [[neostré uspořádání|neostré]]) je '''lineární''', pokud se (kromě ostatních vlastností požadovaných definicí uspořádání) jedná o [[Trichotomická relace|trichotomickou]] [[Binární relace|relaci]]. |
Řekneme, že [[uspořádání]] (ať již [[ostré uspořádání|ostré]] nebo [[neostré uspořádání|neostré]]) je '''lineární''', pokud se (kromě ostatních vlastností požadovaných definicí uspořádání) jedná o [[Trichotomická relace|trichotomickou]] [[Binární relace|relaci]]. |
||
Řádek 12: | Řádek 12: | ||
# [[Trichotomická relace|trichotomie]]: <math> aRb \vee bRa \vee a = b \,\! </math> |
# [[Trichotomická relace|trichotomie]]: <math> aRb \vee bRa \vee a = b \,\! </math> |
||
==Příklady== |
== Příklady == |
||
Relace <math> < \,\! </math> je lineární uspořádání na množině [[Přirozené číslo|přirozených čísel]] i [[Reálné číslo|reálných čísel]]. |
Relace <math> < \,\! </math> je lineární uspořádání na množině [[Přirozené číslo|přirozených čísel]] i [[Reálné číslo|reálných čísel]]. |
||
Relace |
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. |
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== |
== Podívejte se také na == |
||
{{Portál matematika}} |
{{Portál matematika}} |
||
* [[Ostré uspořádání]] |
* [[Ostré uspořádání]] |
Verze z 7. 10. 2006, 12:55
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 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í 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.