Protiřetězec

Z Wikipedie, otevřené encyklopedie

Protiřetězec (někdy také označovaný jako antiřetězec) je matematický termín z oboru algebry a teorie uspořádání, který se používá pro označení množin vzájemně neporovnatelných prvků.

Obsah

1 Definice
2 Příklady
3 Podívejte se také na

[editovat] Definice

Předpokládejme, že množina $X \,\!$ je uspořádána relací $R \,\!$ . O podmnožině $Y \subseteq X \,\!$ řekneme, že se jedná o protiřetězec, pokud jsou každé dva různé prvky $a,b \isin Y \,\!$ neporovnatelné pomocí $R \,\!$ , tj.
$(\forall a,b \isin Y)( a \leq_R b \implies a = b) \,\!$

[editovat] Příklady

[editovat] Protiřetězce v lineárním uspořádání

V lineárně uspořádané množině nemá pojem protiřetězec příliš dobrý smysl - každé dva prvky jsou porovnatelné a neexistují jiné než (nepříliš zajímavé) jednoprvkové protiřetězce. To se týká například běžného uspořádání reálných čísel nebo přirozených čísel podle velikosti.

[editovat] Protiřetězce v množině komplexních čísel

Uvažujme ostré uspořádání $R \,\!$ množiny komplexních čísel podle vzdálenosti od nuly (tj. podle absolutní hodnoty). Kdo by měl problém s pojmem komplexního čísla, může si představit geometrickou rovinu a vzdálenost bodů (uspořádaných dvojic) od počátku souřadnic (tj. od bodu [0,0]):
$c_1 <_R c_2 \Leftrightarrow |c_1| < |c_2| \,\!$

Položme si otázku, jaké největší protiřetězce zde existují. Každé dva body, které mají stejnou vzdálenost od nuly (leží na stejné kružnici se středem v nule) jsou neporovnatelné a mohou tedy spolu náležet do protiřetězce. Jakmile ale nějaké dva body leží na dvou různých kružnicích se středem v 0, mají různou abolutní hodnotu a jsou porovnatelné - nemohou být spolu v jednom protiřetězci.

Největší možné protiřetězce při tomto uspořádání komplexních čísel jsou tedy soustředné kružnice se středem v bodě 0.

[editovat] Protiřetězce vzhledem k dělitelnosti

Uvažujme o množině všech kladných přirozených čísel, s uspořádáním podle dělitelnosti (tj. $a \leq_| b \,\!$ , pokud $a \,\!$ dělí $b \,\!$ ).

Při tomto uspořádání existují v množině přirozených čísel libovolně velké (co do počtu prvků) protiřetězce. Příkladem nekonečného protiřetězce je množina všech prvočísel. Tento protiřetězec je přitom největší možný - jakékoliv kladné přirozené číslo je porovnatelné s nějakým prvočíslem, takže ho nelze k tomuto protiřetězci přidat, aniž by přestal být protiřetězcem.

Existuje zde ale i jeden největší možný protiřetězec, který je pouze jednoprvkový - je to množina $\{ 1 \} \,\!$ . Důvod je ten, že číslo 1 je porovnatelné s každým přirozeným číslem (dělí každé přirozené číslo).