Bestillingsforhold

En ordrerelasjon i et sett er en binær relasjon i dette settet som gjør at elementene kan sammenlignes med hverandre på en konsistent måte. Et sett utstyrt med en ordrerelasjon er et ordnet sett . Vi sier også at forholdet definerer på dette settet en ordre struktur eller ganske enkelt en ordre .

Definisjoner og eksempler

Bestillingsforhold

En ordensrelasjon er en refleksiv , antisymmetrisk og transitiv binær relasjon : la E være et sett; en intern relasjon ≤ på E er en ordrerelasjon hvis for alle x- , y- og z- elementene i E :

x ≤ x (refleksivitet)
( x ≤ y og y ≤ x ) ⇒ x = y (antisymmetri)
( x ≤ y og y ≤ z ) ⇒ x ≤ z (transitivitet)

Selve formen for disse aksiomene lar oss bekrefte at de også er verifisert av den gjensidige binære relasjonen ≥, definert av

y ≥ x hvis og bare hvis x ≤ y .

Til ethvert forhold mellom ordre er derfor assosiert et motsatt forhold mellom ordre på samme sett; formlene x ≤ y og y ≥ x kan leses om hverandre: " x er mindre enn y ", eller " x er mindre enn y ", eller " y er større enn x ", eller " y er større enn x " (eller noen ganger er " x høyst lik y ", eller " y er minst lik x ").

Vi forbinder også med en hvilken som helst rekkefølge av orden ≤, et forhold kjent som av streng orden notert da <(som ikke er en ordrelasjon i den forstand som er definert tidligere siden refleksiviteten ikke er oppfylt), som er begrensningen av forholdet mellom orden og parene med forskjellige elementer:

x < y hvis og bare hvis x ≤ y og x ≠ y .

Formelen x < y er også skrevet y > x , og lyder: " x er strengt mindre enn y ", eller " x er strengt mindre enn y ", " y er strengt større enn x ", eller " y er strengt større enn x ”.

En ordrerelasjon i betydningen av definisjonen ovenfor blir noen ganger referert til som bred orden .

Noen ordensrelasjoner er totale relasjoner , dvs. to elementer i E er alltid sammenlignbare : for alle x , y for E :

x ≤ y eller y ≤ x .

Vi sier da at ≤ er en relasjon av total ordre , og at settet E er totalt ordnet av denne relasjonen. En ordrerelasjon på E sies å være delvis hvis den ikke er total, og E blir deretter delvis ordnet . Det skal bemerkes at på engelsk betegner delvis ordre enhver ordre, som derfor kan være total. Denne terminologien brukes noen ganger også på fransk.

Ordnet sett

Et bestilt sett er et sett som har en ordrerelasjon. Hvis et ordnet sett er endelig, kan det representeres grafisk i form av et Hasse-diagram , som ligner på den vanlige representasjonen av en graf på papir, noe som kan gjøre det lettere å jobbe med det. Hvis det er uendelig, kan vi tegne en del av Hasse-diagrammet.

Eksempler og moteksempler

