In questi Appunti abbiamo cercato di dare forma scritta alle Lezioni di Matematica per le Scienze Sociali, IV e V periodo, tenute durante l’Anno Accademico 2002/2003 dai proff. R. Paoletti e C. Morpurgo.

In questi Appunti abbiamo cercato di dare forma scritta alle Lezioni di Matematica per le Scienze Sociali, IV e V periodo, tenute durante l’Anno Accademico 2002/2003 dai proff. R. Paoletti e C. Morpurgo.

Si `e cercato di tenere la trattazione degli argomenti scelti ad un livello elementare, dando molto spazio alla risoluzione di esercizi (molti dei quali sono stati discussi anche in classe), evitando approfondimenti e ricorrendo il meno possibile a formule complesse.

Ringrazio, oltre che i docenti titolari del corso, gli altri tre tutors che mi hanno affiancato durante le esercitazioni: il dott. S. Bassis, il dott. A. Della Vedova ed in particolare la dott.ssa V. Doldi, per l’aiuto prezioso offerto.

Michele Bricchi

MATEMATICA

In questi Appunti tratteremo alcuni temi elementari di carattere matematico. Perci` o, nonostante la materia che presenteremo non sar` a complicata, `e bene premettere alcune osservazioni di carattere generale riguardanti il linguaggio che si usa in contesti matematici. Cercheremo infatti di mettere in luce la specificit` a di tale linguaggio: `e ben vero che si parler` a e si scriver` a sempre in italiano, tuttavia la matematica ha delle regole di espressione tutte sue; non di rado si ricorre addirittura a formule in cui compaiono simboli non in uso nella lingua corrente, ed `e bene che lo studente cominci ad avere dimestichezza con questo modo di esprimersi e con questi simboli.

Cominciamo con il dire che in matematica certe parole vogliono dire una ed una sola cosa, a differenza della lingua corrente in cui una stessa parola od espressione ha talora sfumature differenti o addirittura significati diversi, a seconda del contesto in cui `e inserita.

Ad esempio, se Tizio dicesse di avere una macchina, tutti penseremmo subito che Tizio vuol dire di possedere una ed una sola automobile.

Ma nel fare questa deduzione noi abbiamo aggiunto molto di pi` u di quanto Tizio abbia in realt` a detto. Abbiamo infatti pensato che la parola “una” significasse “una e soltanto una”, ovvero “una e non pi` u di una”, e non, magari “almeno una”. Parimenti, abbiamo pensato che

“macchina” significasse “automobile” e non, ad esempio, “tosa-erba”

o “telaio meccanico” (tutte “macchine”, a ben guardare). E’ vero che tutti questi dubbi sono presto fugati nel corso del discorso: dal contesto si capisce infatti subito se Tizio intende dire di possedere almeno un tosa-erba o di avere una buona utilitaria, e non pi` u di una.

In matematica non ci si pu` o per` o affidare al contesto, n´e al semplice

buon senso dell’ascoltatore, n´e, ovviamente, si pu` o far riferimento ad

elementi imponderabili e soggettivi di chi parla o scrive, di chi ascolta

o di chi legge.

1.1. Proposizioni, variabili e predicati

Consideriamo le seguenti due affermazioni: a) Tizio `e pi` u alto di Caio;

b) Tizio `e molto alto.

Ora, la prima affermazione `e o vera o falsa. Potrebbe essere difficile appurarlo, potendo le due altezze differire di pochissimo, eppure tutti coloro in grado di giudicare le due altezze concorderebbero: o Tizio `e pi` u alto di Caio, oppure no: la frase a) ha un contenuto oggettivo.

D’altro canto, la seconda affermazione `e condizionata da giudizi sogget- tivi: per qualcuno potrebbe sembrare che Tizio sia molto alto, per altri che sia solo alto. Insomma, non tutti concorderebbero sulla verit` a o la falsit` a della frase b), che quindi ha un contenuto soggettivo.

In matematica le frasi di tipo a) si chiamano proposizioni, mentre quelle del tipo b) devono essere assolutamente scartate.

Dunque, una proposizione `e una frase (di senso compiuto) o vera o falsa, senza mezzi termini.

Come ulteriore esempio segnaliamo la frase seguente:

“ il numero 223 092 871 `e un numero primo ”.

Ebbene, non `e del tutto ovvio se questa frase sia vera (in effetti, essa `e vera), ma nessuno deve avere dubbi sul fatto che essa o `e certamente vera o `e certamente falsa, comunque difficile risulti appurarlo, pertanto essa rientra a buon diritto nella categoria delle proposizioni.

Esaminiamo ora la frase: “x `e pi` u alto di y”. Ora questa frase non `e n´e vera, n´e falsa, infatti non conosciamo x e y. Tuttavia, ogniqualvolta a x e ad y viene dato un nome, ad esempio ad x viene dato il nome Tizio e ad y viene dato il nome Caio, ebbene allora la frase diventa una proposizione, in quanto `e possibile decidere della sua verit` a o della sua falsit` a in maniera precisa.

Frasi di tal fatta si chiamano predicati, mentre x e y sono chiamate variabili.

Dunque un predicato `e una frase dipendente da certe variabili tale

che ogni volta che alle variabili vengono sostituiti valori consentiti essa

diventa una proposizione.

Un altro esempio di predicato `e: x > 5.

Infatti, ogni volta che ad x si sostituisce un numero, la frase scritta diventa una proposizione, la quale `e appunto o indiscutibilmente vera o indiscutibilmente falsa.

Invece, la frase “x `e un bel numero” non `e un predicato, dal momento che sostituendo ad x un numero non si ottiene una proposizione, ma una frase la cui verit` a o falsit` a dipende da giudizi soggettivi.

1.1.1. Esercizio. La frase “per ogni numero n > 1 il numero n ² `e un numero primo” `e una proposizione, un predicato o non `e nessuna delle due?

1.2. I quantificatori

Una proposizione matematica non pu` o dunque essere fraintendibile, pertanto occorre una certa attenzione nel formularla.

Valutiamo il seguente esempio:

1.2.1. Teorema. Per ogni coppia di punti distinti del piano esiste una ed una sola retta che li contiene.

Come abbiamo imparato, si tratta effettivamente di una proposizione.

La geometria elementare insegna inoltre che questa proposizione `e ef- fettivamente vera (ed `e per questo motivo che la si chiama “Teorema”).

Andiamo ora un po’ oltre, cercando di studiarne meglio la struttura.

Questa proposizione comincia con le parole “per ogni”: si tratta di un esempio di quantificatore. I quantificatori principali in matematica sono tre, e precisamente

per ogni ∀ ; esiste ∃ ; esiste un unico ∃! .

I segni che compaiono di fianco ad ogni quantificatore sono i simboli che possono essere impiegati al posto delle parole per designare la medesima cosa. Ne impareremo presto altri, tanto che l’intero Teorema 1.2.1 pu` o essere riformulato semplicemente cos`ı:

∀ p, q ∈ Π : p 6= q ∃! r ∈ R : p ∈ r, q ∈ r, (2.1)

dove abbiamo convenuto di indicare con Π il piano della geometria elementare e con R l’insieme delle rette tracciabili su tale piano. Il segno di interpunzione “:” non ha la stessa funzione che esso riveste nella lingua italiana, ma va letto come se vi fosse scritto “tale che” (o

“tali che”).

Dunque, la frase in simboli scritta qui sopra comincia ad acquistare un senso compiuto: il quantificatore iniziale significa, come abbiamo appena visto, “per ogni”, poi seguono i punti p e q e poi ancora si ha il simbolo “ ∈”, il quale significa “appartenente” (o “appartenenti”, a seconda di ci` o che lo precede). Fino ad ora, quindi, la frase significa:

per ogni p e q appartenenti al piano Π tali che . . .

Ora si ha il segno “ 6=”, il quale significa “diverso”. In generale, quando si vuole negare un qualunque simbolo, basta mettere una sbarretta obliqua sul simbolo da negare. In questo caso negare “=” significa appunto dire “diverso”.

Altri simboli negati sono, ad esempio,

6∈ non appartenente ; 6 ∀ non per ogni ; 6 ∃ non esiste . Cos`ı, l’intera formula diventa chiara: per ogni p e q appartenenti al piano, tali che p `e diverso da q (e dunque p e q sono distinti), esiste un’unica (ecco un altro quantificatore) retta r tale che sia p che q vi appartengono.

Una volta sviscerata la frase si cerca di renderla in italiano accettabile e ne esce il Teorema 1.2.1 enunciato sopra.

