Delvist bestilt sæt - Partially ordered set

Transitive binære forhold

	Symmetrisk	Antisymmetrisk	Tilsluttet	Velbegrundet	Har joins	Har møder	Refleksiv	Irrefleksiv	Asymmetrisk
Også kendt som:			I alt, Semiconnex					Anti-refleksiv
Ækvivalensforhold	Y	✗	✗	✗	✗	✗	Y	✗	✗
Forudbestil (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Delvis rækkefølge	✗	Y	✗	✗	✗	✗	Y	✗	✗
Total forudbestilling	✗	✗	Y	✗	✗	✗	Y	✗	✗
Total ordre	✗	Y	Y	✗	✗	✗	Y	✗	✗
Forudbestilling	✗	✗	Y	Y	✗	✗	Y	✗	✗
Godt kvasi-ordnet	✗	✗	✗	Y	✗	✗	Y	✗	✗
Velordnet	✗	Y	Y	Y	✗	✗	Y	✗	✗
Gitter	✗	Y	✗	✗	Y	Y	Y	✗	✗
Join-semilattice	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗


Strenge delordre	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strenge svag orden	✗	✗	✗	✗	✗	✗	✗	Y	Y
Strenge totalordre	✗	✗	Y	✗	✗	✗	✗	Y	Y
	Symmetrisk	Antisymmetrisk	Tilsluttet	Velbegrundet	Har joins	Har møder	Refleksiv	Irrefleksiv	Asymmetrisk
Definitioner: ${\ displaystyle \ scriptstyle {{\ text {For all}} \, a, b \, {\ text {og}} \, S \ neq \ varnothing:}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow bRa}}$	${\ displaystyle \ scriptstyle {aRb \, {\ text {og}} \, bRa \ Rightarrow a = b}}$	${\ displaystyle \ scriptstyle {a \ neq b \ Højre pil aRb \, {\ tekst {eller}} \, bRa}}$	${\ displaystyle \ scriptstyle {\ min S \, {\ text {eksisterer}}}}$	${\ displaystyle \ scriptstyle {a \ vee b \, {\ tekst {findes}}}}$	${\ displaystyle \ scriptstyle {a \ kile b \, {\ tekst {findes}}}}}$	${\ displaystyle \ scriptstyle {aRa}}$	${\ displaystyle \ scriptstyle {{\ text {not}} \, aRa}}$	${\ displaystyle \ scriptstyle {aRb \ Rightarrow {\ text {not}} \, bRa}}$

Alle definitioner stiller stiltiende krav om, at den homogene relation er transitiv : A " " angiver, at kolonnens egenskab kræves af definitionen af rækkens udtryk (helt til venstre). For eksempel kræver definitionen af en ækvivalensforhold, at den er symmetrisk. Børsnoterede her er yderligere egenskaber, at en homogen forhold kan opfylde.

{\ displaystyle R}

{\ displaystyle \ scriptstyle {{\ text {For all}} \, a, b, c, {\ text {if}} aRb {\ text {og}} bRc {\ text {then}} aRc}.}

Fig.1 Den Hasse diagram af mængden af alle delmængder af en tre-element sæt bestilt af inklusion . Sæt forbundet med en opadgående sti, som og , er sammenlignelige, mens de f.eks. Er og ikke er.

{\ displaystyle \ {x, y, z \},}

{\ displaystyle \ emptyset}

{\ displaystyle \ {x, y \}}

{\ displaystyle \ {x \}}

{\ displaystyle \ {y \}}

I matematik , især ordre teori , en delvist ordnet sæt (også poset ) formaliserer og generaliserer den intuitive begrebet bestilling, sekventering eller arrangement af elementerne i et sæt . Et poset består af et sæt sammen med en binær relation, der angiver, at for nogle par elementer i sættet går et af elementerne forud for det andet i rækkefølgen. Selve forholdet kaldes en "delvis orden". Ordet delvist i navnene "delvis rækkefølge" og "delvist ordnet sæt" bruges som en indikation på, at ikke alle elementpar behøver at være sammenlignelige. Det vil sige, at der kan være par af elementer, for hvilke ingen af elementerne går forud for det andet i stillingen. Delordrer generaliserer således samlede ordrer , hvor hvert par er sammenligneligt.

Uformel definition

En delordre definerer en forestilling om sammenligning . To elementer x og y kan stå i et hvilket som helst af fire indbyrdes udelukkende forhold til hinanden: enten x < y , eller x = y , eller x > y , eller x og y er uforlignelige .

