Qualche esercizio sui reticoli

[perplesso1]

1) Devo disegnare il diagramma di questo insieme ${(i,j) \in NN xx NN | i < j}$ ordinato mediante la relazione

$(i,j) <= (i',j') <=> j <= i'$ oppure ( $i = i'$ e $j <= j'$ )

chiaramente non tutto il diagramma ma l'inizio... questo è il disegno che ho fatto:



è ok ?? grazie mille!

[hamming_burst]

Ciao,
a me sembra che alcune cose non funzionano
es. $(2,4) R (4,5)$ $(0,1) R (1,2)$

$4 < 4$ No
oppure
$2=4 \wedge 4<=5$ no

i legami trasversali destra-sinistra danno problemi, devi saltare un livello:

$(0,2) R (3,4)$
$(0,3) R (4,5)$

Quelli a livelli diagonali invece dovrebbero essere ok.

la relzione $(i=i' \wedge j<=j')$ ha un punto da chiarire, $j=j'$ mi pare non possa esser soddisfatto in alcun modo...o vedo male io?

Alla fine devi dimostrare esser un reticolo?

[perplesso1]

Sono un tonto! Avevo messo un $<$ al posto di $<=$ Ora ho corretto. Cmq si, dopo devo dimostrare che è un reticolo... lo farò appena possibile. Grazie mille!!

[hamming_burst]

in questo caso allora dovrebbe esser ok

[perplesso1]

Per dimostrare che è un reticolo dobbiamo far vedere che presa una coppia di elementi non confrontabili esistono l'estremo superiore ed inferiore, quindi

Siano $(a,b)$ e $(c,d)$ elementi non confrontabili e supponiamo $a
Dimostriamo che il loro estremo inferiore esiste ed è $(a,c)$. infatti da $c < b$ segue $(a,c) <= (a,b)$ e da $c <= c$ segue $(a,c) <= (c,d)$. Quindi $(a,c)$ è un minorante di $(a,b)$ e $(c,d)$. Facciamo vedere che è il più grande. Supponiamo

(*) $(m,n) <= (a,b)$
(**) $(m,n) <= (c,d)$

e distinguiamo 2 casi. Se $m = a$ allora da (**) segue $n <= c$ e quindi $(m,n) = (a,n) <= (a,c)$. Se invece $m \ne a$ da (*) segue che $n <= a$ e quindi $(m,n) <= (a,c)$. Pertanto $(a,b) ^^ (c,d) = (a,c)$.

Dimostriamo che il loro estremo superiore esiste. Sia $x = max {b,d}$, allora l'estremo superiore è $(x,x+1)$. Infatti da $a < b$ segue $a < x$ e inoltre risulta $b <= x$ per la scelta di $x$, quindi $(a,b) <= (x,x+1)$. Da $c < b$ segue $c < x$ e inoltre $d <= x$ per la scelta di $x$ quindi $(c,d) <= (x,x+1)$. Pertanto $(x,x+1)$ è un maggiorante di $(a,b)$ e $(c,d)$. Facciamo vedere che è il più piccolo. Supponiamo

(i) $(a,b) < = (m,n)$
(ii) $(c,d) <= (m,n)$

e distinguamo 3 casi. Se $a= m$ allora da (ii) otteniamo $d <= m = a$ impossibile perchè sappiamo che $a < d$. Se invece $m = c$ allora da (i) otteniamo $b <= m = c$ impossibile poichè abbiamo supposto $c < b$. Quindi concludiamo che $a \ne m \ne c$ e allora da (i) ricaviamo $b <= m$ e da (ii) ricaviamo $d <= m$, cioè $x= max {b,d} <= m$. Inoltre $x <=m x$ allora $x+1 <= m$ e quindi ancora $(x,x+1) <= (m,n)$. Pertanto $(a,b) vv (c,d) = (x,x+1)$.

Fine. Che ne pensate?

[perplesso1]

