N = {0, 1, 2, 3, 4,..., } Z = {..., 4, 3, 2, 1, 0, 1, 2, 3, 4,... } Q è l insieme dei numeri numeri razionali,

(1)

Gli insiemi numerici che lo studente conosce sono:

N ⁼ {0, 1, 2, 3, 4, . . . , } insieme dei numeri naturali

Z ⁼ {. . . , −4, −3, −2, −1, 0, 1, 2, 3, 4, . . . } insieme dei numeri relativi

Q ^`e l’insieme dei numeri numeri razionali, ovvero dei numeri della forma ^p

q, dove p e q sono numeri relativi e q `e diverso da 0. I numeri razionali possono essere rappresentati come numeri decimali periodici.

(2)

Con il simbolo R si indica l’insieme dei numeri reali, che contiene sia i numeri razionali che i numeri irrazionali, come √

2, π o il numero di nepero e, che si rappresentano come numeri decimali non periodici.

E opportuno introdurre alcuni simboli.`

Il simbolo di appartenenza di un oggetto ad un insieme `e:

” ∈ ”

si legge: ”appartiene” oppure ”`e elemento di”. Ad esempio:

3 ∈ N^, ^{−1 ∈} Z^,

5

3 ∈ Q^, ⁻

√5 ∈ R

(3)

I simboli di inclusione sono:







⊂

⊆

il primo indica l’inclusione stretta o propria (che pu`o essere anche scritta come $) tra insiemi e si legge: ”`e incluso (oppure

è contenuto) propriamente o strettamente” o anche ”è sottoinsieme proprio”, il secondo si legge ”è incluso (o uguale)” oppure

”`e contenuto (o uguale)”. Esempi: N ^⊂ Z^, Z ^⊂ Q^.

Definizione 1 Si dice che due insiemi A e B sono uguali, e si scrive A = B, se essi hanno gli stessi elementi.

(4)

E chiaro, quindi, che A = B se e soltanto se A ⊆ B e B ⊆ A.` Osservazione 2 Quali che siano gli insiemi A, B, C si ha:

1. A ⊆ A

2. se A ⊆ B e B ⊆ A allora A = B

3. se A ⊆ B e B ⊆ C allora A ⊆ C

(5)

Naturalmente ci sono le negazioni:

”non appartiene”: /∈ esempi: −3 /∈ N^, ¹₃ ^∈^/ Z^, ^{π /}^∈ Q

”non `e contenuto”: * esempi: Z * N^, R * Q^.

Osservazione `E possibile considerare un insieme che non ha elementi, che si chiame insieme vuoto e si indica con il simbolo

∅.

Esso `e sottoinsieme di qualunque insieme.

(6)

Si può assegnare un insieme enumerando i suoi elementi (nel caso questo sia possibile), oppure tramite una proprietà caratteristica, ovvero una proprietà che verificano tutti e soli gli elementi dell’insieme che si vuole definire. Si scrive:

A = {x ∈ U | P(x)} oppure A = {x ∈ U : P(x)}

Esempi: {x ∈ Z : x > −3}, {3n | n ∈ N^}.

(7)

Quantificatori:







∀ quantificatore universale

∃ quantificatore esistenziale il primo si legge ”per ogni”, il secondo si legge ”esiste”.

Si usa anche il simbolo

∃|

che vuol dire ”esiste ed `e unico”.

(8)

Esempi:

(∀n ∈ N^{) (3n ∈} N⁾

Sia P l’insieme dei numeri pari. Allora si pu`o scrivere P ⁼ {n ∈ Z ^: ^{∃m ∈} Z tale che n = 2m}.

