Teoria degli Insiemi - unipa.itmath.unipa.it/~fbenanti/InsiemiAlgebra1201516.pdf · 2015. 10....

Teoria degli Insiemi

Insiemi

Definire un insieme

Inclusione

Sottoinsiemi Propri . . .

Operazioni tra Insiemi

Proprieta delle . . .

Prodotto Cartesiano

Corrispondenze

Relazioni


Relazioni d’ordine

Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

of 72

Go Back

Full Screen

Close

Quit


Docente: Francesca Benanti

Ottobre 2015

Corso di Algebra 1, a.a. 2015/16

http://math.unipa.it/~fbenanti/


Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

of 72

Go Back

Full Screen

Close

Quit

1. Teoria degli Insiemi

La Teoria degli Insiemi e una bran-ca della matematica creata alla finedel diciannovesimo secolo principalmen-te dal matematico tedesco Georg Cantor(1845-1918). Inizialmente controversa,e arrivata ad avere il ruolo di teoriafondamentale nella matematica moder-na. I concetti di questa teoria, quali peresempio quelli di funzione e di relazione,sono presenti in ogni suo settore.



http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Cantor.html


Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 2 of 72

Go Back

Full Screen

Close

Quit

1. Teoria degli Insiemi

La Teoria degli Insiemi e una bran-ca della matematica creata alla finedel diciannovesimo secolo principalmen-te dal matematico tedesco Georg Cantor(1845-1918). Inizialmente controversa,e arrivata ad avere il ruolo di teoriafondamentale nella matematica moder-na. I concetti di questa teoria, quali peresempio quelli di funzione e di relazione,sono presenti in ogni suo settore.

Un insieme e una collezione di oggetti determinati e distintidella nostra percezione o del nostro pensiero concepiti comeun tutto unico. Tali oggetti si dicono gli elementi dell’insie-me. (G. Cantor)



http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Cantor.html


Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 3 of 72

Go Back

Full Screen

Close

Quit

2. Insiemi

Insieme: concetto primitivo, nel senso che non puo esseredefinito in termini di altre nozioni piu elementari, sinonimodi collezione, raccolta di elementi.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 3 of 72

Go Back

Full Screen

Close

Quit

2. Insiemi


Insiemi Numerici:

• N = {0, 1, 2, 3, 4 . . .} = l’insieme dei numeri naturali,

• Z = {. . . ,−2,−1, 0, 1, 2, . . .} = l’insieme dei numeri in-teri,

• Q = {. . . ,−2.7, . . . ,−34, . . . , 0, . . . , 1

7. . . , 4.8(2), . . .}= l’in-

sieme dei numeri razionali,

• R = {. . . ,−√

5, . . . ,−45, . . . , 0, . . . ,

√2 . . . , 7, . . .}= l’in-

sieme dei numeri reali.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 3 of 72

Go Back

Full Screen

Close

Quit

2. Insiemi


Insiemi Numerici:

• N = {0, 1, 2, 3, 4 . . .} = l’insieme dei numeri naturali,

• Z = {. . . ,−2,−1, 0, 1, 2, . . .} = l’insieme dei numeri in-teri,

• Q = {. . . ,−2.7, . . . ,−34, . . . , 0, . . . , 1

7. . . , 4.8(2), . . .}= l’in-

sieme dei numeri razionali,

• R = {. . . ,−√

5, . . . ,−45, . . . , 0, . . . ,

√2 . . . , 7, . . .}= l’in-

sieme dei numeri reali.

Osservazione:

I simboli N∗, Z∗, Q∗, R∗ indicano gli insiemi numerici N, Z,Q, R privati dell’elemento zero.

I simboli Z+, Q+, R+ indicano gli interi, i razionali, i realipositivi, rispettivamente.

I simboli Z−, Q−, R− indicano gli interi, i razionali, i realinegativi, rispettivamente.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 72

Go Back

Full Screen

Close

Quit

3. Definire un insieme

Modi per definire un insieme:

• Modo esplicito: si elencano tutti gli elementi dell’in-sieme

Esempio: A = {−2,−1, 0, 1, 2}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 72

Go Back

Full Screen

Close

Quit




Esempio: A = {−2,−1, 0, 1, 2}

• Modo implicito: si elencano le proprieta che carat-terizzano gli elementi dell’insieme

Esempio: A = {x intero, − 2 ≤ x ≤ 2}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 72

Go Back

Full Screen

Close

Quit




Esempio: A = {−2,−1, 0, 1, 2}

• Modo implicito: si elencano le proprieta che carat-terizzano gli elementi dell’insieme

Esempio: A = {x intero, − 2 ≤ x ≤ 2}

• Rappresentazione grafica: Diagrammi di Eulero-Venn

Esempio:

A =



http://it.wikipedia.org/wiki/Eulero

https://it.wikipedia.org/wiki/John_Venn


Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 72

Go Back

Full Screen

Close

Quit

Per indicare che a e un elemento dell’insieme A si scrive

a ∈ Ae si legge a appartiene all’insieme A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 72

Go Back

Full Screen

Close

Quit



Per indicare che b non e un elemento dell’insieme A si scrive

b 6∈ Ae si legge b non appartiene all’insieme A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 72

Go Back

Full Screen

Close

Quit





Esempi:

• A = {−2,−1, 0, 1, 2}

−1 ∈ A, 3 6∈ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 72

Go Back

Full Screen

Close

Quit





Esempi:

• A = {−2,−1, 0, 1, 2}

−1 ∈ A, 3 6∈ A

• A = {x ∈ N | x = 2n, x2 > 11}

5 6∈ A, 4 ∈ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 72

Go Back

Full Screen

Close

Quit





Esempi:

• A = {−2,−1, 0, 1, 2}

−1 ∈ A, 3 6∈ A

• A = {x ∈ N | x = 2n, x2 > 11}

5 6∈ A, 4 ∈ A

• A =

3 6∈ A, 1 ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 72

Go Back

Full Screen

Close

Quit

4. Inclusione

Definizione: Dati due insiemi A e B si dice che A e unsottoinsieme di B (o che A e incluso in B) e si scrive

A ⊆ B

se ogni elemento di A e un elemento di B, ossia e veral’implicazione

∀ x ∈ A⇒ x ∈ B




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 72

Go Back

Full Screen

