Relazione d'ordine

In matematica, più precisamente in teoria degli ordini, una relazione d'ordine di un insieme è una relazione binaria tra elementi appartenenti all'insieme che gode delle seguenti proprietà:

• riflessiva;
• antisimmetrica;
• transitiva.

Si definisce insieme parzialmente ordinato (oppure ordine) la coppia costituita da un insieme e da una relazione d'ordine su di esso. Le relazioni d'ordine si indicano spesso con i simboli ${\displaystyle \leq }$, ${\displaystyle \subseteq }$, ${\displaystyle \sqsubseteq }$ e ${\displaystyle \preccurlyeq }$.

In lingua inglese un insieme parzialmente ordinato è anche detto concisamente poset (Partially Ordered Set), e questo termine è usato gergalmente anche nella lingua italiana.

Definizione

Dati due insiemi ${\displaystyle A}$ e ${\displaystyle B}$, il loro prodotto cartesiano è l'insieme delle coppie ordinate definito nel modo seguente:^[1]

${\displaystyle A\times B:=\{(a,b):a\in A{\text{ e }}b\in B\}.}$

Si definisce relazione binaria su un insieme ${\displaystyle A}$ un sottoinsieme ${\displaystyle R}$ del prodotto cartesiano ${\displaystyle A\times A}$.^[2] Due elementi ${\displaystyle x}$ e ${\displaystyle y}$ sono messi in relazione da ${\displaystyle R}$ se:

${\displaystyle (x,y)\in R}$

e in tal caso si scrive ${\displaystyle xRy}$.

Una relazione d'ordine ${\displaystyle \leq }$ è una relazione binaria tra elementi di un insieme ${\displaystyle A}$ riflessiva, antisimmetrica e transitiva.^[3]

Esplicitamente, tale relazione soddisfa le seguenti proprietà:

${\displaystyle x\leq x,\qquad \forall x\in A;}$

${\displaystyle [x\leq y\land y\leq x]\implies x=y,\qquad \forall x,y\in A;}$

${\displaystyle [x\leq y\land y\leq z]\implies x\leq z,\qquad \forall x,y,z\in A.}$

Le relazioni d'ordine si indicano spesso con i simboli ${\displaystyle \leq }$, ${\displaystyle \subseteq }$, ${\displaystyle \sqsubseteq }$ e ${\displaystyle \preccurlyeq }$.

La coppia ${\displaystyle (A,\leq )}$ costituita da un insieme e da una relazione d'ordine su di esso si dice insieme parzialmente ordinato o semplicemente ordine, da non confondere con il termine più specifico insieme totalmente ordinato.

Primi esempi

Esempi ben noti di insiemi parzialmente ordinati sono:

• gli insiemi numerici ${\displaystyle \mathbb {N} }$, ${\displaystyle \mathbb {Z} }$, ${\displaystyle \mathbb {Q} }$, ${\displaystyle \mathbb {R} }$ muniti della relazione d'ordine totale standard ${\displaystyle aRb\Leftrightarrow a\leq b}$;
• l'insieme ${\displaystyle \mathbb {N} \backslash \{0\}}$ munito della relazione di divisibilità ${\displaystyle aRb\Leftrightarrow a|b}$ (cioè ${\displaystyle a}$ è un divisore di ${\displaystyle b}$).

Una qualunque famiglia di insiemi munita della relazione di inclusione ${\displaystyle aRb\Leftrightarrow a\subseteq b}$ (cioè ${\displaystyle a}$ è sottoinsieme di ${\displaystyle b}$)

Ordine largo e ordine stretto

Alcuni autori^[4] definiscono relazione d'ordine "stretto" una relazione ${\displaystyle (A,<)}$ che soddisfi le proprietà antiriflessiva, antisimmetrica e transitiva (o, equivalentemente e più concisamente, le proprietà asimmetrica e transitiva), e quindi chiamano relazione d'ordine "largo" la relazione d'ordine ${\displaystyle (A,\leq )}$. L'ordine stretto mira a concentrarsi sulla asimmetria della relazione, non considerando la riflessività.

Benché le due definizioni siano distinte, il loro studio non presenta grosse differenze, in quanto tra le due classi di relazioni sussiste una corrispondenza biunivoca molto semplice.

