7. Reti di Petri

(1)

FACOLT `A DI SCIENZE MATEMATICHE, FISICHE E NATURALI

CORSO DI LAUREA SPECIALISTICA IN MATEMATICA

R ETI DI P ETRI E

A NALISI F ORMALE DEI C ONCETTI

RELATORE: LAUREANDA:

CHIAR.MO PROF.JOSEF ESCHGF ¨ALLER CHIARA LEARDINI

ANNO ACCADEMICO 2009-2010

(2)

(3)

Introduzione 3

I. TRANSIZIONI IN UN INSIEME PARZIALMENTE ORDINATO

1. Insiemi parzialmente ordinati 7

2. Connessioni di Galois 19

3. Graduazioni 23

4. Insiemi parzialmente ordinati con rango 27

5. Reticoli semimodulari e teorema di Jordan-H¨older 33 6. Transizioni associate a un insieme parzialmente ordinato 37

II. RETI DI PETRI

7. Reti di Petri 43

8. Categorie 49

9. Alcune costruzioni fondamentali 59

10. Funtori 69

11. Semianelli 71

12. La categoria delle reti di Petri 75

13. La graduazione associata a una rete di Petri 93

14. Raggiungibilit `a in una rete reversibile 97

15. Basi di Gr¨obner 101

16. Operatori ternari 107

17. Simulazione di reti di Petri 109

18. Invarianti 113

III. ANALISI FORMALE DEI CONCETTI

19. Contesti formali 117

20. Calcolo del reticolo dei concetti 123

21. Sottocontesti compatibili e immagini omomorfe 127

22. Il completamento di Dedekind-MacNeille 131

23. Alcune applicazioni dell’analisi formale dei concetti 137 24. Analisi formale dei concetti e reti di Petri 141

Bibliografia 149

(4)

(5)

Le reti di Petri sono uno strumento per la modellizzazione grafica e matematica di processi che sono paralleli, asincroni e non determini- stici, durante i quali alcune fasi possono essere eseguite simultanea- mente ma non indipendentemente l’una dall’altra.

A volte infatti non `e possibile descrivere un processo mediante un diagramma di flusso come quelli correntemente usati, in cui le fasi sono rigidamente consequenziali e in cui due distinti rami del diagramma contengono azioni che non avvengono contemporaneamente ma rappresentano strade alternative scelte sulla base di criteri de- terministici dipendenti dall’esito della valutazione di un’espressione booleana.

Le reti di Petri vengono definite in modo tale da ottenere una carat- teristica in pi `u rispetto ai diagrammi di flusso, poich´e non solo descri- vono globalmente un processo, ma permettono di seguirne l’evoluzione visualizzando lo stato in cui si trova le rete in un determinato istante.

Introdotte nel 1962 da Carl Adam Petri (1926-2010) nella sua dis- sertazione sui processi concorrenti e molto popolari nell’informatica teorica, le reti di Petri si prestano molto bene a descrivere sistemi di reazioni chimiche e biologiche e vengono quindi da alcuni anni usate con successo anche nella biochimica e nella medicina teorica.

Nel primo capitolo abbiamo eseguito alcune costruzioni fondamentali per insiemi parzialmente ordinati, includendo le dimostrazioni del teorema di Mirsky (che afferma che ogni insieme parzialmente ordinato di altezza ≤ m pu`o essere rappresentato come unione disgiunta dim + 1 anticatene) e del teorema di Dilworth (che afferma che ogni insieme parzialmente ordinato di larghezza ≤ m pu`o essere rappresentato come unione disgiunta dim catene).

Abbiamo poi presentato il concetto di connessione di Galois che permette di stabilire biiezioni tra i sottoinsiemi chiusi di due insiemi parzialmente ordinati. Nel terzo capitolo abbiamo introdotto la nozione molto generale di graduazione che nell’ambito della teoria delle reti di Petri verr `a utilizzata per formulare la fondamentale relazione di raggiungibilit `a.

Nell’ambito della teoria degli insiemi parzialmente ordinati finiti abbiamo introdotto la definizione di rango (un concetto che generalizza la dimensione di uno spazio vettoriale), considerando poi insiemi parzialmente ordinati e gerarchicamente completi (cio`e dotati di rango) e definendo il completamento gerarchico di un insieme parzialmente ordinato non dotato di rango.

Nel quinto capitolo abbiamo richiamato le nozioni di reticolo, reticolo modulare e reticolo semimodulare; abbiamo dimostrato il teorema di Jordan-H¨older che stabilisce che un reticolo finito semimodulare `e gerarchicamente completo.

(6)

Nel capitolo 6 abbiamo dato le definizioni di stato, posizione e transizione associate a insiemi parzialmente ordinati, definizioni che abbiamo esteso nel capitolo successivo considerando le reti di posizione e transizioneP/T e le reti di Petri.

Le retiP/T vengono definite come triple (P, T, ω), dove T `e l’insieme delle transizioni,P `e l’insieme delle posizioni della rete e dove

ω : T −→ (N × N)^P è un’applicazione che definisce l’effetto delle transizioni della rete. Similmente definiamo le reti di Petri come coppie (P, T ) in cui P è un insieme parzialmente ordinato e T è un sottoinsieme finito di(N × N)^P, per cui una rete di Petri risulta essenzialmente una reteP/T in cui l’applicazione ω è iniettiva.

Rappresentiamo le reti di Petri utilizzando prima dei grafi orientati con spigoli pesati e vertici; questi ultimi comprendono sia le posizioni della rete (rappresentate da cerchietti vuoti) sia le transizioni (cerchietti pieni), mentre i pesi sulle frecce del grafo indicano le quantit `a che intervengono nei processi di cui la rete `e modello (come ad esempio nelle equazioni stechiometriche della chimica). Studiamo in questo capitolo i concetti di transizioni e multitransizioni eseguibili in un dato stato della rete.

Nei capitoli 8-10 abbiamo raccolto alcune costruzioni fondamentali della teoria delle categorie (morfismi, isomorfismi, epimorfismi, mono- morfismi, prodotti e somme, pullback e pushout, funtori).

Nel capitolo 11 sono state introdotte le definizioni di semianello e se- mimodulo. Questa parte viene utilizzata per definire la categoria delle reti di Petri come una categoria di strutture algebriche in cui gli omomorfismi tra reti di Petri f : (P, T ) −→ (P^′, T^′) sono applicazioni f : P −→ P^′ che soddisfano la condizione di invarianza f_∗(T ) ⊂ T^′ dovef_∗ `e un omomorfismo di (N × N)-semimoduli ((N × N)^P). Possiamo allora definire l’applicazione f_T : T −→ T^′ tramitef_T(t) := f_∗(t) per t ∈ T .

Abbiamo associato poi ad una rete di Petri una graduazione, potendo cos`ı formulare la raggiungibilit à in una rete reversibile. Nell’ambito delle reti di Petri, diremo che uno statox è raggiungibile da uno stato y se esiste una transizione generalizzata τ ∈ T^∗ tale che (x, y) ∈ τ , dove conT^∗ denotiamo il monoide libero generato daT . La nozione di reversibilit à per una rete di Petri è molto importante nelle applicazioni pratiche.

La raggiungibilit à in una rete di Petri reversibile può essere carat- terizzata in modo algebrico tramite una relazione in un anello di po- linomi. Questa relazione può essere verificata usando la tecnica delle basi di Gröbner, alle quali è dedicato il capitolo 15.

Il breve capitolo sugli operatori ternari mostra come le reti di Petri potrebbero essere descritte nell’ambito della teoria dei numeri.

Utilizzando un programma in Python abbiamo eseguito una simulazione di rete di Petri relativo al meccanismo di divisione di una cellula

(7)

staminale con lo scopo di rappresentare una crescita controllata della cellula. A questo esempio abbiamo applicato le brevi considerazioni sugli invarianti nel capitolo 18.

Nell’ultima parte della tesi abbiamo dato un’introduzione all’analisi formale dei concetti, in cui un contesto formale è definito come una tripla(G, M, I) tale che G ed M sono insiemi finiti disgiunti ed I è una relazione tra gli elementi diG che chiameremo oggetti e gli elementi di M che chiameremo attributi. Dato un contesto formale è definita una connessione di Galois data tramite le applicazioni^◦ : P(G) −→ P(M ) e ^◦ : P(M ) −→ P(G) che stabiliscono un legame tra i chiusi di G e i chiusi di M . In particolare per ogni contesto formale ogni coppia di chiusi coniugati(A, E) con A chiuso di G e E chiuso di M tali che E = A^◦ si chiama un concetto del testo. Per un teorema fondamentale della teoria i concetti di un contesto formale formano un reticolo. Il capitolo 20 realizza in un programma in Python l’algoritmo di Gan- ter per il calcolo del reticolo dei concetti. Sottocontesti compatibili e immagini omomorfe vengono studiati nel capitolo 21.

Nel capitolo 22 si fa vedere come l’analisi formale dei concetti possa essere usata per costruire il completamento di Dedekind-MacNeille di un insieme parzialmente ordinato finito P , cioè il pi ù piccolo reticolo in cuiP può essere immerso come insieme parzialmente ordinato.

Il capitolo 23 contiene alcuni esempi per le molte applicazioni pratiche delle reti di Petri.

Nell’ultimo capitolo viene infine fatto vedere come l’analisi formale dei concetti possa essere applicata in modo naturale per studiare una rete di Petri.

(8)

(9)

1. Insiemi parzialmente ordinati

Situazione 1.1. SiaP un insieme.

Definizione 1.2. Un quasiordine suP `e una relazione binaria ≤ su P che soddisfa le seguenti condizioni, per ognia, b, c ∈ P :

(1) a ≤ a (riflessivit `a);

