Reticolo (matematica)

In matematica, 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.

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 $(R,\leq )$ un insieme parzialmente ordinato. Diremo che $(R,\leq )$ è un reticolo se per ogni x e y elementi di R, il sottoinsieme $\{x,y\}$ ha estremo superiore ed estremo inferiore in R.

Per ogni x, y elementi di R si denota $x\vee y=\mathrm {sup} \{x,y\}$ e $x\wedge y=\mathrm {inf} \{x,y\}$.

I reticoli come strutture algebriche

Consideriamo una struttura algebrica $(R,\vee ,\wedge )$, dove $\vee$ e $\wedge$ 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:

$a\vee b=b\vee a$

$a\wedge b=b\wedge a$

Leggi associative:

$a\vee (b\vee c)=(a\vee b)\vee c$

$a\wedge (b\wedge c)=(a\wedge b)\wedge c$

Leggi di assorbimento:

$a\vee (a\wedge b)=a$

$a\wedge (a\vee b)=a$

Dalle identità precedenti derivano le seguenti

Leggi di idempotenza:

$a\vee a=a$

$a\wedge a=a$

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 $\vee$ e $\wedge$. 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 $\leq$ su M considerando per ogni elemento x e y in ${M}$

$x\leq y$ se e solo se $x=x\wedge y$

o equivalentemente

$x\leq y$ se e solo se $y=x\vee y$ .

Dalle leggi di assorbimento si dimostra che entrambe le definizioni siano effettivamente equivalenti. Si può ora controllare che la relazione d'ordine $\leq$ introdotta in questo modo definisce un ordinamento parziale in cui le operazioni di sup e inf sono date dalle operazioni $\vee$ e $\wedge$. Al contrario, la relazione d'ordine indotta dal reticolo definito algebricamente (R, ∨, ∧) coincide con l'ordinamento di ${R}$ 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 $(R,\vee ,\wedge )$ e $(M,\cup ,\cap ),$ un omomorfismo tra i reticoli è una funzione $f:R\to M$ che verifica le seguenti proprietà:

$f(x\vee y)=f(x)\cup f(y),$

$f(x\wedge y)=f(x)\cap f(y).$

Se i reticoli sono dotati dell'elemento più piccolo $0$ e dell'elemento più grande $1,$ allora la $f$ deve conservare anche questi elementi:

$f(0)=0,$

$f(1)=1.$

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

$x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$

Sorprendentemente, forse, questa condizione finisce per essere equivalente a

$x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$

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

$x\vee (y\wedge (x\vee z))=(x\vee y)\wedge (x\vee z)$.

Un'altra condizione equivalente è la seguente: se x ≤ z allora per ogni y

$x\vee (y\wedge z)=(x\vee y)\wedge z$

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

Il concetto dei complementi introduce l'idea "della negazione" nella teoria dei reticoli. Si consideri un reticolo limitato con 1 come elemento più grande e 0 come elemento più piccolo. Si dice che un elemento x è complemento dell'elemento y se:

$x\vee y=1$ e $x\wedge y=0$

Un reticolo limitato in cui ogni elemento ha un complemento è denominato reticolo complementato. Si noti che al complemento non è richiesto né di essere unico né essere "speciale" in ogni senso fra tutti i complementi esistenti. Al contrario, un'algebra booleana ha un unico complemento per ogni elemento x che può essere denotato così da ¬ x.

In un reticolo complementato distributivo se un elemento ha un complemento, questo è unico. Infatti se un elemento x avesse due complementi, y e z

$y=y\vee 0=y\vee (x\wedge z)=(y\vee x)\wedge (y\vee z)=(z\vee x)\wedge (y\vee z)=z\vee (x\wedge y)=z\vee 0=z$

Le algebre di Heyting sono esempi di reticoli limitati, all'interno dei quali i complementi solitamente non esistono. Tuttavia, ogni elemento x in un'algebra di Heyting ha uno pseudo-complemento che solitamente è anche denotato da ¬ x. È caratterizzato, essendo il più grande fra tutti gli elementi y dalla proprietà

$x\wedge y=0$.

Se gli pseudo-complementi di un'algebra di Heyting sono in effetti complementi, allora si ha un'algebra booleana.

Sottoreticolo