1.2.2. Esempio. Ora il lettore dovrebbe essere in grado di riconoscere nella formuletta che segue il famoso Quinto Postulato di Euclide, con l’informazione che se r e s indicano due rette, allora la scrittura r ks significa che r `e parallela a s:

∀ p ∈ Π, ∀r ∈ R : p 6∈ r ∃! s ∈ R : s k r, p ∈ s.

A parole quanto abbiamo scritto si traduce dicendo: per ogni punto p del piano e per ogni retta r che giace su tale piano e non contenente p, esiste una ed una sola retta s passante per p e parallela a r.

1.2.3. Esercizio. a) Cosa significa a parole il predicato (supponendo che le variabili in gioco siano numeri): ∀ x ∃ y : x + y = 0 ?

b) E’ vero che ∃ x : ∀ y x·y = 0 ?

1.3. I connettivi

Una volta acquisita una certa dimestichezza con i quantificatori, bi- sogna cercare di capire come collegare tra loro le parti di una propo- sizione, oppure pi` u proposizioni, per formarne una pi` u grande.

Ora tale operazione `e stata fatta sopra tacitamente, usando le congiun- zioni “e” oppure “o” nel corso degli enunciati.

Vediamo ora i connettivi pi` u importanti nel dettaglio. Essi sono:

negazione ¬ , congiunzione ∧ , disgiunzione ∨ , implicazione = ⇒ , equivalenza ⇐⇒.

Negazione. Se P `e una proposizione, allora la negazione di P , ovvero ¬P , `e la proposizione che afferma l’esatto contrario di P . In generale,

la proposizione ¬P `e vera se e solo la proposizione P `e falsa.

Se, ad esempio P fosse:

“ Tizio ha pi` u francobolli di Caio ”, allora ¬P `e la proposizione:

“ `e falso che Tizio abbia pi` u francobolli di Caio ”, oppure, equivalentemente:

“ Tizio non ha pi` u francobolli di Caio”.

Si badi che la proposizione: “Tizio ha meno francobolli di Caio” `e pi` u precisa di ¬P , in quanto esclude che Tizio e Caio abbiano lo stesso numero di francobolli.

Dunque si presti attenzione quando si negano le proposizioni.

Ecco un esempio pi` u complicato: supponiamo che P sia la proposizione seguente (incidentalmente, vera)

“ per ogni numero naturale n, esiste un numero primo mag- giore di n ”.

Cosa significa negare P ? Significa affermare che P `e falsa, ovvero, asserire che

“ `e falso che per ogni numero naturale n esiste un numero primo maggiore di n ”.

Ora, `e sempre meglio cercare di spostare la negazione pi` u all’interno che si pu` o nella proposizione, in quanto la frase acquista maggior chiarezza.

Allora, se `e falso che per ogni numero succede una tal cosa, significa che esiste un’eccezione, ovvero, nel nostro caso, che esiste almeno un numero naturale n tale che non esiste alcun numero primo p maggiore di n.

Guardiamo in simboli cosa succede. La proposizione P si traduce in questo modo:

∀n ∈ N, ∃ p primo: p > n.

La negazione di P abbiamo scoperto dunque essere

∃ n ∈ N : ∀p primo, p ≤ n.

Si `e notato lo scambio dei quantificatori nel passaggio da P a ¬P ? In generale per proposizioni molto complicate, l’uso dei simboli torna molto utile, in quanto si riesce a negare tali proposizioni complesse con un certo grado di automatismo. Ma su questa questione non spendiamo altre parole.

Congiunzione. La congiunzione `e un connettivo molto naturale:

se P e Q sono due proposizioni, la proposizione P ∧Q (si legge“P e Q”)

`e la proposizione che asserisce sia P che Q.

Se ad esempio P fosse: “3 `e un numero primo” (vera) e Q fosse: “4

`e un numero dispari” (falsa), la proposizione P ∧ Q sarebbe: “3 `e un

numero primo e 4 `e un numero dispari” (falsa).

In generale,

la proposizione P ∧ Q `e vera se e solo se entrambe le proposizioni P e Q sono vere.

Disgiunzione. La disgiunzione `e un connettivo pure molto natu- rale: se P e Q sono due proposizioni, la proposizione P ∨ Q (si legge“P oppure Q”) `e la proposizione che asserisce o P oppure Q.

Se ad esempio P fosse di nuovo: “3 `e un numero primo” (vera) e Q fosse: “4 `e un numero dispari” (falsa), la proposizione P ∨ Q sarebbe:

“3 `e un numero primo oppure 4 `e un numero dispari” (vera).

In generale,

la proposizione P ∨ Q `e vera se e solo se almeno una fra le proposizioni P e Q `e vera.

Implicazione. L’implicazione `e il connettivo pi` u delicato: se P e Q sono due proposizioni, la proposizione P ⇒ Q (si legge“P implica Q”, oppure “se P allora Q”) `e la proposizione che asserisce che da P si deduce Q.

Se ad esempio P fosse: “3 `e un numero primo” (vera) e Q fosse: “4 `e un numero dispari” (falsa), la proposizione P ⇒ Q sarebbe: “se 3 `e un numero primo allora 4 `e un numero dispari” (falsa).

Si osservi che P ⇒ Q `e equivalente alla proposizione (¬P ) ∨ Q: infatti dire “se P allora Q” significa dire che o non vale P , oppure vale Q, ci si pensi un po’.

Pertanto,

la proposizione P = ⇒ Q `e vera se e solo se non si ha che la proposizione P (premessa) `e vera e Q (tesi) `e falsa.

Si prenda ad esempio l’implicazione:

“ se fa bel tempo, Tizio va a trovare Caio ”.

Ora, se per caso piovesse, tutti penserebbero che Tizio non andrebbe da Caio, ma questa deduzione aggiuntiva non `e consentita sul piano logico-deduttivo: l’unica cosa che `e certa `e che se fa bel tempo Tizio va da Caio. Equivalentemente si pu` o dire che se Tizio non va a trovare Caio, allora senz’altro non fa bel tempo.

Ma il cattivo tempo non impedisce a Tizio di andare da Caio. La nostra proposizione `e dunque equivalente alla seguente affermazione:

“ o non fa bel tempo, oppure Tizio va da Caio ”.

In ultimo, (lo ribadiamo ancora) osserviamo che se P ⇒ Q `e vera, ci`o non significa che Q sia vera, ma semplicemente che `e vero che da P si deduce Q.

Ad esempio se P fosse 2 < 1 (falsa) e Q fosse 3 < 2 (pure falsa), allora l’implicazione 2 < 1 ⇒ 3 < 2 sarebbe vera, in quanto la conclusione

`e deducibile dalla premessa, bastando aggiungere semplicemente 1 ad ambo i membri della disuguaglianza contenuta nella premessa stessa.

Equivalenza. In ultimo, prendiamo in esame l’equivalenza: se P e Q sono due proposizioni, allora P ⇐⇒ Q (si legge “P se e solo se Q”, oppure “P `e equivalente a Q”) `e la proposizione che `e vera se e solo se P e Q sono contemporaneamente vere o contemporaneamente false, ovvero, sono equivalenti. Ad esempio la proposizione

“ 2 < 1 se e solo se 3 < 2 ”

`e vera, poiche premessa e conclusione sono entrambe false. Invece, la proposizione

“ il numero naturale 10 `e divisibile per 2 se e solo se esso

`e divisibile per 4 ”.

`e una proposizione falsa, in quanto `e ben vero che 10 `e divisibile per 2, ma `e falso che 10 `e divisibile per 4.

In generale,

la proposizione P ⇐⇒ Q `e vera se e solo se le proposizioni

P e Q sono entrambe vere o entrambe false.

1.3.1. Esercizio risolto. Si consideri la seguente proposizione:

¬(P ∨ Q)

= ⇒ (¬P ) ∧ (Q ∨ R)
.

Si dica, usando le regole di riduzione viste sopra, se essa `e vera o falsa, supponendo che P e R siano vere e Q sia falsa.

Soluzione. Se P `e vera e Q `e falsa, allora la disgiunzione P ∨ Q `e vera e quindi la sua negazione ¬(P ∨ Q) `e falsa.

La disgiunzione Q ∨ R `e vera, poich´e almeno una delle due proposizioni Q o R `e vera. Dato poi che P `e vera, si ha che ¬P `e falsa. Pertanto la congiunzione

( ¬P )

| {z }

falsa

∧ (Q ∨ R)

| {z }

vera

risulta nel suo complesso falsa. Dunque, l’implicazione

¬(P ∨ Q)

| {z }

falsa

= ⇒ (¬P ) ∧ (Q ∨ R)

| {z }

falsa

.

`e vera, poich´e, come abbiamo appena visto, se la premessa `e falsa e la tesi `e falsa, l’implicazione `e vera.

1.3.2. Esercizio. Si consideri la seguente proposizione:

¬(P ∧ Q)

⇐⇒ (¬P ) ∨ (¬Q)
.

