Relația de ordine

O relație de ordine într-un set este o relație binară în acest set care permite compararea elementelor sale între ele într-un mod consecvent. Un set dotat cu o relație de ordine este un set ordonat . De asemenea, spunem că relația definește pe acest set o structură de ordine sau pur și simplu o ordine .

Definiții și exemple

Relația de ordine

O relație de ordine este o relație binară reflexivă , antisimetrică și tranzitivă : fie E o mulțime; o relație internă ≤ pe E este o relație de ordine dacă pentru toate elementele x , y și z ale lui E :

x ≤ x (reflexivitate)
( x ≤ y și y ≤ x ) ⇒ x = y (antisimetrie)
( x ≤ y și y ≤ z ) ⇒ x ≤ z (tranzitivitate)

Însăși forma acestor axiome ne permite să afirmăm că sunt verificate și de relația binară reciprocă ≥, definită de

y ≥ x dacă și numai dacă x ≤ y .

Orice relație de ordine este asociată deci o relație opusă de ordine pe același set; formulele x ≤ y și y ≥ x pot fi citite indiferent: „ x este mai mic decât y ” sau „ x este mai mic decât y ” sau „ y este mai mare decât x ” sau „ y este mai mare decât x ” (sau uneori „ x este cel mult egal cu y ”, sau „ y este cel puțin egal cu x ”).

De asemenea, ne asociem cu orice relație de ordine ≤, o relație cunoscută ca fiind de ordine strict notată atunci <(care nu este o relație de ordine în sensul definit anterior, deoarece reflexivitatea nu este satisfăcută), care este restricția relației de ordine la perechile de elemente distincte:

x < y dacă și numai dacă x ≤ y și x ≠ y .

Formula x < y este, de asemenea, scrisă y > x și citește: " x este strict mai mic decât y ", sau " x este strict mai mic decât y ", " y este strict mai mare decât x " sau " y este strict mai mare decât x ”.

O relație de ordine în sensul definiției de mai sus este uneori denumită ordine largă .

Unele relații de ordine sunt relații totale , adică două elemente ale lui E sunt întotdeauna comparabile : pentru toate x , y ale lui E :

x ≤ y sau y ≤ x .

Apoi spunem că ≤ este o relație de ordine totală și că mulțimea E este complet ordonată de această relație. O relație de ordine pe E se spune că este parțială dacă nu este totală, iar E este apoi parțial ordonată . Trebuie remarcat faptul că în limba engleză, ordinea parțială denotă orice ordine, care poate fi deci totală. Această terminologie este uneori folosită și în franceză.

Set ordonat

Un set ordonat este un set prevăzut cu o relație de comandă. Dacă un set ordonat este finit, acesta poate fi reprezentat grafic sub forma unei diagrame Hasse , similar cu reprezentarea obișnuită a unui grafic pe hârtie, care poate face mai ușor lucrul la el. Dacă este infinit, putem desena o parte din diagrama lui Hasse.

Exemple și contra-exemple

