(b) Determinare tutti gli elementi ∨–irriducibili del reticolo L

(1)

MATEMATICA DISCRETA CdL in Informatica prof. Fabio GAVARINI

a.a. 2017–2018 — Esame scritto del 20 Giugno 2018 — Sessione Estiva, I appello Testo & Svolgimento

N.B.: compilare il compito in modo sintetico ma esauriente, spiegando chiaramente quanto si fa, e scrivendo in corsivo con grafia leggibile.

· · · ? · · · ·

[1] Si consideri il reticolo L := {a , b , c , d , e , f , g , h , k , m , n , v , w , x , y , z } descritto dal seguente diagramma di Hasse:

a

b

77

d

OO

c

gg

e

@@

g

^^

h

@@

f

^^

k

^^ @@

m

__ OO ??

n

^^ @@

v

@@

w

__ >>

x

__ ??

y

__

z

jj `` >> 44

(a) Determinare tutti gli atomi del reticolo L ; .

(b) Determinare tutti gli elementi ∨–irriducibili del reticolo L ; .

(c) Per ciascuno dei due elementi a , c e g in L , determinare se esista una ∨–fattorizzazione non ridondante in fattori ∨–irriducibili per tale elemento. Nel caso in cui una tale

∨–fattorizzazione non esista, se ne spieghi il perch´e; nel caso in cui ne esista almeno una, si determinino tutte (a meno dell’ordine dei fattori) le ∨–fattorizzazioni di tal genere.

(d) Trovare un sottoreticolo L⁰ del reticolo L ;

tale che L⁰ abbia esattamente sei elementi e sia distributivo.

(e) Stabilire se il reticolo L ;

sia un’algebra di Boole oppure no.

(f ) Stabilire se il reticolo L ;

sia distributivo oppure no.

[2] (a) Calcolare il resto nella divisione per 11 dei due numeri A := 1111111^44444444 , B := 999999999^333333333

[3] Utilizzando il Principio di Induzione, si dimostri che per ogni n ∈ N il numero A := n²+ 3 n + 2 `e sempre pari.

(2)

[4] (a) Determinare se esista la classe 6⁻¹ inversa di 6 in Z30 e in Z31. In ciascun caso, se la risposta `e positiva si calcoli esplicitamente la classe inversa 6⁻¹.

(b) Risolvere l’equazione modulare 96 x = 21 nell’anello Z30. (c) Risolvere l’equazione modulare 37 x = 29 nell’anello Z31.

[5] Sia G il multigrafo cos`ı rappresentato:

v₄

v₆

v₇ v₁

v₉

v₈

v₃

v₂

v₅

`₁

`₂

`₃

`₄

`₆

`₅

`₇

`₈

`₁₄

`₁₂

`₉ `₁₀

`₁₃

`₁₁

`₁₅

`₁₆

(a) Determinare esplicitamente la matrice di adiacenza di G .

(b) Determinare se G sia euleriano, semieuleriano oppure né l’uno né l’altro: in caso negativo si spieghi il perché, in caso affermativo si spieghi perché esistono cammini euleriani, e se ne determini esplicitamente uno.

(c) Determinare tutte le foglie e tutti i ponti di G .

(d) Esistono alberi ricoprenti di G ? In caso negativo si spieghi il perch´e, in caso affermativo si determinino esplicitamente (se possibile) tre diversi alberi ricoprenti.

[6] Sia E un insieme, e siano η1, η2 due equivalenze in E .

(a) Dimostrare che la relazione η := η₁∩ η₂ in E `e una equivalenza.

(b) Descrivere esplicitamente le classi di equivalenza di η := η₁∩ η₂ in funzione delle classi di equivalenza di η₁ e di η₂.

(3)

SVOLGIMENTO

N.B.: lo svolgimento qui presentato è molto lungo... Questo non significa che lo svolgimento ordinario di tale compito (nel corso di un esame scritto) debba essere altrettanto lungo. Semplicemente, questo lo è perché si approfitta per spiegare — in diversi modi, con lunghe digressioni, ecc. ecc. — in dettaglio e con molti particolari tutti gli aspetti della teoria toccati più o meno a fondo dal testo in questione.

