Reticolo (matematica)

Inmatematica, unreticolo(latticein inglese) è uninsieme parzialmente ordinatoin cui ogni coppia di elementi ha sia unestremo inferiore(inf) che unestremo superiore(sup). I reticoli possono anche essere caratterizzati comestrutture algebricheche soddisfano determinateidentità. Poiché entrambe le definizioni possono essere usate convenientemente, la teoria dei reticoli può essere applicata sia dallateoria dell'ordineche dalla teoria dell'algebra universale. I reticoli costituiscono uno dei rappresentanti più significativi di strutture che ammettono ordine così come le strutture algebriche, quali isemireticoli, lealgebre di Heytingo lealgebre booleane. Il terminereticoloderiva dalla rappresentazione deidiagrammi di Hasse.
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.
Sia(R,≤){\displaystyle (R,\leq )}un insieme parzialmente ordinato. Diremo che(R,≤){\displaystyle (R,\leq )}è unreticolose per ognixeyelementi diR, ilsottoinsieme{x,y}{\displaystyle \{x,y\}}haestremo superioreedestremo inferioreinR.
Per ognix, yelementi diRsi denotax∨y=sup{x,y}{\displaystyle x\vee y=\mathrm {sup} \{x,y\}}ex∧y=inf{x,y}{\displaystyle x\wedge y=\mathrm {inf} \{x,y\}}.
Consideriamo una struttura algebrica(R,∨,∧){\displaystyle (R,\vee ,\wedge )}, dove∨{\displaystyle \vee }e∧{\displaystyle \wedge }sono dueoperazioni binariedefinite inR.Rè un reticolo se le seguentiidentitàvalgono per ogni elementoa,b,cinR:
Leggi commutative:
Leggi associative:
Leggi di assorbimento:
Dalle identità precedenti derivano le seguenti
Leggi di idempotenza:
Si noti che per le leggi diidempotenza, le leggicommutativeeassociativerappresentano 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 diinfesupnella suddetta definizione.
Un reticolo dotato di unarelazione d'ordinepossiede le dueoperazioni binarie∨{\displaystyle \vee }e∧{\displaystyle \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 unarelazione d'ordineparziale≤{\displaystyle \leq }suMconsiderando per ogni elementoxeyinM{\displaystyle {M}}
x≤y{\displaystyle x\leq y}se e solo sex=x∧y{\displaystyle x=x\wedge y}
o equivalentemente
x≤y{\displaystyle x\leq y}se e solo sey=x∨y{\displaystyle y=x\vee y}.
Dalle leggi di assorbimento si dimostra che entrambe le definizioni siano effettivamente equivalenti. Si può ora controllare che larelazione d'ordine≤{\displaystyle \leq }introdotta in questo modo definisce un ordinamento parziale in cui le operazioni disupeinfsono date dalle operazioni∨{\displaystyle \vee }e∧{\displaystyle \wedge }. Al contrario, larelazione d'ordineindotta dal reticolo definito algebricamente (R, ∨, ∧) coincide con l'ordinamento diR{\displaystyle {R}}in origine.
Quindi le due definizioni possono essere usate in senso interamente intercambiabile, secondo quale sia più conveniente usare per uno scopo preciso.
La definizione appropriata diomomorfismotra due reticoli può essere derivata facilmente dalla definizione algebrica seguente: dati due reticoli(R,∨,∧){\displaystyle (R,\vee ,\wedge )}e(M,∪,∩),{\displaystyle (M,\cup ,\cap ),}unomomorfismotra i reticoli è una funzionef:R→M{\displaystyle f:R\to M}che verifica le seguenti proprietà:
Se i reticoli sono dotati dell'elemento più piccolo0{\displaystyle 0}e dell'elemento più grande1,{\displaystyle 1,}allora laf{\displaystyle f}deve conservare anche questi elementi:
Nella formulazione teorica dell'ordine, la condizione corretta è che unomomorfismotra reticoli è una funzione che conserva le operazioni binarieinfesup.
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 degliisomorfismicome omomorfismi invertibili, si trova che un isomorfismo tra reticoli è esattamente un omomorfismo biiettivo tra i reticoli. I reticoli ed i loro omomorfismi formano ovviamente unacategoria.
Due reticoli isomorfi hanno lo stesso diagramma di Hasse.
Vi sono numerose proprietà importanti dei reticoli, introdotte in questo paragrafo, molte delle quali portano a considerarecategoriespeciali di reticoli.
La proprietà più immediata per un reticoloRè forse quella di esserelimitato. 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 reticoloRsi dicelimitatose possiede un massimo ed un minimo.
Lacategoriaaltamente rilevante è quella deireticoli completi. Un reticolo è completo se ogni suosottoinsiemeha sia l’infche ilsup. Questa definizione sembrerebbe contrapporsi alla definizione di reticolo in cui si richiede soltanto l'esistenza dell’info delsup(non vuoto). Risulta che dall'esistenza di tutti gliinfsi conclude l'esistenza di tutti isupe viceversa. Si noti inoltre che i reticoli completi sono sempre limitati. Esempi di reticoli completi sono:
Molti teoremi della teoria dell'ordine assumono forme semplici una volta dichiarati per i reticoli completi. Per esempio ilteorema di Knaster-Tarskidichiara che l'insieme deipunti fissidi una funzione monotòna su un reticolo completo è ancora un reticolo completo.
Poiché ogni reticolo possiede dueoperazioni binarie, è naturale considerare le relativeleggi distributive. Un reticolo (R, ∨, ∧) èdistributivose per ogni elementox,y,zinRvale
Sorprendentemente, forse, questa condizione finisce per essere equivalente a
Per i reticoli completi si possono formulare proprietà più forti ottenendo lecategoriedi 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.
Spesso si trova che la distributività è una condizione troppo forte per determinate applicazioni. Una proprietà rigorosamente più debole è la modularità: un reticolo (R, ∨, ∧) èmodularese per ogni elementox,y,zinRsi ha
Un'altra condizione equivalente è la seguente: sex≤zallora per ogniy
Per esempio, il reticolo dei sottomoduli di un modulo ed il reticolo deisottogruppi normalidi un gruppo hanno questa proprietà. Inoltre ogni grata distributiva è effettivamente modulare.
Nellateoria dei domini, si è spesso interessati all'approssimazione degli elementi di un reticolo dotato di un ordine parziale, tramite elementi "molto più semplici". Questo conduce allacategoriadei reticoli ordinati continui, consistente nei reticoli dotati di relazione d'ordine in cui ogni elemento può essere ottenuto comesupdi uninsieme direttodi 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:
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.
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 elementoxècomplementodell'elementoyse:
x∨y=1{\displaystyle x\vee y=1}ex∧y=0{\displaystyle 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 elementoxche può essere denotato così da ¬x.
In un reticolo complementato distributivo se un elemento ha un complemento, questo è unico.
Infatti se un elementoxavesse due complementi,yez
Lealgebre di Heytingsono esempi di reticoli limitati, all'interno dei quali i complementi solitamente non esistono. Tuttavia, ogni elementoxin un'algebra di Heyting ha unopseudo-complementoche solitamente è anche denotato da ¬x. È caratterizzato, essendo il più grande fra tutti gli elementiydalla proprietà
Se gli pseudo-complementi di un'algebra di Heyting sono in effetti complementi, allora si ha un'algebra booleana.
Sia (R, ∨, ∧) un reticolo, e sia (R', ≤)  un suosottoinsiemeordinato. AlloraR'si dicesottoreticolodiRse per ognix,y∈R'implicax∨y∈R'ex∧y∈R'.
Si noti chex∨yex∧ysono ilsupe l’infdi {x,y} calcolati inR.
Consideriamo il reticoloLin figura
Il reticoloL'=L\ {c}
non è sottoreticolo diL, perchéa∧b=cnon appartiene adL'.
Al contrario,L\ {d} è sottoreticolo diL; inoltreL'è un reticolo pur non essendo un sottoreticolo.
Usando la definizione classica dell'algebra universale, unreticolo liberosu un insiemeSè un reticoloRcon una funzionei:S→R, tale che ogni funzionefdaSsull'insieme sottostante di un generico reticoloMpuò essere scomposta unicamente attraverso un omomorfismof°tra reticoli daRsuM. Diversamente, per ogni elementosdiSpossiamo trovare gli elementi tali chef(s) =f°(i(s)) ef°è 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∨{\displaystyle \vee }e∧{\displaystyle \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 generatoriSsarà denominato daW(S). Questo insieme contiene molte espressioni che risultano essere uguali in ogni reticolo. Per esempio, seaè un elemento diS, alloraa∨ 1 = 1 ea∧ 1 =a. Il problema per i reticoli è quali di questi elementi devono essere identificati.
La risposta a questo problema è la seguente. Definiamo una relazione <~ suW(S) scrivendow<~vse e solo se si verifica una delle seguenti condizioni:
Questo definisce unpreordine<~ suW(S).  L'insieme parzialmente ordinato indotto da questo preordine (cioè l'insieme ottenuto identificando tutti gli elementiwevconw<~vev<~w) è il reticolo libero suS.
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. Tramiteinduzionequesta condizione rende un sottoreticolonumerabilelibero su molti elementi generatori.
Il caso dei reticoli che non sono limitati è trattato similmente, usando soltanto le due operazioni binarie nella suddetta costruzione.
SiaRun reticolo. Definiamo alcune nozioni teoriche di ordine che sono di particolare importanza nella teoria dei reticoli.
Un elementoxdiRè dettosuperiormente irriducibilese e solo se
Quando la prima condizione è generalizzata da una unione∪{\displaystyle \cup }ai,xè dettocompletamente superiormente irriducibile. La definizione duale è dettainferiormente irriducibile. A volte si usano i termini ∪-irriducibile e ∩-irriducibile rispettivamente.
Un elementoxdiRè dettosuperiormente primose e solo se
Analogamente, questa definizione si può generalizzare per ottenere la definizionecompletamente superiormente primoe la sua dualeinferiormente primo. Ogni elemento superiormente primo è anche irriducibile superiormente. Se il reticolo è distributivo è vero anche il viceversa.
Altre nozioni importanti nella teoria dei reticoli sono gliidealie la relativa nozione difiltro. Entrambi i termini descrivono i sottoinsiemi speciali di un reticolo (o in generale di qualsiasi insieme parzialmente ordinato).