Relasjonen "er mindre (eller lik) til" er en relasjon av total orden på settet med heltall ( naturlig eller relativ ), på settet med rasjonelle eller settet med realer .
Gitt et ordnet sett ( E , ≤), er den leksikografiske rekkefølgen på settet med n -upler av elementene i E "ordbokrekkefølgen", enklere å definere ved den tilhørende strenge rekkefølgen : ( x 1 ,…, X n ) < ( y 1 ,…, y n ) hvis x i = y i for alle indekser i opp til en viss k < n og x k +1 < y k +1 .
Inkluder forhold, "er en undergruppe av" eller "inngår i" er en ordre forhold på settet E av delene av et sett X . Hvis X er endelig, er E endelig (nærmere bestemt hvis X inneholder n elementer, inneholder E 2 n ). Figur 1 representerer Hasse-diagrammet for ( E , ⊂) for n = 3.
Enhver begrensning på en del F av E av pålegg på E er en bestilling av F . Spesielt (i henhold til forrige punkt): på ethvert sett F av deler av et sett X er inkluderingen en ordensrelasjon - dette "eksemplet" er faktisk generisk: hver ordre er isomorf til en rekkefølge av denne formen;
Den deleligheten forhold er et delvis orden forhold på naturlige tall . Figur 2 representerer Hasses diagram over begrensningen til heltall fra 0 til 9.
Rekkefølgen av inklusjons (se ovenfor), på alle deler av et kartesisk produkt U x V er den relative finhet av binære forbindelser av U i V . For V = U tillater denne relasjonen for eksempel (ved begrensning, se ovenfor) å sammenligne mellom dem:
- de Ekvivalensrelasjon på U (eller, som beløper seg til det samme: partisjoner av U );
- ordre relasjoner på U .
Gitt en familie ( E jeg ) jeg ∈ jeg av bestilte sett, den naturlige orden på produktsett Π i ∈ I E jeg er produktet for , definert ved:( x i ) i ∈ I ≤ ( y i ) i ∈ I hvis og bare hvis for en hvilken som helst indeks i , x i ≤ y i .For eksempel på settet E I for funksjoner av I i et ordnet sett E , er rekkefølgen produsert gitt ved: f ≤ g hvis for alt i ∈ I , f ( i ) ≤ g ( i ). For rekkefølgen produsert på ℝ ℝ er en funksjon mindre enn en annen hvis kurven alltid er under den andre kurven.
Vi kan generalisere den leksikografiske rekkefølgen (nevnt i begynnelsen av listen) som følger: hvis jeg er ordnet , definerer vi en rekkefølge på ∏ i ∈ I E i av:( x i ) i ∈ I <( y i ) i ∈ I hvis og bare hvis det er indekser i som x i ≠ y i og hvis, for den minste av dem, har vi x i < y i .Hvis bestillingen på E i er total, er leksikografisk rekkefølge på ∏ i ∈ I E i også total (men generelt ikke produktordren).
En forhåndsbestillingsrelasjon er ikke en ordrelasjon generelt fordi den mangler egenskapen til antisymmetri. Men ethvert kvotient av en forhåndsbestilling med tilhørende ekvivalensforhold er en ordre.
En streng ordrerelasjon på et ikke-fritt sett er ikke en ordrerelasjon fordi det ikke er refleksivt. Hvis <er en streng rekkefølge på E , forholdet " x < y eller x = y " er en bestilling av e .
En syklisk relasjon er ikke en ordrelasjon fordi den er en ternær relasjon . Men de binære forhold oppnådd ved å fikse et av de tre argumentene er strenge ordreforhold.
Et rotfestet tre er en asyklisk rettet graf assosiert med en bestemt delvis ordensrelasjon, viktig i informatikk.

Relaterte begreper

Monotone applikasjoner

Hvis $( E , \leq)$ og $( F , ≼)$ er to ordnede sett, sies et kart $f$ fra $E$ til $F$ å øke (eller noen ganger øke i bred forstand, eller isotonisk) når det bevarer rekkefølgen, avtagende (i bred sans), eller antitone når den reverserer denne, det vil si at:

f

øker når for alle

x

y

E

x \leq y \Rightarrow f ( x ) ≼ f ( y )

;

f

avtar når for alle

x

y

E

x \leq y \Rightarrow f ( x ) ≽ f ( y )

Det sies å øke strengt når den holder streng rekkefølge: for alle $x$ og $y$ av $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

og avtar strengt når den reverserer den: for alle $x$ og $y$ av $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Merk at hvis et økende kart over $( E , \leq)$ i $( F , ≼)$ er injiserende, øker det strengt, men det omvendte er falsk generelt (det er imidlertid sant hvis rekkefølgen på $E$ er total).

En monoton eller monoton applikasjon i vid forstand (resp. Strengt monoton) er en økende eller avtagende applikasjon (resp. Strengt økende eller streng avtagende).