[1] — (a) Ricordiamo che in un insieme ordinato in cui esista il minimo si dicono atomi gli elementi (se esistono) che coprono tale minimo. Nel caso in esame il reticolo

L ;

ha per minimo min(L) = z e gli elementi che lo coprono — cio`e appunto gli atomi di L — tutti e soli i seguenti: v , w , x e y .

(b) Ricordiamo che in un reticolo un elemento q si dice ∨–irriducibile se in ogni sua ∨–

fattorizzazione del tipo q = r ∨ s si ha necessariamente r = q oppure s = q . Qualora il reticolo sia finito — come nel caso in esame — e quindi perfettamente descritto tramite il suo diagramma di Hasse, gli elementi ∨–irriducibili si riconoscono facilmente: sono quelli che coprono al pi`u un solo elemento, dunque quelli che hanno al pi`u una sola “zampa”

che scende al disotto di essi; in particolare, il minimo e tutti gli atomi sono sempre ∨–

irriducibili. Nel caso in esame, dall’analisi del diagramma di Hasse concludiamo subito che gli elementi ∨–irriducibili sono tutti e soli i seguenti: z (cio`e il minimo), v , w , x , y (cio`e gli atomi), e , f e d .

(c) Ricordiamo che in un reticolo finito — come `e L — per ogni elemento esiste sempre (almeno) una ∨–fattorizzazione in elementi ∨–irriducibili, e quindi ne esiste anche (almeno) una che sia non ridondante. Nel caso del reticolo L in esame, per gli elementi a , c e g tutte le fattorizzazioni di questo tipo sono le seguenti:

a = e ∨ d = e ∨ f = d ∨ f = v ∨ d = d ∨ y = v ∨ f = e ∨ y =

= e ∨ x ∨ y = v ∨ w ∨ f = v ∨ y = v ∨ w ∨ y = v ∨ x ∨ y = v ∨ w ∨ x ∨ y c = w ∨ f , g = v ∨ w ∨ x = v ∨ x

(d) Cercando un reticolo L⁰ di L che abbia esattamente sei elementi e sia distributivo, l’esempio più semplice possibile (forse) si trova scegliendo un sottoinsieme totalmente ordinato di sei elementi: ad esempio, il sottoinsieme L⁰ := { z , v , k , e , b , a } , oppure il sottoinsieme L⁰ := { z , x , n , f , c , a } , ma ce ne sono molti altri (precisamente, tutte le catene ascendenti in L di sei elementi). Essendo un sottoinsieme totalmente ordinato, esso è automaticamente un sottoreticolo e (come tutti gli insiemi ordinati) è distributivo.

In alternativa, ogni “sotto-diagramma” del diagramma di Hasse di L ;

di forma

∗ ?

∗

??

∗

__

oppure ?

??

?

__

∗

__ ??

∗

__

?

??

?

__ ??

__ ?? __ ??

(4)

rappresenta un sottoreticolo L⁰ di L che ha esattamente sei elementi ed `e certamente distributivo. Ad esempio, due sottoreticoli di questo tipo sono

g c

k

@@

m

__

e h

@@

f

^^

w

__ >>

x

__

m

??

n

__ ??

z

aa >>

x

`` >>

ma ci sono anche varie altre possibilit`a.

Un altro esempio ancora `e dato dalla scelta di un sottoreticolo L⁰ il cui diagramma di Hasse sia di forma

• a

•

OO

d

OO

•

OO

ad esempio m

OO

•

@@

•

^^

w

>>

x

__

•

__ ??

z

aa >>

ma ci sono poi anche molti altri sottoreticoli di questa stessa forma, dunque tutti con sei elementi e distributivi.

(e) Il reticolo L ;

certamente non `e un’algebra di Boole, per varie ragioni, ciascuna sufficiente di per s´e. Ne elenchiamo alcune:

(e.1) L non è un’algebra di Boole perché non è distributivo, come spiegato al punto (f ) qui sotto.

(e.2) L non è un’algebra di Boole perché alcuni elementi non hanno un complemento. Ad esempio, non esiste complemento per l’elemento w , nè per l’elemento x .

(e.3) L non è un’algebra di Boole perché alcuni elementi hanno più di un complemento. Ad esempio, k ha per complemento ciascuno degli elementi f , n e y , mentre f ha per complemento ciascuno degli elementi e , k e v ; l’elemento y ha per complemento ciascuno dei sei elementi b , e , g , k , v e d , ed esistono poi ancora altri casi di elementi con più di un complemento...

(e.4) L non è un’algebra di Boole perché ha troppi elementi ∨–irriducibili. Infatti, in generale in un’algebra di Boole gli elementi ∨–irriducibili sono soltanto gli atomi più il minimo: invece in L ci sono — come si vede dallo svolgimento dei punti (a) e (b) — degli elementi ∨–irriducibili diversi dagli atomi e dal minimo, precisamente e , f e d .

(f ) Come gi`a spiegato al punto (e.1) qui sopra, il reticolo L ;

non `e distributivo,

(5)

perch´e ci sono in L dei sottoreticoli isomorfi al reticolo (non distributivo) N₅ e anche alcuni sottoreticoli isomorfi al reticolo (non distributivo) M₅. Ricordiamo infatti che tali reticoli sono descritti da diagrammi di Hasse della forma

1

◦

@@

1

N₅ = ◦

WW

M₅ = •

AA

•

OO

•

^^

◦

OO

0

]] OO @@