L’insieme D dei numeri dispari pu`o essere scritto come D ⁼ {n ∈ Z ^: ^{∃h ∈} Z tale che n = 2h + 1}.

(∀x)(x /∈ ∅)

(∀A insieme)(∅ ⊆ A)

(9)

Connettivi logici

congiunzione: ∧ che si legge ”e”

disgiunzione: ∨ che si legge ”o”.

Esempi: (8 ∈ P⁾ ∧ (8 `e divisibile per 4) sia n ∈ Z allora: (n ∈ P⁾ ∨ (n ∈ D^).

(10)

Definizione 3 Dati due insiemi A e B si definiscono l’unione A ∪ B e l’intersezione A ∩ B come segue:

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

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

Si osserva subito che per ogni insieme A A ∪ ∅ = A A ∩ ∅ = ∅ e che se A ⊆ B allora si ha

A ∪ B = B A ∩ B = A.

(11)

1. (A ∪ B) ∪ C = A ∪ (B ∪ C) proprietà associativa dell’unione 2. (A∩B)∩C = A∩(B∩C) proprietà associativa dell’intersezione 3. A ∪ B = B ∪ A proprietà commutativa dell’unione

4. A ∩ B = B ∩ A propriet`a commutativa dell’intersezione

5. (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) 6. (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) 5. propriet`a distributive dell’intersezione rispetto all’unione,

6. propriet`a distributive dell’unione rispetto all’intersezione.

(12)

Definizione 4 Sia A insieme e B ⊆ A si definisce il complementare di B rispetto ad A:

{A(B) = {x ∈ A : x /∈ B}.

Si ha ovviamente:

{A(A) = ∅; {A(∅) = A; B ∪ {A(B) = A; B ∩ {A(B) = ∅ Si dimostrano le LEGGI DI DE MORGAN:

{A(B ∪ C) = {A(B) ∩ {A(C); {A(B ∩ C) = {A(B) ∪ {A(C) Definizione 5 L’insieme:

A r B = {x ∈ A : x /∈ B}

si dice insieme differenza tra l’insieme A e l’insieme B

(13)

Definizione 6 Sia A un insieme. Si dice insieme delle parti di A e si indica con P(A) l’insieme formato da tutti i sottoinsiemi di A. In simboli:

P(A) = {X : X ⊆ A}

E ovvio che A ∈ P(A), ∅ ∈ P(A), se X ∈ P(A), Y ∈ P(A), allora` X ∪ Y ∈ P(A) e X ∩ Y ∈ P(A).

Definizione 7 Siano A e B insiemi. Si definisce il prodotto cartesiano:

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

Naturalmente si ha: A × ∅ = ∅ × A = ∅.

Definizione 8 Siano A e B insiemi. Si dice relazione tra A e B un qualunque sottoinsieme del prodotto cartesiano.

(14)

Sia A un insieme ed R una relazione tra gli elementi di A, cio`e R ⊆ A × A.

Definizione 9 Si dice che R `e riflessiva se `e verificata la sequente condizione:

(∀a ∈ A) ((a, a) ∈ R).

Osservazione 10 Ovviamente, perch`e R non sia riflessiva basta che esista un solo elemento x ∈ A tale che (x, x) /∈ A.

Definizione 11 Si dice che R `e antiriflessiva se `e verificata la sequente condizione:

(∀a ∈ A) ((a, a) /∈ R).

(15)

Esempi Delle relazioni sull’insieme A = {α, β, γ}

R₁ = {(α, α), (β, β), (γ, γ), (α, β), (α, γ)}

R₂ = {(α, α), (β, β), (α, β), (β, γ)}

R₃ = {(α, β), (β, α), (γ, β), (β, γ), (γ, γ)}

R₄ = {(α, β), (β, α), (α, γ)}

R₅ = {(α, α), (β, β), (γ, γ), (α, β), (β, α)}

sono riflessive R₁ e R₅, `e antiriflessiva R₄ mentre R₂ e R₃ non sono riflessive ne’ antiriflessive.

(16)

Definizione 12 Si dice che R `e simmetrica se `e verificata la sequente condizione:

(∀a, b ∈ A) ((a, b) ∈ R ⇒ (b, a) ∈ R).

Osservazione 13 Naturalmente `e sufficiente che esista una sola coppia (x, y) ∈ R, x 6= y, tale che (y, x) /∈ R perch`e R non sia simmetrica.

Definizione 14 Si dice che R `e antisimmetrica se `e verificata la sequente condizione:

(∀a, b ∈ A) ((a, b) ∈ R ∧ (b, a) ∈ R) ⇒ a = b.

Esempi Si ha: R₁ e R₂ sono antisimmetriche, R₃ e R₅ sono simmetriche, R₄ non `e simmetrica ne’ antisimmetrica.

(17)

Definizione 15 Si dice che R `e transitiva se `e verificata la sequente condizione:

(∀a, b, c ∈ A) ((a, b) ∈ R ∧ (b, c) ∈ R) ⇒ (a, c) ∈ R.

Osservazione 16 Anche in questo caso `e sufficiente che esi- stano (x, y), (y, z) ∈ R tale che (x, z) /∈ R perch`e R non sia transitiva.

Esempi Si ha: R₁ e R₅ sono transitive, R₂, R₃ e R₄ non lo sono.

(18)

Osservazione Spesso, assegnata una relazione R su un insieme A, si usa la notazione aRb in luogo di (a, b) ∈ R.

Definizione 17 Si dice che una relazione R su un insieme A `e una relazione d’ordine se `e riflessiva, antisimmetrica e transitiva. La coppia ordinata (A, R) (ovvero l’insieme A munito della relazione d’ordine) si chiama insieme ordinato.

Esempio 18 R₁ `e d’ordine.

(19)

Esempio 19 Sia X un insieme. Allora la relazione ” ⊆ ” `e una relazione d’ordine su P(X). Infatti dalla Osservazione 2 segue che per ogni A, B, C sottoinsiemi di X

1. A ⊆ A

2. (A ⊆ B ∧ B ⊆ A) ⇒ A = B

3. (A ⊆ B ∧ B ⊆ C) ⇒ A ⊆ C

(20)

Esempio 20 L’ordinamento naturale ” ≤ ” sull’insieme Z ^dei numeri relativi `e la relazione definita come segue:

∀m, n ∈ Z, si dice che m ≤ n se e solo se ∃h ∈ N tale che n = m+h.

Si verifica che ” ≤ ” `e una relazione d’ordine su Z^.

Definizione 21 Siano m, n ∈ Z^{, m 6= 0.} Si dice che m divide oppure `e un divisore di n (ovvero che n `e un multiplo di m) e si scrive