Si dica, usando le regole di riduzione viste sopra, se essa `e vera o falsa,

supponendo che P sia falsa e Q sia vera.

La nozione di insieme riveste in matematica un ruolo di primaria importanza: potremmo dire, anche se rimarremo vaghi, che il concetto di insieme rappresenta, alla stessa stregua delle operazioni elementari, l’alfabeto della matematica.

Mediante l’uso degli insiemi `e infatti possibile definire oggetti pi` u “evo- luti” e complicati. Tali oggetti pi` u complicati servono poi per definire oggetti ancora pi` u strutturati, e via dicendo.

Continuando il paragone con la nostra lingua, potremmo osservare come la Divina Commedia sia un insieme di cantiche, le quali, a loro volta, sono formate da canti, che a loro volta sono formati da terzine, a loro volta formate da endecasillabi, a loro volta formati da parole. E le parole sono solo (!) sequenze finite di lettere dell’alfabeto.

Dunque una cosa elementarissima come il nostro alfabeto ha permesso la creazione di un capolavoro.

Del tutto similmente, la teoria degli insiemi, a prima vista piuttosto semplice, consente (assieme ad altre nozioni primitive) di creare un linguaggio matematico capace di esprimere idee e nozioni sofisticate, teoremi di grande fascino e teorie capaci di rivoluzionare il pensiero dell’uomo.

Noi in questo capitolo avremo naturalmente pretese assai pi` u modeste:

cercheremo di presentare le prime nozioni riguardanti la teoria degli insiemi nella versione pi` u elementare che ci `e possibile.

2.1. Definizioni e prime propriet` a

Cominciamo con il precisare che cosa intendiamo con la parola “in- sieme”.

2.1.1. Definizione. Chiameremo insieme una qualunque collezione di oggetti (che verranno detti elementi dell’insieme) distinti e ben determinati.

2.1.2. Esempio. Sono effettivamente insiemi la collezione delle let-

tere dell’alfabeto italiano, oppure la totalit` a degli esseri umani, o anche

il gruppo delle squadre di calcio di serie A.

2.1.3. Esempio. Non costituiscono un insieme, invece, la collezione di tre citt` a (non sappiamo quali sono!), cinque monete finlandesi da 1 euro (non le possiamo distinguere!) e il gruppo degli uomini alti (cosa intendiamo per “alto”? E’ una propriet` a soggettiva!)

Useremo di preferenza le lettere maiuscole A, B, . . . per indicare gli insiemi e le lettere minuscole a, b, c, . . . , per indicarne gli elementi.

Per indicare che un dato elemento a sta nell’insieme A, diremo che “a appartiene ad A” e indicheremo questa relazione con “a ∈ A”.

C Inter

Juventus Chievo Milan

Lazio

Figura 2.1: rappresentazione dell’insieme C mediante diagramma di Eule- ro-Venn.

Ci sono tre modi per rappresentare gli insiemi:

• per elencazione:

si scrivono esplicitamente tutti gli elementi dell’insieme (e l’ordine in cui si scrivono `e indifferente); ad esempio

C = {Chievo, Inter, Juventus, Lazio, Milan};

• mediante diagrammi di Eulero-Venn:

gli insiemi vengono rappresentati graficamente come “recinti”

ovali, si veda ad esempio la Figura 2.1;

• per propriet`a caratteristica: si scrive la propriet`a che deve avere ogni elemento per appartenere all’insieme voluto; ad esem- pio,

C = { x `e una squadra di calcio: x `e tra le prime cinque }.

L’elencazione `e certamente il modo pi` u intuitivo per introdurre un dato

insieme. E’ per` o vero che se l’insieme consta di molti elementi, la mera

elencazione di tutti questi elementi pu` o diventare spossante. D’altro canto vi sono casi in cui l’elencazione degli elementi di un dato insieme

`e proprio impossibile. Se ad esempio volessimo indicare matematica- mente l’insieme di tutti i numeri pari, non potremmo certo elencarli tutti! In questi casi `e certamente preferibile (se non obbligatorio) ricorrere al metodo della propriet` a caratteristica. Per i numeri pari potremmo procedere in questo modo:

P = {n `e un numero: n `e pari}

e leggeremo: “P `e l’insieme dei numeri n tali che n `e pari”.

In tal modo, anche se non compaiono affatto i numeri pari nella defini- zione dell’insieme P , si `e capito con esattezza chi sono i suoi elementi.

Ad esempio, 4 appartiene a P in quanto `e un numero pari, 5 non appartiene a P in quanto `e un numero, ma non `e pari, ed infine la lettera q non appartiene a P in quanto non `e nemmeno un numero.

Tra tutti gli insiemi che si possono definire, ce n’`e uno particolarmente facile, che per` o bisogna tenere bene in mente.

2.1.4. Definizione. L’insieme che non contiene nessun elemento si chiama insieme vuoto e si denota con il simbolo ∅.

Dunque, l’insieme vuoto non contiene alcun elemento: ecco due esempi di insiemi che sono uguali all’insieme vuoto:

A = {n `e un numero: n `e dispari e multiplo di 4}, B = {x `e un uomo: x `e padre di suo nonno}.

Come si vede, i due insiemi non possono contenere alcun elemento:

nel primo caso perch´e nessun numero dispari pu` o essere multiplo di 4, altrimenti sarebbe pari, e nel secondo caso perch´e nessun uomo pu` o essere padre di un proprio avo! Quindi A = B = ∅.

2.1.5. Definizione. Un insieme A si dice finito se esso contiene un numero finito di elementi (o non ne contiene nessuno), mentre si dice infinito in caso contrario.

Nel caso in cui un certo insieme A sia finito, il numero dei suoi elementi

(0, nel caso in cui non ve ne siano) si chiama cardinalit` a di tale

insieme e si denota con |A|.

2.2. Relazioni insiemistiche

Passiamo ora alle relazioni tra insiemi e cominciamo con il precisare quando due insiemi sono uguali.

2.2.1. Definizione. Due insiemi A e B sono uguali quando essi con- tengono gli stessi elementi.

Ad esempio i due insiemi

A = {a, b, c} e B = {b, c, a}

sono uguali: essi infatti contengono gli stessi tre elementi. Anche l’insieme

C = {x `e una lettera: x `e una delle prime tre lettere dell’alfabeto}

`e uguale ad A e B, per la stessa ragione.

2.2.2. Definizione. Un insieme A `e incluso in un insieme B, e scri- veremo A ⊆ B, quando ogni elemento di A `e anche elemento di B.

Se A `e incluso in B, diremo anche che B include A e scriveremo B ⊇ A.

Se A `e incluso in B, allora si dice anche che A `e un sottoinsieme di B.

Per convenzione assumiamo che ∅ ⊆ A, qualunque sia A, in altri termini l’insieme vuoto `e sempre un sottoinsieme di ogni altro insieme A.

2.2.3. Osservazione. Osserviamo che ogni insieme `e sottoinsieme di se stesso. Dunque ogni insieme non vuoto ha sempre due sottoinsiemi distinti: l’insieme vuoto e se stesso. Questi due sottoinsiemi vengono spesso chiamati sottoinsiemi banali (o impropri).

Insieme universo. Per evitare confusioni o paradossi `e bene pen-

sare che gli insiemi che si esaminano siano contenuti in un insieme pi` u

grande, detto insieme universo (o ambiente), di volta in volta spec-

ificato (o comunque tacitamente sottinteso). Ad esempio, quando par-

leremo dell’insieme dei numeri pari, o dei numeri dispari, o dei numeri

A B

Figura 2.2: B ` e sottoinsieme di A.

primi, penseremo sempre che tutti questi sottoinsiemi siano contenuti nell’insieme universo costituito da tutti i numeri.

Se consideriamo l’insieme delle prime cinque squadre di serie A o l’insie- me delle ultime otto, o l’insieme delle squadre il cui nome inizia per “C”, allora penseremo che tutti questi insiemi siano immersi nell’insieme universo costituito dalla totalit` a di tutte le squadre di serie A.

2.2.4. Definizione. Sia dato un insieme A. Si chiama insieme delle parti di A l’insieme che ha per elementi tutti i sottoinsiemi di A.

Indicheremo tale insieme con il simbolo P(A).

Ad esempio, sia A = {x, y, z}. Allora (ricordiamoci che ∅ e A sono sottoinsiemi di A!)

P(A) = 

∅, {x, y, z}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}

.

Da ricordare. In seguito osserveremo che se A ha cardinalit` a n, allora P(A) ha cardinalit`a 2 ⁿ : nel nostro caso |A| = 3, ed infatti abbiamo verificato che |P(A)| = 2 ³ = 8.

Esaminiamo ora alcune propriet` a dell’inclusione.

• Propriet`a riflessiva : A ⊆ A;

• Propriet`a antisimmetrica : se A ⊆ B e B ⊆ A, allora A = B;

• Propriet`a transitiva : se A ⊆ B e B ⊆ C, allora A ⊆ C.

