Částečně objednaná sada

Částečně uspořádaná množina je matematický koncept, který formalizuje intuitivní myšlenky řazení, uspořádání prvků v určité posloupnosti. Neformálně je množina částečně uspořádaná, pokud je specifikováno, které prvky následují za kterými (které prvky jsou větší než které). Obecně se může ukázat, že některé páry prvků spolu nesouvisí vztahem „ následuje “ .

Jako abstraktní příklad můžeme uvést sbírku podmnožin množiny tří prvků ( boolean dané množiny), uspořádaných podle vztahu inkluze. $\{x,y,z\}$

Definice a příklady

Relace řádu , nebo částečné pořadí , na množině je binární relace na(definovaná nějakou množinou), která splňuje následující podmínky [1] : $M$ $\varphi$ $M$ $R_{{\varphi }}\subset M\times M$

Reflexivita : $\forall a\;(a\varphi a)$
Přechodnost : $\forall a,b,c\;(a\varphi b)\klín (b\varphi c)\Šipka doprava a\varphi c$
Antisymetrie : $\forall a,b\;(a\varphi b)\klín (b\varphi a)\Šipka doprava a=b$

Množina , na které je dán vztah částečného řádu, se nazývá částečně uspořádaná . Abychom byli docela přesní [2] , pak částečně uspořádaná množina je dvojice , kde je množina a je relace částečného řádu na . $M$ $\langle M,\varphi \rangle$ $M$ $\varphi$ $M$

Rozměr částečně uspořádané množiny se rovná maximálnímu počtu množiny lineárních řádů ( ). Tato definice je založena na vlastnosti rozšiřitelnosti dílčího řádu na lineární. $\langle M,\varphi \rangle$ ${\displaystyle <_{i))$ $i\v I$

Terminologie a notace

Relace částečného řádu se obvykle označuje symbolem , analogicky se vztahem „menší nebo rovno“ na množině reálných čísel . Navíc, jestliže , pak říkáme, že prvek nepřekračuje , nebo že je podřízený . $\leqslant$ $a\leqslant b$ $A$ $b$ $A$ $b$

Jestliže a , pak napíšou a řeknou, že je menší než , nebo že je přísně podřízena . $a\leqslant b$ $a \neq b$ $a<b$ $A$ $b$ $A$ $b$

Někdy, aby se odlišilo libovolné pořadí na určité množině od známého vztahu „menší nebo rovno“ na množině reálných čísel, se místo a , v tomto pořadí , používají speciální symboly a . $\leqslant$ $<$ $\preccurlyeq$ $\prec$

Přísný a nepřísný řád

Vztah, který splňuje podmínky reflexivity, tranzitivity a antisymetrie, se také nazývá nestriktivní nebo reflexivní řád . Pokud je podmínka reflexivity nahrazena podmínkou antireflexivity (pak je vlastnost antisymetrie nahrazena asymetrií):

\forall a\;\neg (a\varphi a)

pak dostaneme definici přísného nebo antireflexivního řádu .

Pokud je na množině nepřísné pořadí , pak vztah definovaný jako: $\leqslant$ $M$ $<$

a<b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a\leqslant b)\wedge (a\neq b)

je přísný příkaz na . Naopak, pokud je striktní řád, pak vztah definovaný jako $M$ $<$ $\leqslant$

a\leqslant b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a<b)\vee (a=b)

je nepřísný řád.

Je tedy jedno, zda na natáčení zadat nepřísné pořadí nebo striktní pořadí . Výsledkem je stejná struktura. Rozdíl je pouze v terminologii a notaci.

Interval

Pro uzavřený interval [ a , b ] je množina prvků x splňujících nerovnici (tj. a ). Interval obsahuje alespoň prvky a a b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Pokud použijeme striktní nerovnost "<", dostaneme otevřený interval ( a , b ), množinu prvků x , které splňují nerovnost a < x < b (tj. a < x a x < b ). Otevřený interval může být prázdný, i když a < b . Například otevřený interval (1,2) pro celá čísla je prázdný, protože neexistují žádná celá čísla i taková, že 1 < i < 2.

Někdy je definice rozšířena tak, aby umožňovala a > b . V tomto případě je interval prázdný.

Polootevřené intervaly [ a , b ) a ( a , b ] jsou definovány podobným způsobem.

Poset je lokálně konečný , pokud je každý interval konečný. Například celá čísla jsou lokálně konečná ve svém přirozeném uspořádání. Lexikografické pořadí na přímém součinu ℕ×ℕ není lokálně konečné, protože například . $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

Pojem interval v posetech by neměl být zaměňován se specifickou třídou posetů známou jako intervalové objednávky .

Příklady

Množina reálných čísel je částečně uspořádána podle vztahu "menší nebo rovno" - . $\mathbb {R}$ $\leqslant$

Nechť je množina všech reálných funkcí definovaných na segmentu , tedy funkcí formuláře $M$ $[a,b]$

f\dvojtečka [a,b]\to {\mathbb {R}}