m | n se esiste h ∈ Z tale che n = mh.

Si osserva subito che un qualunque numero intero divide 0.

(21)

Esempio 22 La relazione “ | ” sull’insieme N^∗ ^:= N r ^{{0} dei} numeri naturali non nulli `e una relazione d’ordine.

Osservazione Sia (A, ≤) un insieme ordinato, X ⊆ A. Allora X `e automaticamente insieme ordinato. Infatti si verifica facilmente che ponendo

∀a, b ∈ X, a ≤_X b ⇔ a ≤ b

la relazione ≤_X `e una relazione d’ordine su X. In genere essa si denota ancora con il simbolo ≤.

Esempio 23 Per ogni n ∈ N^∗ si indica con D_n l’insieme dei divi- sori di n, che per l’osservazione precedente `e un insieme ordinato dalla relazione d’ordine indotta su D_n da “ | ”.

(22)

Definizione 24 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A, x₀ ∈ X. Si dice che x₀ `e minimo di X se:

∀x ∈ X x₀ ≤ x.

Si dice che x₀ `e massimo di X se

∀x ∈ X x ≤ x₀.

Proposizione 25 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A. Se esiste un massimo (o un minimo) di X, esso `e unico.

(23)

Dimostrazione Siano, infatti, x₀ e x₁ due massimi di X. Allora, poichè x₀ è massimo e x₁ ∈ X, si ha x₁ ≤ x₀ e, scambiando i ruoli di x₀ e x₁, si ha x₀ ≤ x₁. Per la proprietà antisimmetrica delle relazioni d’ordine deve essere x₀ = x₁. (Analoga la dimostrazione dell’unicità del minimo.)

E quindi lecito scrivere x` ₀ = min(X) se x₀ è il minimo (che si dice anche il più piccolo elemento) di X, oppure x₀ = max(X) se x₀ è il massimo (che si dice anche il più grande elemento) di X.

(24)

Esempi

1. considerato l’insieme ordinato (A, R₁), dove A = {α, β, γ} e R₁ = {(α, α), (β, β), (γ, γ), (α, β), (α, γ)}.

Si ha α = min(A) ma non esiste il massimo di A

2. 0=min(N), ma non esiste il massimo considerando su N ^la relazione d’ordine “ ≤ ” naturale

3. 1 = min(N^∗) ma non esiste il massimo considerando su N^∗ ^la relazione d’ordine “ | ”

(25)

4. considerando il sottoinsieme X = {2, 3, 9, 18} come sottoinsieme dell’insieme ordinato (N^∗, |), esiste max(X) = 18 ma non esiste il minimo di X

