Lezione 25 (12 maggio 1999 h. 9.30-10.30)

Reticoli come insiemi con operazioni

Abbiamo visto in precedenza che se $(L,\le)$ è un reticolo, allora sono definite le due operazioni binarie $\vee, \wedge:L\times L\to L$ che verificano le proprietà commutativa, associativa e di assorbimento. Vediamo come tali proprietà delle due operazioni determinino la struttura del reticolo.

Teorema 25.1   Sia L un insieme su cui sono definite due operazioni binarie $\vee, \wedge:L\times L\to L$ tali che per ogni $x,y,z\in L$ si abbia:

1.	$x \vee y = y \vee x$		$x \wedge y = y \wedge x$
2.	$(x \vee y)\vee z=x\vee(y\vee z)$		$(x\wedge y)\wedge z =x\wedge(y\wedge z)$
3.	$x\vee(x\wedge y)=x$		$x\wedge(x\vee y)=x$

Allora esiste un ordinamento $\le$ su L che rende $(L,\le)$ un reticolo tale che per ogni $x,y\in L$ si ha che $\sup_\le\{x,y\}=x\vee y$ e $\inf_\le\{x,y\}=x\vee y$.

Dim.  L'esercizio 24.1 ci dice come definire la relazione d'ordine. Definiamo:

$$x\le y \iff x = x\wedge y.$$

Proviamo che $\le$ è una relazione d'equivalenza.

$\le$ è riflessiva. Usando la proprietà di assorbimento si ha che $x = x \vee(x \wedge x)$ e quindi $x \wedge x =x \wedge( x \vee(x \wedge x))$. Ma allora usando ancora la proprietà di assorbimento $x \wedge( x \vee (x \wedge x))= x$ e quindi $x\wedge x = x$ ossia $x \le x$.

$\le$ è antisimmetrica. Siano $x\le y$ e $y\le x$, ossia $x\wedge y = x$ e $y \wedge x = x$. Per la commutatività si ha allora che $x \wedge y = y \wedge x$ e quindi x=y.

$\le$ è transitiva. Sia $x\le y$ e $y \le z$ ossia $x\wedge y = x$ e $y \wedge z = y$. Allora, usando l'associatività, $x=x\wedge y =x \wedge (y\wedge z)= (x\wedge y)\wedge z=x \wedge z$ e quindi $x \le z$.

Proviamo ora che $x \wedge y$ è l'estremo inferiore tra x e y. Usando la commutatività, l'associatività ed il già provato fatto che per ogni $x\in L$ si ha $x\wedge x = x$, si ha

$$\begin{array}{lcl} (x\wedge y)\wedge x = x \wedge(x \wedge y... ...=x\wedge y &\hbox{\rm {ossia }} & x \wedge y \le y \end{array}$$

Sia ora $z \le x$ e $z \le y$, ossia $z\wedge x=z$ e $z\wedge y=z$, allora

$$z\wedge(x\wedge y)=(z\wedge x)\wedge y= =z\wedge y =z \quad\hbox{\rm {ossia}}\quad z\le x\wedge y.$$

$x \wedge y$ verifica quindi le proprietà caratterizzanti dell'estremo inferiore, e quindi è l'estremo inferiore.

Proviamo ora che $x\vee y$ è l'estremo superiore tra x e y. Usando le proprietà commutative e di assorbimento, si ha

$$\begin{array}{lcl} (x\vee y)\wedge x = x \vee(x \wedge y)=x ... ...y \vee x)= y &\hbox{\rm {ossia }} & y \le x \vee y \end{array}$$

Sia ora $x \le z$ e $y \le z$ ossia $x\wedge z = x$ e $y \wedge z = y$. Allora, usando le proprietà di assorbimento e la commutatività, si ha che da $x\wedge z = x$ si ha che $z=(x\wedge z)\vee z= x \vee z$ e, analogamente, $z=y \vee z$, ma allora, usando queste relazioni, l'associatività e la proprietà di assorbimento, si ha

$$\begin{array}{lcl} (x\vee y)\wedge z = (x\vee y)\wedge(x\vee ... ...e z))= (x\vee y) &\hbox{\rm {ossia}} &x\vee y \le z \end{array}$$

Questo, prova che $x\vee y$ è l'estremo superiore tra x e y.