Et sæt med en delvis ordre kaldes et delvist ordnet sæt (også kaldet en poset ). Begrebet ordnet sæt bruges undertiden også, så længe det fremgår af konteksten, at der ikke er meningen med nogen anden form for ordre. Især kan helt ordnede sæt også omtales som "bestilte sæt", især i områder, hvor disse strukturer er mere almindelige end stillinger.

En poset kan visualiseres gennem sit Hasse -diagram , som viser ordningsforholdet.

Delvist ordensforhold

En delvis ordensrelation er en homogen relation, der er transitiv og antisymmetrisk . Der er to fælles underdefinitioner for en delordensrelation, for refleksive og irrefleksive delordensforhold, også kaldet henholdsvis "ikke-streng" og "streng". De to definitioner kan sættes i en en-til-en-korrespondance , så for hver streng delordre er der en unik tilsvarende ikke-streng delordre og omvendt. Udtrykket delordre refererer typisk til et ikke-strengt delordensforhold.

Ikke-streng delordre

En refleksiv , svag eller ikke-streng delvis orden er enhomogen relation≤ over etsæt, der errefleksivt,antisymmetriskogtransitivt. Det vil sige, at altskal tilfredsstille: ${\ displaystyle P}$ ${\ displaystyle a, b, c \ i P,}$

refleksivitet : dvs. at hvert element er relateret til sig selv. ${\ displaystyle a \ leq a}$
antisymmetri : hvis , dvs. ingen to adskilte elementer går forud for hinanden. ${\ displaystyle a \ leq b {\ text {og}} b \ leq a {\ tekst {derefter}} a = b}$
transitivitet : hvis . ${\ displaystyle a \ leq b {\ text {og}} b \ leq c {\ tekst {derefter}} a \ leq c}$

En ikke-streng delvis ordre er også kendt som en antisymmetrisk forudbestilling .

Strenge delordre

En irrefleksiv , stærk ellerstreng delvis ordre påer en homogen relation <der erirrefleksiv,transitivogasymmetrisk; det vil sige, at den opfylder følgende betingelser for alle ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle a, b, c \ i P:}$

Irrefleksivitet : ikke , dvs. intet element er relateret til sig selv ${\ displaystyle a <a}$
Transitivitet : hvis ${\ displaystyle a <b {\ text {og}} b <c {\ text {then}} a <c,}$
Asymmetri : hvis ikke . ${\ displaystyle a <b}$ ${\ displaystyle b <a}$

Irrefleksivitet og transitivitet tilsammen tilsammen asymmetri. Asymmetri indebærer også irrefleksivitet. Med andre ord er et transitivt forhold asymmetrisk, hvis og kun hvis det er irrefleksivt. Så definitionen er den samme, hvis den udelader enten irrefleksivitet eller asymmetri (men ikke begge dele).

En streng delordre er også kendt som en streng forudbestilling .

Korrespondance mellem strenge og ikke-strenge delordensforhold

Fig. 2 Kommutativt diagram om forbindelsen mellem refleksiv lukning ( cls ), irrefleksiv kerne ( ker ) og omvendt relation ( cnv ) langs en eksempelrelation ( Hasse -diagram afbildet).

Strenge og ikke-strenge delordrer på et sæt er nært beslægtede. En ikke-streng delordre kan konverteres til en streng delvis ordre ved at fjerne alle relationer i formen, det vil sige, den strenge delorden er det sæt, hvor er identitetsforholdet på og betegner sæt subtraktion . Omvendt kan en streng delordre <on konverteres til en ikke-streng delordre ved at tilslutte alle relationer af denne form; det vil sige, er en ikke-streng delordre. Så hvis en ikke-streng delordre er, så er den tilsvarende strenge delordre <den irrefleksive kerne givet af ${\ displaystyle P}$ ${\ displaystyle \ leq}$ ${\ displaystyle a \ leq a;}$ ${\ displaystyle <\;: = \ \ leq \ \ setminus \ \ Delta _ {P}}$ ${\ displaystyle \ Delta _ {P}: = \ {(p, p): p \ i P \}}$ ${\ displaystyle P \ gange P}$ ${\ displaystyle \; \ setminus \;}$ ${\ displaystyle P}$ ${\ displaystyle \ leq \;: = \; \ Delta _ {P} \; \ cup \; <\;}$ ${\ displaystyle \ leq}$