Close

Quit

4. Inclusione

Definizione: Dati due insiemi A e B si dice che A e unsottoinsieme di B (o che A e incluso in B) e si scrive

A ⊆ B

se ogni elemento di A e un elemento di B, ossia e veral’implicazione

∀ x ∈ A⇒ x ∈ B

Definizione: Dati due insiemi A e B si dice che A non e unsottoinsieme di B (o che A non e incluso in B) e si scrive

A 6⊆ B

se esiste qualche elemento di A che non appartiene a B, ossiae vera la proposizione

∃ x ∈ A | x 6∈ B




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 7 of 72

Go Back

Full Screen

Close

Quit

Esempi:

• A = {−2,−1, 0, 1, 2, 3, 4, 5}

B = {−1, 4, 5}

C = {−2, 3, 4, 7}

Allora, si ha

B ⊆ A, C 6⊆ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 7 of 72

Go Back

Full Screen

Close

Quit

Esempi:

• A = {−2,−1, 0, 1, 2, 3, 4, 5}

B = {−1, 4, 5}

C = {−2, 3, 4, 7}

Allora, si ha

B ⊆ A, C 6⊆ A

• A = {x ∈ Z | x < 5, }

B = {x ∈ N | x2 < 20, }

C = {x ∈ N | x2 < 30, }

Allora, si ha

B ⊆ A, C 6⊆ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 8 of 72

Go Back

Full Screen

Close

Quit

• Consideriamo i seguenti insiemi

Allora, si haB 6⊆ A, C ⊆ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 9 of 72

Go Back

Full Screen

Close

Quit

5. Sottoinsiemi Propri e Impropri

Definizione: Si definisce insieme vuoto l’insieme privo dielementi e si indica

∅




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 9 of 72

Go Back

Full Screen

Close

Quit



∅

Esempio:

A = {x ∈ N | x2 = −1} = ∅




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 9 of 72

Go Back

Full Screen

Close

Quit



∅

Esempio:

A = {x ∈ N | x2 = −1} = ∅

Osservazione: Dato un generico insieme A per convenzionesi pone

A ⊆ A, ∅ ⊆ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dato un insieme A si definiscono sottoinsiemiimpropri di A l’insieme vuoto e A stesso.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 72

Go Back

Full Screen

Close

Quit


Definizione: Dati due insiemi A e B, si dice che A e unsottoinsieme proprio di B e si scrive

A ⊂ B

se A e un sottoinsieme di B diverso dall’insieme vuoto e daB stesso, ossia

A 6= ∅, ∃ x ∈ B | x 6∈ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 72

Go Back

Full Screen

Close

Quit


Definizione: Dati due insiemi A e B, si dice che A e unsottoinsieme proprio di B e si scrive

A ⊂ B

se A e un sottoinsieme di B diverso dall’insieme vuoto e daB stesso, ossia

A 6= ∅, ∃ x ∈ B | x 6∈ A

Esempio:

A = {a, b, 1}sottoinsiemi impropri di A:

∅, Asottoinsiemi propri di A:

{a}, {b}, {1}, {a, b}, {a, 1}, {b, 1}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dato un insieme A si definisce insieme delleparti di A l’insieme i cui elementi sono i sottoinsiemi di A, esi indica

P(A)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dato un insieme A si definisce insieme delleparti di A l’insieme i cui elementi sono i sottoinsiemi di A, esi indica

P(A)

Esempio:

A = {a, b, 1}

P(A) = {A, ∅, {a}, {b}, {1}, {a, b}, {a, 1}, {b, 1}}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 12 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B si dice che A e ugualea B, e si scrive

A = B

se ogni elemento di A e un elemento di B e viceversa, ovvero

A ⊆ B, B ⊆ A




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 12 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B si dice che A e ugualea B, e si scrive

A = B

se ogni elemento di A e un elemento di B e viceversa, ovvero

A ⊆ B, B ⊆ A

Esempio:A = {x ∈ N | x2 < 11}

B = {0, 1, 2, 3}Allora

A = B




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 13 of 72

Go Back

Full Screen

Close

Quit

6. Operazioni tra Insiemi

Definizione: Dati due insiemi A e B si definisce unione diA e di B, e si indica

A ∪B,l’insieme di tutti gli elementi che stanno in almeno uno deidue insiemi

A ∪B = {x | x ∈ A ∨ x ∈ B}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 13 of 72

Go Back

Full Screen

Close

Quit

6. Operazioni tra Insiemi

Definizione: Dati due insiemi A e B si definisce unione diA e di B, e si indica

A ∪B,l’insieme di tutti gli elementi che stanno in almeno uno deidue insiemi

A ∪B = {x | x ∈ A ∨ x ∈ B}

Esempio:

A = {1, 2, 3}, B = {4, 3}Allora

A ∪B = {1, 2, 3, 4}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 14 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B, si definisce interse-zione di A e di B, e si indica

A ∩B,l’insieme di tutti gli elementi che appartengono sia ad A chea B

A ∩B = {x | x ∈ A ∧ x ∈ B}

Esempio:

A = {1, 2, 3}, B = {4, 3}Allora

A ∩B = {3}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 15 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B, si definisce differenzadi A e B, e si indica

A\B,l’insieme di tutti gli elementi che appartengono ad A e nona B

A\B = {x | x ∈ A ∧ x 6∈ B}

(Analogamente B\A = {x | x ∈ B ∧ x 6∈ A}, detta la diffe-renza di B e A)

Esempio:

A = {1, 2, 3}, B = {4, 3}Allora

A\B = {1, 2} B\A = {4}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 72

Go Back

Full Screen

Close

Quit

Osservazione: Se A ⊆ B allora B\A e detto complemen-tare di A in B.

Esempio:

A = {0, 1}, B = {−1, 0, 1, 4, 3}Allora

A ⊆ B, B\A = {−1, 3, 4}

(Analogamente se B ⊆ A allora A\B e detto complementaredi B in A)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 17 of 72

Go Back

Full Screen

Close

Quit

Sia U un fissato universo, ossia un insieme che contiene tuttigli oggetti che ci possono interessare.

Definizione: Dato un insieme A, si definisce complemen-tare di A, e si indica

CA,

l’insieme di tutti gli elementi che non appartengono ad A

