Teorie uspořádání

Teorie uspořádání množin je matematická disciplína, která se zabývá studiem vlastností binárních relací^[1] zachycujících intuitivní pojem různých typů uspořádání množin. V teorii uspořádání se intuitivní pojem uspořádání formalizuje pomocí binárních relací speciálních vlastností. To umožňuje zkoumat jev uspořádání na velmi obecné úrovni. Výsledky získané na takové obecné úrovni pak lze velmi snadno aplikovat v konkrétních situacích. Častý výskyt uspořádání v praktických situacích vedl k definici různých uspořádání se speciálními vlastnostmi. Teorie uspořádání se neomezuje jen na studium vlastností různých typů uspořádání ale zkoumá i vztahy mezi nimi.

Motivace

Jev uspořádání se přirozeným způsobem vyskytuje skoro všude, zvláště v matematice a v informatice. Známý příklad uspořádání, se kterým se lze setkat již na základní škole, je standardní uspořádání přirozených čísel podle jejich velikosti. Jiným příkladem uspořádání z každodenního života je lexikografické uspořádání slov ve slovníku. Některá uspořádání mají speciální vlastnost: Kterýkoliv prvek lze porovnat s každým jiným prvkem a rozhodnout zda je větší, menší nebo stejný. To splňuje například uspořádání čísel nebo uspořádání slov ve slovníku. Obecně ale uspořádání tuto vlastnost mít nemusí. Například v hierarchii pracovníků, dva kolegové pracující na nejnižší úrovni, kteří již nemají další podřízené, nejsou srovnatelní - ani jeden z nich není nadřízen tomu druhému.

Typy uspořádání

Na tuto kapitolu jsou přesměrována hesla Ostré uspořádání a Neostré uspořádání.

• Kvaziuspořádání je relace, která je reflexivní a tranzitivní.
• Ostré uspořádání je relace, která je antireflexivní a tranzitivní.
• Neostré (částečné) uspořádání je relace, která je reflexivní, slabě antisymetrická a tranzitivní.
• Dobré uspořádání je taková relace uspořádání na množině M, kde každá neprázdná podmnožina této množiny má nejmenší prvek.
• Úplné (lineární) uspořádání je taková relace uspořádání R na množině M, kde pro každé dva různé prvky této množiny x a y platí buď xRy nebo yRx.
• Husté uspořádání je taková relace ostrého lineárního uspořádání R na množině M, kde pro každé dva různé prvky této množiny x a y, pro které platí xRy, existuje prvek z této množiny tak, že platí xRz a zRy.

Pozn.: Výše uvedená množina M se nazývá nosná množina.

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

• Obvyklá nerovnost ${\displaystyle a\leq b}$ je na přirozených číslech lineární uspořádání, ne však husté. Ovšem relace „${\displaystyle a}$ je dělitel ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \langle 0;1\rangle }$ není dobrým uspořádáním: sice má nejmenší prvek, ale jeho podmnožina ${\displaystyle (0;1)}$ žádný nejmenší prvek nemá.
• Na přirozených číslech je běžná nerovnost ${\displaystyle a\leq b}$ dobrým uspořádáním, ale obrácené uspořádání ${\displaystyle 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 „${\displaystyle a\preceq b}$, právě když ${\displaystyle |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é ${\displaystyle n}$ platilo ${\displaystyle -n\preceq n}$, ale nikoli ${\displaystyle n\preceq -n}$. Jinými slovy, rozhoduje primárně absolutní hodnota obou čísel a teprve v druhé řadě jejich znaménko: ${\displaystyle a\preceq b}$, právě když buď ${\displaystyle |a|<|b|}$, nebo ${\displaystyle |a|=|b|}$ a ${\displaystyle 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ů ${\displaystyle \{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 ${\displaystyle 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.