{\ displaystyle a <b {\ text {if}} a \ leq b {\ text {og}} a \ neq b.}

Omvendt, hvis <er en streng delordre, så er den tilsvarende ikke-strenge delordre den refleksive lukning givet af:

{\ displaystyle \ leq}

{\ displaystyle a \ leq b {\ text {if}} a <b {\ text {eller}} a = b.}

Dobbelt ordrer

Det dobbelte (eller modsatte ) af en delordens relation defineres ved at lade være det

omvendte forhold mellem , dvs. hvis og kun hvis . Det dobbelte af en ikke-streng delordre er en ikke-streng delordre, og det dobbelte af en streng delordre er en streng delordre. Dualen af en dual af en relation er den oprindelige relation.

{\ displaystyle (P, R^{\ tekst {op}})}

{\ displaystyle (P, R)}

{\ displaystyle R^{\ tekst {op}}}

{\ displaystyle R}

{\ displaystyle xR^{\ text {op}} y}

{\ displaystyle yRx}

Notation

Vi kan betragte en poset som en 3-tupel , eller endda en 5-tupel , hvor og er ikke-strenge delordensforhold, og er strenge delordensforhold, dobbelten af er og og er ligeledes dobbelte af hinanden. ${\ displaystyle (P, \ leq, <)}$ ${\ displaystyle (P, \ leq, <, \ geq,>)}$ ${\ displaystyle (P, \ leq)}$ ${\ displaystyle (P, \ geq)}$ ${\ displaystyle (P, <)}$ ${\ displaystyle (P,>)}$ ${\ displaystyle (P, \ geq)}$ ${\ displaystyle (P, \ leq)}$ ${\ displaystyle (P, <)}$ ${\ displaystyle (P,>)}$

Enhver af de fire delordensforhold på et givet sæt bestemmer unikt de tre andre. Som et spørgsmål om notation kan vi derfor skrive eller antage, at de andre relationer er defineret korrekt. Definition via en ikke-streng delordre er mest almindelig. Nogle forfattere bruger andre symboler end f.eks. Eller til at skelne delordrer fra samlede ordrer. ${\ displaystyle \ leq, <, \ geq, {\ text {og}}>}$ ${\ displaystyle (P, \ leq)}$ ${\ displaystyle (P, <)}$ ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$ ${\ displaystyle \ sqsubseteq}$ ${\ displaystyle \ preceq}$

Når der henvises til delordrer, skal det ikke tages som

supplement til . er det modsatte af den irrefleksive kerne af , som altid er en delmængde af komplementet af , men er lig med komplementet af hvis, og kun hvis , er en samlet orden.

{\ displaystyle \ leq}

{\ displaystyle>}

{\ displaystyle>}

{\ displaystyle \ leq}

{\ displaystyle \ leq}

{\ displaystyle>}

{\ displaystyle \ leq}

{\ displaystyle \ leq}

Eksempler

Standardeksempler på poser, der opstår i matematik, omfatter:

De reelle tal eller generelt et fuldstændigt ordnet sæt, ordnet efter standardforholdet ≤ eller lig med ≤, er en ikke-streng delordre.
På de reelle tal er den sædvanlige

mindre end relation <en streng delvis rækkefølge, og det samme er også tilfældet med den sædvanlige større end relation> på

{\ displaystyle P: = \ mathbb {R},}

{\ displaystyle \ mathbb {R}.}

Per definition er hver streng svag orden en streng delvis ordre.

Sættet af undersæt af et givet sæt (dets effektsæt ) bestilt ved inklusion (se figur 1). Tilsvarende sæt af sekvenser ordnet efter undersekvens og sæt af strenge bestilt af delstreng .

Sættet med naturlige tal udstyret med forholdet mellem delbarhed .

Spidssættet af en rettet acyklisk graf sorteret efter tilgængelighed .

Sættet med underrum i et vektorrum bestilt ved inklusion.

For et delvist ordnet sæt P , sekvensrummet, der indeholder alle sekvenser af elementer fra P , hvor sekvens a går forud for sekvens b, hvis hvert element i a går forud for det tilsvarende element i b . Formelt, hvis og kun hvis for alle ; det vil sige en

komponentvis rækkefølge .

{\ displaystyle \ left (a_ {n} \ right) _ {n \ in \ mathbb {N}} \ leq \ left (b_ {n} \ right) _ {n \ in \ mathbb {N}}}

