Cos' un reticolo

Un reticolo è un insieme parzialmente ordinato A in cui gli elementi, presi a coppia di due (x,y), formano un sottoinsieme B con un estremo inferiore e superiore.
la formula del reticolo in algebra

Dove

  • L'estremo inferiore è il massimo dei minoranti del sottoinsieme B.

    E' detto intersezione e si indica con $$ x ∧ y \:\: = \:\: inf(x,y) $$

  • L'estremo superiore è il minimo dei maggioranti del sottoinsieme B.

    E' detto unione e si indica con $$ x ∨ y \:\: = \:\: sup(x,y) $$

Un esempio di reticolo

In questa figura ho disegnato due insiemi parzialmente ordinati (A,≥).

Uno è un reticolo e l'altro no.

differenza tra reticolo e insieme parzialmente ordinato

Nel primo insieme parzialmente ordinato mancano le relazioni inf() e sup() tra le coppie di elementi (2,3) e (2,4).

Nel secondo insieme, invece, tutte le coppie del prodotto cartesiano dei due insiemi hanno una relazione di inferiorità e superiorità.

Il secondo insieme è un reticolo.

Altri esempi pratici di reticoli

esempi di reticoli

Il reticolo algebrico

Il reticolo algebrico (L,∧,∨) è un reticolo in cui sono definite due operazioni binarie ∧ e ∨ dette, rispettivamente, intersezione ( moltiplicazione ) e unione ( addizione ).

In un reticolo sono definite due operazioni con i simboli

  • ∧ detta "e" ( and o congiunzione )
  • ∨ detta "o" ( or o disgiunzione )

Le operazioni del reticolo devono sempre soddisfare queste proprietà per ogni coppia di elementi (x,y) dell'insieme parzialmente ordinato.

  • commutatività

    $$ x ∧ y = y ∧ x $$ $$ x ∨ y = y ∨ x $$

  • associatività

    $$ x ∧ ( y ∧ z ) =( x ∧ y ) ∧ z $$ $$ x ∨ ( y ∨ z ) = ( y ∨ x ) ∨ z $$

  • assorbimento

    $$ x ∧ ( x ∨ y ) =x $$ $$ x ∨ ( x ∧ y ) = x $$

  • idempotenza

    $$ x ∧ x =x $$ $$ x ∨ x = x $$

Nota. Le prime due proprietà sono comuni nella matematica. Le ultime due, invece, sono peculiari dei reticoli. Inoltre, nei reticoli manca la proprietà distributiva.

Esempio

Definisco un insieme composto soltanto da due parti a e b.

$$ L = \{ a , b \} $$

Dal punto di vista grafico

un esempio di insieme

Le operazioni sono:

  • ∧ = ⋂ ( intersezione )
  • ∨ = ∪ ( unione )

Devo capire se l'insieme (L,⊆) è un reticolo.

Per farlo devo verificare se soddisfa le quattro leggi dei reticoli.

Commutatività

Dati due elementi a e b

$$ a ∪ b = b ∪ a $$

$$ a \cap b = b \cap a $$

Entrambe le proprietà sono soddisfatte.

Associatività

Dati tre elementi a, b, c

$$ a ∪ ( b ∪ c ) = ( a ∪ b ) ∪ c $$

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

Entrambe le proprietà sono soddisfatte.

Assorbimento

Dati due elementI

$$ a ∪ ( a \cap b ) = a $$

$$ a \cap ( a ∪ b ) = a $$

Entrambe le proprietà sono soddisfatte.

Idempotenza

Dato un elemento qualsiasi

$$ a ∪ a = a $$

$$ a \cap a = a $$

Entrambe le proprietà sono soddisfatte.

Tutte le proprietà sono soddisfatte.

Pertanto, l'insieme delle parti è un reticolo.

Come capire se un insieme parzialmente ordinato è un reticolo

Per capire se un insieme parzialmente ordinato è un reticolo, devo verificare se l'insieme (A,r) soddisfa le proprietà dei reticoli.