Si poteva anche osservare che dalle tre proprietà si ricava che $x=x\wedge y\iff y=x\vee y$ (si veda l'esercizio seguente), ossia $x\le y$ se e solo se $y=x\vee y$. L'ultima proprietà poteva più semplicemente essere mostrata nel seguente modo: se $x \le z$ e $y \le z$ allora $z=x\vee z$e $z=y \vee z$, ma allora

$$(x\vee y)\vee z =x\vee(y\vee z)=x\vee z= z \quad\hbox{\rm {ossia}}\quad x\vee y\le z.$$

    $\square$

Osservazione 25.2   La proposizione 24.7 ed il teorema precedente mostrano che è completamente equivalente definire un reticolo in termini di ordinamento oppure definirlo come insieme dotato di due operazioni commutative, associative e che verificano la proprietà di assorbimento. Le due strutture algebrica (data dalle proprietà delle operazioni) e d'ordine sono due facce della stessa medaglia e che possono quindi essere usate indifferentemente a seconda delle necessità.

Esercizio 25.1      Si dimostri usando soltanto le proprietà commutativa, associativa e di assorbimento delle due operazioni, che in un reticolo $x\vee y=y\iff x\wedge y =x$.
Soluzione

Definizione di complemento

Definizione 25.3   Sia L un reticolo diremo che L è limitato se ha massimo e minimo, che saranno denotati rispettivamente con 0 e 1. Ossia, nel linguaggio dell'ordinamento

$$\exists 0,1\in L : x\le 1\hbox{\rm { e }} 0\le x \quad \forall x\in L$$

o, equivalentemente, nel linguaggio algebrico

$$\exists 0,1\in L : x\wedge1 = x \hbox{\rm { e }} x \wedge0 = 0 \quad \forall x\in L$$

che, in virtù di quanto visto nell'esercizio 24.1, equivale a dire

$$\exists 0,1\in L : x\vee1 = 1 \hbox{\rm { e }} x \vee0 = x \quad \forall x\in L.$$

Se L è un reticolo limitato, diremo che $x'\in L$ è un complemento di x se:

$$x\vee x' =1\qquad x\wedge x' = 0.$$

Un reticolo limitato in cui ogni elemento ha un complemento di dice complementato

Osservazione 25.4   Rispetto alla struttura algebrica, lo 0 è elemento neutro per $\vee$ mentre 1 è un elemento neutro per $\wedge$.

Definizione di reticolo distributivo

Definizione 25.5   Diremo che un reticolo L è distributivo se valgono le seguenti:

$$\begin{eqnarray*}x\vee(y\wedge z)=(x\vee y) \wedge(x \vee z) \quad \forall x,y\i... ...e(y\vee z)=(x\wedge y) \vee(x \wedge z) \quad \forall x,y\in L \end{eqnarray*}$$

Esercizio 25.2      Sia L un reticolo. Si provi che le due proposizioni

1.

$x\vee(y\wedge z)=(x\vee y) \wedge(x \vee z) \quad \forall x,y\in L$

2.

$x\wedge(y\vee z)=(x\wedge y) \vee(x \wedge z) \quad \forall x,y\in L$

sono equivalenti. In altri termini, nella definizione che abbiamo dato una delle due richieste è superflua, e quindi per verificare che un reticolo è distributivo è sufficiente mostrarne una delle due.
Soluzione

Proposizione 25.6   Sia L un reticolo distributivo e limitato. Se $x\in L$ ha un complemento, allora tale complemento è unico.

Dim.  Supponiamo che x₁ e x₂ siano due complementi di x, allora

$$x_1=x_1\wedge1 =x_1\wedge(x\vee x_2) = (x_1\wedge x)\vee(x_1\wedge x_2) = 0\vee (x_1\wedge x_2)=(x_1\wedge x_2)$$

scambiando x₁ con x₂ si ottiene anche $x_2=x_2\wedge x_1$ e quindi, x₁=x₂.     $\square$

Osservazione 25.7   La distributività è essenziale per l'unicità del complemento. Si prenda ad esempio il reticolo schemattizzato dal seguente diagramma:

intendendo con questo che $0\le x$ e $x \le 1$ per ogni x e che a,b,c non sono tra loro confrontabili. Allora chiaramente sia b che c sono dei complementi per a ed infatti il reticolo non è distributivo:

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

mentre

$$( a \vee b)\wedge(a \vee c) = 1 \wedge1 =1.$$

Definizione di algebra di Boole

Definizione 25.8   Un reticolo distributivo, e complementato viene chiamato un'algebra di Boole.

Esempio 25.9   Se X è un insieme il reticolo ${\cal P}(X)$ delle sue parti è un'algebra di Boole. Valgono infatti le relazioni di distributività ed il complemento di un $A\in {\cal P}(X)$ non è altro che il suo complementare insiemistico $\complement A=X\setminus A$.

Gli anelli booleani sono algebre di Boole

Teorema 25.10   Sia R un anello booleano allora R, con la sua struttura di reticolo è un'algebra di Boole.

Dim.  Dobbiamo dimostrare che R è limitato, complementato e distributivo. Ricordiamo che la struttura di reticolo di Rè data dll'ordinamento parziale $a\le b\iff ab=a$ per la quale si ha $a\vee b= a+b+ab$ e $a\wedge b = ab$.

Osserviamo che $a \wedge0 =a0=o0$ per ogni $a\in R$ e quindi lo 0 dell'anello è anche lo 0 del reticolo.

Se $a\in R$ allora $a\wedge1 = a 1 =a$ e quindi l'1 dell'anello è anche l'1 del reticolo.

Se $a\in R$ allora

$$\begin{eqnarray*}a \wedge(1+a) &=& a (1+a)=a+a^2=a+a=0 \\ a\vee(1+a)&=& a +(1+a) +a(1+a) = \\ & = & a + 1 + a + a + a^2 = 1+ a+a+a+a =1. \end{eqnarray*}$$

quindi (1+a) è un complemento di a.

Proviamo che è distributivo.

$$\begin{eqnarray*}a\vee(b\wedge c) & = & a\vee(bc) = a+bc+a(bc) = a+bc+abc \\ [5p... ...bc= \\ & = & a+ac+ac+ab+bc+abc+ab+abc+abc= \\ & = & a+bc+abc \end{eqnarray*}$$

e quindi $a\vee(b\wedge c)=(a\vee b)\wedge(a \vee c)$. Per quanto detto nell'esercizio 25.2, possiamo allora affermare che il reticolo è distributivo.     $\square$