{\ displaystyle a_ {n} \ leq b_ {n}}

{\ displaystyle n \ in \ mathbb {N}}

For et sæt X og et delvist ordnet sæt P , funktionsrummet indeholder alle funktioner fra X til P , hvor f ≤ g hvis og kun hvis f ( x ) ≤ g ( x ) for alle

{\ displaystyle x \ i X.}

Et hegn , et delvist ordnet sæt defineret af en skiftevis rækkefølge af ordensrelationer a < b > c < d ...

Sættet af begivenheder i speciel relativitet og i de fleste tilfælde, almen relativitet , hvor der for to begivenheder X og Y , X ≤ Y , hvis og kun hvis Y er i fremtiden lyskeglen af X . En hændelse Y kan kun kausalt påvirket af X , hvis X ≤ Y .

Et velkendt eksempel på et delvist ordnet sæt er en samling mennesker, der er ordnet efter genealogisk afstamning. Nogle par mennesker bærer efterkommer-forfader-forholdet, men andre par mennesker er uforlignelige, idet ingen af dem er en efterkommer af den anden.

Ordrer på det kartesiske produkt af delvist bestilte sæt

Fig.3 Leksikografisk rækkefølge på

{\ displaystyle \ mathbb {N} \ times \ mathbb {N}}

Fig.4 Produktordre på

{\ displaystyle \ mathbb {N} \ times \ mathbb {N}}

Fig.5 Refleksiv lukning af streng direkte produktordre på elementer omfattet af (3,3) og dækning (3,3) er markeret med henholdsvis grønt og rødt.

{\ displaystyle \ mathbb {N} \ times \ mathbb {N}.}

For at øge styrken, dvs. faldende sæt par, er tre af de mulige delordrer på det kartesiske produkt af to delvist ordnede sæt (se figur 3-5):

den leksikografiske rækkefølge : ( a , b ) ≤ ( c , d ) hvis a < c eller ( a = c og b ≤ d );
det produkt rækkefølge : ( a , b ) ≤ ( c , d ) hvis en ≤ c og b ≤ d ;
den refleksive lukning af det direkte produkt af de tilsvarende strenge ordrer: ( a , b ) ≤ ( c , d ) if ( a < c og b < d ) eller ( a = c og b = d ).

Alle tre kan på samme måde defineres for det kartesiske produkt med mere end to sæt.

Anvendt på bestilte vektorrum over det samme felt , er resultatet i hvert tilfælde også et ordnet vektorrum.

Se også ordrer på det kartesiske produkt af totalt bestilte sæt .

Summer af delvist bestilte sæt

En anden måde at kombinere to (usammenhængende) stillinger er den ordinære sum (eller lineære sum ), Z = X ⊕ Y , defineret på foreningen af de underliggende sæt X og Y ved rækkefølgen a ≤ _Z b, hvis og kun hvis:

a , b ∈ X med a ≤ _X b eller
a , b ∈ Y med a ≤ _Y b , eller
en ∈ X og b ∈ Y .

Hvis to posetter er velordnede , så er deres ordinære sum det samme.

Serie-parallelle delordener dannes ud fra ordinal sumoperationen (i denne sammenhæng kaldet seriesammensætning) og en anden operation kaldet parallelsammensætning. Parallelsammensætning er den usammenhængende forening af to delvist ordnede sæt, uden ordensforhold mellem elementer i det ene sæt og elementer i det andet sæt.

Afledte forestillinger

Eksemplerne bruger poset bestående af

sættet af alle delmængder af et sæt tre elementer bestilt efter sætinddragelse (se figur 1).

{\ displaystyle ({\ mathcal {P}} (\ {x, y, z \}), \ subseteq)}

{\ displaystyle \ {x, y, z \},}

