Delvis beställt set

En delvis ordnad mängd är ett matematiskt koncept som formaliserar de intuitiva idéerna om ordning, arrangemanget av element i en viss sekvens. Informellt är en uppsättning delordnad om det anges vilka element som följer efter vilka (vilka element är större än vilka). I allmänhet kan det visa sig att vissa par av element inte är relaterade av " följer "-relationen .

Som ett abstrakt exempel kan vi ge en samling av delmängder av en uppsättning av tre element ( booleska för en given mängd), ordnade efter relationen av inkludering. $\{x,y,z\}$

Definition och exempel

Orderrelation , eller partiell ordning , på en mängd är en binär relation på(definierad av någon uppsättning) som uppfyller följande villkor [1] : $M$ $\varphi$ $M$ $R_{{\varphi }}\subset M\ gånger M$

Reflexivitet : $\forall a\;(a\varphi a)$
Transitivitet : $\forall a,b,c\;(a\varphi b)\wedge (b\varphi c)\Högerpil a\varphi c$
Antisymmetri : $\forall a,b\;(a\varphi b)\wedge (b\varphi a)\Högerpil a=b$

Mängden som den partiella ordningsrelationen ges på kallas partiellt ordnad . För att vara ganska exakt [2] , då är en delvis ordnad mängd ett par , där är en mängd och är en partiell ordningsrelation på . $M$ $\langle M,\varphi \rangle$ $M$ $\varphi$ $M$

Dimensionen för en delvis ordnad uppsättning är lika med det maximala antalet av uppsättningen linjära order ( ). Denna definition är baserad på egenskapen att en partiell ordning kan utökas till en linjär ordning. $\langle M,\varphi \rangle$ ${\displaystyle <_{i))$ $i\i jag$

Terminologi och notation

Den partiella ordningsrelationen betecknas vanligtvis av symbolen , i analogi med relationen "mindre än eller lika med" på uppsättningen av reella tal . Dessutom, om , då säger vi att elementet inte överstiger , eller att det är underordnat . $\leqslant$ $a\leqslant b$ $a$ $b$ $a$ $b$

Om och , så skriver de , och säger att det är mindre än , eller att det är strikt underordnat . $a\leqslant b$ $a \neq b$ $a<b$ $a$ $b$ $a$ $b$

Ibland, för att skilja en godtycklig ordning på en viss mängd från den kända "mindre än eller lika"-relationen på mängden reella tal, används specialsymbolerna och istället för respektive . $\leqslant$ $<$ $\precurlyeq$ $\prec$

Strikt och icke-strikt ordning

En relation som uppfyller villkoren för reflexivitet, transitivitet och antisymmetri kallas också nonstrict , eller reflexiv ordning . Om villkoret för reflexivitet ersätts med villkoret för antireflexivitet (då ersätts egenskapen antisymmetri med asymmetri):

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

då får vi definitionen av en strikt eller antireflexiv ordning .

Om är en icke-strikt ordning på uppsättningen , då är relationen definierad som: $\leqslant$ $M$ $<$

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

är en strikt ordning på . Omvänt, om är en strikt ordning, då är relationen definierad som $M$ $<$ $\leqslant$

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

är en icke strikt ordning.

Därför är det likadant om man ska ange en icke-strikt ordning eller en strikt ordning på uppsättningen . Resultatet är samma struktur. Skillnaden är bara i terminologi och notation.

Intervall

För ett slutet intervall är [ a , b ] en uppsättning element x som uppfyller olikheten (dvs. och ). Intervallet innehåller åtminstone elementen a och b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Om vi använder den strikta olikheten "<" får vi ett öppet intervall ( a , b ), en uppsättning element x som uppfyller olikheten a < x < b (dvs a < x och x < b ). Ett öppet intervall kan vara tomt även om a < b . Till exempel är det öppna intervallet (1,2) för heltal tomt eftersom det inte finns några heltal i så att 1 < i < 2.

Ibland utökas definitionen för att tillåta a > b . I det här fallet är intervallet tomt.

De halvöppna intervallen [ a , b ) och ( a , b ] definieras på liknande sätt.

En poset är lokalt finit om varje intervall är finita. Till exempel är heltalen lokalt ändliga i sin naturliga ordning. Den lexikografiska ordningen på den direkta produkten ℕ×ℕ är inte lokalt ändlig eftersom t.ex. $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

Begreppet ett intervall i posets bör inte förväxlas med en specifik klass av posets som kallas intervallorder .

Exempel

Mängden reella tal är delvis ordnad enligt relationen "mindre än eller lika med" - . $\mathbb {R}$ $\leqslant$

Låt vara uppsättningen av alla verkliga funktioner definierade på segmentet , det vill säga funktioner i formen $M$ $[a,b]$

