Lineárně uspořádaná množina

Částečně uspořádaná množina (též poset z anglického „Partially ordered set“) je jakákoli množina spolu s částečným uspořádáním (někdy též nazvaným neostré uspořádání), neboli binární relací na této množině, která je reflexivní, tranzitivní a antisymetrická. To znamená, že

• Částečné uspořádání lze definovat na jakékoli množině ${\displaystyle M}$ (které se pak říká nosná množina), protože jde o abstraktní strukturu: částečně uspořádat lze množinu čísel, množinu množin čísel (i množinu množin … množin čísel), množinu funkcí, množinu grafů, uspořádaných seznamů či jakýchkoli dalších struktur.
• Binární relace pro každou (uspořádanou) dvojici prvků ${\displaystyle M}$ stanoví, zda v relaci jsou nebo ne. Částečné uspořádání je zobecněním relace „je menší nebo rovno“ na přirozených číslech. Definice částečného uspořádání zachycuje některé vlastnosti této relace (např. tranzitivnost), ale částečným uspořádáním je každá množina s jakoukoli relací, která tuto definici splňuje. To, že dvojice prvků z ${\displaystyle M}$ je v relaci, se zapisuje

• ${\displaystyle a\preceq b}$ a čte „${\displaystyle a}$ předchází ${\displaystyle b}$“, pokud je vhodné zdůraznit, že se relace může lišit od běžného významu symbolu ${\displaystyle \leq }$.
• Nehrozí-li toto nedorozumění, lze tutéž skutečnost psát ${\displaystyle a\leq b}$ a číst „${\displaystyle a}$ je menší nebo rovno ${\displaystyle b}$“.

• Tranzitivnost: Pokud ${\displaystyle a}$ předchází prvku ${\displaystyle b}$ a ${\displaystyle b}$ předchází ${\displaystyle c}$, pak ${\displaystyle a}$ předchází ${\displaystyle c}$. Částečným uspořádáním na přirozených číslech proto není relace ${\displaystyle a+1=b}$.
• Reflexivnost: Každý prvek předchází sám sobě, neboli „je menší nebo roven“ sám sobě. Proto ostrá nerovnost ${\displaystyle a<b}$ na přirozených číslech není částečným uspořádáním: neplatí ${\displaystyle 1<1}$. Takové relace se nazývají ostrá uspořádání. Hrozí-li nejednoznačnost, částečným uspořádáním se též říká „neostrá uspořádání“.
• Antisymetrie: Uspořádáním není relace, pro niž existují ${\displaystyle a\neq b}$ taková, že ${\displaystyle a\preceq b}$ a zároveň ${\displaystyle b\preceq a}$, např. relace ${\displaystyle |a-b|<=1}$ na přirozených číslech, která vyjadřuje, že čísla jsou si rovna nebo spolu sousedí.

Uspořádané množiny lze graficky znázornit pomocí Hasseových diagramů.

• Relace ≤ je uspořádání na přirozených, celých, racionálních i reálných číslech.
• Relace ${\displaystyle \subseteq }$ ("být podmnožinou") je uspořádání na třídě všech množin (na univerzální třídě).
• Relace dělitelnosti | (a dělí b) je uspořádáním na přirozených číslech.
• Sémantický důsledek ⊨ je uspořádáním logických formulí ve výrokové logice i logice prvního řádu.
• prázdná relace (tj. relace, která neobsahuje žádnou dvojici) je ostré uspořádání nad libovolnou množinou
• relace „existuje cesta z A do B“ je neostrým uspořádáním na množině vrcholů orientovaného
• Relace „být předkem“ na množině všech lidí je ostré uspořádání.

Všimněte si, že na rozdíl od prvního příkladu nejsou ve třetím a čtvrtém případě každé dva prvky množiny srovnatelné

Částečně uspořádaná množina se nazývá