5. considerando l’insieme ordinato (D_n, |) si ha min(D_n) = 1, max(D_n) = n

(26)

Definizione 26 Sia (A, ≤) un insieme ordinato, A ⊆ X. Un elemento y ∈ A si dice minorante di X se

(∀x ∈ X)(y ≤ x).

Se X `e dotato di minoranti si dice minorato o limitato inferior- mente.

Definizione 27 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A, minorato, α ∈ A. Si dice che α è estremo inferiore di X se è il più grande dei minoranti.

(27)

In altri termini α `e estremo inferiore di se verifica le seguenti condizioni:

1. (∀x ∈ X) (α ≤ x)

2. ∀ β ∈ A tale che (∀x ∈ X) (β ≤ x) si ha β ≤ α.

Si vede che se esiste un estremo inferiore, esso `e unico, per cui

`e lecito scrivere α = inf (X).

(28)

Definizione 28 Sia (A, ≤) un insieme ordinato, A ⊆ X. Un elemento y ∈ A si dice maggiorante di X se

(∀x ∈ X)(x ≤ y).

Se X `e dotato di maggioranti si dice maggiorato o limitato su- periormente.

Definizione 29 Sia (A, ≤) un insieme ordinato, X un sottoinsieme di A, maggiorato, α ∈ A. Si dice che α è estremo superiore di X se è il più piccolo dei maggioranti.

(29)

In altre parole α `e estremo superiore verifica le seguenti condizioni:

1. (∀x ∈ X) (x ≤ α)

2. ∀ β ∈ A tale che (∀x ∈ X) (x ≤ β) si ha α ≤ β.

Si vede che se esiste un estremo superiore di X, esso `e unico, per cui `e lecito scrivere α = sup(X).

(30)

Osservazione 30 Nel caso X = {x, y}, α = sup(x, y) vuol dire

1. x ≤ α, y ≤ α

2. ∀ β ∈ A tale che x ≤ β, y ≤ β si ha α ≤ β.

Analogamente α = inf (x, y) si scrive

1. α ≤ x, α ≤ y

2. ∀ β ∈ A tale che β ≤ x, β ≤ y si ha β ≤ α.

(31)

Esplicitando la definizione di estremo superiore e inferiore per una coppia di interi nell’insieme ordinato (N^∗, |) cosa si ottiene?

e per due sottoinsiemi di un insieme X nell’insieme ordinato in (P(X), ⊆)?

(32)

Definizione 31 Sia (A, ≤) un insieme ordinato. Si dice che ” ≤ ”

`e una relazione di ordine totale ovvero che (A, ≤) `e totalmente ordinato se e soltanto se

(∀x, y ∈ A) (x ≤ y ∨ y ≤ x).

Nel caso contrario, cioè se ∃x, y tali che x ^{y ∧ y} ^{x, si dice} che ” ≤ ” è una relazione di ordine parziale oppure che (A, ≤) è parzialmente ordinato.

Esempi Sono totalmente ordinati (N^{, ≤), (}Z, ≤); sono parzialmente ordinati (N^∗^{, |), (D}ⁿ, |), (P(X), ⊆), (A, R₁).

(33)

Definizione 32 Sia A insieme, naturalmente non vuoto, R relazione su A. Si dice che R `e una relazione di equivalenza se `e riflessiva, simmetrica e transitiva.

Esempi Sono di equivalenza le seguenti relazioni:

1. R₅ = {(α, α), (β, β), (γ, γ), (α, β), (β, α)} su A = {α, β, γ}

2. R₆ = {(n, m) ∈ Z ^× Z | 2| n − m}

3. R₇ = {(a, b) ∈ Z ^× Z ^{| a}² ^{= b}²^}

4. R₈ = {(x, y) ∈ Z^∗ ^× Z^∗ | x · y > 0}.

(34)

Osservazione 33 Talvolta si usa il simbolo ∃|, che vuol dire ”e- siste ed `e unico”.

Definizione 34 Siano A, B insiemi non vuoti, R una relazione tra elementi di A ed elementi di B. Si dice che R `e una relazione funzionale se e soltanto se

∀a ∈ A ∃|b ∈ B tale che (a, b) ∈ R