f\kolon [a,b]\to {\mathbb {R}}

Låt oss introducera ordningsrelationen på följande sätt: , om ojämlikheten gäller för alla . Uppenbarligen är den introducerade relationen verkligen en partiell ordningsrelation. $\leqslant$ $M$ $f\leqslant g$ $x\i[a,b]$ $f(x)\leqslant g(x)$

Låt vara lite uppsättning. Uppsättningen av alla delmängder (den så kallade boolean ), ordnas delvis genom inkludering . $M$ ${\mathcal {P}}(M)$ $M$ $M\subseteq N$

Mängden av alla naturliga tal är delvis ordnad efter delbarhetsrelationen . $\mathbb {N}$ $m\mitten n$

Relaterade definitioner

Ojämförbara element

Om och är reella tal , gäller bara en av följande relationer: $a$ $b$

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

Om och är element i en godtycklig, delvis ordnad uppsättning, så finns det en fjärde logisk möjlighet: ingen av ovanstående tre relationer är uppfyllda. I det här fallet kallas elementen och ojämförliga . Till exempel, om är uppsättningen av verkligt värderade funktioner på segmentet , då kommer elementen och att vara ojämförbara. Möjligheten att det finns ojämförliga element förklarar innebörden av termen "delvis ordnad uppsättning" . $a$ $b$ $a$ $b$ $M$ $[0,1]$ $f(x) = x$ $g(x)=1-x$

Minimum/Maximum och Minst/Största element

På grund av att det kan finnas par av ojämförbara element i en delvis ordnad uppsättning, introduceras två olika definitioner: minimielementet och minsta elementet .

Ett element sägs vara minimalt om elementet inte finns . Med andra ord, är minimielementet om för något element antingen , eller , eller och är ojämförbara. Ett element kallas det minsta om olikheten gäller för något element . Uppenbarligen är alla minsta element också minimala, men det omvända är inte sant i det allmänna fallet: det minimala elementet kanske inte är det minsta om det finns element som inte är jämförbara med . $en \i M$ $b<a$ $a$ $b\in M$ $b>a$ $b=a$ $b$ $a$ $a$ $b\in M$ $b\geqslant a$ $a$ $b$ $a$

Självklart, om det finns ett minsta element i en uppsättning, så är det unikt. Men det kan finnas flera minimala element. Som ett exempel, betrakta mängden naturliga tal utan enhet, ordnade efter delbarhetsrelationen . Här kommer minimielementen att vara primtal , men det minsta elementet existerar inte. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\mitten$

Begreppen maximala och största element introduceras på liknande sätt.

Topp- och undersida

Låta vara en delmängd av en delvis ordnad uppsättning . Ett element kallas en övre gräns om något element inte överskrider . Konceptet med den nedre gränsen av uppsättningen introduceras på liknande sätt . $A$ $\langle M,\leqslant \rangle$ $u\i M$ $A$ $a\i A$ $u$ $A$

Alla element som är större än någon toppyta kommer också att vara en toppyta . Och alla element mindre än vissa infimum kommer också att vara ett infimum . Dessa överväganden leder till introduktionen av begreppen minst övre gräns och största nedre gräns . $A$ $A$ $A$ $A$

Övre och nedre uppsättningar

För ett element i en delvis ordnad uppsättning är den övre uppsättningen uppsättningen av alla element som föregås av ( ). $m$ $\langle M,\leqslant \rangle$ $M\uparrow m$ $m$ $\{x\in M\mid m\leqslant x\}$

Den lägre uppsättningen definieras dubbelt som uppsättningen av alla element som föregår den givna: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Avbrottsvillkor

En partiellt ordnad uppsättning sägs uppfylla det strikt ökande kedjeavslutningsvillkoret om det inte finns någon oändlig strikt ökande sekvens . Detta tillstånd är ekvivalent med stabiliseringsvillkoret för icke strikt ökande kedjor : varje icke strikt ökande sekvens av dess element stabiliseras. Det vill säga för vilken sekvens som helst av formuläret $M$ $(a_{i}\,<\,a_{i+1})$ $(a_{i}\,\leqslant \,a_{i+1})$

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

det finns ett naturligt sådant $n,$

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

Definierat på ett liknande sätt för minskande kedjor, uppfyller då uppenbarligen det fallande kedjeavslutningsvillkoret om och endast om någon icke strikt minskande sekvens av dess element stabiliseras. Dessa begrepp används ofta i allmän algebra - se till exempel Noetherian ring , Artinian ring . $M$

Specialtyper av delvis ordnade uppsättningar

Linjärt ordnade uppsättningar

