Bestil forhold

En ordrerelation i et sæt er en binær relation i dette sæt, som gør det muligt at sammenligne dets elementer med hinanden på en konsistent måde. Et sæt udstyret med en ordrerelation er et ordnet sæt . Vi siger også, at forholdet definerer på dette sæt en ordre struktur eller ganske enkelt en ordre .

Definitioner og eksempler

Bestil forhold

En ordrerelation er en refleksiv , antisymmetrisk og transitiv binær relation  : lad E være et sæt; en intern relation ≤ på E er en rækkefølge, hvis for alle x- , y- og z- elementerne i E  :

Selve formen for disse aksiomer giver os mulighed for at bekræfte, at de også er verificeret af det gensidige binære forhold ≥, defineret af

y ≥ x hvis og kun hvis x ≤ y .

Til en hvilken som helst rækkefølge er derfor en modsat rækkefølge af orden på det samme sæt; formlerne x ≤ y og y ≥ x kan læses ligegyldigt: "  x er mindre end y  ", eller "  x er mindre end y  ", eller "  y er større end x  ", eller "  y er større end x  " (eller undertiden er "  x højst lig med y  ", eller "  y er mindst lig med x ").

Vi forbinder også med en hvilken som helst relation af orden ≤, en relation kendt som af streng rækkefølge, der er noteret derefter <(hvilket ikke er en ordenrelation i den forstand, der er defineret tidligere, da refleksiviteten ikke er opfyldt), hvilket er begrænsningen af ​​forholdet mellem orden og par af forskellige elementer:

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

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

En ordrelation i betydningen af ​​ovenstående definition kaldes undertiden bred rækkefølge .

Nogle ordenrelationer er samlede relationer , dvs. to elementer i E er altid sammenlignelige  : for alle x , y for E  :

x ≤ y eller y ≤ x .

Vi siger så, at ≤ er en relation af den samlede ordre , og at sættet E er totalt ordnet af denne relation. En ordrerelation på E siges at være delvis, hvis den ikke er total, og E ordnes derefter delvist . Det skal bemærkes, at på engelsk betegner delvis rækkefølge enhver ordre, som derfor kan være total. Denne terminologi bruges undertiden også på fransk.

Ordnet sæt

Et bestilt sæt er et sæt forsynet med en ordrerelation. Hvis et ordnet sæt er endeligt, kan det repræsenteres grafisk i form af et Hasse-diagram svarende til den sædvanlige repræsentation af en graf på papir, hvilket kan gøre det lettere at arbejde på det. Hvis den er uendelig, kan vi tegne en del af dens Hasse-diagram.

Eksempler og modeksempler

Relaterede begreber

Monotone applikationer

Hvis ( E , ≤) og ( F , ≼) er to ordnede sæt, siges et kort f fra E til F at stige (eller undertiden stige i bred forstand eller isotonisk), når det bevarer rækkefølgen og falder (i bred sans) eller antitone, når den vender denne, det vil sige at:

f stiger, når for alle x og y af E , x ≤ y ⇒ f ( x ) ≼ f ( y )  ; f er faldende, når for alle x og y af E , x ≤ y ⇒ f ( x ) ≽ f ( y ) .

Det siges at stige strengt, når det holder den strenge rækkefølge: for alle x og y af E , x < y ⇒ f ( x ) ≺ f ( y ) ,

og strengt faldende, når det vender det: for alle x og y af E , x < y ⇒ f ( x ) ≻ f ( y ) .

Bemærk, at hvis et stigende kort over ( E , ≤) i ( F , ≼) er injektionsdygtigt , øges det strengt, men at det omvendte generelt er falsk (det er dog sandt, hvis rækkefølgen på E er total).

En monoton eller monoton anvendelse i bred forstand (resp. Strengt monoton) er en stigende eller faldende anvendelse (resp. Strengt stigende eller strengt faldende).