Se R `e una relazione funzionale tra A e B, la terna ordinata f = (A, B, R) si dice applicazione o funzione tra A e B. A si dice dominio o insieme di partenza di f , B si dice insieme di arrivo di f . La relazione R si chiama grafico di f .

Quando ci si riferir`a ad applicazioni, si supporr`a implicitamente che l’insieme di partenza e l’insieme di arrivo siano non vuoti.

(35)

Esempi: Siano A = {1, 2, 3, 4}, B = {a, b, c, d, e} allora R = {(1, a), (2, b), (2, c), (3, d), (4, e)}

non `e funzionale,

R⁰ = {(1, a), (2, a), (3, b), (4, c)}

`e funzionale

R⁰⁰ = {(1, a), (2, b)(4, c)}

non `e funzionale.

(36)

D’ora in avanti si user`a la notazione f : A → B

per indicare un’applicazione dall’insieme A all’insieme B. Se, inoltre, R_f è la relazione funzionale tale che f = (A, B, R_f), si porrà b = f (a) se e solamente se (a, b) ∈ R_f. In questo caso si dice che b è l’immagine di a mediante f o il valore assunto da f in a. Pertanto il grafico dell’applicazione f è:

R_f = {(a, f (a)) | a ∈ A}.

(37)

Quindi l’applicazione f⁰ = (A, B, R⁰) precedentemente introdotta si scriver`a nel modo seguente:

f⁰ : A → B tale che f⁰(1) = a, f⁰(2) = a, f⁰(3) = b, f⁰(4) = c.

Osservazione Due applicazioni f : A → B, g : C → D sono uguali se e soltanto se A = C, B = D e ∀a ∈ A f (a) = g(a).

Osservazione Si osservi che un’applicazione è una particolare relazione, mentre non è vero che una qualsiasi relazione è un’applicazione.

(38)

Esempi

1. Siano X e Y insiemi, c ∈ Y . Allora l’applicazione f_c : X → Y tale che ∀x ∈ X f_c(x) = c si dice applicazione costante di costante valore c

2. sia X un insieme. Allora l’applicazione

id_X : X → X tale che ∀x ∈ X id_X^{(x) = x} si dice applicazione identica di X

3. f₁ : Z ^→ Z ^{tale che} ^{∀n ∈} Z ^f1(n) = 2n

(39)

4. f₂ : Z ^→ Z ^{tale che} ^{∀x ∈} Z ^f2(x) = ^x₂ non `e un’applicazione

5. f₃ : P → Z ^{tale che} ^{∀x ∈} P f₃(x) = ₂^x

6. f₄ : Q^∗ ^→ Q ^{tale che} ^{∀x ∈} Q ^f4(x) = ¹_x

7. f₅ : Z ^→ Z ^{tale che} ^{∀a ∈} Z ^f5(a) = a².

(40)

Definizione 35 Data un’applicazione f : A → B e considerato X ⊆ A, si dice immagine di X mediante f il sottoinsieme di B

f (X) = {b ∈ B | (∃a ∈ X)(b = f (a))} = {f (a) | a ∈ X}.

Se Y ⊆ B, si dice controimmagine (o immagine reciproca) di Y mediante f il sottoinsieme di A

f⁻¹(Y ) = {a ∈ A | f (a) ∈ Y }.

(41)

Con riferimento agli esempi precedetemente esaminati:

Esempi 1. ∀A ⊆ X, A 6= ∅, f_c(A) = {c}; sia B ⊆ Y , allora f_c⁻¹(B) = X se c ∈ B mentre f_c⁻¹(B) = ∅ se c /∈ B

2. le immagini e le controimmagini di sottoinsiemi di X mediante l’applicazione identica id_X : X → X rimangono invariati

3. f⁰(A) = {a, b, c}, f⁰({1, 3}) = {a, b}, f⁰⁻¹({a, b, c}) = A;

4. f₁(N^{) =} P∩N^{, f}₁⁻¹⁽D^{) =} ∅; f₃(P^{) =} Z^{, f}₃⁻¹⁽P^{) =} {4n | n ∈ Z^} 5. f₄(Q^∗^{) =} Q^∗^{; f}5(Z^{) =} {0, 1, 4, 9, 16, 25, . . . }; f₅⁻¹({4}) = {±2}.

(42)

PROPRIET `A

Sia f : A → B un’applicazione. Allora per ogni X, X⁰ ⊆ A, e per ogni Y, Y ⁰ ⊆ B si ha

