Delvist bestilt sæt

Et delvist ordnet sæt er et matematisk koncept, der formaliserer de intuitive ideer om orden, arrangementet af elementer i en bestemt rækkefølge. Uformelt ordnes et sæt delvist, hvis det er angivet, hvilke elementer der følger efter hvilke (hvilke elementer er større end hvilke). Generelt kan det vise sig, at nogle par af elementer ikke er relateret af " følger "-forholdet .

Som et abstrakt eksempel kan vi give en samling af delmængder af et sæt af tre elementer ( boolsk værdi for en given mængde), ordnet efter inklusionsforholdet. $\{x,y,z\}$

Definition og eksempler

Ordrerelation , eller delvis rækkefølge , på et sæt er en binær relation på(defineret af et sæt), der opfylder følgende betingelser [1] : $M$ $\varphi$ $M$ $R_{{\varphi }}\subset M\ gange M$

Refleksivitet : $\forall a\;(a\varphi a)$
Transitivitet : $\forall a,b,c\;(a\varphi b)\wedge (b\varphi c)\Højrepil a\varphi c$
Antisymmetri : $\forall a,b\;(a\varphi b)\wedge (b\varphi a)\Højrepil a=b$

Mængden, som den partielle ordensrelation er givet på, kaldes delvis ordnet . For at være helt præcis [2] , så er et delvist ordnet sæt et par , hvor er et sæt, og er en delvis ordensrelation på . $M$ $\langle M,\varphi \rangle$ $M$ $\varphi$ $M$

Dimensionen af et delvist ordnet sæt er lig med det maksimale antal af sættet af lineære ordrer ( ). Denne definition er baseret på egenskaben til at udvide en delordre til en lineær. $\langle M,\varphi \rangle$ ${\displaystyle <_{i))$ $i\i I$

Terminologi og notation

Den partielle ordensrelation er normalt angivet med symbolet , analogt med forholdet "mindre end eller lig med" på sættet af reelle tal . Desuden, hvis , så siger vi, at elementet ikke overstiger , eller at det er underordnet . $\leqslant$ $a\leqslant b$ $-en$ $b$ $-en$ $b$

Hvis og , så skriver de , og siger, at det er mindre end , eller at det strengt taget er underordnet . $a\leqslant b$ $a \neq b$ $a<b$ $-en$ $b$ $-en$ $b$

Nogle gange, for at skelne en vilkårlig rækkefølge på et bestemt sæt fra den kendte "mindre end eller lig"-relation på sættet af reelle tal, bruges de specielle symboler og i stedet for hhv . $\leqslant$ $<$ $\precurlyeq$ $\præc$

Streng og ikke-streng rækkefølge

En relation, der opfylder betingelserne for refleksivitet, transitivitet og antisymmetri, kaldes også nonstrict eller refleksiv orden . Hvis betingelsen om refleksivitet erstattes af betingelsen om antirefleksivitet (så er egenskaben for antisymmetri erstattet af asymmetri):

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

så får vi definitionen af en streng eller antirefleksiv orden .

Hvis er en ikke-streng rækkefølge på sættet , så er relationen defineret som: $\leqslant$ $M$ $<$

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

er en streng ordre på . Omvendt, hvis er en streng rækkefølge, så er relationen defineret som $M$ $<$ $\leqslant$

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

er en ikke-streng ordre.

Derfor er det lige meget, om der skal angives en ikke-streng rækkefølge eller en streng rækkefølge på sættet . Resultatet er den samme struktur. Forskellen er kun i terminologi og notation.

Interval

For et lukket interval er [ a , b ] et sæt af elementer x , der opfylder uligheden (dvs. og ). Intervallet indeholder mindst elementerne a og b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Hvis vi bruger den strenge ulighed "<", får vi et åbent interval ( a , b ), et sæt af elementer x , der opfylder uligheden a < x < b (dvs. a < x og x < b ). Et åbent interval kan være tomt, selvom a < b . For eksempel er det åbne interval (1,2) for heltal tomt, fordi der ikke er heltal i , således at 1 < i < 2.

Nogle gange udvides definitionen til at tillade a > b . I dette tilfælde er intervallet tomt.

De halvåbne intervaller [ a , b ) og ( a , b ] er defineret på lignende måde.

En poset er lokalt finit hvis hvert interval er endeligt. For eksempel er heltalene lokalt endelige i deres naturlige rækkefølge. Den leksikografiske rækkefølge på det direkte produkt ℕ×ℕ er ikke lokalt begrænset, fordi f.eks . $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

Begrebet et interval i posets bør ikke forveksles med en specifik klasse af posets kendt som interval orders .

Eksempler

Mængden af reelle tal er delvist ordnet efter relationen "mindre end eller lig med" - . $\mathbb {R}$ $\leqslant$