• Spojový polosvaz, pokud v ní každá dvojice prvků má supremum, tj. nejmenší mezi horními závorami.
• Průsekový polosvaz, má-li v ní každá dvojice infimum neboli největší dolní závoru.
• Svaz, má-li v ní každý dvojice supremum i infimum. Pak lze indukcí ukázat, že v ní má supremum i infimum každá neprázdná konečná množina prvků.
• Úplný svaz, pokud v ní má supremum a infimum každá (i nekonečná) množina prvků.

Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházení ${\displaystyle a\preceq b}$ je definováno vztahem „a je dělitel b“. Číslo 12 je největší prvek tohoto svazu. 2 i 3 jsou minimální prvky (tj. nic jim nepředchází), ale poset nemá nejmenší prvek (neboli takový, který by předcházel všem ostatním). Protože čísla 2 a 3 nemají dolní závoru, tento poset není svazem.

V druhém diagramu je číslo 2 největší dolní závora, tj. infimum, prvků 4 a 6. Nejmenší horní závora prvků 4 a 6 (supremum) neexistuje, i když existují dvě minimální horní závory, 24 a 36. Proto daný poset rovněž není svazem. Navíc prvky 2 a 5 nemají vůbec žádnou horní závoru. Jejich jediná (a tedy největší) dolní závora je 1.

Svaz ${\displaystyle P}$ se nazývá úplný, pokud v něm supremum a infimum mají nejen dvouprvkové podmnožiny ${\displaystyle A\subseteq P}$ (z čehož plyne, že to platí pro všechny konečné podmnožiny), ale všechny (i nekonečné) podmnožiny.

Např. celá či reálná čísla jsou svazem, ale nikoli úplným svazem. Typičtějším příklad neúplného svazu je množina všech konečných množin celých čísel uspořádaná obvyklou množinovou inkluzí.

Racionální čísla nejsou úplným svazem; supremum nemá např. množina racionálních čísel menších než zvolené iracionální číslo, např. ${\displaystyle \pi }$ nebo Eulerova konstanta. To úzce souvisí i s tím, že racionální čísla nejsou úplný metrický prostor.

Má-li suprema a infima každá podmnožina ${\displaystyle A\subseteq P}$, má je i celý svaz ${\displaystyle A=P}$, protože je sám sobě podmnožinou (${\displaystyle P\subseteq P}$). Proto má každý úplný svaz nejmenší a největší prvek. Svazem není např. žádný otevřený interval reálných čísel, protože nemá nejmenší prvek (ať už je dolní mezí nekonečno nebo konečné číslo) ani největší prvek.