Sia ${\displaystyle A}$ un insieme e denotiamo con ${\displaystyle \Delta (A)}$ la diagonale di ${\displaystyle A\times A}$, cioè ${\displaystyle \Delta (A):=\{(x,x):x\in A\}}$, allora ad ogni relazione d'ordine largo ${\displaystyle (A,\leq )}$ è associata la relazione d'ordine stretto ${\displaystyle (A,\leq )\setminus \Delta (A)}$; viceversa ad ogni relazione d'ordine stretto ${\displaystyle (A,<)}$ è associata la relazione d'ordine largo ${\displaystyle (A,<)\cup \Delta (A)}$.

Digrafo di un ordine

Se l'insieme ${\displaystyle A}$ è finito o numerabile la relazione d'ordine si può rappresentare visivamente mediante un digrafo (risp. finito o numerabile) i cui nodi sono gli elementi di ${\displaystyle A}$ e tale che due nodi ${\displaystyle a}$ e ${\displaystyle b}$ sono connessi da un arco se e solo se ${\displaystyle a\leq b}$ e non ci sono elementi intermedi tra di loro (cioè non esiste nessun ${\displaystyle c\neq a,b}$ tale che ${\displaystyle a\leq c}$ e ${\displaystyle c\leq b}$). Il grafo di una relazione d'ordine non può avere cicli, mentre può avere più componenti connesse e da ogni suo nodo può entrare ed uscire qualsiasi numero di archi. Se il grafo è numerabile, da un nodo possono entrare o uscire infiniti archi (questo è il caso della relazione di divisibilità).

Ordini semplici, lineari e totali

Due elementi ${\displaystyle a}$ e ${\displaystyle b}$ di un insieme parzialmente ordinato ${\displaystyle (A,\leq )}$ si dicono confrontabili se accade che ${\displaystyle a\leq b}$ oppure che ${\displaystyle b\leq a}$.

In generale, due elementi di una relazione d'ordine parziale possono non essere confrontabili, cioè non sono necessariamente in relazione fra di loro. Ad esempio in ${\displaystyle \mathbb {N} \backslash \{0\}}$ munito della relazione di divisibilità, gli elementi 2 e 3 non sono in relazione perché nessuno dei due è divisore dell'altro.

Un insieme si dice un ordine semplice o lineare, oppure ordine totale se per ogni ${\displaystyle a,b\in A}$, ${\displaystyle a}$ e ${\displaystyle b}$ sono confrontabili (ossia vale ${\displaystyle a\leq b}$ oppure ${\displaystyle b\leq a}$).