Lade være sættet af alle reelle værdier funktioner defineret på segmentet , det vil sige funktioner af formen $M$ $[a,b]$

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

Lad os introducere ordensrelationen på som følger: , hvis uligheden gælder for alle . Det er klart, at den introducerede relation faktisk er en delvis ordensrelation. $\leqslant$ $M$ $f\leqslant g$ $x\i[a,b]$ $f(x)\leqslant g(x)$

Lad være et sæt. Sættet af alle delmængder (den såkaldte boolean ), er delvist ordnet ved inklusion . $M$ ${\mathcal {P}}(M)$ $M$ $M\subseteq N$

Mængden af alle naturlige tal er delvist ordnet efter delelighedsrelationen . $\mathbb {N}$ $m\midt n$

Relaterede definitioner

Usammenlignelige elementer

Hvis og er reelle tal , gælder kun én af følgende relationer: $-en$ $b$

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

Hvis og er elementer i et vilkårligt delvist ordnet sæt, så er der en fjerde logisk mulighed: ingen af de ovennævnte tre relationer er opfyldt. I dette tilfælde kaldes elementerne og uforlignelige . For eksempel, hvis er sættet af funktioner med reel værdi på segmentet , så vil elementerne og være uforlignelige. Muligheden for eksistensen af uforlignelige elementer forklarer betydningen af udtrykket "delvis ordnet sæt" . $-en$ $b$ $-en$ $b$ $M$ $[0,1]$ $f(x) = x$ $g(x)=1-x$

Minimum/maksimum og mindst/største elementer

På grund af det faktum, at der kan være par af uforlignelige elementer i et delvist ordnet sæt, introduceres to forskellige definitioner: minimumselementet og det mindste element .

Et element siges at være minimalt , hvis elementet ikke eksisterer . Med andre ord, er minimumselementet, hvis for ethvert element enten , eller , eller og er uforlignelige. Et element kaldes det mindste , hvis uligheden gælder for noget element . Det er klart, at ethvert mindste element også er minimalt, men det omvendte er ikke sandt i det generelle tilfælde: det minimale element er muligvis ikke det mindste, hvis der er elementer , der ikke er sammenlignelige med . $en \i M$ $b<a$ $-en$ $b\i M$ $b>a$ $b=a$ $b$ $-en$ $-en$ $b\i M$ $b\geqslant a$ $-en$ $b$ $-en$

Det er klart, hvis der er et mindste element i et sæt, så er det unikt. Men der kan være flere minimale elementer. Som et eksempel kan du overveje mængden af naturlige tal uden en enhed, ordnet efter delelighedsrelationen . Her vil minimumselementerne være primtal , men det mindste element eksisterer ikke. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\midt$

Begreberne maksimale og største elementer introduceres på samme måde.

Top- og bundflader

Lad være en delmængde af et delvist ordnet sæt . Et element kaldes en øvre grænse, hvis et element ikke overskrider . Konceptet med den nedre grænse af sættet introduceres på samme måde . $EN$ $\langle M,\leqslant \rangle$ $u\i M$ $EN$ $a\i A$ $u$ $EN$

Ethvert element større end en topflade vil også være en topflade . Og ethvert element mindre end nogle infimum vil også være et infimum . Disse overvejelser fører til introduktionen af begreberne mindst øvre grænse og største nedre grænse . $EN$ $EN$ $EN$ $EN$

Øvre og nedre sæt

For et element i et delvist ordnet sæt er det øverste sæt sættet af alle elementer efter ( ). $m$ $\langle M,\leqslant \rangle$ $M\uparrow m$ $m$ $\{x\in M\mid m\leqslant x\}$

Det nederste sæt er defineret dobbelt som det sæt af alle elementer, der går forud for det givne: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Pausebetingelser

Et delvist ordnet sæt siges at opfylde den strengt stigende kædetermineringsbetingelse, hvis der ikke er en uendelig strengt stigende sekvens . Denne betingelse svarer til stabiliseringsbetingelsen for ikke-strengt stigende kæder : enhver ikke-strengt stigende sekvens af dens elementer stabiliseres. Det vil sige for enhver sekvens af formen $M$ $(a_{i}\,<\,a_{i+1})$ $(a_{i}\,\leqslant \,a_{i+1})$

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

der er en naturlig sådan $n,$

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

Defineret på en lignende måde for aftagende kæder, opfylder så åbenbart den faldende kædetermineringsbetingelse, hvis og kun hvis en ikke-strengt faldende sekvens af dens elementer stabiliserer sig. Disse begreber bruges ofte i generel algebra - se for eksempel Noetherian ring , Artinian ring . $M$

Særlige typer af delvist ordnede sæt

Lineært ordnede sæt