Della prima propriet` a abbiamo gi` a parlato, quanto alla seconda essa dice che se A `e incluso in B e B `e incluso in A, allora l’unica possibilit` a

`e che A = B. In ultimo, la transitivit` a esprime un fatto intuitivamente

ovvio: se un certo insieme A `e contenuto in B, ed a sua volta B `e

contenuto in C, allora anche A `e contenuto in C.

2.3. Operazioni tra insiemi

Ora esaminiamo quattro operazioni fondamentali nella teoria degli in- siemi: unione, intersezione, differenza e complementazione.

Ricordiamo che tutti gli insiemi che consideriamo sono da considerarsi contenuti in un insieme universo X, fissato una volta per tutte.

Ecco le definizioni:

2.3.1. Definizione. Siano dati due insiemi A e B contenuti in X.

Allora l’unione di A e B, denotata con A ∪B, `e l’insieme i cui elementi appartengono o ad A, oppure a B.

A B

a b

cc d

h i

l e

f g a

b c

d

h i

l

Figura 2.3: l’intera parte ombreggiata rappresenta l’unione di A e B.

2.3.2. Definizione. Siano dati due insiemi A e B contenuti in X.

Allora l’intersezione di A e B, denotata con A ∩ B, `e l’insieme i cui elementi appartengono sia ad A, sia a B.

A

B a

b c d

h i

l e

f g

Figura 2.4: la parte ombreggiata rappresenta l’intersezione di A e B.

2.3.3. Definizione. Siano dati due insiemi A e B contenuti in X.

Allora la differenza di A e B, denotata con A \ B `e l’insieme i cui elementi appartengono ad A ma non a B.

A

B e

f g a

b c

d

h i

l

Figura 2.5: la parte ombreggiata rappresenta la differenza di A e B.

2.3.4. Definizione. Sia dato un insieme A contenuto in X. Allora il complementare di A, denotato con A ^c , `e l’insieme i cui elementi non appartengono ad A.

e f a b c

d

h i l

A B

X h

i g l

Figura 2.6: la parte ombreggiata rappresenta il complementare di A: si os- servi come questo dipenda da X.

Ad esempio se X = {1, 2, 3, 4, 5, 6, 7}, A = {1, 2, 3, 4} e B = {1, 3, 7}, allora abbiamo che

A ∪ B = {1, 2, 3, 4, 7}, A ∩ B = {1, 3}, A \ B = {2, 4},

B \ A = {7}, A ^c = {5, 6, 7} e B ^c = {2, 4, 5, 6}.

2.3.5. Osservazione. Direttamente dalla definizione si ha che A ∪ B = B ∪ A, e analogamente A ∩ B = B ∩ A. Per contro A \ B non `e uguale (in generale) a B \A, e l’esempio appena discusso mostra infatti che questi due ultimi insiemi possono non coincidere. Ad ogni modo si osservi che A \ B = A ∩ B ^c .

Si possono dimostrare le seguenti formule (alcune sono immediate, altre meriterebbero qualche considerazioni aggiuntiva):

1. A ^c = X \ A

2. (A ^c ) ^c = A ( (·)

` e involutorio)

