Relazione d'ordine

Da Wikipedia, l'enciclopedia libera.

In matematica, una relazione binaria $R$ entro un insieme $S$ , cioè un sottoinsieme di $S \times S := \{ (a,b) : a \in S, b \in S \}$ , si dice relazione d'ordine (entro $S$ ) se soddisfa le seguenti tre proprietà:

riflessività: per ogni $\,a \in S\,$ vale $\,a R a\,$
antisimmetria: per ogni $a,b \in S$ se $\,a R b\,$ e $\,b R a\,$ , allora $\,a=b\,$
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 tradizionalmente con il più familiare simbolo " $\leq$ " (è da notare che in questo caso il simbolo " $\leq$ " può denotare relazioni d'ordine differenti da quella che denota nell'ambito dell'insieme dei numeri reali o di suoi sottoinsiemi).

Una relazione d'ordine si dice anche ordine (che può però essere confuso con un ordine totale) o ordine parziale. 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 un insieme totalmente ordinato). In inglese un insieme parzialmente ordinato è anche detto concisamente poset (partially ordered set); questo termine è usato gergalmente anche da 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

1 Esempi
2 Ordine largo e stretto
3 Grafo di una relazione d'ordine
4 Ordinamenti totali
5 Elementi massimali e minimali; massimi e minimi
6 Ordinamenti ben fondati
7 Il Teorema del buon ordinamento
8 Catene e anticatene
9 Voci correlate

[modifica] Esempi

Alcuni esempi di insiemi parzialmente ordinati sono:

gli insiemi numerici $\mathbb N$ , $\mathbb Z$ , $\mathbb Q$ , $\mathbb R$ muniti della relazione d'ordine 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 stretto

Alcuni autori definiscono relazione d'ordine stretto una relazione $(S, < )$ che soddisfi le proprietà antiriflessiva, asimmetrica e transitiva, e quindi largo la relazione d'ordine $(S, \leq)$ definita sopra. Benché le due definizioni siano distinte, il loro studio non presenta grosse differenze poiché è facile estendere una relazione d'ordine stretto ad uno largo e viceversa.

[modifica] Grafo 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 grafo (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$ 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

In generale due elementi di una relazione d'ordine parziale non sono 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).

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.

Il grafo 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

Un elemento $a \in S$ si dice:

minimo (risp. massimo) per l'insieme $(S,\leq)$ se per ogni $x \in S$ si ha $a \leq x$ (risp. $x \leq a$ ),
minimale se l'unico $x \in S$ tale che $x\leq a$ è $a$ stesso,
massimale se l'unico $x \in S$ tale che $a\leq x$ è $a$ stesso,
maggiorante (risp. minorante) di un sottoinsieme $Y \subseteq S$ se $x\leq a$ (risp. $a\leq x$ ) per ogni $x \in Y$
estremo superiore (risp. estremo inferiore) del sottoinsieme $Y \subseteq S$ se è il minimo dell'insieme dei maggioranti (risp. il massimo dei minoranti).

[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 elemento sono mutuamente inconfrontabili. Una anticatena dell'insieme parzialmente ordinato delle divisibilità è fornita dall'insieme dei numeri primi.