Relazione d'ordine

Una relazione d'ordine in un insieme è una relazione binaria in questo insieme che consente ai suoi elementi di essere confrontati tra loro in modo coerente. Un insieme dotato di una relazione d'ordine è un insieme ordinato . Diciamo anche che la relazione definisce su questo insieme una struttura d' ordine o semplicemente un ordine .

Definizioni ed esempi

Relazione d'ordine

Una relazione d'ordine è una relazione binaria riflessiva , antisimmetrica e transitiva : sia E un insieme; una relazione interna ≤ su E è una relazione ordine se per ogni x , y e z elementi di E :

x ≤ x (riflessività)
( x ≤ y e y ≤ x ) ⇒ x = y (antisimmetria)
( x ≤ y e y ≤ z ) ⇒ x ≤ z (transitività)

La forma stessa di questi assiomi permette di affermare che sono verificati anche dalla reciproca relazione binaria ≥, definita da

y ≥ x se e solo se x ≤ y .

Ad ogni relazione d'ordine è dunque associata una relazione d'ordine opposta sullo stesso insieme; le formule x ≤ y e y ≥ x possono essere lette indifferentemente: " x è minore di y ", oppure " x è minore di y ", oppure " y è maggiore di x ", oppure " y è maggiore di x " ( oppure a volte " x è al massimo uguale a y ", o " y è almeno uguale a x ").