CA = {x ∈ U | x 6∈ A} = {x | x 6∈ A}

Esempio:

A = {x |x < 2}Allora

CA = {x |x ≥ 2}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit

7. Proprieta delle Operazioni

tra Insiemi

1. Idempotenza:A ∪ A = A, A ∩ A = A;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi


2. Associativa:(A ∪B) ∪ C = A ∪ (B ∪ C),(A ∩B) ∩ C = A ∩ (B ∩ C);




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi



3. Commutativa:A ∪B = B ∪ A, A ∩B = B ∩ A;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi




4. Distributiva:A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C),A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C);




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi





5. Legge dei neutri:A ∪ ∅ = A, A ∪ U = U,A ∩ ∅ = ∅, A ∩ U = A;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi






6. Complemento:A ∪C A = U, A ∩C A = ∅,C(CA) = A, C∅ = U, CU = ∅;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 72

Go Back

Full Screen

Close

Quit


tra Insiemi






6. Complemento:A ∪C A = U, A ∩C A = ∅,C(CA) = A, C∅ = U, CU = ∅;

7. Leggi di De Morgan :C(A ∪B) =C A ∩C B,C(A ∩B) =C A ∪C B.



https://it.wikipedia.org/wiki/Augustus_De_Morgan


Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 19 of 72

Go Back

Full Screen

Close

Quit

8. Prodotto Cartesiano

Definizione: Dati due insiemi A e B, si definisce prodottocartesiano di A e B, e si indica

A×B,l’insieme formato dalle coppie ordinate (a, b) in cui a ∈ A eb ∈ B

A×B = {(a, b) | a ∈ A, b ∈ B}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 19 of 72

Go Back

Full Screen

Close

Quit




A×B = {(a, b) | a ∈ A, b ∈ B}

Esempio:

A = {x, y, z}, B = {1, 2}Allora

A×B = {(x, 1), (x, 2), (y, 1), (y, 2), (z, 1), (z, 2)}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 19 of 72

Go Back

Full Screen

Close

Quit




A×B = {(a, b) | a ∈ A, b ∈ B}

Esempio:

A = {x, y, z}, B = {1, 2}Allora

A×B = {(x, 1), (x, 2), (y, 1), (y, 2), (z, 1), (z, 2)}

Osservazione:

• (x, y) 6= (y, x)

• X × Y 6= Y ×X

• (x1, y1) = (x2, y2)⇔ x1 = x2, y1 = y2




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 72

Go Back

Full Screen

Close

Quit

Rappresentazioni del Prodotto Cartesiano:

1. (Tavola Pitagorica)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 72

Go Back

Full Screen

Close

Quit

2. (Piano Cartesiano)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 22 of 72

Go Back

Full Screen

Close

Quit

3. (Diagramma di Eulero - Venn)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 23 of 72

Go Back

Full Screen

Close

Quit

Esercizi:

1. Dimostrare le proprieta delle operazioni tra insiemi;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 23 of 72

Go Back

Full Screen

Close

Quit

Esercizi:


2. SianoA = {x ∈ Z | x4 − 13x2 + 36 = 0}

eB = {x ∈ Z | x|18}.

Determinare A ∪B, A ∩B, A\B e B\A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 23 of 72

Go Back

Full Screen

Close

Quit

Esercizi:


2. SianoA = {x ∈ Z | x4 − 13x2 + 36 = 0}

eB = {x ∈ Z | x|18}.

Determinare A ∪B, A ∩B, A\B e B\A.

3. Siano

A = {a, b}, B = {2, 3} e C = {4, 3}

DeterminareA× (B ∪ C), (A×B) ∪ (A× C), A× (B ∩ C)e (A×B) ∩ (A× C).




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 24 of 72

Go Back

Full Screen

Close

Quit

Proprieta Distributiva, A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C):Verifichiamo

• A ∩ (B ∪ C) ⊆ (A ∩B) ∪ (A ∩ C):

∀x ∈ A ∩ (B ∪ C)⇒ x ∈ A ∧ x ∈ (B ∪ C)⇒

(x ∈ A) ∧ (x ∈ B ∨ x ∈ C)⇒

(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)⇒

(x ∈ A ∩B) ∨ (x ∈ A ∩ C)⇒ x ∈ (A ∩B) ∪ (A ∩ C)

• (A ∩B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C):

∀x ∈ (A ∩B) ∪ (A ∩ C)⇒ x ∈ (A ∩B) ∨ x ∈ (A ∩ C)⇒

(x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)⇒

(x ∈ A) ∧ (x ∈ B ∨ x ∈ C)⇒

x ∈ A ∧ (x ∈ B ∪ C)⇒ x ∈ A ∩ (B ∪ C).




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 72

Go Back

Full Screen

Close

Quit

9. Corrispondenze

Definizione: Dati due insiemi A e B si definisce corrispon-denza o relazione R da A in B una legge che associa elementidi A ad elementi di B.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 72

Go Back

Full Screen

Close

Quit

9. Corrispondenze


N.B. A e detto dominio della corrispondenza,B e detto codominio della corrispondenza.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 72

Go Back

Full Screen

Close

Quit

9. Corrispondenze


N.B. A e detto dominio della corrispondenza,B e detto codominio della corrispondenza.

Esempio:

A = {1, 4,−5} B = {0, 1,−2, 2, 3}

consideriamo la corrispondenza R definita nel modo seguen-te:

aRb, se b2 = a

dove a ∈ A e b ∈ B.

Allora si ha:

1R 1, 4R 2, 4R − 2




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 26 of 72

Go Back

Full Screen

Close

Quit

Osservazione: In una corrispondenza da A in B ad unelemento del dominio puo essere associato piu di un elementoo nessun elemento del codominio.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 26 of 72

Go Back

Full Screen

Close

Quit

Osservazione: In una corrispondenza da A in B ad unelemento del dominio puo essere associato piu di un elementoo nessun elemento del codominio.

Esempio:

A = {1, 4,−5} B = {0, 1,−2, 2, 3}

aRb, se b2 = a

1R 1

4R 2, 4R − 2

6 ∃ b ∈ B | − 5R b




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 27 of 72

Go Back

Full Screen

Close

Quit

Osservazione: Una corrispondenza da A in B puo esserevista come un sottoinsieme del prodotto cartesiano A×B,ossia