Zaveďme relaci pořadí na takto: , platí- li nerovnost pro všechny . Je zřejmé, že zavedená relace je skutečně relací částečného řádu. $\leqslant$ $M$ $f\leqslant g$ $x\in[a,b]$ $f(x)\leqslant g(x)$

Nechte to být . Množina všech podmnožin (tzv. boolean ), je částečně uspořádána inkluzí . $M$ ${\mathcal {P}} (M)$ $M$ $M\subseteq N$

Množina všech přirozených čísel je částečně uspořádána podle vztahu dělitelnosti . $\mathbb {N}$ $m\střed n$

Související definice

Nesrovnatelné prvky

Jestliže a jsou reálná čísla , pak platí pouze jeden z následujících vztahů: $A$ $b$

a<b,\qquad a=b,\qquad b<a

Jestliže a jsou prvky libovolné částečně uspořádané množiny, pak existuje čtvrtá logická možnost: žádný z výše uvedených tří vztahů není splněn. V tomto případě se prvky a nazývají nesrovnatelné . Pokud je například množina funkcí se skutečnou hodnotou na segmentu , pak prvky a budou nesrovnatelné. Možnost existence nesrovnatelných prvků vysvětluje význam pojmu „částečně uspořádaná množina“ . $A$ $b$ $A$ $b$ $M$ $[0,1]$ $f(x) = x$ $g(x)=1-x$

Minimum/Maximum a Nejmenší/Největší prvky

Vzhledem k tomu, že v částečně uspořádané množině mohou být dvojice nesrovnatelných prvků, jsou zavedeny dvě různé definice: minimální prvek a nejmenší prvek .

Prvek je považován za minimální , pokud prvek neexistuje . Jinými slovy, je minimální prvek, pokud pro jakýkoli prvek buď , nebo , nebo a jsou nesrovnatelné. Prvek se nazývá nejmenší , pokud pro jakýkoli prvek platí nerovnost . Je zřejmé, že jakýkoli nejmenší prvek je také minimální, ale obráceně to v obecném případě neplatí: minimální prvek nemusí být nejmenší, pokud existují prvky , které nejsou srovnatelné s . $a \in M$ $b<a$ $A$ $b\in M$ $b>a$ $b=a$ $b$ $A$ $A$ $b\in M$ $b\geqslant a$ $A$ $b$ $A$

Je zřejmé, že pokud je v sadě nejmenší prvek, pak je jedinečný. Minimálních prvků však může být několik. Jako příklad uvažujme množinu přirozených čísel bez jednotky, uspořádaných podle vztahu dělitelnosti . Zde budou minimálními prvky prvočísla , ale nejmenší prvek neexistuje. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\střední$

Pojmy maximální a největší prvky jsou zavedeny podobně.

Horní a spodní plochy

Dovolit být podmnožinou částečně uspořádané množiny . Prvek se nazývá horní mez , pokud žádný prvek nepřesahuje . Pojem dolní hranice množiny je zaveden podobně . $A$ $\langle M,\leqslant \rangle$ $u\v M$ $A$ $v A$ $u$ $A$

Jakýkoli prvek větší než některá horní plocha bude také horní plochou . A každý prvek menší než nějaké infimum bude také infimum . Tyto úvahy vedou k zavedení pojmů nejmenší horní hranice a největší dolní hranice . $A$ $A$ $A$ $A$

Horní a dolní sady

U prvku částečně uspořádané množiny je horní množinou množina všech prvků , kterým předchází ( ). $m$ $\langle M,\leqslant \rangle$ $M\nahoru m$ $m$ $\{x\in M\mid m\leqslant x\}$

Spodní množina je definována duálně jako množina všech prvků předcházejících dané množině: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Podmínky přerušení

O částečně uspořádané množině se říká , že uspokojí podmínku ukončení řetězu striktně rostoucí , pokud neexistuje nekonečná přísně rostoucí posloupnost . Tato podmínka je ekvivalentní stabilizační podmínce pro nestriktně rostoucí řetězce : jakákoli nestriktivně rostoucí sekvence jejích prvků se stabilizuje. Tedy pro libovolnou sekvenci formuláře $M$ $(a_{i}\,<\,a_{i+1})$ $(a_{i}\,\leqslant \,a_{i+1})$

a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots

existuje přírodní takový, že $n,$

a_{n}=a_{{n+1}}=a_{{n+2}}=\cdots .

Definováno podobným způsobem pro klesající řetězce pak zjevně splňuje podmínku ukončení sestupného řetězce tehdy a jen tehdy, když se stabilizuje jakákoli nestriktivně klesající sekvence jeho prvků. Tyto pojmy se často používají v obecné algebře - viz např. Noetherian ring , Artinian ring . $M$

Speciální typy částečně uspořádaných sad

Lineárně uspořádané množiny

Nechť je částečně uspořádaná sada. Pokud jsou v libovolných dvou prvcích srovnatelné, pak se množina nazývá lineárně uspořádaná . Lineárně uspořádaná množina se také nazývá dokonale uspořádaná množina nebo jednoduše uspořádaná množina [3] . V lineárně uspořádané množině tedy pro libovolné dva prvky a platí pouze jeden ze vztahů: buď , nebo , nebo . $\langle M,\leqslant \rangle$ $M$ $M$ $A$ $b$ $a<b$ $a=b$ $b<a$