(2) a ≤ b ≤ c =⇒ a ≤ c (transitivit `a).

P = (P, ≤) si chiama allora un insieme quasiordinato.

≤ si chiama un ordine parziale se `e un quasiordine tale che (3) a ≤ b ≤ a =⇒ a = b (antisimmetria).

P = (P, ≤) si chiama allora un insieme parzialmente ordinato.

Sea ≤ b =⇒ a = b, diciamo che l’ordine parziale ≤ `e discreto.

Talvolta indicheremo ancheP scrivendo ≤P.

Definizione 1.3. (P, ≤) sia un insieme parzialmente ordinato. Per a, b ∈ P definiamo:

(1) a < b : ⇐⇒ a ≤ b e a 6= b . (2) [a, b] := {x ∈ P | a ≤ x ≤ b}.

(a, b) := {x ∈ P | a < x < b}.

(a, b] := {x ∈ P | a < x ≤ b}.

[a, b) := {x ∈ P | a ≤ x < b}.

(3) a ⊳ b : ⇐⇒ [a, b] = {a, b}.

Quindia ⊳ b ⇐⇒ a ≤ b e (a, b) = ∅.

In questo casoa si chiama un inferiore diretto di b e b un supe- riore direttodia.

(4) [a, ∞] := {x ∈ P | a ≤ x}.

[−∞, a] := {x ∈ P | x ≤ a}.

(a, ∞] := {x ∈ P | a < x}.

[−∞, a) := {x ∈ P | x < a}.

Per un sottoinsiemeA ⊂ P poniamo (5) [A, ∞] := S

a∈A

[a, ∞].

[−∞, A] := S

a∈A

[−∞, a].

Osservazione 1.4. (P, ≤) sia un insieme parzialmente ordinato e Q un sottoinsieme di P . La restrizione (≤) ∩ (Q × Q) di ≤ a Q × Q definisce un ordine parziale suQ che denotiamo con lo stesso simbolo

(10)

≤ ; esso si chiama l’ordine parziale indotto da P su Q. In questo modo possiamo considerare ogni sottoinsieme di P in modo naturale come un insieme parzialmente ordinato.

Definizione 1.5. Un insieme parzialmente ordinatoP si chiama (1) una catena, se pera, b ∈ P si ha sempre a ≤ b oppure b ≤ a;

(2) un’anticatena, se pera, b ∈ P la relazione a ≤ b implica a = b.

Per l’oss. 1.4 `e cos`ı anche definito quando un sottoinsieme di P `e una catena rispettivamente un’anticatena.

La lunghezza di una catenaC `e |C| − 1.

Denotiamo concatene(P ) l’insieme delle catene di P , con anticatene(P ) l’insieme delle anticatene diP .

Definizione 1.6. La larghezza (in inglese width)larg(P ) di un insieme parzialmente ordinato è la massima cardinalit à di un’anticatena diP . Definizione 1.7. L’altezza (in inglese height)alt(P ) di un insieme parzialmente ordinato è la massima lunghezza di una catena diP . Quindi

alt(P ) = max{|C| − 1 | C ∈ catene(P )}

Questa è la definizione pi ù usata (ad es. in Harzheim, pag. 24, Schröder, pag. 34).

Alcuni autori (Trotter, pag. 4) definiscono invece l’altezza come la massima cardinalit `a di una catena.

Definizione 1.8. Un’applicazioneϕ : P −→ Q tra insiemi parzialmente ordinati si dice

(1) monotona, sea, b ∈ P con a ≤ b implica ϕ(a) ≤ ϕ(b);

(2) antimonotona, sea, b ∈ P con a ≤ b implica ϕ(a) ≥ ϕ(b);

(3) un isomorfismo, se ϕ `e biiettiva e monotona e se anche ϕ⁻¹ `e monotona.

E chiaro che l’identit `a e la composizione di applicazioni monotone so-` no monotone, perci`o gli insiemi parzialmente ordinati formano una categoria che denotiamo conORD.

Osservazione 1.9. Nella figura seguente l’identit à P −→ Q è monotona, ma non è un isomorfismo.

1

2 3

4

P

1 2 3

4 Q

(11)

Ci`o mostra che un’applicazione biiettiva e monotona non `e automa- ticamente un isomorfismo.

Osservazione 1.10. Ogni insieme parzialmente ordinato può, in teo- ria, essere rappresentato mediante un diagramma di Hasse che rispec- chia la relazione⊳, come nell’oss. 1.9. Non è però vero che ogni grafo diretto, finito e senza cicli è un diagramma di Hasse, come mostra l’esempio

Definizione 1.11. P sia un insieme parzialmente ordinato. Un ele- mentoa ∈ P si dice

(1) minimale, seb ≤ a con b ∈ P implica b = a, cio`e se [−∞, a] = {a};

(2) massimale, sea ≤ b con b ∈ P implica b = a, cio`e se [a, ∞] = {a}.

Denotiamo conMin P l’insieme degli elementi minimali di P , con Max P l’insieme degli elementi massimali.

Osservazione 1.12.P sia un insieme parzialmente ordinato ed U un sottoinsieme diP . Allora Max U e Min U sono anticatene di P.

Proposizione 1.13. P sia un insieme parzialmente ordinato finito.

Allora per ognia ∈ P esistono p ∈ Min P e q ∈ Max P tali che p ≤ a ≤ q.

Dimostrazione. Immediata, sfruttando l’ipotesi cheP sia finito.

Definizione 1.14.P e Q siano insiemi parzialmente ordinati che supponiamo disgiunti¹. Definiamo la somma direttaP + Q come l’insieme parzialmente ordinatoP ∪ Q con il seguente ordine parziale:

a ≤ b in P + Q ⇐⇒







a, b ∈ P e a ≤ b in P oppure

a, b ∈ Q e a ≤ b in Q

La somma diretta è ben definita, cos`ı pure la relazione d’ordine parziale, poiché sono ben definite le relazioni d’ordine parziale sugli insiemi P e Q. Il diagramma di Hasse per P + Q è formato ponendo l’uno di fianco all’altro i diagrammi di Hasse diP e Q.

Poniamo inoltrenP := P + · · · + P

| {z }

n volte .

Proposizione 1.15.P e Q siano insiemi parzialmente ordinati. Allora P + Q `e la somma diretta di P e Q nella categoria ORD. Ci`o significa che, se coni : P −→ P + Q e j : Q −→ P + Q denotiamo le inclusioni

1Ci`o non `e una reale restrizione, ma implica che in seguito quando ad esempio scriviamo P + P , uno dei due P deve essere sostituito con una copia disgiunta dell’altro.

(12)

naturali, queste sono monotone (come `e ovvio) e per ogni diagramma

P

Q

P + Q

R i

f j

g

inORD esiste un’applicazione monotona h : P +Q −→ R, univocamente determinata, che rende commutativo il diagramma

P

Q

P + Q

R i

f j

g

h

Dimostrazione. Definiamoh(p) = f (p) per ogni p ∈ P e h(q) = g(q) per ogni q ∈ Q. È chiaro che questa è l’unica scelta possibile; infatti h(i(p)) = f (p) per p ∈ P significa proprio h(p) = f (p) e lo stesso si ha perq ∈ Q. Il diagramma è evidentemente commutativo.

Definizione 1.16.P e Q siano insiemi parzialmente ordinati. La con- catenazione(detta talvolta somma lineare)P Q `e definita prendendo la seguente relazione suP ∪ Q:

a ≤ b ⇐⇒











a, b ∈ P e a ≤ b in P oppure

a, b ∈ Q e a ≤ b in Q oppure

a ∈ P e b ∈ Q

Anche in questo caso `e immediato che si ottiene un ordine parziale.

Il diagramma di Hasse diP Q (nel caso che P e Q siano finiti) si ottiene ponendo il diagramma diP al di sotto del diagramma di Q aggiungendo un tratto rettilineo da ciascun elemento massimale di P a ciascun elemento minimale diQ.

(13)

Esempio 1.17. Consideriamo i seguenti diagrammi di Hasse:

C = C¹ C² C³ 2C 4C

C²+ C³ 2C · 3C C · (2C) · C C · (C²+ C) · C Definizione 1.18. (I, ≤) sia un insieme parzialmente ordinato. Per ogni i ∈ I sia dato un insieme parzialmente ordinato (Pi, ≤i). Suppo- niamo che gli insiemi parzialmente ordinatiP_j siano disgiunti a due a due.

Definiamo la somma ordinata (talvolta somma lessicografica) 1

i∈IPi

come S

i∈I

Piin cui gli elementi sono cos`ı ordinati:

p ≤ q se e solo se `e soddisfatta una delle due seguenti condizioni:

(1) p e q appartengono allo stesso Pj ep ≤j q.

(2) p ∈ Pi eq ∈ Pj coni < j.

Definizione 1.19. 1

i∈IPisia una somma ordinata.

(1) Se l’insieme degli indici I `e una catena, allora diremo che la somma ordinata `e lineare.

(2) Denotiamo una somma ordinata lineare finita diP1, . . . , Pn con P₁ ⊕ · · · ⊕ Pn; in essa l’addendo minore si trova all’inizio della somma.

(3) Denotiamo la somma ordinata diP1, . . . , Pnin cui l’insieme degli indici `e un’anticatena din-elementi con P₁+· · ·+P_n. Tale somma si chiama somma disgiunta diP1, . . . , Pn.

(4) Se tutti gli addendi della somma ordinata hanno un solo elemento, o se la somma ordinata `e costituita da un solo addendo, la somma ordinata `e detta banale.

Definizione 1.20. P sia un insieme parzialmente ordinato. Se P `e isomorfo ad una somma ordinata non banale 1

i∈IPi,P si dice decompo- nibile; negli altri casiP `e detto indecomponibile.

(14)

Esempio 1.21.

Definizione 1.22.P e Q siano insiemi parzialmente ordinati tali che

≤P e≤Qcoincidono suP ∩ Q. Allora definiamo la fusione U := P ⌣ Q diP e Q nel modo seguente:

a ≤U b se e solo se `e soddisfatta una delle seguenti condizioni:

(1) a ∈ P, b ∈ P e a ≤P b.

(2) a ∈ Q, b ∈ Q e a ≤Qb.

(3) a ∈ P, b ∈ Q ed esiste r ∈ P ∩ Q tale che a ≤P r ≤Qb.

(4) a ∈ Q, b ∈ P ed esiste s ∈ P ∩ Q tale che a ≤_Q s ≤_P b.

La relazione `e ben definita.

Vediamo ora che si tratta effettivamente di un ordine parziale.

(I) La riflessivit `a `e immediata.

(II) Antisimmetria.

Sianoa, b ∈ U con a ≤_U b ≤_U a. Verifichiamo i seguenti casi:

✴ a ∈ P, b ∈ P : a ≤P b, b ≤P a.

Alloraa ≤P b ≤P, quindia = b.

✴ a ∈ P, b ∈ Q : a ≤P r ≤_Qb, b ≤_Qs ≤_P a con r, s ∈ P ∩ Q.

Alloraa ≤P r ≤Q b ≤Q s ≤P a, quindi a ≤P r ≤Q s ≤P a; ora a ≤P r ≤P s ≤P a poich´e ≤P e≤Q coincidono su P ∩ Q. Allora a = r = s = a, dunque a = r = b = s = a, perci´o a = b.

✴ a ∈ Q, b ∈ P : a ≤Qs ≤_P b, b ≤_P r ≤_Qa con s, r ∈ P ∩ Q.

Alloraa ≤Q s ≤P b ≤P r ≤Q a, quindi a ≤Q s ≤P r ≤Q a; ora a ≤Q s ≤Q r ≤Q a poich´e ≤P e≤Q coincidono su P ∩ Q. Allora a = s = r = a, dunque a = s = b = r = a, perci´o a = b.

✴ a ∈ Q, b ∈ Q : a ≤Qb, b ≤_Qa.

Alloraa ≤Qb ≤Q, quindia = b.

(III) Transitivit `a .

Sianoa, b, c ∈ U con a ≤U b ≤U c. Verifichiamo i seguenti casi:

✴ a ∈ P, b ∈ P, c ∈ P : a ≤P b, b ≤P c.

Alloraa ≤_P b ≤_P c, quindi a ≤_P c, cio´e a ≤_U c.

✴ a ∈ P, b ∈ P, c ∈ Q : a ≤P b, b ≤_P r ≤_Qc con r ∈ P ∩ Q.

Alloraa ≤P b ≤P r ≤Qc, quindi a ≤P r ≤Qc, cio´e a ≤U c.

✴ a ∈ P, b ∈ Q, c ∈ P : a ≤P r ≤_Qb, b ≤_Qs ≤_P c con r, s ∈ P ∩ Q.

(15)

Alloraa ≤_P r ≤_Q b ≤_Q s ≤_P c, quindi a ≤_P r ≤_Q s ≤_P c; ora a ≤P r ≤P s ≤P c poich´e ≤P e≤Q coincidono su P ∩ Q. Allora a ≤_P c, cio´e a ≤_U c.

✴ a ∈ P, b ∈ Q, c ∈ Q : a ≤P r ≤Qb, b ≤Qc con r ∈ P ∩ Q.

Alloraa ≤P r ≤Qb ≤Qc, quindi a ≤P r ≤Qc, cio´e a ≤U c.

✴ a ∈ Q, b ∈ P, c ∈ P : a ≤Qs ≤P b, b ≤P c con s ∈ P ∩ Q.

Alloraa ≤Qs ≤P b ≤P c, quindi a ≤Q s ≤P c, cio´e a ≤U c.

✴ a ∈ Q, b ∈ P, c ∈ Q : a ≤Qs ≤P b, b ≤P r ≤Qc con r, s ∈ P ∩ Q.

Alloraa ≤_Q s ≤_P b ≤_P r ≤_Q c, quindi a ≤_Q s ≤_P r ≤_Q c; ora a ≤Q s ≤Q r ≤Q c poich´e ≤P e≤Q coincidono suP ∩ Q. Allora a ≤Qc, cio´e a ≤U c.

✴ a ∈ Q, b ∈ Q, c ∈ P : a ≤Qb, b ≤Qs ≤P c con s ∈ P ∩ Q.

Alloraa ≤Qb ≤Qs ≤P c, quindi a ≤Qs ≤P c, cio´e a ≤U c.

✴ a ∈ Q, b ∈ Q, c ∈ Q : a ≤Qb, b ≤_Qc.

Alloraa ≤Qb ≤Qc, quindi a ≤Qc, cio´e a ≤U c.

Definizione 1.23. I sia un insieme e P_i un insieme parzialmente ordinato per ognii ∈ I. Allora il prodotto cartesiano Q

i∈I

Pi diventa un insieme parzialmente ordinato se perx, y ∈ Q

i∈I

Piconx =

i

xiey =

i

yi

poniamox ≤ y ⇐⇒ xi ≤ yi per ognii ∈ I.

Si dimostra facilmente che in questo modo con Q

i∈I

P_i otteniamo il prodotto direttodiP_i nella categoria ORD.

Definizione 1.24.P sia un insieme parzialmente ordinato. Un sotto- insiemeU di P si dice

(1) un ideale diP , se [−∞, U ] ⊂ U e quindi [−∞, U ] = U ; (2) un coideale diP , se [U, ∞] ⊂ U e quindi [U, ∞] = U .

Denotiamo con ideali(P ) l’insieme degli ideali di P e con coideali(P ) l’insieme dei coideali di P . Questi insiemi possono essere considerati come insiemi parzialmente ordinati rispetto all’inclusione insiemistica.

Osservazione 1.25.P sia un insieme parzialmente ordinato ed A un sottoinsieme diP . Allora [−∞, A] `e un ideale di P e similmente [A, ∞]

`e un coideale di P . Inoltre

Max[−∞, A] = Max A Min[A, ∞] = Min A

Si noti che per un insieme parzialmente ordinato infinito questi insiemi possono essere vuoti.

Dimostrazione.

(1) Innanzitutto dimostriamo che U := [−∞, A] `e un ideale di P . Siax ∈ U e y ≤ x. Dobbiamo dimostrare che y ∈ U . Per ipotesi esiste una ∈ A tale che x ≤ a; ma y ≤ x, quindi y ≤ a, cio`e y ∈ U .

Similmente si dimostra che[A, ∞] `e un coideale di P .

(16)

(2) Vediamo ora cheMax[−∞, A] = Max A.

E chiaro che` Max[−∞, A] ⊂ Max A.

Sianom ∈ Max A ed x ∈ [−∞, A] tali che x ≥ m. Allora esiste a ∈ A tale che x ≤ a, quindi m ≤ x ≤ a, cosicch´e m ≤ a e quindi m = a. Ci`o implica m = x.

Similmente si dimostra cheMin[A, ∞] = Min A.

Osservazione 1.26.P sia un insieme parzialmente ordinato finito. Se U `e un ideale di P , allora U = [−∞, Max U ]; se U `e un coideale di P , alloraU = [Min U, ∞].

Dimostrazione. L’enunciato `e una conseguenza della prop 1.13.

Teorema 1.27. P sia un insieme parzialmente ordinato finito. Allora esistono biiezioni naturali

ideali(P ) ←→ anticatene(P ) ←→ coideali(P )

U 7−→ Max U A 7−→ [A, ∞]

[−∞, A] ←−[ A Min V ←−[ V Dimostrazione.

(1) Consideriamo innanzitutto le applicazioni ϕ : ideali(P ) −→ anticatene(P )

U 7−→ Max U e ψ : anticatene(P ) −→ ideali(P ) A 7−→ [−∞, A]

Queste applicazioni sono ben definite poichéMax U è un’anticatena per l’oss.1.12 e[−∞, A] è un ideale per l’oss.1.25.

(2) Sia oraU ∈ ideali(P ). Allora

ψ(ϕ(U )) = ψ(Max U ) = [−∞, Max U ]^1.26= U (3) Sia oraA ∈ anticatene(P ). Allora

ϕ(ψ(A)) = ϕ([−∞, A]) = Max[−∞, A]^1.25= Max A, ma per ipotesiA `e un’anticatena, per cui Max A = A.

(4) Nello stesso modo si dimostra l’enunciato duale.

Osservazione 1.28. Nel teorema 1.27 si hanno in particolare a sini- stra le corrispondenze

P 7−→ Max P

∅ 7−→ ∅ e a destra le corrispondenze

Min P ←−[ P

∅ ←−[ ∅

che possono essere espresse mediante le uguaglianze P = [−∞, Max P ] = [Min P, ∞]

∅ = [−∞, ∅] = [∅, ∞]

(17)

Proposizione 1.29.P sia un insieme parzialmente ordinato ed U un sottoinsieme di P . Allora U `e un ideale di P se e solo se P \ U `e un coideale diP . In questo modo otteniamo un’altra biiezione

ideali(P ) ←→ coideali(P ) valida anche nel caso che P sia infinito.

Dimostrazione.U sia un ideale di P ed x ∈ P \ U . Sia inoltre a ∈ P conx ≤ a. Allora anche a ∈ P \ U , perch´e altrimenti si avrebbe x ∈ U . P \ U `e quindi un coideale di P .

Nello stesso modo si vede cheP \ U `e un ideale se U `e un coideale.

Proposizione 1.30.P sia un insieme parzialmente ordinato. α sia un insieme di ideali diP . Allora S

A∈α

A e T

A∈α

A sono anch’essi ideali di P . Lo stesso vale per i coideali. Ci`o implica, come si dimostra facilmente, cheideali(P ) e coideali(P ) sono reticoli completi.

Dimostrazione. SiaI := S

A∈α

A e a ∈ I. Allora esiste A ∈ α tale che a ∈ A. Sia x ≤ a. Allora x ∈ A, quindi x ∈ I, cio`e I `e un ideale.

Sia ora J := T

A∈α

A e a ∈ J. Allora a ∈ A per ogni A ∈ α. Sia x ≤ a.

Allorax ∈ A per ogni A ∈ α, quindi x ∈ J, cio`e J `e un ideale.

Analogamente si dimostra cheI e J sono coideali.

Esempio 1.31. P sia l’insieme parzialmente ordinato rappresentato dal diagramma di Hasse

1

4

5 2

3

Gli insiemi∅, {1}, {2}, {3}, {4}, {5} sono sicuramente anticatene; ad essi si aggiungono gli insiemi {2, 4} e {3, 4}. La larghezza di P `e quindi 2. Si vede anche cheP possiede altezza 3.

Tramite il teorema 1.27 troviamo gli ideali e i coideali diP :

anticatene ideali coideali

A [−∞, A] [A, ∞]

∅ ∅ ∅

{1} = Max P {1, 2, 3, 4, 5} = P {1}

{2} {2, 3, 5} {1, 2}

{3} {3, 5} {1, 2, 3}

{4} {4, 5} {1, 4}

{5} = Min P {5} {1, 2, 3, 4, 5} = P {2, 4} {2, 3, 4, 5} {1, 2, 4}

{3, 4} {3, 4, 5} {1, 2, 3, 4}

(18)

Rispetto all’inclusione insiemisticaideali(P ) pu`o essere rappresentato dal seguente diagramma di Hasse

∅ {5}

{4, 5}

{3, 5}

{3, 4, 5}

{2, 3, 5}

{2, 3, 4, 5}

{1, 2, 3, 4, 5}

La regolarit `a che si osserva non `e casuale. Infatti dall’oss. 1.30 sappiamo cheideali(P ) e coideali(P ) sono reticoli.

Osservazione 1.32. Siano m ∈N e P un insieme parzialmente ordinato che pu`o essere rappresentato come unione di m + 1 anticatene.

Alloraalt(P ) ≤ m.

Dimostrazione. SiaP = A0∪ A1∪ . . . Am con anticateneA0, . . . , Am

m + 1 e supponiamo che esista in P una catena di m + 2 elementi x₀ < x₁ < · · · < x_m+1. Ciò implica che almeno due degli x_j si devono trovare nella stessa anticatenaAk, e ciò non è possibile.

Teorema 1.33 (teorema di Mirsky). P sia un insieme parzialmente ordinato edm ∈N tale che alt(P ) ≤ m. Allora P pu`o essere rappresen- tato come unione disgiunta dim + 1 anticatene.

Dimostrazione. Seguiamo Lint/Wilson, pag. 54. Induzione sum.

m = 0: In questo caso |P | = 1, e banalmente P `e rappresentato da un’unica anticatena di cardinalit `a1.

m − 1 −→ m : Sia P un insieme parzialmente ordinato che non contiene catene di m + 2 elementi. Dalla prop. 1.13 sappiamo che Max P

è un’anticatena di P . Sia C = x0 < x1 < · · · < xm una catena in P \ Max P . Per l’ipotesi su P allora C è una catena massimale in P . Ciò implica però (per la prop. 1.13) chexm ∈ Max P , mentre avevamo xm ∈ P \ Max P . Di conseguenza P \ Max P non può contenere catene dim + 1 elementi, cosicché alt(P \ Max P ) ≤ m − 1 per cui, per ipotesi di induzione,P \ Max P può essere rappresentato come unione disgiunta dim anticatene. Ma allora P = (P \ Max P ) ∪ Max P è unione disgiunta dim + 1 anticatene.

Osservazione 1.34. Siano m ∈ N + 1 e P un insieme parzialmente ordinato che pu`o essere rappresentato come unione dim catene. Allora larg(P ) ≤ m.

Dimostrazione. SianoP = C₁∪ C2∪ · · · ∪ Cm con cateneC₁, . . . , C_m

(19)

ed A un’anticatena. A può contenere un solo elemento per ogni C_j e vediamo che la massima cardinalit à di un’anticatena diP è m.

Lemma 1.35.P sia un insieme parzialmente ordinato ed A un’anticatena massimale diP . Allora [−∞, A] ∪ [A, ∞] = P .

Dimostrazione. Siax ∈ P \ [−∞, A] ∪ [A, ∞]. Ci`o implica che x /∈ A.

Inoltre per ogni a ∈ A né x ≤ a né a ≤ x, e quindi A ∪ [x] è ancora un’anticatena strettamente maggiore diA, una contraddizione.

Teorema 1.36 (teorema di Dilworth).P sia un insieme parzialmen- te ordinato ed m ∈ N + 1 tale che larg(P ) ≤ m. Allora P pu`o essere rappresentato come unione disgiunta dim catene.

Dimostrazione. Seguiamo la dimostrazione di Tverberg in Lint/Wilson, pagg. 53-54.

Induzione sulla cardinalit `a|P | di P .

|P | = 0, 1: Chiaro.

SiaC una catena massimale di P . Se ogni anticatena di P \ C possiede al massimom − 1 elementi, otteniamo l’enunciato per induzione. Sup- poniamo che esista un’anticatenaA = {a1, . . . , am} con m elementi in P \ C. Poiché C è una catena massimale, l’elemento pi ù grande p di C appartiene a Max P , e quindi non può appartenere a [−∞, A], perché altrimentip ≤ a per un a ∈ A con p 6= a perché A∩C = ∅. In particolare si vede che[−∞, A]$ P , quindi, per ipotesi di induzione, [−∞, A] può essere rappresentato come unione di m catene disgiunte C1, . . . , Cm, dove ai ∈ Ci. Dimostriamo che ai è l’elemento massimo della catena Ci per ogni i. Sia infatti x ∈ Ci e x > ai. Essendo Ci ⊂ [−∞, A], esiste però j tale che x ≤ aj, per cui dovremmo avere ai < aj, ma ciò è assurdo, perchéA è un’anticatena. Facciamo la stessa cosa per [A, ∞], ottenendo cateneD_i cona_i ∈ Di e[A, ∞] = D₁˙∪ . . . ˙∪D_m. Combinando le catene Ci e Di per ogni i = 1, . . . , m otteniamo m catene disgiunte la cui unione è uguale a[−∞, A] ∪ [A, ∞] che, per il lemma 1.35, a sua volta è uguale a P . Infatti A è un’anticatena massimale di P , poiché

|A| = larg(P ).

(20)

(21)

Situazione 2.1. α e β siano due insiemi parzialmente ordinati. Usia- mo lettere greche minuscole perch´e nelle applicazioni di Galois questi insiemi sono spesso sistemi di insiemi. Come finora, nelle considerazioni generali, denotiamo l’ordine parziale con ≤ per entrambi gli insiemi. Assumiamo inoltre che α ∩ β = ∅ per evitare equivoci, ad esempio quando nella definizione 2.2. usiamo lo stesso simbolo^◦ per le due applicazioni che stabiliscono la connessione di Galois.

Definizione 2.2. Una connessione di Galois tra α e β `e una coppia di applicazioni^{1 ◦}: α −→ β ,^◦ : β −→ α con le seguenti propriet `a:

(1) Entrambe le applicazioni sono antimonotone.

(2) A ≤ A^◦◦per ogni A ∈ α.

E ≤ E^◦◦ per ogni E ∈ β.

Per A ∈ α ed E ∈ β definiamo allora le chiusure A:= A^◦◦

E:= E^◦◦

Con queste notazioni, la condizione (2) implica le inclusioni A ≤ A ed E ≤ E. A ∈ α si chiama chiuso se A= A; similmente E ∈ β si chiama chiusose E= E.

Denotiamo conchiusi(α) l’insieme dei chiusi di α, con chiusi(β) l’insieme dei chiusi di β.

Proposizione 2.3. Tra α e β sia data una connessione di Galois.

(1) A e B siano chiusi di α. Allora A= B ⇐⇒ A^◦= B^◦. (2) E ed F siano chiusi di β. Allora E= F ⇐⇒ E^◦= F^◦. Dimostrazione.

(1) Sia A^◦ = B^◦. Allora A= A = A^◦◦= B^◦◦= B = B.

L’implicazione opposta `e ovvia.

(2) Nello stesso modo.

Si noti che in questa dimostrazione non abbiamo usato nessuna delle condizioni (1) e (2) della def. 2.2. e nemmeno l’ipotesi che α e β siano insiemi parzialmente ordinati.

Infatti, siano f : α −→ β e g : β −→ α due applicazioni qualsiasi e A= g(f (A)), B = g(f (B)). Se adesso f (A) = f (B), allora A = B.

Osservazione 2.4.Tra α e β sia data una connessione di Galois.

(1) Siano A, B ∈ α con A^◦ ≤ B^◦. Allora B ≤ A.

(2) Siano E, F ∈ β con E^◦ ≤ F^◦. Allora F ≤ E.

1Denotiamo le applicazioni con lo stesso simbolo, ma per l’assunzione fatta nella situazione 2.1. risulter`a chiaro quale delle due applicazioni si sta considerando.

(22)

Dimostrazione.

(1) L’ipotesi implica B^◦◦≤ A^◦◦, cio`e B ≤ A.

Lemma 2.5. Tra α e β sia data una connessione di Galois. Allora:

(1) A^◦◦◦= A^◦ per ogni A ∈ α.

(2) E^◦◦◦= E^◦ per ogni E ∈ β.

Dimostrazione.

(1) Abbiamo da un lato A ≤ A^◦◦e quindi A^◦◦◦ ≤ A^◦, dall’altro lato per`o anche A^◦≤ A^◦◦◦.

Corollario 2.6. Tra α e β sia data una connessione di Galois. Allo- ra:

(1) A= A per ogni A ∈ α.

(2) E= E per ogni E ∈ β.

Osservazione 2.7.Tra α e β sia data una connessione di Galois. Per B ∈ α ed F ∈ β sono equivalenti:

(1) B `e chiuso ed F = B^◦. (2) F `e chiuso e B= F^◦. Dimostrazione.

(1)=⇒ (2) : F = F^◦◦= B^◦◦◦ = B^◦ = F , mentre F^◦ = B^◦◦= B = B.

(2)=⇒ (1) : Nello stesso modo.

Lemma 2.8. Tra α e β sia data una connessione di Galois.

Per A ∈ α ed E ∈ β sono equivalenti:

(1) E ≤ A^◦. (2) E ≤ A^◦. (3) A ≤ E^◦. (4) A ≤ E^◦.

Dimostrazione. Siccome E ≤ E e A ≤ A, abbiamo chiaramente le implicazioni (2) =⇒ (1) e (4) =⇒ (3). `E sufficiente dimostrare che (1) =⇒ (4) e (3) =⇒ (2).

(1)=⇒ (4) : E ≤ A^◦ implica A^◦◦≤ E^◦, cio`e A ≤ E^◦. (3)=⇒ (2) : A ≤ E^◦ implica E^◦◦≤ A^◦, cio`e E ≤ A^◦.

Proposizione 2.9. Tra α e β sia data una connessione di Galois.

(I) Per A ∈ α sono equivalenti:

(1) A `e chiuso.

(2) Esiste B ∈ α con A= B.

(3) Esiste E ∈ β con A= E^◦. (II) Per E ∈ β sono equivalenti:

(23)

(1) E `e chiuso.

(2) Esiste F ∈ β con E= F . (3) Esiste A ∈ α con E= A^◦. Dimostrazione.

(1)=⇒ (2) : Se A `e chiuso, allora A = A e possiamo prendere B = A.

(2)=⇒ (3) : Sia A = B con B ∈ α. Allora A = B = B^◦◦ e possiamo prendere E= B^◦.

(3)=⇒ (1) : Sia A = E^◦con E ∈ β. Allora A= A^◦◦= E^◦◦◦ = E^◦ = A.

Nello stesso modo si dimostra la seconda parte.

Corollario 2.10. Tra α e β sia data una connessione di Galois.

(1) Siano A, B ∈ α con A^◦ ≤ B^◦. Se esiste E ∈ β con A= E^◦, allora B ≤ B ≤ A.

(2) Siano E, F ∈ β con E^◦ ≤ F^◦. Se esiste A ∈ α con E = A^◦, allora F ≤ F ≤ E.

Dimostrazione.

(1) L’ipotesi implica B^◦◦≤ A^◦◦, cio`e B ≤ A. Per la prop. 2.9. A= A.

Teorema 2.11. Tra α e β sia data una connessione di Galois. Dalla prop. 2.9 sappiamo che A^◦ `e chiuso per ogni A ∈ α e che E^◦ `e chiuso per ogni E ∈ β. Le applicazioni

ϕ: chiusi(α) −→ chiusi(β)

A 7−→ A^◦ e ψ: chiusi(β) −→ chiusi(α) E 7−→ E^◦

sono quindi ben definite Esse sono inoltre l’una l’inversa dell’altra, e stabiliscono quindi una biiezione naturale tra i chiusi di α e i chiusi di β.

Dimostrazione. Affinch´e ϕ sia ben definita, basta dimostrare che A^◦

`e chiuso, come osservato nell’enunciato. La stessa cosa vale per ψ.

Sia A= A ∈ α. Allora

ψ(ϕ(A)) = ψ(A^◦) = A^◦◦= A = A Sia invece E = E ∈ β. Allora

ϕ(ψ(E)) = ϕ(E^◦) = E^◦◦= E = E

(24)

(25)

Definizione 3.1. Una graduazione `e una terna(X, S, τ ), dove X `e un insieme, S un monoide (un semigruppo con elemento neutro1S) e τ ⊂ X × S × X una relazione, la quale, se scriviamo (x, y) ∈ s invece di (x, s, y) ∈ τ , soddisfa le seguenti condizioni, per ogni x, y, z ∈ X e per ogni s, t∈ S:

(1) (x, x) ∈ 1S per ogni x∈ X.

(2) (x, y) ∈ s ed (y, z) ∈ t =⇒ (x, z) ∈ st.

(X, S, τ ) si chiama allora una S-graduazione di X o una graduazione di X su S; diciamo anche che X è graduato su S. Quando τ è sottintesa, diciamo anche che(X, S) è una graduazione.

Esempio 3.2. X sia un insieme ed S un monoide che opera a destra su X. Se definiamo(x, y) ∈ s : ⇐⇒ xs = y, otteniamo una graduazione. Se S opera invece a sinistra su X, possiamo definire

(x, y) ∈ s : ⇐⇒ x = sy.

Osservazione 3.3.(X, S, τ ) sia una graduazione.

(1) Y sia un qualsiasi sottoinsieme di X. Allora (Y, S, τ^′) `e ancora una graduazione, se poniamo τ^′ := τ_{|Y ×S×Y}. Nell’esempio 3.2 quindi per ogni Y ⊂ X otteniamo una graduazione, senza che Y sia necessariamente invariante sotto S. Questa osservazione `e piuttosto importante nelle applicazioni in informatica.

(2) T sia un sottomonoide di S (cio`e un sottosemigruppo con

1T = 1S). Allora otteniamo una graduazione(X, T, τ^′′) se poniamo τ^′′:= τ_{|X×T ×X}.

Esempio 3.4. X sia un insieme ed S un monoide che opera a destra di X. Per A ⊂ X ed s ∈ S sia As := { as | a ∈ A}. Allora S opera anche a destra sull’insieme delle parti P(X), cosicch´e otteniamo una S-graduazione di P(X). Possiamo graduare P(X) su S per`o anche in un altro modo, ponendo

(A, B) ∈ s : ⇐⇒ As ⊂ B

oppure in modo duale ponendo(A, B) ∈ s : ⇐⇒ As ⊃ B.

Esempio 3.5. S = 1 sia il monoide con un elemento. Una S-graduazione di un insieme X `e allora la stessa cosa come un quasiordine su X.

Esempio 3.6. S sia un semigruppo di relazioni (binarie) su X. Allora otteniamo direttamente una S-graduazione se con(x, y) ∈ s intendia- mo l’appartenenza insiemistica di(x, y) ad s.

Semigruppi di relazioni sono stati molto studiati nella letteratura.

Esempio 3.7.(X, d) sia uno spazio metrico. Allora d(x, y) ≤ ε e d(y, z) ≤ δ =⇒ d(x, z) ≤ ε + δ

Otteniamo quindi una graduazione di X su([0, ∞), +) se poniamo (x, y) ∈ ε : ⇐⇒ d(x, y) ≤ ε

(26)

Esempio 3.8. S sia un monoide. Allora possiamo graduare un qual- siasi sottoinsieme X ⊂ S su S non solo tramite

(a, b) ∈ s : ⇐⇒ as = b

come nell’es. 3.2, ma anche mediante (a, b) ∈ s ⇐⇒ as = sb

Se S `e un gruppo, ci`o equivale alla condizione b= s⁻¹as.

Dimostrazione. Dobbiamo dimostrare la condizione (2) della def. 3.1.

Siano(a, b) ∈ s e (b, c) ∈ t. Allora as = sb e bt = tc, da cui ast= sbt = stc, ovvero (a, c) ∈ st.

Definizione 3.9. S sia un monoide. Se per M, N ⊂ S poniamo M N := { st | s ∈ M, t ∈ N }

P(S) diventa un monoide con 1_P(S) = {1S}. Si noti che ∅M = M ∅ = ∅ per ogni M ⊂ S.

Osservazione 3.10.(X, S) sia una graduazione. Allora otteniamo una graduazione(X, P(S)) se per M ⊂ S ed x, y ∈ X poniamo

(x, y) ∈ M : ⇐⇒ esiste s ∈ M con (x, y) ∈ s.

Dimostrazione.

(1) Per ipotesi (x, x) ∈ 1S rispetto alla prima graduazione(X, S).

Ci`o significa(x, x) ∈ {1S}, mentre abbiamo osservato nella def.

3.9 che{1S} = 1_P(S).

(2) Siano(x, y) ∈ M ed (y, z) ∈ N . Allora esistono s ∈ M e t ∈ N tali che(x, y) ∈ s ed (y, z) ∈ t, e quindi (x, z) ∈ st. Ci`o significa che (x, z) ∈ M N .

Definizione 3.11. (X, S) sia una graduazione ed M ⊂ S. Per x, y ∈ X diciamo che y `e raggiungibile da x attraverso M , se(x, y) ∈ M .

Nota 3.12. Il concetto di graduazione `e molto generale e appare in molti campi della matematica. Elenchiamo altri esempi, ciascuno dei quali permette numerose variazioni.

(1) X sia un insieme ed S un monoide che opera a destra su X. Su X sia dato un quasiordine compatibile con l’azione di S, per il quale cio`e vale l’implicazione

x≤ y =⇒ xs ≤ ys per ogni x, y ∈ X e per ogni s ∈ S.

Allora si pu`o definire una graduazione tramite (x, y) ∈ s : ⇐⇒ xs ≤ y

In questo modo si ottiene un gran numero di esempi; casi speciali sono l’esempio 3.2 e l’esempio 3.3.

(2) T sia uno spazio topologico ed S il semigruppo di tutti gli aperti di T con l’intersezione come moltiplicazione. Allora possiamo definire una graduazione su X = P(T ) ponendo

(A, B) ∈ U : ⇐⇒ A ∩ U = B ∩ U

(27)

Anche questa costruzione `e un caso speciale di (1) e si ritrova frequen- temente nelle applicazioni; spesso ci si limita a determinati sottoinsiemi diP(T ), ad esempio ai sottoinsiemi analitici di uno spazio analitico complesso.

(3) X sia un insieme e ⁻ : P(X) −→ P(X) un operatore di chiusura esatto su X (cfr. def. 16.6) e S un sottomonoide di(P(X), ∪).

Definiamo una graduazione su X ponendo (x, y) ∈ A : ⇐⇒ x ∈ A ∪ y

(4) X = A sia un anello commutativo ed S il monoide degli ideali di A (compreso l’ideale improprio A) con l’addizione come composizione.

Otteniamo una graduazione ponendo (a, b) ∈ I : ⇐⇒ a ∈ I + Ab

Una graduazione pi `u familiare si ottiene ponendo (a, b) ∈ I : ⇐⇒ a − b ∈ I

(5) X sia un monoide ed S un sottomonoide di X× X. Allora si ottiene una graduazione ponendo

(x, y) ∈ (a, b) : ⇐⇒ xa = by

Questo tipo di graduazione permette di descrivere le varie forme di coniugatezza che si trovano in algebra.

(6) Pi `u in generale siano X ed Y due insiemi ed S un monoide che opera a destra su X, T un monoide che opera a sinistra su Y . Allora otteniamo una graduazione di X× Y attraverso S × T ponendo ancora

(x, y) ∈ (a, b) : ⇐⇒ xa = by

(7) X sia un grafo (diretto o non diretto). Definiamo una graduazione di X tramite(N, +) ponendo

(x, y) ∈ n : ⇐⇒ esiste un cammino di lunghezza n (oppure anche di lunghezza≤ n) da x a y.

(8) X sia un insieme e T un monoide che opera a sinistra su X. S sia un sottomonoide di P(T ) rispetto alla moltiplicazione di sottoinsiemi.

Allora otteniamo una graduazione ponendo (x, y) ∈ A : ⇐⇒ x ∈ Ay

(9) X = A sia un anello commutativo ed I un ideale di A. S sia un sottomonoide di(A, ·). Otteniamo una graduazione ponendo

(a, b) ∈ s : ⇐⇒ a − sb ∈ I

Dimostrazione. Dimostriamo, nei casi non evidenti, che si tratta ve- ramente di graduazioni. Tralasciamo la condizione (1) nella def. 3.1 che `e sempre evidente.

(3) Siano(x, y) ∈ A e (y, z) ∈ B, cio`e x ∈ A ∪ y e y ∈ B ∪ z. Allora x∈ A ∪ y ⊂ A ∪ B ∪ z ⊂ A ∪ B ∪ z = (A ∪ B) ∪ z, per cui (x, z) ∈ A∪B.

(28)

(4) Siano(a, b) ∈ I e (b, c) ∈ J, cio`e a − b ∈ I e b − c ∈ J. Allora a− c = (a − b) + (b − c) ∈ I + J.

(6) Siano(x, y) ∈ (a, b) e (y, z) ∈ (c, d), cio`e xa = by e yc = dz. Allora xac= byc = bdz, per cui (x, z) ∈ (ac, bd).

(8) Siano(x, y) ∈ A e (y, z) ∈ B, cio`e x ∈ Ay e y ∈ Bz. Allora x∈ Ay ⊂ ABz.

(9) Siano(a, b) ∈ s e (b, c) ∈ t, cio`e a − sb ∈ I e b − tc ∈ I. Allora a− stc = a + sb − sb − stc = (a + sb) − s(b − tc) ∈ I + I = I.

(29)

Situazione 4.1. P sia un insieme parzialmente ordinato finito.

Definizione 4.2. Definiamo le derivate superiori di P nel modo seguente:

P⁽⁰⁾ := P

P⁽¹⁾ := P \ Max P . . .

P^(m+1) := P^(m)(1)= P^(m)\ Max P^(m) . . .

perm ∈ N. `E chiaro cheP⁽⁰⁾⊃ P⁽¹⁾ ⊃ P⁽²⁾ ⊃ . . . . Osservazione 4.3.P^(m)(k)= P^(m+k) per ognim, k ∈ N.

Dimostrazione. Per induzione suk.

k = 0, 1 : Chiaro.

k −→ k + 1 : P^(m)(k+1)= P^(m)(k)(1) = P^(m+k)(1) = P^(m+k+1).

Osservazione 4.4.SiaQ ⊂ P . Allora Q^(m)⊂ P^(m)per ognim ∈ N.

Dimostrazione. `E sufficiente dimostrare cheQ⁽¹⁾⊂ P⁽¹⁾. Siaq ∈ Q e q /∈ Max Q. Allora anche q /∈ Max P e quindi q ∈ P⁽¹⁾. Osservazione 4.5.C = {a₁, . . . , a_n} sia una catena con a1 < · · · < a_n. AlloraC⁽ⁱ⁾= {a1, . . . , a_n−i} per i < n e C⁽ⁱ⁾= ∅ per i ≥ n.

Dimostrazione.Max C = a_n, quindi

C⁽¹⁾ = {a₁, . . . , a_n−1} C⁽²⁾ = {a₁, . . . , a_n−2} . . .

C⁽ⁿ⁻¹⁾= {a₁} C⁽ⁿ⁾= ∅ . . .

Osservazione 4.6.SianoP 6= ∅ ed h ∈ N. Allora alt(P ) = h ⇐⇒ P^(h)6= ∅ e P^(h+1)= ∅

Dimostrazione. Per induzione suh.

h = 1 : Sia P⁽⁰⁾ = P 6= ∅, ma P⁽¹⁾= P \ Max P = ∅. Ci`o significa P 6= ∅ (come per ipotesi), maP = Max P . `E chiaro allora chealt(P ) = 0.

h − 1 −→ h : Sia P^(h) 6= ∅, ma P^(h+1) = P^(h)\ Max P^(h)= ∅. Per l’oss. 4.3 ci`o significaP^(1)(h−1) 6= ∅ e P^(1)(h) = ∅, e quindi per ipotesi di induzione alt(P⁽¹⁾) = h−1. P⁽¹⁾contiene perci`o una catena dih elementi; siccome P⁽¹⁾ = P \Max P , possiamo estendere quella catena con un elemento di Max P (per la prop. 1.13), ottenendo cos`ı una catena di h + 1 elementi.

(30)

Ci`o mostra chealt(P ) ≥ h. Sia alt(P ) ≥ h + 1. Allora esiste una catena C in P con almeno h + 2 elementi, per la quale quindi C^(h+1) 6= ∅ per l’oss. 4.5. L’oss. 4.4 implica per`oC^(h+1) ⊂ P^(h+1), una contraddizione.

Nota 4.7.SianoP 6= ∅ ed h := alt(P ). Allora P = Max P⁽⁰⁾˙∪ . . . ˙∪ Max P^(h)

Per ognia ∈ P esiste quindi un unico indice k ∈ {0, . . . , h} per il quale a ∈ Max P^(k).k si chiama la profondit `a di a in P ; usiamo la notazione

prof(a) := prof(a, in P ) := k.

Esempio 4.8.

a) 1

3 4

2

k Max P^(k) 0 1, 2

1 3

2 4

b) 1

4

5 2

3

k Max P^(k)

0 1

1 2, 4

2 3

3 5

c)

1 2 3

4 5 6

7 8

9

10 11

12 13 14 15

16 17

k Max P^(k) 0 1, 2, 3 1 4, 5, 6

2 7, 8

3 9

4 10, 11 5 12, 13, 14, 15 6 16, 17

(31)

Osservazione 4.9.Sianoa, b ∈ P con a < b. Allora prof(a) > prof(b).

Dimostrazione. Sianoa ∈ Max P^(k) eb ∈ Max P^(j) conj ≥ k. Allora P^(j) ⊂ P^(k), e quindib ∈ P^(k), in contraddizione alla massimalit `a dia inP^(k).

Osservazione 4.10.Sianoa, b ∈ P con a ⊳ b. Per la prop. 4.9. abbiamo prof(a) > prof(b), ma pu`o accadere che prof(a) 6= prof(b) + 1, come mostra l’esempio

1 3

4

2

in cui4 ⊳ 2, ma prof(2) = 0, prof(4) = 2.

Lemma 4.11. Sianok ∈ N + 1 ed a ∈ P^(k). Allora esisteb ∈ Max P^(k−1) cona < b.

Sea ∈ Max P^(k), alloraa ⊳ b.

Dimostrazione.

(1) Applicando la prop. 1.13 all’insieme parzialmente ordinatoP^(k−1) vediamo che esiste b ∈ Max P^(k−1) tale che a ≤ b. Per ipotesi a ∈ P^(k)= P^(k−1)\ Max P^(k−1), per cuia 6= b.

(2) Siaa ∈ Max P^(k). Vogliamo dimostrare chea ⊳ b. Assumiamo che non sia cos`ı . Allora esistex ∈ P tale che a < x < b. Per l’oss. 4.9 allora

k = prof(a) > prof(x) > prof(b) = k − 1 ma ci`o non `e possibile.

Proposizione 4.12. Sianok ∈ N + 1 ed a ∈ P^(k). Allora esistono b_k−1∈ Max P^(k−1), . . . , b₀ ∈ M axP⁽⁰⁾

tali chea < b_k−1⊳ · · · ⊳ b₀.

Sea ∈ Max P^(k), allora anchea ⊳ b_k−1. Dimostrazione. Immediato dal lemma 4.11.

Corollario 4.13. Sianok ∈ N ed a ∈ P^(k). Alloraalt([a, ∞]) ≥ k.

Dimostrazione. L’enunciato `e banale perP⁽⁰⁾e segue dalla prop. 4.12 perk > 0.

Proposizione 4.14. Siaa ∈ P . Allora prof(a) = alt([a, ∞]).

Dimostrazione. Siano k := prof(a) ed h := alt([a, ∞]). Dobbiamo dimostrare che h = k. Per il cor. 4.13 abbiamo h ≥ k. Supponiamo per assurdo che h > k. Allora esiste una catena C di k + 2 elementi nell’insieme parzialmente ordinato[a, ∞]. Per la nota 4.7

(32)

C ⊂ [a, ∞] ⊂ Max P⁽⁰⁾∪ · · · ∪ Max P^(k). Siccome ogniMax P^(j) `e

un’anticatena,C può contenere al massimo un elemento di Max P^(j) per ognij. Ciò non è possibile, perché |C| = k + 2.

Definizione 4.15.Una funzioner : P −→ N si chiama un rango (o una funzione di rango) diP , se soddisfa le due seguenti condizioni, per ognia, b ∈ P :

(1) a ∈ Max P =⇒ r(a) = 0.

(2) a ⊳ b =⇒ r(a) = r(b) + 1.

Se P possiede un rango, diciamo che P `e un insieme parzialmente ordinato gerarchicamente completo. `E anche chiaro che in tal caso la funzione di rangor `e univocamente determinata.

Teorema 4.16. Sono equivalenti:

(1) Sea, b ∈ P con a ⊳ b, allora prof(a) = prof(b) + 1.

(2) prof `e un rango di P .

(3) P `e gerarchicamente completo.

(4) Per ogni elemento fissato a ∈ P tutte le catene massimali in [a, ∞] hanno lo stesso numero di elementi.

Dimostrazione.

(1)=⇒ (2) : Chiaro perch´e prof(a) = 0 per ogni a ∈ Max P . (2)=⇒ (3) : Chiaro.

(3)=⇒ (4) : Siano a ∈ P ed am < . . . a₀ una catena massimale in [a, ∞]. `E chiaro che ci`o implicaa₀∈ Max P ed

a = am ⊳ · · · ⊳ a0. r sia un rango di P . Per definizione allora r(a₀) = 0, r(a₁) = 1, . . . , r(a) = r(am) = m. Vediamo cos`ı che m = r(a). Ci`o mostra che ogni catena massimale di [a, ∞] possiede esattamenter(a) + 1 elementi.

(4)=⇒ (1) : Siano a, b ∈ P con a ⊳ b. Assumiamo, per assurdo, che a ∈ Max P^(k), b ∈ Max P^(j)conk ≥ j + 2. Per la prop. 4.12 esiste una catenab = bj⊳ b_j−1⊳ · · · ⊳ b0conb0 ∈ Max P , la quale, se alla sinistra aggiungiamoa, diventa una catena massimale di [a, ∞]

di lunghezzaj + 2. Sempre per la prop. 4.12 esiste però anche una catenaa = ak⊳ a_k−1⊳ · · · ⊳ a₀cona₀ ∈ Max P . Anche questa è una catena massimale di[a, ∞], però di lunghezza k + 1 ≥ j + 3, in contraddizione all’ipotesi.

Proposizione 4.17.P sia gerarchicamente completo e a, b ∈ P . Allora tutte le catene massimali in[a, b] hanno lo stesso numero di elementi.

Dimostrazione. Possiamo assumere che a < b, perch´e altrimenti l’enunciato `e banale.

Sia cm < · · · < c₀ una catena massimale in [a, b]. È chiaro che ciò implica chea = c_m⊳· · ·⊳c₀= b. Siccome P è gerarchicamente completo, si haprof(a) = prof(b) + m, e quindi m = prof(a) − prof(b).

Definizione 4.18. Pôpp sia l’insieme parzialmente ordinato (P, ≤ôpp) cona ≤ôpp b ⇐⇒ b ≤ a.

(33)

Definizione 4.19.SiaP definito come nell’oss 4.10:

1 3

4

2

P P soddisfa le seguenti due condizioni:

(1) Per ogni a, b ∈ P tutte le catene massimali in [a, b] hanno lo stesso numero di elementi.

(2) Per ogni a ∈ P tutte le catene massimali in [−∞, a] hanno lo stesso numero di elementi.

Ci`o mostra che questa due condizioni non sono sufficienti a garantire che un insieme parzialmente ordinato sia gerarchicamente completo.

E chiaro anche (dalla figura seguente o dal punto (2) insieme al teore-` ma 4.16.) cheP^opp `e gerarchicamente completo:

1 3

4

2 P^opp

Nella def. 4.15. dovremmo quindi parlare pi `u precisamente di rango superiore.

Osservazione 4.20.Sia| Max P | = 1. Allora sono equivalenti:

(1) P `e gerarchicamente completo.

(2) Per ogni a, b ∈ P tutte le catene massimali in [a, b] hanno llo stesso numero di elementi.

Dimostrazione.

(1)=⇒ (2) : Prop. 4.17.

(2)=⇒ (1) : Ci`o segue dal teorema 4.16, perch´e se Max P = {b}, allora[a, ∞] = [a, b] per ogni a ∈ P .

Definizione 4.21. Pera ∈ P sia V (a) l’insieme dei superiori diretti di a ed N (a) l’insieme degli inferiori diretti di a, ovvero

V (a) = {b ∈ P | a ⊳ b}

N (a) = {b ∈ P | b ⊳ a}

Corollario 4.22. Sono equivalenti:

(1) P `e gerarchicamente completo.

(2) Per ognik ∈ N + 1 e per ogni a ∈ P vale a ∈ Max P^(k) =⇒ V (a) ⊂ Max P^(k−1). (3) Per ognik ∈ N ed ogni a ∈ P vale

a ∈ Max P^(k) =⇒ N (a) ⊂ Max P^(k+1).

(34)

Dimostrazione. Chiaro dalla condizione (1) nel teorema 4.16.

Definizione 4.23. Definiamo il completamento gerarchico bP di P nel modo seguente. Per ogni coppiaa, b di elementi di P con a ⊳ b ed s := prof(a) − prof(b) ≥ 2 inseriamo s − 1 nuovi elementi tra a e b.

Indichiamo gli elementi nuovi talvolta con cerchietti pieni:

Questi nuovi elementi formano una catena tra a e b in cui l’ordine parziale `e definito in modo ovvio. `E chiaro che cos`ı bP diventa un insieme parzialmente ordinato in cui l’ordine parziale ristretto aP coincide con la relazione ≤ data su P . Per a ∈ P inoltre prof(a, in bP ) = prof(a, in P ), mentre a ⊳ b in P implica a ⊳ b in bP solo se si ha prof(a) = prof(b) + 1.

Sea⊳b con a ∈ Max P^(k), b ∈ Max P^(j), i nuovi elementi si inseriscono ai livelliMax bP^(k−1), . . . , Max bP^(j+1). `E anche chiaro che bP `e gerarchicamente completo.

(35)

Situazione 5.1. R sia un reticolo.

Se R `e finito, denotiamo con1^Rl’elemento massimo e con0^Rl’elemento minimo di R.

Un reticolo sia per definizione sempre6= ∅, quindi anche R 6= ∅.

Definizione 5.2. R si chiama distributivo, se per a, b, c ∈ R valgono le uguaglianze

(D₁) a ∧(b ∨ c) = (a ∧ b) ∨ (a ∧ c).

(D₂) a ∨(b ∧ c) = (a ∨ b) ∧ (a ∨ c).

Proposizione 5.3. Sono equivalenti:

(1) R `e distributivo.

(2) R soddisfa la condizione D₁ nella def. 5.2.

(3) R soddisfa la condizione D₂ nella def. 5.2.

Dimostrazione. Per simmetria `e sufficiente dimostrare(2) =⇒ (3).

Assumiamo quindi che in R valga la propriet `a D1. Allora per a, b, c ∈ R abbiamo

(a ∨ b) ∧ (a ∨ c)^D= ((a ∨ b) ∧ a) ∨ ((a ∨ b) ∧ c) = a ∨ ((a ∨ b) ∧ c)¹ ^D=¹

= a ∨ ((a ∧ c) ∨ (b ∧ c)) = a ∨ (b ∧ c).

Definizione 5.4. R si chiama modulare, se per a, b, a0 ∈ R si ha a₀ ≤ a =⇒ a ∧ (a0∨ b) = a0∨ (a ∧ b).

Osservazione 5.5.Un reticolo distributivo `e modulare.

Dimostrazione. Infatti per a, b, a₀ ∈ R con a₀≤ a abbiamo a ∧(a₀∨ b) = (a ∧ a0) ∨ (a ∧ b) = a₀∨ (a ∧ b).

Proposizione 5.6. G sia un gruppo. Allora il reticolo dei sottogruppi normali di G (che coincide con il reticolo di tutti i sottogruppi di G se G `e abeliano) `e modulare.

Dimostrazione. Bozzini, pagg. 43-44.

Osservazione 5.7. Il reticolo di tutti i sottogruppi di un gruppo `e in generale non modulare. Ci`o accade ad esempio per il gruppo A₄:

sottogruppi(A₄)

(36)

Questo reticolo non `e modulare perch´e contiene

come sottoreticolo.

Dimostrazione. Bozzini, pag. 44.

Teorema 5.8. R sia modulare ed a, b ∈ R. Allora le applicazioni ϕ: [a ∧ b, a] −→ [b, a ∨ b]

x 7−→ x ∨ b e ψ: [b, a ∨ b] −→ [a ∧ b, a]

y 7−→ a ∧ y sono isomorfismi di reticoli con ψ = ϕ⁻¹.

Se R è finito, questa propriet à implica a sua volta la modularit à di R.

Dimostrazione. Bozzini, pag. 42, Aigner, pagg. 82-83, Birkhoff, pagg.

14 e 41.

Corollario 5.9. R sia modulare ed a, b ∈ R. Allora a ⊳ a ∨ b ⇐⇒ a ∧ b ⊳ b

Definizione 5.10. R si dice i-semimodulare (o semimodulare inferior- mente) se per a, b ∈ R vale l’implicazione a ⊳ a ∨ b =⇒ a ∧ b ⊳ b.

R si dice s-semimodulare (o semimodulare superiormente) se per a, b ∈ R vale l’implicazione a ∧ b ⊳ b =⇒ a ⊳ a ∨ b.

R si chiama semimodulare se `e i-semimodulare oppure s-semimodulare.

Esempio 5.11.Il reticolo

`e i-semimodulare, ma non modulare. Il reticolo a ∨ b

b a

a ∧ b non `e i-semimodulare.

(37)

Osservazione 5.12. R sia finito ed x ∈ Max R⁽¹⁾. Sia a ∈ R ed a x.

Allora a ∨ x= 1^R.

Dimostrazione. Infatti x ≤ a ∨ x, quindi a ∨ x 6= 1^R implicherebbe x= a ∨ x. Ma da ci`o seguirebbe a ≤ x, in contraddizione all’ipotesi.

Proposizione 5.13. R sia finito. Allora sono equivalenti:

(1) R `e i-semimodulare.

(2) Per ogni x ∈Max R⁽¹⁾ ed ogni b ∈ R vale l’implicazione b x =⇒ x ∧ b ⊳ b.

Dimostrazione.

(1)=⇒(2) Per l’oss. 5.12 abbiamo b ∨ x = 1^Re x ⊳ b ∨ x. Dalla def. 5.10 segue b ∧ x ⊳ b.

(2)=⇒(1) Siano a, b ∈ R con a ⊳ a ∨ b. Allora a 6= 1R e b a. Perci`o esiste x ∈Max R⁽¹⁾tale che a ≤ x, ma b x. Per ipotesi x ∧ b ⊳ b.

D’altra parte a ≤(a ∨ b) ∧ x ≤ a ∨ b, mentre (a ∨ b) ∧ x 6= a ∨ b perché altrimenti b ≤ x. Siccome per ipotesi a ⊳ a ∨ b, ciò implica (a ∨ b) ∧ x = a. Perciò a ∧ b = (a ∨ b) ∧ x ∧ b = x ∧ b, cosicché a ∧ b ⊳ b.

Teorema 5.14 (Teorema di Jordan-H ¨older). R sia finito ed i-semimodulare. Allora R `e gerarchicamente completo.

Dimostrazione. Per l’oss. 4.20 dobbiamo dimostrare che per ogni a, b ∈ R tutte le catene massimali in[a, b] hanno la stesa lunghezza. `E sufficiente dimostrare per induzione su n il seguente enunciato Eⁿper ogni n ∈N:

En: Se a, b ∈ R e se[a, b] contiene una catena massimale di lunghezza n, allora tutte le catene massimali di [a, b] hanno la stessa lunghezza n.

n= 0 : Chiaro.

n= 1 : [a, b] contiene una catena massimale di lunghezza 1 se e solo se a ⊳ b, e in questo caso l’enunciato `e evidente.

n −→ n+ 1 : Siano a, b ∈ R e

a ⊳ x₁⊳ · · · ⊳ xn−2⊳ u ⊳ b a ⊳ y₁⊳ · · · ⊳ yn−2⊳ v ⊳ b

due catene massimali di[a, b]. Allora u ∨ v = b, cosicch´e u, v ⊳ u ∨ v, e la i-semimodularit `a di R implica u ∧ v ⊳ u e u ∧ v ⊳ v.

b v u

u ∧ v

a

(38)

Consideriamo adesso una qualsiasi catena C massimale di [a, u ∧ b]

(una tale catena esiste sicuramente); sia s la sua lunghezza.

Aggiungendo u a C otteniamo una catena massimale in[a, u], e siccome anche a ⊳ x₁⊳ · · · ⊳ u `e una catena massimale di [a, u], l’ipotesi di induzione implica s = n − 1. Ma ci`o significa che aggiungendo v a C troviamo una catena massimale di [a, v] di lunghezza m, e l’ipotesi di induzione implica n= m.

Corollario 5.15. R sia finito e modulare. Allora R `e gerarchicamente completo.

Teorema 5.16. R sia finito. Allora sono equivalenti:

(1) R `e modulare.

(2) R `e i-semimodulare ed s-semimodulare.

Dimostrazione. Aigner, pag. 88, Gr ¨atzer, pagg. 227-228.