1. f (X ∪ X⁰) = f (X) ∪ f (X⁰)

2. f (X ∩ X⁰) ⊆ f (X) ∩ f (X⁰)

3. f⁻¹(Y ∪ Y ⁰) = f⁻¹(Y ) ∪ f⁻¹(Y ⁰)

4.. f⁻¹(Y ∩ Y ⁰) = f⁻¹(Y ) ∩ f⁻¹(Y ⁰)

(43)

Definizione 36 Si dice che una applicazione f : A → B `e ingettiva o iniettiva se e soltanto se

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

Equivalentemente (1) pu`o essere scritta:

(∀x, x⁰ ∈ A) (f (x) = f (x⁰) ⇒ x = x⁰).

Esempi 1. L’applicazione costante f_c non `e ingettiva (naturalmente se l’insieme X di partenza ha pi`u di un elemento)

2. l’applicazione identica di un qualunque insieme `e ingettiva

3. f⁰ non `e ingettiva

(44)

4. f₁, f₃, f₄ sono ingettive, mentre f₅ non `e ingettiva.

Definizione 37 Si dice che un’applicazione f : A → B `e surgettiva o suriettiva se e soltanto se

(2) (∀y ∈ B) (∃x ∈ A tale che f (x) = y).

Equivalentemente (2) si pu`o scrivere:

f (A) = B.

Esempi 1. Delle applicazioni precedentemente considerate, soltanto f₃ `e surgettiva.

(45)

2. In generale, fermi restando l’insieme di partenza e ”la legge”, se si considera come insieme di arrivo l’immagine dell’applicazione f , si ottiene una nuova applicazione f_] che si dice ridotta di f ed

`e surgettiva. In altre parole se

f : A → B, allora

f_] : A → f (A) tale che ∀x ∈ A, f_](x) = f (x).

(46)

3. In riferimento all’applicazione f⁰, si ha f⁰(A) = {a, b, c} ⊂ B e quindi f_]⁰ : A → {a, b, c} tale che

f_]⁰(1) = a, f_]⁰(2) = a, f_]⁰(3) = b, f_]⁰(4) = c

4. (f₁)_] : Z ^→ P ^{tale che} ∀n ∈ Z ^(f1)_](n) = 2n;

5. (f₄)_] : Q^∗ ^→ Q^∗ ^{tale che} ^{∀x ∈} Q ^(f4)_](x) = ¹_x

6. (f₅)_] : Z → {0, 1, 4, 9, 16, . . . } tale che ∀a ∈ Z ^(f5)_](a) = a².

(47)

Definizione 38 Si dice bigettiva o biettiva o biunivoca ogni applicazione che sia contemporaneamente ingettiva e surgettiva.

Esempi Sono bigettive le applicazioni id^{, (f}₁⁾_]^{, f}₃^{, (f}₄⁾_]^{, .}

Definizione 39 Siano f : A → B, g : B → C. Si dice composta di f e di g l’applicazione

g ◦ f : A → C tale che ∀a ∈ A (g ◦ f )(a) = g(f (a)).

Esempi 1. f : N ^→ N^{, tale che} ^{∀n ∈} N f (n) = 2n, g : N ^→ Z ^{tale che} ^{∀x ∈} N ^{g(x) = −x.}

Allora

g ◦ f : N ^→ Z ^{tale che} ^{∀n ∈} N (g ◦ f )(n) = g(f (n)) = −2n

(48)

2. f : Q r ^{{1} →} Q^{, tale che} ^{∀x ∈} Q r {1} f (x) = _x−1¹ g : Q ^→ Q ^{tale che} ^{∀y ∈} Q ^{g(y) = y}²^.

Allora

g ◦ f : Q r ^{{1} →} Q ^{tale che}

∀x ∈ Q r {1} g ◦ f (x) = g(f (x)) = 1

(x − 1)².

(49)

3. f : Z ^→ Z ^{tale che} ^{∀n ∈} Z, f (n) = n² + n, g : Z ^→ Z ^{tale che} ^{∀m ∈} Z, g(m) = −m.

Allora

(g ◦ f )(n) = g(f (n)) = g(n² + n) = −n² − n;

(f ◦ g)(m) = f (g(m)) = f (−m) = (−m)² + (−m) = m² − m.

Quindi g ◦ f 6= f ◦ g, essendo, ad esempio,

(g ◦ f )(3) = −12 e (f ◦ g)(3) = 6.

Da questo esempio si vede che in generale, anche se `e possibile scambiare l’ordine della composizione di applicazioni, non si ottiene lo stesso risultato.

