Relazione d'ordine

Da Wikipedia, l'enciclopedia libera.

In matematica, più precisamente in teoria degli ordini, una relazione binaria R entro un insieme S, cioè un sottoinsieme del quadrato cartesiano S \times S := \{ (a,b) : a \in S, b \in S \}, si dice relazione d'ordine (o semplicemente ordine) su S se soddisfa le seguenti tre proprietà:

  1. riflessività: per ogni \,a \in S\, vale \,a R a\,
  2. antisimmetria: per ogni a,b \in S se \,a R b\, e \,b R a\,, allora \,a=b\,
  3. transitività: per ogni \,a,b,c \in S\, se vale \,a R b\, e \,b R c\,, allora vale anche \,a R \,c.

Le relazioni d'ordine si indicano spesso con il familiare simbolo "\leq", anche quando questo simbolo denota una relazione d'ordine che nulla ha a che fare con quella usata tradizionalmente per l'insieme dei numeri reali e per i suoi sottoinsiemi. Talora si usa in modo estrapolato anche il simbolo insiemistico "\subseteq". Poco usati ma più consigliabili simboli chiaramente dissimmetrici come "\sqsubseteq" e "\preccurlyeq".

La coppia (S,\leq) costituita da un insieme e da una relazione d'ordine su di esso si dice insieme parzialmente ordinato, o anche semplicemente insieme ordinato (che può però essere confuso con il termine più specifico insieme totalmente ordinato). In inglese un insieme parzialmente ordinato è anche detto concisamente poset (partially ordered set); questo termine è usato gergalmente anche da molti studiosi italiani.

Le relazioni d'ordine, e gli insiemi ordinati loro alter ego, si incontrano, esplicitamente o meno, in tutti i settori della matematica (dalla teoria astratta degli insiemi, alle applicazioni enumerative e strutturali). Esse si presentano in una grande varietà di forme ed è importante che esse siano studiate organicamente.

Indice

[modifica] Primi esempi

Esempi ben noti di insiemi parzialmente ordinati sono:

  • gli insiemi numerici \mathbb N, \mathbb Z, \mathbb Q, \mathbb R muniti della relazione d'ordine totale standard aRb \Leftrightarrow a \leq b,
  • l'insieme \mathbb N \backslash \{0\} munito della relazione di divisibilità aRb \Leftrightarrow a | b (cioè a è un divisore di b)
  • Una qualunque famiglia di insiemi munita della relazione di inclusione aRb \Leftrightarrow a \subseteq b (cioè a è sottoinsieme di b)

[modifica] Ordine largo e ordine stretto

Alcuni autori definiscono relazione d'ordine stretto una relazione (S, < ) che soddisfi le proprietà riflessiva, asimmetrica e transitiva, e quindi chiamano relazione d'ordine largo la relazione d'ordine (S, \leq) definita sopra.

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 S un insieme e denotiamo con \,\Delta(S)\, la diagonale di \,S\times S\,, \,\Delta(S):= \{ (s,s) : s\in S \} \,. Ad ogni relazione d'ordine stretto \,(S,R)\, è associata la relazione d'ordine largo \,(S,R\cup \Delta(S))\,; viceversa ad ogni relazione d'ordine largo \,(S,R')\, è associata la relazione d'ordine stretto \,(S,R'\setminus \Delta(S))\,.

[modifica] Digrafo di una relazione d'ordine

Grafo della relazione di divisibilità

Se l'insieme S è 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 S e tale che due nodi a e b sono connessi da un arco se e solo se a \leq b e non ci sono elementi intermedi tra di loro (cioè non esiste nessun c\ne a,b tale che a \leq c e 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à).

[modifica] Ordinamenti totali

Due elementi a e b di un insieme ordinato \,(S,R)\, si dicono confrontabili se accade che a R b oppure che b R a. In generale due elementi di una relazione d'ordine parziale possono non essere confrontabili, cioè non sono necessariamente in relazione. Ad esempio in \mathbb N \backslash \{0\} munito della relazione di divisibilità gli elementi 2 e 3 non sono in relazione (nessuno dei due è divisore dell'altro) e vi sono coppie di sottoinsiemi di un dato ambiente tali che si trovano elementi del primo non appartenenti al secondo e viceversa, per cui nessuno dei due è sottoinsieme dell'altro.

