Richiami di Matematica

1. Insiemi, relazioni, funzioni.

2. Cardinalitá degli insiemi infiniti e numerabilitá.

3. Notazione asintotica.

InsiemiDefinizioni di baseDato un insieme A:

x ∈ A: elemento x appartenente ad A B ⊆ A: B è un sottoinsieme di A B ⊂ A: B è un sottoinsieme proprio di A. Se A costituito da un numero finito n di elementi, |A| = n

indica la sua cardinalità ∅: insieme vuoto

DefinizioneDue insiemi A e B si dicono uguali, e si scrive A = B, se ognielemento di A è anche elemento di B e, viceversa, se ognielemento di B è anche elemento di A, cioè

A = B se e solo se (A ⊆ B ∧ B ⊆ A).

Insieme delle parti

DefinizioneL’insieme composto da tutti i sottoinsiemi di un insieme A sidice insieme delle parti di A, e si indica con P(A).

P(A) contiene A e l’insieme vuoto ∅Esercizio: Dimostrare che se A è un insieme finito |P(A)| = 2|A|.

Per questa ragione P(A) viene anche indicato con 2A.

Induzione matematica

Dimostrazione di proprietá di insiemi infiniti

Data una proposizione P(n) definita per un generico numeronaturale n, si ha che essa è vera per tutti i naturali se

P(0) è vera (passo base dell’induzione); per ogni naturale k , P(k) vera (ipotesi induttiva) implica

P(k + 1) vera (passo induttivo).

Esempio: Dimostrare

n∑

i=0

i =n(n + 1)

2.

RelazioniProdotto CartesianoDati due insiemi A e B:

DefinizioneIl prodotto cartesiano di A e B, denotato con A × B, è l’insieme

C =< x , y >| x ∈ A ∧ y ∈ B

,

cioè C è costituito da tutte le possibili coppie ordinate ove ilprimo elemento appartiene ad A ed il secondo a B

Il prodotto cartesiano gode della proprietà associativa, mentrenon gode di quella commutativa.Si usa la notazione An per indicare il prodotto cartesiano di Acon se stesso, ripetuto n volte, cioè per indicare

A × · · · × A.︸ ︷︷ ︸

n volte

Si noti che se A = ∅ o B = ∅ allora A × B = ∅.

Relazione

DefinizioneUna relazione n-aria R su A1, A2, . . . , An è un sottoinsieme delprodotto cartesiano A1 × · · · × An

R ⊆ A1 × · · · × An.

Il generico elemento di una relazione viene indicato con ilsimbolo

< a1, a2, . . . , an >∈ R,

oppure con il simbolo

R(a1, . . . , an);

n viene detto arità della relazione R.

Relazioni binarie

Nel caso delle relazioni binarie (n = 2) si usa anche lanotazione a1Ra2.

Esempio: La relazione binaria < definita sui naturali, èl’insieme R ⊆ N2 definito daR = < x , y >∈ N2 | ∃z ∈ N(z 6= 0 ∧ x + z = y).

Esempio: La relazione quadrato definita sui naturali è l’insiemeR ⊆ N2

R =< x , y >| x2 = y

.

Relazioni d’ordine

DefinizioneUna relazione R ⊆ A2 si dice relazione d’ordine se per ognix , y , z ∈ A valgono le seguenti proprietà

1. < x , x >∈ R (riflessività),

2. < x , y >∈ R∧ < y , x >∈ Rse e solo se x = y(antisimmetria),

3. < x , y >∈ R∧ < y , z >∈ R se e solo se < x , z >∈ R(transitività).

Un insieme A su cui è definita una relazione d’ordine vienedetto insieme parzialmente ordinato.

Relazioni d’ordine

DefinizioneUna relazione d’ordine R ⊆ A2 tale che

< a, b >∈ A2se e solo se aRb ∨ bRa,

dove cioè ogni elemento è in relazione con ogni altro elemento,si dice relazione di ordine totale.

La relazione ≤ è una relazione d’ordine su N. In questo casol’ordinamento è totale in quanto per ogni x ed y si ha che< x , y >∈ R oppure che < y , x >∈ R, oppure valgonoentrambe, nel qual caso si ha che x = y , per antisimmetria.