Odstraněním nuly z uzavřeného intervalu ${\displaystyle \langle -1;1\rangle }$ vznikne množina ${\displaystyle \langle -1;0)\cup (0;1\rangle }$, která sice nejmenší prvek má, ale nemá je její podmnožina ${\displaystyle (0;1\rangle }$; proto není svazem.

Důležitou vlastností reálných čísel je, že v nich má supremum a infimum každá omezená (tj. shora i zdola omezená) podmnožina kromě prázdné. Množina ${\displaystyle A\subseteq \mathbb {R} }$ se nazývá shora omezená, pokud existuje reálné číslo větší než každý její prvek.

Supremum shora neomezené množiny reálných čísel se značí symbolem ${\displaystyle +\infty }$ (čteno „plus nekonečno“), infimum zdola neomezené pak ${\displaystyle -\infty }$. Přidáním těchto dvou hodnot k reálným číslům (a zavedením vhodných operací, jako je sčítání a nerovnost, na této množině) vzniknou rozšířená reálná čísla, která již úplným svazem jsou.

Booleovou algebrou je takový typ svazu, na němž existují binární operace ${\displaystyle \land }$, ${\displaystyle \lor }$, unární operace ${\displaystyle \lnot }$ a konstanty značené ${\displaystyle 0}$ a ${\displaystyle 1}$, které splňují axiomy, díky nimž vykazují podobnost s logickými operacemi „a“, „nebo“, „ne“ a logickými konstantami „pravda“ a „nepravda“.

Pojem svaz, tj. částečně uspořádaná množina s konečnými supremy a infimy, má totiž i ekvivalentní definici jako algebraická struktura: svazem je právě taková množina s binárními operacemi zvanými průsek (${\displaystyle \land }$) a spojení (${\displaystyle \lor }$), která splňuje následující axiomy:

Asociativita: ${\displaystyle (a\lor b)\lor c=a\lor (b\lor c);\quad (a\land b)\land c=a\land (b\land c)}$ 
Komutativita: ${\displaystyle a\lor b=b\lor a;\quad a\land b=b\land a}$
Idempotence: ${\displaystyle a\lor a=a;\quad a\land a=a}$
Absorpce: ${\displaystyle a\lor (a\land b)=a;\quad a\land (a\lor b)=a}$ 

Tyto dvě definice, zdánlivě dost různorodé, jsou ekvivalentní, tj. v důsledku totožné, protože

• Existují-li na nějaké množině takové operace, tj. je-li svazem v algebraickém smyslu, pak na ní lze částečné uspořádání se supremy a infimy získat takovou definicí relace ${\displaystyle \preceq }$, že ${\displaystyle a\preceq b}$ právě když ${\displaystyle a\land b=a}$, nebo ekvivalentně ${\displaystyle a\lor b=b}$.
• Naopak každá částečně uspořádaná množina se supremy a infimy je svazem i v algebraickém smyslu, pokud symboly ${\displaystyle \lor }$ a ${\displaystyle \land }$ označíme právě suprema a infima.

Svaz se nazývá komplementární, pokud má nejmenší i největší prvek (značí se ${\displaystyle 0}$ a ${\displaystyle 1}$) a pro každý prvek ${\displaystyle a\in M}$ existuje jeho komplement, prvek ${\displaystyle \neg a\in M}$, takový, že

${\displaystyle a\land \neg a=0}$
${\displaystyle a\lor \neg a=1}$

Komplementární svaz se nazývá Booleova algebra, pokud je navíc distributivní, tj. pro libovolné prvky ${\displaystyle a,b,c\in M}$ platí:

 ${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$
 ${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c)}$

Symboly pro spojení a průsek byly záměrně zvoleny podobné symbolům ${\displaystyle \cup }$ a ${\displaystyle \cap }$, protože ve svazech množin se často supremum rovná sjednocení a infimum průniku.

Jejich souvislost s logickými operacemi „nebo“ a „a zároveň“ (které se rovněž značí ${\displaystyle \lor }$ a ${\displaystyle \land }$) vynikne na dvouprvkové Boolově algebře ${\displaystyle \mathbb {B} _{2}}$, kterou lze chápat jako logickou nulu a jedničku (tj. nepravdu a pravdu).

Nebo na direktním součinu několika dvouprvkových algeber: pro libovolné přirozené číslo ${\displaystyle n}$ (nebo i pro nekonečnou mohutnost ${\displaystyle n}$ reprezentované např. kardinálním číslem) lze sestrojit direktní součin ${\displaystyle n}$ dvouprvkových algeber ${\displaystyle \mathbb {B} _{2}}$, který se někdy značí ${\displaystyle \mathbb {B} _{2}^{n}}$ :

• Nosnou množinu tvoří všechny posloupnosti nul a jedniček o délce ${\displaystyle n}$.
• Booleovské operace se na ní definují po složkách, např. 01011 ${\displaystyle \land }$ 00111 je 00011.
• Předcházení se definuje rovněž po složkách, tj. ${\displaystyle a\preceq b}$, právě když pro každé ${\displaystyle i\leq n}$ platí ${\displaystyle a_{i}\leq b_{i}}$. Např. platí 10100 ${\displaystyle \preceq }$ 10101. Nikoli však 00110${\displaystyle \preceq }$ 10101, protože čtvrtá složka je u prvně jmenované posloupnosti větší.

Např. ${\displaystyle \mathbb {B} _{2}^{7}}$ lze interpretovat jako informaci, které dny v týdnu má nějaký podnik otevřeno. Úřad otevřený v pondělí a středu je popsán posloupností 1010000, kino otevřené všechny dny kromě pondělí posloupností 0111111. Průsek 1010000 ${\displaystyle \land }$ 0111111 = 00100000 pak vyjadřuje, které dny je možno zajít na úřad a po něm hned do kina. Podobně ${\displaystyle \mathbb {B} _{2}^{12}}$ lze použít jako údaj, ve kterých měsících má nějaké středisko otevřeno.

Každá konečná Booleova algebra má právě takovou strukturu, tj. je izomorfní s ${\displaystyle \mathbb {B} _{2}^{n}}$ pro nějaké ${\displaystyle n}$. Jednoprvková Booleova algebra je izomorfní s ${\displaystyle \mathbb {B} _{2}^{0}}$, neboť existuje právě jedna posloupnost nulové délky. Toto může působit proti intuici, ale formálně je to pravda a taková algebra exaktně splňuje všechny vlastnosti Booleovy algebry i částečného uspořádání.

Nekonečné Booleovy jsou různorodější; u některých je možné každý prvek vyjádřit jako spojení některých atomů. Atomem v Booleově algebře ${\displaystyle B}$ je takový prvek ${\displaystyle a}$, pod kterým již nic není, tj. pro žádné ${\displaystyle x\in B}$ neplatí ostrá nerovnost ${\displaystyle 0\prec x\prec a}$. Takové jsou obvykle úplné, takže má smysl mluvit i o spojení nekonečně mnoha atomů, tzn. nekonečných podmnožin množiny všech atomů.

Jiné jsou naopak husté, tj. mezi každými prvky ${\displaystyle x\prec y}$ existuje další prvek: ${\displaystyle x\prec z\prec y}$. Všechny husté Booleovy algebry (kromě jednoprvkové) jsou nekonečné a bezatomární - nemají žádné atomy.

Pojem „orientovaný graf ${\displaystyle (V,E)}$ s množinou uzlů ${\displaystyle V}$ a množinou hran ${\displaystyle E}$“ přesně splývá s pojmem „binární relace ${\displaystyle E}$ na množině ${\displaystyle V}$“, a to jak formálním zápisem jako uspořádaná dvojice, tak i v tom, jakých podob mohou tyto struktury nabývat. Orientovaný graf je, stejně jako částečné uspořádání, příkladem abstraktní struktury, takže za množinu vrcholů (tj. „nosnou množinu struktury“) lze zvolit libovolné matematické objekty.

Označíme-li proto pojmem „tranzitivní graf“ takový orientovaný graf, který s každou hranou ${\displaystyle (u,v)}$ (tj. šipkou z vrcholu ${\displaystyle u}$ do vrcholu ${\displaystyle v}$) a hranou ${\displaystyle (v,w)}$ obsahuje i „tranzitivní hranu“ ${\displaystyle (u,w)}$, pak „ostré částečné uspořádání“ je přesně totéž, co „tranzitivní acyklický orientovaný graf“. I jako „tranzitivní ireflexivní orientovaný graf“, protože existuje-li cyklus jakékoli délky z ${\displaystyle u}$ do ${\displaystyle u}$, díky tranzitivitě graf obsahuje i ${\displaystyle (u,u)}$, takže není ireflexivní.

• Každou ostře částečně uspořádanou množinu lze chápat jako graf, v němž do každého vrcholu vedou šipky z vrcholů, které mu ostře předchází. Hrany, které z ostatních vyplývají díky tranzitivitě, se pro přehlednost často neznázorňují, např. šipka 1→4, 2→12 a 1→12 na diagramu vpravo.
• Naopak každému orientovanému grafu (tj. množině vrcholů a šipek), který neobsahuje cyklus, lze doplnit „tranzitivní“ hrany, a tak získat ostré částečné uspořádání, doplněním též „reflexivních“ hran pak neostré částečné uspořádání.

Z toho plyne, že jakákoli acyklická množina vrcholů a šipek popisuje částečné uspořádání. To ilustruje, jak mnoha podob mohou nabývat částečná uspořádání na konečných i nekonečných množinách.

• Téma Uspořádání ve Wikicitátech
• Slovníkové heslo uspořádání ve Wikislovníku

Zdroj