struttura d'ordine

struttura d'ordine

struttura d’ordine un insieme non vuoto A, costituito da elementi di natura arbitraria, è dotato di una struttura d’ordine se su di esso è definita una relazione d’ordine ≤ (→ ordinamento). L’insieme A è detto sostegno della struttura, mentre con struttura d’ordine ci si riferisce alla coppia (A, ≤). Una struttura d’ordine (A, ≤) è detta totale (o lineare) se ≤ è una relazione d’ordine totale su A; per sottolineare che ≤ può non essere totale, si parla talvolta di struttura d’ordine parziale. Importanti esempi di strutture d’ordine totali sono costituiti dagli insiemi numerici (N, ≤), (Z, ≤), (Q, ≤), (R, ≤), dove N, Z, Q, R indicano rispettivamente l’insieme dei numeri naturali, interi, razionali e reali e dove ≤ indica la relazione d’ordine canonica su di essi definita. Se X è un insieme arbitrario costituito da più di un elemento, allora la coppia (℘(X), ⊆) costituisce un esempio di struttura d’ordine non totale, dove ℘(X) indica l’insieme delle parti di A e dove ⊆ indica la relazione di inclusione.

Una struttura d’ordine (R, ≤) è detta → reticolo se, per ogni coppia di elementi a e b di R, sono definiti il loro minimo comune maggiorante (denotato con a ∧ b) e il loro massimo comune minorante (denotato con a ∧ b). Ogni struttura d’ordine totale costituisce banalmente un reticolo: il minimo comune maggiorante e il massimo comune minorante di due elementi a e b coincidono rispettivamente con il loro massimo e il loro minimo. Un esempio di reticolo che non sia una struttura d’ordine totale è costituito invece dalla coppia (℘(X), ⊆): il minimo comune maggiorante e il massimo comune minorante di due sottoinsiemi E e F coincidono rispettivamente con la loro unione E ∪ F e con la loro intersezione E ∩ F. Un reticolo è un esempio di struttura doppia: oltre a essere dotato di una struttura d’ordine, esso è dotato anche di una → struttura algebrica giacché può essere definito come una terna (R, ∧, ∨), dove R è un insieme e dove ∧ e ∨ sono due operazioni binarie interne su di esso che soddisfano proprietà analoghe a quelle soddisfatte dalle operazioni di massimo comune minorante e di minimo comune maggiorante.

Uno strumento fondamentale nella classificazione delle strutture d’ordine sono i morfismi, e, più in particolare, gli isomorfismi. Un → morfismo (o un omomorfismo) d’ordine tra due strutture d’ordine (X, ≤) e (Y, ◁) è un’applicazione ƒ: X → Y che sia compatibile con le due strutture d’ordine, vale a dire tale che valga ƒ(a) ◁ ƒ(b) ogniqualvolta sia verificato a ≤ b, per due opportuni elementi a e b di X. Un isomorfismo d’ordine è un morfismo d’ordine che sia biunivoco. Con un leggero abuso di linguaggio, due insiemi ordinati sono detti avere la stessa struttura d’ordine se sono dotati di due strutture d’ordine isomorfe.

Le strutture d’ordine possono essere rappresentate graficamente mediante i diagrammi di → Hasse: se (A, ≤) è una struttura d’ordine, allora si rappresentano gli elementi di A come vertici nel piano e li si collega mediante segmenti secondo le due seguenti regole:

a) se x e y sono due elementi confrontabili e distinti di A e se x ≤ y, allora i corrispondenti punti nel diagramma sono disegnati in modo che quello corrispondente a x compaia “più in basso” di quello corrispondente a y;

b) due punti del diagramma sono collegati da un segmento se e solo se i corrispondenti elementi di A sono confrontabili e non esistono terzi elementi di A compresi tra di essi relativamente a ≤.

Si possono in questo modo distinguere tre particolari tipi di strutture d’ordine, a seconda della struttura del corrispondente diagramma di Hasse:

a) strutture con diagramma lineare: sono le strutture d’ordine totali, i cui elementi possono essere collocati lungo una linea retta disposta verticalmente;

b) strutture con diagramma ad albero: sono strutture d’ordine non totali tali che ogni coppia di elementi ammette un comune maggiorante o un comune minorante, ma mai entrambi;

c) strutture con diagramma a foresta: sono strutture d’ordine non totali tali che elementi non confrontabili non ammettono mai contemporaneamente maggioranti e minoranti comuni;

d) strutture con diagramma non arboreo: sono strutture d’ordine non totali, come per esempio i reticoli, in cui esistono elementi non confrontabili dotati contemporaneamente di maggioranti e minoranti comuni.