Částečně 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ě $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ů $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 $M$ je v relaci, se zapisuje

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

Tranzitivnost: Pokud $a$ předchází prvku $b$ a $b$ předchází $c$ , pak $a$ předchází $c$ . Částečným uspořádáním na přirozených číslech proto není relace $a 1=b$ .
Reflexivnost: Každý prvek předchází sám sobě, neboli „je menší nebo roven“ sám sobě. Proto ostrá nerovnost $a<b$ na přirozených číslech není částečným uspořádáním: neplatí $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í $a\neq b$ taková, že $a\preceq b$ a zároveň $b\preceq a$ , např. relace $|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ů.

Příklady

Relace ≤ je uspořádání na přirozených, celých, racionálních i reálných číslech.
Relace $\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é

Další typy uspořádání

Lineární a dobré uspořádání

Částečné uspořádání množiny $M$ se nazývá

Lineární uspořádání (někdy též: úplné uspořádání v protikladu k „částečnému uspořádání“), pokud pro každé $a,b\in M$ buď $a\preceq b$ nebo $b\preceq a$ , tj. pokud neexistuje dvojice prvků vzájemně nesrovnatelných.
Dobré uspořádání, pokud je lineární a každá neprázdná podmnožina $A\subseteq M$ má nejmenší prvek $a$ , tj. takový, že pro každé $b\in A$ (ale ne nutně pro ostatní $b\in M$ ) platí $a\preceq b$ . Ekvivalentně, lineární uspořádání je dobré, pokud v něm neexistuje nekonečná klesající posloupnost, tj. taková, v níž každý prvek je ostře menší než předchozí, tj. $a_{1}\succ a_{2}\succ a_{3}\succ \dots$
Husté uspořádání, je-li lineární a mezi každými $a\prec b$ leží prvek $a\prec c\prec b$ ; symbol $\prec$ značí „předchází a není roven.“

Na jedné množině může existovat řada uspořádání různých vlastností, např.

Obvyklá nerovnost $a\leq b$ je na přirozených číslech lineární uspořádání, ne však husté. Ovšem relace „ $a$ je dělitel $b$ “ není lineární (a tedy ani dobrá či hustá), což dosvědčují čísla 2 a 3: jsou navzájem nesrovnatelná.
Husté uspořádání nemůže být dobré, je-li $M$ alespoň dvouprvková.
Obvyklá nerovnost na racionálních či reálných číslech je lineární a hustá. Není dobrým uspořádáním, neboť nemá nejmenší prvek.
Uzavřený interval reálných čísel $\langle 0;1\rangle$ není dobrým uspořádáním: sice má nejmenší prvek, ale jeho podmnožina $(0;1)$ žádný nejmenší prvek nemá.
Na přirozených číslech je běžná nerovnost $a\leq b$ dobrým uspořádáním, ale obrácené uspořádání $a\geq b$ nikoli.
Množina celých čísel není dobře uspořádaná ani obvyklou nerovností, ani obrácenou. Jedna z cest k nalezení dobrého uspořádání je najít takové, aby každému číslu předcházelo jen konečně mnoho jiných. Relace porovnávající absolutní hodnotu „ $a\preceq b$ , právě když $|a|\leq |b|$ “ není částečným uspořádáním: není antisymetrická, jak dosvědčují čísla 1 a -1. Částečným a dokonce dobrým uspořádáním je však zúžení této relace tak, aby pro kladné $n$ platilo $-n\preceq n$ , ale nikoli $n\preceq -n$ . Jinými slovy, rozhoduje primárně absolutní hodnota obou čísel a teprve v druhé řadě jejich znaménko: $a\preceq b$ , právě když buď $|a|<|b|$ , nebo $|a|=|b|$ a $a\leq b$ .
V informatice, zejména teorii automatů a gramatik, se často pracuje s konečnou množinou formálních (tj. nenesoucích jiný význam, než své jméno) symbolů $\{a,b,c,\dots \}$ , která je zvána abeceda. Jsou pak zkoumány vztahy a přechody mezi jednotlivými slovy, tj. posloupnostmi symbolů (různých konečných délek).
- Lexikografické uspořádání značí třídění abecedním pořadím, jaké lidé používají ve slovnících a rejstřících. Toto třídění je lineární, ale nikoli dobré, protože existuje ostře klesající posloupnost $b\succ ab\succ aab\succ aaab\succ aaaab\succ \dots$
- I zde lze dobré uspořádání nejsnáze nalézt tak, aby každému slovu předcházelo jen konečně mnoho jiných slov. Vhodným řešením je maximo-lexikografické uspořádání, které porovnává přednostně délku slov a až v druhé řadě jejich abecední (tj. lexikografické) pořadí.