a er relateret til b, når a ≤ b . Dette betyder ikke, at b også er relateret til a , fordi relationen ikke behøver at være symmetrisk . For eksempel er relateret til, men ikke omvendt. ${\ displaystyle \ {x \}}$ ${\ displaystyle \ {x, y \},}$
a og b er sammenlignelige, hvis a ≤ b eller b ≤ a . Ellers er de uforlignelige . For eksempel og er sammenlignelige, mens og ikke er. ${\ displaystyle \ {x \}}$ ${\ displaystyle \ {x, y, z \}}$ ${\ displaystyle \ {x \}}$ ${\ displaystyle \ {y \}}$
En total orden eller lineær orden er en delvis rækkefølge, hvor hvert elementpar er sammenligneligt, dvs. trikotomi holder. For eksempel de naturlige tal med deres standardrækkefølge.
En kæde er en delmængde af en poset, der er et totalt bestilt sæt. For eksempel er en kæde. ${\ displaystyle \ {\ {\, \}, \ {x \}, \ {x, y, z \} \}}$
Et antikæde er en delmængde af en poset, hvor der ikke er to forskellige elementer, der kan sammenlignes. For eksempel sæt af singletoner ${\ displaystyle \ {\ {x \}, \ {y \}, \ {z \} \}.}$
Et element a siges at være strengt mindre end et element b , hvis a ≤ b og for eksempel er strengt mindre end ${\ displaystyle a \ neq b.}$ ${\ displaystyle \ {x \}}$ ${\ displaystyle \ {x, y \}.}$
Et element a siges at være dækket af et andet element b , skrevet a ⋖ b (eller a <: b ), hvis a er strengt mindre end b, og intet tredje element c passer imellem dem; formelt: hvis både a ≤ b og er sandt, og

a ≤ c ≤ b er falsk for hver c med Brug af den strenge rækkefølge <, kan forholdet a ⋖ b omformuleres ækvivalent til " a < b men ikke a < c < b for enhver c ". For eksempel er dækket af, men er ikke dækket af

{\ displaystyle a \ neq b}

{\ displaystyle a \ neq c \ neq b.}

{\ displaystyle \ {x \}}

{\ displaystyle \ {x, z \},}

{\ displaystyle \ {x, y, z \}.}

Ekstrem

Fig.6 Ovenstående figur med de største og mindste elementer fjernet. I denne reducerede position er den øverste række af elementer alle maksimale elementer, og den nederste række er alle minimale elementer, men der er ikke noget største og ikke mindst element.

Der er flere forestillinger om "største" og "mindst" element i en poset, især: ${\ displaystyle P,}$

Største element og mindst element: Et element er et

største element, hvis for hvert element Et element er det mindste element, hvis for hvert element En poset kun kan have et største eller mindst element. I vores løbende eksempel er sættet det største element og det mindste.

{\ displaystyle g \ i P}

{\ displaystyle a \ i P, a \ leq g.}

{\ displaystyle m \ i P}

{\ displaystyle a \ i P, m \ leq a.}

{\ displaystyle \ {x, y, z \}}

{\ displaystyle \ {\, \}}

Maksimale elementer og minimal elementer: Et element er en maksimal element, hvis der er noget element , således at lignende måde et element er en minimal element, hvis der er noget element , således at hvis en poset har en største element, skal det være den unikke maksimale element, men ellers kan der være mere end et maksimalt element, og tilsvarende for mindst elementer og minimale elementer. I vores løbende eksempel, og er de maksimale og minimale elementer. Når disse fjernes, er der 3 maksimale elementer og 3 minimale elementer (se figur 6).

{\ displaystyle g \ i P}

{\ displaystyle a \ i P}

{\ displaystyle a> g.}

{\ displaystyle m \ i P}

{\ displaystyle a \ i P}

{\ displaystyle a <m.}

{\ displaystyle \ {x, y, z \}}

{\ displaystyle \ {\, \}}

Øvre og nedre grænser : For en delmængde A af P , et element x i P er en øvre grænse for A , hvis en ≤ x , for hvert element en i A . Navnlig x behøver ikke at være i A at være en øvre grænse for A . Ligeledes et element x i P er en nedre grænse A hvis en ≥ x , for hvert element en i A . En største element i P er en øvre grænse for P selv, og en mindste element er en nedre grænse for P . I vores eksempel er sættet en

øvre grænse for samling af elementer

{\ displaystyle \ {x, y \}}

{\ displaystyle \ {\ {x \}, \ {y \} \}.}

Fig.7 Ikke -negative heltal, sorteret efter delbarhed

