Delvis bestilt sett

I matematikk formaliserer og generaliserer et delvis ordnet sett (noen ganger kalt poset fra det engelske delvis ordnede settet ) den intuitive forestillingen om orden eller arrangement mellom elementene i et sett . Et delvis ordnet sett er et sett utstyrt med en ordrerelasjon som indikerer at for visse par av elementene er det ene mindre enn det andre. Alle elementene er ikke nødvendigvis sammenlignbare, i motsetning til tilfellet med et sett utstyrt med en total ordre .

Hvis settet er endelig, har vi en grafisk fremstilling av det delvis ordnede settet, Hasse-diagrammet , som kan gjøre det lettere å jobbe med det. Hvis settet er uendelig, kan vi tegne en del av Hasse-diagrammet.

Definisjon og eksempler

Definisjon

En orden (eller delvis orden) er en binær relasjon på et sett P som er refleksivt , antisymmetrisk og transitivt . Det er notert ≤.

De tre foregående aksiomene blir omskrevet:

a ≤ a (refleksivitet).
Hvis a ≤ b og b ≤ a , så er a = b (antisymmetri).
Hvis a ≤ b og b ≤ c , så a ≤ c (transitivitet).

Så det er ikke nødvendigvis en total ordre .

Eksempler

Settet med naturlige heltall, forsynt med delbarhet, er et uendelig, delvis ordnet sett.
Et sett av mennesker med forholdet mellom genealogiske avstamning er en delvis ordnet sett. For eksempel er to søstre dårligere enn moren, men er ikke sammenlignbare med hverandre.
Det sett av deler av et gitt sett forsynt med inkluderingen, danner en delvis ordnet sett. Hvis det gitte settet er endelig, er dets sett med deler endelig (nærmere bestemt for , vi har ). Figuren nedenfor representerer Hasse-diagrammet til et sett med 3 elementer. $\ # A = n$ $\ #P (A) = 2 ^ {n}$