Esercizio: Dimostrare che la relazione < su N non è unarelazione d’ordine.

Relazioni di Equivalenza

DefinizioneUna relazione R ⊆ A2 si dice relazione di equivalenza se perogni x , y , z ∈ A valgono le seguenti proprietà

1. < x , x >∈ R (riflessività),

2. < x , y >∈ Rse e solo se < y , x >∈ R (simmetria),

3. < x , y >∈ R∧ < y , z >∈ R se e solo se < x , z >∈ R(transitività).

Consideriamo l’insieme delle coppie < n, m > con n ∈ N edm ∈ N+. La relazione

E =<< u, v >,< p, q >>| uq = vp

è una relazione d’equivalenza.

Classi di Equivalenza

DefinizioneUn insieme A su cui sia definita una relazione d’equivalenza Rsi può partizionare in sottoinsiemi, detti classi d’equivalenza,ciascuno dei quali è un sottoinsieme massimale che contienesolo elementi tra loro equivalenti.

Dati un insieme A ed una relazione d’equivalenza R su A2,l’insieme delle classi d’equivalenza di A rispetto a R è dettoinsieme quoziente, e viene normalmente denotato con A/R.

Data una relazione d’equivalenza R ⊆ A2, si dice indice di R, esi denota con ind(R), il numero di elementi di A/R.

Classi di Equivalenza

Esempio: Dato un intero k , definiamo la relazione ≡k , dettacongruenza modulo k , su N2 nel seguente modo:

n≡km se e solo se esistono q, q′, r , con 0 ≤ r < k , tali che

n = qk + rm = q′k + r

Essa è una relazione d’equivalenza e le sue classid’equivalenza sono dette classi resto rispetto alla divisione perk .

Dato un intero k , qual è l’indice della relazione ≡k?

Grafi

Di particolare interesse sono le relazioni rappresentabilimediante grafi.

DefinizioneDato un insieme finito V ed una relazione binaria E ⊆ V × V, lacoppia < V , E > si definisce grafo orientato.

Esempio: Sia dato l’insieme V = A, B, C, D. Consideriamo larelazione E = < A, B >,< A, C >,< A, D >,< B, C >,<C, D >,< B, B >,< B, A >. Rappresentare la relazione comeun grafo orientato

Se la relazione E gode della proprietà simmetrica il grafo puòessere rappresentato senza assegnare un orientamento agliarchi. In tal caso la coppia < V , E > si definisce grafo nonorientato o semplicemente grafo.

Chiusura transitiva

Chiusura transitiva:

DefinizioneSia R una relazione su A2; si definisce chiusura transitiva di R,denotata con R+, la relazione

R+ = < x , y >| ∃y1, . . . , yn ∈ A, con n ≥ 2, y1 = x , yn = y , tali che

〈yi , yi+1〉 ∈ R, i = 1, . . . , n − 1.

Chiusura transitiva e riflessiva

DefinizioneSia R una relazione su A2; si definisce chiusura transitiva eriflessiva di R, denotata con R∗, la relazione

R∗ = R+ ∪ < x , x > | x ∈ A.

Chiusura transitiva

Esercizio: Sia dato un grafo orientato G =< V , E > in cui V èl’insieme dei nodi ed E ⊆ V ×V è l’insieme degli archi orientati.Dimostrare che se R è la relazione tale che xRy se e solo sex = y oppure è possibile raggiungere y a partire da xpercorrendo gli archi secondo il loro orientamento, allora R è lachiusura transitiva e riflessiva della relazione E .

Esercizio: Dato un grafo orientato G =< V , E >, cosarappresentano le classi d’equivalenza del grafoG∗ =< V , E∗ >?

Funzioni

DefinizioneSi dice che R ⊆ X1 × . . . × Xn (n ≥ 2) è una relazionefunzionale tra una (n − 1)-pla di elementi e l’n-esimo elemento,se ∀ < x1, . . . , xn−1 >∈ X1 × . . . × Xn−1 esiste al più unelemento xn ∈ Xn tale che < x1, . . . , xn >∈ R.