Osservazione Siano f : A → B, g : B → C, h : C → D. Allora si ha: h ◦ (g ◦ f ) = (h ◦ g) ◦ f

(50)

Proposizione 40 Siano f : A → B, g : B → C. Allora si ha:

1. f ◦ id_A ⁼ id_B ◦ f = f

2. se f e g sono ingettive, allora g ◦ f `e ingettiva

3. se f e g sono surgettive, allora g ◦ f `e surgettiva

4. se f e g sono bigettive, allora g ◦ f `e bigettiva.

Osservazione Pu`o capitare che la composizione di due applicazioni sia ingettiva, surgettiva o bigettiva senza che le due applicazioni componenti lo siano.

(51)

Definizione 41 Sia f : A → B un’applicazione. Si dice che f `e invertibile se esiste g : A → B tale che

g ◦ f = id_A ∧ f ◦ g = id_B^.

L’applicazione g si dice applicazione inversa di f .

Osservazione Se esiste l’spplicazione inversa, essa `e unica.

Teorema 42 Un’applicazione `e invertibile se e solo se `e bigettiva.

(52)

Cenno di dimostrazione Assegnata un’applicazione f : A → B la sua bigettivit`a pu`o essere espressa nel modo che segue:

∀b ∈ B ∃| a ∈ A tale che f (a) = b.

Allora si può considerare l’applicazione g : B → A definita ponendo per ogni b ∈ B g(b) = a, dove a è l’unico elemento di A tale che f (a) = b. Si verifica che g è l’inversa di f . Viceversa si verifica che un’applicazione invertibile è ingettiva e surgettiva.

Usualmente si indicher`a con f⁻¹ l’inversa di un’applicazione invertibile f .

(53)

Esempi 1. L’applicazione identica id_X : X → X di qualunque insieme X ha se’ stessa come inversa.

2. se f `e un’applicazione bigettiva e ha inversa g, allora anche g

`e bigettiva e ha inversa f

3. l’applicazione (f₁)_] : Z ^→ P tale che (f₁)_](n) = 2n `e bigettiva e ha come inversa

g₁ : P → Z ^{tale che} ^{∀m ∈} P g₁(m) = m 2

4. l’applicazione f₃ : P → Z ^{tale che} ^{∀x ∈} P f₃(x) = ₂^x non `e altro che g₁ e quindi ha come inversa (f₁)_]

(54)

5. l’applicazione (f₄)_] : Q^∗ ^→ Q^∗ ^{tale che} ^{∀x ∈} Q^∗ ^(f4)_](x) = ¹_x `e invertibile ed ha come inversa se’ stessa.

6. La funzione inversa della funzione f : R ^→ R ^{tale che} ^{∀x ∈} R f (x) = 3x `e g : R ^→ R ^{tale che} ^{∀x ∈} R ^{g(x) =} ^x₃^.

(55)

Osservazione 43 Siano f : A → B, g : B → C due applicazioni bigettive. Allora g ◦ f ha come inversa f⁻¹ ◦ g⁻¹. Infatti:

(g◦f )◦(f⁻¹◦g⁻¹) = g◦(f ◦f⁻¹)◦g⁻¹ = g◦id_A◦g⁻¹ = g◦g⁻¹ = id_B e analogamente

(f⁻¹ ◦ g⁻¹) ◦ (g ◦ f ) = id_A.

(56)

Definizione 44 Si dice che un insieme X `e infinito se esiste un’applicazione ingettiva ma non surgettiva di X in X.

Esempio Sicuramente l’insieme N dei numeri naturali `e infinito in quanto per esempio l’applicazione f : N ^→ N tale che per ogni n ∈ N f (n) = 2n, `e ingettiva ma non surgettiva.

Osservazione Se X è un insieme infinito ed è contenuto in un insieme Y , allora anche Y è infinito.

Definizione 45 Si dice che un insieme X è finito se è vuoto o se non è infinito.

Teorema 46 Sia X un insieme finito non vuoto. Allora esiste un sottoinsieme J_n = {1, 2, . . . , n} di N ed esiste un’applicazione bigettiva γ : J_n → X.