ARB = {(a, b) | a ∈ A, b ∈ B, aR b} ⊆ A×B




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 27 of 72

Go Back

Full Screen

Close

Quit

Osservazione: Una corrispondenza da A in B puo esserevista come un sottoinsieme del prodotto cartesiano A×B,ossia

ARB = {(a, b) | a ∈ A, b ∈ B, aR b} ⊆ A×B

Esempio:

A = {1, 4,−5} B = {0, 1,−2, 2, 3}

aRb, se b2 = a

1R 1, 4R 2, 4R − 2

ARB = {(1, 1), (4, 2), (4,−2)} ⊆ A×B




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 28 of 72

Go Back

Full Screen

Close

Quit




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 29 of 72

Go Back

Full Screen

Close

Quit

10. Relazioni

Definizione: Dato un insieme A si definisce relazione bi-naria o semplicemente relazione su A una corrispondenza Rda A in se stesso.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 29 of 72

Go Back

Full Screen

Close

Quit

10. Relazioni


Osservazione: Una relazione su A individua un sottoinsie-me del prodotto cartesiano A× A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 29 of 72

Go Back

Full Screen

Close

Quit

10. Relazioni


Osservazione: Una relazione su A individua un sottoinsie-me del prodotto cartesiano A× A.

Esempio: Sia

A = {0, 1, . . . , 9}

consideriamo la relazione R definita nel modo seguente:

aR a, se a = 2a

dove a, a ∈ A. Allora

ARA = {(a, a) | a, a ∈ A, a = 2a} =

= {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8)}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 30 of 72

Go Back

Full Screen

Close

Quit




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 31 of 72

Go Back

Full Screen

Close

Quit

Osservazione: Una relazione su A puo essere rappresenta-ta anche mediante un grafo in cui i nodi sono gli elementi diA e gli archi le relazioni tra gli elementi di A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 31 of 72

Go Back

Full Screen

Close

Quit

Osservazione: Una relazione su A puo essere rappresenta-ta anche mediante un grafo in cui i nodi sono gli elementi diA e gli archi le relazioni tra gli elementi di A.

Esempio: A = {0, 1, . . . , 9}

ARA = {(a, a) | a, a ∈ A, a = 2a}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 32 of 72

Go Back

Full Screen

Close

Quit

11. Proprieta delle Relazioni

• Proprieta Riflessiva: Una relazione R definita suun insieme A e riflessiva se ogni elemento di A e inrelazione con se stesso:

∀x ∈ A, xRx.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 32 of 72

Go Back

Full Screen

Close

Quit

11. Proprieta delle Relazioni

• Proprieta Riflessiva: Una relazione R definita suun insieme A e riflessiva se ogni elemento di A e inrelazione con se stesso:

∀x ∈ A, xRx.

• Proprieta Simmetrica: Una relazione R definitasu un insieme A e simmetrica se, comunque presi x ey in A, se x e in relazione con y allora y e in relazionecon x:

∀x, y ∈ A, xRy ⇒ yRx.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 33 of 72

Go Back

Full Screen

Close

Quit

• Proprieta Antisimmetrica: Una relazione R de-finita su un insieme A e antisimmetrica se, comunquepresi x e y in A con x 6= y, se x e in relazione con yallora y non e in relazione con x:

∀x, y ∈ A, x 6= y, xRy ⇒ y 6 Rx.

o, equivalentemente, se x e in relazione con y e y e inrelazione con x allora x = y

∀x, y ∈ A, xRy, yRx⇒ x = y.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 33 of 72

Go Back

Full Screen

Close

Quit

• Proprieta Antisimmetrica: Una relazione R de-finita su un insieme A e antisimmetrica se, comunquepresi x e y in A con x 6= y, se x e in relazione con yallora y non e in relazione con x:

∀x, y ∈ A, x 6= y, xRy ⇒ y 6 Rx.

o, equivalentemente, se x e in relazione con y e y e inrelazione con x allora x = y

∀x, y ∈ A, xRy, yRx⇒ x = y.

• Proprieta Transitiva: Una relazione R definita suun insieme A e transitiva se, comunque presi tre ele-menti in A, x, y, z, se x e in relazione con y e y con z,allora x e in relazione con z:

∀x, y, z ∈ A, xRy, yRz ⇒ xRz.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 34 of 72

Go Back

Full Screen

Close

Quit

12. Relazioni d’ordine

Definizione: Una relazione R su un insieme A per la qualevalgono le proprieta riflessiva, antisimmetrica e transitiva edetta relazione d’ordine parziale.

A e detto parzialmente ordinato.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 34 of 72

Go Back

Full Screen

Close

Quit

12. Relazioni d’ordine

Definizione: Una relazione R su un insieme A per la qualevalgono le proprieta riflessiva, antisimmetrica e transitiva edetta relazione d’ordine parziale.

A e detto parzialmente ordinato.

Definizione: Una relazione d’ordine R su un insieme A edetta relazione d’ordine totale se comunque presi due ele-menti a e b in A si ha aRb o bRa, ossia a e b si possonosempre confrontare.

A e detto totalmente ordinato.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 35 of 72

Go Back

Full Screen

Close

Quit

Esempio: Sia A = {1, 2, 3, 6, 12}, consideriamo la relazioneR definita nel modo seguente:

xRy ⇔ x|y, x, y ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 35 of 72

Go Back

Full Screen

Close

Quit



R e una relazione d’ordine parziale su A, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 35 of 72

Go Back

Full Screen

Close

Quit




• R e riflessiva:

∀x ∈ A, x|x




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 35 of 72

Go Back

Full Screen

Close

Quit




• R e riflessiva:

∀x ∈ A, x|x

• R e antisimmetrica:

∀x, y ∈ A, xRy, yRx⇒ x|y, y|x⇒ x = y




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 35 of 72

Go Back

Full Screen

Close

Quit




• R e riflessiva:

∀x ∈ A, x|x


∀x, y ∈ A, xRy, yRx⇒ x|y, y|x⇒ x = y

• R e transitiva:

∀x, y, z ∈ A, xRy, yRz ⇒ x|y, y|z ⇒ x|z ⇒ xRz




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 36 of 72

Go Back

Full Screen

Close

Quit

Graficamente:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 36 of 72

Go Back

Full Screen