Dobré uspořádání hraje velkou roli v teorii ordinálních čísel:

Každý ordinál je dobře uspořádaná množina. Na druhou stranu jakákoli dobře uspořádaná množina je izomorfní s přesně jedním ordinálem.
Na každé konečné množině jsou všechna lineární (a tedy i všechna dobrá) uspořádání navzájem izomorfní. Na nekonečných spočetných množinách existuje dobrých uspořádání (až na izomorfismus, tzn. počítáme-li všechny navzájem izomorfní jako jedno) nespočetně mnoho: každý typ uspořádání odpovídá jednomu spočetnému ordinálu.
Otázka, zda na každé množině existuje nějaké dobré uspořádání, je ekvivalentní s axiomem výběru a dotýká se proto základů a axiomatizace celé matematiky. Přidává se jako dodatečný axiom, protože ze základních (Zermelových–Fraenkelových) axiomů matematiky ji nelze rozhodnout (tj. dokázat nebo vyvrátit).
Nerozhodnutelná je i otázka, zda vůbec nějaké dobré uspořádání existuje na reálných číslech (i kdyby se naprosto lišilo od běžné nerovnosti). Bez tohoto dodatečného axiomu nelze dokázat významná matematická tvrzení, např. Banachův-Tarského paradox nebo existenci Lebesgueovsky neměřitelné množiny reálných čísel.

Svazy

Čá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ů.

**Diagram 1**
		12
		↑
		6
	↗		↖
2				3

**Diagram 2**
		72
	↗		↖
24				36
↑	↗		↖	↑
4				6	15
	↖		↗		↑
		2			5
		↑		↗
		1

Např. diagram 1 zachycuje poset některých přirozených čísel, kde předcházení $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.

Úplný svaz