Relația „este mai mică (sau egală) cu„ este o relație de ordine totală asupra setului de numere întregi ( naturale sau relative ), pe setul raționalelor sau al setului de reali .
Având în vedere o mulțime ordonată ( E , ≤), ordinea lexicografică pe mulțimea de n -cupluri a elementelor E este „ordinea dicționarului”, mai simplu de definit prin ordinea strictă asociată : ( x 1 , ..., X n ) < ( y 1 ,…, y n ) dacă x i = y i pentru toți indicii i până la un anumit k < n și x k +1 < y k +1 .
Relația de incluziune „ este un subset de“ sau „este conținută în“ este o relație de ordine pe setul E de părți ale unui set X . Dacă X este finit, E este finit (mai exact dacă X conține n elemente, E conține 2 n ). Figura 1 reprezintă diagrama Hasse a lui ( E , ⊂) pentru n = 3.
Orice restricție privind o parte F a E de ordine pe E este un ordin al F . În special (conform punctului anterior): pe orice set F de părți ale unei mulțimi X , includerea este o relație de ordine - acest „exemplu” este de fapt generic: fiecare ordine este izomorfă la o ordine de această formă;
Relația de divizibilitate este o relație de ordine parțială a numerelor naturale . Figura 2 reprezintă diagrama lui Hasse a restricției sale la numere întregi de la 0 la 9.
Ordinea de incluziune (vezi mai sus), pe toate părțile componente ale unui produs cartezian U × V este finețea relativă a relațiilor binare de U în V . Pentru V = U , această relație face posibilă, de exemplu (prin restricție, vezi mai sus) să comparăm între ele:
- în relațiile de echivalență pe U (sau, care se ridică la același lucru: partițiile de U );
- relațiile de ordine pe U .
Având în vedere o familie ( E i ) i ∈ I de seturi ordonate, ordinea naturală a setului de produse ∏ i ∈ I E i este ordinea produsului , definită de:( x i ) i ∈ I ≤ ( y i ) i ∈ I dacă și numai dacă pentru orice indice i , x i ≤ y i .De exemplu, pe mulțimea E I a funcțiilor lui I într-o mulțime ordonată E , ordinea produsă este dată de: f ≤ g dacă pentru toate i ∈ I , f ( i ) ≤ g ( i ). Pentru ordinea produsă pe ℝ ℝ , o funcție este mai mică decât alta dacă curba sa este întotdeauna sub cealaltă curbă.
Putem generaliza ordinea lexicografică (menționată la începutul listei) după cum urmează: dacă I este bine ordonat , definim o ordine pe ∏ i ∈ I E i prin:( x i ) i ∈ I <( y i ) i ∈ I dacă și numai dacă există indici i pentru care x i ≠ y i și dacă, pentru cel mai mic dintre ei, avem x i < y i .Dacă comenzile pe E i sunt totale, ordinea lexicografică pe ∏ i ∈ I E i este de asemenea totală (dar nu în general comanda produsului).
O relație de precomandă nu este o relație de ordine în general, deoarece nu are proprietatea antisimetriei. Dar orice coeficient al unei precomenzi prin relația de echivalență asociată este un ordin.
O relație de ordine strictă pe un set nevat nu este o relație de ordine, deoarece nu este reflexivă. Dacă <este un ordin strict pe E , relația „ x < y sau x = y “ este un ordin E .
O relație ciclică nu este o relație de ordine, deoarece este o relație ternară . Dar relațiile binare obținute prin fixarea unuia dintre cele trei argumente ale sale sunt relații stricte de ordine.
Un copac înrădăcinat este un grafic direcționat aciclic asociat cu o anumită relație de ordine parțială, importantă în informatică.

Concepte conexe

Aplicații monotone

Dacă $( E , \leq)$ și $( F , ≼)$ sunt două mulțimi ordonate, se spune că o hartă $f de$ la $E$ la $F$ crește (sau uneori crește în sens larg sau izotonică) atunci când păstrează ordinea, scăzând (în sens larg), sau antiton atunci când îl inversează pe acesta, adică:

f

crește când pentru toate

x

și

y

ale lui

E

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

;

f

scade când pentru toate

x

și

y

ale lui

E

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

Se spune că crește strict atunci când păstrează ordinea strictă: pentru toate $x$ și $y$ ale lui $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

și strict descrescător când îl inversează: pentru toate $x$ și $y$ ale lui $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Rețineți că dacă o hartă în creștere a lui $( E , \leq)$ în $( F , ≼)$ este injectivă, atunci este strict crescătoare, dar că inversul este fals în general (este totuși adevărat dacă ordinea pe $E$ este totală).

Un monotonă sau monotonă aplicare în sens larg (resp. Strict monotonă) este o creștere sau descreștere aplicare (resp. Strict crescatoare sau strict descrescătoare).