Close

Quit

Graficamente:

N.B. La relazione d’ordine non e totale, infatti 2 6 | 3 e 3 6 | 2,dunque 2 6 R3 e 3 6 R2.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit

Esempio: Sia A = R. Consideriamo la relazione R definitanel modo seguente:

xRy ⇔ x ≤ y, x, y ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit


xRy ⇔ x ≤ y, x, y ∈ A.

R e una relazione d’ordine totale su A, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit


xRy ⇔ x ≤ y, x, y ∈ A.


• R e riflessiva:

∀x ∈ A, x ≤ x




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit


xRy ⇔ x ≤ y, x, y ∈ A.


• R e riflessiva:

∀x ∈ A, x ≤ x


∀x, y ∈ A, xRy, yRx⇒ x ≤ y, y ≤ x⇒ x = y




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit


xRy ⇔ x ≤ y, x, y ∈ A.


• R e riflessiva:

∀x ∈ A, x ≤ x



• R e transitiva:

∀x, y, z ∈ A, xRy, yRz ⇒ x ≤ y, y ≤ z ⇒ x ≤ z ⇒ xRz




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 37 of 72

Go Back

Full Screen

Close

Quit


xRy ⇔ x ≤ y, x, y ∈ A.


• R e riflessiva:

∀x ∈ A, x ≤ x



• R e transitiva:

∀x, y, z ∈ A, xRy, yRz ⇒ x ≤ y, y ≤ z ⇒ x ≤ z ⇒ xRz

• e inoltre

∀x, y ∈ A, x ≤ y, oppure y ≤ x.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 38 of 72

Go Back

Full Screen

Close

Quit

13. Relazioni d’equivalenza

Definizione: Una relazione R su un insieme A per la qualevalgono le proprieta riflessiva, simmetrica e transitiva e dettarelazione d’equivalenza.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 38 of 72

Go Back

Full Screen

Close

Quit



Esempi:

1. Sia A un generico insieme. Consideriamo la relazioneR definita nel modo seguente:

xRy ⇔ x = y, x, y ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 38 of 72

Go Back

Full Screen

Close

Quit



Esempi:


xRy ⇔ x = y, x, y ∈ A.

Banalmente si verifica che R e una relazione d’equiva-lenza su A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 39 of 72

Go Back

Full Screen

Close

Quit

2. Sia A = Z. Consideriamo la relazione R definita nelmodo seguente:

aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 39 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

R e una relazione d’equivalenza su A, infatti:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 39 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z, a− a = 0 = 2 · 0⇒ aRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 39 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z, a− a = 0 = 2 · 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z, aRb⇒ a− b = 2 · n, n ∈ Z⇒

b−a = −(a−b) = −(2·n) = 2·(−n) = 2·n′, n′ ∈ Z⇒bRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 39 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z, a− a = 0 = 2 · 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z, aRb⇒ a− b = 2 · n, n ∈ Z⇒

b−a = −(a−b) = −(2·n) = 2·(−n) = 2·n′, n′ ∈ Z⇒bRa;

• R e transitiva:

∀a, b, c ∈ Z, aRb e bRc⇒a− b = 2 · n, b− c = 2 · n′, n, n′ ∈ Z⇒

a−c = (a−b)+(b−c) = 2·n+2·n′ = 2·(n+n′) =

2 ·m, m ∈ Z⇒ aRc.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 40 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab ≥ 0, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 40 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab ≥ 0, a, b ∈ A.

R non e una relazione d’equivalenza su A, infatti:

• R e riflessiva:

∀a ∈ Z, aa = a2 ≥ 0⇒ aRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 40 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab ≥ 0, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z, aa = a2 ≥ 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z, aRb⇒ ab ≥ 0⇒ ba ≥ 0⇒ bRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 40 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab ≥ 0, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z, aa = a2 ≥ 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z, aRb⇒ ab ≥ 0⇒ ba ≥ 0⇒ bRa;

• R non e transitiva:

3R0, 0R(−5) ma 3 6 R(−5).




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 41 of 72

Go Back

Full Screen

Close

Quit

4. Sia A = Z∗. Consideriamo la relazione R definita nelmodo seguente:

aRb⇔ ab > 0, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 41 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z∗, aa = a2 > 0⇒ aRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 41 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z∗, aa = a2 > 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z∗, aRb⇒ ab > 0⇒ ba > 0⇒ bRa;




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 41 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.


• R e riflessiva:

∀a ∈ Z∗, aa = a2 > 0⇒ aRa;

• R e simmetrica:

∀a, b ∈ Z∗, aRb⇒ ab > 0⇒ ba > 0⇒ bRa;

• R e transitiva:

∀a, b, c ∈ Z∗, aRb, bRc⇒ ab > 0, bc > 0⇒

(ab)(bc) > 0⇒ ab2c > 0⇒ ac > 0⇒ aRc.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 42 of 72

Go Back

Full Screen

Close

Quit

Definizione: Sia dato un insieme A e sia R una relazionedi equivalenza definita in A. Sia a ∈ A, si chiama classedi equivalenza di a il sottoinsieme di A formato da tutti glielementi b di A che sono in relazione con a

[a] = {b ∈ A | aRb}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 42 of 72

Go Back

Full Screen

Close

Quit


[a] = {b ∈ A | aRb}.

Osservazione: [a] 6= ∅, infatti a ∈ [a].




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 42 of 72

Go Back

Full Screen

Close

Quit


[a] = {b ∈ A | aRb}.


Esempi:


xRy ⇔ x = y, x, y ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 42 of 72

Go Back

Full Screen

Close

Quit


[a] = {b ∈ A | aRb}.


Esempi:


xRy ⇔ x = y, x, y ∈ A.

Sia a ∈ A, allora

[a] = {b ∈ A | aRb} = {b ∈ A | a = b} = {a}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 43 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 43 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [3]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 43 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [3]:

[3] = {x ∈ Z | 3Rx} = {x ∈ Z | 3− x = 2n, n ∈ Z} =

{x ∈ Z | x = 3− 2n = 3 + 2n′ = 2n′′ + 1, n′′ ∈ Z} =

{x ∈ Z | x = 2n+ 1, n ∈ Z} =

{tutti gli interi dispari}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 44 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 44 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [−5] e [−2]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 44 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.