Svaz $P$ se nazývá úplný, pokud v něm supremum a infimum mají nejen dvouprvkové podmnožiny $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ř. $\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 $A\subseteq P$ , má je i celý svaz $A=P$ , protože je sám sobě podmnožinou ( $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 $\langle -1;1\rangle$ vznikne množina $\langle -1;0)\cup (0;1\rangle$ , která sice nejmenší prvek má, ale nemá je její podmnožina $(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 $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 $\infty$ (čteno „plus nekonečno“), infimum zdola neomezené pak $-\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.

Booleovy algebry

Booleovou algebrou je takový typ svazu, na němž existují binární operace $\land$ , $\lor$ , unární operace $\lnot$ a konstanty značené $0$ a $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 ( $\land$ ) a spojení ( $\lor$ ), která splňuje následující axiomy:

Asociativita:  $(a\lor b)\lor c=a\lor (b\lor c);\quad (a\land b)\land c=a\land (b\land c)$  
Komutativita:  $a\lor b=b\lor a;\quad a\land b=b\land a$ 
Idempotence:  $a\lor a=a;\quad a\land a=a$ 
Absorbce:  $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 $\preceq$ , že $a\preceq b$ právě když $a\land b=a$ , nebo ekvivalentně $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 $\lor$ a $\land$ označíme právě suprema a infima.

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

 $a\land \neg a=0$ 
 $a\lor \neg a=1$

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

  $a\land (b\lor c)=(a\land b)\lor (a\land c)$ 
  $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 $\cup$ a $\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čí $\lor$ a $\land$ ) vynikne na dvouprvkové Boolově algebře $\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 $n$ (nebo i pro nekonečnou mohutnost $n$ reprezentované např. kardinálním číslem) lze sestrojit direktní součin $n$ dvouprvkových algeber $\mathbb {B} _{2}$ , který se někdy značí $\mathbb {B} _{2}^{n}$ :

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

Např. $\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 $\land$ 0111111 = 00100000 pak vyjadřuje, které dny je možno zajít na úřad a po něm hned do kina. Podobně $\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 $\mathbb {B} _{2}^{n}$ pro nějaké $n$ . Jednoprvková Booleova algebra je izomorfní s $\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 $B$ je takový prvek $a$ , pod kterým již nic není, tj. pro žádné $x\in B$ neplatí ostrá nerovnost $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 $x\prec y$ existuje další prvek: $x\prec z\prec y$ . Všechny husté Booleovy algebry (kromě jednoprvkové) jsou nekonečné a bezatomární - nemají žádné atomy.

Ostré a neostré uspořádání

Každé uspořádání je možno vyjádřit „neostrou“ relací, v níž pro každé $a$ platí $a\preceq a$ , tak i „ostrou“, která se značí $\prec$ a vztah $a\prec a$ neplatí pro žádné $a$ . Zatímco $a\preceq b$ se čte „ $a$ předchází $b$ “ (případně „ $a$ je menší nebo rovno $b$ “), vztah $a\prec b$ se čte „ $a$ ostře předchází $b$ “, případně (nehrozí-li nedorozumění) „ $a$ je menší než $b$ “.

Jde o dva popisy téhož vztahu; rozdíl je jen technický, protože někdy při je matematických konstrukcích potřeba ostrá varianta. Vztah mezi $\prec$ a $\preceq$ v jakékoli částečně uspořádané množině je obdobný vztahu mezi $<$ a $\leq$ , tedy ostrou a neostrou nerovností na přirozených číslech.

Přesná definice: Zatímco „částečné uspořádání“ standardně znamená „neostré částečné uspořádání“ z úvodu článku, neboli antisymetrickou tranzitivní binární relaci, která je reflexivní, pojem ostré částečné uspořádání značí antisymetrickou tranzitivní binární relaci, která je ireflexivní, což znamená, že $a\prec a$ neplatí pro žádné $a$ .

Ke každému ostrému uspořádání lze zkonstruovat neostré, a to přidáním „reflexivních“ dvojic. Stejně tak k neostrému lze vytvořit ostré jejich odebráním.

Ostré částečné uspořádání se nazývá „ostré lineární uspořádání“ nebo „ostré dobré uspořádání“, splňuje-li obdobné podmínky, jako lineární uspořádání nebo dobré uspořádání. Například na každém ordinálním číslu je náležení $a\in b$ ostrým dobrým uspořádáním, zatímco množinová inkluze $a\subseteq b$ je neostrým dobrým uspořádáním.

Souvilost s acyklickými grafy

Množina ${1,2,3,4,12}$ uspořádaná dělitelností.
	12
↗		↖
4
↑			3
2
↖		↗
	1

Množina ${2,3,4,5}$ uspořádaná dělitelností.
4
↑	3	5
2

Pojem „orientovaný graf $(V,E)$ s množinou uzlů $V$ a množinou hran $E$ “ přesně splývá s pojmem „binární relace $E$ na množině $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 $(u,v)$ (tj. šipkou z vrcholu $u$ do vrcholu $v$ ) a hranou $(v,w)$ obsahuje i „tranzitivní hranu“ $(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 $u$ do $u$ , díky tranzitivitě graf obsahuje i $(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.

Externí odkazy

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

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.