Bijectie reciprocă a unei creșterii bijectie $f : ( E , \leq) \to ( F , ≼)$ nu este în mod necesar în creștere (iau de exemplu identitatea de cartografiere , a $E$ = ℝ înzestrat cu ordinul egalității în $F$ = ℝ prevăzut cu de obicei Ordin). Cu toate acestea, este dacă ≤ este total (dacă $f -1 ( y 1 ) \geq f -1 ( y 2 )$ atunci, prin creșterea lui $f$ , $y 1 ≽ y 2.$ Prin urmare, prin contrapus : dacă $y 1 ≺ y 2$ și dacă ≤ este total, atunci $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

Un izomorfism între două mulțimi ordonate $( E , \leq)$ și $( F , ≼)$ este o bijecție $f$ din $E$ în $F$ care este în creștere și al cărei invers este în creștere, ceea ce înseamnă că $f$ este bijectiv și satisface pentru toate $x$ și $y$ de $E$ :

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

O încorporare a seturilor ordonate de la $( E , \leq)$ în $( F , ≼)$ este o hartă $f de$ la $E$ la $F$ satisfăcătoare pentru toate $x$ și $y$ din $E$ :

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

(o astfel de aplicație este neapărat injectivă ). Prin urmare, izomorfismele de ordine sunt încorporări surjective .

În categoria mulțimilor ordonate, morfismele sunt prin definiție hărțile în creștere, iar izomorfismele sunt, prin urmare, cele introduse mai sus.

Cel mai mare element și elementul maxim

Într-o mulțime ordonată E , nu există neapărat un element mai mare . Dacă E este finit, va conține (cel puțin) un element maxim . Dacă E este un set inductiv infinit, lema lui Zorn încă garantează existența unui element maxim.

Relație de ordine strictă

Am văzut că la o relație de ordine ≤ pe un set E , asociem în mod natural o relație <pe E , care este apoi o relație de ordine strictă , adică antireflexivă ( x < x n 'este adevărat pentru orice element x din E ) și tranzitiv.

Cu toate acestea, orice relație de ordine strictă este antisimetrică și chiar asimetrică (ceea ce este echivalent cu: antisimetric și antireflexiv), adică pentru toate x și y :

x < y ⇒ nu ( y < x) .

În consecință, reciproc, cu orice relație de ordine strictă <pe E , se poate asocia o relație de ordine ≤ pe E punând:

x ≤ y dacă și numai dacă x < y sau x = y .

Este ușor să verificăm că punând aceste două construcții cap la cap, dintr-o ordine sau o ordine strictă, găsim relația de pornire. Alegerea uneia sau alteia dintre axiomatizări nu este deci importantă în sine.

Pentru o ordine strictă, totalitatea este exprimată după cum urmează:

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

și spunem atunci că este o relație de ordine strictă totală . Nu există confuzie posibilă cu noțiunea de relație totală , deoarece relațiile stricte de ordine sunt antireflexive, în timp ce relațiile totale sunt reflexive.

Pentru o ordine totală strictă, cele trei posibilități - x < y , x = y și y < x - sunt exclusive și uneori vorbim, urmând Cantor , despre proprietatea trichotomiei .

Relația aciclică

Tranzitiv închiderea reflexivă a unei relații R este o relație de ordine - sau o dată: închiderea tranzitivă a R este antisimetrică - dacă și numai în cazul în care R este aciclic .

Închiderea tranzitivă a lui R este o ordine strictă dacă și numai dacă R este strict aciclic, adică dacă graficul său este aciclic .

Negarea (sau complementul) unei relații de ordine

Negarea unei relații binare definite pe un set este relația graficului complementara celei din in . O observăm . Cu alte cuvinte, două elemente sunt legate de dacă și numai dacă nu sunt . $R$ $LA$ $R$ $A \ ori A$ $\ nu \! R$ $\ nu \! R$ $R$

A spune că o ordine este totală înseamnă a spune că negarea acesteia este ordinea inversă strictă. Adică există o echivalență pentru o ordine între: $\ leqslant$

$\ leqslant$ este total;
$x \ not \ leqslant y \ if y <x$ .

Pe de altă parte, de îndată ce există două elemente distincte care nu sunt comparabile printr-o ordine, negarea acesteia nu poate fi o ordine (strictă sau largă), deoarece nu este antisimetrică. Negarea unei ordine non-totale nu este deci niciodată o ordine.

De exemplu, negarea includerii ⊄ pe setul părților unui set de cel puțin două elemente nu este o ordine, deoarece, dacă a ≠ b , avem întotdeauna { a } ≠ { b } cu totuși { a } ⊄ { b } și { b } ⊄ { a }.

Comandă dublă

Ordinea duală (sau ordinea opusă ) a unei mulțimi ordonate P = ( E , ≤) este mulțimea ordonată P op = ( E , ≤ op ), unde ≤ op este relația de ordine opusă a ≤, c 'adică relația ≥ (uneori folosim * în loc de op ).

Bidual ( P op ) op de P este egal cu P .

Pre-comanda

O precomandă este o relație binară reflexivă și tranzitivă .

Orice precomandă ℛ pe o mulțime $E$ induce o relație de ordine pe mulțimea $E$ cotată de relația de echivalență ~ definită de „ $x ~ y dacă și numai dacă ( x ℛ y și y ℛ x )$ ”.

Pentru mai multe detalii și exemple, consultați articolul detaliat.

Proprietăți complementare

Compatibilitate

Compatibilitatea unei relații de ordine cu o structură algebrică poate fi definită doar de la caz la caz.

O ordine ≤ pe o jumătate de grup ( G , +) se spune că este compatibilă dacă, pentru toate x , y și z în G astfel încât x ≤ y , avem x + z ≤ y + z și z + x ≤ z + y .
Când ( G , +) este un grup , atunci spunem că ( G , +, ≤) este un grup ordonat și că un element este pozitiv dacă este mai mare decât elementul neutru .
Orice grup arhimedian complet ordonat este abelian și este scufundat în ( ℝ , +, ≤).
Un inel sau un câmp ( A , +, ×) se spune că este ordonat dacă are o ordine ≤ astfel încât ( A , +, ≤) este un grup ordonat și produsul a două elemente pozitive este pozitiv.
Orice corp arhimedian complet ordonat este scufundat în (ℝ, +, ×, ≤).
Într-un câmp complet ordonat, –1 nu este niciodată un pătrat sau chiar o sumă de pătrate.
Un spațiu vector ordonat (de) este un spațiu vectorial real ( E , +, ∙) dotat cu un ordin ≤ astfel încât ( E , +, ≤) este un grup ordonat și că orice produs vectorial al unui real pozitiv printr-un vector pozitiv este pozitiv.

Set bine ordonat

Un set ordonat se spune bine ordonat dacă fiecare subset care nu este gol, acest set are cel mai mic element .

Spalier

Un set se numește rețea dacă este ordonat și dacă orice pereche de elemente are o margine superioară și una inferioară .

Aplicații

Topologia comenzii

Un set ordonat poate fi prevăzut cu mai multe topologii rezultate din ordine : topologia ordinii, topologia ordinii din dreapta și topologia ordinii în stânga.

Legături cu complexe simpliciale

O clasă importantă de complexe simpliciale provine din mulțimi ordonate finite. Definim complexul de ordine D (P) al unei mulțimi ordonate finite P ca fiind mulțimea lanțurilor lui P. Complexul de ordine este în mod trivial un complex simplicial.

Studiul setului ordonat în sine oferă informații despre complexul său de ordine și, prin urmare, este interesant să studiezi un complex simplicial ca complexul de ordine al unui set ordonat.

Note și referințe

N. Bourbaki , Elemente de matematică : teoria seturilor [ detaliile edițiilor ], p. III.4 .
Bourbaki , p. III.5.
(în) AG Kurosh , Lectures in General Algebra , Pergamon Press ,1965( citiți online ) , p. 11.
Bourbaki , p. III.22-23.
Nathalie Caspard, Bruno Leclerc și Bernard Monjardet, Seturi ordonate finite: concepte, rezultate și utilizări , Springer,2007( citiți online ) , p. 73.
Bourbaki , p. III.7 și III.14.
Gustave Choquet , Curs de analiză , 1966, p. 23 .
(în) Steven Roman, Lattices and Ordered Sets , Springer ,2008, 305 p. ( ISBN 978-0-387-78900-2 , citit online ) , p. 13.
Roman 2008 , p. 284.
De exemplu J. Riguet , „ Relații binare, închideri, corespondențe ale lui Galois ”, Bull. Soc. Matematica. Pr. , Vol. 76,1948, p. 114-155 ( citește online ).
(ro) George Bergman (ro) , O invitație la algebră generală și construcții universale , Cham, Springer ,2015, A 2 -a ed. ( 1 st ed. 1988), 572 p. ( ISBN 978-3-319-11478-1 , citit online ) , p. 113.
Bourbaki , p. III.4 și III.77.
Jean-Pierre Ramis , André Warusfel și colab. , Matematică all-in-one pentru licență: Nivelul L1 , Dunod ,2013, A 2 -a ed. ( citiți online ) , p. 37.

Vezi și tu

Articole similare

Antichaine
Corp ordonat
Corespondența Galois
Ideal (teoria comenzilor)
Ordin , jurnal matematic care se ocupă de teoria ordinelor
Ordin bine întemeiat
Ordinea ciclică
Comandă parțială completă
Secțiunea pentru începători
Teorema extensiei Szpilrajn
Tipul comenzii

Bibliografie

(ro) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ detaliu ediții ] ( prezentare online )
(ro) Efe A. Ok, Teoria comenzilor și aplicațiile sale ( citiți online )