Le relazioni d'ordine

Le relazioni d'ordine sono una tipologia di relazioni matematiche che soddisfano le seguenti proprietà:


• Proprietà riflessiva $$ \forall a \in A \:\: aρa $$
• Proprietà antisimmetrica $$ \forall a,b \in A \:\: [ aρb ∧ bρa ] \rightarrow a=b $$
• Proprietà transitiva $$ \forall a,b,c \in A :\: [ aρb ∧ bρc ] \rightarrow aρc $$

Le relazioni d'ordine totali e parziali

La relazione d'ordine può essere totale o parziale

• Una relazione d'ordine parziale si applica soltanto in un sottoinsieme di coppie (a,b) dell'insieme. In questo caso l'insieme degli elementi è detto insieme parzialmente ordinato. In un insieme parzialmente ordinato soltanto alcune coppie di elementi del prodotto cartesiano sono confrontabili tra loro.

  Esempio. L'insieme delle parti P(X) con X={1,2,3} è composto dai seguenti elementi: { Ø {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }. Si tratta di un insieme parzialmente ordinato rispetto alla relazione di inclusione ⊆ perché soltanto alcune coppie sono confrontabili: {1}⊆{1,2} ma {3} ⊈ {1,2}. E così via. La rappresentazione grafica della relazione è la seguente:
  

• Una relazione d'ordine totale si applica su tutte le coppie (a,b) dell'insieme. In questo caso l'insieme degli elementi è detto insieme totalmente ordinato o catena. Sono dette catene perché hanno una struttura verticale. Tutte le coppie dell'insieme sono confrontabili tra loro.

  Esempio. Lo stesso insieme precedente X={1,2,3} è un ordinamento totale nei confronti della relazione di minoranza ≤ ( oppure di maggioranza ≥ ). In questo caso è possibile mettere in relazione qualsiasi coppia di elementi tra loro. Ad esempio, 1ρ3, 1ρ2, 2ρ3. La rappresentazione grafica prende la forma di una catena perché ogni elemento è direttamente confrontabile con gli altri elementi dell'insieme.
  

Come rappresentare graficamente una relazione d'ordine

Le relazioni d'ordine di un insieme X sono rappresentabili graficamente tramite punti e linee.

Ogni punto è associato a un elemento dell'insieme X.

Il segmento che unisce due punti individua due elementi direttamente confrontabili tra loro tramite la relazione d'ordine senza elementi intermedi.

Esempio. Gli elementi 1 e 3 sono confrontabili tra loro tramie la relazione di minoranza (≤). Tuttavia, tra loro c'è anche l'elemento 2. Per questa ragione i punti 1 e 3 non sono uniti da una linea. Sono invece collegati da una linea i punti 1 e 2 perché non c'è nessun elemento intermedio. Lo stesso si può dire per gli elementi 2 e 3.

Insiemi ordinati isomorfi

Due insiemi ordinati sono isomorfi se hanno la stessa struttura relazionale.

Ad esempio, gli insiemi totalmente ordinati con lo stesso numero n di elementi (cardinalità) sono sempre isomorfi.

In pratica, negli insiemi isomorfi le relazioni tra gli elementi hanno la stessa forma.

E così via.