3. A ∩ A = A (idempotenza di ∩ ⁾

4. A ∪ A = A (idempotenza di ∪ ⁾

5. A \ A = ∅

6. A ∪ A ^c = X (non contradditoriet` a)

7. A ∩ (B ∩ C) = (A ∩ B) ∩ C (associativit` a di ∩ <sup>)</sup> 8. A ∪ (B ∪ C) = (A ∪ B) ∪ C (associativit` a di ∪ ⁾ 9. (A ∪ B) ^c = A ^c ∩ B ^c (legge di De Morgan)

10. (A ∩ B) ^c = A ^c ∪ B ^{c ”}

11. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (distributivit` a di ∩ <sup>rispetto a</sup> ∪ <sup>)</sup> 12. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (distributivit` a di ∪ ^{rispetto a} ∩ ⁾ Grazie alle propriet` a 8, possiamo scrivere impunemente A ∪B∪C, senza preoccuparci di specificare se intendiamo A ∪(B∪C) o (A∪B)∪C, dato che si tratta della stessa cosa. Analogamente (grazie alla propriet` a 7), per la scrittura A ∩ B ∩ C. Si osservi l’analogia di questa propriet`a con quella della consueta operazione “+”: anche qui si ha che a + (b + c) = (a + b) + c e pertanto risulta non ambigua la scrittura a + b + c. Al contrario l’operazione di differenza per gli insiemi non gode di questa propriet` a: non `e vero che A \(B\C) = (A\B)\C. Per rendersene conto, si consideri il seguente esempio: X = {a, b, c, d, e, f, g}, A = {a, b, c}, B = {a, b, g, f}, C = {a, g}. Ora,

A \ (B \ C) = A \ {b, f} = {a, c},

mentre

(A \ B) \ C = {c} \ {a, g} = {c}.

Come si vede i due insiemi non coincidono. Si osservi l’analogia con l’operazione di sottrazione tra numeri: anche in questo caso non vale la propriet` a associativa; infatti (a − b) − c non `e in generale uguale a a − (b − c) (si costruisca un esempio!).

2.3.6. Esercizio risolto. Ridurre in forma pi` u semplice l’insieme A ^c ∪ (A ∩ B)

\ B ∩ (B \ A) ^c
c

, (3.1)

sfruttando le regole elencate sopra.

Soluzione. Poniamo

A ^c ∪ (A ∩ B)

| {z }

= I

\ B ∩ (B \ A) ^c
c

| {z }

= II

.

Occupiamoci della parte I dell’espressione:

A ^c ∪ (A ∩ B) = (A ^c ∪ A) ∩ (A ^c ∪ B)

= X ∩ (A ^c ∪ B)

= A ^c ∪ B, grazie alle regole 12 e 6.

Per quanto riguarda il membro II dell’espressione abbiamo B ∩ (B \ A) ^c
c

= B ^c ∪ (B \ A) ^c
c

= B ^c ∪ (B \ A)

= B ^c ∪ (B ∩ A ^c )

= (B ^c ∪ B) ∩ (B ^c ∪ A ^c )

= X ∩ (B ^c ∪ A ^c )

= B ^c ∪ A ^c ,

grazie alle regole 10, 2, 12 e 6.

Dunque, in definitiva la nostra espressione iniziale `e uguale a (A ^c ∪ B) \ (A ^c ∪ B ^c ) = (A ^c ∪ B) ∩ (A ^c ∪ B ^c ) ^c

= (A ^c ∪ B) ∩ (A ^c ) ^c ∩ (B ^c ) ^c

= (A ^c ∪ B) ∩ (A ∩ B)

= (A ^c ∩ A ∩ B) ∪ (B ∩ A ∩ B)

= ∅ ∪ (A ∩ B) = A ∩ B.

Sicch´e l’intera espressione (3.1) altri non `e che l’insieme A ∩ B.

A B

X

Figura 2.7: qui ` e ombreggiato l’insieme I dell’Esercizio 2.3.6, cio` e l’insieme A ^c ∪ (A ∩ B).

A B

X

Figura 2.8: qui ` e ombreggiato l’insieme II dell’Esercizio 2.3.6, cio` e l’insie-

me (B ∩ (B \ A) ^c ) ^c .

A B X

Figura 2.9: qui ` e ombreggiato l’insieme I \ II dell’Esercizio 2.3.6, cio`e l’in- sieme A ∩ B.

2.3.7. Esercizio. Ridurre in forma pi` u semplice l’insieme A ∩ (A ∪ B ^c )

∪ A \ (B \ A)

. (3.2)

2.4. Contare gli elementi

Se A ha n elementi e B ha m elementi, quanti elementi ha A ∩ B? E A ∩ B?

In questo paragrafo diamo le formulette che rispondono a queste do- mande.

2.4.1. Proposizione. Siano A e B due insiemi non vuoti di cardi- nalit` a finita. Allora si hanno le seguenti relazioni:

|A ∪ B| = |A| + |B| − |A ∩ B|,

|A ∩ B| = |A| + |B| − |A ∪ B|,

|A \ B| = |A| − |A ∩ B| = |A ∪ B| − |B|.

2.4.2. Esempio. Se, ad esempio A = {a, b, c, d, e} e B = {a, f}, ab- biamo che |A| = 5, |B| = 2, |A ∩ B| = 1, |A ∪ B| = 6, |A \ B| = 4 e

|B \ A| = 1.

2.5. Partizioni

Ora veniamo ad un altro concetto importante nella teoria degli insiemi.

2.5.1. Definizione. Dato un insieme non vuoto A, una partizione di A `e una collezione qualunque di sottoinsiemi non vuoti di A tali che ogni elemento di A appartiene ad uno ed uno solo di tali sottoinsiemi.

Se A = {a, b, c, d, e, f}, quelli che seguono sono tutti esempi di possibili partizioni di A:

P ₁ = 

{a}, {b, c}, {d, e, f}

; P ₂ = 

{a, b, c}, {d}, {e, f}

; P ₃ = 

{a, b, c, d, e, f}

; P ₄ = 

{a}, {b}, {c}, {d}, {e}, {f}

; P ₅ = 

{a, f}, {b, e}, {c, d}

.

Come si vede in ognuno degli esempi si ha che ogni elemento di A sta in uno ed in uno solo dei sottoinsiemi non vuoti di volta in volta scelti, i quali, quindi, costituiscono una partizione di A.

Nel caso in cui A sia l’insieme dei numeri naturali, una possibile par- tizione `e data dai seguenti sottoinsiemi:

A ₁ = {1}, A ₂ = {2, 3}, A ₃ = {4, 5, 6}, . . .

In questo modo costruiamo un’infinit` a di sottoinsiemi, i quali costitui- scono una partizione di A: infatti ognuno di questi sottoinsiemi `e non vuoto, in pi` u `e chiaro dalla loro costruzione che ogni numero sta in uno ed uno solo di tali sottoinsiemi.

Attenzione. Non `e detto che una partizione di un insieme infinito sia infinita: ad esempio la partizione

P = 

{numeri pari}, {numeri dispari}

`e una partizione dell’insieme dei numeri naturali che ha solo due ele-

menti!

A

A

A

A

A

A

A

A

A

A

A

A

A

A

A

A

Figura 2.10: i 15 sottoinsiemi A _i ; i =1,2,. . . ,15 rappresentano, in maniera schematica, una partizione di un certo insieme A.

2.6. Prodotto cartesiano

In questo paragrafo consideriamo un’altra operazione tra due insiemi:

il prodotto cartesiano.

Consideriamo due insiemi non vuoti A e B. Supponiamo, per il mo- mento, che A e B siano due insiemi finiti. Per facilitare la comprensione di quanto diremo supponiamo che A sia l’insieme delle quattro giacche che Tizio ha nell’armadio, diciamo

A = {giacca 1 , giacca ₂ , giacca ₃ , giacca ₄ }.

L’insieme B `e invece l’insieme delle tre cravatte che Tizio ha sempre nell’armadio:

B = {cravatta ¹ , cravatta ₂ , cravatta ₃ }.

Ora, l’insieme A × B (prodotto cartesiano di A e B) indica tutti gli abbinamenti tra giacche e cravatte, precisamente gli elementi di A × B sono:

(giacca ₁ , cravatta ₁ ), (giacca ₁ , cravatta ₂ ), (giacca ₁ , cravatta ₃ ),

(giacca ₂ , cravatta ₁ ), (giacca ₂ , cravatta ₂ ), (giacca ₂ , cravatta ₃ ),

(giacca ₃ , cravatta ₁ ), (giacca ₃ , cravatta ₂ ), (giacca ₃ , cravatta ₃ ),

(giacca ₄ , cravatta ₁ ), (giacca ₄ , cravatta ₂ ), (giacca ₄ , cravatta ₃ ).

Notiamo che gli elementi del prodotto cartesiano sono coppie ordinate di elementi: il primo elemento della coppia appartiene ad A, mentre il secondo elemento della coppia appartiene a B. Dunque se A e B sono due insiemi inclusi dell’insieme ambiente X e, rispettivamente, Y , il loro prodotto cartesiano A × B `e un sottoinsieme di X × Y .

La definizione rigorosa `e questa:

2.6.1. Definizione. Siano A e B due insiemi non vuoti contenuti l’uno nell’insieme ambiente X, l’altro nell’insieme ambiente Y . Allora l’insieme

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

si chiama prodotto cartesiano di A e B ed `e un sottoinsieme di X × Y .

2.6.2. Esempio. Se X `e l’insieme dei numeri ed A = {1, 2} e se Y `e l’insieme delle lettere dell’alfabeto italiano e B = {a, f, z}, allora

A × B = 

(1, a), (1, f ), (1, z), (2, a), (2, f ), (2, z)

⊆ X × Y.

Si scriva per esercizio esplicitamente anche B × A.

A B

a b c

1 2

(a,1) (a,2)

(b,1) (b,2)

(c,1) (c,2)

A x B

Figura 2.11: realizzazione intuitiva del prodotto cartesiano: su di un asse indichiamo gli elementi di A, sull’altro quelli di B: le relative coppie ordina- te di punti nel piano rappresentano gli elementi di A × B.

E’ chiaro che se A ha n elementi e B ha m elementi, allora A × B ha n ·m elementi, ovvero, in formula,

|A × B| = |A|·|B|.

Osserviamo anche che il prodotto cartesiano non `e commutativo: un conto `e considerare A × B, un altro `e considerare B × A: dunque la posizione degli elementi a e b nella coppia (a, b) `e importante e non si pu` o invertire.

Ad esempio poniamo che A = {Inter}, B = {Juventus} e che X = {squadre di serie A}, allora

A × B = {(Juventus, Inter)}, mentre

B × A = {(Inter, Juventus)},

ed `e chiaro che la prima partita si disputa a Torino, mentre la seconda si gioca a Milano!

2.7. Insiemi numerici

Tra tutti gli insiemi che si possono costruire, in matematica rivestono grande importanza i cosiddetti insiemi numerici.

Vediamoli nel dettaglio, soffermandoci un poco su ognuno di questi.

Numeri naturali. Il primo insieme che consideriamo `e l’insieme dei numeri naturali, indicato con N.

L’insieme dei numeri naturali contiene i numeri 1, 2, 3, eccetera, ovvero i numeri che tutti hanno imparato a conoscere alle scuole elementari. Si preferisce non considerare lo 0 come numero naturale, pertanto esso non appartiene ad N. L’insieme {0, 1, 2, . . .}, ottenuto da N con l’aggiunta dello 0, ovvero N ∪ {0}, verr`a chiamato N 0 .

Sull’insieme dei numeri naturali non ci pare il caso di spendere altre parole.

Numeri interi. Il secondo insieme che prendiamo in considerazione `e l’insieme dei numeri interi, denotato con Z.

Tale insieme `e costituito da tutti i numeri naturali, dallo 0 e da tutti i loro opposti, dunque

Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}.

L’insieme Z contiene N ₀ e dunque anche N.

Numeri razionali. Il terzo insieme che prendiamo in considerazione

`e l’insieme dei numeri razionali, denotato con Q.

Tale insieme `e costituito da tutti i numeri che si possono presentare come rapporto di numeri interi. Ad esempio 1/2 `e un numero razionale, in quanto esso `e il rapporto tra 1 e 2, i quali sono due numeri interi.

Anche −7/8 `e un numero razionale, in quanto esso pu`o essere visto come rapporto tra i numeri −7 e 8. Dunque tutte le frazioni, positive o negative, sono numeri razionali. In maniera analoga si pu` o vedere che tutti i numeri con allineamento decimale finito o periodico sono numeri razionali, infatti essi possono sempre essere scritti come frazioni: il numero 1, 34 pu` o essere infatti scritto come 134/100, che `e appunto una frazione.

Questo procedimento pu` o essere esteso a tutti i numeri decimali con allineamento decimale periodico.

Ad esempio, il numero 1, 333 · · · = 1, 3 pu`o essere scritto come 4/3, mentre il numero 14, 3414141 · · · = 14, 341 = 13 + 13/10 + 41/990.

Ora, non `e importante cercare di ricordarsi i procedimenti meccanici usati per convertire ogni numero decimale con allineamento periodico in frazione. L’importante `e comprendere che `e sempre possibile farlo.

Pertanto,

Q = {p/q : p ∈ Z, q ∈ N},

cio`e Q `e l’insieme di tutte le possibili frazioni tra due numeri interi (e denominatore diverso da 0). Tale insieme contiene tutti i numeri interi (e quindi anche tutti i naturali), i quali possono essere visti come particolari frazioni con denominatore uguale a 1.

Numeri reali. L’ultimo insieme numerico che consideriamo `e anche il pi` u grande.

Si tratta dell’insieme dei numeri reali, denotato con R. A differenza degli insiemi visti sino ad ora, esso `e difficilmente definibile. Per dare una definizione davvero rigorosa bisognerebbe ricorrere a strumenti matematici non elementari e preferiamo essere poco rigorosi piutto- sto che incomprensibili.

Diremo quindi, un po’ grossolanamente che l’insieme dei numeri reali raccoglie tutti i numeri che ci sono: pertanto, oltre a Q faranno parte di R tutti qui numeri che non sono razionali, come ad esempio √

2

o π (cio`e con allineamento decimale illimitato e non periodico, ma non

insistiamo oltre).

Tutti questi numeri che non sono razionali e che, nondimeno, sono sem- pre numeri reali (ovvero appartengono a R \ Q), si chiamano numeri irrazionali.

Altri esempi di numeri irrazionali sono, ad esempio − √

21, 7 ^{√ 3} , 5 ^2/5 , π ^π , il numero di Nepero e e moltissimi altri.

Qualche volta ci servir` a considerare solo i numeri reali positivi. Per questo diamo un nome a tale insieme ponendo

R

0 = {x ∈ R : x ≥ 0}.

N Z

Q

R

Figura 2.12: gli insiemi N, Z, Q e R sono rappresentati schematicamen- te: essi sono inclusi l’uno nell’altro. L’insieme dei numeri naturali ` e il pi` u piccolo, mentre quello dei numeri reali ` e il pi` u grande.

2.7.1. Esercizio. Chi sono gli elementi di Z \ N ?

2.7.2. Esercizio. Sia A = {x ∈ R : x ≥ 5} e B = {x ∈ R : x ≤ 5}.

Individuare gli insiemi:

a) A ∩ B; b) A ∪ B; c) A \ B; d) B \ A.

Il concetto di funzione `e di grande importanza nella matematica.

Dati due insiemi non vuoti A e B, vorremmo poter chiamare funzione ogni legge che associa elementi di A ad elementi di B in maniera uni- voca, cio`e in modo tale che ad ogni elemento di A si associ un unico elemento di B e non, ad esempio nessuno, o due o quarantotto ele- menti di B (relazioni di tal fatta, ovvero non univoche, non verranno mai prese in considerazione in questi Appunti).

3.1. Definizione ed esempi

Ecco la definizione vera e propria di funzione.

3.1.1. Definizione. Siano A e B due insiemi non vuoti. Una fun- zione f da A in B (si scrive “ f : A −→ B ”) `e una qualunque relazione che associa ad ogni elemento a di A un unico elemento b di B.

Per denotare che all’elemento a si associa b si scrive “ f (a) = b ”.

L’insieme di partenza A si chiama dominio della funzione f , mentre l’insieme di arrivo B si chiama codominio della funzione f .

A B

f

Figura 3.1: la relazione f : A → B disegnata qui sopra `e effettivamente una

funzione: ad ogni elemento di A (circoletti) ` e univocamente associato un ele-

mento di B (triangolini).

3.1.2. Esempio. Prendiamo A = {2, 7, 10, 12} e B = {2, 3, 5, 9}.

Definiamo ora la relazione seguente: ad ogni elemento a di A asso- ciamo gli elementi di B che sono suoi divisori.

Ebbene in questo caso la relazione introdotta non `e una funzione. In- fatti, da un lato non ogni elemento di A ha associato elementi di B: il numero 7 non ha infatti divisori in B e quindi a 7 non `e associato nes- sun elemento di B; d’altro canto capita anche che al numero 10 siano associati i numeri 2 e 5, pertanto non `e vero che ad ogni numero di A sia associato un solo elemento di B, come richiederebbe la definizione.

A B

2 7 10 12

2

3 5

?

9

Figura 3.2: schema della situazione discussa nell’Esempio 3.1.2.

3.1.3. Esempio. Prendiamo adesso come insieme A l’insieme delle automobili acquistate e come insieme B prendiamo l’insieme degli esseri umani. Scegliamo la relazione f che associa ad ogni automobile il legittimo proprietario.

Ora, si tratta in effetti di una funzione, infatti ogni automobile acqui- stata ha un suo proprietario (non sottilizziamo ed immaginiamo che i proprietari siano tutti esseri umani e non societ` a o ditte . . . ). Inoltre ogni automobile ha un solo proprietario e quindi entrambe le richieste perch´e f sia una funzione sono soddisfatte.

3.1.4. Osservazione. Ritorniamo sull’Esempio 3.1.3. Si noti che non

`e affatto detto che ogni essere umano sia proprietario di un’automobile, n´e che ogni essere umano ne abbia soltanto una.

In altre parole, pi` u automobili possono avere lo stesso proprietario e pu` o

esserci qualche essere umano cui non `e associata nessuna automobile,

ma questo non `e vietato dalla definizione.

3.2. Funzioni iniettive, suriettive e biettive

In termini matematici, l’Osservazione 3.1.4 pu` o essere riformulata di- cendo che pu` o accadere che due elementi distinti a e a ⁰ del dominio A di una certa funzione f vengano associati allo stesso b (ovvero f (a) = f (a ⁰ ) = b). In tal caso si dir` a che la funzione f non `e iniettiva.

Se invece succede che qualche b ∈ B non `e raggiunto da nessun ele- mento a in A mediante la f (cio`e b rimane “scoperto”), allora diremo che la funzione in questione non `e suriettiva.

Ecco le definizioni rigorose.

3.2.1. Definizione. Una funzione f : A −→ B `e detta iniettiva se per ogni elemento b ∈ B esiste al pi`u un elemento a ∈ A tale che f (a) = b.

Equivalentemente, una funzione `e detta iniettiva se e solo se per ogni a, a ⁰ ∈ A tali che f(a) = f(a ⁰ ) si ha a = a ⁰ .

A B

f

Figura 3.3: la funzione f non ` e iniettiva: a due elementi distinti viene as- sociato uno stesso elemento nel codominio. La funzione f ` e per` o suriettiva.

3.2.2. Definizione. Una funzione f : A −→ B `e detta suriettiva se per ogni elemento b ∈ B esiste almeno un elemento a ∈ A tale che f (a) = b.

3.2.3. Definizione. Una funzione f : A −→ B `e detta biettiva (o corrispondenza biunivoca) se per ogni elemento b ∈ B esiste uno ed un solo elemento a ∈ A tale che f(a) = b.

Equivalentemente, una funzione `e biettiva se e solo se essa `e sia iniettiva

che suriettiva.

A B f

Figura 3.4: la funzione f non ` e suriettiva: c’` e un elemento del codominio che non ` e associato ad alcun elemento del dominio. Si ha per` o che f ` e iniet- tiva.

Automobili Proprietari

f

Figura 3.5: la funzione f rappresentata nell’immagine non ` e n´ e iniettiva, n´ e suriettiva.

Allora, la funzione discussa prima che associa ad ogni automobile ac- quistata il suo proprietario non `e n´e iniettiva, n´e suriettiva, in quanto esistono proprietari di pi` u automobili (salta l’iniettivit` a) e ci sono anche persone senza automobile (salta la suriettivit` a).

Passiamo a qualche esempio pi` u “matematico”.

3.2.4. Esempio. Sia f : N −→ N la funzione definita da f(n) = n ² . Ora, una tale funzione `e certamente iniettiva, in quanto non `e possibile che due numeri naturali distinti abbiano lo stesso quadrato.

D’altro canto f non `e suriettiva, in quanto ci sono dei numeri naturali che non sono il quadrato di un numero naturale. Ad esempio 2 non `e il quadrato di nessun numero naturale in quanto non c’`e nessun n ∈ N tale che n ² = 2.

3.2.5. Esempio. Sia ora f : Z −→ N la funzione definita da f(n) = n ² .

Essa sembra simile a quella definita nell’esempio precedente, ma in

realt` a non si tratta della stessa funzione, in quanto i domini sono diversi

(anche se le due funzioni hanno la stessa “formula”!).

In questo caso f non `e iniettiva: infatti se n <sup>2</sup> = m <sup>2</sup> non possiamo pi` u concludere che n = m: ad esempio 3 e −3 hanno lo stesso quadrato e quindi f non pu` o essere iniettiva.

Quanto alla suriettivit` a abbiamo anche in questo caso gli stessi proble- mi di prima: ci sono dei numeri naturali che non sono il quadrato di un numero intero. Ad esempio 2 non `e il quadrato di nessun numero intero dal momento che non c’`e nessun n ∈ Z tale che n ² = 2.

3.2.6. Esempio. Sia ora f : R −→ R la funzione definita da f(x) = x ² (si preferisce usare la lettera x quando la variabile appartiene ad R, ma `e solo una convenzione, si poteva usare qualunque altra lettera).

Ora il dominio della funzione f `e l’insieme dei numeri reali. La fun- zione f non `e iniettiva, sempre per il fatto che due numeri reali opposti hanno lo stesso quadrato, ad esempio √

2 e − √ 2.

La funzione non `e nemmeno suriettiva, in quanto non `e vero che tutti i numeri reali sono il quadrato di un numero reale: −1, ad esempio, non pu` o essere il quadrato di alcun numero reale.

3.2.7. Esempio. Consideriamo adesso la funzione f : R −→ R

0 de- finita da f (x) = x ² .

Ora, il codominio della funzione f `e l’insieme dei numeri reali non negativi. La funzione f non `e iniettiva, sempre per la ragione espressa negli esempi precedenti.

La funzione ora `e per` o finalmente suriettiva, in quanto `e vero che tutti i numeri reali non negativi sono il quadrato di un numero reale: se a `e un qualunque numero reale non negativo, allora il numero reale √

a ha per quadrato proprio a, e questo basta per dire che la funzione data `e suriettiva.

3.2.8. Esercizio. Cosa si pu` o dire della funzione f : R

0 −→ R

0 , definita da f (x) = x ² ?

3.2.9. Osservazione. Abbiamo visto in questi esempi che cambiando

il dominio o il codominio di una stessa relazione si ottengono fun-

zioni diverse, con diverse propriet` a. Pertanto si ricordi che una fun-

zione `e assegnata quando si conosce il suo dominio, il suo codominio e

l’espressione di f (non basta conoscere solo quest’ultima!).

3.2.10. Esempio. La funzione f : R −→ R data da f(x) = x ³ `e un esempio di funzione biettiva.

Procediamo con ordine: verifichiamo che f `e iniettiva. Per questo sup- poniamo che per un certo x ∈ R ed un certo y ∈ R si abbia f(x) = f(y), ovvero x <sup>3</sup> = y <sup>3</sup> . Per dimostrare che f `e iniettiva bisogna dedurre da qui che x = y. Si tratta tuttavia di un passaggio elementare se x ³ = y ³ , estraendo la radice cubica a destra ed a sinistra di questa uguaglianza si arriva a x = y, che `e appunto quanto volevamo. Dunque, la fun- zione f `e iniettiva.

Per quanto riguarda la suriettivit` a, dobbiamo procedere in questo modo:

comunque si scelga un numero y nel codominio, bisogna essere in grado di reperire almeno un x nel dominio, tale per cui f (x) = y, ovvero tale che x ³ = y. Ma `e a questo punto chiaro che una volta scelto y, baster` a scegliere x = √

y, infatti ( √

y) ³ = y, come volevamo.

Questo mostra che la funzione f `e sia iniettiva che suriettiva, pertanto essa `e biettiva.

3.2.11. Esempio. Consideriamo la funzione f : N −→ N data da f (n) = 1 + 2 + · · · + n.

Ad esempio f (1) = 1, f (2) = 1 + 2 = 3, f (3) = 1 + 2 + 3 = 6 e cos`ı via.

Si tratta di una funzione suriettiva? In altre parole, se prendiamo un numero naturale m qualunque, `e vero che esiste n tale che m `e la somma dei primi n numeri?

Se, ad esempio, si scegliesse m = 6, avremmo che n = 3, infatti f (3) = 1 + 2 + 3 = 6.

Se per` o scegliessimo m = 7 non riusciamo a trovare nessun n tale che f (n) = 7. Infatti non possiamo scegliere n = 1, 2, 3, dato che f (1) = 1 f (2) = 3 e f (3) = 6. Se scegliamo n = 4 abbiamo che f (4) = 1 + 2 + 3 + 4 = 11, che `e maggiore di 7. Ogni n maggiore di quattro render` a poi f (n) ancora pi` u grande di 11 e quindi non potr` a mai essere uguale a 7. Insomma la funzione non `e suriettiva: ci sono dei numeri naturali m che non sono della forma f (n), per nessun n ∈ N.

I numeri 2, 7, 8 e 9 ne sono un esempio, ma in queste condizioni ce ne sono addirittura infiniti.

Veniamo all’iniettivit` a: supponiamo pertanto che per un certo n e per

un certo n ⁰ in N si abbia f (n) = f (n ⁰ ), ovvero

1 + 2 + · · · + n = 1 + 2 + · · · + n ⁰ . (2.1) Ora, `e del tutto ovvio che una tale uguaglianza non pu` o sussistere se n 6= n ⁰ , dal momento che se, ad esempio fosse n ⁰ > n, allora sarebbe 1+2+ · · ·+n ⁰ > 1+2+ · · ·+n e non si potrebbe avere l’uguaglianza (2.1).

Lo stesso discorso vale se fosse n ⁰ < n e pertanto non pu` o che essere n = n <sup>0</sup> . Dunque la funzione `e iniettiva.

3.2.12. Esempio. Dagli esempi sino ad ora discussi sembrerebbe che non si possano costruire funzioni f : N −→ N che siano suriettive e non iniettive. Cos`ı non `e: consideriamo la funzione f : N −→ N definita in questo modo:

f (1) = f (2) = 1, f (3) = 2, f (4) = 3, . . . , f (k) = k − 1, (2.2) per ogni k > 4. Per come `e definita questa funzione `e evidente che essa risulti suriettiva ma non iniettiva: si mediti sulla figura sottostante che rappresenta tale funzione.

1 2 3 4 5

1 2 3 4 ...

...

f

Figura 3.6: la funzione f definita nella (2.2): si tratta di una funzione da N in N suriettiva e non iniettiva.

3.3. Il grafico di una funzione

Limitiamoci ad esaminare una funzione f : R −→ R.

3.3.1. Definizione. Il grafico di una funzione f : R −→ R `e l’insieme costituito dai punti del piano che hanno coordinate (x, f (x)), al variare di x ∈ R.

Ad esempio il grafico della funzione f (x) = x `e la retta bisettrice del I–III quadrante del piano cartesiano, mentre il grafico della funzione f (x) = x <sup>2</sup> , definita ed a valori in R, `e la caratteristica parabola che tutti conosciamo.

Non vogliamo approfondire molto questo punto, ma segnaliamo che in qualche caso si pu` o leggere l’iniettivit` a e la suriettivit` a di una funzione f : R −→ R direttamente dal suo grafico. Abbiamo detto che ci`o `e possibile solo qualche volta, in quanto non `e sempre facile tracciare il grafico in maniera sufficientemente accurata di una data funzione.

In ogni caso, supposto che tale grafico sia stato disegnato, si procede in questo modo: si considerano le rette parallele all’asse delle x.

• Se ognuna di queste rette taglia il grafico della funzione in almeno un punto, allora la funzione `e suriettiva.

• Se ognuna di tali rette taglia il grafico in al massimo un punto, allora la funzione data `e suriettiva.

Si mediti sulla figura sottostante.

3.4. Immagine di una funzione

Aggiungiamo ora un’altra definizione importante.

3.4.1. Definizione. Sia f : A −→ B una funzione. L’insieme Im(f ) = {b ∈ B : ∃ a ∈ A : f(a) = b}

si chiama immagine (o insieme immagine) di f .

Si dice inoltre che un elemento a ∈ A ha per immagine b ∈ B se si ha f (a) = b.

L’immagine di una funzione rappresenta il sottoinsieme del codominio

i cui elementi sono quelli “raggiunti” da qualche elemento di A.

x y

a

b

b

c

c

grafico di f rette parallele all'asse x

b

intersezioni

Figura 3.7: in questa figura si ha il grafico di una certa funzione f . Essa non risulta n´ e iniettiva, n´ e suriettiva, in quanto vi sono rette parallele all’as- se delle ascisse che non tagliano il grafico della funzione (che non ` e pertanto suriettiva) e rette che tagliano tale grafico in pi` u di un punto (non si ha per- tanto l’iniettivit` a).