0

^^ HH

e all’interno del reticolo L troviamo ad esempio che il sottoinsieme L^◦ := { a , b , d , g , m }

`e un sottoreticolo ismorfo a N₅, come anche — ad esempio — il sottoinsieme L^• :=

{ a , b , d , c , m } è un sottoreticolo isomorfo a M₅. Questo implica, per il Criterio di Distributività dei Reticoli, che certamente L non è distributivo.

In modo più diretto, possiamo osservare che L non è distributivo perché esistono elementi `₁, `₂, `₃ ∈ L che non soddisfano uno o l’altra delle identità (che esprimono le proprietà distributive)

`₁∧ (`₂∨ `₃) = (`₁ ∧ `₂) ∨ (`₁∧ `₃) , `₁∨ (`₂∧ `₃) = (`₁ ∨ `₂) ∧ (`₁∨ `₃) (1) Infatti, nel caso `₁ = b , `₂ = d , `₃ = g (che sono elementi di L^◦), abbiamo

b ∧ (d ∨ g) = b ∧ a = b 6= g = m ∨ g = (b ∧ d) ∨ (b ∧ g)

dunque non vale l’identit`a di sinistra in (1); analogamente, `₁ = h , `₂ = d , `₃ = c , abbiamo

h ∨ (d ∧ c) = h ∨ m = h 6= c = a ∧ c = (h ∨ d) ∧ (h ∨ c)

quindi non vale l’identit`a di destra in (1). Con calcoli analoghi si trova che anche per i tre elementi `₁ = b , `₂ = d , `₃ = c (che sono elementi di L^•) non valgono le identit`a distributive in (1).

[2] — Osserviamo che calcolare il resto di N nella divisione per d significa trovare l’unico numero r ∈ N tale che 0 ≤ r < d e N = q d+r per un certo numero q ∈ N (che ora non ci interessa). Questo equivale a trovare l’unico numero r ∈ N tale che 0 ≤ r < d e N ≡ r mod d , che scritto in un’altra forma significa trovare l’unico numero r ∈ N tale che 0 ≤ r < d e N = r ∈ Zd. Procediamo allora a svolgere i calcoli necessari.

Per N := A = 1111111^44444444 abbiamo

A = 1111111^44444444 = 1111111^44444444 = 1^44444444 = 1 (2) perch´e 1111111 = 11 · 10⁵+ 11 · 10³+ 11 · 10 + 1 ≡₁₁1 , dunque 1111111 ≡₁₁1 e quindi