(57)

Osservazione Nella situazione del Teorema 4, si pu`o scrivere X = {γ(1), γ(2), . . . , γ(n)}. Inoltre si dice che X ha cardinalit`a n e si scrive:

|X| = n.

Definizione 47 Si dice che due insiemi X e Y sono equipotenti Y se esiste una bigezione tra X e Y .

Osservazione Due insiemi finiti X e Y sono equipotenti se e solo se hanno la stessa cardinalit`a (verificata a lezione).

(58)

Osservazione Siano X, Y due insiemi finiti. Allora può esistere un’applicazione ingettiva avente X come insieme di partenza e Y come insieme di arrivo solo se |X| ≤ |Y |; invece può esistere un’applicazione surgettiva solo se |X| ≥ |Y |. Infine, se |X| = |Y | allora un’applicazione f : X → Y è ingettiva se e soltanto se è surgettiva e quindi se e soltanto se è bigettiva.

(59)

Cenni di combinatorica

Definizione 48 Siano n, k ∈ N^∗. Si dice disposizione con ripetizioni di k elementi di classe n una n-pla ordinata con ripetizioni di k oggetti.

Si dice combinazione con ripetizioni di k elementi di classe n una n-pla non ordinata con ripetizioni di k oggetti.

Definizione 49 Siano n, k ∈ N^∗, n ≤ k. Si dice disposizione semplice di k elementi di classe n una n-pla ordinata senza ripetizioni di k oggetti.

Si dice combinazione semplice di k elementi di classe n una n- pla non ordinata senza ripetizioni di k oggetti.

(60)

Proposizione 50 Il numero delle disposizioni con ripetizioni di k elementi di classe n `e kⁿ. (Dimostrato a lezione).

Proposizione 51 Il numero delle disposizioni semplici di k elementi di classe n `e

(k)_n = k · (k − 1) · (k − 2) · . . . · (k − n + 1).

(Dimostrato a lezione)

In particolare il numero delle disposizioni semplici di n elementi di classe n `e

(n)_n = n·(n−1)·(n−2)·. . .·(n−n+1) = n·(n−1)·(n−2)·. . .·1 = n!

(61)

Osservazione Si possono riguardare le disposizioni semplici o con ripetizioni come applicazioni tra insiemi finiti, queste ultime pensate con il modello delle parole. Allora è facile rendersi conto del fatto che il numero delle permutazioni di un insieme di car- dinalità n è n!.

Osservazione Naturalmente n! ha senso nel discorso fatto finora solo per n ∈ N^∗. Comunque si definisce anche

0! = 1.

Corollario 52 Sia A un insieme finito con |A| = n. Allora

|P(A)| = 2ⁿ. (Dimostrato a lezione)

(62)

Definizione 53 Siano k, n interi positivi, con k ≤ n. Si dice coefficiente binomiale il numero

_n k

= (n)_k

k! = n · (n − 1) · . . . · (n − k + 1)

k! = n!

k!(n − k)!

Osservazione Si ha: ⁿ

0

= 1, ⁿ

1

= n, ⁿ

n

= 1.

Osservazione Vale la formula del binomio di Newton:

(a + b)ⁿ =

n X k=0

_n k

a^kb^n−k.

(63)

Proposizione 54 Il numero dei sottoinsiemi di n elementi di un insieme di k elementi, ovvero il numero delle combinazioni semplici di k elementi di classe n `e proprio ^k

n

.

Proposizione 55 Il numero delle combinazioni con ripetizione di k elementi di classe n `e dato da ^k+n−1

n

.

(64)

Proposizione 56 Il numero delle applicazioni surgettive di un insieme di cardinalità n in un insieme di cardinalità m, n ≥ m è:

m X k=1

_m k

(−1)^m−kkⁿ.

Esempi 1. Per n = 3, m = 2

2 X k=1

₂ k

(−1)^2−kk³ = ²

1

(−1)¹ + ²

2

(−1)⁰8 = −2 + 8 = 6 2. per n = 4, m = 3

3 X k=1

₃ k

(−1)^3−kk⁴ = ³

1

(−1)² + ³

2

(−1)¹2⁴ + ³

3

(−1)⁰3⁴

= 3 − 3 · 16 + 81 = 3 − 48 + 81 = 36.