La notazione generalmente usata per indicare tra quali insiemiviene realizzata la corrispondenza è:

f : X1 × · · · × Xn−1 7→ Xn.

FunzioniDominio e Codominio di una funzione

DefinizioneData una funzione f : X1 × · · · × Xn−1 7→ Xn, l’insiemeX1 × · · · × Xn−1 viene detto dominio della funzione, dom(f), el’insieme Xn viene detto codominio, cod(f).

Dominio di definizione di una funzione

DefinizioneData una funzione f : X1 × · · · × Xn−1 7→ Xn si chiama dominiodi definizione della funzione f , e lo si indica con la notazionedef(f), il sottoinsieme di dom(f) su cui f é definita.

Immagine di una funzione

DefinizioneSi definisce immagine della funzione f , e lo si indica con lanotazione imm(f) il sottoinsieme di Xn dei valori assunti da f .

Funzioni

Funzioni totali e parziali

DefinizioneUna funzione f : X1 × . . . × Xn−1 7→ Xn viene detta totale sedef (f ) = dom(f ). Nel caso più generale in cui def (f ) ⊆ dom(f ),f viene detta funzione parziale.

Funzione suriettiva

DefinizioneUna funzione f : X1 × · · · × Xn−1 7→ Xn viene detta suriettiva se

imm(f ) = cod(f ).

Funzioni

Funzione Iniettiva

DefinizioneUna funzione f si dice iniettiva o uno-ad-uno (1:1) se facorrispondere ad elementi diversi del dominio di definizioneelementi diversi del codominio.

Funzione Biiettiva

DefinizioneUna funzione si dice biiettiva o biunivoca se è allo stesso tempoiniettiva, suriettiva e totale. Una funzione biiettiva si dice anchebiiezione.

Esercizio: Dimostrare che esiste una biiezione tra l’insieme deisottoinsiemi di un insieme S finito di cardinalità |S| = n e lesequenze binarie di lunghezza n.

Cardinalitá di un insieme infinito

Concetto di Equinumerositá

DefinizioneDue insiemi A e B si dicono equinumerosi se esiste unabiiezione tra di essi.

Esempio: Gli insiemi

lunedì, martedì, . . . , domenica

e5, 7, 31, 50, 64, 70, 75

sono equinumerosi.

Esercizio: Dimostrare che la relazione di equinumerosità è unarelazione d’equivalenza.

Cardinalitá di insiemi finiti

DefinizioneDato un insieme finito A, la sua cardinalità |A| è così definita:

|A| =

0 se A = ∅n seA è equinumeroso a0, 1, . . . , n − 1, conn ≥ 1.

Il numero n può infatti essere definito come la classed’equivalenza di tutti gli insiemi equinumerosi a 0, . . . , n − 1

Insiemi numerabili

DefinizioneUn insieme si dice numerabile se esso è equinumeroso a N.

Per indicare la cardinalità degli insiemi infiniti equinumerosi adN si utilizza il simbolo ℵ0

DefinizioneUn insieme si dice contabile se esso è finito o numerabile.

Teorema: Se un insieme A è equinumeroso a un insieme B,con B ⊆ C, dove C è un insieme contabile, allora anche A ècontabile.

Esempio: L’insieme Z degli interi relativi risulta esserenumerabile cioè |Z| = ℵ0 poiché i suoi elementi possonoessere posti in corrispondenza biunivoca con N tramite labiiezione f : Z 7→ N definita nel seguente modo:

f (i) =

−2i se i ≤ 0

2i − 1 se i > 0.

L’insieme N è propriamente contenuto nell’insieme Z,ciononostante i due insiemi risultano equinumerosi.

Coppia di Cantor

L’insieme N2 delle coppie di naturali risulta essere numerabile.La corrispondenza biunivoca può essere stabilita con laseguente biiezione, frequentemente chiamata funzione coppiadi Cantor

p(i , j) =(i + j)(i + j + 1)

2+ i .

Il metodo con cui la biiezione p pone in corrispondenza coppiedi naturali con i naturali è detto diagonalizzazione. (vedi Figura)