3.4.2. Esempio. Sia A = {1, 2, 3} e B = {a, b, c, d, e, f}. Definiamo f nel modo seguente: f (1) = a, f (2) = b, f (3) = a.

L’immagine di f `e l’insieme Im(f ) = {a, b}, cio`e `e l’insieme dei valori effettivamente raggiunti dalla funzione.

3.4.3. Osservazione. Notiamo che una funzione `e suriettiva se e solo se l’immagine di tale funzione coincide con l’intero codominio (ovvero, graficamente, si ha che la parte ombreggiata in Figura 3.8 coincide con tutto B).

3.5. Funzione inversa

Abbiamo detto che una funzione f associa ad ogni elemento del do-

minio uno ed un solo elemento del codominio. Ora vorremmo, in un

Im(f) f

A B

Figura 3.8: l’insieme immagine di f ` e ombreggiato.

certo senso, invertire la procedura ed associare ad elementi del codo- minio i rispettivi elementi del dominio.

Questa relazione, tuttavia, non `e pi` u in generale una funzione. Conside- riamo infatti la funzione f : A −→ B, dove A = {1, 2, 3}, B = {a, b, c, d}

e f (1) = a, f (2) = a, f (3) = d.

A B

1 f 2

3

a b c

d

?

?

f

?

Figura 3.9: funzione non invertibile: al punto a in B non ` e univocamente associato un unico elemento di A ed ai punti b e c non corrisponde alcun ele- mento.