Esempio 1

Ho un insieme A e una relazione di divisibilità indicata con il simbolo |

$$ ( A=\{1,2,3,4,5,6,7,12 \} , | ) $$

Le operazioni sono due

  • ∧ = MCD ( Massimo Comune Divisore )
  • ∨ = mcm ( minimo comune multiplo )

Devo verificare se l'insieme parzialmente ordinato (A,|) è un reticolo oppure no.

Dati due elementi qualsiasi (a,b) è un reticolo se esiste sempre un estremo inferiore e superiore appartenente ad A.

$$ \forall (a,b) \rightarrow \inf(a,b) $$

$$ \forall (a,b) \rightarrow \sup(a,b) $$

Prendo due elementi qualsiasi (4,6)

$$ 4∧6 = MCD(4,6) = 2 \in A $$

$$ 4∨6 = mcm(4,6) = 12 \in A $$

Entrambi i rusultati appartengono all'insieme.

Prendo altri due elementi (2,5)

$$ 2∧5 = MCD(2,5) = 1 \in A $$

$$ 2∨5 = mcm(2,5) = 10 \notin A $$

In questo caso l'estremo superiore sup(2,5)=10 non è compreso nell'insieme A.

Pertanto, l'insieme (A,|) non è un reticolo.

Esempio 2

Ho un insieme A e una relazione di divisibilità indicata con il simbolo |

$$ ( A=\{1,2,3,6,12 \} , | ) $$

Le operazioni sono due

  • ∧ = MCD ( Massimo Comune Divisore )
  • ∨ = mcm ( minimo comune multiplo )

In questo caso si tratta di un reticolo.

Tutte le coppie soddisfano le relazioni x∧y e x∨y.

( x , y ) MCD mcm
( 1 , 2 ) 1 2
( 1 , 3 ) 1 3
( 1 , 6 ) 1 6
( 1 , 12 ) 1 12
( 2 , 3 ) 1 6
( 2 , 6 ) 2 6
( 2 , 12 ) 2 12
( 3 , 6 ) 3 6
( 3 , 12 ) 3 12

Esempio 3

Aggiungo un elemento (9) all'insieme precedente

$$ ( A=\{1,2,3,9,6,12 \} , | ) $$

In questo caso non è più un reticolo perché manca l'estremo sup(2,9)=18.

Il numero 18 non fa parte dell'insieme A.

( x , y ) MCD mcm
( 1 , 2 ) 1 2
( 1 , 3 ) 1 3
( 1 , 9 ) 1 9
( 1 , 6 ) 1 6
( 1 , 12 ) 1 12
( 2 , 3 ) 1 6
( 2 , 9 ) 1 18
( 2 , 6 ) 2 6
( 2 , 12 ) 2 12
( 3 , 9 ) 3 9
( 3 , 6 ) 3 6
( 3 , 12 ) 3 12

Esempio 4

Aggiungo anche gli elementi 18 e 36 all'insieme precedente

$$ ( A=\{1,2,3,9,6,12, 18, 36 \} , | ) $$

Ora l'insieme è di nuovo un reticolo.

( x , y ) MCD mcm
( 1 , 2 ) 1 2
( 1 , 3 ) 1 3
( 1 , 6 ) 1 6
( 1 , 9 ) 1 9
( 1 , 12 ) 1 12
( 1 , 18 ) 1 18
( 1 , 36 ) 1 36
( 2 , 3 ) 1 6
( 2 , 6 ) 2 6
( 2 , 9 ) 1 18
( 2 , 12 ) 2 12
( 2 , 18 ) 2 18
( 2 , 36 ) 2 36
( 3 , 6 ) 3 6
( 3 , 9 ) 3 9
( 3 , 12 ) 3 12
( 3 , 18 ) 3 18
( 3 , 36 ) 3 36
( 6 , 9 ) 3 18
( 6 , 12 ) 6 12
( 6 , 18 ) 6 18
( 6 , 36 ) 6 36
( 9 , 12 ) 3 36
( 9 , 18 ) 9 18
( 9 , 36 ) 9 36
( 12 , 18 ) 6 36
( 12 , 36 ) 12 36
( 18 , 36 ) 18 36