(6)

Per N := B = 999999999^333333333 abbiamo

B = 999999999^333333333 = 999999999^44444444 = 9^333333333 (3) perch´e 999999999 = 9 · 111111111 = 9 · 11 · 10⁷+ 11 · 10⁵+ 11 · 10³+ 11 · 10 + 1

≡₁₁ 9 · 1 ≡11 9 , dunque 999999999 ≡11 9 e quindi 999999999 = 9 ∈ Z¹¹ . Ora, per calcolare la potenza nel membro di destra della (3) osserviamo che il Teorema di Eulero ci garantisce che, siccome M.C.D.(9, 11) = 1 , abbiamo 9^ϕ(11)≡111 , cioè 9^ϕ(11)= 1 ∈ Z¹¹, dove ϕ(11) è il valore della funzione di Eulero su 11. Poiché 11 è numero primo — o direttamente dalla definizione di ϕ — abbiamo ϕ(11) = 11 − 1 = 10 . Allora, sfruttando il Teorema di Eulero, dalla (3) ricaviamo

9^333333333 = 933333333·10+3

=

9¹⁰

333333333

9³ = 1333333333

9³ = 1 · 9³ = 9³ da cui poi il calcolo diretto ci d`a

9³ = 11 − 2³ = −2³ = (−2)³ = −(2³) = −8 = 11 − 8 = 3 oppure, seguendo un’altra strada,

9³ = 9²⁺¹ = 9²· 9¹ = 9²· 9¹ = 81 · 9 = 4 · 9 = 4 · 9 = 36 = 3 · 11 + 3 = 3 In ogni caso, da questi calcoli ricaviamo che il resto cercato per B `e r = 3 .

[3] — Dovendo dimostrare che A_n := n² + 3 n + 2 `e pari, per ogni n ∈ N , utilizzando il principio di induzione, adottiamo quello in forma debole, nei due passi Base dell’Induzione e Passo Induttivo.

Base dell’Induzione: dobbiamo dimostrare che la tesi `e vera per n = 0 , cio`e che A0

`e pari. Ora, per definizione abbiamo A₀ := 0²+ 3 · 0 + 2 = 2 , che `e pari, q.e.d.

Passo Induttivo: dobbiamo dimostrare che, dato un k (∈ N) qualsiasi, SE è vera la tesi per k , ALLORA è vera la tesi anche per k +1 . Dunque abbiamo (=Ipotesi induttiva) Hp Ind : A_k è pari, cioè ∃ N_k ∈ Z : Ak = 2 N_k (4) e dobbiamo dimostrare (=Tesi Induttiva) che

Th Ind : A_k+1 `e pari, cio`e ∃ N_k+1∈ Z : Ak = 2 N_k+1 (5) Per ottenere dunque la (5) dalla (4), sviluppiamo esplicitamente A_k+1 e poi lo riscriv- iamo in termini di A_k, come segue:

A_k+1 := (k +1)² + 3 (k + 1) + 2 = k² + 2 k + 1 + 3 k + 3 + 2 =

= k²+ 3 k + 2 + 2 k + 1 + 3 = k²+ 3 k + 2 + 2 k + (1 + 3) =

= Ak+ 2 k + 4^(∗)= 2 Nk+ 2 (k + 2) = 2 (Nk+ k + 2) = 2 Nk+1

dove N_k+1 := N_k+ k + 2 e nel passaggio indicato con “^(∗)= ” abbiamo sfruttato l’ipotesi induttiva (4) che dice proprio che A_k= 2 N_k . Cos`ı la (5) `e dimostrata, q.e.d.

(7)

[4] — (a) In generale, ricordiamo che nell’anello Zn degli interi modulo n per una specifica classe a := [a]_n esiste la classe inversa a⁻¹ := [a]_n⁻¹ se e soltanto se M.C.D.(a, n) = 1 . Infatti, questo segue dal fatto che a⁻¹, se esiste, `e l’unica soluzione dell’equazione modulare a x = 1 in Zn: quest’ultima `e equivalente all’equazione congruenziale (in Z ) a x ≡ 1 mod n , che a sua volta ammette soluzioni se e soltanto se M.C.D.(a, n)

1 , dunque se e soltanto se M.C.D.(a, n) = 1 .

Applicando quanto appena ricordato al caso a := 6 e n := 30 otteniamo che M.C.D.(6, 30) = 6 6= 1 , e quindi concludiamo che non esiste in Z30 la classe 6⁻¹ = [6]₃₀⁻¹ inversa della classe 6 = [6]₃₀ in Z30 .

Applicando lo stesso criterio per a := 6 e n := 31 osserviamo che M.C.D.(6, 31) = 1 , e dunque esiste in Z³⁰ la classe 6⁻¹ = [6]₃₁⁻¹ inversa della classe 6 = [6]₃₁ in Z³¹ .

A questo punto per calcolare effettivamente la classe [6]₃₁⁻¹procediamo cos`ı: l’algoritmo euclideo delle divisioni successive ci d`a

31 = 6 · 5 + 1 6 = 1 · 6 + 0

da cui ricaviamo l’identità di Bézout 31 · 1 + 6 · (−5) = 1 , che a sua volta ci dà 6 · (−5) = 1 , per cui la classe inversa cercata è 6⁻¹ = (−5) = −5 = 26 in Z31.

(b) Per risolvere l’equazione modulare 96 x = 21 nell’anello Z30 cominciamo riducendo modulo 30 i numeri che compaiono in tale equazione, o comunque sostituen- doli con numeri ad essi congruenti (modulo 30) che siano però più “semplici”, in modo da semplificare i calcoli. Operativamente, abbiamo 96 = 6 e 21 = −9 = −9 , perciò l’equazione modulare di partenza si può riscrivere nella forma

6 x = −9 in Z30

Ma risolvere tale equazione equivale a risolvere l’equazione congruenziale (in Z ) 6 x ≡ −9 mod 30

la quale non ammette soluzioni, perch´e si ha 6 = M.C.D.(6, 30) 6

(−9) , cio`e il M.C.D.

