Ordini Parziali - Reticoli. Tino CortesiTecniche di Analisi di Programmi 2 Insiemi parzialmente...

Ordini Parziali - Reticoli

Tino Cortesi Tecniche di Analisi di Programmi 2

Insiemi parzialmente ordinati

Nell’analisi di programmi ordini parziali e reticoli giocano un ruolo importantissimo

Dato un insieme L, un ordine parziale su L è una relazione: L L {vero, falso}

che gode delle proprietà:riflessiva: l L : l l

transitiva: l1, l2, l3 L : l1 l2 l2 l3 l1 l3

antisimmetrica: l1, l2 L : l1 l2 l2 l1 l1 l2

Un insieme parzialmente ordinato (L, ) è un insieme L sul quale è definito un ordine parziale .


Esempio

a b

c d e f

g

L= {a,b,c,d,e,f,g}={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}T

(L, ) è un insieme parzialmente ordinato (finito)


Esempio

(x1,y1) N N (x2,y2) x1N x2 y1N y2

(N N, N N) è un insieme parzialmente ordinato (infinito)

N N

a

b cb N N c

a N N c


EsempioTutti i possibili insiemi ordinati con tre elementi:


lub e glbDato un insieme parzialmente ordinato (L, ),

un insieme Y di L ha un elemento l come upper bound se l’ Y : l’ l

un insieme Y di L ha un elemento l come lower bound sel’ Y : l l’

Un least upper bound (lub) di Y è un upper bound l0 di Y che soddisfa la seguente proprietà:

l’ è un upper bound di Y l0 l’

Un greatest lower bound (glb) di Y è un lower bound l0 di Y che soddisfa la seguente proprietà:

l’ è un lower bound di Y l’ l0Se un sottoinsieme Y di L ha un least upper bound, questo è unico (per la proprietà antisimmetrica dell’ordine parziale )


Esempio

(x1,y1) N N (x2,y2) x1N x2 y1N

y2

N N

Y

lower bounds di Y

upper bounds di Y

lub(Y)

glb(Y)


Esempio

c dba

g

jih

fe

T

lub({b,c})= ?

Gli upper bounds dell’insieme {b,c} sono {h,i,T}

e questo insieme non ha un minimo elemento:

Il lub non c’è !

T

ih


Esempio

c dba

g

jih

fe

T

lub({a,b})= ?

Gli upper bounds dell’insieme {a,b} sono {T,h,i,f}

e questo insieme ha un f come minimo elemento:

lub({a,b})= f

ih

f

T


ReticoliUn reticolo è un insieme parzialmente ordinato (L, ) tale che per ogni coppia di elementi di L esiste il least upper bound ed il greatest lower bound.

Se L è un insieme parzialmente ordinato non vuoto, e xy, allora

lub({x,y}) y glb({x,y}) x.

Per dimostrare che L è un reticolo basterà quindi verificare che per ogni coppia di elementi incomparabili esistano sia lub che glb.


EsempioRivediamo tutti i possibili insiemi ordinati con tre elementi: sono reticoli?

SI NO NO NO NO


Esempio

a b

c d e f

g

L= {a,b,c,d,e,f,g}={(a,c), (a,e), (b,d), (b,f), (c,g), (d,g), (e,g), (f,g)}T

(L,) non è un reticolo: sia a che b sono lower bounds di Y, ma a e b sono incomparabili

Y


CateneDato un insieme parzialmente ordinato (L,), un sottoinsieme Y di L è una catena se

l1, l2 Y : (l1 l2) (l2 l1)

ovvero una catena è un sottoinsieme di L totalmente ordinato.

Un insieme parzialmente ordinato (L,) ha altezza finita se e solo se tutte le catene di L sono finite

Una sequenza (ln)nN di elementi di L è una catena ascendente se

n m ln lm


Esempio: catene

c dba

g

jih

fe

T

c dba

g

jih

fe

T


Insiemi DirettiSia (P,P) un insieme parzialmente ordinato. Un sottoinsieme S di P si dice diretto se per ogni sottoinsieme finito F di S esiste un elemento di S che appartiene all’insieme degli upper bounds di F.