[−5] = {x ∈ Z∗ | (−5)Rx} = {x ∈ Z∗ | (−5)x > 0} =

{x ∈ Z∗ | x < 0} = Z−




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 44 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.


[−5] = {x ∈ Z∗ | (−5)Rx} = {x ∈ Z∗ | (−5)x > 0} =

{x ∈ Z∗ | x < 0} = Z−

Analogamente

[−2] = {x ∈ Z∗ | (−2)Rx} = {x ∈ Z∗ | (−2)x > 0} =

{x ∈ Z∗ | x < 0} = Z− = [−5].




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 45 of 72

Go Back

Full Screen

Close

Quit

Domanda: Quando due classi di equivalenza coincidono?




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 45 of 72

Go Back

Full Screen

Close

Quit


Criterio: Sia R una relazione di equivalenza definita su uninsieme A. ∀a, b ∈ A,

[a] = [b]⇔ aRb.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 45 of 72

Go Back

Full Screen

Close

Quit


Criterio: Sia R una relazione di equivalenza definita su uninsieme A. ∀a, b ∈ A,

[a] = [b]⇔ aRb.

Dimostrazione:

(⇒): bRb⇒ b ∈ [b] = [a]⇒ b ∈ [a]⇒ aRb.

(⇐): Dimostriamo dapprima che [a] ⊆ [b]. ∀c ∈ [a]⇒ aRc.Ma per ipotesi aRb. Dunque, per la proprieta simmetrica,si ha che bRa. Allora bRa e aRc. Per la transitivita di R,si ha bRc. Dunque c ∈ [b]. In modo analogo si dimostra che[b] ⊆ [a]. In conclusione si ha [a] = [b].




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 46 of 72

Go Back

Full Screen

Close

Quit

Definizione: Sia dato un insieme A e sia R =∼ una relazio-ne di equivalenza definita in A. Si definisce insieme quozientedi A modulo ∼ l’insieme di tutte le classi di equivalenza

A/ ∼= {[a]∼ | a ∈ A}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 46 of 72

Go Back

Full Screen

Close

Quit


A/ ∼= {[a]∼ | a ∈ A}.

Esempi:

1. Sia A un generico insieme. Consideriamo la relazione∼ definita nel modo seguente:

x ∼ y ⇔ x = y, x, y ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 46 of 72

Go Back

Full Screen

Close

Quit


A/ ∼= {[a]∼ | a ∈ A}.

Esempi:


x ∼ y ⇔ x = y, x, y ∈ A.

Sia a ∈ A, allora [a] = {a}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 46 of 72

Go Back

Full Screen

Close

Quit


A/ ∼= {[a]∼ | a ∈ A}.

Esempi:


x ∼ y ⇔ x = y, x, y ∈ A.

Sia a ∈ A, allora [a] = {a}.Dunque

A/ ∼= {[a] | a ∈ A} = {{a} | a ∈ A}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit

2. Sia A = Z. Consideriamo la relazione ∼ definita nelmodo seguente:

a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit


a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [0]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit


a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [0]:

[0] = {x ∈ Z | 0 ∼ x} = {x ∈ Z | 0− x = 2n, n ∈ Z} =

{x ∈ Z | x = −2n = 2n′, n′ ∈ Z} =

{x ∈ Z | x = 2n, n ∈ Z} = {tutti gli interi pari}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit


a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [0]:

[0] = {x ∈ Z | 0 ∼ x} = {x ∈ Z | 0− x = 2n, n ∈ Z} =

{x ∈ Z | x = −2n = 2n′, n′ ∈ Z} =


Determiniamo [1]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit


a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [0]:

[0] = {x ∈ Z | 0 ∼ x} = {x ∈ Z | 0− x = 2n, n ∈ Z} =

{x ∈ Z | x = −2n = 2n′, n′ ∈ Z} =


Determiniamo [1]:

[1] = {x ∈ Z | 1 ∼ x} = {x ∈ Z | 1− x = 2n, n ∈ Z} =

{x ∈ Z | x = 1− 2n = 1 + 2n′, n′ ∈ Z} =

{x ∈ Z | x = 2n+ 1, n ∈ Z} = {tutti gli interi dispari}




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 47 of 72

Go Back

Full Screen

Close

Quit


a ∼ b⇔ a− b = 2n, n ∈ Z, a, b ∈ A.

Determiniamo [0]:

[0] = {x ∈ Z | 0 ∼ x} = {x ∈ Z | 0− x = 2n, n ∈ Z} =

{x ∈ Z | x = −2n = 2n′, n′ ∈ Z} =


Determiniamo [1]:

[1] = {x ∈ Z | 1 ∼ x} = {x ∈ Z | 1− x = 2n, n ∈ Z} =

{x ∈ Z | x = 1− 2n = 1 + 2n′, n′ ∈ Z} =

{x ∈ Z | x = 2n+ 1, n ∈ Z} = {tutti gli interi dispari}

DunqueZ/ ∼= {[0], [1]}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit

3. Sia A = Z∗. Consideriamo la relazione ∼ definita nelmodo seguente:

aRb⇔ ab > 0, a, b ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [1]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [1]:

[1] = {x ∈ Z∗ | 1 ∼ x} = {x ∈ Z∗ | 1x > 0} =

{x ∈ Z∗ | x > 0} = Z+




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [1]:

[1] = {x ∈ Z∗ | 1 ∼ x} = {x ∈ Z∗ | 1x > 0} =

{x ∈ Z∗ | x > 0} = Z+

Determiniamo [−1]:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [1]:

[1] = {x ∈ Z∗ | 1 ∼ x} = {x ∈ Z∗ | 1x > 0} =

{x ∈ Z∗ | x > 0} = Z+


[−1] = {x ∈ Z∗ | (−1) ∼ x} = {x ∈ Z∗ | (−1)x > 0} =

{x ∈ Z∗ | x < 0} = Z−




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 48 of 72

Go Back

Full Screen

Close

Quit


aRb⇔ ab > 0, a, b ∈ A.

Determiniamo [1]:

[1] = {x ∈ Z∗ | 1 ∼ x} = {x ∈ Z∗ | 1x > 0} =

{x ∈ Z∗ | x > 0} = Z+