Som et andet eksempel betragtes de positive heltal , sorteret efter delbarhed: 1 er et mindst element, da det deler alle andre elementer; på den anden side har denne poset ikke et største element (selvom hvis man ville inkludere 0 i poset, som er et multiplum af et helt tal, ville det være et største element; se figur 7). Dette delvist ordnede sæt har ikke engang maksimale elementer, da g deler f.eks. 2 g , hvilket adskiller sig fra det, så g ikke er maksimal. Hvis tallet 1 er udelukket, samtidig med at delbarheden bevares som bestilling på elementerne større end 1, har den resulterende poset ikke det mindste element, men ethvert primtal er et minimalt element for det. I dette poset er 60 en øvre grænse (dog ikke mindst øvre grænse) for delsættet, som ikke har nogen nedre grænse (da 1 ikke er i poset); på den anden side 2 er en nedre grænse for delsættet af kræfter på 2, som ikke har nogen øvre grænse. ${\ displaystyle \ {2,3,5,10 \},}$

Kortlægninger mellem delvist bestilte sæt

Fig.8 Ordensbevarende , men ikke ordensreflekterende (siden f ( u ) ≼ f ( v ), men ikke u v) kort.

{\ displaystyle \ leq}

Fig.9 Ordensisomorfisme mellem delerne på 120 (delvist ordnet efter delbarhed) og delelukkede delmængder af {2, 3, 4, 5, 8 } (delvist ordnet ved indstillet inklusion)

I betragtning af to delvist ordnede sæt ( S , ≤) og ( T , ≼) kaldes en funktion

for ordrebevarende eller monoton eller isoton , hvis det for alt indebærer f ( x ) ≼ f ( y ). Hvis ( U , ≲) er også en delvist ordnet sæt, og begge og er ordre-konservering, deres sammensætning er ordre-konservering, også. En funktion kaldes ordre-reflekterende hvis for alle f ( x ) ≼ f ( y ) indebærer Hvis både ordre-bevarelse og orden-reflekterende, så kaldes en ordre-indlejring af ( S , ≤) i ( T , ≼ ). I sidstnævnte tilfælde er nødvendigvis injektiv , eftersom indebærer og til gengæld ifølge antisymmetry af Hvis en ordre-embedding mellem to Posets S og T eksisterer, man siger, at S kan indlejres i T . Hvis en ordreindlejring er bijektiv , kaldes det en ordensisomorfisme , og delordrene ( S , ≤) og ( T , ≼) siges at være isomorfe . Isomorfe ordener har strukturelt ens Hasse -diagrammer (se figur 8). Det kan vises, at hvis ordre-bevarelse kort og forefindes, således at og udbytter den identitet funktion på S og T henholdsvis derefter S og T er ordre-isomorfe.

{\ displaystyle f: S \ til T}

{\ displaystyle x, y \ i S,}

{\ displaystyle x \ leq y}

{\ displaystyle f: S \ til T}

{\ displaystyle g: T \ til U}

{\ displaystyle g \ circ f: S \ til U}

{\ displaystyle f: S \ til T}

{\ displaystyle x, y \ i S,}

{\ displaystyle x \ leq y.}

{\ displaystyle f}

{\ displaystyle f}

{\ displaystyle f (x) = f (y)}

{\ displaystyle x \ leq y {\ text {og}} y \ leq x}

{\ displaystyle x = y}

{\ displaystyle \ leq.}

{\ displaystyle f: S \ til T}

{\ displaystyle f: S \ til T}

{\ displaystyle g: T \ til U}

{\ displaystyle g \ circ f}

{\ displaystyle f \ circ g}

For eksempel en kortlægning fra sættet af naturlige tal (bestilt af delelighed) til

indstillede effekt kan af naturlige tal (bestilt af sæt inklusion) defineres ved at tage hvert nummer til sættet af sine primdivisorer . Det er ordenebevarende: hvis dividerer, så er hver prime divisor af også en prime divisor af Dog er det hverken injektiv (da det kortlægger både 12 og 6 til ) eller ordensreflekterende (da 12 ikke deler 6). Ved i stedet at tage hvert tal til sættet af dets primære effektdelere definerer et kort, der er ordenbevarende, ordrereflekterende og dermed en ordreindlejring. Det er ikke en orden-isomorfisme (da det f.eks. Ikke knytter et tal til sættet ), men det kan laves til et ved at begrænse sit codomain til figur 9 viser en delmængde af og dets isomorfe billede under Konstruktionen af sådan en orden-isomorfisme til et magtsæt kan generaliseres til en bred klasse af delordner, kaldet distributive gitter , se " Birkhoffs repræsentationsteorem ".

{\ displaystyle f: \ mathbb {N} \ to \ mathbb {P} (\ mathbb {N})}

{\ displaystyle x}

{\ displaystyle y,}

{\ displaystyle x}

{\ displaystyle y.}

{\ displaystyle \ {2,3 \}}