Den gjensidige sammenheng av en økende sammenheng $f : ( E , \leq) \to ( F , ≼)$ øker ikke nødvendigvis (ta for eksempel kartleggingsidentiteten til $E$ = ℝ utstyrt med rekkefølgen av likhet i $F$ = ℝ forsynt med det vanlige rekkefølge). Det er imidlertid hvis ≤ er totalt (hvis $f -1 ( y 1 ) \geq f -1 ( y 2 ),$ da, ved vekst av $f$ , $y 1 ≽ y 2.$ Derfor ved kontrast : hvis $y 1 ≺ y 2$ og hvis ≤ er totalt så er $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

En isomorfisme mellom to ordnede sett $( E , \leq)$ og $( F , ≼)$ er en sammenheng $f$ fra $E$ til $F$ som øker og hvis samtale øker, noe som tilsvarer at $f$ er bijektiv og tilfredsstiller for alle $x$ og $y$ av $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

En innebygging av ordnede sett fra $( E , \leq)$ i $( F , ≼)$ er et kart $f$ fra $E$ til $F som$ tilfredsstiller for alle $x$ og $y$ av $E$ :

x \leq y \Leftrightarrow f ( x ) ≼ f ( y )

(en slik applikasjon er nødvendigvis injiserende ). Ordenisomorfismer er derfor overlappende embeddinger .

I kategorien ordnede sett er morfismene per definisjon de økende kartene, og isomorfismene er derfor de som er introdusert ovenfor.

Største element og maksimale element

I et ordnet sett E , eksisterer det ikke nødvendigvis et større element . Hvis E er endelig, vil den inneholde (minst) ett maksimalt element . Hvis E er et uendelig induktivt sett , garanterer Zorns lemma fortsatt eksistensen av et maksimalt element.

Strengt ordensforhold

Vi har sett at til et forhold av orden ≤ på et sett E , assosierer vi naturlig nok et forhold <på E , som da er et forhold av streng orden , dvs. antirefleksiv ( x < x n 'er sant for ethvert element x av E ) og transitive.

Imidlertid er enhver streng rekkefølge relasjon antisymmetrisk og til og med asymmetrisk (som tilsvarer: antisymmetrisk og antireflekterende), det vil si at for alle x og y :

x < y ⇒ nei ( y < x) .

Følgelig kan man gjensidig, med enhver ordensforhold streng <på E , knytte et forhold mellom ordre ≤ på E ved å stille:

x ≤ y hvis og bare hvis x < y eller x = y .

Det er enkelt å verifisere at ved å sette disse to konstruksjonene fra ende til slutt, fra en ordre eller en streng ordre, finner vi startforholdet. Å velge den ene eller den andre av aksiomatiseringene er derfor ikke viktig i seg selv.

For en streng ordre uttrykkes helheten som følger:

∀ x , y ∈ E ( x < y eller x = y eller y < x ).

og vi sier da at det er et forhold av total streng orden . Det er ingen mulig forveksling med forestillingen om total relasjon , fordi strenge ordenforhold er antirefleksive, mens totale forhold er refleksive.

For en streng totalbestilling er de tre mulighetene - x < y , x = y og y < x - eksklusive, og vi snakker noen ganger, etter Cantor , om trikotomiegenskapen .

Syklisk forhold

Den transitive refleksive lukkingen av en relasjon R er en ordensrelasjon - eller igjen: den transitive lukkingen av R er antisymmetrisk - hvis og bare hvis R er acyklisk .

Den transitive lukkingen av R er en streng rekkefølge hvis og bare hvis R er strengt asyklisk, dvs. hvis grafen er asyklisk .

Negasjon (eller komplement) av en ordrerelasjon

Negasjonen av et binært forhold definert i et sett er forholdet mellom grafen og komplementet til det i . Vi merker det . Med andre ord, to elementer er relatert av hvis og bare hvis de ikke er av . $R$ $PÅ$ $R$ $A \ ganger A$ $\ ikke \! R$ $\ ikke \! R$ $R$

Å si at en ordre er total, er å si at negasjonen er den strenge omvendte rekkefølgen. Det vil si at det er en ekvivalens for en ordre mellom: $\ leqslant$

$\ leqslant$ er totalt;
$x \ not \ leqslant y \ iff y <x$ .

På den annen side, så snart det er to forskjellige elementer som ikke kan sammenlignes med en ordre, kan negasjonen ikke være en ordre (streng eller bred), fordi den ikke er antisymmetrisk. Negasjonen av en ikke-total ordre er derfor aldri en ordre.

For eksempel, er negasjonen av inklusjons ⊄ på settet av deler av et sett av minst to elementer ikke en ordre, fordi, hvis en ≠ b , vi alltid ha { en } ≠ { b } med imidlertid { en } ⊄ { b } og { b } ⊄ { a }.

Dobbel bestilling

Den doble rekkefølgen (eller motsatt rekkefølge ) av et ordnet sett P = ( E , ≤) er det ordnede settet P op = ( E , ≤ op ), der ≤ op er motsatt rekkefølge av ≤, c 'dvs. forholdet ≥ (vi bruker noen ganger * i stedet for op ).

Den bidual ( P op ) op av P er lik P .

Forhåndsbestille

En forhåndsbestilling er en refleksiv og transitiv binær relasjon .

Enhver forhåndsbestilling ℛ på et sett $E$ induserer en ordensrelasjon på mengden $E$ kvotientert av ekvivalensforholdet ~ definert av “ $x ~ y hvis og bare hvis ( x ℛ y og y ℛ x )$ ”.

For mer detaljer og eksempler, se detaljert artikkel.

Utfyllende egenskaper

Kompatibilitet

Kompatibiliteten til en ordrerelasjon med en algebraisk struktur kan bare defineres fra sak til sak.

En rekkefølge ≤ på en halv gruppe ( G , +) sies å være kompatibel hvis vi for alle x , y og z i G slik at x ≤ y , vi har x + z ≤ y + z og z + x ≤ z + y .
Når ( G , +) er en gruppe , så sier vi at ( G , +, ≤) er en ordnet gruppe , og at et element er positivt hvis det er større enn det nøytrale elementet .
Enhver fullordnet arkimedisk gruppe er abelsk og er nedsenket i ( ℝ , +, ≤).
En ring eller et felt ( A , +, ×) sies å være ordnet hvis den har en ordre ≤ slik at ( A , +, ≤) er en ordnet gruppe og produktet av to positive elementer er positivt.
Ethvert fullordnet arkimedisk legeme er nedsenket i (ℝ, +, ×, ≤).
I et totalt ordnet felt er –1 aldri en firkant eller til og med en sum av firkanter.
Et ordnet vektorrom (de) er et reelt vektorrom ( E , +, ∙) utstyrt med en ordre ≤ slik at ( E , +, ≤) er en ordnet gruppe og at ethvert vektorprodukt av en positiv real med en positiv vektor er positiv.

Velordnet sett

Et ordnet sett sies ordnet hvis hvert delmengde som ikke er tomt, har dette settet et minste element .

Trellis

Et sett kalles et gitter hvis det er bestilt, og hvis noen par elementer har en øvre og en nedre grense .

applikasjoner

Bestill topologi

Et bestilt sett kan utstyres med flere topologier som følger av ordren : ordens topologi, ordens topologi til høyre og ordens topologi til venstre.

Koblinger til enkle komplekser

En viktig klasse med enkle komplekser kommer fra endelige ordnede sett. Vi definerer rekkefølgen D (P) av et endelig ordnet sett P som settet med kjeder av P. Komplekset av orden er trivielt et forenklet kompleks.

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

Merknader og referanser

N. Bourbaki , Elementer av matematikk : Mengdelære [ detalj utgaver ], s. III.4 .
Bourbaki , s. III.5.
(in) AG Kurosh , Forelesninger i generell algebra , Pergamon Press ,1965( les online ) , s. 11.
Bourbaki , s. III.22-23.
Nathalie Caspard, Bruno Leclerc og Bernard Monjardet, Finite bestilte sett: konsepter, resultater og bruksområder , Springer,2007( les online ) , s. 73.
Bourbaki , s. III.7 og III.14.
Gustave Choquet , Course of Analysis , 1966, s. 23 .
(in) Steven Roman, Lattices and Ordered Sets , Springer ,2008, 305 s. ( ISBN 978-0-387-78900-2 , leses online ) , s. 1. 3.
Roman 2008 , s. 284.
For eksempel J. Riguet , " binær relasjon, nedleggelser, korrespondanser av Galois ", Bull. Soc. Matte. Fr. , vol. 76,1948, s. 114-155 ( les online ).
(en) George Bergman (en) , En invitasjon til generell algebra og universelle konstruksjoner , Cham, Springer ,2015, 2 nd ed. ( 1 st ed. 1988), 572 s. ( ISBN 978-3-319-11478-1 , leses online ) , s. 113.
Bourbaki , s. III.4 og III.77.
Jean-Pierre Ramis , André Warusfel et al. , Alt-i-ett-matematikk for lisensen: Nivå L1 , Dunod ,2013, 2 nd ed. ( les online ) , s. 37.

Se også

Relaterte artikler

Antichaine
Ordnet kropp
Galois korrespondanse
Ideell (ordre teori)
Orden , matematisk journal som omhandler ordrenes teori
Velbegrunnet orden
Syklisk orden
Full delordre
Nybegynnerseksjon
Szpilrajn utvidelsessetning
Bestillingstype

Bibliografi

(no) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ detalj av utgaver ] ( online presentasjon )
(en) Efe A. Ok, Order Theory and its Applications ( les online )