Ora, la funzione inversa che vorremo definire, dovrebbe associare a d il numero 3, dal momento che f (3) = d e dunque porre f ⁻¹ (d) = 3.

Tuttavia gi` a per f <sup>−1</sup> (c) abbiamo dei problemi, dato che non c’`e nessun elemento del dominio che viene mandato in c dalla f . Quindi f ⁻¹ (c) non `e definita.

Inoltre, e qui si ha un secondo problema, si ha che f ⁻¹ (a) vale sia 1

che 2, infatti entrambi questi numeri sono mandati in a dalla funzione f :

A B f

Im(f) f

Figura 3.10: la funzione f ha per dominio A e codominio B: essa ` e biuni- voca, come si accerta subito. La sua funzione inversa f <sup>−1</sup> quindi esiste: essa ha dominio B e per codominio A; f <sup>−1</sup> ` e mostrata con le frecce tratteggiate.

qui c’`e un problema di non univocit` a.

Le considerazioni che abbiamo appena fatto ci inducono a pensare che non tutte le funzioni siano invertibili.

Per ovviare al primo tipo di problema baster` a considerare funzioni su- riettive, mentre per quanto riguarda il secondo problema bisogner` a con- siderare solo funzioni f iniettive: infatti per tali funzioni un qualunque punto b appartenente all’immagine Im(f ) di f proviene da uno ed un solo punto del dominio, ovvero esiste un unico a ∈ A tale che f(a) = b e possiamo pertanto definire f ⁻¹ (b) = a senza ambiguit` a. Dunque le funzioni biunivoche sono le funzioni adatte ad essere invertite.