{\ displaystyle g: \ mathbb {N} \ to \ mathbb {P} (\ mathbb {N})}

{\ displaystyle \ {4 \}}

{\ displaystyle g (\ mathbb {N}).}

{\ displaystyle \ mathbb {N}}

{\ displaystyle g.}

Antal delordrer

Sekvens A001035 i OEIS angiver antallet af delordrer på et sæt n mærkede elementer:

Antal n -element binære relationer af forskellige typer
Elementer	Nogen	Transitiv	Refleksiv	Forudbestille	Delvis rækkefølge	Total forudbestilling	Total ordre	Ækvivalensforhold
0	1	1	1	1	1	1	1	1
1	2	2	1	1	1	1	1	1
2	16	13	4	4	3	3	2	2
3	512	171	64	29	19	13	6	5
4	65.536	3.994	4.096	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ² - n}			${\ textstyle \ sum _ {k = 0}^{n} k!}$	n !	${\ textstyle \ sum _ {k = 0}^{n}}$
OEIS	A002416	A006905	A053763	A000798	A001035	A000670	A000142	A000110

Antallet af strenge delordrer er det samme som for delordrer.

Hvis tællingen kun foretages op til isomorfisme, opnås sekvensen 1, 1, 2, 5, 16, 63, 318, ... (sekvens A000112 i OEIS ).

Lineær forlængelse

En delordre på et sæt er en

udvidelse af en anden delordre på, forudsat at for alle elementer, når det også er tilfældet, at En lineær udvidelse er en udvidelse, der også er en lineær (det vil sige total) rækkefølge. Som et klassisk eksempel er den leksikografiske rækkefølge af totalt bestilte sæt en lineær forlængelse af deres produktordre. Hver delordre kan udvides til en samlet ordre ( ordreudvidelsesprincip ).

{\ displaystyle \ leq ^{*}}

{\ displaystyle X}

{\ displaystyle \ leq}

{\ displaystyle X}

{\ displaystyle x, y \ i X,}

{\ displaystyle x \ leq y,}

{\ displaystyle x \ leq ^{*} y.}

I datalogi , algoritmer til at finde lineære udvidelser af delvise ordrer (repræsenteret som Sikring af adgang ordrer rettet acykliske grafer er) kaldes topologiske sortering .

Direkte acykliske grafer

Strenge delordrer svarer direkte til dirigerede acykliske grafer (DAG'er). Hvis en graf er konstrueret ved at tage hvert element af til at være en knude og hvert element for at være en kant, så er hver streng delordre en DAG, og den

transitive lukning af en DAG er både en streng delordre og også en DAG selv . I modsætning hertil ville en ikke-streng delvis ordre have selvsløjfer ved hver knude og derfor ikke være en DAG.

{\ displaystyle P}

{\ displaystyle \ leq}

I kategoriteori

Hvert poset (og hvert forudbestilte sæt ) kan betragtes som en kategori, hvor der for objekter og højst er én

morfisme fra til Mere eksplicit, lad hom ( x , y ) = {( x , y )} hvis x ≤ y ( og ellers det tomme sæt) og Sådanne kategorier kaldes undertiden posetal .

{\ displaystyle x}

{\ displaystyle y,}

{\ displaystyle x}

{\ displaystyle y.}

{\ displaystyle (y, z) \ circ (x, y) = (x, z).}

Posetter svarer til hinanden, hvis og kun hvis de er isomorfe . I en poset er det mindste element, hvis det eksisterer, et indledende objekt , og det største element, hvis det findes, er et terminalobjekt . Hvert forudbestilte sæt svarer også til en poset. Endelig er hver underkategori af en poset isomorfisme-lukket .

Delordre i topologiske rum

Hvis er et delvist ordnet sæt, der også har fået strukturen af et

topologisk rum , så er det sædvanligt at antage, at det er en lukket delmængde af det topologiske produktrum. Under denne antagelse opfører partielle ordensforhold sig godt ved grænser i den forstand, at hvis og for alle så

{\ displaystyle P}

{\ displaystyle \ {(a, b): a \ leq b \}}

{\ displaystyle P \ gange P.}

{\ displaystyle a_ {i} \ til a,}

{\ displaystyle b_ {i} \ to b,}

{\ displaystyle i}

{\ displaystyle a_ {i} \ leq b_ {i},}

{\ displaystyle a \ leq b.}

Intervaller

En interval i en poset P er en delmængde $I$ af P med den egenskab, at, for ethvert x og y i $I$ og enhver z i P , hvis x ≤ z ≤ y , så z er også i $jeg$ . (Denne definition generaliserer intervaldefinitionen for reelle tal.)

For a ≤ b er det lukkede interval $[a, b]$ mængden af elementer x, der opfylder a ≤ x ≤ b (det vil sige a ≤ x og x ≤ b ). Den indeholder mindst elementerne a og b .

Ved hjælp af den tilsvarende strenge relation "<" er det åbne interval $(a, b)$ sættet af elementer x, der opfylder 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)$ på heltalene tomt, da der ikke er nogen heltal $I,$ således at $1 < I <2$ .

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