Každá lineárně uspořádaná podmnožina částečně uspořádané množiny se také nazývá řetězec , to znamená, že řetězec v částečně uspořádané množině je její podmnožinou, ve které jsou libovolné dva prvky srovnatelné. $\langle M, \leqslant \rangle$

Z výše uvedených příkladů částečně uspořádaných množin je lineárně uspořádaná pouze množina reálných čísel. Množina reálných funkcí na intervalu (pod podmínkou ), booleovských (pro ), přirozených číslech s relací dělitelnosti není lineárně uspořádána. $[a,b]$ $a<b$ ${\mathcal {P}} (M)$ $|M|\geqslant 2$

V lineárně uspořádané množině jsou pojmy nejmenší a minimum, stejně jako největší a maximum, stejné.

Dobře uspořádané sady

Lineárně uspořádaná množina se nazývá dobře uspořádaná , pokud každá její neprázdná podmnožina má nejmenší prvek [4] . Taková objednávka na sadě se nazývá úplná objednávka v kontextu, kdy ji nelze zaměňovat s úplnou objednávkou ve smyslu úplných částečně objednaných sad .

Klasickým příkladem dobře uspořádané množiny je množina přirozených čísel . Tvrzení, že jakákoli neprázdná podmnožina obsahuje nejmenší prvek, je ekvivalentní principu matematické indukce . Příkladem lineárně uspořádané, ale ne dobře uspořádané množiny je přirozeně uspořádaná množina nezáporných čísel . Ve skutečnosti její podmnožina nemá nejmenší prvek. $\mathbb {N}$ $\mathbb {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Dobře uspořádané množiny hrají v obecné teorii množin mimořádně důležitou roli .

Kompletní poset

Kompletní poset je poset, který má dno — jediný prvek, který předchází jakýkoli jiný prvek a že každá řízená podmnožina má přesnou horní hranici [5] . V λ-kalkulu a informatice se používají kompletní částečně uspořádané množiny , konkrétně je na nich představena Scottova topologie , na jejímž základě je postaven konzistentní model λ-kalkulu a denotační sémantiky . Speciálním případem úplné částečně uspořádané množiny je úplná mříž - pokud má některá podmnožina, která nemusí být nutně směrovaná, nejmenší horní mez, pak se ukáže jako úplná mřížka.

Uspořádaná množina je kompletní částečně uspořádaná množina právě tehdy, pokud má každá funkční monotónnost vzhledem k řádu ( ) alespoň jeden pevný bod :. $M$ $f\dvojtečka M\šipka doprava M$ $a\leqslant b\Rightarrow f(a)\leqslant f(b)$ $\existuje _{{x\in M}}f(x)=x$

Libovolnou sadu lze proměnit v kompletní částečně objednanou vytažením dna a definováním pořadí jako u všech prvků sady . $M$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $m$ $M$

Věty o částečně uspořádaných množinách

Mezi základní věty o částečně uspořádaných množinách patří princip Hausdorffova maxima a Kuratowski-Zornovo lemma . Každý z těchto teorémů je ekvivalentní axiomu výběru .

V kategorii teorie

Na každý poset (a každou předobjednávku ) lze nahlížet jako na kategorii , ve které se každá sada morfismů skládá maximálně z jednoho prvku. Tuto kategorii lze například definovat následovně: jestliže A ≤ B (a prázdná množina jinak); pravidlo skládání morfismu: ( y , z )∘( x , y ) = ( x , z ). Každá kategorie předobjednávky je ekvivalentní částečně objednané sadě. ${\mathrm {Hom}} (A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

Funktor z kategorie-částečně uspořádané množiny (tj. diagram , jehož kategorie indexu je poset) je komutativní diagram .

Poznámky

↑ Kolmogorov, 2004 , s. 36.
↑ Aleksandrov, 1977 , s. 78.
↑ Kolmogorov, 2004 , s. 38.
↑ Kolmogorov, 2004 , s. 40.
↑ Barendregt, 1985 , str. 23.

Literatura

Aleksandrov PS Úvod do teorie množin a obecné topologie. — M .: Nauka , 1977. — 368 s.
Barendregt, Henk. Lambda kalkul. Jeho syntaxe a sémantika = Lambda kalkul. Jeho syntaxe a sémantika. — M .: Mir , 1985. — 606 s. - 4800 výtisků.
Kolmogorov AN, Fomin SV Základy teorie funkcí a funkcionální analýzy. - 7. vyd. — M .: Fizmatlit , 2004. — 572 s. — ISBN 5-9221-0266-4 .
Hausdorff F. Teorie množin. - 4. vyd. — M .: URSS , 2007. — 304 s. - ISBN 978-5-382-00127-2 .
Gurov S.I. Booleovské algebry, uspořádané množiny, svazy: Definice, vlastnosti, příklady. - 2. vyd. — M .: Librokom , 2013. — 352 s. - ISBN 978-5-397-03899-7 .