[−1] = {x ∈ Z∗ | (−1) ∼ x} = {x ∈ Z∗ | (−1)x > 0} =

{x ∈ Z∗ | x < 0} = Z−

DunqueZ/ ∼= {Z+,Z−}.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 49 of 72

Go Back

Full Screen

Close

Quit

Risultato: Sia dato un insieme A e sia ∼ una relazione diequivalenza definita in A. Allora l’insieme quoziente A/ ∼ euna partizione di A, ossia e una famiglia di sottoinsiemi diA non vuoti, a due a due disgiunti e la cui unione e tutto A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 50 of 72

Go Back

Full Screen

Close

Quit

14. Funzioni

Definizione: Dati due insiemi A e B si chiama applicazioneo funzione da A in B una corrispondenza che associa ad ognielemento di A uno ed un solo elemento di B. Si scrive:

f : A→ B

a→ b

dove a ∈ A. Si scrive anche f(a) = b.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 50 of 72

Go Back

Full Screen

Close

Quit

14. Funzioni

Definizione: Dati due insiemi A e B si chiama applicazioneo funzione da A in B una corrispondenza che associa ad ognielemento di A uno ed un solo elemento di B. Si scrive:

f : A→ B

a→ b

dove a ∈ A. Si scrive anche f(a) = b.

N.B. A e detto dominio della funzione,

B e detto codominio della funzione.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 51 of 72

Go Back

Full Screen

Close

Quit

Esempio: Dati gli insiemi

A = {−2,−1, 0, 1, 2} e B = {−4,−3,−2,−1, 0, 1, 2, 3, 4}

si consideri la corrispondenza

f : A→ B

definita da

f(x) = x2, ∀x ∈ A.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 51 of 72

Go Back

Full Screen

Close

Quit

Esempio: Dati gli insiemi

A = {−2,−1, 0, 1, 2} e B = {−4,−3,−2,−1, 0, 1, 2, 3, 4}

si consideri la corrispondenza

f : A→ B

definita da

f(x) = x2, ∀x ∈ A.

f e un’applicazione, infatti ad ogni elemento di A corrispondeuno ed un solo elemento di B

f(−2) = 4 ∈ B, f(−1) = 1 ∈ B, f(0) = 0 ∈ B,

f(1) = 1 ∈ B, f(2) = 4 ∈ B.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 52 of 72

Go Back

Full Screen

Close

Quit

Graficamente:




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 53 of 72

Go Back

Full Screen

Close

Quit

Criterio: Per verificare che una corrispondenza f : A→ Be un’applicazione bisogna verificare

• ∀x ∈ A, ∃f(x) ∈ B;

• ∀x ∈ A, ∃!f(x) (e unico):

x = y ⇒ f(x) = f(y)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 54 of 72

Go Back

Full Screen

Close

Quit

Esempi:

1. Consideriamo la corrispondenza

f : Z→ Z

definita daf(x) = 2x, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 54 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e un’applicazione, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 54 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z



• ∀x ∈ Z, 2x ∈ Z⇒ f(x) = 2x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 54 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z



• ∀x ∈ Z, 2x ∈ Z⇒ f(x) = 2x ∈ Z.

• Siano x, y ∈ Z. Se x = y ⇒ 2x = 2y ⇒ f(x) = f(y)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 55 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 5

a

b, ∀a

b∈ Q.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 55 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 5

a

b, ∀a

b∈ Q.


• ∀ab∈ Q, 5a

b∈ Q⇒ f(a

b) ∈ Q.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 55 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 5

a

b, ∀a

b∈ Q.


• ∀ab∈ Q, 5a

b∈ Q⇒ f(a

b) ∈ Q.

• Siano ab, cd∈ Q. Se a

b= c

d⇒ 5a

b= 5 c

d⇒ f(a

b) = f( c

d)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 56 of 72

Go Back

Full Screen

Close

Quit


f : R→ R

definita da

f(x) =5

2− x, ∀x ∈ R.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 56 of 72

Go Back

Full Screen

Close

Quit


f : R→ R

definita da

f(x) =5

2− x, ∀x ∈ R.

f non e un’applicazione, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 56 of 72

Go Back

Full Screen

Close

Quit


f : R→ R

definita da

f(x) =5

2− x, ∀x ∈ R.


• f(2) 6∈ R




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 57 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 2b, ∀a

b∈ Q.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 57 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 2b, ∀a

b∈ Q.


• ∀ab∈ Q, 2b ∈ Q⇒ f(a

b) ∈ Q.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 57 of 72

Go Back

Full Screen

Close

Quit


f : Q→ Q

definita daf(a

b) = 2b, ∀a

b∈ Q.


• ∀ab∈ Q, 2b ∈ Q⇒ f(a

b) ∈ Q.

• 12

= 36

ma f(12) = 4 6= f(3

6) = 12




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 58 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione. Si dice che f e iniettiva se elementi distinti deldominio hanno immagini distinte nel codominio, ossia

∀x, y ∈ A, x 6= y ⇒ f(x) 6= f(y).




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 58 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione. Si dice che f e iniettiva se elementi distinti deldominio hanno immagini distinte nel codominio, ossia

∀x, y ∈ A, x 6= y ⇒ f(x) 6= f(y).

Esempi:

INIETTIVA NON INIETTIVA




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 59 of 72

Go Back

Full Screen

Close

Quit

Criterio: f : A→ B e iniettiva se, ∀x, y ∈ A,

f(x) = f(y)⇒ x = y




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 60 of 72

Go Back

Full Screen

Close

Quit

Esempi:

1. Consideriamo l’applicazione

f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 60 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e iniettiva, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 60 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e iniettiva, infatti

Siano x, y ∈ Z. Se

f(x) = f(y)⇒

3x+ 1 = 3y + 1⇒ 3x = 3y ⇒ x = y




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 61 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita daf(x) = x2, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 61 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z


f non e iniettiva, infatti




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 61 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z


f non e iniettiva, infatti

1 6= −1 ma f(1) = 1 = f(−1)




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 62 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione. Si dice che f e surgettiva o suriettiva se ognielemento del codominio e immagine di qualche elemento deldominio, ossia

∀b ∈ B, ∃a ∈ A t.c. f(a) = b.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 62 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione. Si dice che f e surgettiva o suriettiva se ognielemento del codominio e immagine di qualche elemento deldominio, ossia