Den gensidige sammenhæng af en stigende sammenhæng f  : ( E , ≤) → ( F , ≼) er ikke nødvendigvis stigende (tag f.eks. Kortlægningsidentiteten af E = ℝ udstyret med rækkefølgen af lighed i F = ℝ forsynet med den sædvanlige bestille). Det er dog, hvis ≤ er total (hvis f −1 ( y 1 ) ≥ f −1 ( y 2 ), så ved vækst af f , y 1 ≽ y 2. Så ved modsætning  : hvis y 1 ≺ y 2 og hvis ≤ er total, så er f −1 ( y 1 ) < f −1 ( y 2 ) ).

En isomorfisme mellem to ordnede sæt ( E , ≤) og ( F , ≼) er en sammenhæng f fra E til F, som er stigende, og hvis samtale stiger, hvilket svarer til at sige, at f er bijektiv og tilfredsstiller for alle x og y af E  :

x ≤ y ⇔ f ( x ) ≼ f ( y ) .

En indlejring af ordnede sæt fra ( E , ≤) i ( F , ≼) er et kort f fra E til F, der tilfredsstiller alle x og y af E  :

x ≤ y ⇔ f ( x ) ≼ f ( y )

(en sådan applikation er nødvendigvis injektionsdygtig ). Ordenisomorfismer er derfor indbydelser med overvejelser .

I kategorien af ordnede sæt er morfismerne pr. Definition de stigende kort, og isomorfismerne er derfor de, der er introduceret ovenfor.

Største element og maksimale element

I et ordnet sæt E findes der ikke nødvendigvis et større element . Hvis E er endelig, vil den indeholde (mindst) et maksimalt element . Hvis E er et uendeligt induktivt sæt , garanterer Zorns lemma stadig eksistensen af ​​et maksimalt element.

Strengt ordreforhold