Il sottoreticolo

Un sottoreticolo è un sottoinsieme L' del reticolo L(A,≥) se per ogni coppia x,y ∈ L' , le operazioni x∧y e x∨y fanno parte del reticolo L. $$ \forall x,y \in L' \rightarrow x ∧ y \in L , x ∧ y \in L $$

Esempio

esempi di sottoreticoli

Esempio

Ho tre insiemi parzialmente ordinati

$$ A={a,b,c,d,e,f} $$

$$ B={a,c,d,f} $$

$$ C={b,c,d,e} $$

Il diagramma di Hasse degli insiemi è

i diagrammi di Hasse

Il sottoinsieme B non è un sottoreticolo di A perché l'estremo inferiore inf(c,d) di B è diverso da inf(c,d) di A

$$ A] \:\: c ∧ d = b $$

$$ B] \:\: c ∧ d = a $$

Pertanto, il sottoinsieme B non è un sottoreticolo di A.

Nota. Pur non essendo un sottoreticolo di A, l'insieme B è comunque un reticolo perché per qualsiasi coppia di elementi esiste un estremo inferiore e superiore.

Il sottoinsieme C è invece un sottoreticolo di A perché tutti gli estremi inferiori e superiori di C coincidono con A.

Omomorfismo e isomorfismo di reticoli

Un omomorfismo di reticoli è un'applicazione A che lega un reticolo (L,≤) a un altro reticolo (L',≤). $$ A: L \rightarrow L' $$ tale che per ogni coppia x,y di L $$ A(x∧y)=A(x)∧A(y) \\ A(x∨y)=A(x)∨A(y) $$

Un esempio pratico di omomorfismo

Ho un'applicazione A che calcola la potenza.

$$ A: x \in L \rightarrow x^2 \in L' $$

Pertanto, se il reticolo L è il seguente

$$ ( A=\{1,2,3,6,12 \} , | ) $$

Nota. So già che si tratta di un reticolo dagli esempi precedenti.

L'applicazione A crea un secondo reticolo L' con la potenza degli elementi del primo

$$ ( A=\{1,4,9,36,144 \} , | ) $$

Tra il reticolo L e L' c'è una relazione.

un esempio di omomorfismo

Ovviamente, non è detto che la relazione crei un altro reticolo.

Devo verificare che L' sia effettivamente un reticolo.

( x , y ) x∧y x∨y
( 1 , 4 ) 1 4
( 1 , 9 ) 1 9
( 1 , 36 ) 1 36
( 1 , 144 ) 1 144
( 4 , 9 ) 1 36
( 4 , 36 ) 4 36
( 4 , 144 ) 4 144
( 9 , 36 ) 9 36
( 9 , 144 ) 9 144
( 36 , 144 ) 36 144

Per ogni elemento (x,y) esiste un estremo inferiore (x∧y) e superiore (x∨y) di L'.

Quindi L' è un reticolo e l'applicazione A è un omomorfismo.

Un isomorfismo di reticoli è un omomorfismo biettivo $$ A: L \rightarrow L' $$ $$ A^{-1}: L' \rightarrow L $$

Un esempio di isomorfismo di reticoli

L'applicazione precedente calcola la potenza degli elementi

$$ A: x \in L \rightarrow x^2 \in L' $$

So già che L e L' sono reticoli.

Posso fare l'applicazione inversa A-1 usando la radice quadrata.

$$ A^{-1}: x \in L' \rightarrow \sqrt{x} \in L $$

Quindi l'applicazione è anche biettiva oltre a essere un omomorfismo.

esempio di isomorfismo

Si tratta pertanto di un isomorfismo.

E così via.

 


 

Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base

Reticoli