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.