Reticolo (matematica)

Da Wikipedia, l'enciclopedia libera.

In matematica, un reticolo è un insieme parzialmente ordinato in cui tutti i sottoinsiemi limitati non vuoti ammettono sia un estremo inferiore (inf) sia 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 degli schemi di Hasse.

Questo articolo tratta le definizioni più importanti della teoria dei reticoli.

Indice

1 Definizione formale
2 I reticoli come insiemi parzialmente ordinati
3 I reticoli come strutture algebriche
4 L'equivalenza fra entrambe le definizioni
5 Esempi
6 Omomorfismi tra reticoli
7 Le proprietà dei reticoli
8 Sottoreticolo
- 8.1 Esempio
9 I reticoli liberi
10 Importanti nozioni teoriche sui reticoli
11 Voci correlate

[modifica] 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.

[modifica] 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, l'insieme { x, y } ha estremo superiore ed estremo inferiore.

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

Se entrambi gli elementi esistono, il reticolo si dice limitato.

Usando una facile dimostrazione per induzione, si può anche concludere l'esistenza dell'estremo superiore e dell'estremo inferiore per tutti i sottoinsiemi limitati non vuoti di un reticolo.

Ulteriori conclusioni possono essere possibili in presenza di altre proprietà .

[modifica] I reticoli come strutture algebriche

Consideriamo una struttura algebrica nel senso più generale dell'algebra, data da ( $R$ , $\vee$ , $\wedge$ ), dove $\vee$ e $\wedge$ sono le due operazioni binarie. $R$ è un reticolo se le seguenti identità valgono per ogni elemento a, b, c in $R$

Leggi di idempotenza:

$a \vee a = a$

$a \wedge a = a$

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$

Si noti che per le leggi di idempotenza,le leggi commutative e associative rappresentano la condizione perché ( $R$ , $\vee$ ) e ( $R$ , $\wedge$ ) costituiscano due semireticoli, mentre le leggi di assorbimento garantiscono che le due strutture interagiscano correttamente. Inoltre, risulta che le leggi di idempotenza possono essere dedotte dalle leggi di assorbimento e così non devono essere esplicitate separatamente.

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.

[modifica] L'equivalenza fra entrambe le 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$ , $\vee$ , $\wedge$ ) in senso algebrico. Forse,più sorprendentemente, si può anche ottenere l'inverso di questo risultato: si consideri ogni reticolo definito algebricamente ( $M$ , $\vee$ , $\wedge$ ). Si può definire una relazione d'ordine parziale $\leq$ su $M$ considerando per ogni elemento x e y in $M$

$x \leq y$ sse $x = x \wedge y$

o equivalentemente

$x \leq y$ sse $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$ , $\vee$ , $\wedge$ ) 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.

[modifica] Esempi

Per ogni insieme A, l'insieme di tutti i suoi sottoinsiemi limitati ( compreso l'insieme vuoto) possono essere ordinati 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.
Tutto il 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 gli schemi di Hasse di tutti i possibili reticoli con al più cinque elementi.

[modifica] 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 → M che verifica le seguenti proprietà:

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

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

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

f(0) = 0, e 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.

[modifica] Le proprietà dei reticoli

Le definizioni soprastanti hanno introdotto la condizione semplice di un reticolo perché sia limitato. Vi sono numerose altre proprietà importanti, che saranno introdotte adesso, molte delle quali portano a considerare categorie speciali di reticoli.

[modifica] 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, 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 dal guscio convesso dell'unione.
Le topologie su un insieme, ordinate tramite la relazione di inclusione. 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).

[modifica] Distributività

Poiché ogni reticolo possiede due operazioni binarie, è naturale considerare le relative leggi distributive. Un reticolo (R, $\vee$ , $\wedge$ ) è 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 termina 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.

[modifica] Modularità

Spesso si trova che la distributività è una condizione troppo forte per determinate applicazioni. Una proprietà rigorosamente più debole è la modularità: un reticolo (R, $\vee$ , $\wedge$ ) è 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.

[modifica] 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.

Entrambi 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.

[modifica] 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∨0 = y∨(x∧z) = (y∨x)∧(y∨z) = (z∨x)∧(y∨z) = z∨(x∧y) = z∨0 = z

Al contrario, le algebre di Heyting sono esempi più generali di reticoli, 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.

[modifica] Sottoreticolo

Sia ( $R$ , $\leq$ ) un reticolo, e sia ( $R'$ , $\leq$ ) un suo sottoinsieme ordinato. Allora R' si dice sottoreticolo di R se x, y $\in$ R'' implica x $\vee$ y $\in$ R e x $\wedge$ y $\in$ R.

Si noti che x $\vee$ y e x $\wedge$ y sono il sup e l'inf di { x, y }calcolati in R.

[modifica] Esempio

Consideriamo il reticolo L in figura

Il reticolo L' = L - { c }

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

[modifica] 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 $\vee$ 1 = 1 e a $\wedge$ 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 sse 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 $\vee$ w2 e (inclusivo) w1<~v e w2<~v ,
w = w1 $\wedge$ w2 e (esclusivo) w1<~v o w2<~v ,
v = v1 $\vee$ v2 e (esclusivo) w<~v1 o w<~v2 ,
v = v1 $\wedge$ 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.

[modifica] 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 sse

x = a $\vee$ 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 $\cup$ -irriducibile e $\cap$ -irriducibile rispettivamente.

Un elemento x di R è detto superiormente primo sse

x ≤ a v b implica x ≤ a o x ≤ b,
if 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 ).

[modifica] Voci correlate

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

Estratto da "http://it.wikipedia.org../../../r/e/t/Reticolo_%28matematica%29.html"

Categorie: Teoria degli ordini | Teoria dei reticoli