Appunti e esercizi su insiemi e funzioni

(1)

ELEMENTI DI MATEMATICA E LOGICA

MATEMATICA DISCRETA INSIEMI

Assumiamo come “primitivo” il concetto di insieme e quello di appartenenza di un ele-mento a un insieme. La notazione x ∈ A indica che l’eleele-mento x appartiene all’insieme A. Per indicare che x non appartiene all’insieme A si scrive x 6∈ A.

Un insieme pu`o essere finito (cio`e avere un numero finito di elementi) oppure infinito. Simboli particolari:

∅ denota l’insieme vuoto cio`e l’insieme privo di elementi.

N denota l’insieme dei numeri naturali 0, 1, 2, . . . , quelli che usiamo abitualmente per con-tare.

Z(dal tedesco zahl = numero) denota l’insieme dei numeri interi . . . , −2, −1, 0, 1, 2, . . . Q(da quoziente) denota l’insieme dei numeri razionali p_q con p, q ∈ Z, q 6= 0.

R denota l’insieme dei numeri reali. Altre notazioni:

∃ x significa: esiste x ∀ x significa: per ogni x

P ⇒ Q significa: la proprietà P implica la proprietà Q. Equivalentemente si può scrivere non Q ⇒ non P (questo si usa per dimostrare per assurdo che P implica Q).

P ⇔ Q significa: P se e solo se Q cioè la proprietà P equivale alla proprietà Q.

Per descrivere un insieme basta elencare tutti i suoi elementi tra parentesi graffe, per esempio X = {1, 2, 3}, o i primi elementi seguiti da puntini se l’insieme è infinito e non c’è ambiguità, per esempio per indicare i numeri naturali pari si può scrivere {0, 2, 4, 6, . . . }.

Oppure si può utilizzare una proprietà che caratterizza tutti e soli i suoi elementi, per esempio {x ∈ N | x è divisibile solamente per 1 e per x} (dove | significa: tale che) descrive l’insieme dei numeri positivi primi.

Dati due insiemi A e B si dice che A `e un sottoinsieme di B se ogni elemento di A appartiene a B (cio`e se a ∈ A =⇒ a ∈ B) e si indica A ⊆ B.

Si ha ∅ ⊆ A, per qualunque insieme A.

Due insiemi A e B sono uguali se e solo se ogni elemento di A appartiene a B e viceversa (cio`e se contemporaneamente A ⊆ B e B ⊆ A).

(2)

Dati A, B ⊆ X, si definiscono:

intersezione di A e B l’insieme A ∩ B = {x ∈ X | x ∈ A e x ∈ B} Esempio_{: Se A = {x ∈ N | x pari} e B = {x ∈ N | x > 0 primo}, allora A ∩ B = {2};} se poi C = {x ∈ N | x dispari}, allora A ∩ C = ∅ e B ∩ C = {x ∈ N | x primo, x > 2} = {3, 5, 7, 11, 13, 17, 19, 23 . . . }.

unione di A e B l’insieme A ∪ B = {x ∈ X | x ∈ A o x ∈ B} Esempio_{: Se A, B, C sono come sopra si ha A∪B = {x ∈ N | x pari o primo}, A∪C = N} e B ∪ C = {2} ∪ C, perch´e l’unico numero primo positivo non dispari `e 2.

complementare di A in X l’insieme CX(A) = {x ∈ X | x /∈ A} (l’indice X si omette se non c’`e ambiguit`a).

Esempio_{: C}_N_{(N) = ∅, C}_N_{(∅) = N e pi´}_{u in generale C}_X_{(X) = ∅, C}_X_{(∅) = X per ogni} insieme X. Inoltre, se A e C sono come sopra, si ha CN(A) = C, CN(C) = A

differenza l’insieme B\A = {b ∈ B | b /∈ A} Esempio_{: Se B e C sono come sopra si ha B\C = {2}.}

prodotto cartesiano di A e B l’insieme delle coppie ordinate che hanno il primo ele-mento in A e il secondo in B, cio`e A × B = {(a, b) | a ∈ A, b ∈ B}.

