Ordine totale

Inmatematica, unordine semplice/ordine totaleoordine lineare(orelazione d'ordine totaleolineare) è unarelazione binariasu uninsiemeX che èriflessiva,antisimmetrica,transitiva(quindi unarelazione d'ordine) etotale. Questo significa che, se denotiamo una tale relazione con ≤, valgono i seguenti enunciati per tutti glia,becelementi diX:
Un insieme munito di un ordine totale viene chiamatoinsieme totalmente ordinato, o ancheinsieme linearmente ordinato, ocatena.
La stessa definizione si può dare per ipreordini: un preordine che soddisfi la proprietà di totalità si dicepreordine totale.
La proprietà ditotalitàdi una relazione si può descrivere dicendo che due suoi elementi qualsiasi costituiscono unacoppia confrontabileper la relazione stessa.
Notare che la proprietà di totalità implica lariflessività, cioè che per ogni elementoasiaa≤a. Un ordine totale è in particolare unordine parziale, cioè è una relazione binaria riflessiva, antisimmetrica e transitiva. Un ordine totale si può anche definire come un ordine parziale che è anche unarelazione totale.
Alternativamente un insieme totalmente ordinato si può definire a partire da un particolare tipo direticolo⟨X,∨,∧⟩{\displaystyle \langle X,\vee ,\wedge \rangle }per il quale sia
A tale reticolo si associa la relazione definita ponendo per due suoi generici elementiaeb:
Seaebsono elementi di un insieme totalmente ordinato dalla relazione ≤, allora si può definire la relazione binariaa<bchiedendo:a≤bea≠b. Questa relazione, come la ≤, è transitiva (a<beb<cimplicanoa<c) ma, contrariamente a ≤, ètricotomica, cioè tale che è vero uno e uno solo dei tre fattia<b,b<aea=b. Si può anche seguire il percorso costruttivo opposto, cioè partire da una relazione binaria transitiva tricotomica <, definire la relazionea≤bper esprimere la relazione "a<boa=b" e dimostrare che ≤ è un ordine totale.
Per ogni insieme totalmente ordinatoXsi possono definire gliintervalli(a,b) := {x:a<xex<b}, (−∞,b) := {x:x<b}, (a, ∞) := {x:a<x} e (−∞, ∞) =X.  Questi intervalli aperti possono essere usati per definire unatopologiasull'insiemeXchiamatatopologia 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 seNdenota l'insieme deinumeri naturali, < e > le usuali relazioni, possiamo fare riferimento alla topologia di ordine indotta suNda < e da quella indotta da >; in questo caso le due topologie coincidono, ma questo non è vero in generale.
Questo termine all'inizio di questo articolo è stato considerato come mero sinonimo diinsieme totalmente ordinato. Esso però viene usato più spesso per denotare un sottoinsieme totalmente ordinato di qualcheinsieme parzialmente ordinato. Accade dunque che usualmente si dice che i reali costituiscono uninsieme 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 { In|: 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 nellemma di Zorn.
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 è unbuon ordinamento. O con una dimostrazione diretta costruttiva, o in base all'osservazione che ogni buon ordinamento èisomorfoa unordinale, si può dimostrare che ogni ordine totale finito èisomorfoa unsegmento inizialedei 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 unordine parziale, in quanto non gode della terza condizione. A questo proposito si ricordi l'esempio di ordine parziale fornito dalla relazioneaccadde-prima.