Sia (R, ∨, ∧) un reticolo, e sia (R' , ≤) un suo sottoinsieme ordinato. Allora R' si dice sottoreticolo di R se per ogni x, y ∈ R' implica x ∨ y ∈ R' e x ∧ y ∈ R' .

Si noti che x ∨ y e x ∧ y sono il sup e l’inf di {x,y} calcolati in R.

Esempio

Consideriamo il reticolo L in figura

Il reticolo L' = L \ { c }

non è sottoreticolo di L, perché a ∧b = c non appartiene ad L'. Al contrario, L \ { d } è sottoreticolo di L; inoltre L' è un reticolo pur non essendo un sottoreticolo.

I reticoli liberi

Usando la definizione classica dell'algebra universale, un reticolo libero su un insieme S è un reticolo R con una funzione i : S → R, tale che ogni funzione f da S sull'insieme sottostante di un generico reticolo M può essere scomposta unicamente attraverso un omomorfismo f° tra reticoli da R su M. Diversamente, per ogni elemento s di S possiamo trovare gli elementi tali che f(s) = f°(i(s)) e f° è l'unico omomorfismo dei reticoli con questa proprietà. Queste condizioni ci inducono a dire che esiste una connessione tra la categoria degli insiemi e delle funzioni alla categoria dei reticoli e degli omomorfismi tra i reticoli.

Trattiamo il caso dei reticoli limitati, cioè strutture algebriche con le due operazioni binarie $\vee$ e $\wedge$ e le due costanti (operazioni nulle) 0 e 1. L'insieme di tutte le espressioni corrette (ben formate) che possono essere formulate usando queste operazioni sugli elementi da un dato insieme di generatori S sarà denominato da W(S). Questo insieme contiene molte espressioni che risultano essere uguali in ogni reticolo. Per esempio, se a è un elemento di S, allora a ∨ 1 = 1 e a ∧ 1 =a. Il problema per i reticoli è quali di questi elementi devono essere identificati.

La risposta a questo problema è la seguente. Definiamo una relazione <~ su W(S) scrivendo w <~ v se e solo se si verifica una delle seguenti condizioni:

• w = v (questa può limitarsi al caso in cui w e v sono elementi di S),
• w = 0 o v = 1,
• w = w1 ∨ w2 e (inclusivo) w1<~v e w2<~v ,
• w = w1 ∧ w2 e (esclusivo) w1<~v o w2<~v ,
• v = v1 ∨ v2 e (esclusivo) w<~v1 o w<~v2 ,
• v = v1 ∧ v2 e (inclusivo) w<~v1 e w<~v2 .

Questo definisce un preordine <~ su W(S). L'insieme parzialmente ordinato indotto da questo preordine (cioè l'insieme ottenuto identificando tutti gli elementi w e v con w<~v e v<~w) è il reticolo libero su S.

Una delle conseguenze di questa definizione è che il reticolo libero generato da un insieme di tre elementi è già infinito. Infatti, si può persino dimostrare che ogni reticolo libero generato da tre elementi contiene un sottoreticolo che è libero per un insieme generato da quattro elementi. Tramite induzione questa condizione rende un sottoreticolo numerabile libero su molti elementi generatori.

Il caso dei reticoli che non sono limitati è trattato similmente, usando soltanto le due operazioni binarie nella suddetta costruzione.

Importanti nozioni teoriche sui reticoli

Sia R un reticolo. Definiamo alcune nozioni teoriche di ordine che sono di particolare importanza nella teoria dei reticoli.

Un elemento x di R è detto superiormente irriducibile se e solo se

• x = a ∨ b implica x = a o x = b per ogni a, b in R,
• se R ha lo 0, a volte è richiesto ad x di essere diverso da 0.

Quando la prima condizione è generalizzata da una unione $\cup$a_i, x è detto completamente superiormente irriducibile. La definizione duale è detta inferiormente irriducibile. A volte si usano i termini ∪-irriducibile e ∩-irriducibile rispettivamente.

Un elemento x di R è detto superiormente primo se e solo se

• x ≤ a v b implica x ≤ a o x ≤ b,
• se R possiede lo 0, a volte è richiesto ad x di essere diverso da 0.

Analogamente, questa definizione si può generalizzare per ottenere la definizione completamente superiormente primo e la sua duale inferiormente primo. Ogni elemento superiormente primo è anche irriducibile superiormente. Se il reticolo è distributivo è vero anche il viceversa.

Altre nozioni importanti nella teoria dei reticoli sono gli ideali e la relativa nozione di filtro. Entrambi i termini descrivono i sottoinsiemi speciali di un reticolo (o in generale di qualsiasi insieme parzialmente ordinato).

Bibliografia

• Garrett Birkhoff (1967): Lattice Theory, 3rd edition, American Mathematical Society
• E. Mendelson (1973): Introduction to Boolean Algebra and Switching Circuits, McGraw-Hill
• S. N. Burris, H. P. Sankappanavar (1981): A Course in Universal Algebra, Springer. Ora anche disponibile liberamente in linea
• P. T. Johnstone (1982): Stone spaces, Cambridge University Press,
• B. A. Davey, H. A. Priestley (2002): Introduction to Lattices and Order. Cambridge University Press, ISBN 0-521-78451-4
• G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott (2003): Continuous Lattices and Domains, Cambridge University Press, ISBN 0-521-80338-1

Voci correlate

• 06-XX, sezione di livello 1 dello schema di classificazione MSC 2000

Altri progetti

Altri progetti

• Wikizionario
• Wikiversità
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «reticolo»
• Wikiversità contiene risorse su reticolo
• Wikimedia Commons contiene immagini o altri file su reticolo