Poi l'esercizio mi chiede: dimostrare che per ogni $n >=3$ l'elemento $\bigwedge_{i=1}^n (a_i,b_i)$ si può esprimere come "meet" di al più 2 elementi $(a_i,b_i)$. Procediamo per induzione su $n$. Per $n = 3$ abbiamo $(a_1,b_1) ^^ (a_2,b_2) ^^ (a_3,b_3)$, se due di questi elementi sono confrontabili allora è tutto facile. Se invece sono a due a due non confrontabili, possiamo supporre senza ledere la generalità del ragionamento che $a_1 < a_3 < a_2$ . Quindi $(a_1,b_1) ^^ (a_2,b_2) ^^ (a_3,b_3) = (a_1,a_2) ^^ (a_3,b_3)$. Se $b_3 <= a_1$ allora $(a_3,b_3) <= (a_1,a_2)$ e $(a_1,a_2) ^^ (a_3,b_3) = (a_3,b_3)$. Se invece $b_3 > a_1$ allora $(a_1,a_2)$ e $(a_3,b_3)$ non sono confrontabili e quindi $(a_1,a_2) ^^ (a_3,b_3) = (a_1,a_3) = (a_1,b_1) ^^ (a_3,b_3)$. Ora facciamo il passo induttivo. Supponiamo che $\bigwedge_{i=1}^n (a_i,b_i) = (a_j,b_j) ^^ (a_k,j_k)$ allora $\bigwedge_{i=1}^{n+1} (a_i,b_i) = (a_j,b_j) ^^ (a_k,j_k) ^^ (a_{n+1},b_{n+1})$ e con ragionamenti analoghi a quelli del caso $n=3$ si conclude.

Spero che tutte queste disuguaglianze non vi facciano girare le palle... degli occhi!

[perplesso1]

2) Quali dei seguenti reticoli sono modulari / distributivi ??



Devo applicare il teorema $M_3-N_5$. Allora il primo reticolo contiene $N_5$ (pallini rossi) quindi non è distributivo ne modulare, il secondo invece è distributivo perchè è un sottoreticolo di $3 xx 3$ che è distributivo. Il terzo contiene sia $N_5$ (pallini rossi) che $M_3$ (pallini verdi) quindi non è distributivo nè modulare. Il quarto e il quinto contengono $M_3$ quindi non sono distributivi. Il sesto è distributivo perchè è un sottoreticolo di $3 xx 3 xx 2$.

Rimane da mostrare che il quarto e il quinto reticolo sono modulari. Per il quarto notiamo che se togliamo il punto centrale del sottoreticolo $M_3$ otteniamo il reticolo modulare $3 xx 3$, quindi se il reticolo 4 contiene $N_5$ questo pentagono deve contenere il punto centrale di $M_3$. Studiando il diagramma si vede che non c'è nessun sottoreticolo isomorfo a $N_5$ che contiene quel punto. Stesso discorso per il reticolo 5. Se togliamo il punto giallo otteniamo un reticolo modulare, quindi se 5 contiene un pentagono questo deve passare per il punto giallo, ma un facile studio del diagramma mostra che questo non avviene.

[perplesso1]

3) Trovare una coppia di reticoli $L$ e $K$ tali che:

(a) $L xx K$ contiene $20$ elementi
(b) $L$ non è distributivo
(c) $K$ ha alemno $3$ elementi
(d) il massimo di $L xx K$ copre esattamente $4$ elementi

La condizione (b) ci dice che $L$ deve contenere almeno $5$ elementi, quindi usando la (c) si ottiene subito che $|K| = 4$ e $|L| = 5$. Io ho trovato che ponendo $L= M_3$ e $K = 4$ (catena di quattro elementi) il reticolo $L xx K$ rispetta la condizione (d) e chiaramente non è distributivo perchè contiene $M_3$

[perplesso1]

4) trovare due reticoli $L$ e $K$ tali che

(a) $|L xx K| = 18$
(b) $L$ non è distributivo
(c) $K$ ha almeno 3 elementi
(d) $L xx K$ è modulare
(e) Il minimo di $L xx K$ è coperto esattamente da 4 elementi

Da (b) ricaviamo che $L$ ha almeno 5 elementi e usando (c) ci si convince che $|L|=6$ e $|K|=3$. Pertanto $K$ è una catena di 3 elementi che è modulare. Se troviamo un $L$ modulare il prodotto $L xx K$ sarà certamente modulare. Io ho scelto $L = M_3 + 2 $, in questo modo il prodotto $L xx K$



rispetta anche la condizione (e).

[perplesso1]

5) Sia $L$ un reticolo distributivo provare che per ogni $a,b,c \in L$ vale

(*) ($a ^^ b = c ^^ b$ e $a vv b = c vv b$) $=> a=c$

Mostrare che nei reticoli $M_3$ e $N_5$ vi sono tre elemwnti $a,b,c$ che non rispettano (*) e dedurre che un reticolo è distributivo se e solo se vale (*).


Basta fare un pò di calcoli

$a = a ^^ (a vv b) = a ^^ (c vv b) =$ $(a ^^ c) vv (a ^^ b) = (a ^^ c) vv (c ^^ b)$ $= (a vv c) ^^ (c vv c) ^^ (a vv b) ^^ (c vv b) =$ $(a vv c) ^^ c ^^ (a vv b) ^^ (c vv b) =$ $c ^^ (a vv b) ^^ (c vv b) = c ^^ (c vv b) ^^ (c vv b) = c ^^ (c vv b) = c$

