Algebra e gemoetria - relazioni binarie

A x B={(a,b) | a in A , b in B }

Es,

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

B = {1,2}

|A x B| = |A| * |B| = 2*2 = 4

|P(AxB)| = 2^|A * B| = 2^4 = 16

A x B = {(a,1),(a,2),(b,1),(b,2)}

,

P(AxB) = { {(a,1)},{(a,2)}, {(b,1)}, {(b,2)}, {(a,1), (a,2)}, {(a,1),(b,1)}, {(a,1), (b,2)}, {(a,2),

∅

(b,1)} {(b,2),(a,2)}, {(a,2),(b,1),(b,2))}, {(a,1),(b,1),(b,2)}, {(a,1),(a,2),(b,2)}{(a,1),(a,2),(b,1)}}

A∈B

Def. Una relazione un sottoinsieme di A x B

R⊆ A x B

Notazione

Se , b)∈ R Sottoinsieme di a R b

(a

Se , b)∉ R Sottoinsieme di a ! R b

(a

Esempio A = {cane, gatto} B = {osso, topo}

A x B

R = {(cane, osso), (gatto, topo)} ¿

Cane R osso Gatto R topo

Def

2 N è l'insieme dei multipli di 2 (multipli pari)

2N + 1 è l'insieme dei numeri dispari

2Z e 2 Z +1 sono l'insieme dei numeri interi pari e dispari

in generale

k N sono i multipli di k

3 N = {a,3,6,9,12,...}

102 N = {0, 102, 204, 306, … }

Es.

R⊆ N ⊈2N n in N) }⊆N x 2N

R = {(n,2n)| R 6

(3,6)∈R3

2 R8

(2,8)∈R

2R4 5R10 6!R13

R

(2,4)∈ n∈ N }⊆N x 2N

R1 = {(2n, 2n+2) | }

3 R1 6 4 R2 6 5!R17 10 R2 12

n IN N}⊆N X N

R2 = {(n,n^2) (

(1,1) APPARTIENE a r2

3 R2 9

4!R2 10

Def. R⊆ A x Aallora R si chiama Relazione Binaria∈ A

Se

Es. r2 (di prima) + una rel. binaria su N

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

R = {(a,a),(a,b),(b,a),(a,c)} ⊆A

x A

{(a,a), (b,b),(c,c)} ⊆A

Nota che una Rel. Binaria E in A

R A X A R a P(A x A)

∈ ∈

Quante rel. Binaria su A

ci sono (se |A| = n)?

Tante quanti i sottoinsiemi di A X A e cioè

| P (AxA)| = 2^|AXA| = 2 ^(|A|*|A|) = 2^(n^2)

A

Quindi per esempio se |A| ∈

allora ci sono 2^4 rel. binarie su A

Def.

Una relaz. Binaria su A si dice:

Riflessiva se

–

x∈ A si ha x R x

∀

Es. Se Se A=a , b , c R=( a , a) ,(a , b) ,(b , b) ,(b , c) ,(c , c )

R è riflessiva perchè per ogni elemento di A,R contiene la coppia che ha questo elemento come

prima e seconda componente.

Es.

A = {a,b,c}

R3 = {(a,a),(a,b),(c,c)}

R3 non è riflessiva perchè non è vero che per ogni x appartenente ad a x non è in relazione con x

perchè a è in relazione con a, c è in relazione con c, ma b non è in relazione con b.

infatti (b,b) non appartiene a R1 cioè b! R1 b

R non è riflessiva

x b , c , x! R x

∃ ∈A

Es. IN N} x N

R = {(n,2n) | n ⊆N

R è riflessiva? No

Ax A

Def. R ∈

R è SIMMETRICA Se

x , y∈ A x R y => y R x

∀

cioè per ogni coppia di elementi di A se x R y allora deve valere y R x

Es. {a,b,c}

R = {(a,a), (b,a), (a,c), (a,b),(c,a)}

R è simmetrica se all'interno dell'insieme per ogni coppia c'è anche il suo opposto (es. (b,a) e (a,b))

Es. A = {a,b,c}

R1 = {(a,b), (b,c),(c,b)}

R1 non è simmetrica perchè

(a,b) R1 ma(b , a)∉R1

∈

R non è SIMMETRICA se

x , y che x R y=! y R x

∃ ∈Atali >

x y tali che x R y ma y ! R x

cioè ∃ ∈A

x y tali che x R y ma y ! R x

∃ ∈A

ovvero se esiste almeno una coppia che non ha il suo opposto

n∈ N }⊆N x N

R = {(n,2n)| n

R è simmetrica

se n R 2n allora 2n R n ? NO

R

(2n, n) ∉

P(S) R = {(x,y)| |x| = |y| } ⊆P (s)

S = {a,b,c}

{a} R {b} perchè |{a}| = |{b}| = 1

{a,b} R {b,c} perchè |{a,b}| = |{b,c}| = 2

{a} !R {a,b} perchè |{a}| = \1

|{a,b}| = 2

R∅

∅

R riflessiva? È vero che ogni elemento di P(s= è in relazione R con se stesso?

SI perchè |x| = |x| per ogni x ∈P (s)

quindi se X R Y allora Y R X

=> è simmetrica

Def. R rel. Binaria su A è TRANSITIVA se

x , y , z A si ha

∀ ∈

se x R y e y R => x R z

R non è TRANSITIVA se

x , y , z tali che

∃ ∈A

x R y, y R z ma x !R z