Esempio

2 3 4 1 0 -1 -2 -3 -4

T

L= Z {T,}

n Z : n T

SF

S non è un insieme diretto:non esiste un elemento di S che appartiene all’insieme degli upper bounds di F


Esempio

2 3 4 1 0 -1 -2 -3 -4

T

L= Z {T,}

n Z : n T

S

F

S è un insieme diretto: per ogni F finitoesiste un elemento di S che appartiene all’insieme degli upper bounds di F


Insiemi diretti e catene

Sia (P,P) un insieme parzialmente ordinato. Ogni catena non vuota di P è un insieme diretto.

c dba

g

jih

fe

T

0

1

2

3

4

5

6


Insiemi diretti

In (N,) l’insieme S={X N | X è finito} è diretto?

In (N,) l’insieme S={X N | N-X è finito} è diretto?


CPOUn insieme parzialmente ordinato (P,P) si dice CPO (insieme completo parzialmente ordinato) se:

Esiste un elemento minimo (bottom)

Per ogni sottoinsieme diretto S di P esiste lub(S).


Reticoli completiUn reticolo completo è un insieme parzialmente ordinato (L, ) tale che tutti i sottoinsiemi di L hanno least upper bound e greatest lower bound.

Se (L, ) è un reticolo completo, si denotano:

= lub() bottom elementT = glb(L) top element

Ogni reticolo finito è un reticolo completoOgni reticolo completo è un CPO


Esempio

{3}{2}{1}

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

{1,2,3}

L= ({1,2,3})

= lub(Y) = Yglb(Y) = Y


Esempio

{3}{2}{1}

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

{1,2,3}

L= ({1,2,3})

= lub(Y) = Yglb(Y) = Y

Y

lub(Y)

glb(Y)


Esempio

2 3 4 1 0 -1 -2 -3 -4

T

L= Z {T,}

n Z : n T


Esempio

0

1

2

3

4

5

6L= Z+

ordine totale su Z+ lub = maxglb = min

E’ un reticolo, ma non completo:Ad es. l’insieme dei pari non ha

lub


Esempio

0

1

2

3

4

5

6

T

L= Z+ {T}

ordine totale su Z+ {T}lub = maxglb = min

E’ un reticolo completo


EsempiL=R (numeri reali) con ordine totale

(R, ) non è un reticolo completo: ad esempio {x R | x > 2} non ha lub

Per ogni x<y in R, ([x,y], ) è un reticolo completo

L=Q (numeri razionali) con ordine totale

(Q, ) non è un reticolo completo

E non basta aggiungere un top ed un bottom per ottenere la completezza:l’insieme {x Q | x2 < 2} ha upper bounds ma non ha un least upper bound.


Teorema: Se (L, ) è un insieme parzialmente ordinato, sono equivalenti:

1. L è un reticolo completo2. ogni sottoinsieme di L ha un least upper bound3. ogni sottoinsieme di L ha un greatest lower bound

Dimostrazione:1 2 e 1 3 seguono immediatamente dalla definizione

Per mostrare che 2 1, basta definire per ogni Y L

glb(Y) = lub({lL | l’ Y : l l’})Tutti gli elementi dell’insieme a destra sono lower bounds dell’insieme Y. Quindi lub({...}) definisce un lower bound di Y.Poiché tutti i lower bound di Y appartengono all’insieme a destra, lub({...}) definisce il greatest lower bound di Y.


Y

Esempio

{3}{2}{1}

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

{1,2,3}

Z= {lL | l’ Y : l l’}

lub(Z)

glb(Y)= lub({lL | l’ Y : l l’})

upper bounds di Z

Ordini Parziali - Reticoli. Tino CortesiTecniche di Analisi di Programmi 2 Insiemi parzialmente...

Documents

Transcript of Ordini Parziali - Reticoli. Tino CortesiTecniche di Analisi di Programmi 2 Insiemi parzialmente...