Insiemi ordinati e reticoli - Imati

MATematica – Nozioni di base
%
Capitolo B55:
Insiemi ordinati e reticoli
Contenuti delle sezioni
a. Nozioni di base per gli insiemi ordinati p.1 b. Catene e anticatene p.7 c. Reticoli p.8 d.
Reticoli booleani p.11 e. Digrafi di partizioni p.16 f. Omomorfismo e isomorfismo tra digrafi p.19
B55:0.01 In questo capitolo studiamo con una certa ampiezza gli insiemi ordinati discreti, strutture
che presentano una grande varietà di tipi, molti dei quali giocano ruoli di grande importanza sia per
la matematica che per le sue applicazioni.
B55:a. Nozioni di base per gli insiemi ordinati
B55:a.01 Ricordiamo che per insieme ordinato si intende un insieme munito di una relazione ⟨P, ≼⟩
che gode delle tre proprietà seguenti
– riflessività: per ogni x ∈ P si ha x ≼ x;
– antisimmetria: per ogni coppia x, y ∈ P , da x ≼ y e y ≼ x segue x = y;
– transitività: per ogni terna x, y, z ∈ P , se accade che x ≼ y ≼ z, allora x ≼ z.
Un tale sistema (P, ≼) è chiamato anche ordine, ordine parziale, insieme parzialmente ordinato, o, con uno
sbrigativo termine gergale inglese, poset.
Denotiamo con Poset la classe dei posets e PosetF la classe dei posets finiti.
La relazione x ≼ y si legge “x precede o coincide con y”, oppure “x precede in senso lato y”.
B55:a.02 Abbiamo già incontrato vari posets: insiemi numerici con la relazione ≤, collezioni di insiemi
con la relazione di inclusione, partizioni, ... . Abbiamo poi visto che per i posets finiti è vantaggioso
servirsi delle corrispondenti raffigurazioni mediante digrafi.
Anche l’insieme delle relazioni d’ordine esplicite (e degli equivalenti grafi ordinati) contiene una grande
varietà di elementi e riveste grande importanza per i molteplici collegamenti con altre strutture discrete
e per le numerose applicazioni.
Sviluppiamo ora alcune nozioni generali sui posets, senza occuparci della costruibilità.
B55:a.03 Consideriamo un poset P = ⟨P, ≼⟩ e un elemento x ∈ P .
Si dicono minoranti di x tutti gli elementi y ∈ P t.c. y ≼ x.
Si dicono invece maggioranti di x tutti gli elementi y ∈ P t.c. x ≼ y.
Denotiamo risp. xM nr e xM jr gli insiemi dei minoranti e dei maggioranti di x.
Si parla anche di minoranti e maggioranti in P di un sottoinsieme S ⊆ P : sono risp. gli elementi di P
che sono preceduti o precedono in senso lato tutti gli elementi di S.
2010-02-12
B55: Insiemi ordinati e reticoli
1
Alberto Marini
Denotiamo risp. S M nr e S M jr gli insiemi dei minoranti e dei maggioranti di S.
Evidentemente S M nr = ∩s∈S sM nr e S M jr = ∩s∈S sM jr .
B55:a.04 Si dice elemento minimale di P ogni elemento privo di minoranti: formalmente è un m ∈
P ST y ≼ m ⇒ y = m.
Si dice elemento massimale di P ogni elemento privo di maggioranti: formalmente è un M ∈ P ST M ≼
y ⇒ y = M.
Denotiamo risp. PM nl e PM xl l’insieme degli elementi minimali e massimali del poset P.
Un poset dotato di elementi minimali si dice inferiormente limitato.
Un poset dotato di elementi massimali si dice superiormente limitato.
Un poset dotato sia di elementi minimali che di massimali si dice limitato.
Collettivamente gli elementi minimali ed i massimali si dicono elementi estremali.
B55:a.05 Se un poset ha un unico elemento minimale, questo viene detto minimo o zero del poset e si
denota min(P).
Se un poset ha un unico elemento massimale, questo viene detto massimo o unità del poset e si denota
max(P).
In molte considerazioni locali per lo zero e l’unità di un poset generico si usano notazioni come 0 e 1,
oppure come 0 e 1.
B55:a.06 Le nozioni di elemento minimale, elemento massimale, minimo e massimo relative alla relazione ≼ si possono definire anche per un generico sottoinsieme S di un poset. Inoltre a ciascuno di
questi S può essere o meno un sottoinsieme limitato inferiormente, limitato superiormente o limitato
tout court.
B55:a.07 Spesso, insieme alla relazione ≼, è opportuno considerarne altre da essa derivabili. Innanzi
tutto si introduce la ≺ chiedendo che sia x ≺ y sse x ≼ y e x ̸= y; questa può leggersi “precede
in senso stretto” o “precede” ed è una relazione d’ordine-stretto, relazione antiriflessiva, antisimmetrica
e transitiva. Si hanno poi le negazioni delle relazioni precedenti, ̸≼ e ̸≺. Inoltre si introducono per
riflessione altre quattro relazioni:
≽ definita da x ≽ y sse y ≼ x, cioè ≽:=≼∂ (che si può leggere “segue o coincide con”, oppure “segue
in senso lato”);
≻ per la quale x ≻ y sse y ≺ x sse x ≽ y e x ̸= y (che si può leggere “segue” oppure “segue in senso
stretto”);
le negazioni ̸≽ e ̸≻.
B55:a.08 Delle relazioni introdotte a partire dalla ≼, solo ≽ è una relazione d’ordine; questa constatazione induce ad introdurre il poset duale o poset riflesso o poset trasposto di P, P := ⟨P, ≽⟩. Il
passaggio al poset duale è involutorio, cioè il poset duale di un poset duale coincide con quello di
partenza: (P ) = P .
La simmetria fra un poset ed il suo duale consente di trattare contemporaneamente le costruzioni e le
proprietà delle due strutture. Accade allora di individuare costruzioni e proprietà che non cambiano
quando si passa da un poset al suo duale: esse sono dette invarianti per dualità o autoduali. Si hanno
invece coppie di costruzioni e coppie di proprietà che si scambiano tra di loro quando si passa da un
poset al suo duale: queste sono dette costruzioni e proprietà (mutuamente) duali. È spesso utile chiarire
queste situazioni, in quanto si consegue maggiore chiarezza nella visione dei fatti, si possono trattare
agevolmente alcune costruzioni ed alcune proprietà riconducendosi alle rispettive duali e si garantisce
2
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
l’autodualità di proprietà che derivano da proprietà notoriamente autoduali. In queste occasioni si
dice che si utilizza il principio di dualità per i posets.
B55:a.09 Si verifica facilmente che sono mutuamente duali le nozioni di minorante e maggiorante, di
minimale e massimale, di minimo e massimo; sono duali anche le proprietà di limitatezza inferiore e
limitatezza superiore. È invece invariante per dualità la limitatezza.
B55:a.10 Individuati due elementi x ed y del poset P, si possono verificare quattro situazioni mutuamente esclusive: può accadere che x ≺ y, che y ≺ x, che si constati che x = y o, infine, che non valga
nessuna delle relazioni precedenti. Nell’ultimo caso si dice che x ed y sono non comparabili per ≼; nei
primi tre casi si dicono comparabili o confrontabili.
B55:a.11 Si dice ordine totale, insieme totalmente ordinato, o anche insieme linearmente ordinato, un poset
nel quale gli elementi di ogni coppia risultano comparabili.
Il tipico insieme totalmente ordinato con un numero finito n di elementi è l’insieme degli interi da 1 a
n ordinati dalla usuale relazione ≤. Ogni altro poset totalmente ordinato di n elementi è isomorfo al
precedente.
In astratto un tale poset viene chiamato catena di cardinalità n e viene indicato con Chn .
Tre importanti insiemi totalmente ordinati numerabili sono ⟨N, ≤⟩, ⟨Z, ≤⟩ e ⟨Q, ≤⟩.
⟨R, ≤⟩ è invece un insieme totalmente ordinato non numerabile.
Si trova facilmente che il duale di un insieme totalmente ordinato è anch’esso un poset di questo tipo.
In effetti le proprietà di confrontabilità e non confrontabilità sono invarianti per dualità.
B55:a.12 Consideriamo due posets P = ⟨P, ≺⟩ e Q = ⟨Q, ⊑⟩. Si dice prodotto cartesiano di P e Q e si
indica con P × Q := ⟨P × Q, ≼ × ⊑⟩ il poset costituito dalle coppie ⟨x, u⟩ con x ∈ P e u ∈ Q per le
quali si ha ⟨x, u⟩(≼ × ⊑)⟨y, v⟩ sse x ≼ y e u ⊑ v.
Componendo posets totalmente ordinati si ottengono prodotti di posets relativamente semplici. Si
considerino ad es. ⟨3, ≤⟩ × ⟨3, ≤⟩ e ⟨2, ≤⟩ × ⟨4, ≤⟩.
Si considerino anche P × P, N × N, Z × Z, Q × Q ed R × R.
B55:a.13 Prop.
Se P = ⟨P, ≼⟩ e Q = ⟨Q, ⊑⟩ sono posets totalmente ordinati non banali, il loro
prodotto cartesiano non è totalmente ordinato.
Dim.: Se x ≺ y e u ⋣ = v, ⟨x, y⟩ e ⟨u, v⟩ non sono comparabili
B55:a.14 Siano x, y elementi di un poset ⟨P, ≼⟩; diciamo che y copre x, o che x precede immediatamente
y, e scriviamo y ≺I x, sse x ≺ y e nessun z ∈ P soddisfa la x ≺ z ≺ y.
In un poset P dotato di minimo, gli elementi che coprono questo elemento si chiamano atomi; Atom(P)
denota il loro insieme.
In un poset Q dotato di massimo, gli elementi coperti da questo elemento si dicono coatomi; Coatm(Q)
denota il loro insieme.
B55:a.15 Si dice sottoposet di P = ⟨P, ≼⟩ ∈ Poset ogni Q = ⟨Q, ⊑⟩ con Q ⊆ P e ⊑ relazione ottenuta
riducendo ≼ a Q × Q. In tal caso si scrive P ≤P oset Q.
Si dice intervallo del poset P = ⟨P, ≼⟩ compreso tra x e z, l’insieme {y ∈ P x ≼ y ≼ z}. Gli elementi
x e y sono detti estremità dell’intervallo. Un tale insieme si indica con una notazione del tipo [x, y]P .
Questo insieme munito della riduzione della relazione ≼ è sottoposet di P.
2010-02-12
B55: Insiemi ordinati e reticoli
3
Alberto Marini
Osserviamo che si sono definiti intervalli di tipo chiuso, in quanto contengono i propri estremi; si
potrebbero anche considerare intervalli di tipo aperto o semiaperto.
B55:a.16 Consideriamo ora i posets finiti, ricordando che essi sono equivalenti ai digrafi ordinati e
quindi possono essere raffigurati efficacemente nel piano.
A causa della riflessività, ogni nodo di un digrafo ordinato è dotato di cappio, mentre per la transitività,
la presenza di due archi consecutivi ⟨q, r⟩ ed ⟨r, s⟩, implica che sia presente anche l’arco ⟨q, s⟩, cioè
l’arco che va dall’estremità iniziale del primo arco all’estremità finale del secondo.
Quindi le regole generali per le raffigurazioni nel caso dei digrafi ordinati comportano la presenza di
numerosi archi “pleonastici”: i cappi presenti in tutti i nodi e gli archi riconducibili a cammini di
lunghezza superiore o uguale a 2 non costituiscono elementi essenziali della raffigurazione, in quanto
si possono desumere facilmente dai rimanenti.
Ne segue la possibilità di una raffigurazione essenziale dei digrafi ordinati ottenuta da quella che segue le
indicazioni generali eliminando (e considerando sottintesi) cappi e archi riconducibili a cammini.
La antisimmetria non consente che nei digrafi ordinati siano presenti circuiti che non si riducano ad
un cappio. Infatti la presenza di due archi l’uno riflesso dell’altro contraddice l’antisimmetria. Se poi
⟨
⟩
esistesse un circuito ⟨q0 , q1 ⟩ ,..., ⟨qs−2 , qs−1 ⟩,⟨qs−1 , q0 ⟩ di lunghezza superiore a 2, per la transitività,
dovrebbe essere presente anche l’arco ⟨q0 , qs−1 ⟩ e quindi sarebbero presenti due archi mutuamente
riflessi.
Questo consente raffigurazioni nelle quali gli archi hanno orientazioni che si discostano meno di 90◦
da una fissata: questa potrebbe essere quella che va dall’alto in basso, quella che va da sinistra verso
destra o una delle due opposte. In una tale raffigurazione si può evitare di segnare il senso delle frecce.
Una raffigurazione cosı̀ ottenuta è decisamente più semplice e chiara di quelle costruite seguendo le
regole generali ed è detta raffigurazione o diagramma di Hasse.
Ad esempio una raffigurazione come:
....
....
...
...
.....................
.....................
...
...
...
...
....
.....
.
.
.
...
.
..
...
.
.
.
.
.
.................................................................................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
............... ............
.
.....
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......
.......
....
......
....... .
.............
....
.......
.........
.... ......................
..............
.....
.................
.....
..............
.........
.......
.....
....... .......................... ..
.
.
.
.
.
.
.
.
.
.
.
.
.........
.
.
.
.
.......
.
.
.
.
.
.
.
.
.
.
.
....
...
..
..
....... ........ .......
...
.
.
... .......................................
.
.
.
.....
.
.............
.....................................................................................................................................................................................................................................................
.
...............
..
........... ..
.
................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...... .........
.
.
....... ......
..................
.....
............. .......
.......
.....
....... ...........
............... ..............
.....
.
......... ..........
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......
............
.
.
....
.
.
................. ..................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
....
.......
.......
....... .......................... ..........................
.......
....... .... ................... .
.......
......................
................................................................................................................
.......
..... ............... .
..........
.
.
.............
.....
............. .................... ..............
.....
............. .. .......... ... ..........
.....
................ ........... ..........
.....
... .................................. ..........
.....
....................... .......
.....
.................
..............................
..... .
......................... ......
.
..
..............
.............
.............
.........
.
.....
.
.
.
.
.
.
.....
...... ........
.....
.
.
.
.
.
.
.....
.
.
.
.
.
.
.
.....
.....
..................
.....
.
.
.
.
.
.....
...
.....
....... .
.....
.......
..... .............
...
....... ..........
.
.
.
...
.....
.
.... . .....
..................
....
•
•
•
•
•
•
•
•
può essere vantaggiosamente rimpiazzata da:
In genere per i digrafi ordinati si utilizzano solo diagrammi di Hasse. Tra questi si adottano spesso
quelli con presuppongono archi volti dal basso verso l’alto; meno spesso diagrammi di Hasse dei tipi
alto → basso e sinistra → destra; raramente quelli del tipo destra → sinistra.
B55:a.17 Prop.
Ogni sottoinsieme S non vuoto di un poset finito contiene almeno un elemento
minimale e, dualmente, almeno un elemento massimale.
4
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
Dim.: Proviamo l’esistenza di un elemento minimale delineando un procedimento che consente di individuare tale oggetto.
Si sceglie un elemento qualsiasi x1 ; con un numero finito di confronti si stabilisce se esso è minimale; in
caso positivo il procedimento è concluso; in caso contrario si è trovato un x2 ≺ x1 e si riprende l’esame
di minimalità da x2 ; per la finitezza di S il procedimento si conclude sicuramente con il reperimento
di un minimale
B55:a.18 Prop. Per ogni elemento di un poset finito si possono individuare effettivamente tutti gli altri
elementi che lo precedono immediatamente e, dualmente, tutti quelli che lo seguono immediatamente.
Dim.: Si possono determinare tutti i minoranti di x e del loro insieme si possono determinare tutti i
massimali
In altre parole, per ogni poset finito si può effettivamente individuare la relazione di copertura. Si
osservi che nella raffigurazione di Hasse sono collegati solo coppie di nodi uno dei quali copre l’altro.
B55:a.19 Prop. La relazione di copertura per posets numerabili come ⟨N, ≤⟩, [z : +∞), (−∞ : z]
(z ∈ Z) ed ⟨Z, ≤⟩ è quella che collega interi consecutivi: w <I z ⇐⇒ z = w + 1
Viceversa ⟨Q, ≤⟩ è un poset numerabile privo di relazione di copertura: infatti dati due numeri razionali
si trova sempre un razionale compreso fra di essi. Neppure ⟨R, ≤⟩ possiede relazione di copertura, in
quanto dati due numeri reali si trova sempre un reale compreso fra di essi.
Per un poset finito con minimo e massimo si sanno individuare effettivamente anche Atom(P ) e
Coatm(P ). Il poset ⟨N, ≤⟩ ha 0 come elemento minimo ed 1 come unico atomo, mentre manca di
massimo e di coatomi; ⟨Z, ≤⟩ non ha nessuno di questi elementi particolari: Z è illimitato sia inferiormente che superiormente.
B55:a.20 Si dicono digrafi graduati i digrafi ordinati i cui nodi si possono distribuire su successivi livelli
in modo che due nodi si trovano nella relazione di copertura sse appartengono a due livelli consecutivi.
Formalizzando, G := ⟨Q, U ⟩ si dice digrafo graduato sse P artordQ ∋ ⟨Q1 , ...Qr ⟩ tale che
Q1 U ⊆ Q2 , Q2 U ⊆ Q3 , ..., Qr−1 U ⊆ Qr .
Denotiamo con DgrfGrd la classe dei digrafi graduati.
Interessano soprattutto digrafi graduati connessi; in un digrafo graduato non connesso la attribuzione
dei livelli ai nodi di una componente connessa potrebbe essere modificata con aumenti o diminuzioni
complessive arbitrarie e prive di interesse.
I digrafi degli ordini totali finiti e quelli di ⟨N, ≤⟩ e ⟨Z, ≤⟩ sono evidentemente digrafi graduati e su
ciascuno dei loro livelli si trova un solo nodo.
2010-02-12
B55: Insiemi ordinati e reticoli
5
Alberto Marini
Tra i più semplici digrafi ordinati non graduati vi sono:
•
..
..........
... ........
.....
...
.....
..
.
.....
.....
...
.....
..
.
.....
..
.....
.
.....
..
.
.....
..
.....
.
.....
..
.
.....
..
.
...
..
...
.
..
..
.
...
..
.
...
...
...
.....
...
.
...
...
.
...
.
.
...
...
.
.
.
.
...
...
.
.
.
.
...
....
...
.....
...
.....
...
.....
.....
...
.
.
.
.
...
.....
...
.....
...
.....
... .........
........
..
•
•
.
.........
... ........
.....
...
.....
...
.
.
.....
.....
...
.....
...
.
.
...
..
.
.
.
..
.
.....
.
.
...
.....
...
...
...
...
...
.
.
...
...
.
.
...
.
.
...
...
.
.
.
.
...
...
...
.....
... ........
... .....
....
•
•
•
•
•
•
•
•
•
•
.....
... ......
... ........
.....
...
.....
...
.
.
.....
...
.....
....
...
.
.
..
....
.
.
..
.
....
.
...
.
.
...
.
.. ...
.
...
.
.. ....
..
.
.
...
..
.
.
.
.
.
...
..
..
.
.
.
.
.
...
..
..
.
.
.
.
.
...
..
...
...
...
...
...
...
...
...
...
...
... .....
....
... ...
...
... ..
...
....
...
..
...
.
....
.
..
.
.....
.
.
.....
...
.....
...
.....
...
.....
...
.....
.
.
.
..... ..
........
.
•
•
•
•
•
•
•
Inoltre non è possibile considerare graduati ⟨Q, ≤⟩ e ⟨R, ≤⟩.
6
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
B55:b. Catene e anticatene
B55:b.01 Un sottoinsieme totalmente ordinato di un poset è chiamato catena. Un sottoinsieme costituito
da elementi mutuamente incomparabili è detto anticatena.
Si dice lunghezza di una catena finita il numero dei suoi elementi diminuito di 1.
B55:b.02 Un poset si dice localmente finito sse ogni suo intervallo è finito. Denotiamo PosetLf la classe
di questi posets.
La nozione di intervallo è autoduale; quindi lo è anche la proprietà di finitezza locale per i poset che
si basa su tale nozione. In altre parole il duale di un poset localmente finito è anch’esso localmente
finito.
Ovviamente tutti i posets finiti sono localmente finiti. Sono tali anche ⟨N, ≤⟩ ed ⟨Z, ≤⟩; ogni loro
intervallo è isomorfo ad una catena C(n). Non sono invece localmente finiti ⟨Q, ≤⟩ e ⟨R, ≤⟩, in quanto
fra due numeri razionali (risp. reali) si trovano sempre infiniti razionali (risp. reali).
Anche per tutti i posets localmente finiti si può individuare effettivamente la relazione di copertura.
B55:b.03 Tra le catene di un poset localmente finito interessano in particolare le catene massimali, cioè
le catene C che non possono essere estese, cioè tali che ogni altro elemento del poset ambiente risulta
incomparabile con qualche elemento della C.
Interessano anche le catene con ripetizione di un poset, sequenze di elementi x0 , x1 ,...,xs t.c. x0 ≼ x1 ≼
... ≼ xs .
Un poset P = ⟨P, ≼⟩ si dice che soddisfa la condizione catenaria di Jordan-Dedekind o condizione catenaria
-JD sse tutte le sue catene massimali relative alla stessa coppia di estremità hanno la stessa lunghezza
finita. In particolare se tutte le catene massimali con a elemento massimo hanno la stessa lunghezza,
questa lunghezza è chiamata il rango di a e si indica rnk(a).
Evidentemente rnk : P → N:
B55:b.04 Prop. Sia P = ⟨P, ≤⟩ un poset dotato di zero 0 e soddisfacente la condizione catenaria -JD.
Per la sua funzione rango:
(i) rnk(0) = 0
(ii) a ≺I b =⇒ rnk(b) = rnk(a) + 1.
B55:2.05 Teorema (Dilworth 1950) Sia P = ⟨P, ≤⟩ un poset finito. Il minimo numero di catene disgiunte
la cui unione contiene tutti gli elementi di P è uguale al massimo numero di elementi costituenti
un’anticatena di P.
B55:b.06 Il duale a questo teorema é:
Teorema (Mirsky 1971) Se il poset finito P = ⟨P, ≤⟩ possiede una catena di m elementi ma nessuna
catena di m + 1, allora P è unione di m anticatene.
2010-02-12
B55: Insiemi ordinati e reticoli
7
Alberto Marini
B55:c. Reticoli
B55:c.01 In un poset due elementi x e y possono avere nessuno, uno o molti minoranti (o maggioranti)
comuni. Se esistono minoranti di x e y e se esiste un massimo di tali minoranti, questo elemento si
chiama l’infimo di x e y.
Dualmente si dice supremo di x e y il minimo dei loro maggioranti, se questo elemento esiste.
Più in generale si può parlare di infimo e supremo di un qualsiasi sottoinsieme S del poset.
Per l’infimo di x e y si usano notazioni come ∧
x ∧ y e inf(x, y); per il supremo notazioni∨come x ∨ y e
sup(x, y); per l’infimo di S si scrive inf(S) o
x; il supremo di S si denota sup(S) o
x.
x∈S
x∈S
In luogo di infimo si usano anche il termine incontro o l’inglese meet.
In luogo di supremo si usano anche il termine giunzione e l’inglese join.
B55:c.02 Si dice poset reticolato un poset in cui ogni coppia di elementi possiede un infimo ed un
supremo. Un poset completamente reticolato è un poset ogni sottoinsieme del quale possiede un infimo
ed un supremo. Denotiamo PosetLatt la classe dei posets reticolati e PosetLattC la classe dei posets
completamente reticolati.
I posets totali sono particolari posets reticolati, PosetT ⊂ PosetLatt.
B55:c.03 In un poset reticolato ⟨P, ≼⟩ il passaggio da due elementi x e y al loro infimo x ∧ y ed il
passaggio al loro massimo x ∨ y sono operazioni binarie.
Si può quindi prendere in considerazione la struttura algebrica costituita da ⟨P, ∧, ∨⟩. Essa viene detta
reticolo associato al poset reticolato.
Conviene ricordare che il termine reticolo viene tradotto in inglese con “lattice”, in francese da “treillis”,
in tedesco da “verband”.
È ovvio che le due operazioni del reticolo sono commutative ed idempotenti. Si vede facilmente anche
che esse sono associative: infatti, per ogni scelta x, y, z ∈ P , sia x ∧ (y ∧ z) che (x ∧ y) ∧ z individuano
il minimo dei maggioranti di {x, y, z}.
B55:c.04 Si osserva poi che x ≼ y ⇐⇒ x ∧ y = x ⇐⇒ x ∨ y = y.
Da questo si deduce che valgono le cosiddette proprietà di assorbimento in un reticolo:
∀x, y ∈ P : x ∨ (x ∧ y) = x
x ∧ (x ∨ y) = x,
B55:c.05 Si può compiere ora un cammino opposto, definendo la nozione di reticolo in termini puramente algebrici e quindi associando ad un generico reticolo un poset che risulta reticolato.
Definiamo reticolo una struttura algebrica della forma ⟨P, ∧, ∨⟩, ove ∧ e ∨ sono due operazioni per le
quali valgono le proprietà di
– commutatività,
– associatività,
– assorbimento.
Denotiamo Latt la classe dei reticoli e con LattF la classe dei reticoli finiti.
Ad una tale struttura algebrica si associa la relazione ≼ chiedendo:
x ≼ y ⇐⇒ x ∧ y = x ⇐⇒ x ∨ y = y.
Si dimostra che ≼ è una relazione riflessiva, antisimmetrica e transitiva e, più precisamente, che ⟨P, ≼⟩
è un poset reticolato. Esso si dice poset associato al reticolo.
8
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
B55:c.06 Si verifica anche che passando da un poset reticolato P = ⟨P, ≼⟩ al reticolo associato e
da questo al poset associato si ritorna al poset P. E analogamente trasformando un reticolo L nel
corrispondente poset reticolato e quest’ultimo nel reticolo associato si riottiene L.
Abbiamo quindi che le nozioni di poset reticolato e di reticolo sono logicamente equivalenti, cioè ogni
affermazione vera per uno di queste strutture può essere trasformata in una affermazione vera per
la struttura corrispondente, previo cambiamento di alcuni costrutti (come scambiare una relazione
d’ordine con una coppia di operazioni binarie). Si ha quindi un interessante esempio di criptomorfismo.
B55:c.07 Si tratta di una situazione che consente di portare sistematicamente le costruzioni e le
proprietà di una specie di struttura all’altra.
Quindi si parla di zero, unità, atomi e coatomi del reticolo.
Si parla anche di passaggio al reticolo duale: si tratta della trasformazione in cui i due operatori di
incontro e giunzione si scambiano i ruoli.
Un principio di dualità si può applicare anche ai reticoli. In particolare le operazioni di giunzione ed
incontro sono nozioni duali.
Osserviamo che un reticolo è limitato inferiormente sse è dotato di minimo.
Dualmente un reticolo è limitato superiormente sse è dotato di massimo.
Inoltre il minimo, se esiste, è elemento neutro per l’operazione ∨ ed è lo zero per la ∧; dualmente il
massimo, se esiste, è elemento neutro per l’operazione ∧ ed è lo zero per la ∨.
B55:c.08 Un sottoinsieme M di un reticolo L é chiamato sottoreticolo di L sse incontri e giunzioni di
elementi di N portano ad altri elementi di N , cioè sse è chiuso rispetto alle due operazioni binarie.
B55:c.09 Un reticolo L = ⟨L, ∧, ∨⟩ dotato di minimo 0 è chiamato atomico sse ogni elemento a ∈ L è
esprimibile come supremo di un insieme di elementi che coprono il minimo.
B55:c.10 Un reticolo L = ⟨L, ∧, ∨⟩ é chiamato distributivo sse per ogni terna x, y, z di suoi elementi
valgono le seguenti identità:
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) ,
x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) ,
Entrambe le identità possono essere generalizzate ad un arbitrario insieme di operandi:
m
∨
xi ∧
i=1
m
∧
n
∨
yj =
j=1
xi ∨
i=1
n
∧
m,n
∨
(xi ∧ yj ) ,
i,j
yj =
j=1
m,n
∧
(xi ∨ yj ) ,
i,j
B55:c.11 Un reticolo L = ⟨L, ∧, ∨⟩ è detto modulare sse per tutte le coppie di suoi elementi x, z avviene
che:
z ≤ x =⇒ ∀y ∈ P : x ∧ (y ∨ z) = (x ∧ y) ∨ c ,
B55:c.12 Un reticolo L = ⟨L, ∧, ∨⟩ è chiamato semimodulare sse per tutte le coppie di suoi elementi x, z:
x ∧ y ≺I x
2010-02-12
=⇒
∀y ∈ P : y ≺I x ∨ y ,
B55: Insiemi ordinati e reticoli
9
Alberto Marini
B55:c.13 Consideriamo un reticolo dotato di minimo 0 e di massimo 1 ed un suo elemento x. Si dice
complemento di x ogni x′ t.c. x ∧ x′ = 0 e x ∨ x′ = 1.
Evidentemente 0 è complemento di 1 e viceversa; inoltre se x′ è un complemento di x, allora x è un
complemento di x′ .
In un reticolo generico si hanno elementi con nessun complemento, elementi con un complemento ed
elementi con più complementi.
Un reticolo limitato è chiamato reticolo complementato sse ciascun suo elemento è dotato di uno e un
solo complemento.
Nella figura che segue accanto ad ogni elemento è scritto il numero dei suoi complementi. input fB55c13
B55:c.14 Consideriamo due posets P = ⟨P, ≼⟩ e Q = ⟨Q, ≤⟩. Si dice prodotto diretto di P e Q
P × Q := ⟨P × Q, ≼ × ≤⟩. Osserviamo che ≼ × ≤= {⟨p1 , p2 ⟩ ∈≼ , ⟨q1 , q2 ⟩ ∈≤: |⟨⟨p1 , q1 ⟩, ⟨p1 , q1 ⟩⟩.
Si verifica che anche P × Q è un poset.
⟨
⟩ ⟨
⟩ ⟨
⟩
Semplici esempi di prodotti diretti di poset sono N × N, ≤ × ≤ , Z × Z, ≤ × ≤ e R × R, ≤ × ≤ .
Si osserva che questi prodotti di poset totali sono posets non totali. Si tratta invece di posets reticolati.
In effetti si dimostra facilmente che il prodotto diretto di posets reticolati è un poset reticolato.
B55:c.15 Consideriamo gli insiemi delle potenze naturali dei due numeri primi 2 e 3 ordinate per
divisibilità ed il loro prodotto diretto.
Esso è isomorfo al poset di naturali potenze di 2 e 3 ordinati per divisibilità ⟨{i, j ∈ N :| 2i , 3j }, :⟩.
Questo poset a sua volta è isomorfo a ⟨N × N, ≤ × ≤⟩.
B55:c.16 Consideriamo ora l’insieme di interi positivi e la relazione di divisibilità che intercorre tra i
suoi elementi: evidentemente si tratta di una relazione d’ordine che ha la una seguente raffigurazione
di Hasse:
10
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
input fB55c16
Osserviamo che si tratta di un digrafo graduato numerabile nel quale al livello più basso, livello 0, si
trova il minimo 1 e al livello 1 degli atomi si trovano i numeri primi; al generico livello l si trovano i
positivi dati dal prodotto di l fattori primi, da contare con la propria molteplicità.
Questo reticolo si può considerare il prodotto diretto degli infiniti reticoli totali delle potenze naturali
dei numeri primi. Esso è isomorfo al reticolo delle sequenze finite di numeri naturali con le operazioni di
sup ed inf che a due sequenze ⟨a1 , ..., ar ⟩ e ⟨b1 , ..., bs ⟩ associano le sequenze di lunghezza m = max(r, s)
fomate risp. dai max(ai , bi ) e min(ai , bi ), convenendo di assumere aj = 0 per r < j ≤ m e bj = 0 per
s < j ≤ m.
B55:d. Reticoli booleani
B55:d.01 Con le raffigurazioni essenziali di digrafi reticolati si possono rappresentare efficacemente
molte situazioni riguardanti importanti entità matematiche ed oggetti o processi di elevato interesse
pratico.
In questo paragrafo e nel seguente presentiamo alcune di queste situazioni concernenti entità matematiche fondamentali, molto semplici da definire ma che hanno moltissime applicazioni.
B55:d.02 Se S è un insieme, si dice reticolo booleano dei sottoinsiemi di S ⟨P(S), ⊆⟩. Evidentemente
i reticoli booleani di due insiemi equicardinali sono isomorfi: infatti le modalità di costruzione degli
elementi di S non influisce sulla struttura del reticolo. Questo fatto implica anche che permutando gli
elementi di S si permutano i nodi del reticolo booleano lasciando invariata la sua struttura: in altre
parole il reticolo booleano è invariante per le permutazioni indotte dalle permutazioni degli elementi
di S e presenta forti simmetrie.
I reticoli booleani per gli insiemi S con cardinalità n = 1, 2, 3 sono piuttosto semplici:
{a}
.
....
...
..
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
∅
{a, b, c}
{a,... b}
..
... ....
... .....
...
...
...
...
.
.
...
...
...
..
.
...
.
..
...
.
.
...
...
.
...
.
.....
...
...
...
...
.
.
...
...
...
.
..
...
...
...
...
...
...
...
... .....
... ...
......
{a}
∅
........
........ .....
...... ... .........
...... ..
.....
...... ....
.....
.
.
.
.
.
.
.....
..
......
.....
..
......
.
.....
.
.
.
.
.
.
.....
.
....
.
.
.
.
.
.
.
..
.......
......
.
.
.
.
.
.......
.
.
.
.
.........
.
... ........ ........... .........
.
.
.
.
..... ......
.... ....
.....
.
.
..
.
.
.
.
..... .......
.........
.
.
.
.
..
.
.
.
.
.
.
.
.
.
... ...
... .......
...
... .........
.....
.........
...... ......... ...
.....
... ......
..... ...
..... ............
.. .......
.....
......
...........
.
.
.
.
.....
.
...
.....
......
...
.....
......
...
......
.....
......
...
.....
.. ............
.....
.
..... ... ......
..... .. ......
.............
.
{a, b}
{b}
{a}
{a, c}
{b}
{b, c}
{c}
∅
B55:d.03 I grafici si appesantiscono notevolmente se si aumenta n: infatti il numero di parti di S è
dato da 2n , quantità che cresce in misura molto rilevante con il crescere di n.
Cerchiamo di dare una raffigurazione dell’inclusione fra le parti di un insieme di 4 elementi. Si deve
tracciare un reticolo con 24 = 16 nodi ciascuno dei quali caratterizzato da un insieme con 0, 1, 2, 3 o
4 elementi.
Un primo problema pratico che si pone è quello della rappresentazione o codifica dei sottoinsiemi: per
individuarli conviene servirsi di stringhe binarie di lunghezza 4 corrispondenti alle sequenze indicatrici.
Ad es. se l’insieme è {a, b, c, d}, in luogo di {b} si scrive 0100, invece di {a, c} si usa 1010 ed invece di
2010-02-12
B55: Insiemi ordinati e reticoli
11
Alberto Marini
{a, c, d} si scrive 1011. In tal modo si hanno scritture mediamente più concise; inoltre come vedremo
esse facilitano la comprensione dell’insieme dei nodi e sui loro mutui collegamenti.
B55:d.04 Ora una breve digressione sulla geometria multidimensionale. Si osserva che il reticolo
booleano per n = 2 è un quadrato e quello per n = 3 è la rappresentazione assonometrica di un
cubo. Per n = 4 si ha invece una figura che suggerisce una sovrapposizione di cubi; questa figura
riguarda un cosiddetto ipercubo quadridimensionale, denotato da Q4 , generalizzazione delle figure precedenti allo spazio a 4 dimensioni. Analogamente al cubo tridimensionale Q3 delimitato da 6 quadrati
(bidimensionali) Q2 , l’ipercubo Q4 è delimitato da 8 cubi Q3 .
B55:d.05 Nei reticoli booleani si possono interpretare utilmente le operazioni di unione, intersezione
e complementazione. L’unione tra due parti dell’insieme ambiente corrispondenti ai nodi q1 e q2
individua l’insieme corrispondente al nodo più in basso tra quelli che si trovano al di sopra sia di q1
che di q2 (maggioranti di q1 e q2 ). L’intersezione tra due parti dell’insieme ambiente corrispondenti ai
nodi q1 e q2 individua invece l’insieme corrispondente al nodo più in alto tra quelli che si trovano al
12
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
di sotto sia di q1 che di q2 , nodi minoranti. Infine la complementazione corrisponde a passare da un
nodo x del reticolo a quello relativo al sottoinsieme complementare. Si osservi che questo è unico, è il
più distante sul reticolo e può essere raggiunto solo con un percorso di lunghezza n. Infatti si devono
trasformare tutte le componenti 0 in 1 e viceversa, si devono modificare n componenti e ciascuna di
queste modifiche corrisponde a percorrere un arco del reticolo.
Questo può essere chiarito dal grafo per n = 4 e da alcuni cammini di complementazione evidenziati.
input fB55d05
Si osserva inoltre che ogni reticolo booleano è complementato.
B55:d.06 Accade spesso di considerare collezioni limitate di parti di un insieme ambiente, o perchè
le parti rimanenti non rivestono interesse, o perchè non si riesce a conoscerle ed a controllarle con
sufficiente padronanza. Per i sottoinsiemi che interessano si devono prendere in considerazione le
relazioni di inclusione, ricavabili riducendo i cammini sul reticolo booleano mediante eliminazione dei
nodi corrispondenti alle parti trascurate. Si osservi che in genere cadono le possibilità di effettuare su
un digrafo cosı̀ ottenuto le operazioni di unione, intersezione e complementazione.
Un digrafo ottenuto da un digrafo D eliminando alcuni dei suoi nodi e semplificando di conseguenza
taluni cammini in archi si dice sottodigrafo di D.
Osserviamo che i sottodigrafi dei digrafi ordinati sono anch’essi ordinati; questo accade in particolare
per i sottodigrafi dei reticoli booleani.
I sottodigrafi dei digrafi booleani costituiscono alternative interessanti ed efficaci dei diagrammi di Venn
per raffigurare le relazioni che intercorrono fra collezioni di oggetti che soddisfano determinate proprietà
e quindi per raffigurare fatti concernenti la classificazione di oggetti studiati in ambito matematico e
non. Ci accadrà di incontrarne vari esempi.
B55:d.07 I nodi del reticolo booleano relativo ad un insieme S di n elementi si ripartiscono nei livelli
0, 1, 2, ..., n − 1 ed n: nel livello i si collocano i sottoinsiemi con i elementi.
La collezione di questi
( ) sottoinsiemi di S la indicheremo con la scrittura Pi (S).
n
Indichiamo con
la numerosità di Pi (S), cioè il numero delle parti di S contenenti i elementi.
i
Questa scrittura riteniamo opportuno che venga letta come “n binomiale i”; spesso essa viene letta
“n
su i”, ma questa dizione è più opportuno
( )
( che
) sia riservata a n/i. Un’altra dizione interessante per
n
n
è “i scelte tra n”. Gli interi positivi
si dicono coefficienti binomiali, in quanto intervengono
i
i
come coefficienti nello sviluppo della potenza del binomio.
Spesso essi vengono introdotti quando si presenta questo sviluppo: qui invece vengono presentati e
studiati in relazione a nozioni che ci sembrano più essenziali.
( )
n
B55:d.08 Osserviamo che
dipende solo da n e da i e non dall’insieme ambiente S: infatti se S
i
′
ed S sono in corrispondenza biunivoca si ha un isomorfismo tra i reticoli costituiti da P(S) e P(S ′ )
quando S ed S ′ si possono porre in corrispondenza biunivoca. In effetti da questa considerazione si
ricava anche che tutti i reticoli booleani relativi agli insiemi con un dato numero di elementi sono
isomorfi.
Per calcolare i coefficienti binomiali è opportuno prendere in considerazione la loro totalità e pensarli
disposti in un triangolo infinito.
Questo schema in Italia viene solitamente chiamato triangolo di Tartaglia, dal soprannome del matematico rinascimentale che l’ha studiato. In altri paesi viene chiamato triangolo di Pascal per ricordare
il grande matematico francese che utilizzò i coefficienti binomiali in fondamentali studi sul calcolo
2010-02-12
B55: Insiemi ordinati e reticoli
13
Alberto Marini
delle probabilità. In realtà esso era noto ai cinesi intorno al 1300. Con atteggiamento europeista lo
chiameremo triangolo di Tartaglia-Pascal.
(0)
(1) 0 (1)
(2) 0 (2) 1 (2)
0
1
2
....................................
(n)
(n)
( n )
(n)
0
1
n−1
n
..........................................
B55:d.09 Osserviamo innanzi tutto che:
( )
0
= 1,
0
Questo significa che esiste un solo insieme costituito da 0 elementi, l’insieme vuoto ∅. Da questo fatto e
dalla osservazione dei reticoli booleani relativa a n = 1, 2, 3, 4 si trova che la parte più alta del triangolo
di Tartaglia-Pascal è la seguente:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
B55:d.10 Si trova facilmente che per ogni n intero naturale:
( ) ( )
n
n
=
=1;
0
n
infatti un insieme qualsiasi di n elementi possiede un unico sottoinsieme con 0 elementi, ∅, e un unico
sottoinsieme con n elementi, S stesso.
Si ha inoltre che per ogni n ∈ N
( ) (
)
n
n
=
,
i
n−i
Questa uguaglianza esprime il fatto che il numero dei sottoinsiemi di S con i elementi è uguale al
numero dei sottoinsiemi con n − i elementi, cioè che:
|Pi | = |P(S|S|−i )| ,
In effetti ad ogni sottoinsieme I di S si può associare il complementare S \ I e questa corrispondenza
è evidentemente biunivoca (anzi essa è una involuzione senza punti fissi)
La precedente uguaglianza dice che il triangolo di Tartaglia-Pascal è simmetrico rispetto alla verticale,
fatto evidente nel triangolino trovato in 4.9 .
B55:d.11 Un altro fatto generale è dato dall’uguaglianza:
( ) (
)
n
n
=
=n,
1
n−1
Questa dice semplicemente che il numero dei sottoinsiemi di S con un solo elemento è uguale al numero
degli elementi di S; in effetti dovrebbe essere chiaro che:
P1 {a, b, ..., h} = {{a}, {b}, ..., {h}} ,
14
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
B55:d.12 Un po’ più complessa è l’espressione del numero di sottoinsiemi con due elementi:
( )
n
n(n − 1)
=
,
2
2
Dimostriamola considerando rappresentazioni dei sottoinsiemi che individuano ogni elemento di S con
un segno peculiare e che si servono di allineamenti di segni.
Un sottoinsieme di due elementi è individuato da una coppia di segni diversi: il numero di tali coppie
è chiaramente n(n − 1), in quanto il primo componente può scegliersi tra n segni ed il secondo tra gli
n − 1 rimanenti. Accade però che due rappresentazioni come ab e ba forniscono lo stesso insieme.
n(n − 1)
blocchi, ciascuno con due stringhe che danno lo stesso doppietto. La formula
Quindi si hanno
2
è cosı̀ dimostrata.
B55:d.13 Dimostriamo ora una formula che consente di estendere il triangolo di Tartaglia-Pascal quanto
si vuole:
( ) (
) (
)
n
n−1
n−1
=
+
,
i
i−1
i
Per dimostrare questa uguaglianza pensiamo di ripartire la collezione C dei sottoinsiemi di S con i
elementi in due sottocollezioni: la collezione C ′ dei sottoinsiemi che contengono un dato elemento a
e la collezione C ′′ di quelli che non contengono a. Dimostriamo ora che la precedente uguaglianza
traduce l’uguaglianza evidente:
|C| = |C ′ | + |C ′′ | .
Se da ciascuno dei sottoinsiemi di S facenti parte di C ′ eliminiamo a abbiamo la collezione dei sottoinsiemi con i − 1 elementi di S \ {a}; per il loro numero si trova:
(
)
n−1
′
|C | =
,
i−1
in quanto S \ {a} possiede n − 1 elementi.
Per il numero di sottoinsiemi facenti parte di C ′′ basta osservare che questa si può considerare come
la collezione dei sottoinsiemi di S \ {a} con i elementi: quindi
(
)
n−1
|C ′′ | =
i
e l’uguaglianza è dimostrata.
B55:d.14 Possiamo ora dimostrare la seguente espressione chiusa per i coefficienti binomiali:
( )
n
n!
,
=
i!(n − i)!
i
Questa formula si verifica essere vera per le parti alte del triangolo di Tartaglia-Pascal relative a
n = 0, 1, 2, 3, 4 e per n qualsiasi e i = 0, 1, 2, n − 2, n − 1, n.
Dimostriamola pensando a rappresentazioni dei sottoinsiemi di S fornite da stringhe formate da n segni
che consentono di identificare gli elementi di S. Le stringhe formate da questi n segni diversi sono n!.
Ogni stringa individua un sottoinsieme di Pi (S), se si conviene che i suoi primi i segni individuino gli
elementi nel sottoinsieme.
Di queste rappresentazioni molte individuano lo stesso sottoinsieme, precisamente le i!(n − i)! stringhe
ottenibili l’una dall’altra permutando come si vuole i primi i segni tra di loro ed i rimanenti n − i segni
tra di loro.
2010-02-12
B55: Insiemi ordinati e reticoli
15
Alberto Marini
n!
i!(n − i)!
i!(n − i)! rappresentazioni, tutte rappresentanti lo stesso sottoinsieme.
La formula resta cosı̀ dimostrata.
Quindi l’insieme delle n! rappresentazioni si suddivide in
blocchi, ciascuno contenente
B55:d.15 A questo punto si può procedere ad estendere il triangolo di Tartaglia-Pascal quanto si vuole:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
. . . . . . . . . . . . . . . . . . . .
B55:e. Digrafi di partizioni
B55:e.01 Introducendo le partizioni di un insieme, o partizioni -S, che chiameremo anche partizioni
-S per distinguerle dalle partizioni -I o partizioni di un intero positivo, abbiamo definito la relazione
“essere non meno fine di”. Anche questa è una relazione di ordine: riflessività e antisimmetria sono
evidenti; per la transitività basta osservare che il passaggio da una partizione π ad una più fine può
descriversi come l’effettuazione di nuove suddivisioni sopra alcune parti di π e quindi due passaggi a
partizioni via via più fini possono descriversi come l’effettuazione di nuove suddivisioni eseguite in due
stadi successivi.
La raffigurazione basso-alto delle partizioni dell’insieme {a, b, c, d} è:
a/b/c/d
...
...............................
................. .. ... ..................
........... ....... .. ..... ....................................
........... ............ .....
.......
.
...
.
.
.
.
.
.
.
.
....... ......................
...
...
.......
.......
...........
...
.......
...
..........
.......
...........
.......
...
...
...........
.......
...........
.......
..........
..
.
.
.
.
.
.
.......
.
.
.
...........
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.......
...........
....
..
........
.
.
.
.
.
.
.
.
.
.
.
.......
.
.
...........
.
.
.
.
.
...
.
....
.......
.......
.
.
.
.
...........
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......
...
...........
....
.
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
...........
.
.
.
.
.
.
.
.
.
.......
...
.
......
....
.
.
...........
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.......
..
.
...
...........
..
...........
.
.......
...
ab/c/d
....
ac/b/d
ad/b/c
bc/a/d
bd/a/c
cd/a/b
ab/cd
ac/bd
ad/bc
bc/ad
bd/ac
cd/ab
.....
....
..
.....
..........
...........
................
...... ....
..... ........
...........
..... .......
.........
...... ........
...... .... ........
....... .......
...... ...........
...... .....
. ..
.... .... ....
......
.
.
......
.
.. ...
.. ... ........
.
.
.
.
......
.
.
.
.
.
.
.
.
.
.
... ... ......
.
.
.
.
.
.....
.
..
.....
......
... . .
.....
.....
... ... .......
....
... ...
... ...
.... ....
......
......
.....
.... .. ..
.....
.....
.....
......
......
... ...
... ...
..... ...........
... ....
...
..... .... ....
... ....
..... ...........
.....
......
....
.. ..
.. ..
...........
... ...
...
... ...
.. ..
.......
......
.....
.. ....
.. ....
.....
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... ...
.
... ....
.
.
.
.
.
.
.
.....
...... . .
.
... ......
... ......
.
....
.. ...
......... ..
.....
... ...
.... ..........
.... ....
... ...
......
.....
.....
....
..
.
.....
.
.
.
..
....... ... ..........
.
.
.
.
.
.
.
.
.
.
.
.
... ....
.
.
....
.
.
.
.
.
.
.....
.....
...
.
. ...
.....
.
...
...
.....
.....
...
....
...
.....
... ..............
...
.......
... ........
..... ....
.. ............
..
.....
.....
...
........
..... ..
..
..
..
... .....
..... .
............ .. ...........
..
.
.
.
...
.
.
.
.
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..........
.....
......
......
......
.
...
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.....
......
.. ......
...
.....
.......
.
. ......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...... .....
.....
..... .... .... ...
...
.
......
.
...
.... .
.....
..........
..
...... .....
..... ....
...... .... ...
... ........
...
...... ....
.....
...
...... ..
..... ......
..... ..
...
......
................
........ .....
...
.
... ......
...
...... ...
.
.....
........
.....
.....
...
......
..
.. ......
.... ........
.......
...
...
..... ................
......
..
............
......
.... ...............
......
.
.
.
.
..
.
.
.
.
.
.
.........
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..... ..... ....
...... .. .....
...
.. .....
..
... ... .......
... ........ ...
...... .. ....
...
... ..............
.....
.... .....
........ ......
.......
.
.......
... ..........
. .... ..
...
.....
..... ....
.
...... ....
.........
.. .....
.....
...
..... ........ ...... ...
.... .....
..... .............. ...
...... ....
... .......... ........
.....
... .... .......... ..........
.... .......
. .. ...
.....
... ...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.....
.
.....
...... .... .... ....
...
... ..
..
...... ........ ..... ....
...... ..... .... ....
..... ........... ..........
...
...
... ... ......................
.....
..... .. ..
.............. ....
..... .. .........
......
...
... .. .......
...
......
..........
..................
......
..
...
......
.............
............ .....
.....
......
....... ....
.....
..
.... ..........
.
.
.
.
.
.
.
.
......
.
.
.
.
.
....
...
..
.
....
.
.
......
.
.
.
.
.
.
.
.
.
.
...
...
......
...
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...... ....
...
...
.........
...
... ......
....
...... .....
...
.........
.........
...
....
...... ......
............
...
........
.........
...
...
.....
...... ......
....
........
............
.........
..
...
.....
...... ......
.........
...........
...
.........
..
........
.... ....................
.
....
............
.
.........
.
.
.
.
.
.
.
.
.
.
.
.
...
.........
............
....
.
... ....
...
.........
...
.........
........... ......
...
.... ............
.........
.........
............ ...
... ....... ..................
.........
........
........... .... ....
.........
... .... ...........
.........
......... .................... ...... .... ... ....... .................... ...............
......... ........... ... .. .. .... ........... .........
......... ...... ... ... .. ............... .........
......... .......... .. .. .......... .........
................... ....................
.............................
.
abc/d
abd/c
acd/b
bcd/a
abcd
16
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
B55:e.02 Si può osservare che anche con un insieme formato da pochi elementi si ottiene un digrafo
assai complesso che presenta una grande varietà di collegamenti.
Molti problemi pratici portano a considerare digrafi di partizioni e ad operare entro di essi: Si tratta
di strutture discrete facili da definire ma assai estese ed articolate quando gli insiemi di base sono un
poco estesi. L’estensione di queste strutture comporta l’onerosità della individuazione delle soluzioni
per molti degli accennati problemi pratici.
B55:e.03 Accanto alla relazione fra partizioni -S, è interessante esaminare le corrispondenti partizioni
-I, partizioni di interi positivi. Ricordiamo che, date due partizioni -I y1 e y2 di un intero positivo, si
dice che y2 è più fine di y1 se y2 si può ottenere suddividendo in più addendi alcuni degli addendi di
y1 . La raffigurazione di questa relazione nel caso delle partizioni -I di 4 è:
2010-02-12
B55: Insiemi ordinati e reticoli
17
Alberto Marini
1+1+1+1
..
..
...
..
...
...
...
...
.
2+1+1
....
........... .....................
...........
...........
...........
...........
...........
...........
...........
...........
.
.
.
.
.
.
.
.
.
.......
.
......
3+1
........
2+2
........
...........
...........
...........
...........
...........
...........
...........
...........
...........
................................
.
4
Si ha quindi un digrafo assai più semplice del precedente.
Questi digrafi, noti come reticoli di Young, si possono tracciare facilmente anche nei casi delle partizioni
-I di 5 e di 6.
1+1+1+1+1
..
..
...
..
....
2+1+1+1
.............................
...........
...........
...........
...........
...........
...........
...........
...........
.
.
.
.
.
.
.
.
.
...........
.
..........
3+1+1
..........
2+2+1
4+1
.....
3+2
.. ...............
...............
............
............
...
...
............
............
..
............
............
...
............ .......................
...
...
.................
.
.
.
.
.
.
.
.
.
...
.
...
.
............
........
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
.
.
...
.
............
........
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
.
.
.
.
............ ...
.....
............
...................
...
.......
.......
.......
......
.......
.......
.......
.......
.......
......
.
.
.
.......
.
.
.......
.......
.......
......
.......
.......
.......
......
..................
5
1+1+1+1+1+1
..
...
...
..
...
...
...
...
..
2+1+1+1+1
..........
..
.......
......
......
.......
......
.
.
.
.
.
.
.......
.......
......
.......
.......
.......
.......
.......
.......
.......
.......
.......
.......
.......
.......
.......
3+1+1+1
..
2+2+1+1
...............
..
.................. ..
...
............ ...... ....
............ ............
..
..
............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
.
...
.
.
.
...
.......
............
...
...
......
............
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
.
.
...
.
.....
.....
.
.
.
.
... .......................
.
...
....
.
.
.
.
.
..
............
.
.
4+1+1
......
2+2+2
3+2+1
5+1
.....
4+2
3+3
..
.........
...
... ............
................... ..
.......
............ ...... ...
...
...
.......
............ ......
.......
....
.... ........................ .............
...
.......
..
...
...
......
....... .........................
.......
...
..
...
......
....................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...
.
...
.
.
.
....... .. ......
.....
....... . .......
...
... .......................
........
.
....
....
...
.......
......
.......
...
......
.......
.......
...
.......
.......
.
.
.
.......
.
.
.
.
.......
.....
....
.......
......
.......
.......
...
......
.......
....... .... .............
..............
6
B55:e.04 Osserviamo che ad una partizione -S π di un insieme S di n elementi corrisponde naturalmente
una partizione -I di n, quella avente come addendi le cardinalità delle parti di π. In questa trasformazione due partizioni ottenibili l’una dall’altra con una permutazione degli elementi di S conducono
18
B55: Insiemi ordinati e reticoli
2010-02-12
MATematica – Nozioni di base
alla stessa partizione -I. Sostanzialmente questa trasformazione corrisponde a considerare indistinguibili i diversi elementi di S, a “dimenticare” le loro individualità: la chiameremo pertanto quoziente
dimenticanza.
È poi evidente che a due partizioni -S π1 e π2 dello stesso insieme, la prima più fine della seconda, il
quoziente dimenticanza fa corrispondere rispettivamente due partizioni -I y1 e y2 , la prima delle quali
più fine della seconda.
B55:e.05 A questo punto si può osservare che il reticolo di Young di un certo intero n si ottiene dal
reticolo delle partizioni di un insieme con n elementi “fondendo” i nodi che corrispondono a partizioni
-S ottenibili l’una dall’altra permutando gli elementi di S e fondendo di conseguenza gli archi. Questo
fatto dovrebbe risultare chiaro anche dalla sola osservazione dei digrafi nel caso {a, b, c, d}.
Si può dire che i nodi dei reticoli di Young permettono di dare una classificazione importante dei nodi
dei reticoli delle partizioni -S, reticoli assai più “affollati e ripetitivi” dei precedenti.
B55:f. Omomorfismo e isomorfismo tra digrafi
B55:f.01 A questo punto può essere utile ritornare sulla nozione di isomorfismo tra digrafi facendo
riferimento ai reticoli booleani ed ai reticoli delle partizioni -S relativi ad insiemi diversi ma con uguale
numerosità.
L’identità degli elementi dell’insieme di base non interessa in modo sostanziale e si può giustificare
come veniale l’abuso di linguaggio che porta a parlare, per gli insiemi di data numerosità n, di un solo
reticolo booleano e di un solo reticolo delle partizioni -S.
B55:f.02 A rigore si dovrebbe parlare della classe di isomorfismo dei reticoli booleani relativi agli
insiemi con n elementi e della classe di isomorfismo dei reticoli delle s-partizioni degli insiemi formati
da n elementi. La pesantezza e la poca immediatezza della frase precedente giustifica le abbreviazioni
introdotte precedentemente.
Si può inoltre ritornare sulla nozione di omomorfismo tra digrafi facendo notare che la trasformazione
che porta dal reticolo delle partizioni -S per gli insiemi di una data numerosità n al reticolo di Young
relativo allo stesso n costituisce un significativo esempio di omomorfismo.
Le varie componenti di questo testo sono accessibili in http://www.mi.imati.cnr.it/∼alberto
2010-02-12
B55: Insiemi ordinati e reticoli
19