Lad være et delvist bestilt sæt. Hvis to elementer er sammenlignelige, kaldes sættet lineært ordnet . Et lineært ordnet sæt kaldes også et perfekt ordnet sæt , eller simpelthen et ordnet sæt [3] . I et lineært ordnet sæt gælder således for to elementer og , en og kun en af relationerne: enten , eller , eller . $\langle M,\leqslant \rangle$ $M$ $M$ $-en$ $b$ $a<b$ $a=b$ $b<a$

Enhver lineært ordnet delmængde af et delvist ordnet sæt kaldes også en kæde , det vil sige, at en kæde i et delvist ordnet sæt er dens undermængde, hvori to vilkårlige elementer er sammenlignelige. $\langle M, \leqslant \rangle$

Af eksemplerne på delvist ordnede mængder ovenfor er kun mængden af reelle tal lineært ordnet. Mættet af funktioner med reel værdi på intervallet (under betingelsen ), boolske (for ), naturlige tal med en delelighedsrelation er ikke lineært ordnet. $[a,b]$ $a<b$ ${\mathcal {P}}(M)$ $|M|\geqslant 2$

I et lineært ordnet sæt er begreberne mindst og minimum samt størst og maksimum de samme.

Velordnede sæt

En lineært ordnet mængde kaldes velordnet, hvis hver af dens ikke-tomme delmængder har et mindste element [4] . En sådan rækkefølge på et sæt kaldes en komplet rækkefølge i en sammenhæng, hvor den ikke kan forveksles med en komplet rækkefølge i betydningen fuldstændige delvist ordnede sæt .

Et klassisk eksempel på et velordnet sæt er sættet af naturlige tal . Udsagnet om, at enhver ikke-tom delmængde indeholder det mindste element, svarer til princippet om matematisk induktion . Et eksempel på et lineært ordnet, men ikke velordnet sæt er det naturligt ordnede sæt af ikke-negative tal . Faktisk har dens undergruppe ikke det mindste element. $\mathbb {N}$ $\mathbb {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Velordnede sæt spiller en usædvanlig vigtig rolle i generel mængdeteori .

Det komplette poset

En komplet poset er en poset, der har en bund - det eneste element, der går forud for ethvert andet element, og at hver rettet delmængde har en nøjagtig øvre grænse [5] . Komplette delvist ordnede sæt bruges i λ-regning og datalogi , især Scott-topologi introduceres på dem , på grundlag af hvilken en konsistent model af λ-regning og denotationel semantik bygges . Et særligt tilfælde af et komplet delvist ordnet sæt er et komplet gitter - hvis en delmængde, ikke nødvendigvis rettet, har en mindst øvre grænse, så viser det sig at være et komplet gitter.

Et ordnet sæt er et komplet delvist ordnet sæt, hvis og kun hvis hver funktion monotone i forhold til rækkefølgen ( ) har mindst ét fikspunkt : . $M$ $f\kolon M\højrepil M$ $a\leqslant b\Højrepil f(a)\leqslant f(b)$ $\eksisterer _{{x\i M}}f(x)=x$

Ethvert sæt kan omdannes til et komplet delvist bestilt ved at trække bunden ud og definere rækkefølgen som for alle elementer i sættet . $M$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $m$ $M$

Sætning om delvist ordnede mængder

Grundlæggende sætninger om delvist ordnede sæt inkluderer Hausdorff-maksimumprincippet og Kuratowski-Zorn-lemmaet . Hver af disse sætninger svarer til det valgte aksiom .

I kategoriteori

Hvert poset (og hver forudbestilling ) kan ses som en kategori , hvor hvert sæt af morfismer består af højst ét element. For eksempel kan denne kategori defineres som følger: hvis A ≤ B (og det tomme sæt ellers); morfismesammensætningsregel: ( y , z )∘( x , y ) = ( x , z ). Hver forudbestillingskategori svarer til et delvist bestilt sæt. ${\mathrm {Hom}}(A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

En funktor fra et kategori-delvist ordnet sæt (det vil sige et diagram , hvis indekskategori er en poset) er et kommutativt diagram .

Noter

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

Litteratur

Aleksandrov PS Introduktion til mængdeteori og generel topologi. — M .: Nauka , 1977. — 368 s.
Barendregt, Henk. Lambdaregning. Dens syntaks og semantik = The Lambda Calculus. Dens syntaks og semantik. — M .: Mir , 1985. — 606 s. - 4800 eksemplarer.
Kolmogorov AN, Fomin SV Elementer i funktionsteorien og funktionel analyse. - 7. udg. — M .: Fizmatlit , 2004. — 572 s. — ISBN 5-9221-0266-4 .
Hausdorff F. Sæteori. - 4. udg. — M .: URSS , 2007. — 304 s. - ISBN 978-5-382-00127-2 .
Gurov S.I. Booleske algebraer, ordnede mængder, gitter: Definitioner, egenskaber, eksempler. - 2. udg. — M .: Librokom , 2013. — 352 s. - ISBN 978-5-397-03899-7 .