Più in generale è possibile mostrare che, per ogni n ∈ N, se A ècontabile, anche An lo è.

Diagonalizzazione

0

1

2

3

4

5

0 1 2 3 4 5

0 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Numerabilitá dei numeri razionali

L’insieme dei numeri razionali Q corrisponde alle classid’equivalenza della relazione binaria R definita sull’insiemeZ × (Z+):

R(< a, b >,< c, d >

)se e solo se ad = bc.

L’insieme Q è dunque equinumeroso all’insieme Z × (Z+)/R .D’altronde poiché Z è contabile, anche Z2 lo è e così anchel’insiemeZ × (Z+)/R che è equinumeroso ad un sottoinsiemeproprio di Z2. Ciò prova che Q è contabile.

Viceversa:

L’insieme R dei reali e P(N) delle parti di N non sononumerabili.

Notazione O

Notazione che esprime l’andamento asintotico di una funzionerispetto ad un’altra.

DefinizioneData una funzione f : N 7→ N, la notazione O

(f (n)

)denota

l’insieme delle funzioni:

g | (∃c > 0) (∃n0 > 0) (∀n ≥ n0)(g(n) ≤ cf (n)

).

Se O(f (n)

)(oppure g(n) = O

(f (n)

)), per valori

sufficientemente grandi, la funzione assume valori nonsuperiori a quelli assunti dalla funzione f (n), a meno di unacostante moltiplicativa prefissata.

g(n) cresce al più come f (n).

Notazione Ω

DefinizioneData una funzione f : N 7→ N, la notazione Ω

(f (n)

)denota

l’insieme delle funzioni:

g | (∃c > 0) (∃n0 > 0) (∀n ≥ n0)(g(n) ≥ cf (n)

).

Se g(n) ∈ Ω(f (n)

)(oppure g(n) = Ω

(f (n)

)) si dice che g(n)

cresce almeno come f (n).

Notazione Θ

DefinizioneData una funzione f : N 7→ N, la notazione Θ

(f (n)

)denota

l’insieme delle funzioni:

g | (∃c1 > 0) (∃c2 ≥ c1) (∃n0 > 0) (∀n ≥ n0)(c1f (n) ≤ g(n) ≤ c2f (n)

).

Se g(n) ∈ Θ(f (n)

)(oppure g(n) = Θ

(f (n)

)) si dice che g(n) e

f (n) crescono nello stesso modo.

Notazione o

DefinizioneDate due funzione f : N 7→ N, con la notazione g(n) = o(f (n))indichiamo che:

limn→∞

g(n)

f (n)= 0.

Se g(n) = o(f (n)) diciamo che g(n) è un infinitesimo rispetto af (n) o, equivalentemente, che f (n) è un infinito rispetto a g(n).La stessa relazione può essere espressa mediante lanotazione f (n) = ω(g(n)).

Proprietá

Valgono le seguenti proprietà:

f (n) = O(g(n)

)if and only if g(n) = Ω

(f (n)

)

f (n) = Θ(g(n)

)if and only if g(n) = Θ

(f (n)

)

f (n) = Θ(g(n)

)if and only if

(

f (n) = O((g(n)

))

∧(f (n) = Ω

(g(n))

)

.

Nel seguito utilizzeremo questa notazione per indicare ilnumero di passi eseguiti da un algoritmo ed esprimere quindi,anche informalmente, il suo costo di esecuzione.

Se un algoritmo ha un costo O(n2

)per una stringa in input di n

caratteri, intenderemo dire che esiste una opportuna costante ctale che, per ogni n sufficientemente grande, il numero di passieseguiti dall’algoritmo su ogni stringa di lunghezza n è minore oeguale a cn2.

Esercizi

Esprimere con le notazioni O, Ω, Θ e o l’andamento asintoticodelle seguenti funzioni:

f (n) = 3n2 + 2 log n

g(n) = 2√

n + 5n4/3

n

Dimostrare le sequenti relazioni:

f (n) = 3n2 + 10n = O(n2)

g(n) =12

n2 − 3n = O(n2)