Per ordinate si intende che se invertiamo l’ordine degli elementi di una coppia otteniamo un coppia differente, per esempio (1, 2) 6= (2, 1).

Pi´u in generale se A1, A2, . . . , An sono insiemi, indichiamo con A1× A2× . . . × An l’insieme

delle n-uple ordinate (x1, x2, . . . , xn) la cui i-esima componente xi `e un elemento di Ai. Si

denota con An _{il prodotto cartesiano di n copie di A, cio`e A}n _{= A × A × · · · × A.}

Esempio_{: D×E = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)}, se D = {1, 2, 3} e E = {1, 2},} mentre E × D = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}. Entrambi hanno 3 · 2 = 6 = 2 · 3 elementi. Si pu`o osservare che (D × E) ∩ (E × D) = {(1, 1), (1, 2), (2, 1), (2, 2)} = E × E, mentre (D × E) ∪ (E × D) = (D × D)\{3, 3} = (D × D)\(CD(E) × CD(E)). Questo accade

ogni volta che uno dei due insiemi `e contenuto nell’altro.

Valgono le seguenti propriet`a la cui prova `e lasciata per esercizio:

1) A ∩ ∅ = ∅ A ∩ A = A 2) A ∪ ∅ = A A ∪ A = A 3) A ∪ B = B ⇐⇒ A ⊆ B 4) A ∩ B = A ⇐⇒ A ⊆ B 5) A ∪ (B ∪ C) = (A ∪ B) ∪ C e A ∩ (B ∩ C) = (A ∩ B) ∩ C (proprietà associativa) 6) A ∪ B = B ∪ A e A ∩ B = B ∩ A (proprietà commutativa) 7) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) e (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) (proprietà distributiva) 8) CX(CX(A)) = A CX(∅) = X CX(X) = ∅ 9) CX(A) ⊇ CX(B) ⇐⇒ A ⊆ B 10) B\A = CB(A ∩ B) 11) CX(A ∩ B) = CX(A) ∪ CX(B) 12) CX(A ∪ B) = CX(A) ∩ CX(B) Esercizi:

1) Determinare tutti i sottoinsiemi di ciascuno dei seguenti insiemi: {a}, {a, b}, {{1, 2}, x}, {2, 3, 5}, {{1, 2}, {3, 4}}, ∅, {∅}.

(3)

3) Se A e B hanno rispettivamente 17 e 22 elementi e A ∪ B ne ha 30, quanti ne ha A ∩ B? 4) Siano A, B e C insiemi. Provare che A ∩ B = A se e solo se A ∪ B = B.