Nogle gange udvides definitionerne til at tillade a > b , i hvilket tilfælde intervallet er tomt.

Et interval $I$ er afgrænset, hvis der findes elementer , som

I

\subseteq

[

a

,

b

]

. Hvert interval, der kan repræsenteres i intervalnotation, er naturligvis afgrænset, men det modsatte er ikke sandt. Lad for eksempel

P

=

(0, 1)

\cup

(1, 2)

\cup

(2, 3)

som et underposet af de reelle tal . Undergruppen

(1, 2)

er et begrænset interval, men det har ingen infimum eller supremum i P , så kan det ikke være skrevet i intervallet notation anvendelse elementer af P .

{\ displaystyle a, b \ i P}

En poset kaldes lokalt endelig, hvis hvert afgrænset interval er begrænset. For eksempel er heltalene lokalt begrænsede under deres naturlige rækkefølge. Den leksikografiske rækkefølge på det kartesiske produkt er ikke lokalt endelig, da

(1, 2) \leq (1, 3) \leq (1, 4) \leq (1, 5) \leq ... \leq (2, 1)

. Ved hjælp af intervalnotationen kan egenskaben " a er dækket af b " omformuleres tilsvarende som

{\ displaystyle \ mathbb {N} \ times \ mathbb {N}}

{\ displaystyle [a, b] = \ {a, b \}.}

Dette koncept om et interval i en delordre bør ikke forveksles med den særlige klasse af delordrer, der kaldes intervallordrene .

Se også

Antimatroid , en formalisering af bestillinger på et sæt, der tillader mere generelle bestillingsfamilier end poseter
Årsagssæt , en posetbaseret tilgang til kvantegravitation
Sammenlignelighed graf
Komplet delordre
Directed set - Set med en forudbestilling, hvor to elementer altid begge er mindre end eller lig med et tredje element
Gradueret poset
Incident algebra
Gitter - Abstrakt struktur studeret i de matematiske underdiscipliner af ordensteori og abstrakt algebra
Lokalt begrænset poset
Möbius -funktion på poseter
Indlejret sæt samling
Bestil polytop
Bestilt felt
Bestilt gruppe
Bestilt vektorrum
Posettopologi , en slags topologisk rum, der kan defineres ud fra enhver poset
Scott kontinuitet - kontinuitet i en funktion mellem to delordner.
Semilatice
Semiorder
Stokastisk dominans
Strenge svag rækkefølge - streng delvis ordre "<", hvor forholdet "hverken a < b eller b < a " er transitivt.
Total ordre - Ordre, hvis elementer alle er sammenlignelige
Træ - Datastruktur for sæt inkludering
Zorns lemma - Matematisk forslag svarende til valgaksiomet

Noter

Citater

Referencer

Davey, BA; Priestley, HA (2002). Introduktion til gitter og orden (2. udgave). New York: Cambridge University Press. ISBN 978-0-521-78451-1.
Deshpande, Jayant V. (1968). "Om kontinuitet i en delvis ordre" . Proceedings of the American Mathematical Society . 19 (2): 383–386. doi : 10.1090/S0002-9939-1968-0236071-7 .
Schmidt, Gunther (2010). Relationsmatematik . Encyclopedia of Mathematics og dets applikationer. 132 . Cambridge University Press. ISBN 978-0-521-76268-7.
Bernd Schröder (11. maj 2016). Bestilte sæt: En introduktion med forbindelser fra Combinatorics til topologi . Birkhäuser. ISBN 978-3-319-29788-0.
Stanley, Richard P. (1997). Enumerative Combinatorics 1 . Cambridge studier i avanceret matematik. 49 . Cambridge University Press. ISBN 0-521-66351-2.

Languages

In other projects