Ordine totale

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

In matematica, un ordine semplice/ordine totale o ordine lineare (o relazione d'ordine totale o lineare) è una relazione binaria su un insieme X che è riflessiva, antisimmetrica, transitiva (quindi una relazione d'ordine) e totale. Questo significa che, se denotiamo una tale relazione con ≤, valgono i seguenti enunciati per tutti gli a, b e c elementi di X:

a ≤ a (riflessività)

se a ≤ b e b ≤ a, allora a = b (antisimmetria)

se a ≤ b e b ≤ c allora a ≤ c (transitività)

a ≤ b oppure b ≤ a (totalità)

Un insieme munito di un ordine totale viene chiamato insieme totalmente ordinato, o anche insieme linearmente ordinato, o catena.

La stessa definizione si può dare per i preordini: un preordine che soddisfi la proprietà di totalità si dice preordine totale.

La proprietà di totalità di una relazione si può descrivere dicendo che due suoi elementi qualsiasi costituiscono una coppia confrontabile per la relazione stessa.

Notare che la proprietà di totalità implica la riflessività, cioè che per ogni elemento a sia a ≤ a. Un ordine totale è in particolare un ordine parziale, cioè è una relazione binaria riflessiva, antisimmetrica e transitiva. Un ordine totale si può anche definire come un ordine parziale che è anche una relazione totale.

Alternativamente un insieme totalmente ordinato si può definire a partire da un particolare tipo di reticolo ${\displaystyle \langle X,\vee ,\wedge \rangle }$ per il quale sia

${\displaystyle \forall a,b\in X~:~\{a\vee b,a\wedge b\}=\{a,b\}}$ .

A tale reticolo si associa la relazione definita ponendo per due suoi generici elementi a e b:

a ≤ b se e solo se ${\displaystyle a=a\wedge b}$ .

Se a e b sono elementi di un insieme totalmente ordinato dalla relazione ≤, allora si può definire la relazione binaria a < b chiedendo: a ≤ b e a ≠ b. Questa relazione, come la ≤, è transitiva (a < b e b < c implicano a < c) ma, contrariamente a ≤, è tricotomica, cioè tale che è vero uno e uno solo dei tre fatti a < b, b < a e a = b. Si può anche seguire il percorso costruttivo opposto, cioè partire da una relazione binaria transitiva tricotomica <, definire la relazione a ≤ b per esprimere la relazione "a < b o a = b" e dimostrare che ≤ è un ordine totale.