Un insieme parzialmente ordinato si dice totalmente ordinato se per ogni a,b \in S vale a \leq b oppure b \leq a. Gli ordini totali si chiamano anche ordini lineari e risultano tendenzialmente più semplici da trattare.


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).

[modifica] Elementi massimali e minimali; massimi e minimi

All'interno di un ordine possiamo trovare alcuni elementi che giocano un ruolo particolare. Supponiamo (S,\leq) un ordine: se esiste un m \in S tale che

m\leq a

per ogni a in S, allora si dice che m è l'elemento minimo di S. Dualmente si definisce elemento massimo un M tale che

a\leq M per ogni a.

Minimo e massimo sono anche detti a volte 0 e 1, richiamando aspetti di logica booleana, ma sono notazioni infelici. Infatti per esempio, nella relazione di divisibilità tra naturali essi giocano proprio il ruolo opposto: 1 divide ogni altro elemento, dunque è un minimo, mentre 0 è divisibile per qualsiasi numero, dunque è il massimo.

Concetti relativi ma distinti sono quelli di elemento minimale e massimale: m si dice elemento minimale di S se

a\leq m implica m = a per ogni a.

M sarà invece un elemento massimale se

M\leq a implica M = a per ogni a.

In generale, massimo ed elemento massimale non sono la stessa cosa. Si pensi a {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é 3\geq x è soddisfatto solo per x = 3. Addirittura 5 è sia elemento massimale che minimale, poiché non è in relazione con nessun altro elemento dell'insieme diverso da sé stesso. Dall'esempio è facile intuire che le due definizioni (massimo e elemento massimale; minimo e elemento minimale) coincidono in presenza di un ordine totale.

Consideriamo ora un sottoinsieme K di un insieme ordinato S. Esso eredita naturalmente, per restrizione, una sua struttura d'ordine e le relative proprietà. Per K si possono dare altre nozioni: un elemento z di S si dirà un maggiorante per K se

y \leq z per ogni y in K

Un minorante sarà un t in S tale che

t\leq y per ogni y in K

Ad esempio, -1 è un minorante per l'insieme dei numeri naturali con l'ordinamento classico. Ma lo è anche un qualsiasi altro numero negativo: da qua nasce la definizione di estremo superiore (risp. estremo inferiore), come quel maggiorante (risp. minorante) tale che

M\leq M' per ogni altro maggiorante M' (risp. m'\leq m per ogni altro minorante m').

[modifica] Intervalli

Se a\leq b, l'intervallo [a,b] è definito come l'insieme degli elementi x tali che a\leq x e x\leq b, in completa analogia con gli intervalli reali. Similmente si definiscono intervalli semiaperti o aperti, utilizzando l'ordine stretto < , e le semirette (-\infty,b]=\{x: x\leq b\} e [a,+\infty)=\{x: a\leq x\}.

[modifica] 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" (a_1, b_1) \leq (a_2, b_2) se a_1\leq a_2 e b_1\leq b_2 (l'ordine così formato è detto il prodotto diretto dei due ordini)
  • secondo la relazione (a_1, b_1) \leq (a_2, b_2) se a_1 < a_2 \wedge b_1 < b_2 o a_1=a_2 \wedge b_1= b_2

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

[modifica] Ordinamenti ben fondati

Una relazione d'ordine su un insieme si dice ben fondata o buon ordinamento se per ogni sottoinsieme Y\subseteq S non vuoto esiste un elemento minimale.

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

[modifica] 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).

[modifica] Catene e anticatene

Facciamo riferimento ad un insieme parzialmente ordinato (S,\leq). Due elementi di S si dicono confrontabili se il primo è minore del secondo o viceversa; se nessuna delle due relazioni vale si dicono elementi inconfrontabili.

Si dice catena ogni sottoinsieme Y di S tale che la relazione d'ordine ridotta a Y costituisce un ordine totale. 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.

Si dice invece anticatena dell'insieme parzialmente ordinato (S,\leq) un sottoinsieme di S i cui elementi sono mutuamente inconfrontabili. Una anticatena dell'insieme parzialmente ordinato delle divisibilità è fornita dall'insieme dei numeri primi.

[modifica] Voci correlate


Estratto da "http://it.wikipedia.org/wiki/Relazione_d%27ordine"
Strumenti personali