Un reticolo (lattice in inglese) è un insieme parzialmente ordinato in cui ogni coppia di elementi ha sia un estremo inferiore (inf) che un estremo superiore (sup). I reticoli possono anche essere caratterizzati come strutture algebriche che soddisfano determinate identità. Poiché entrambe le definizioni possono essere usate convenientemente, la teoria dei reticoli può essere applicata sia dalla teoria dell'ordine che dalla teoria dell'algebra universale. I reticoli costituiscono uno dei rappresentanti più significativi di strutture che ammettono ordine così come le strutture algebriche, quali i semireticoli, le algebre di Heyting o le algebre booleane. Il termine reticolo deriva dalla rappresentazione dei diagrammi di Hasse.
La teoria dei reticoli (in inglese: lattice theory) è la branca della matematica che si occupa proprio dello studio dei reticoli.
Definizione formale
Come accennato precedentemente, il reticolo può essere caratterizzato sia come insieme parzialmente ordinato, che come struttura algebrica. Entrambe le definizioni e la loro relazione sono spiegate più avanti.
I reticoli come insiemi parzialmente ordinati
Sia un insieme parzialmente ordinato. Diremo che è un reticolo se per ogni x e y elementi di R, il sottoinsieme ha estremo superiore ed estremo inferiore in R.
Per ogni x, y elementi di R si denota e .
I reticoli come strutture algebriche
Consideriamo una struttura algebrica , dove e sono due operazioni binarie definite in R. R è un reticolo se le seguenti identità valgono per ogni elemento a, b, c in R:
Leggi commutative:
Leggi associative:
Leggi di assorbimento:
Dalle identità precedenti derivano le seguenti
Leggi di idempotenza:
Si noti che per le leggi di idempotenza, le leggi commutative e associative rappresentano la condizione perché (R, ∨) e (R, ∧) costituiscano due semireticoli, mentre le leggi di assorbimento garantiscono che le due strutture interagiscano correttamente.
Per descrivere un reticolo limitato, una legge deve includere gli elementi neutri 0 e 1 per unire le operazioni di inf e sup nella suddetta definizione.
Equivalenza delle due definizioni
Un reticolo dotato di una relazione d'ordine possiede le due operazioni binarie e . Ora si può vedere facilmente che queste operazioni permettono di considerare il reticolo (R, ∨, ∧) in senso algebrico. Forse più sorprendentemente, si può anche ottenere l'inverso di questo risultato: si consideri ogni reticolo definito algebricamente (M, ∨, ∧). Si può definire una relazione d'ordine parziale su M considerando per ogni elemento x e y in
se e solo se
o equivalentemente
se e solo se .
Dalle leggi di assorbimento si dimostra che entrambe le definizioni siano effettivamente equivalenti. Si può ora controllare che la relazione d'ordine introdotta in questo modo definisce un ordinamento parziale in cui le operazioni di sup e inf sono date dalle operazioni e . Al contrario, la relazione d'ordine indotta dal reticolo definito algebricamente (R, ∨, ∧) coincide con l'ordinamento di in origine.
Quindi le due definizioni possono essere usate in senso interamente intercambiabile, secondo quale sia più conveniente usare per uno scopo preciso.
Esempi
Per ogni insieme A, l'insieme di tutti i suoi sottoinsiemi limitati (compreso l'insieme vuoto) può essere ordinato con la relazione di inclusione per ottenere un reticolo. Le operazioni del reticolo sono l'intersezione (inf) e l'unione (sup) degli insiemi, rispettivamente. Questo reticolo ha l'insieme vuoto come elemento più piccolo, ma conterrà l'elemento più grande soltanto se A è limitato. In generale non è un reticolo limitato. I numeri naturali con la relazione d'ordine comune sono un reticolo. L'elemento più piccolo è lo 0, mentre non esiste l'elemento più grande. Ogni reticolo completo è un reticolo limitato. L'insieme degli elementi compatti di un reticolo aritmetico completo è un reticolo con un elemento in meno, in cui le operazioni sono date limitando le operazioni rispettive del reticolo aritmetico. Questa è una proprietà specifica che distingue i reticoli aritmetici dai reticoli algebrici, per cui i compatti formano soltanto un semireticolo. In figura sono rappresentati i diagrammi di Hasse di tutti i possibili reticoli con al più cinque elementi.
Omomorfismi tra reticoli
La definizione appropriata di omomorfismo tra due reticoli può essere derivata facilmente dalla definizione algebrica seguente: dati due reticoli e un omomorfismo tra i reticoli è una funzione che verifica le seguenti proprietà:
Se i reticoli sono dotati dell'elemento più piccolo e dell'elemento più grande allora la deve conservare anche questi elementi:
Nella formulazione teorica dell'ordine, la condizione corretta è che un omomorfismo tra reticoli è una funzione che conserva le operazioni binarie inf e sup.
Si noti che ogni omomorfismo tra reticoli è necessariamente monotòno rispetto alla relazione d'ordine associata. Non è vero il viceversa: la monotonia non implica affatto le proprietà richieste di conservazione.
Usando la definizione standard degli isomorfismi come omomorfismi invertibili, si trova che un isomorfismo tra reticoli è esattamente un omomorfismo biiettivo tra i reticoli. I reticoli ed i loro omomorfismi formano ovviamente una categoria.
Due reticoli isomorfi hanno lo stesso diagramma di Hasse.
Proprietà dei reticoli
Vi sono numerose proprietà importanti dei reticoli, introdotte in questo paragrafo, molte delle quali portano a considerare categorie speciali di reticoli.
La proprietà più immediata per un reticolo R è forse quella di essere limitato. Se in generale il più piccolo elemento, il minimo, viene indicato con il simbolo 0, e il più grande, il massimo, con il simbolo 1, un reticolo R si dice limitato se possiede un massimo ed un minimo. Completezza
La categoria altamente rilevante è quella dei reticoli completi. Un reticolo è completo se ogni suo sottoinsieme ha sia l’inf che il sup. Questa definizione sembrerebbe contrapporsi alla definizione di reticolo in cui si richiede soltanto l'esistenza dell’inf o del sup (non vuoto). Risulta che dall'esistenza di tutti gli inf si conclude l'esistenza di tutti i sup e viceversa. Si noti inoltre che i reticoli completi sono sempre limitati. Esempi di reticoli completi sono:
L'insieme dei sottoinsiemi di un dato insieme, ordinato tramite la relazione di inclusione. Il sup è dato dall'unione dei sottoinsiemi e l’inf dall'intersezione dei sottoinsiemi. L'intervallo unitario [0,1] e la retta reale, con la relazione d'ordine totale e il sup e l’inf ordinari. I numeri interi non negativi, ordinati dalla relazione di divisibilità. Il più piccolo elemento di questo reticolo è il numero 1, poiché divide qualunque altro numero. Sorprendentemente, forse, l'elemento più grande è 0, perché può essere diviso da qualunque altro numero. Il sup degli insiemi limitati è dato dal minimo comune multiplo ed l’inf dal massimo comun divisore. Per gli insiemi infiniti, il sup sarà sempre 0 mentre l’inf è più grande di 1. Per esempio, l'insieme di tutti i numeri pari ha 2 come divisore comune più grande. Se 0 è rimosso da questa struttura, rimane un reticolo ma cessa di essere completo. I sottogruppi di un gruppo, ordinati tramite la relazione di inclusione. Il sup è dato dal sottogruppo generato dall'unione dei gruppi mentre l’inf è dato dall'intersezione. I sottomoduli di un modulo, sono ordinati tramite la relazione di inclusione. Il sup è dato dall'unione dei sottomoduli mentre l’inf dall'intersezione. Gli ideali di un anello, ordinati tramite la relazione di inclusione. Il sup è dato dall'unione dei ideali mentre l’inf dall'intersezione. Gli insiemi aperti di uno spazio topologico, ordinati tramite la relazione di inclusione. Il sup è dato dall'unione degli insiemi aperti mentre l’inf dall'intersezione interna. I sottoinsiemi convessi di uno spazio reale o complesso di vettori ordinati tramite la relazione di inclusione. L’inf è dato dall'intersezione degli insiemi convessi mentre il sup dall'inviluppo convesso dell'unione. Le topologie su un insieme, ordinate tramite la relazione di finezza. L’inf è dato dall'intersezione delle topologie mentre il sup dalla topologia generata dall'unione delle topologie. Il reticolo di ogni relazione binaria transitiva su un insieme. Il reticolo di ogni sottomultiinsieme di un multiinsieme. Il reticolo di ogni relazione d'equivalenza su un insieme; il simbolo di equivalenza ~ è considerato come restrittivo di ≈ ; x ~ y implica sempre x ≈ y.
Molti teoremi della teoria dell'ordine assumono forme semplici una volta dichiarati per i reticoli completi. Per esempio il teorema di Knaster-Tarski dichiara che l'insieme dei punti fissi di una funzione monotòna su un reticolo completo è ancora un reticolo completo.
Distributività
Poiché ogni reticolo possiede due operazioni binarie, è naturale considerare le relative leggi distributive. Un reticolo (R, ∨, ∧) è distributivo se per ogni elemento x, y, z in R vale
Sorprendentemente, forse, questa condizione finisce per essere equivalente a
Per i reticoli completi si possono formulare proprietà più forti ottenendo le categorie di reticoli completi e distributivi.
Esistono reticoli non distributivi; di seguito si riporta il diagramma di Hasse dei più piccoli reticoli non distributivi.
Siccome è facile verificare che ogni reticolo distributivo è a complemento unico, sorge spontanea la domanda se è vero il contrario, cioè se esistono reticoli a complemento unico che non siano distributivi.
La risposta a questa domanda è affermativa, esistono reticoli a complemento unico non distributivi (teorema di Dilwhort). Sfortunatamente in matematica non esistono ancora esempi di tali reticoli (e forse non si ha speranza di trovarli), si può solo vedere che essi esistono.
Possiamo osservare, però, alcune proprietà che devono obbligatoriamente avere reticoli così fatti. La più immediata è che essi devono essere infiniti, cioè devono avere un numero infinito di elementi. Infatti un reticolo a complemento unico, finito, è certamente distributivo.
Modularità
Spesso si trova che la distributività è una condizione troppo forte per determinate applicazioni. Una proprietà rigorosamente più debole è la modularità: un reticolo (R, ∨, ∧) è modulare se per ogni elemento x, y, z in R si ha
.
Un'altra condizione equivalente è la seguente: se x ≤ z allora per ogni y
Per esempio, il reticolo dei sottomoduli di un modulo ed il reticolo dei sottogruppi normali di un gruppo hanno questa proprietà. Inoltre ogni grata distributiva è effettivamente modulare.
La continuità e l'algebricità
Nella teoria dei domini, si è spesso interessati all'approssimazione degli elementi di un reticolo dotato di un ordine parziale, tramite elementi "molto più semplici". Questo conduce alla categoria dei reticoli ordinati continui, consistente nei reticoli dotati di relazione d'ordine in cui ogni elemento può essere ottenuto come sup di un insieme diretto di elementi che sono in relazione con l'elemento stesso. Se si possono limitare ulteriormente gli elementi compatti di un reticolo ordinato per ottenere questi insiemi diretti, allora il reticolo è anche algebrico. Entrambi i concetti possono essere applicati ai reticoli come segue: Un reticolo continuo è un reticolo completo che è continuo come reticolo ordinato. Un reticolo algebrico è un reticolo completo che è algebrico come reticolo ordinato.
Entrambe le categorie hanno proprietà interessanti. Per esempio, i reticoli continui possono essere caratterizzati come strutture algebriche (con infinite operazioni) che soddisfano determinate identità. Mentre una proprietà simile non è conosciuta per i reticoli algebrici che possono essere descritti "sintatticamente" tramite i sistemi d'informazione di Scott.
I complementi e gli pseudo-complementi