Total ordre
I matematikk kaller vi total ordenrelasjon på et sett E et hvilket som helst forhold av orden ≤ som to elementer av E alltid er sammenlignbare, dvs.
.
Vi sier da at E er totalt ordnet etter ≤.
Definisjon
En binær relasjon ≤ på et sett E er en total rekkefølge hvis (for alle elementene x , y og z av E ):
- hvis x ≤ y og y ≤ z , så x ≤ z ( transitivitet );
- hvis x ≤ y og y ≤ x , så x = y ( antisymmetri );
- x ≤ x ( refleksivitet );
- x ≤ y eller y ≤ x ( totalitet ).
De tre første egenskapene er de som lager ≤ en ordrerelasjon. Den fjerde gjør denne bestillingen til en total ordre.
Eksempler
- Bokstavsettet i et alfabet er ordnet i alfabetisk rekkefølge .
- Ethvert euklidisk felt , som feltet ℝ med reelle tall , er utstyrt med en naturlig totalrekkefølge: x ≤ y hvis og bare hvis y - x er en firkant .
- La f : X → Y være en injeksjon , ≤ en rekkefølge på Y , og ≼ den induserte rekkefølgen på X ved å sette: x 1 ≼ x 2 hvis og bare hvis f ( x 1 ) ≤ f ( x 2 ). Hvis ≤ er totalt, så ≼ også. Spesielt: å begrense en del X av Y av en total orden på Y er en total orden på X . For eksempel er hvilken som helst del av totally fullstendig ordnet etter den vanlige ordrelasjonen.
- Hvis en rekkefølge ≤ på E er total, er motsatt rekkefølge ≥ på E total (det omvendte resultatet).
- Den leksikografiske ordren på det kartesiske produktet av et velordnet sett med totalt bestilte sett er i seg selv en total ordre; for eksempel er ethvert sett ord ordnet fullstendig alfabetisk, og god ordre er total orden.
- En kjede av et delvis ordnet sett ( E , ≤) er en del av E som rekkefølgen ≤ er total over. Denne forestillingen spiller en viktig rolle i mengdeteorien , etter Zorns lemma .
- Vi kan definere et totalt ordnet sett som et gitter der { a ∨ b , a ∧ b } = { a, b } for alle a , b ; vi kan da sette a ≤ b hvis og bare hvis a = a ∧ b ; vi beviser at en total ordre også er et distribuerende gitter.
- I følge Szpilrajns utvidelsesteorem kan enhver delrekkefølge ≤ på et sett E utvides til en total orden på E , kalt en lineær utvidelse på ≤.
Moteksempler
- På settet med naturlige heltall er ikke rekkefølge relasjonen “er en divisor av” ikke en total orden, fordi vi kan finne par positive heltall hvor ingen av dem er en skillelinje fra den andre.
- På samme måte, på settet med deler av et sett som inneholder minst to elementer a og b (distinkt), er inkluderingen bare en delvis rekkefølge: vi har verken { a } ⊂ { b } eller { b } ⊂ { a } .
Den ferdige saken
- I et fullstendig bestilt endelig sett har enhver ikke-fri del et mindre element . Med andre ord: på et endelig sett er en total ordre en god ordre .
- Enhver endelig helt beordret sett er isomorf med den rekkefølgen til en innledende segment av N .
I kategoriteori
Helt bestilt sett danne en underkategori av kategori av ordre , hvis morphisms er økende applikasjoner .
Enhver økende tilknytning fra en total ordre til en hvilken som helst ordre er en ordens isomorfisme .
Total streng ordre
Den kanoniske sammenhengen mellom de strenge ordrene og ordrene på samme sett E forbinder en relasjon av streng orden <(antirefleksiv og transitiv derfor antisymmetrisk) til en relasjon av orden ≤ (refleksiv, transitiv og antisymmetrisk), ved:
x < y ⇔ ( x ≤ y og x ≠ y )eller:
x ≤ y ⇔ ( x < y eller x = y ).En ordre ≤ er total hvis og bare hvis den tilknyttede strenge ordren <tilfredsstiller:
∀ x , y ∈ E ( x < y eller x = y eller y < x ).Vi kaller total streng ordre enhver streng ordre som bekrefter denne egenskapen, kalt “trikotomi”.