tra il coefficiente dell’incognita e il modulo non divide il termine noto. Concludiamo allora che l’equazione modulare di partenza non ammette soluzioni.

(c) Per risolvere l’equazione modulare 37 x = 29 nell’anello Z31 cominciamo riducendo modulo 31 i numeri che compaiono in tale equazione, o comunque sostituen- doli con numeri ad essi congruenti (modulo 31) che siano però più “semplici”, in modo da semplificare i calcoli. Operativamente, abbiamo 37 = 6 e 29 = −2 = −2 , perciò l’equazione modulare di partenza si può riscrivere nella forma

6 x = −2 in Z31 (6)

Ora, risolvere tale equazione equivale a risolvere l’equazione congruenziale (in Z ) 6 x ≡ −2 mod 31

(8)

la quale ammette soluzioni, perch´e si ha 1 = M.C.D.(6, 31) 6

(−2) , cio`e il M.C.D. tra il coefficiente dell’incognita e il modulo divide il termine noto. Concludiamo allora che l’equazione modulare di partenza non ammette soluzioni. A questo punto, la soluzione — unica! — di (6) pu`o essere calcolata cos`ı

6 x = −2 ⇐⇒ 6 x = 6⁻¹ − 2

= − 5

− 2

= 10

sfruttando quanto gi`a visto al punto (a), per cui x = 10 `e l’unica soluzione dell’equazione modulare di partenza.

In alternativa, un possibile metodo che consente calcoli elementari (ma richiede un po’

di astuzia) pu`o essere il seguente: dato che −2 = 2 · 31 − 2 = 62 − 2 = 60 = 6 · 10 , la (6) si riscrive come

6 x = 6 · 10