Associamo anche a qualsiasi relazione di ordine ≤, una relazione nota come di ordine stretto nota poi <(che non è una relazione d'ordine nel senso definito in precedenza poiché la riflessività non è soddisfatta), che è la restrizione della relazione di ordine a le coppie di elementi distinti:

x < y se e solo se x ≤ y e x ≠ y .

La formula x < y si scrive anche y > x , e si legge: " x è strettamente minore di y ", oppure " x è strettamente minore di y ", " y è strettamente maggiore di x ", o " y è strettamente maggiore di x ”.

Una relazione d'ordine ai sensi della definizione di cui sopra è talvolta indicata come ordine ampio .

Alcune relazioni di ordine sono relazioni totali , cioè due elementi di E sono sempre confrontabili : per tutti x , y di E :

x ≤ y o y ≤ x .

Diciamo allora che è una relazione di ordine totale , e che l'insieme E è totalmente ordinato da questa relazione. Una relazione d'ordine su E si dice parziale se non è totale, ed E è quindi parzialmente ordinata . Va notato che in inglese, ordine parziale denota qualsiasi ordine, che può quindi essere totale. Questa terminologia è talvolta utilizzata anche in francese.

Insieme ordinato

Un insieme ordinato è un insieme dotato di una relazione d'ordine. Se un insieme ordinato è finito, può essere rappresentato graficamente sotto forma di diagramma di Hasse , simile alla consueta rappresentazione di un grafico su carta, che può facilitare il lavoro su di esso. Se è infinito, possiamo disegnare parte del suo diagramma di Hasse.

Esempi e controesempi

La relazione "è minore (o uguale) a" è una relazione di ordine totale sull'insieme degli interi ( naturali o relativi ), sull'insieme dei razionali o sull'insieme dei reali .
Dato un insieme ordinato ( E , ≤), l' ordine lessicografico sull'insieme di n -uples di elementi di E è l'"ordine del dizionario", più semplice da definire con l'ordine stretto associato : ( x 1 ,…, X n ) < ( y 1 ,…, y n ) se x i = y i per tutti gli indici i fino a un certo k < n e x k +1 < y k +1 .
La relazione di inclusione, "è un sottoinsieme di" o "è contenuto in" è una relazione d'ordine sull'insieme E delle parti di un insieme X . Se X è finito, E è finito (più precisamente se X contiene n elementi, E contiene 2 n ). La figura 1 rappresenta il diagramma di Hasse di ( E , ) per n = 3.
Qualsiasi restrizione su una parte F di E di ordine su E è un ordine di F . In particolare (secondo il punto precedente): su qualsiasi insieme F di parti di un insieme X , l'inclusione è una relazione d'ordine - questo "esempio" è infatti generico: ogni ordine è isomorfo ad un ordine di questa forma;
La relazione di divisibilità è una relazione di ordine parziale sui numeri naturali . La figura 2 rappresenta il diagramma di Hasse della sua restrizione a numeri interi da 0 a 9.
L'ordine di inclusione (vedi sopra), su tutte le parti di un prodotto cartesiano U × V è la finezza relativa delle relazioni binarie di U in V . Per V = U , questa relazione consente ad esempio (per restrizione, vedi sopra) di confrontare tra loro:
- le relazioni di equivalenza su U (o, che equivale alla stessa cosa: le partizioni di U );
- le relazioni d'ordine su U .
Data una famiglia ( E i ) i ∈ I di insiemi ordinati, l'ordine naturale sull'insieme di prodotti ∏ i ∈ I E i è l' ordine di prodotto , definito da:( x i ) i ∈ I ≤ ( y i ) i ∈ I se e solo se per qualsiasi indice i , x i ≤ y i .Ad esempio sull'insieme E I di funzioni di I in un insieme ordinato E , l'ordine prodotto è dato da: f ≤ g if for all i ∈ I , f ( i ) ≤ g ( i ). Per l'ordine prodotto su ℝ ℝ , una funzione è più piccola di un'altra se la sua curva è sempre al di sotto dell'altra curva.
Possiamo generalizzare l'ordine lessicografico (menzionato all'inizio dell'elenco) come segue: se I è ben ordinato , definiamo un ordine su ∏ i ∈ I E i per:( x i ) i ∈ I <( y i ) i ∈ I se e solo se esistono indici i per cui x i ≠ y i e se, per il più piccolo di essi, abbiamo x i < y i .Se gli ordini su E i sono totali, anche l'ordine lessicografico su ∏ i ∈ I E i è totale (ma non in generale l'ordine del prodotto).
Una relazione di preordine non è una relazione d'ordine in generale perché manca della proprietà dell'antisimmetria. Ma ogni quoziente di un preordine per la relazione di equivalenza associata è un ordine.
Una relazione d'ordine rigorosa su un insieme non vuoto non è una relazione d'ordine perché non è riflessiva. Se <è un ordine rigoroso su E , la relazione " x < y o x = y " è un ordine di E .
Una relazione di ordine ciclico non è una relazione di ordine perché è una relazione ternaria . Ma le relazioni binarie ottenute fissando uno dei suoi tre argomenti sono relazioni di ordine stretto.
Un albero radicato è un grafo diretto aciclico associato a una particolare relazione di ordine parziale, importante nell'informatica.

Concetti correlati

Applicazioni monotone

Se $( E , \leq)$ e $( F , ≼)$ sono due insiemi ordinati, una mappa $f$ da $E$ a $F$ si dice crescente (o talvolta crescente in senso lato, o isotonica) quando conserva l'ordine, decrescente (in il senso lato ), o antitono quando inverte questo, vale a dire che:

f

è crescente quando per ogni

x

y

E

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

;

f

diminuisce quando per tutti

x

y

E

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

Si dice che è strettamente crescente quando mantiene l'ordine rigoroso: per ogni $x$ e $y$ di $E$ , $x < y \Rightarrow f ( x ) ≺ f ( y )$ ,

e strettamente decrescente quando si inverte: per tutti $x$ ed $y$ di $E$ , $x < y \Rightarrow f ( x ) ≻ f ( y )$ .

Si noti che se una mappa crescente di $( E , )$ in $( F , ≼)$ è iniettiva allora è strettamente crescente, ma che il contrario è falso in generale (è comunque vero se l'ordine su $E$ è totale).

Un'applicazione monotona o monotona in senso lato (rispettivamente strettamente monotona) è un'applicazione crescente o decrescente (rispettivamente crescente o strettamente decrescente).

La biiezione reciproca di una biiezione crescente $f : ( E , \leq) \to ( F , ≼)$ non è necessariamente crescente (si pensi ad esempio all'identità di mappatura , di $E$ = ℝ dotata dell'ordine di uguaglianza in $F$ = ℝ dotata dell'usuale ordine). È, tuttavia, se ≤ è totale (se $f -1 ( y 1 ) \geq f -1 ( y 2 )$ allora, per crescita di $f$ , $y 1 ≽ y 2.$ Quindi per contrapposizione : se $y 1 ≺ y 2$ e se ≤ è totale allora $f -1 ( y 1 ) < f -1 ( y 2 )$ ).

Un isomorfismo tra due insiemi ordinati $( E , \leq)$ e $( F , ≼)$ è una biiezione $f$ da $E$ in $F$ che è crescente e il cui inverso è crescente, il che equivale a dire che $f$ è biunivoca e soddisfa per tutti $x$ e $y$ di $E$ :

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

Un incorporamento di insiemi ordinati di $( E , \leq)$ in $( F , ≼)$ è una mappa $f$ da $E$ a $F$ soddisfacente per tutti $x$ ed $y$ di $E$ :

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

(tale domanda è necessariamente iniettiva ). Gli isomorfismi d'ordine sono quindi immersioni suriettive .

Nella categoria degli insiemi ordinati, i morfismi sono per definizione le mappe crescenti, e gli isomorfismi sono, quindi, quelli introdotti sopra.

Elemento più grande e elemento massimo

In un insieme ordinato E , non esiste necessariamente un elemento più grande . Se E è finito, conterrà (almeno) un elemento massimale . Se E è un insieme induttivo infinito, il lemma di Zorn garantisce ancora l'esistenza di un elemento massimale.

Stretto rapporto d'ordine

Abbiamo visto che ad una relazione di ordine su un insieme E , associamo naturalmente una relazione <su E , che è allora una relazione di ordine stretto , cioè antiriflessiva ( x < x n ' è vera per ogni elemento x di E ) e transitivo.

Tuttavia, qualsiasi relazione di ordine stretto è antisimmetrica e persino asimmetrica (che equivale a: antisimmetrica e antiriflesso), vale a dire che per tutti x e y :

x < y ⇒ no ( y < x) .

Di conseguenza, reciprocamente, ad ogni relazione di ordine rigoroso <su E , si può associare una relazione di ordine ≤ su E ponendo:

x ≤ y se e solo se x < y o x = y .

È facile verificare che ponendo queste due costruzioni una dopo l'altra, da un ordine o da un ordine rigoroso, troviamo la relazione di partenza. La scelta dell'una o dell'altra assiomatizzazione è quindi di per sé irrilevante.

Per un ordine rigoroso, la totalità è espressa come segue:

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

e diciamo allora che è una relazione di ordine rigoroso totale . Non c'è confusione possibile con la nozione di relazione totale , perché le relazioni di ordine stretto sono antiriflessive, mentre le relazioni totali sono riflessive.

Per un rigoroso ordine totale, le tre possibilità - x < y , x = y e y < x - sono esclusive, e si parla talvolta, seguendo Cantor , della proprietà della tricotomia .

relazione aciclica

La chiusura riflessiva transitiva di una relazione R è una relazione d'ordine - o ancora: la chiusura transitiva di R è antisimmetrica - se e solo se R è aciclico .

La chiusura transitiva di R è un ordine rigoroso se e solo se R è strettamente aciclico, cioè se il suo grafico è aciclico .

Negazione (o complemento) di una relazione d'ordine

La negazione di una relazione binaria definita su un insieme è la relazione di grafo complementare di quella di in . Lo notiamo . In altre parole, due elementi sono collegati da se e solo se non lo sono . $R$ $A$ $R$ $A \ volte A$ $\ non \! R$ $\ non \! R$ $R$

Dire che un ordine è totale significa dire che la sua negazione è l'ordine inverso. Cioè, esiste un'equivalenza per un ordine tra: $\ leqslant$

$\ leqslant$ è totale;
$x \ not \ leqslant y \ iff y <x$ .

D'altra parte, non appena vi sono due elementi distinti non confrontabili da un ordine, la sua negazione non può essere un ordine (stretto o ampio), perché non è antisimmetrico. La negazione di un ordine non totale non è quindi mai un ordine.

Ad esempio, la negazione dell'inclusione ⊄ sull'insieme delle parti di un insieme di almeno due elementi non è un ordine, perché, se a ≠ b , abbiamo sempre { a } ≠ { b } con comunque { a } ⊄ { b } e { b } ⊄ { a }.

Doppio ordine

L' ordine duale (o opposto ) di un insieme ordinato P = ( E , ≤) è l'insieme ordinato P op = ( E , ≤ op ), dove ≤ op è la relazione di ordine opposto di ≤, c 'cioè la relazione ≥ (a volte usiamo * invece di op ).

Il bidual ( P op ) op di P è uguale a P .

Preordinare

Un preordine è una relazione binaria riflessiva e transitiva .

Qualsiasi preordine ℛ su un insieme $E$ induce una relazione d'ordine sull'insieme $E$ quoziente dalla relazione di equivalenza ~ definita da “ $x ~ y se e solo se ( x ℛ y e y ℛ x )$ ”.

Per maggiori dettagli ed esempi, vedere l'articolo dettagliato.

Proprietà complementari

Compatibilità

La compatibilità di una relazione d'ordine con una struttura algebrica può essere definita solo caso per caso.

Un ordine ≤ su un semigruppo ( G , +) si dice compatibile se, per tutti x , y e z in G tali che x ≤ y , abbiamo x + z ≤ y + z e z + x ≤ z + y .
Quando ( G , +) è un gruppo , allora diciamo che ( G , +, ) è un gruppo ordinato e che un elemento è positivo se è maggiore dell'elemento neutro .
Qualsiasi gruppo Archimedeo completamente ordinato è abeliano ed è immerso in ( ℝ , +, ≤).
Un anello o un campo ( A , +, ×) si dice ordinato se ha un ordine ≤ tale che ( A , +, ≤) è un gruppo ordinato e il prodotto di due elementi positivi è positivo.
Qualsiasi corpo di Archimede completamente ordinato è immerso in (ℝ, +, ×, ≤).
In un campo totalmente ordinato, -1 non è mai un quadrato o anche una somma di quadrati.
Uno spazio vettoriale ordinato (de) è uno spazio vettoriale reale ( E , +, ∙) dotato di un ordine ≤ tale che ( E , +, ≤) è un gruppo ordinato e che qualsiasi prodotto vettoriale di un reale positivo per un vettore positivo è positivo.

Set ben ordinato

Un insieme ordinato si dice ben ordinato se ogni sottoinsieme non vuoto questo insieme ha un elemento più piccolo .

Traliccio

Un insieme è detto reticolo se è ordinato e se una qualsiasi coppia di elementi ha un limite superiore e uno inferiore .

Applicazioni

Topologia dell'ordine

Un insieme ordinato può essere dotato di diverse topologie risultanti dall'ordine : la topologia dell'ordine, la topologia dell'ordine a destra e la topologia dell'ordine a sinistra.

Collegamenti con complessi simpliciali

Un'importante classe di complessi simpliciali deriva da insiemi ordinati finiti. Definiamo il complesso di ordine D (P) di un insieme ordinato finito P come l'insieme delle catene di P. Il complesso di ordine è banalmente un complesso simpliciale.

Lo studio dell'insieme ordinato in sé fornisce informazioni sul suo complesso d'ordine, ed è quindi interessante studiare un complesso simpliciale come complesso d'ordine di un insieme ordinato.

Note e riferimenti

N. Bourbaki , Elementi di matematica : Teoria degli insiemi [ dettaglio delle edizioni ], pag. III.4 .
Bourbaki , pag. III.5.
(in) AG Kurosh , Lezioni di algebra generale , Pergamon Press ,1965( leggi in linea ) , p. 11.
Bourbaki , pag. III.22-23.
Nathalie Caspard, Bruno Leclerc e Bernard Monjardet, Insiemi ordinati finiti: concetti, risultati e usi , Springer,2007( leggi in linea ) , p. 73.
Bourbaki , pag. III.7 e III.14.
Gustave Choquet , Corso di analisi , 1966, p. 23 .
(in) Steven Roman, Reticoli e insiemi ordinati , Springer ,2008, 305 pag. ( ISBN 978-0-387-78900-2 , leggi in linea ) , p. 13.
Romano 2008 , p. 284.
Ad esempio J. Riguet , “ Relazioni binarie, chiusure, corrispondenze di Galois ”, Boll. Soc. Matematica. Fr. , vol. 76,1948, pag. 114-155 ( leggi in linea ).
(en) George Bergman (en) , Un invito all'algebra generale e alle costruzioni universali , Cham, Springer ,2015, 2 ° ed. ( 1 ° ed. 1988), 572 p. ( ISBN 978-3-319-11478-1 , leggi in linea ) , p. 113.
Bourbaki , pag. III.4 e III.77.
Jean-Pierre Ramis , André Warusfel et al. , Matematica all-in-one per la licenza: Livello L1 , Dunod ,2013, 2 ° ed. ( leggi in linea ) , p. 37.

Vedi anche

Bibliografia

(it) Richard P. Stanley , Combinatoria enumerativa , vol. 1 [ dettaglio edizioni ] ( presentazione online )
(it) Efe A. Ok, Teoria dell'ordine e sue applicazioni ( leggi online )

Relazione d'ordine

Definizioni ed esempi