Il digrafo di un insieme totalmente ordinato si può rappresentare come un segmento o una retta o una semiretta su cui giacciono tutti i nodi (corrispondenti a tutti gli elementi dell'insieme).

Catene e anticatene

Sia un ordine ${\displaystyle (A,\leq )}$, si dice catena ogni sottoinsieme ${\displaystyle Y\subseteq A}$ tale che la relazione d'ordine ridotta a ${\displaystyle Y}$ costituisce un ordine semplice.

Si dice invece anticatena dell'insieme parzialmente ordinato ${\displaystyle (A,\leq )}$ un sottoinsieme ${\displaystyle Y\subseteq A}$ i cui elementi sono mutuamente inconfrontabili. Una anticatena dell'insieme parzialmente ordinato delle divisibilità è fornita dall'insieme dei numeri primi.

Esempio

Per l'insieme parzialmente ordinato della divisibilità, sono catene gli insiemi delle potenze positive di un numero primo e più in generale i sottoinsiemi ottenuti con un processo che inizia considerando un intero positivo e prosegue aggiungendo ad ogni passo un multiplo dell'intero aggiunto in precedenza. Si possono considerare catene finite o infinite; il processo precedente può essere finito o illimitato.

Maggiorante e minorante

Sia ${\displaystyle (A,\leq )}$ un insieme parzialmente ordinato (poset) e ${\displaystyle \varnothing \neq S\subseteq A}$. Allora si dice che un elemento ${\displaystyle y\in A}$ è un maggiorante di ${\displaystyle S}$ se ${\displaystyle x\leq y}$ per ogni ${\displaystyle x\in S}$.

Analogamente, in modo duale, un elemento ${\displaystyle y\in A}$ si definisce un minorante di un insieme ${\displaystyle S}$ se ${\displaystyle y\leq x}$ per ogni ${\displaystyle x\in S}$.

Se ${\displaystyle S}$ ammette almeno un maggiorante (minorante), allora si dice che ${\displaystyle S}$ è un sottoinsieme limitato superiormente (inferiormente).

Un sottoinsieme che possiede sia maggioranti che minoranti si dice limitato d'ordine.

Se l'insieme ${\displaystyle S}$ è un insieme numerico con cardinalità maggiore di uno (${\displaystyle |S|>1}$), allora scegliendo un suo sottoinsieme ${\displaystyle S_{2}\subseteq S}$ con cardinalità uguale a 2 (${\displaystyle |S_{2}|=2}$), si può definire il minimo tra i due soli elementi, ${\displaystyle a}$ e ${\displaystyle b}$ con la seguente relazione:

${\displaystyle \min\{a,b\}=\mathbf {1} _{\mathbb {R} ^{-}}(a-b)(a-b)+b.}$

Il massimo tra i due elementi si trova invece con la seguente espressione:

${\displaystyle \max\{a,b\}=\mathbf {1} _{\mathbb {R} ^{+}}(a-b)(a-b)+b,}$

dove con ${\displaystyle \mathbf {1} }$ si è indicata la funzione indicatrice.

Elementi massimali e minimali

Sia ${\displaystyle (A,\leq )}$ un ordine. Si dice che ${\displaystyle m}$ è l'elemento minimo di ${\displaystyle A}$ se ${\displaystyle m\leq a}$ per ogni ${\displaystyle a\in A}$.

Si definisce elemento massimo di ${\displaystyle A}$ un ${\displaystyle y\in A}$ tale che ${\displaystyle a\leq y}$ per ogni ${\displaystyle a\in A}$.

Vi sono ordinamenti per cui non esiste l'elemento minimo (rispettivamente, massimo); si mostra facilmente che se esiste un elemento minimo (rispettivamente, massimo) esso è unico. Quando esistono, l'elemento massimo e l'elemento minimo di ${\displaystyle A}$ si indicano rispettivamente come ${\displaystyle \max A}$ e ${\displaystyle \min A}$.

Su ordini non semplici è utile definire altri due concetti: quello di elemento minimale e massimale.

• ${\displaystyle m}$ si dice elemento minimale di ${\displaystyle A}$ se ${\displaystyle a\in A,\ a\leq m\;\Rightarrow \;a=m}$.
• ${\displaystyle M}$ è invece un elemento massimale se ${\displaystyle a\in A,\ M\leq a\;\Rightarrow \;a=M}$.

In generale, massimo ed elemento massimale non corrispondono allo stesso elemento. Si consideri come esempio l'insieme ${\displaystyle \{2,3,4,5,6\}}$ fornito della relazione di divisibilità: esso non ammette né massimo né minimo, ma per esempio 3 è un elemento minimale, poiché ${\displaystyle x\mid 3}$ è soddisfatto solo per ${\displaystyle x=3}$. Si presti attenzione inoltre che l'elemento 3 non può essere massimale. Se così fosse, allora 3 non dividerebbe nessun altro elemento dell'insieme, ma ${\displaystyle 3\mid 6}$ che dimostra l'assurdità della asserzione dato che ${\displaystyle 3\neq 6}$. Addirittura 5 è sia elemento massimale che minimale, poiché non è in relazione con nessun altro elemento dell'insieme diverso da se stesso. Dall'esempio è facile intuire che le due definizioni (massimo ed elemento massimale; minimo e elemento minimale) coincidono in presenza di un ordine semplice.

Estremo superiore ed inferiore

Sia ${\displaystyle (A,\leq )}$ un ordine e sia ${\displaystyle \varnothing \neq S\subseteq A}$. Definiamo:

${\displaystyle M_{S}=\{x\in A:x{\text{ è maggiorante di }}S\};}$

${\displaystyle m_{s}=\{x\in A:x{\text{ è minorante di }}S\}.}$

Allora si definiscono:

• estremo superiore di ${\displaystyle S}$ il ${\displaystyle \min M_{S}}$; quando esiste è indicato con ${\displaystyle \sup S}$;
• estremo inferiore di ${\displaystyle S}$ il ${\displaystyle \max m_{S}}$; quando esiste è indicato con ${\displaystyle \inf S}$.

Osserviamo che, dato un sottoinsieme, non è detto che esso ammetta un minimo o un massimo, e dunque non è detto che esistano gli estremi superiori e inferiori.

Segmenti iniziali e finali

Sia ${\displaystyle (A,\leq )}$ un insieme ordinato e un sottoinsieme ${\displaystyle S\subseteq A}$, allora ${\displaystyle S}$ è detto:

• segmento iniziale di ${\displaystyle A}$, se dati due elementi ${\displaystyle x\in S}$ e ${\displaystyle y\in A}$, si ha che ${\displaystyle y\leq x\Rightarrow y\in S}$;
• segmento finale di ${\displaystyle A}$, se analogamente ${\displaystyle x\leq y\Rightarrow y\in S}$.

In altre parole, gli elementi di ${\displaystyle S}$ non ammettono (rispettivamente) minimo o massimo al di fuori da ${\displaystyle S}$.

Ordinamenti ben fondati

Una relazione d'ordine su un insieme ${\displaystyle A}$ si dice "ben fondata" o buon ordinamento se ogni sottoinsieme ${\displaystyle Y\subseteq A}$ non vuoto è dotato di minimo.

Un tipico esempio di buon ordinamento è quello che stabilisce la relazione d'ordine standard sull'insieme ${\displaystyle \mathbb {N} }$ dei numeri naturali. L'affermazione che i naturali sono un insieme ben ordinato, ossia che ogni sottoinsieme ${\displaystyle X}$ di ${\displaystyle \mathbb {N} }$ ha un minimo viene talvolta chiamata principio del buon ordinamento e si può dimostrare essere equivalente al principio di induzione.

Il teorema del buon ordinamento

Il teorema del buon ordinamento (da non confondere con il principio del buon ordinamento) asserisce che su ogni insieme non vuoto può essere definita una relazione d'ordine ben fondata (o buon ordinamento). Tale enunciato è equivalente all'assioma della scelta (cioè assumendolo vero si può dimostrare l'assioma della scelta e viceversa).

Prodotto cartesiano di ordini

Il prodotto cartesiano di due insiemi parzialmente ordinati può essere munito anch'esso di un ordine in più modi:

• secondo il criterio dell'ordine lessicografico;
• secondo il confronto "termine a termine" ${\displaystyle (a_{1},b_{1})\leq (a_{2},b_{2})}$ se ${\displaystyle a_{1}\leq a_{2}}$ e ${\displaystyle b_{1}\leq b_{2}}$ (l'ordine così formato è detto il prodotto diretto dei due ordini);
• secondo la relazione ${\displaystyle (a_{1},b_{1})\leq (a_{2},b_{2})}$ se ${\displaystyle a_{1}<a_{2}\land b_{1}<b_{2}}$ o ${\displaystyle a_{1}=a_{2}\land b_{1}=b_{2}}$.

Se i due ordini sono semplici, lo è anche l'ordine lessicografico, ma non necessariamente gli altri due.

Funzioni e relazioni d'ordine

Siano ${\displaystyle (A,\leq )}$ e ${\displaystyle (P,\preccurlyeq )}$ due ordini e sia ${\displaystyle f\colon A\to P}$.

• ${\displaystyle f}$ si dice monotona se ${\displaystyle x\leq y\Rightarrow f(x)\preccurlyeq f(y)}$ per ogni ${\displaystyle x,y\in P}$.
• ${\displaystyle f}$ si dice antitona se ${\displaystyle x\leq y\Rightarrow f(x)\succcurlyeq f(y)}$ per ogni ${\displaystyle x,y\in P}$.

Note

Bibliografia

• Michael Reed, Barry Simon, Methods of Modern Mathematical Physics, Vol. 1: Functional Analysis, 2ª ed., San Diego, California, Academic press inc., 1980, ISBN 0-12-585050-6.

Voci correlate

• Insieme totalmente ordinato
• Reticolo (matematica)
• Ordine denso
• Arborescenza, o albero con radice
• Teoria dei grafi
• Relazione di equivalenza
• Preordine
• Estremo superiore
• Condizione della catena ascendente
• Gruppo ordinato
• Campo ordinato

Collegamenti esterni

• relazione d'ordine, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Partial Order, su MathWorld, Wolfram Research.
• (EN) Partial order, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

Controllo di autorità	GND (DE) 4172733-2