5) Siano X = {n ∈ N | n < 10}, Y = {n ∈ N | n > 5}, Z = {n ∈ N | n `e multiplo di 3}. Determinare: X ∩ Y, X ∩ Z, Y ∩ Z, X ∩ Y ∩ Z, CN(X ∩ Y ), CN(X ∩ Z), X ∪ Y, X ∪ Z,

Y ∪ Z, X ∪ Y ∪ Z, CN(X ∪ Y ), CN(X ∪ Z), X ∪ Y ∩ Z, X ∩ Y ∪ Z.

6) Siano A l’insieme dei numeri naturali pari, B = {n ∈ N | n `e multiplo di 3} (a) `e vero che A ∪ B = N?

(b) determinare A ∩ B.

7) Siano A = {n ∈ N | n è multiplo di 3}, B = {n ∈ N | n è multiplo di 4}, C = {n ∈ N | n è multiplo di 6}, D = {n ∈ N | n è multiplo di 12}. Provare che A ∩ B = B ∩ C = D. 8) Siano A = {(x, y) ∈ R2 _{| x}2_{+ y}2 _{= 0},} _{B = {(x, y) ∈ R}2 _{| x = 0},} C = {(x, y) ∈ R2 _{| y = 0},} D = {(x, y) ∈ R2 _{| xy = 0}.} Provare che A ( B ( D, A = B ∩ C e D = B ∪ C.

9) Siano A, B, C ⊆ X. Provare che (A ∪ B) ∩ CX(B) = A ⇐⇒ A ∩ B = ∅

A ∩ B = C, B ∩ C = A, C ∩ A = B ⇐⇒ A = B = C 10) Provare con un esempio che A ∩ B = A ∩ C =⇒/ B = C 11) Provare con un esempio che A ∪ B = A ∪ C =⇒/ B = C 12) Sia A = {1, 2, 3}, determinare A2

= A × A.

13) Siano A = {1, 2, 3} e B = {0, 2}; determinare (A × B) ∩ (B × A) e (A × B) ∪ (B × A). 14) Date le coppie (1, 1), (−1, 1), (1, −1), (−3, 0), (0, −2) dire quali appartengono a N × Z.

Le definizioni di unione e intersezione di due insiemi si estendono facilmente al caso di un insieme (o famiglia) F di insiemi ponendo

[

A∈F

A = {x | x ∈ A per qualche A ∈ F} \

A∈F

A = {x | x ∈ A per ogni A ∈ F}

Esempio_{: per ogni j ∈ N sia A}_j _{= {n ∈ Z | n 6= 2 j e n 6= −2 j} e sia F = {A}_j _{| j ∈ N}.} Allora A0 = Z − {0}, A1 = Z − {2, −2}, A2 = Z − {4, −4}, ... e quindi si ha S A∈F A = S i∈N Aj = Z e T A∈F A = T j∈N Aj = {x ∈ Z | x `e dispari} Esercizi:

1) Per ogni n ∈ N sia An= {x ∈ N | x 6= 2n}

(a) Determinare A1∩ A2, A1∪ A2;

(b) Per ogni n ∈ N determinare CN(An);

(c) Dire per quali valori di m e n valgono le relazioni An ⊆ Am, An ⊇ Am, An= Am

2) Per ogni n ∈ N sia An= {x ∈ N | x > n}.

(a) Determinare A100∩ A3 e A100∪ A3;

(b) per ogni n ∈ N determinare CN(An);

(c) dire per quali valori di m e n valgono le relazioni An⊆ Am, An ⊇ Am, An = Am;

3) Determinare l’unione e l’intersezione delle seguenti famiglie di insiemi: Aj = {x ∈ Z | x ≤ j} (j ∈ N);

Bj = {x ∈ R | j ≤ x ≤ j + 1} (j ∈ Z);

(4)

RELAZIONI E FUNZIONI

Una relazione o corrispondenza R tra due insiemi non vuoti A e B `e un modo di associare elementi di A con elementi di B. Essa `e data da un sottoinsieme R 6= ∅ del prodotto cartesiano A × B: diremo che a ∈ A e b ∈ B sono in relazione (o corrispondenti) se (a, b) ∈ R e scriveremo aRb.

Data una relazione R ⊆ A × B, si dice relazione inversa di R la relazione Ro _{= {(b, a) ∈ B × A | (a, b) ∈ R} ⊆ B × A.}

Dati due insiemi A e B, si dice applicazione (o funzione) di A in B, e si denota f : A −→ B , una relazione che ad ogni elemento a ∈ A associa uno e un solo elemento b ∈ B. Tale b si dice immagine di a mediante f e si scrive b = f (a). Gli insiemi A e B si dicono rispettivamente dominio e codominio dell’applicazione f .