For å ta en konkret sak (faktisk isomorf ) av det forrige eksemplet, kan et sett med mennesker utstyrt med forholdet donere blod til å danne et sett som delvis er ordnet i henhold til ABO- og Rhesus- systemene . Elementene x , y og z i det mer generelle foregående eksempel blir instantiert av antigenene A, B og D (Rh +) til individet. For eksempel kan en gruppe O + -individ gi til en gruppe B + -mottaker, men ingen kan gi til eller motta fra en gruppe A- person.
Settet med komplekse tall gitt i følgende rekkefølge forhold er delvis bestilt: . $a + ib <a '+ ib' \ Leftrightarrow \ left \ {{\ begin {matrix} a <a '\\ b <b' \ end {matrix}} \ right.$

For eksempel kan vi ikke sammenligne 1 og i . Denne ordren er ikke kompatibel med kroppsstrukturen til . $\ mathbb {C}$

Funksjonssettene til in , levert med ordreforholdet si , er et delvis ordnet uendelig sett. Intuitivt er en funksjon mindre enn en annen hvis kurven alltid er under den andre kurven. Vi kan generalisere dette eksemplet til funksjonene til et sett X i et delvis ordnet sett P. $\ mathbb {R}$ $\ mathbb {R}$ $f <g$ $\ forall x, f (x) <g (x)$
Settet av skillevegger med et gitt sett er delvis bestilt, med rekkefølgen gitt ved raffinering av skilleveggene: ved definisjon, er en skillevegg finere enn et annet dersom det splitter de delene av den andre i små deler..
Vi kan gi settet med polynomer med n variabler med en delvis ordensrelasjon. Vi starter med å sammenligne monomene med n variabler via den leksikografiske rekkefølgen indusert av (denne leksikografiske rekkefølgen er total). Vi sammenligner to polynomer og sier at det er strengt mindre enn om noe ikke-null monomial er strengt mindre enn noe ikke-null monomial av . Denne ordensforholdet på polynomene er delvis. $R [X_ {1}, ..., X_ {n}]$ $1 <X_ {1} <X_ {2} <... <X_ {n}$ $P$ $Spørsmål$ $P$ $Spørsmål$ $P$ $Spørsmål$

Spesifikasjoner for delvis bestilte sett

Greatest Element , Maximum Element og Upper Bound

La P være et delvis bestilt sett:

Et element a av P er et større element hvis for et element b av P, b ≤ a. Et delvis bestilt sett kan bare ha ett større element.

Et element a av P er et maksimalt element hvis det ikke er noe element b av P slik at b> a. Hvis P har et større element, er det det unike maksimale elementet til P.

For en delmengde A av P er elementet x av P en øvre grense av A hvis a ≤ x for et hvilket som helst element a av A. x ikke nødvendigvis tilhører A. Det største elementet av P, s 'det finnes, er et øvre grense for P.

Eksempel : vurder settet med positive heltall, ordnet etter divisjon. 1 er det minste elementet. På den annen side har ikke dette settet et større element. Hvis vi nå ekskluderte element 1, ville det delvis ordnede settet ikke lenger ha et mindre element, men en uendelig minimal element: primtallene .

Hvis E er et delvis ordnet sett, eksisterer det ikke nødvendigvis et større element. Hvis E er et endelig, delvis ordnet sett, vil det inneholde minst ett maksimalt element. Hvis E er et uendelig induktivt sett , kan vi bruke Zorns lemma for å ha eksistensen av et maksimalt element.

Visse forhold på de største elementene og de minste elementene i et delvis ordnet sett fører til definisjonen av et gitter .

Av samme resonnement oppnår vi det minste elementet, de minimale elementene og den nedre grensen.

Sammenlignbarhet

Hvis a ≤ b eller a b, så er a og b sammenlignbare. I Hasse-diagrammet ovenfor er {x} og {x, y, z} sammenlignbare, mens {x} og {y} ikke er det. En delvis rekkefølge der et par element er sammenlignbare, kalles en total rekkefølge , og settet kalles en streng . Et sett der ingen sammenlignbare par kan bli funnet, kalles et antikjede (f.eks. Settet {{x}, {y }, {z}} i figuren ovenfor) $\ geq$

Gjenoppretting

Vi sier at et element a er dekket av et element b, som skrives a <: b, hvis a er strengt mindre enn b og det ikke er noe element c mellom hverandre. For eksempel er {x} dekket av {x, z} i figuren ovenfor, men ikke av {x, y, z}.

Koblinger til enkle komplekser

En viktig klasse med enkle komplekser kommer fra endelige, delvis ordnede sett. Vi definerer komplekset av orden D (P) for et endelig, delvis ordnet sett P som værende settet med kjeder av P. Komplekset av orden er trivielt et forenklet kompleks.

Studiet av det delvis bestilte settet gir informasjon om dets ordrekompleks, og derfor er det interessant å studere et forenklet kompleks som ordrekomplekset til et delvis ordnet sett.

Drift på delvis bestilte sett

Kartesisk produkt delvis bestilt sett

For å eliminere mangfoldet av mulige ordrelasjoner under et delvis ordnet sett, kan vi definere tre forskjellige regler:

Den leksikografiske rekkefølgen : ( a , b ) ≤ ( c , d ) hvis a < c eller ( a = c og b ≤ d );
Det multiplikative rekkefølge : ( en , b ) ≤ ( c , d ) hvis en ≤ c og b ≤ d ;
Den refleksive lukkingen av det direkte produktet : ( a , b ) ≤ ( c , d ) hvis ( a < c og b < d ) eller ( a = c og b = d ).

Alle disse reglene gjelder også for produkter av mer enn to delvis bestilte sett.

Lokal endelighet

Et delvis ordnet sett E sies å være lokalt endelig hvis intervallet for alle er endelig. Denne antagelsen gjør det mulig å generalisere Möbius inversjonsformelen . $x, y \ i E$ $[x, y]$

Referanser

(no) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ detalj av utgaver ] ( online presentasjon )

Se også