Ecco la definizione rigorosa.

3.5.1. Definizione. Sia f : A −→ B una funzione biettiva. Allora si definisce la funzione inversa di f , denotandola con f ⁻¹ , nel modo seguente: il dominio di f ⁻¹ `e B (codominio di f ), mentre il codominio di f <sup>−1</sup> `e A (dominio di f ) e si pone

f ⁻¹ (b) = a, dove a ∈ A `e tale che f(a) = b.

3.5.2. Esempio. La funzione f : R −→ R definita da f(x) = x ² non `e

invertibile, poich´e non `e iniettiva, come abbiamo osservato nell’Esem-

pio 3.2.6.

3.5.3. Esempio. La funzione f : R

0 −→ R

0 definita da f (x) = x ²

`e invertibile, poich´e f `e biunivoca, come sappiamo dall’Esercizio 3.2.8.

La sua funzione inversa `e la funzione radice √

· : R

0 −→ R

0 .

3.5.4. Esercizio. Sia f : R −→ R la funzione data da f(x) = x ² − 1.

Calcolare l’immagine di f . E’ una funzione suriettiva? Si tratta di una funzione invertibile?

3.5.5. Esercizio. Sia f : {a, b, c, d} −→ {a, b, c, d} la funzione data da f (a) = f (b) = a, f (c) = f (d) = c. Calcolare l’immagine di f . E’ una funzione suriettiva? Si tratta di una funzione invertibile?

3.5.6. Esercizio. Si trovi la funzione inversa della funzione f : R

0 −→

R

0 data da f (x) = x ² + 2x.

3.5.7. Esercizio. a) Si contino tutte le possibili funzioni da {a, b} in {α, β, γ}.

b) Si contino tutte le possibili funzioni iniettive da {a, b} in {α, β, γ}.

3.5.8. Esercizio. Pu` o esistere una funzione suriettiva f tra un in- sieme di 5 elementi in un insieme di 6 elementi?

3.5.9. Esercizio. Pu` o esistere una funzione iniettiva f tra un insieme di 6 elementi in un insieme di 5 elementi?

3.5.10. Esercizio. E’ vero che una funzione fra due insiemi finiti e

non vuoti con la stessa cardinalit` a k `e iniettiva se e solo se `e suriettiva?

COMBINATORIO

In questo capitolo prendiamo in considerazione alcuni fatti di carat- tere elementare riguardanti il calcolo combinatorio.

4.1. Il Principio di Moltiplicazione

Cominciamo con l’enunciare un principio fondamentale, cui ricorreremo spesso.

Principio di Moltiplicazione (PM). Se k procedure hanno, rispet- tivamente, n ₁ , n ₂ , . . . , n _k esiti possibili, allora ci sono n ₁ ·n 2 · · · · ·n k

esiti possibili risultanti dall’applicazione della prima procedura seguita dalla seconda, dalla terza, ecc., fino alla k-esima.

4.1.1. Esempio. Supponiamo che in un ristorante si servano 3 primi diversi (ad esempio, pasta, riso e zuppa) e 4 secondi (ad esempio vitello, maiale, pesce e pollo). In quanti modi si pu` o mangiare in quel risto- rante?

In questo caso la prima procedura di cui si parla del Principio di Molti- plicazione consiste nello scegliere un primo piatto: questo pu` o essere fatto in n ₁ = 4 modi.

La seconda procedura consiste nello scegliere un secondo, e ci` o pu` o es- sere fatto in n ₂ = 4 modi.

In definitiva, per (PM) si ha che vi sono 3 ·4 = 12 modi possibili per abbinare un primo con secondo. Essi sono, elencandoli,

(pasta, vitello), (riso, vitello), (zuppa, vitello), (pasta, maiale), (riso, maiale), (zuppa, maiale), (pasta, pesce), (riso, pesce), (zuppa, pesce), (pasta, pollo), (riso, pollo), (zuppa, pollo).

Se vi fossero stati 4 antipasti, 6 primi, 10 secondi e 3 dolci, si sarebbero

potuti ottenere 4 ·6·10·3 = 720 possibili men`u differenti.

4.1.2. Esempio. Supponiamo Tizio non ami il riso e pertanto che non gli interessino quei men` u che abbiano “riso” come prima portata.

Quanti men` u avrebbe a disposizione se andasse nel ristorante conside- rato nell’esempio precedente?

Usando di nuovo (PM) abbiamo che Tizio sceglie il primo in n ₁ = 2 modi (non considera infatti il riso), mentre sceglie tranquillamente i secondi in n ₂ = 4 modi. Pertanto per lui ci sono 2 ·4 = 8 possibili men`u a disposizione.

4.1.3. Esercizio. Un lucchetto per biciclette ha un dispositivo di chiu- sura a combinazione formato da tre rotelle dentellate imperniate, ognu- na delle quali pu` o essere ruotata su 10 posizioni numerate da 0 a 9.

Quante combinazioni segrete si possono formare?

01 23 45 67 89

01 23 45 67 89

01 23 45 67 89

Figura 4.1: schema del lucchetto a combinazione dell’Esercizio 4.1.3.

4.1.4. Esercizio. Il PIN di ogni tessera bancomat `e costituito da 5 cifre. Quanti sono i possibili codici segreti?

4.1.5. Esercizio risolto. Supponiamo che in un certo paese straniero le targhe delle automobili siano costituite da due lettere diverse dell’al- fabeto italiano e da tre cifre, dallo 0 al 9.

Quante targhe si possono formare?

Soluzione. Vi sono n ₁ = 21 modi per scegliere la prima lettera della targa. La seconda lettera pu` o essere scelta in n <sub>2</sub> = 20 modi, in quanto non si possono avere due lettere uguali. Poi la prima cifra pu` o essere scelta in n ₃ = 10 modi ed analogamente per le altre due: n ₄ = n ₅ = 10.

In definitiva, si hanno 21 ·20·10·10·10 = 420 000 possibili targhe.

4.1.6. Esercizio risolto. Estraiamo da un comune mazzo di 40 carte tre carte consecutivamente, reinserendo subito nel mazzo la carta di volta in volta estratta.

Qual `e il numero di casi in cui la prima carta sia un Re e la seconda non sia di fiori?

Soluzione. Vi sono n ₁ = 4 modi possibili perch´e la prima carta e- stratta sia un Re e vi sono n ₂ = 30 modi possibili perch´e la seconda carta estratta non sia un fiori, mentre vi sono ovviamente 40 modi per estrarre l’ultima.

In totale si hanno 4 ·30·40 = 4 800 estrazioni possibili.

4.1.7. Esercizio. (1) Quante parole di tre lettere si possono formare usando l’alfabeto ridotto A = {a, b, c, d}?

(Per “parola” si intender` a qui sempre una mera sequenza ordinata di lettere giustapposte. Ad esempio, aac `e una parola ammessa, anche se nella nostra lingua non ha alcun senso.)

(2) Quante parole di tre lettere che non finiscono per d si possono formare?

(3) Quante parole di tre lettere che abbiano due lettere b si possono formare?

(4) Quante parole di tre lettere che abbiano almeno due lettere b si possono formare?

4.2. Disposizioni semplici

Supponiamo di avere un insieme A di n oggetti: vogliamo sapere in quanti modi si pu` o formare una lista ordinata di k oggetti scelti fra questi n.

Una tale lista `e ci` o che chiamiamo disposizione di k oggetti scelti in n.

4.2.1. Definizione. Sia A un insieme di n elementi. Una qualunque lista ordinata di k ≤ n oggetti scelti fra questi n si chiama disposizione semplice di elementi di A a k a k.

Il numero di tutte le disposizioni semplici di elementi di A a k a k `e

denotato con D(n, k), dove n indica il numero di elementi di A.