la quale ovviamente ha soluzione x = 10 ; inoltre, poich´e M.C.D.(6, 31) = 1 , sappiamo anche che questa `e l’unica soluzione esistente in Z31.

[5] — (a) Ricordiamo che la matrice di adiacenza A_G = a_ijj=1,...,n;

i=1,...,n; di un multigrafo G con n vertici ha come coefficienti i numeri

a_ij := (1 + δ_ij) · (numero di spigoli tra il vertice i-esimo e il vertice j-esimo) Perci`o dall’analisi diretta del multigrafo in esame troviamo che la matrice richiesta `e

AG =







0 0 1 2 0 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 2 1 1 0 0 0 0 2 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0







(b) Ricordiamo che un multigrafo si dice euleriano, risp. semieuleriano, se possiede un cammino euleriano chiuso, risp. un cammino euleriano aperto, laddove si dice cammino euleriano un cammino che percorra esattamente una e una sola volta ogni spigolo del multigrafo. Inoltre, un criterio per stabilire se un multigrafo sia euleriano, semieuleriano, o nessuno dei due, formulato esclusivamente in termini del grado di ciascun vertice, `e il seguente:

(E) — Un multigrafo `e euleriano se e soltanto se per ogni suo vertice il grado `e pari.

(SE) — Un multigrafo `e semieuleriano se e soltanto se esistono esattamente due vertici, siano v+ e v×, con grado dispari mentre ogni altro vertice ha grado pari; in questo caso, ogni possibile cammino euleriano nel multigrafo ha per estremi i vertici con grado dispari v₊ e v×.

(9)

Ricordiamo che il grado di un vertice v `e, per definizione, il numero di semi-spigoli che si appoggiano in v . Dall’analisi diretta allora troviamo che nel caso del multigrafo G in esame i gradi d(v_i) dei vari vertici v_i sono

d(v1) = 6 , d(v2) = 4 , d(v3) = 6 , d(v4) = 4 , d(v5) = 1 d(v₆) = 5 , d(v₇) = 2 , d(v₈) = 2 , d(v₉) = 2

Dunque abbiamo esattamente due vertici v₊ := v₅ e v_× := v₆ con grado dispari, mentre tutti gli altri hanno grado pari. Pertanto, per il criterio (SE) su ricordato concludiamo che il multigrafo G `e semieuleriano, e in esso ogni cammino euleriano ha per estremi i vertici v₊ := v₅ e v_×:= v₆ .

Un possibile cammino euleriano (orientato da v₊ := v₅ a v× := v₆) `e dato dalla seguente successione di vertici e spigoli:

v₊:= v₅ ≺ `₁₅ v₃ ≺ `₁₆ v₃ ≺ `₁₃ v₂ ≺ `₁₁ v₇ ≺ `₁₀ v₆ ≺ `₆ v₂· · ·

· · · v₂ ≺ `₂ v₈ ≺ `₁ v₁ ≺ `₃ v₉ ≺ `₄ v₆ ≺ `₅ v₁ ≺ `₇ v₄· · ·

· · · v₄ ≺ `₈ v₁ ≺ `₁₄ v₃ ≺ `₁₂ v₄ ≺ `₉ v₆ =: v_× Un altro possibile cammino (orientato da v× := v6 a v+:= v5), tra i tanti, `e dato da v×:= v₆ ≺ `₁₀ v₇ ≺ `₁₁ v₂ ≺ `₆ v₆ ≺ `₄ v₉ ≺ `₃ v₁ ≺ `₁₄ v₃· · ·

· · · v₃ ≺ `₁₆ v₃ ≺ `₁₃ v₂ ≺ `₂ v₈ ≺ `₁ v₁ ≺ `₇ v₄ ≺ `₉ v₆· · ·

· · · v₆ ≺ `₅ v₁ ≺ `₈ v₄ ≺ `₁₂ v₃ ≺ `₁₅ v₅ =: v₊ (c) Ricordiamo che una foglia di un multigrafo `e un vertice che ha grado minore di 2:

dall’analisi diretta vediamo allora che nel multigrafo G esiste esattamente una sola foglia, che `e il vertice v₅.

Ricordiamo che un ponte di un multigrafo è uno spigoli tale che, cancellandolo, la componente connessa che lo contiene si spezzi in due componenti connesse distinte; ad esempio, se c’è nel multigrafo una foglia di grado 1, allora l’unico spigolo che si appoggia a quella data foglia è certamente un ponte. Nel caso del multigrafo G in esame dall’analisi diretta vediamo che esiste esattamente un solo ponte, che è proprio quell’unico spigolo `15

che si appoggia all’unica foglia (di grado 1) v₅ presente in G .

(d) Il multigrafo G `e chiaramente connesso, perci`o sicuramente esistono alberi ricoprenti di G . In particolare, tra i tanti possibili presentiamo i sei seguenti:

[6] — (a) Ricordiamo che una relazione ρ si dice (di) equivalenza se è riflessiva, transitiva e simmetrica. Proviamo allora che, per ciascuna di queste tre proprietà, se η₁ e η₂ la soddisfa allora ciò è vero anche per η := η₁∩ η₂ . Ricordiamo anche che la relazione η := η₁∩ η₂ è descritta da a η b ⇐⇒ (a η₁b) ∧ (a η₂b) .

(a.1) Riflessività: Per ogni y ∈ E si ha y η₁y (perché η₁ è riflessiva!) e y η₂y (perché η₂ è riflessiva!), e quindi anche y η y , q.e.d.

(a.2) Transitivit`a: Per ogni x, y, z ∈ E tali che x η y e y η z , vogliamo dimostrare che x η z . Ora,

(10)

v4

v6

v7 v1

v9 v8

v3

v2

v5

`2

`3

`6

`5

`7

`14

`10

`15

v4

v6

v7 v1

v9 v8

v3

v2

v5

`1

`3

`7

`12

`9

`13

`11

`15

v4

v6

v7 v1

v9 v8

v3

v2

v5

`2

`4

`6

`8 `9

`13

`11

`15

v4

v6

v7 v1

v9 v8

v3

v2

v5

`1

`3

`4

`5

`12

`9

`10

`11

`15

v4

v6

v7 v1

v9 v8

v3

v2

v5

`2

`3

`4

`6

`14

`12 `13

`11

`15

v4

v6

v7 v1

v9 v8

v3

v2

v5

`2

`3

`4

`6

`12

`9

`10

`15

perché η := η₁ ∩ η₂ e perché η_i è transitiva, per ogni i ∈ {1, 2} . Dunque abbiamo (x η1z) ∧ (x η2z) , cioè proprio x η z , q.e.d.

(a.3) Simmetria: Per ogni x, y ∈ E tali che x η y , vogliamo provare che y η x . Ma (x η y) =⇒ (x η_iy) =⇒ (y η_ix) ∀ i ∈ {1, 2}

perché η := η₁ ∩ η₂ e perché η_i è simmetrica, per ogni i ∈ {1, 2} ; quindi abbiamo (y η1x) ∧ (y η2x) , cioè proprio y η x , q.e.d.

(b) Per ogni e ∈ E , vogliamo descrivere la classe di η–equivalenza di e , che per definizione `e il sottoinsieme di E dato da

[e]_η := e⁰ ∈ E

e⁰η e

Analogamente, le classi di η_i–equivalenza ( i = 1, 2 ) di e sono date da [e]_η

1 := e⁰ ∈ E

e⁰η₁e

, [e]_η

2 := e⁰ ∈ E

e⁰η₂e A questo punto, il calcolo diretto ci d`a

[e]_η := e⁰ ∈ E

e⁰η e

= e⁰ ∈ E

e⁰η1e ∧ e⁰η2e

=

= e⁰ ∈ E

e⁰η₁e T e⁰ ∈ E

e⁰η₂e

= [e]_η

1T [e]_η₂ dunque [e]_η = [e]_η

1T [e]_η₂ , che `e proprio una descrizione del tipo richiesto. In parole, ogni classe di equivalenza (di un elemento e in E) per η := η₁ ∩ η₂ `e nient’altro che l’intersezione delle classi di equivalenza (dello stesso elemento!) per η₁ e per η₂.