Vi har set, at til et forhold mellem orden ≤ på et sæt E forbinder vi naturligvis et forhold <på E , hvilket derefter er et forhold af streng orden , dvs. antirefleksiv ( x < x n 'er sandt for ethvert element x af E ) og forbigående.

Enhver streng rækkefølge er imidlertid antisymmetrisk og endda asymmetrisk (hvilket svarer til: antisymmetrisk og antireflekterende), det vil sige at for alle x og y  :

x < y ⇒ nej ( y < x) .

Følgelig kan man gensidigt, med ethvert ordenforhold strengt <på E , knytte et forhold mellem orden ≤ på E ved at stille:

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

Det er let at kontrollere, at ved at sætte disse to konstruktioner fra ende til slut fra en ordre eller en streng ordre, finder vi startforholdet. At vælge den ene eller den anden af ​​aksiomatiseringerne er derfor ikke i sig selv vigtig.

For en streng ordre udtrykkes helheden som følger:

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

og vi siger så, at det er et forhold af total streng orden . Der er ingen mulig forveksling med forestillingen om total relation , fordi strenge ordenforhold er antirefleksive, mens totale forhold er refleksive.

For en streng samlede ordre, de tre muligheder - x < y , x = y og y < x - er eksklusive, og nogle gange taler vi, efter Cantor , den tredeling ejendom .

Acyklisk forhold

Den transitive refleksive lukning af en relation R er en rækkefølge - eller igen: den transitive lukning af R er antisymmetrisk - hvis og kun hvis R er acyklisk .

Den transitive lukning af R er en streng rækkefølge, hvis og kun hvis R er strengt acyklisk, dvs. hvis dens graf er acyklisk .

Negation (eller komplement) af en ordrerelation

Negationen af ​​et binært forhold defineret på et sæt er forholdet mellem grafen og det komplementære af det i . Vi bemærker det . Med andre ord er to elementer forbundet med, hvis og kun hvis de ikke er .

At sige, at en ordre er total, er at sige, at dens negation er den strenge omvendte rækkefølge. Det vil sige, at der er en ækvivalens for en ordre mellem:

På den anden side, så snart der er to forskellige elementer, der ikke kan sammenlignes med en ordre, kan negationen ikke være en ordre (streng eller bred), fordi den ikke er antisymmetrisk. Negationen af ​​en ikke-total ordre er derfor aldrig en ordre.

F.eks negation af optagelsen ⊄ på sættet af de dele af et sæt af mindst to elementer ikke er en ordre, fordi, hvis en ≠ b , vi altid har { a } ≠ { b } med dog { a } ⊄ { b } og { b } ⊄ { a }.

Dobbelt rækkefølge

Den dobbelte rækkefølge (eller modsat rækkefølge ) af et ordnet sæt P = ( E , ≤) er det ordnede sæt P op = ( E , ≤ op ), hvor ≤ op er den modsatte rækkefølge af ≤, c 'dvs. forholdet ≥ (vi bruger nogle gange * i stedet for op ).

Den bidual ( P OP ) op af P er lig med P .

Forudbestille

En forudbestilling er et refleksivt og transitivt binært forhold .

Enhver forbestilling ℛ på et sæt E inducerer en ordrerelation på sættet E kvotificeret af ækvivalensforholdet ~ defineret af “  x ~ y hvis og kun hvis ( x ℛ y og y ℛ x )  ”.

For flere detaljer og eksempler, se den detaljerede artikel.

Supplerende egenskaber

Kompatibilitet

Kompatibiliteten af ​​en ordrerelation med en algebraisk struktur kan kun defineres fra sag til sag.

Velordnet sæt

Et ordnet sæt siges velordnet, hvis hver delmængde, der ikke er tom, har dette sæt et mindste element .

Trellis

Et sæt kaldes et gitter, hvis det er bestilt, og hvis et par element har en øvre og en nedre grænse .

Ansøgninger

Bestil topologi

Et bestilt sæt kan forsynes med flere topologier, der følger af ordren  : ordens topologi, ordens topologi til højre og ordens topologi til venstre.

Links til enkle komplekser

En vigtig klasse af enkle komplekser kommer fra begrænsede ordnede sæt. Vi definerer komplekset af rækkefølge D (P) for et endeligt ordnet sæt P som værende sæt af kæder af P. Komplekset af orden er trivielt et simpelt kompleks.

Studiet af det bestilte sæt i sig selv giver information om dets ordrekompleks, og det er derfor interessant at studere et simpelt kompleks som ordrekomplekset for et ordnet sæt.

Noter og referencer

  1. N. Bourbaki , Elementer i matematik  : Sætteori [ detaljer af udgaver ], s.  III.4 .
  2. Bourbaki , s.  III.5.
  3. (i) AG Kurosh , Forelæsninger i General Algebra , Pergamon Press ,1965( læs online ) , s.  11.
  4. Bourbaki , s.  III.22-23.
  5. Nathalie Caspard, Bruno Leclerc og Bernard Monjardet, Finite bestilte sæt: koncepter, resultater og anvendelser , Springer,2007( læs online ) , s.  73.
  6. Bourbaki , s.  III.7 og III.14.
  7. Gustave Choquet , Analyse , 1966, s.  23 .
  8. (in) Steven Roman, Lattices and Ordered Sets , Springer ,2008, 305  s. ( ISBN  978-0-387-78900-2 , læs online ) , s.  13.
  9. Romersk 2008 , s.  284.
  10. F.eks. J. Riguet , "  Binære relationer, lukninger, korrespondancer fra Galois  ", Bull. Soc. Matematik. Fr. , vol.  76,1948, s.  114-155 ( læs online ).
  11. (en) George Bergman  (en) , En invitation til generel algebra og universelle konstruktioner , Cham, Springer ,2015, 2 nd  ed. ( 1 st  ed. 1988), 572  s. ( ISBN  978-3-319-11478-1 , læs online ) , s.  113.
  12. Bourbaki , s.  III.4 og III.77.
  13. Jean-Pierre Ramis , André Warusfel et al. , All-in-one matematik til licensen: Niveau L1 , Dunod ,2013, 2 nd  ed. ( læs online ) , s.  37.

Se også

Relaterede artikler

Bibliografi

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">