Relazioni d'ordine degli insiemi

Un altro tipo importante di relazioni binarie sono le relazioni d’ordine o ordinamenti indicate con i simboli ≥ (l’elemento di sinistra segue quello di destra) o ≤ (l’elemento di sinistra precede quello di destra). Un ordinamento è tale se soddisfa le proprietà:

• riflessiva: ∀ x ∈ X | x ≤ x, ovvero ogni elemento dell’insieme X è corrispondente a se stesso attraverso la relazione ≤ ;
• antisimmetrica: ∀ x, y ∈ X | x ≤ y ⋀ y ≤ x ⇒ x = y, cioè dati due elementi vale la relazione ≤ anche al contrario se e solo se i due elementi coincidono;
• transitiva: ∀ x, y, z ∈ X | x ≤ y ⋀ y ≤ z ⇒ x ≤ z, ovvero per ogni terna di elementi dell’insieme, l’ordinamento attraverso ≤ di un elemento y che segue un secondo elemento x e precede un terzo elemento z implica che quest’ultimo elemento z deve seguire x.

Gli elementi ℜ(x,y) - appartenenti al grafico - di una relazione d’ordine si dicono confrontabili tra loro. Se presi qualsiasi x, y ∈ X possiamo stabilire x ≤ y ⋁ y ≤ x l’ordinamento sarà totale, altrimenti parziale.

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

Esempi di relazioni d'ordine degli insiemi

Esempio 1: ℕ l’insieme dei numeri naturali è un insieme ordinato con ordinamento totale per mezzo della relazione ≤, ≥. Il suo grafo orientato può essere rappresentato come segue:

Esempio 2: ℤ, ℚ e ℝ rispettivamente l’insieme dei numeri interi, razionali e reali sono insiemi ordinati con ordinamento totale per mezzo della relazione ≤, ≥.

Esempio 3: ℂ l’insieme dei numeri complessi è parzialmente ordinato poichè dati (x, x’), (y, y’) ∈ ℂ è possibile stabilire (x, x’) ≤ (y, y’) ⇔ (x’ = y’ ⋀ x ≤ y) ⋁ (x = y ⋀ x’ ≤ y’). Tuttavia non è possibile stabilire un ordinamento totale su tale insieme.