Un’applicazione `e determinata quando sono dati il dominio, il codominio e l’immagine di ogni elemento del dominio.

Esempi:

f : N → N data da f (x) = 2x + 1 per ogni x ∈ N; g : Z → N data da g(x) =

₀ _{∀x pari} 1 ∀x dispari

Data un’applicazione f : A −→ B e dati S ⊆ A, T ⊆ B, b ∈ B si definiscono: immaginedi S l’insieme f (S) = {b ∈ B | ∃ a ∈ S b = f (a)}

(in particolare f (A) si dice immagine di f e si denota anche Imf ); controimmaginedi b l’insieme f−1 (b) = {a ∈ A | f (a) = b}; controimmaginedi T l’insieme f−1 (T ) = {a ∈ A | f (a) ∈ T } =S b∈T f −1 (b); Un’applicazione f : A −→ B si dice iniettiva se

∀a1, a2 ∈ A a1 6= a2 =⇒ f (a1) 6= f (a2)

o equivalentemente se f (a1) = f (a2) =⇒ a1 = a2

o anche se e solo se f−1

(b) `e costituita da un solo elemento ∀ b ∈ Imf. Un’applicazione f : A −→ B si dice surgettiva se

Imf = B

o equivalentemente se ∀ b ∈ B ∃ a ∈ A tale che f (a) = b o ancora se e solo se f−1

(b) 6= ∅ ∀ b ∈ B.

Un’applicazione f : A −→ B si dice bigettiva se `e iniettiva e surgettiva e in tal caso si chiama anche corrispondenza biunivoca.

Esempi:

• idA : A −→ A definita da f (a) = a ∀ a ∈ A si dice applicazione identica ed `e bigettiva.

• Si dice che f : A −→ B `e un’applicazione costante se, fissato b0 ∈ B, si ha f (a) =

b0 ∀ a ∈ A.

(5)

Esercizi: Provare che:

1) Se A = {a1, . . . , an} e B = {b1, . . . , bs} sono insiemi finiti, allora

∃f : A −→ B iniettiva ⇐⇒ n ≤ s ∃f : A −→ B surgettiva ⇐⇒ n ≥ s ∃f : A −→ B bigettiva ⇐⇒ n = s

2) Sia f : A −→ B un’applicazione e siano A1, A2 ⊆ A, B1, B2 ⊆ B. Allora:

(i) A1 ⊆ A2 =⇒ f (A1) ⊆ f (A2)

(ii) B1 ⊆ B2 =⇒ f−1(B1) ⊆ f−1(B2)

(iii) f (A1∩ A2) ⊆ f (A1) ∩ f (A2) ; dare anche un esempio in cui l’uguaglianza non vale

(iv) f (A1∪ A2) = f (A1) ∪ f (A2)

(v) f−1_(B

1∩ B2) = f−1(B1) ∩ f−1(B2)

(vi) f−1

(B1∪ B2) = f−1(B1) ∪ f−1(B2)

3) Sia f : A −→ B un’applicazione e siano C ⊆ A, D ⊆ B. Allora: (i) f−1

(f (C)) ⊇ C; dare anche un esempio in cui l’uguaglianza non vale (ii) f (f−1_{(D) ⊆ D; dare anche un esempio in cui l’uguaglianza non vale}

(iii) f (f−1_{(D) = D ∩ Imf}

4) Sia f : A −→ B un’applicazione. Sono fatti equivalenti: (i) f `e iniettiva

(ii) f−1

(f (C)) = C ∀ C ⊆ A

(iii) f (A1∩ A2) = f (A1) ∩ f (A2) ∀ A1, A2 ⊆ A

(iv) ∀ A1, A2 ⊆ A tali che A1 ∩ A2 = ∅ si ha f (A1) ∩ f (A2) = ∅

5) Sia f : A −→ B un’applicazione. Sono fatti equivalenti: (i) f `e surgettiva

(ii) f (f−1

(D) = D ∀ D ⊆ B Applicazioni composte

Applicazioni composteApplicazioni composte

Date due applicazioni f : A −→ B e g : B −→ C si dice applicazione composta di f e g l’applicazione definita nel modo seguente:

g ◦ f : A −→ C a −→ g(f (a))

Esercizio 1. _{Date due applicazioni f : A −→ B e g : B −→ C provare che per ogni D ⊆ C} si ha:

(g ◦ f )−1

(D) = f−1

(g−1

(D))

Esercizio 2. _{Date due applicazioni f : A −→ B e g : B −→ C provare che valgono le} seguenti propriet`a:

(1) f, g iniettive =⇒ g ◦ f iniettiva (2) f, g surgettive =⇒ g ◦ f surgettiva (3) g ◦ f iniettiva =⇒ f iniettiva (4) g ◦ f surgettiva =⇒ g surgettiva

(6)

Provare inoltre, fornendo esempi opportuni, che non vale il viceversa per nessuna delle propriet`a (1), (2), (3), (4).

Osserviamo che dalle propriet`a (3) e (4) dell’esercizio 2 discende immediatamente che: Date due applicazioni f : A −→ B e g : B −→ A si ha

(i) g ◦ f = idA =⇒ f iniettiva e g surgettiva

(ii) f ◦ g = idB =⇒ f surgettiva e g iniettiva.

Se f : A −→ B `e un’applicazione bigettiva, la relazione inversa `e ancora un’applicazione g : B −→ A definita nel modo seguente: ∀ b ∈ B si pone g(b) = ab dove {ab} = f−1(b).

Tale applicazione g si dice inversa di f e si denota con f−1

. Provare che f−1

: B −→ A `e l’unica applicazione tale che f−1_{◦ f = id}

A e che si ha anche

f ◦ f−1_{= id}

B. Da questo segue che f−1 `e bigettiva e la sua inversa `e f .

Viceversa se f : A −→ B `e un’applicazione e ∃f−1_{tale che f}−1_{◦f = id}

A e f ◦f−1 = idB

allora f `e bigettiva.

Esercizio 3. _{Date due applicazioni f : A −→ B e g : B −→ C bigettive, provare che} (g ◦ f )−1_{= f}−1_{◦ g}−1_.

Osserviamo inoltre che se f : A −→ B `e un’applicazione iniettiva, si pu`o sempre definire un’applicazione g : B −→ A tale che g ◦ f = idA. Infatti se b ∈ Imf , allora f−1(b) = {ab}

`e costituita da un solo elemento e si pone g(b) = ab; se b /∈ Imf si pone g(b) = a0 dove a0 `e

un elemento di A scelto arbitrariamente.

Se f non `e surgettiva, un’applicazione g tale che g ◦ f = idA non `e univocamente

deter-minata e ogni siffatta applicazione risulta non iniettiva.

Se f : A −→ B `e un’applicazione surgettiva si pu`o sempre definire un’applicazione g : B −→ A tale che f ◦ g = idB. Infatti se b ∈ B, allora f−1(b) 6= ∅ e si pone g(b) = a dove a

`e un elemento di f−1

(b) scelto arbitrariamente.

Chiaramente se f non `e iniettiva, un’applicazione g tale che f ◦ g = idB non `e

univoca-mente determinata e ogni siffatta applicazione risulta non surgettiva. Esercizi:

1) Stabilire quali delle seguenti relazioni sono funzioni. In caso affermativo dire se sono iniettive e/o surgettive e per quelle bigettive determinare l’inversa.

a) f1 : R → R , f1(x) = 3x+2₅ ; b) f2 : Q → Z , f2(p_q) = pq ; c) f3 : Z → N , f3(n) = _{2n − 1} _se _{n > 0} −2n se n ≤ 0 d) f4 : R2 → R , f4(x, y) = x ; e) f5 : N → N2 , f5(a) = (a, a + 1) ; f) f6 : R → R, f6(x) = x2 ; g) f7 : R2 → R2 , f7(x, y) = (2x + y, x − 2y) .

2) Esiste un’applicazione f : R → R tale che f ({1, 2}) = {1,1 3, π}?

3) Sia f : R2 _{→ R data da f (x, y) = xy. Determinare f}−1

(0) e f−1

(1).

4) Siano f : R → R2 _{data da f (x) = (x, 3) e g : R}2 _{→ R data da g(x, y) = x + y.}

Determinare le applicazioni composte g ◦ f e f ◦ g. Determinare (g ◦ f )−1

(0) e (f ◦ g)−1