Ordine totale

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 $\langle X,\vee ,\wedge \rangle$ per il quale sia

$\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 $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.

Esempi

• Numeri naturali, numeri interi, numeri razionali, numeri algebrici, numeri costruibili e numeri reali muniti della usuale relazione ≤ o della sua riflessa costituiscono ordini totali.
• Ogni sottoinsieme di un insieme totalmente ordinato è un ordine totale.
• Ogni insieme di numeri cardinali o di numeri ordinali è totalmente ordinato (in effetti è anche un insieme ben ordinato).
• Le lettere dell'alfabeto inglese ordinate secondo l'ordine standard dei dizionari in lingue come inglese e italiano sono implicitamente ordinate: A < B < C ... .
• L'ordine lessicografico sull'insieme delle potenze cartesiane di un qualsiasi ordine totale o su ogni prodotto cartesiano di una qualsiasi sequenza di ordini totali. Tenuto conto del fatto che un alfabeto è implicitamente totalmente ordinato e che l'ordinamento totale si mantiene per passaggio a sottoinsieme, si ricava che ogni insieme di parole munito dell'ordine alfabetico è un ordine totale.
• Gli insiemi ordinati per inclusione (A < B se e solo se A è sottoinsieme di B) costituiscono tipici esempi di insiemi non totalmente ordinati (né {1} < {2} né {2} < {1} ). Spesso tuttavia si individuano speciali collezioni di insiemi che risultano totalmente ordinati per inclusione. Ad esempio, se per ogni intero positivo n consideriamo gli insiemi dei primi n interi positivi scrivendo I_n := {1, …, n}, allora la collezione di insiemi {I_n |: n positivo} è totalmente ordinata per inclusione.
• Se X è un qualsiasi insieme ed f una biiezione da un segmento iniziale di interi positivi ordinati totalmente da < su X, allora f induce un ordinamento totale su X se si stabilisce che x₁ < x₂ se e solo se x₁ = f(n₁) e x₂ = f(n₂) e n₁ < n₂. In effetti, più in generale ogni biiezione da un insieme totalmente ordinato induce un ordine totale nel suo codominio.

Topologia di ordine

Per ogni insieme totalmente ordinato X si possono definire gli intervalli (a, b) := {x : a < x e x < b}, (−∞, b) := {x : x < b}, (a, ∞) := {x : a < x} e (−∞, ∞) = X. Questi intervalli aperti possono essere usati per definire una topologia sull'insieme X chiamata topologia d'ordine.

Si osserva che la definizione di insieme ordinato come insieme munito di una relazione d'ordine garantisce l'unicità della topologia di ordine su ogni insieme ordinato. Tuttavia in pratica non si insiste nella distinzione tra un insieme munito di un proprio ordinamento e coppia insieme-ordine sull'insieme. Quindi per evitare confusioni quando si considerano più ordini in associazione con un solo insieme, si usa comunemente parlare di topologia di ordine indotta da un particolare ordine. Per esempio se N denota l'insieme dei numeri naturali, < e > le usuali relazioni, possiamo fare riferimento alla topologia di ordine indotta su N da < e da quella indotta da >; in questo caso le due topologie coincidono, ma questo non è vero in generale.

Il termine catena

Questo termine all'inizio di questo articolo è stato considerato come mero sinonimo di insieme totalmente ordinato. Esso però viene usato più spesso per denotare un sottoinsieme totalmente ordinato di qualche insieme parzialmente ordinato. Accade dunque che usualmente si dice che i reali costituiscono un insieme totalmente ordinato; se invece si sta considerando la totalità dei sottoinsiemi dell'insieme dei numeri interi ordinata parzialmente dall'inclusione, allora la collezione totalmente ordinata dall'inclusione { I_n |: n numero naturale} definita in un precedente esempio viene solitamente chiamata catena.

L'uso preferenziale del termine "catena" per denotare un sottoinsieme totalmente ordinato di un insieme parzialmente ordinato deriva verosimilmente dal ruolo importante che tali catene svolgono nel lemma di Zorn.

Ordini totali finiti

Ogni ordine totale finito possiede elemento minimo: la cosa si dimostra con semplici considerazioni esaustive. Quindi anche ogni sottoinsieme di un ordine totale finito possiede minimo. Quindi ogni ordine finito totale è un buon ordinamento. O con una dimostrazione diretta costruttiva, o in base all'osservazione che ogni buon ordinamento è isomorfo a un ordinale, si può dimostrare che ogni ordine totale finito è isomorfo a un segmento iniziale dei numeri interi positivi ordinati da <. In altre parole su un insieme di k elementi una biiezione con l'insieme dei primi k interi positivi induce un ordine totale. Quindi risulta possibile indicizzare gli elementi di ogni ordine finito totale e ogni buon ordine contabile mediante numeri interi positivi, oppure mediante numeri naturali in modo da rispettare l'ordinamento.

La cosa non vale per un ordine parziale, in quanto non gode della terza condizione. A questo proposito si ricordi l'esempio di ordine parziale fornito dalla relazione accadde-prima.

Bibliografia

• George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
• John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4