Algebra e geometria - relazione d'ordine

PROPRIETÀ TRANSITIVA

n = m * h e m = l * k

n è multiplo di m m è multiplo di l

=> n = l * k * h

Quindi n è multiplo di l

=> n = l* k * h

Quindi n è multiplo di l

=> R è una relazione d'ordine

Non è simmetrica

10 R 2 ma 2 !R 10

Esempio

A = {a,b,c,d}

P parole costituite con le lettere di A

# lunghezza (numero di lettere)

di una parola

# abcd = 4 # aab = 3

# abc = 3 #ba = 2

R = {(u,v)| #u <= #v}

ba R abc aab R abcd

b R abc ab R cd

RIFLESSIVA

#u <= #u => R è riflessiva

TRANSITIVA

Se #u <= #b e #b <= #w

allora #u <= #w

ASIMMETRICA

# u<= # v e # v <= #u

=> #u = #v però può essere che u != v

#ab = #bc ab R bc =/> ab = bc

bc R ab

NO R non è SIMMETRICA

DIAGRAMMI DI HASSE

Def. x , y A

Se R è una rel. d'ordine su A e ∈

Y copre x se x R y e NON ESISTE

z tale che x R z e z R y

Es. in ℕcon≤

3 copre 2 ma 4 non copre 2

in con la rel. Di MULTIPLO

– ℕ

4 copre 2, 6 non copre 2

DIAGRAMMI

Rappresentiamo ogni elemento di A come un punto del diagramma due punti sono collegati se uno

copre l'altro.

Di solito in alto si scrivono gli elementi che coprono

,≤

Es, ℕ 4

3

2

1

0

ES.

A = {1,3,4,6,8,10,12}

(3,1), (4,1), (6,1), (8,1),(10,1),(12,1)

(6,3), (8,4), (12,4), (12,6), (12,3)

8 12

10 4 6

3 1 è minimo, non c'è massimo

1

Es.

A = {2,3,4,5,10,22,21,36} 36

12

4 10 21

2 5 3

10 R 5 10 R 2

Es. A = {a,b}

P(A) = { , {a}, {b}, {a,b} }

∅

Relazione di inclusione

{a} {b} {a,b}

⊆ ⊆ ⊆

∅ ∅ ∅

{a} {a,b} {b} < {a,b}

⊆ ⊆

{a} {a} {b} {b}

⊆ ⊆ ⊆

∅ ∅

{a,b} {a,b}

⊆

Inclusione è una relazione d'ordine

Rifl., Asimmetrica, Transitiva

Asimm.

Se x y e y x => x = y

⊆ ⊆

Riferito all'insieme sopra

{a,b}

{a} {b}

∅

Es. A ={a,b,c}

P(A) = { , {a},{b},{c}, {a,b}, {a,c}, {a,c}, {b,c}, {a,b,c} }

∅ {a,b,c}

{a,b} {a,c} {b,c}

{a} {b} {c}

∅

Es. A = {a,b,c,d}

P insieme delle parole su A

u ,v P

Def. ∈ w

u è un PREFISSO di v SE se si ha ∈P

tale che v = u w

Es. ab è un prefisso di abcdab

ba è un prefisso di bac

acb è un prefisso di acba

Caso Particolare: ogni parole è prefisso di se stessa

R = {(u,v) | u è prefisso di v }

è una rel. D'ordine

Rifl. Ogni parola è prefisso di se stessa

Asimm. u prefisso di v => v = u * w

v prefisso di u => u = v * k

=> v = v * k * w può solo essere che v = u

ab è pref di abc

abc non è prefisso di ab

Transitiva

se u è prefisso di u

e v prefisso di w

=> u è prefisso di w

Es. ab abc abcd

Diagramma di P dacb

aaa aab dac

aa ab ba da

a b c d

Def. Se R è una rel. d'ordine su A

M A si chiama

un elemento ∈ a∈ A

MASSIMO se PER OGNI

si ha a <= M

m∈ A è il MINIMO di A se a A m R a

- ∀ ∈

Es. A = {1,3,7,10} R = <=

10 è il massimo

1 è il minimo

Es. ℕ ≤

0 è il minimo di ℕ

NON ESISTE IL MASSIMO

,≤ non esiste né minimo né massimo

ℤ A

Def. Due elementi x e y ∈