Čá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 \}$ $\{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

12 je **největší prvek** svazu. 2 i 3 jsou **minimální prvky** (tj. nic jim nepředchází), ale svaz nemá **nejmenší prvek**, který by předcházel všem ostatním.
		12
		↑
		6
	↗		↖
2				3

2 je v tomto posetu největší dolní závora, tj. **supremum**, prvků 4 a 6. *Nejmenší* horní závora prvků 4 a 6 (**infimum**) neexistuje, i když existují dvě *minimální* horní závory, 24 a 36. Svaz proto není úplný. Navíc prvky 2 a 5 nemají vůbec žádnou horní závoru. Jejich jediná (a tedy největší) dolní závora je 1.
		72
	↗		↖
24				36
↑	↗		↖	↑
4				6	15
	↖		↗		↑
		2			5
		↑		↗
		1

Následující struktury se běžně definují jako algebraické struktury, ale lze je definovat i pomocí částečných uspořádání:

Polosvaz (spojový a průsekový)

Poset (tj. částečně uspořádaná množina) $M$ se nazývá spojový polosvaz, pokud nad každými dvěma prvky $a,b\in M$ existuje supremum neboli nejmenší horní závora. Pojem horní závora $h$ znamená, že $a\preceq h$ a $b\preceq h$ . Pojem nejmenší pak to, že musí předcházet každé jiné horní závoře.

Ekvivalentně lze spojový polosvaz definovat jako algebraickou strukturu s binární operací $\lor$ zvanou spojení, která splňuje axiomy:

Asociativita:  $(a\lor b)\lor c=a\lor (b\lor c)$  
Komutativita:  $a\lor b=b\lor a$ 
Idempotence: $a\lor a=a$

Je-li na množině definována struktura polosvazu algebraicky, ekvivalentem je poset, v němž $a\preceq b$ je definováno jako $a\lor b=b$ . Od posetu k algebraické definici se přejde tak, že spojení dvou prvků je definováno jako jejich supremum, které ve spojovém polosvazu vždy existuje.

Podobně průsekový polosvaz je poset, v němž každá dvojice prvků má infimum neboli největší horní závoru. Ekvivalentně je to množina s binární operací $\land$ zvanou průsek.

Svazy

Uspořádaná množina se nazývá svaz, pokud každá dvojice $a,b\in M$ má supremum (nejmenší horní závoru) i infimum (největší dolní závoru). Supremum a infimum se ve svazu značí $\lor$ a $\land$ a nazývají spojení a průsek.

Tyto symboly 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 „zároveň“ (které se rovněž značí $\lor$ a $\land$ ) vynikne na dvouprvkové Boolově algebře, kterou lze chápat jako logickou nulu a jedničku (tj. nepravdu a pravdu), nebo na svazu, který je direktním součinem několika dvouprvkových Booleových algeber. Tj. pro libovolné konečné $n$ lze za nosnou množinu vzít $n$ -prvkové posloupnosti logických nul a jedniček; posloupnost předchází druhou, pokud je menší nebo rovna ve všech složkách. Např. 1010 předchází 1011, ale nikoli 1100, neboť ta má druhý prvek větší.

Pro $n=7$ lze takovou strukturu interpretovat např. jako definici, které dny v týdnu má daná restaurace otevřeno. 1111100 znamená, že pouze v pracovní dny. Pokud má nějaký úřad otevřeno jen v pondělí a středu (1010000), pak 1111100 $\land$ 10100000 = 10100000 vyjadřuje dny, kdy je možné navštívit úřad a hned se pak najíst v restauraci.

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 $a\lor \neg a=1$ , kde $0$ je nejmenší prvek a $1$ je největší prvek svazu.

Booleovy algebry

Komplementární svaz se nazývá Booleova algebra, pokud je 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)$

Úplné svazy

Úplný svaz je svaz, ve kterém všechna suprema a infima existují nejen pro dvojice prvků, ale pro libovolné množiny. Analogicky se definuje úplná Booleova algebra.

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í.

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.