nei vari passaggi ho usato le proprietà: assorbimento, ipotesi, distributività, ipotesi, distributività, idempotenza, assorbimento, ipotesi, idempotenza, assorbimento.

La situazione in $M_3$ e $N_5$ è questa



il resto segue dal teorema $N_5-M_3$

[perplesso1]

Sia $L$ un reticolo. Un ideale $J$ in $L$ è un sottoinsieme tale che

i) se $a, b \in J$ allora $a vv b \in J$
ii) se $y \in J$ e $x <= y$ allora $x \in J$

Un filtro $G$ in $L$ invece si definisce in maniera duale

i) se $a, b \in G$ allora $a ^^ b \in G$
ii) se $y \in G$ e $x >= y$ allora $x \in G$

Esercizio
5) Sia $L$ un reticolo, $J$ un ideale e $G$ un filtro tali che $L=J \cup G$ e inoltre $J \cap G \ne \emptyset$. Mostrare che:

(a) Se $L$ ha $M_3$ come sottoreticolo allora $M_3 \subset J$ oppure $M_3 \subset G$
(b) Se $x \in J$ e $y \in G$ e inoltre $x <= y$ allora esiste $z \in J \cap G$ tale che $x <= z <= y$
(c) se $L$ ha $N_5$ come sottoreticolo allora $N_5 \subset J$ oppure $N_5 \subset G$


Svolgimento
Facendo riferimento alla figura del post precedente

(a) Consideriamo l'anticatena ${a,b,c}$. Uno fra $J$ e $G$ deve contenere almeno due di questi elementi. Diciamo per esempio $a$ e $b$.

Se $a,b \in J => 1=a vv b \in J => c,0 \in J => M_3 \subset J$

Se $a,b \in G => 0 = a ^^ b \in G => c,1 \in G => M_3 \subset G$


(b) Scegliamo $w \in J \cap G$ e poniamo $z = x vv (y ^^ w)$

$y ^^ w \in G$ perchè è chiuso rispetto a $^^$. Inoltre $x vv (y ^^ w) >= y ^^ w => x vv (y ^^ w) \in G$

$y ^^ w <= w$ quindi $y ^^ w \in J => x vv (y ^^ w) \in J$ perchè $J$ è chiuso rispetto a $vv$

quindi $z = x vv (y ^^ w) \in J \cap G$. Ci resta da provare che $x <= z <= y$. La disuguaglianza $x<=z$ è ovvia. Per ottenere $z <= y$ basta notare che $y vv (x vv (y ^^ w )) = x vv (y vv (y ^^ w)) = x vv y = y$.


(c) Procediamo per casi (queste mie affermazioni non mi convincono, suggerimenti sono graditi...)

Se $0 \in G$ allora $N_5 \subset G$
Se $1 \in J$ allora $N_5 \subset J$

Supponiamo quindi $0 \in J$ e $1 \in G$. Per quanto detto nel punto precedente deve esistere $z \in J \cap G$ tale che $0 <= z <= 1$.

Se $z = 0$ oppure $z=1$ si torna ai casi precedenti

Se $z = a$ allora $1,c \in G$. Se $b \in G$ allora $a ^^ b = 0 \in G$ quindi $N_5 \subset G$, se invece $b \notin G$ esiste $w \in J \cap G$ tale che $b <= w <= 1$. Se $w = b$ allora $b \in G$ assurdo, quindi $w=1 => 1 \in J => N_5 \subset J$.

Se $z = c$ allora $0,a \in J$. Se $b \in J$ allora $c vv b = 1 \in J$ quindi $N_5 \subset J$, se invece $b \notin J$ esiste $w \in J \cap G$ tale che $0 <= w <= b$. Se $w = b$ allora $b \in J$ assurdo, quindi $w=0 => 0 \in G => N_5 \subset G$.

Sia $z = b$. Se $a \in G => a ^^ b = 0 \in G => N_5 \subset G$, se invece $a \in J => a vv b = 1 \in J => N_5 \in J$

Se $z \ne a,b,c$ basta riposizionare opportunamente i punti $a,b,c$ per ottenere un pentagono adatto allo scopo.

[perplesso1]

6) Per quali interi positivi $n$ il reticolo $M_n$ è isomorfo al reticolo dei sottogruppi di un gruppo abeliano ?



Se $p$ è un numero primo il gruppo abeliano $ZZ_p xx ZZ_p$ contiene esattamente $p+1$ sottogruppi distinti di ordine $p$ oltre ai sottogruppi banali, quindi il reticolo dei suoi sottogruppi è isomorfo a $M_{p+1}$ e quindi tutti gli interi $n=p+1$ con $p$ primo sono adatti allo scopo. Ce ne sono altri ??