Låt vara ett delvis beställt set. Om två element är jämförbara, kallas mängden linjärt ordnad . En linjärt ordnad uppsättning kallas också en perfekt ordnad uppsättning , eller helt enkelt en ordnad uppsättning [3] . Således, i en linjärt ordnad uppsättning, för två element och , gäller en och endast en av relationerna: antingen , eller , eller . $\langle M,\leqslant \rangle$ $M$ $M$ $a$ $b$ $a<b$ $a=b$ $b<a$

Alla linjärt ordnade delmängder av en partiellt ordnad uppsättning kallas också en kedja , det vill säga en kedja i en partiellt ordnad uppsättning är dess delmängd där två valfria element är jämförbara. $\langle M, \leqslant \rangle$

Av exemplen på delvis ordnade mängder ovan är endast mängden reella tal linjärt ordnad. Uppsättningen av verkligt värderade funktioner på intervallet (under villkoret ), booleska (för ), naturliga tal med en delbarhetsrelation är inte linjärt ordnade. $[a,b]$ $a<b$ ${\mathcal {P}}(M)$ $|M|\geqslant 2$

I en linjärt ordnad mängd är begreppen minst och minimum, såväl som störst och maximum, desamma.

Välordnade set

En linjärt ordnad mängd kallas välordnad om var och en av dess icke-tomma delmängder har ett minsta element [4] . En sådan ordning på en uppsättning kallas för en komplett order , i ett sammanhang där den inte kan förväxlas med en komplett order i betydelsen kompletta delvis ordnade uppsättningar .

Ett klassiskt exempel på en välordnad mängd är mängden naturliga tal . Påståendet att varje icke-tom delmängd innehåller det minsta elementet motsvarar principen om matematisk induktion . Ett exempel på en linjärt ordnad men inte välordnad uppsättning är den naturligt ordnade uppsättningen av icke-negativa tal . Dess delmängd har faktiskt inget minsta element. $\mathbb {N}$ $\mathbb {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Välordnade uppsättningar spelar en exceptionellt viktig roll i allmän mängdlära .

Den kompletta posen

En komplett poset är en poset som har en botten — det enda elementet som föregår något annat element och att varje riktad delmängd har en exakt övre gräns [5] . Kompletta partiellt ordnade uppsättningar används i λ-kalkyl och datavetenskap , speciellt Scott-topologi introduceras på dem , på grundval av vilken en konsekvent modell av λ-kalkyl och denotationssemantik byggs . Ett specialfall av en komplett delvis ordnad uppsättning är ett komplett gitter - om någon delmängd, inte nödvändigtvis riktad, har en minsta övre gräns, så visar det sig vara ett komplett gitter.

En beställd uppsättning är en komplett delvis ordnad uppsättning om och endast om varje funktion monoton med avseende på ordern ( ) har minst en fixpunkt : . $M$ $f\kolon M\högerpil M$ $a\leqslant b\Högerpil f(a)\leqslant f(b)$ $\existerar _{{x\i M}}f(x)=x$

Varje set kan förvandlas till ett helt delvis beställt genom att extrahera botten och definiera ordningen som för alla delar av setet . $M$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $m$ $M$

Satser om delvis ordnade mängder

Grundläggande satser om delvis ordnade uppsättningar inkluderar Hausdorff-maximumprincipen och Kuratowski-Zorns lemma . Var och en av dessa satser motsvarar valets axiom .

I kategoriteori

Varje poset (och varje förbeställning ) kan ses som en kategori , där varje uppsättning morfismer består av högst ett element. Till exempel kan denna kategori definieras enligt följande: om A ≤ B (och den tomma uppsättningen annars); morfismsammansättningsregel: ( y , z )∘( x , y ) = ( x , z ). Varje förbeställningskategori motsvarar en delvis beställd uppsättning. ${\mathrm {Hom}}(A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

En funktor från en kategori-delvis ordnad uppsättning (det vill säga ett diagram vars indexkategori är en poset) är ett kommutativt diagram .

Anteckningar

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

Litteratur

Aleksandrov PS Introduktion till mängdlära och allmän topologi. — M .: Nauka , 1977. — 368 sid.
Barendregt, Henk. Lambdakalkyl. Dess syntax och semantik = The Lambda Calculus. Dess syntax och semantik. — M .: Mir , 1985. — 606 sid. - 4800 exemplar.
Kolmogorov AN, Fomin SV Element i funktionsteorin och funktionsanalys. - 7:e uppl. — M .: Fizmatlit , 2004. — 572 sid. — ISBN 5-9221-0266-4 .
Hausdorff F. Mängdlära. - 4:e uppl. — M .: URSS , 2007. — 304 sid. - ISBN 978-5-382-00127-2 .
Gurov S.I. Booleska algebror, ordnade mängder, gitter: Definitioner, egenskaper, exempel. - 2:a uppl. — M .: Librokom , 2013. — 352 sid. - ISBN 978-5-397-03899-7 .