Ordinamento

ordinamento

ordinamento o relazione d’ordine, relazione antisimmetrica e transitiva (→ antisimmetria; → transitività). La proprietà di antisimmetria porta a escludere ordinamenti di tipo circolare: infatti, fissando un verso di percorrenza su una circonferenza, si ha che dati due suoi punti distinti, ciascuno precede e ciascuno segue l’altro nel verso stabilito; per questo tale proprietà è anche detta anticircolare. Una relazione d’ordine che sia anche riflessiva (come la relazione ≤ in N), è detta ordinamento largo, mentre una relazione d’ordine tale che nessun elemento dell’insieme sia in relazione con sé stesso è detta ordinamento stretto (per esempio la relazione < in N). Si segnala tuttavia che in letteratura si trova anche una diversa definizione, che richiede che l’ordinamento, di per sé, goda anche della proprietà riflessiva. In ogni caso, lo studio degli ordinamenti larghi e quello degli ordinamenti stretti sono sostanzialmente equivalenti, nel senso che a ogni ordinamento largo è naturalmente associato un ordinamento stretto e viceversa. Se infatti ρ è un ordinamento (largo) su un insieme A, la relazione ρ′ definita da «a ρ′ b se e solo se a ρ b e a ≠ b» è un ordinamento stretto; viceversa se ψ è un ordinamento stretto, allora la relazione ψ′ definita da «a ψ′ b se e solo se a ψ b oppure a = b» è un ordinamento (largo): in entrambi i casi la seconda relazione si dice generata dalla prima.

Un insieme su cui sia definita una tale relazione è detto ordinato; più formalmente, si può pensare a un insieme ordinato come a una struttura d’ordine, vale a dire come a una coppia (A, ρ), dove A è un insieme e ρ un ordinamento su esso.

Una relazione d’ordine ρ in A è detta ordinamento totale o lineare se comunque si considerino due elementi distinti x e y di A, essi sono confrontabili rispetto alla relazione data, se cioè vale x ρ y oppure y ρ x. Un insieme in cui sia definito un ordinamento totale è detto totalmente (o linearmente) ordinato. Se esistono coppie di elementi non confrontabili l’ordinamento è detto parziale. Un insieme dotato di una relazione d’ordine parziale è detto parzialmente ordinato (o, secondo la dizione inglese, poset, acronimo di Partially Ordered Set). Per esempio, l’insieme N dei numeri naturali (come anche gli insiemi Z, Q e R dei numeri interi, razionali e reali) dotato della relazione di minore o uguale (≤) è un insieme totalmente ordinato; in analogia con i casi numerici, spesso le relazioni d’ordine (anche quando non sono totali) sono indicate con il simbolo ≤. L’insieme delle parti di un insieme A dotato della relazione di inclusione (⊆) tra sottoinsiemi è un esempio di insieme parzialmente ordinato, ma non totalmente ordinato (a meno che A non consista di un solo elemento).

Ogni insieme ordinato risulta anche strettamente ordinato e viceversa. Per esempio, l’ordinamento stretto associato alla relazione ≤ tra numeri naturali è l’ordinaria relazione di minore (<), mentre quello associato alla relazione ≥ è l’ordinaria relazione di maggiore (>). Un insieme totalmente ordinato (A, ≤) si dice bene ordinato se ogni suo sottoinsieme ha un elemento minimo ossia un primo elemento rispetto alla relazione d’ordine, cioè un elemento m ∈ A tale che per ogni a ∈ A si ha m ≤ a; in tale caso ≤ è detto un buon ordinamento. Per esempio, l’insieme N dei numeri naturali è bene ordinato rispetto al suo ordinamento naturale: tale fatto va sotto il nome di principio del buon ordinamento e risulta essere equivalente al principio di → induzione. Non avendo minimo, non è invece bene ordinato l’insieme Z dei numeri interi rispetto all’ordinamento naturale. Conseguenza dell’assioma della → scelta è il teorema del buon ordinamento (o teorema di → Zermelo), il quale afferma che ogni insieme può essere bene ordinato, vale a dire che esso ammette una relazione d’ordine totale rispetto alla quale è bene ordinato.

Un campo K è detto ordinato se su di esso è definita una relazione d’ordine totale ≤ compatibile con la sua struttura di campo (→ ordinamento, compatibilità con un’operazione di un).

Un ordinamento totale ≤ su un insieme A si dice denso se, comunque presi due elementi distinti x e y, con x che precede y nell’ordinamento, entrambi appartenenti ad A, esiste almeno un elemento z di A, distinto da essi, che segue x e precede y nell’ordinamento. Se questo è il caso, A, che necessariamente è un insieme infinito, è detto denso rispetto a ≤. Per esempio, rispetto agli ordinamenti naturali, sono densi l’insieme → Q dei numeri razionali e l’insieme → R dei numeri reali. Un ordinamento totale ≤ su un insieme infinito A si dice invece discreto se per ogni elemento di A esiste uno e un solo successore; in tale caso, l’insieme stesso si dice discreto rispetto a tale ordinamento; sono per esempio discreti rispetto all’ordinamento ≤ l’insieme N dei numeri naturali e quello Z dei numeri interi. Un insieme finito è discreto rispetto a un ordinamento totale se e soltanto se possiede un solo elemento che non ha successore: tale elemento, che è l’ultimo nell’ordinamento, è il massimo di A. Un insieme A dotato di un ordinamento denso ≤ è detto completo rispetto a esso e l’ordinamento ≤ è detto un ordinamento continuo su A, se vale l’assioma di → Dedekind. Tale assioma è per esempio soddisfatto da una retta, dotata di uno dei suoi due ordinamenti naturali (assioma di → ordinamento della retta; → Hilbert, assiomi di). L’ordinamento naturale definito sull’insieme Q dei numeri razionali non è continuo: per esempio, i due insiemi {x ∈ Q : x < 0 o x ² ≤ 2} e {x ∈ Q : x ≥ 0 e x ² ≥ 2} soddisfano le ipotesi dell’assioma di Dedekind, ma non esiste alcun elemento che separa i due insiemi; tale fatto è equivalente ad affermare l’irrazionalità di √(2). L’ordinamento canonico definito sull’insieme R dei numeri reali è invece un ordinamento continuo: ciò equivale al fatto che ogni sottoinsieme limitato di R ammette estremo superiore ed estremo inferiore, ciò che a sua volta equivale ad affermare la completezza di R come spazio metrico.