∀b ∈ B, ∃a ∈ A t.c. f(a) = b.

Esempi:

SURGETTIVA NON SURGETTIVA




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 63 of 72

Go Back

Full Screen

Close

Quit

Criterio: f : A→ B e surgettiva se, ∀b ∈ B ∃x ∈ A, taleche l’equazione

f(x) = b

ha soluzione.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z

definita daf(x) = x+ 6, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e surgettiva?




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. x+ 6 = b?




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. x+ 6 = b?

Risolviamox+ 6 = b




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. x+ 6 = b?

Risolviamox+ 6 = b

si ottiene

x = b− 6 ∈ Z




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 64 of 72

Go Back

Full Screen

Close

Quit

Esempi:


f : Z→ Z


f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. x+ 6 = b?

Risolviamox+ 6 = b

si ottiene

x = b− 6 ∈ Z

dunque

∀b ∈ Z ∃x = b− 6 ∈ Z t.c. f(b− 6) = b

f e surgettiva.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 65 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 65 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e surgettiva?




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 65 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. 3x+ 1 = b?




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 65 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. 3x+ 1 = b?

Risolviamo3x+ 1 = b




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 65 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z

definita da

f(x) = 3x+ 1, ∀x ∈ Z.

f e surgettiva?

∀b ∈ Z ∃x ∈ Z t.c. 3x+ 1 = b?

Risolviamo3x+ 1 = b

si ottiene

x =b− 1

36∈ Z

dunque f non e surgettiva, infatti per b = 5 si ha x = 436∈ Z




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 66 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione. Si dice che f e biunivoca se e iniettiva e surgettiva.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 66 of 72

Go Back

Full Screen

Close

Quit


Esempi:

1.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 66 of 72

Go Back

Full Screen

Close

Quit


Esempi:

1.


f : Z→ Z





Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 66 of 72

Go Back

Full Screen

Close

Quit


Esempi:

1.


f : Z→ Z


f e biunivoca




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 67 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione biunivoca. Si definisce funzione inversa di f , e siindica f−1, l’applicazione f−1 : B → A che associa ad ognielemento di B, b ∈ B, quell’unico elemento a ∈ A di cui eimmagine tramite la f , ossia f(a) = b.

∀b ∈ B, f−1(b) = a, dove a ∈ A e f(a) = b




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 67 of 72

Go Back

Full Screen

Close

Quit

Definizione: Dati due insiemi A e B ed f : A→ B un’ap-plicazione biunivoca. Si definisce funzione inversa di f , e siindica f−1, l’applicazione f−1 : B → A che associa ad ognielemento di B, b ∈ B, quell’unico elemento a ∈ A di cui eimmagine tramite la f , ossia f(a) = b.

∀b ∈ B, f−1(b) = a, dove a ∈ A e f(a) = b

Esempio:

f f−1




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 68 of 72

Go Back

Full Screen

Close

Quit

Esempio: Consideriamo l’applicazione

f : Z→ Z





Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 68 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z


Abbiamo visto che f e biunivoca




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 68 of 72

Go Back

Full Screen

Close

Quit


f : Z→ Z


Abbiamo visto che f e biunivoca

La funzione inversa

f−1 : Z→ Ze definita da

f(x) = x− 6, ∀x ∈ Z.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 69 of 72

Go Back

Full Screen

Close

Quit

Definizione: Siano f : A→ B e g : B → C due applicazio-ni. Allora l’applicazione g ◦ f : A→ C definita da

g ◦ f(x) = g(f(x)), ∀x ∈ A

e detta applicazione composta.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 69 of 72

Go Back

Full Screen

Close

Quit


g ◦ f(x) = g(f(x)), ∀x ∈ A


Esempio: Consideriamo

f : Z∗ → N

f(x) = x2, ∀x ∈ Z∗g : N→ Q

g(x) = 3x+52, ∀x ∈ N




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 69 of 72

Go Back

Full Screen

Close

Quit


g ◦ f(x) = g(f(x)), ∀x ∈ A


Esempio: Consideriamo

f : Z∗ → N

f(x) = x2, ∀x ∈ Z∗g : N→ Q

g(x) = 3x+52, ∀x ∈ N

g ◦ f : Z∗ → Q

g ◦ f(x) = g(f(x)) = g(x2) =3x2 + 5

2




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 70 of 72

Go Back

Full Screen

Close

Quit

Esercizi:

1. Delle seguenti relazioni su N verificare quali tra le pro-prieta riflessiva, simmetrica, anti-simmetrica e transi-tiva sono valide:

a) xRy ⇔ x|y;

b) xRy ⇔ hanno lo stesso numero di cifre;

c) xRy ⇔ x− y = 3n per qualche naturale n;

d) xRy ⇔ hanno un divisore comune diverso da 1.

2. Su Z si definisca la seguente relazione:

xRy ⇔ λx− 3y = 1

con λ ∈ Z. Dire per quale valore di λ la relazione R esimmetrica:

a) λ = 0;

b) λ = 12;

c) λ = −3;

d) λ = 2.




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 71 of 72

Go Back

Full Screen

Close

Quit

3. Delle seguenti funzioni dire quali sono iniettive e qualisurgettive:

a) f : R→ R, definita da f(x) = 4x+ 1;

b) g : R∗ → R, definita da g(x) = 2x;

c) h : Z∗ → R, definita da h(x) = 1x2+1

;

4. Siano f : R→ R e g : R→ R due funzioni definite daf(x) = (x− 1)2 e g(x) = x+ 1. Determinare le funzio-ni composte f ◦ g, g ◦ f , f ◦ f e g ◦ g.

SOLUZIONI




Insiemi

Definire un insieme

Inclusione




Prodotto Cartesiano

Corrispondenze

Relazioni



Relazioni . . .

Funzioni

Stampa

Home Page

Title Page

JJ II

J I

Page 72 of 72

Go Back

Full Screen

Close

Quit

15. Stampa



Teoria degli Insiemi - unipa.itmath.unipa.it/~fbenanti/InsiemiAlgebra1201516.pdf · 2015. 10....

Documents

Transcript of Teoria degli Insiemi - unipa.itmath.unipa.it/~fbenanti/InsiemiAlgebra1201516.pdf · 2015. 10....