September 30, 2014

INSIEMI

In modo piuttosto informale si introducono nozioni e notazioni insiemistiche che vengono corrente-mente usate per sviluppare le teorie matematiche tra cui quella che e argomento del corso.

1. Nozioni di base

La notazione fondamentale ea A

che si legge a e un elemento dellinsieme A oppure, equivalentemente, a appartiene ad A. Ilsimbolo indica quindi una relazione (di appartenenza) che puo correlare (o no) un elemento edun insieme. La notazione a / A significa che a non e un elemento di A cioe che a non appartiene adA. I concetti di elemento e di insieme sono concetti primitivi, cioe non vengono definiti in terminidi altri concetti piu elemetari. Per dare sostanza al discorso postuleremo che certi enti sono insiemi.Per esempio gli insiemi di numeri N, Z, Q, R (naturali, interi, razionali, reali) che assumiamo piu omeno familiari al lettore sono, appunto, insiemi. Inoltre fisseremo in modo preciso certe procedureper manipolare gli insiemi, per esempio per costruire nuovi insiemi a partire da insiemi dati.

La notazioneA B

si legge dicendo che linsieme A e un sottoinsieme dellinsieme B oppure, equivalentemente, che Ae contenuto in B; significa che ogni elemento di A e anche un elemento di B (cioe se a A alloraa B). Quindi indica una relazione (di inclusione) che puo correlare (o no) un insieme conun altro insieme. Per ogni insieme A, si ha che A A. Postuliamo che esiste linsieme vuoto, cioelinsieme privo di elementi che e indicato con il simbolo . Per ogni insieme A, A. A non econtenuto in B se esiste un elemento a A tale che a / B. A e strettamente contenuto in B se A Bed esiste b B che non appartiene a A.

PoniamoA = B

se valgono entrambe le inclusioniA B e B A .

Quindi A 6= B se esiste a A che non appartiene a B o esiste b B che non appartiene ad A, dovequesto o non e esclusivo, ma significa che almeno una delle due circostanze si verifica.

Attenzione alle notazioni senza senso: se A e B sono insiemi, allora la notazione A B non hasenso. Se a A, allora la notazione a A non ha senso. Invece ha senso scrivere {a} A, dove {a}e linsieme costituito dal solo elemento a; in particolare ha senso scrivere a {a}.

1.1. Unione, intersezione, complementare. Dati due insiemi A e B, linsieme unione

A B

e caratterizzato dalla proprieta che x A B se e solo se x A o x B. Come sopra, questo onon e esclusivo: richiediamo che x appartenga ad almeno uno dei due insiemi A, B. E chiaro cheA,B A B, cioe entrambi gli insiemi A e B sono sottoinsiemi dellinsieme unione A B.

Linsieme intersezioneA B

e tale che x A B se e solo se x A e x B, cioe x e un elemento di entrambi gli insiemi A e B.E chiaro che A B A,B, cioe lintersezione e un sottoinsieme di entrambi gli insiemi A e B.

Se A B, alloraCB(A) = {x B|x / A}

e linsieme complementare di A in B. Si verifica che (farlo per esercizio):

1

2 INSIEMI

(1) CB(CB(A)) = A;(2) Se A,D B, allora

CB(A D) = CB(A) CB(D)

CB(A D) = CB(A) CB(D) .

Dati due insiemi A, BA \B := CA(A B)

e per definizione linsieme differenza. Si osserva che A B \ A B consiste proprio degli elementidellinsieme unione che appartengono in modo esclusivo ad A oppure a B.

1.2. Prodotto. Dati insiemi non vuoti A1, . . . , An, linsieme prodotto A1 An ha per elementi len-uple ordinate (a1, . . . , an) tali che, per ogni j = 1, . . . , n, aj Aj . Attenzione, lordine e essenziale:ad esempio (1, 2) e (2, 1) sono elementi diversi dellinsieme prodotto N N.

1.3. Linsieme delle parti. Dato un insieme A, P(A) e linsieme che ha per elementi i sottoinsiemidi A. Linsieme delle parti P(A) e sempre non vuoto perche P(A). In particolare P() e nonvuoto e e il suo unico elemento. Se A e non vuoto e a A, allora a {a} P(A), ma a / P(A);daltra parte se a A e A B, allora a B. Questo mette in evidenza il fatto (sottile e importante)che lo stato di un ente in quanto elemento o insieme non e dato una volta per tutte ma dipendedalla relazione con altri enti. Si puo iterare la costruzione in modo induttivo (si veda la dispensa[INDUZIONE]) ponendo

P(n)(A) = P(Pn1(A)) .

Per esempio P(P()) = {, {}} e costituto di due elementi. La possibilita di creare insiemi i cuielementi sono insiemi e un punto molto delicato del discorso, su cui torneremo in seguito per i lettoriparticolarmente interessati.

1.4. Funzioni. Una funzionef : A B

(chiamata anche con il sinonimo applicazione) definita sullinsieme A a valori nellinsieme B, associaad ogni a A un unico elemento b = f(a) B. A volte A e detto il dominio di definizione di f , B ilcodominio.

Data una funzione f : A B, il sottoinsieme di B:

Im(f) = {b B| a A, f(a) = b}

e detto limmagine di f . A volte si scrive anche f(A) invece di Im(f).

Per ogni C B, il sottoinsieme di A:

f1(C) = {a A| f(a) C}

e detto limmagine inversa o anche la controimmagine di C.

Il sottoinsieme di AB:G(f) = {(a, b) AB| b = f(a)}

e detto il grafico di f . Si osserva che G(f) A f(A).

Attenzione: Una funzione e il suo grafico sono strettamente legati tra loro ma non sono la stessacosa. Trattando le funzioni bisogna imparare a tenere concettualmente distinti i vari oggetti associati(dominio di definizione, immagine, grafico, ...); per esempio, data una funzione f : A B, la notazionea f non ha senso; bisogna avere chiaro se si intende un elemento a A, un elemento f(a) f(A),oppure un elemento (a, f(a)) G(f), . . . e cos via.

Una funzione f : A B e surgettiva se B = f(A), cioe per ogni elemento b B esiste a A tale chef(a) = b. E iniettiva se per ogni b f(A), esiste un unico a A tale che f(a) = b. Attenzione a nonconfondere (come agli studenti capita spesso) la definizione di funzione iniettiva con la definizionestessa di funzione. La proprieta di essere iniettiva si puo esprimere in modo equivalente dicendo

INSIEMI 3

che per ogni b f(A), f1({b}) = {a}, oppure dicendo che per ogni coppia di elementi a1, a2 A, sea1 6= a2 allora f(a1) 6= f(a2).

Una funzione f : A B e bigettiva se e contemporaneamente iniettiva e surgettiva.Per ogni A 6= ,

idA : A A, x A, idA(x) = x

e la funzione identita di A che e evidentemente bigettiva. Se C A,

i : C A, x C, i(x) = x

e la funzione di inclusione di C in A che e evidentemente iniettiva.

Dati due insiemi non vuoti A e B indicheremo con

BA = {f : A B}

cioe linsieme di tutte le applicazioni definite su A a valori in B.

1.5. Composizione di funzioni. Date due funzioni f : A B e g : B C, definiamo la funzionecomposta

g f : A C, x A, (g f)(x) = g(f(x)) .

Se f e bigettiva, possiamo definire la funzione inversa

f1 : B A

dove per ogni b B, a = f1(b) e lunico a A tale che f(a) = b; si ha che (f1 f) = idA,(f f1) = idB.Attenzione. Per ogni funzione f : A B e per ogni C B, abbiamo gia incontrato linsiemeimmagine inversa f1(C). In questo caso non facciamo alcuna ipotesi particolare sulla funzione f .Invece la funzione inversa f1 e definita solo se f e bigettiva. Quindi il simbolo f1 ha un significatodiverso nei due contesti. Attenti a non fare confusione.

2. Logichetta: proposizioni e teoremi

Allinterno di una teoria matematica (per esempio quella di Analisi I) si trattano proposizionisensate (in particolare formulate rispettando le regole di una certa sintassi - includendo nel nostrocaso le regole dellitaliano), che sono in modo esclusivo vere oppure false, cioe non possono esserecontemporaneamente vere e false: capita una e una sola delle due possibilita. Il corpo della teoria inun dato momento del suo sviluppo e dato dallinsieme delle proposizioni che sono state riconosciutecome vere (e magari anche interessanti). La dimostrazione di un nuovo teorema della teoria accresceil numero di proposizioni riconosciute come vere. Di solito la teoria non e compiuta nel senso cherestano sul campo proposizioni sensate (e anche interessanti) che pero sono ancora indeterminate,cioe non e ancora noto se siano vere oppure false.Si incontrano diversi tipi di proposizioni sensate. Per il tipo piu semplice si fissa un insieme A, unelemento a A e di predica una proprieta p che a puo verificare (o no). La proposione e vera se esolo se a verifica la proprieta. Ad esempio a = 5 N = A, p := 2|5 (cioe 5 e pari).

e una proposizione (falsa) di questo tipo. A volte possiamo considerare famiglie di proposizioni diquesto tipo che dipendono da un parametro a che varia in A. Ogni volta che fissiamo il valore delparametro, otteniamo una proposizione del tipo in questione. Una cosa di questo genere capita quandodefiniamo un sottoinsieme si A per mezzo di una proprieta verificata dai suoi elementi. Per esempio

{n N| 2|n} N

definisce il sottoinsieme dei numeri pari.Proposizioni piu complicate si ottengono ammettendo che intervengano diversi elementi che varianoeffettivamente e non necessariamente in un unico insieme. In questo caso e essenziale luso correttodei due quantificatori esiste () e per ogni (). Esempi minimali di proposizioni di questo tiposono della forma:

4 INSIEMI

a A che verifica la proprieta p

oppure

a A, a verifica la proprieta p.

Lespressione senza quantificatori a A, a verifica la proprieta p, non e sensata.Di solito si ha pero a che fare con proposizioni sensate piu complicate dove frammenti elementari sicombinano variamente. Per esempio incontreremo in seguito la seguente proposizione sensata (e vera- il significato dei termini e i simboli usati saranno definiti in seguito):

f : [a, b] R continua, R, > 0, R, > 0, tale che x [a, b], y [a, b], se |y x| < ,allora |f(y) f(x)| < .

Attenzione. In una proposizione in cui appaiono piu di un quantificatore, lordine dei quantificatorie cruciale. Cambiando lordine il senso della proposizione puo cambiare radicalmente. Si consideri adesempio:

n N, m N, m > n

m N, n N, m > n

nel primo caso si afferma che per ogni n esiste m piu grande di n (vera: basta per esempio prenderem = n + 1). Nel secondo caso si afferma che esiste m che e piu grande di qualsiasi n (falsa: infattiper ogni m esiste n (per esempio n = m+ 1) tale che m < n).

Le proposizioni si possono manipolare e combinare in modi che ricordano quanto abbiamo fatto congli insiemi. Se P e Q sono due proposizioni, abbiamo la proposizione

P o Q

che e vera se e solo se P e vera o Q e vera. Qui o non e esclusivo, come nella definizione dellunioneA B: richiediamo che almeno una delle due proposizioni sia vera.

La proposizione

P e Q

e vera se e solo se P e Q sono entrambe vere, analogamente a quanto accadeva nella definizionedellintersezione A B.

La negazione

non(P )

e vera se e solo se P e falsa. Chiaramente non(non (P ))=P (proprieta che ricorda quelle del comple-mentare CB(A)).

E importante sapere negare una proposizione. Per le proposizioni minimali, basta scambiare i quan-tificatori e negare la proprieta. Ad esempio la negazione di:

a N, a e pari

(che e falsa) e

a N che non e pari

(che e vera). Per le proposizioni piu complesse occorre applicare ripetutamente questa regola di base,insieme allaltra per cui o e si scambiano, facendo un po di pratica. Per esempio:

non(P o Q) e vera se e solo se e vera non(P ) e non(Q). Si osserva lanalogia con:

CB(A D) = CB(A) CB(D)

non(P e Q) e vera se e solo se e vera non(P ) o non(Q). Si osserva lanalogia con:

CB(A D) = CB(A) CB(D) .

INSIEMI 5

Una proposizione della forma

P e non(P )

e sempre falsa e viene detta una contraddizione. La sua negazione

non (P ) o P

e sempre vera.

Tipicamente la dimostrazione di un teorema consiste nel verificare che una certa implicazione e vera.Un implicazione ha la forma

P = Q

e si legge se P allora Q. Infatti vale la seguente regola di deduzione:

Se P e vera ed e vera limplicazione P = Q, allora anche Q e vera.

Dunque se P faceva gia parte del corpo della teoria che stiamo sviluppando, dimostrando che limplicazionee vera, aggiungiamo Q al corpo della teoria. Il lettore esigente potrebbe pensare che in effetti nonabbiamo ancora detto precisamente cosa intendiamo per P = Q. Lo accontentiamo dicendo che eun altro modo di denotare la proposizione

non(P ) o Q

Si noti infatti che se questultima e vera e P e vera, allora non(P ) e falsa e quindi necessariamente Qe vera, in accordo con la regola di deduzione che abbiamo enunciato sopra.Un fatto spesso utile e che limplicazione

P = Q

e equivalente alla sua contronominale

non(Q) = non(P )

cioe la prima implicazione e vera se e solo se e vera la seconda. Per esempio supponiamo di voleredimostrare limplicazione:

h = f g iniettiva = g iniettiva

la contronominale e

g non iniettiva = h = f g non iniettiva

e questa implicazione e facile da dimostrare: infatti se x 6= y sono tali che g(x) = g(y), allorah(x) = f(g(x)) = f(g(y)) = h(y).Una versione piu elaborata ma sostanzialmente equivalente alluso della contronominale e la cosiddettadimostrazione per assurdo. Si procede cos: volendo dimostrare limplicazione

P = Q

si dimostra invece unimplicazione della forma

P e non(Q) = S

dove sappiamo che S e falsa. Allora, se P e vera, necessariamente non(Q) e falsa, perche altrimenti,grazie alla solita regola di deduzione, S sarebbe vera ed invece sappiamo che e falsa. Dunque Q evera. Nella pratica molto spesso la S che funziona e della forma

S = N e non(N)

cioe e una contraddizione.

Avvertenza: Nella parte che segue faremo riferimento al principio di induzione. Pertanto, primadi procedere con la presente dispensa, conviene leggere (e capire) la dispensa [INDUZIONE].

6 INSIEMI

3. Insiemi finiti, numero di elementi

Per ogni n 1, il sottoinsieme di N

In = {0, 1, 2, . . . , n 1} N

e linsieme finito campione con n 1 elementi.Un insieme A e finito se e vuoto, oppure esistono n 1 e unapplicazione bigettiva f : In A. Iseguenti fatti sono del tutto intuitivi, non sono difficili da dimostrare e comunque saranno assunticome veri.

Esiste unapplicazione bigettiva f : In Im se e solo se m = n. Se A e finito e non vuoto, allora esiste un unico n 1 per il quale esiste f : In A bigettiva.Allora |A| = n e per definizione il numero di elementi di A. Naturalmente poniamo || = 0.

Se A e finito, C A, allora: C e finito; |C| |A|; |C| = |A| se e solo se C = A. A e B finiti non vuoti, allora:

(i) |A| |B| se e solo se esiste f : B A iniettiva.(ii) |A| = |B| se e solo se esiste f : B A bigettiva.(iii) |A| = |B| se e solo se |A| |B| e |A| |B|.

3.1. Un po di calcolo combinatorio. In una certa misura il calcolo combinatorio consiste neldeterminare il numero di elementi di un certo insieme finito A in funzione del numero di elementi dialtri insiemi finiti che intervengono nella definizione di A. Vedremo alcuni esempi.

(1) Siano |A| = m, |B| = n, n,m 1. Allora |BA| = nm. Dimostriamolo per induzione su m 1.Se m = 1, A = {a}, e ci sono n modi di definire f(a). Se |A| = s + 1, fissiamo a A e siaA = A\{a}. Quindi |A| = s. Ci sono n modi di definire b = f(a). Per ogni scelta di b = f(a)questa si completa ad una f : A B, per mezzo di una qualsiasi funzione g : A B. Perinduzione ci sono ns possibilita per definire g e quindi in totale n ns = ns+1 possibilita perdefinire f .

(2) Se |A| = n, allora |P(A)| = 2n. Diamo una prima dimostrazione costruendo unapplicazionebigettiva

f : P(A) {0, 1}A .

In tal caso si avra che |P(A)| = |{0, 1}A| = 2n. Per ogni C P(A), sia 1C : A {0, 1}tale che 1C(x) = 1 se e solo se x C. Questa e detta la funzione indicatrice del sottoinsiemeC. Poniamo allora f(C) = 1C . Dimostriamo che f e iniettiva: infatti se C 6= C

(a menodi invertire lordine dei due insiemi) esiste x C tale che x / C. Ma allora 1 = 1C(x) 6=1C(x) = 0, cioe f(C) 6= f(C

). Dimostriamo che f e surgettiva. Infatti data g : A {0, 1},sia C = g1(1). Allora f(C) = 1C = g.

Diamo ora un altra dimostrazione per induzione su n 0. Se n = 0, A = , P(A) = {},1 = 20. Supponiamo ora che |A| = n+1. Fissiamo a A. Definiamo X = {C P(A)| a C},Y = {C P(A)| a / C}. Allora P(A) = XY e XY = . Ne segue che |P(A)| = |X |+ |Y |.Sia A = A \ {a}. |A| = n. Definiamo

: P(A) X, (C) = C {a}

: P(A) Y, (C) = C .

Si verifica facilmente che sono entrambe bigettive. Allora, per induzione |X | = |Y | = |P(A)| =2n, |P(A)| = 2n + 2n = 2n+1.

(3) Se |A| = n, |B| = m, m n 1, poniamo i(A,B) linsieme delle applicazioni iniettive definite

su A a valori in B. Allora |i(A,B)| = m(m 1) . . . (m n + 1) =m!

(m n)!. Operiamo per

induzione su n 1. Per n = 1, A = {a}, e ci sono m modi di definire b = f(a) B. Se|A| = s+ 1, s + 1 m, fissiamo a A, poniamo A = A \ {a}, |A| = s. Ci sono m modi diassegnare b = f(a) B. Fissato uno di questi modi ci sono |i(A, B \{b})| modi di completareil dato b = f(a) ad unapplicazione iniettiva definita su tutto A. Dunque, per induzione,

INSIEMI 7

|i(A,B)| = m[(m 1) . . . (m 1 (n 1) + 1)] come voluto. Se n = m, i(A,B) e linsiemedelle applicazioni bigettive definite su A a valori in B e risulta |i(A,B)| = n! .

(4) Sia |A| = n, 0 m n. Poniamo

Pm(A) := {C P(A)| |C| = m}(

n

m

)

:= |Pm(A)| .

Ricaviamo un metodo induttivo per calcolare questi numeri, noto anche come triangolo diTartaglia detto anche di Pascal.

Il triangolo in questione e dato dal sottoinsieme di N2, T = {(n,m) N2| n m}.

Lungo il bordo di T abbiamo

(

n

n

)

=

(

n

0

)

= 1. Infatti A e lunico sottoinsieme di A

con n elementi, e lunico con 0 elementi. Consideriamo ora 0 < m < n. Fissiamo a A. A = A \ {a}. |A| = n 1. Con lo stessoargomento della dimostrazione induttiva vista sopra di |P(A)| = 2n, osserviamo che:

|Pm(A)| = |Pm1(A)|+ |Pm(A

)|

da cui equivalentemente:(

n

m

)

=

(

n 1

m 1

)

+

(

n 1

m

)

.

Questo schema induttivo determina completamente

(

n

m

)

per ogni (n,m) T . Per ricondursi

ad una induzione formalmente piu ordinaria, definiamo per ogni (n,m) T la distanza d(n,m)di (n,m) dal bordo di T come il numero minimo di segmenti orizzontali o verticali nel piano R2

con estremi in N2 che e necessario percorrere per andare da (n,m) ad un punto di coordinate(p, p) o (p, 0). Chiaramente d(p, p) = d(p, 0) = 0. Allora lo schema induttivo stabilito sopra

puo essere riconvertito in una definizione di

(

n

m

)

per induzione su d = d(n,m) 0.

Nelle stesse ipotesi, poniamo adesso

F (n,m) =n!

m!(nm)!.

Affermiamo che

F (n,m) =

(

n

m

)

.

Ci sono almeno due modi per dimostrarlo; il primo consiste nel verificare algebricamente che

F (n,m) verifica lo stesso schema induttivo che definisce

(

n

m

)

, cioe che:

F (n, 0) = F (n, n) = 0

F (n,m) = F (n 1,m 1) + F (n 1,m) .

Il secondo metodo considera lapplicazione surgettiva

g : i(Im, A) Pm(A), g(h) = h(Im)

cioe g associa ad ogni applicazione iniettiva h : Im A la sua immagine che ha appunto melementi. Si osserva poi che per ogni C Pm(A) ci sono m! funzioni h tali che g(h) = h(Im) =C. Si conclude che

(

n

m

)

=|i(Im, A)|

m!= F (n,m) .

Segue inoltre dalle considerazioni precedenti che:n

j=0

(

n

j

)

=

n

j=0

|Pj(A)| = |P(A)| = 2n .

8 INSIEMI

(5) I numeri

(

n

m

)

si chiamano anche coefficienti binomiali perche intervengono nello sviluppo

delle potenze di un binomio secondo la formula di Newton:

(a+ b)n =

n

j=0

(

n

j

)

ajbnj

che si puo dimostrare sia per induzione su n 0, sia identificando esplicitamente il coefficiente

del monomio ajbnj con il numero

(

n

j

)

, usando la prima definizione che ne abbiamo dato.

4. Insiemi infiniti, cardinalita

Un insieme A e infinito se non e finito. Vogliamo estendere la nozione di numero degli elementi alcaso di insiemi arbitrari (finiti o infiniti). Prendiamo alcune delle proprieta del numero di elementi diun insieme finito come modello della definizione generale.

Definizione 4.1. Dati due insiemi A e B diciamo che A ha cardinalita (a volte si dice anche potenza)maggiore o uguale a quella di B (e scriveremo |A| |B|) se esiste f : B A iniettiva. Diremo che Ae B hanno la stessa cardinalita e scriveremo |A| = |B|, se esiste g : B A bigettiva. Diremo che Aha cardinalita strettamente maggiore a quella di B e scriveremo |A| > |B|, se |A| |B| ma |A| 6= |B|,cioe esiste f : B A iniettiva ma non esiste g : B A bigettiva.

Nel caso degli insiemi finiti ritroviamo lusuale numero di elementi |A| N. In generale la cardinalitanon e un numero ma una specie di qualita condivisa da due insiemi correlati da una applicazionebigettiva. Se |A| = |N|, allora diciamo che A e numerabile. Bisogna stare attenti perche diverseproprieta che sono intuitivamente evidenti nel caso degli insiemi finiti, invece non sono piu vereper gli insiemi infiniti, come mostra il punto (2) nel seguente teorema. Questo sara conseguenza diun ulteriore proprieta che postuliamo verificata dagli insiemi. Ancora una volta, questa proprieta eintuitivamente del tutto accettabile nel caso degli insiemi finiti, lo e molto meno per quelli infiniti. Sistratta dellesistenza di funzioni di scelta:

Per ogni insieme non vuoto A e per ogni X P(A) non vuoto tale che ogni C X, C 6= , postuliamolesistenza di una funzione (di scelta)

s : X A

tale che per ogni C X, s(C) C. In altre parole la funzione s sceglie un elemento s(C) in ogniinsieme C appartenente alla famiglia X di sottoinsiemi non vuoti di A.

Teorema 4.1. (1) Sia A un insieme infinito. Allora |A| |N|.(2) Linsieme A e infinito se e solo se esiste B A, B 6= A, tale che |A| = |B|.

Dim. (1) Sia X il sottoinsieme di P(A) formato dai sottoinsiemi non vuoti di A. Definiamo perinduzione f : N A iniettiva, partendo da una funzione di scelta s : X A (di cui abbiamopostulato lesistenza). Poniamo allora f(0) = s(A), f(n+1) = s(A \ {f(0), . . . , f(n)}). Si osservi chef e ben definita perche, essendo A infinito, per ogni n, A\{f(0), . . . , f(n)} e non vuoto. E immediatoche f cos definita e iniettiva.

(2) Se A e finito sappiamo gia che un tale B non esiste. Resta da dimostrare che invece esiste se Ae infinito. Dimostriamo intanto la tesi quando A = N. Poniamo B = 2N, cioe linsieme dei numeripari. g : N 2N, g(n) = 2n e bigettiva, quindi |N| = |2N|. In generale sia f : N A iniettiva comein (1). A = f(N) CA(f(N)) e poniamo: B = f(2N) CA(f(N)); G : A B, G(x) = f(g(f

1(x)))se x f(N), G(x) = x altrimenti. G e bigettiva. 2

Altre proprieta del numero degli elementi invece si generalizzano alla cardinalita degli insiemi (ancheinfiniti). Indichiamone alcune.

Vale in generale il seguente Teorema di Bernstein la cui dimostrazione, abbastanza complicata,viene omessa.

Teorema 4.2. Dati due insiemi A e B, se |A| |B| e |B| |A|, allora |A| = |B|.

INSIEMI 9

Si ricordi che le cardinalita non sono numeri ordinari. Si tratterebbe di dimostrare che seesistono f : B A e h : A B entrambe iniettive (e a priori del tutto indipendenti tra loro),allora esiste g : A B bigettiva. Se ci si pensa un pochino si capisce che la cosa non e affattoevidente.

Abbiamo visto prima che se A e finito, |A| = n, allora |P(A)| = 2n e quindi |P(A)| > |A|.Anche questa proprieta si generalizza.

Teorema 4.3. Per ogni insieme A, |P(A)| > |A|.

Dim. Dimostriamo intanto che |P(A)| |A| cioe che esiste f : A P(A) iniettiva. Infattibasta porre per ogni a A, f(a) = {a}. Per concludere basta dimostrare che qualsiasig : A P(A) non puo essere surgettiva. Infatti, data g, poniamo C = {x A| x / g(x)}.Affermiamo che C non appartiene allimmagine g(A). Infatti se fosse C = g(y), y C se esolo se y / g(y) = C e questo e assurdo. 2

Se A e B sono finiti ed esiste g : A B surgettiva, allora e facile vedere che |A| |B|. Anchequesta proprieta si generalizza:

Teorema 4.4. Sia g : A B unapplicazione surgettiva. Allora |A| |B|.

Dim. Vogliamo mostrare che esiste f : B A iniettiva. Per ogni b B, Xb = g1(b)

P(A) e non vuoto perche g e surgettiva. Poniamo X = {Xb| b B}. Sia s : X A unafunzione di scelta. Definiamo f(b) = s(Xb). Resta da verificare che f e iniettiva. Infatti seb 6= b, Xb Xb = , da cui f(b) 6= f(b

) perche appartengono a sottoinsiemi disgiunti di A.2

Osservazioni 4.2. (Per un lettore particolarmente interessato.) Abbiamo detto allinizio che lapossibilita di formare insiemi i cui elementi sono insiemi e un punto delicato che puo portare a seriedifficolta. Ispirati anche dalla penultima dimostrazione, consideriamo l insieme U formato da tuttigli insiemi che non sono un elemento di se stessi. Allora U U se e solo se U / U . Questo eassurdo, quindi nella nostra teoria ce un paradosso. Potremmo cercare di aggirarlo aggiungendo agliassiomi della nostra teoria degli insiemi la proprieta che ogni insieme non puo essere un elementodi se stesso. Ma il paradosso riappare considerando ora come U l insieme di tutti gli insiemi. Unmodo piu sostificato di aggirare il paradosso e allora quello di decretare che U non e un insieme,accettando cos di pagare il prezzo che la nostra teoria degli insiemi non e chiusa in se stessa e siimmege in una qualche sovra-teoria (in cui magari si annidano altri paradossi meno immediati....).Ma anche pagando questo prezzo, nella pratica lavoriamo tranquillamente con molti insiemi diinsiemi che, appunto, abbiamo decretato essere insiemi. E se ci fosse annidato da qualche parte unparadosso meno evidente ma altrettanto fatale .... ?

4.1. Alcuni confronti di cardinalita. Dimostriamo per esempio che |N| = |N2|. Costruiamo cioef : N N2 bigettiva. Consideriamo N2 come un sottoinsieme del piano R2. Consideriamo la famigliadi rette parallele rn, n 0, di equazione x + y = n. Sia Un = rn N

2. Allora: per ogni n N,|Un| = n + 1; Un Um = se n 6= m; N

2 = nNUn. Ordiniamo totalmente gli elementi di N2 nel

modo seguente:

Se (a, b) rm, (c, d) rn, n > m, allora (c, d) > (a, d). Se (a, b), (c, d) rm, a > c, allora (a, b) > (c, d).

Si verifica che e un buon ordinamento (linsieme degli Un e bene ordinato come lo e N, ogni Un e finitoe quindi ben ordinato). Si puo allora definire f per induzione, ponendo f(0) = (0, 0) cioe uguale alminimo elemento di N2, f(n+ 1) uguale al minimo elemento di N2 \ {f(0), . . . , f(n)}.

Dimostriamo che |N| = |Q+|. Usando la rappresentazione di ogni numero razionale per mezzo diununica frazione ridotta ai minimi termini abbiamo che

Q+ = {n

d| (n, d) N2, d > 0, MCD(n, d) = 1} .

Lapplicazione

j : Q+ N2, j(n

d) = (n, d)

10 INSIEMI

e evidentemente iniettiva. Consideriamo j1 : j(Q+) Q+ che e bigettiva. Consideriamo su N2 ilbuon ordinamento totale gia usato prima. Il sottoinsieme j(Q+) N2 eredita un buon ordinamentototale. Possiamo allora definire per induzione g : N j(Q+) bigettiva usando la stessa procedurausata prima per definire f : N N2. Infine j1g : N Q+ e lapplicazione bigettiva cercata. Questorisultato puo apparire anti-intuitivo se consideriamo N e Q+ come sottoinsiemi di R+ e ricordiamo cheN e discreto mentre Q+ e denso in R (vedi [REALI]). Il punto e che quando trattiamo la cardinalita,gli insiemi sono nudi cioe privi di qualsiasi altra struttura ulteriore (quale quella, per esempio, chee necessaria per potere definire cosa vuol dire che Q e denso in R).

Poiche linclusione i : N R e iniettiva, ne segue che |R| |N|. In effetti si puo mostrare che |R| > |N|(vedi [AD]).

Osservazioni 4.3. (Per un lettore particolarmente interessato.) Consideriamo la seguente propo-sizione sensata

Esiste un insieme infinito X tale che |N| < |X | < |R|.

La sua negazione e anche nota come ipotesi del continuo. Per lungo tempo e stata una proposizioneindeterminata della teoria degli insiemi(nel senso di quanto detto nel capitolo 2). Alla fine e statoappurato che e in effetti indecidibile. Questultimo aggettivo ha un significato preciso e molto ripostoche non siamo in grado qui di spiegare. Vogliamo solo segnalare che lo studio di questa proposizioneha portato ad alcune delle riflessioni piu profonde sui fondamenti della logica e della matematica.

12 Ottobre 2014

I Reali: un approccio quasi assiomatico.

Indice

1 Primi passi. 1

2 Alcune proprieta (importanti) di R. 7

3 Estremo superiore ed estremo inferiore. 9

4 Un teorema di unicita. 10

5 Rappresentazione decimale. 11

6 Approssimazione. 13

7 Radici e potenze. 14

8 Rappresentazione decimale e numeri razionali: algoritmo della fra-zione generatrice. 16

1 Primi passi.

Dovendo introdurre i reali e dobbligo un riferimento al mondo greco, al loro gustoper la riflessione teorica, ed al fatto che la scoperta della non commensurabilita dellato e della diagonale del quadrato abbia messo in crisi i fondameni di una concezionedel mondo, che vedeva tutto come proveniente da un armonico assembramento diparticelle elementari.

Cio si applicava in particolare anche alle grandezze geometriche, intuitivamente re-cepite come omogenee: questa scoperta metteva in crisi il fatto che due grandezzeavessero sempre un comune sottomultiplo e quindi che tutti i rapporti fra grandezzepotessero esser valutati in termini di rapporti di numeri interi, arrivando in un certosenso a valutare quanti elementi corpuscolari simili le costituissero.

Ad esempio si pensi al processo pitagorico che poteva portare alla determinazionedi una possibile grandezza in comune tra due grandezze pensate come lunghezze didue segmenti. Si prende il segmento piu corto e si ricopre quello piu lungo con tantecopie di quello piu corto: se si arriva a ricoprirlo si finisce altrimenti si prende il

segmento rimanente e si cerca di ricoprire il piu corto con tante copie di questultimo.Anche qui se ci si riesce si termina altrimenti si ricomincia. Per i pitagorici questoprocedimento avrebbe dovuto sempre terminare e questo e praticamente equivalentealla commensurabilita: una sorta di algoritmo di Euclide geometrico. La scopertadi grandezze incommensurabili dava una scossa proprio a questa concezione.

A tutto cio si aggiunse lazione critica di altri pensatori come Zenone che non riusci-vano a conciliare questa visione con il fatto che una grandezza finita potesse risultaredalla somma di un numero infinito di grandezze finite (Achille e la tartaruga).

Anche se queste idee saranno presenti in sottofondo lungo tutto il testo, ripercorrerlein dettaglio e pero fuori dagli scopi di queste brevi note e preferiamo rimandare peruna trattazione piu sistematica a testi di storia della matematica o della scienza.

Vogliamo qui solo introdurre in modo rapido linsieme dei numeri reali seguendoun approccio astratto che si rifa a Dedekind, ancorche anche egli, almeno a suodire, probabilmente altro non fece che evidenziare le idee gia espresse nel mondogreco, rifacendosi al metodo per confrontare due grandezze detto di esaustione eal principio di Eratostene, che per comodita del lettore riportiamo qui di seguitoutilizzando terminologie piu moderne.

Pricipio di Eratostene. Diremo che due grandezze a e b sono nella stessa proporzionedi altre due grandezze A e B se comunque fissati due numeri interi positivi m e n siha

ma < nb se e solo se mA < nB

ma > nb se e solo se mA > nB

Fissiamo il contesto. Il nostro punto di partenza saranno gli insiemi numerici, nelsenso che daremo per noti gli insiemi dei numeri naturali (N), dei numeri interi (Z) edei numeri razionali (Q) con le loro principali proprieta e la usuale rappresentazionedecimale dei numeri razionali.

Cerchiamo un insiemeX che estenda gli insiemi N, Z e Q e in cui si possano fare delleoperazioni e delle considerazioni che ad esempio in Q non si possono fare, come adesempio la misurazione della diagonale del quadrato o provare che Achille raggiungela tartaruga.

Abbiamo pertanto bisogno di un insieme X e del fatto che su questo insieme sipossano fare (siano cioe definite) due operazioni che chiameremo somma e prodottoe che indicheremo rispettivamente con + e con . Una operazione (binaria) su Xaltro non e che una legge che associa ad una coppia di elementi di X un altroelemento di X: si pensi allusuale somma in Z. Vorremo inoltre poter operare conun certo numero di regole di calcolo: chiederemo quindi che le operazioni soddisfinoun numero minimo di regole da cui poter ricavare le altre, cioe che le operazioniverifichino un elenco, se pur minimo, di assiomi.

Abbiamo quindi bisogno di un insieme X, la natura dei cui elementi per ora lascia-mo nel vago, e su X pensiamo definite due operazioni, cioe due applicazioni chechiameremo rispettivamente somma e prodotto

2

X X X, (x, y) x+ y

X X X, (x, y) x y

che verificano i seguenti assiomi:

1. assiomi per loperazione somma

S1 (associativita) x, y, z X (x+ y) + z = x+ (y + z)S2 (commutativita) x, y X x+ y = y + xS3 (esitenza elemento neutro) u X : x X x+ u = xS4 (esitenza inverso) x Xx : x+ x = u

2. assiomi per loperazione prodotto

P1 (associativita) x, y, z X (x y) z = x (y z)P2 (commutativita) x, y X x y = y xP3 (esitenza elemento neutro) e X : x X x e = xP4 (esitenza inverso) x 6= u x : x x = e

3. e di un assioma che leghi il comportamento delle due operazioni, cioe che leoperazioni definite non siano del tutto indipendenti tra di loro:

Dis (distributivita) x, y, z X x (y + z) = x y + x z

Per comodita di notazione indicheremo con 0 lelemento neutro per loperazione +e con 1 quello per loperazione e indicheremo con x linverso dellelemento x perloperazione + e con x1 quello per loperazione ed abbrevieremo con x x lascrittura x+ (x).Dagli assiomi discende immediatamente che lelemento neutro per la somma e unico;supponiamo infatti che ve ne siano due u e v: risulta immediatamente dagli assiomiS3 ed S2 che u = u+v = v. Allo stesso modo si ha che linverso per la somma e unico;siano infatti x ed x due inversi per x si ha x = 0+x = (x+x)+x = x+(x+x) =x + 0 = x. Notare che lassioma S2 permette di non fare distinzioni tra inversodestro e sinistro. Avremo anche bisogno di richiedere che 1 6= 0. Proprieta analoghesi dimostrano per il prodotto.

Da questi assiomi discendono immediatamente, con dimostrazioni analoghe a quelleviste, quelle che potremmo chiamare regole di calcolo in X e che sono le usuali regolearitmetiche. Vediamone qualcuna.

3

1. x X x 0 = 0 x = 0Prova: x 0 = x (0 + 0) = x 0 + x 0 da cui x 0 = 0 2

2. (x)y = (xy) = x(y)Prova: 0 = 0 y = (x + (x))y = xy + (x)y da cui (x)y = (xy) edanalogamente a destra. 2

3. (x)(y) = xyProva: Da (2) si ha (x) y = (x y). Sempre per (2) (x) (y) =(x) (y) = x y per unicita dellopposto. 2

Analogamente a queste si ricavano tutte le altre usuali regole di calcolo: osserviamoin particolare che la regola di calcolo (1) fornisce una giustificazione del fatto chenellassioma P4 viene posta la condizione di non essere lelemento neutro per lasomma.

Un insieme dotato di due operazioni verificanti questi 9 assiomi viene detto breve-mente corpo commutativo o campo.

Avremo bisogno inoltre che sull insieme X sia definita anche una relazione di ordineche indicheremo con .Gli assiomi (le richieste) per la relazione dordine sono i seguenti

O1 (dicotomia) x, y X e vera una delle seguenti due relazioni x y o y x

O2 (riflessivita) x Xx x

O3 (antisimmetria) x y e y x x = y

O4 (transitivita)x y e y z x z

Con i seguenti due assiomi esprimiamo infine che tale relazione sia compatibile conle operazioni esistenti

14 x y x+ z y + zx, y, z X

15 x 0 e y 0 x y 0

Un insieme verificante tutti questi 15 assiomi viene detto brevemente un campoordinato. Un esempio di insieme siffatto, cioe di campo ordinato e linsieme deinumeri razionali Q.

4

Anche qui si puo verificare rapidamente che da questi assiomi si possono dedurre leusuali regole di calcolo.

Un insieme X dotato di queste propieta e una estensione di Q, nel senso che esisteuna applicazione iniettiva : Q X che rispetta la struttura, cioea, b Q

(a+ b) = (a) + (b)

(a b) = (a) (b)

a b (a) (b)

Una tale si ottiene in questo modo: facciamo corrispondere allelemento 0 Qlelemento neutro per la somma ed al numero razionale 1 lelemento neutro per ilprodotto; definiamo (n) la somma di n volte lelemento neutro per il prodottoed infine ponendo (m

n) = (m) ((n))1 si ha una estensione a tutto Q. L

applicazione cos definita e iniettiva (perche?).

Quindi in un insieme dotato di queste proprieta sappiamo ritrovare i numeri na-turali, gli interi ed i razionali. Continueremo ad indicare con la simbologia usualegli interi e i razionali anche pensati dentro X se la cosa non da adito a confusione.

Fatte queste premesse, dentro un campo ordinato completo possiamo rifare tutti gliabituali calcoli dellaritmetica elementare, per esempio risolvere equazioni e disequa-zioni lineari. Per il momento con la parola risolvere intenderemo solo descriverein modo a noi piu intelligibile il sottoinsieme descritto dalla relazione.

Vediamo su un esempio che cosa significhi: trasformiamo la descrizione di alcuniinsiemi applicando gli assiomi (si cerchi di comprendere ad ogni passaggio la sualiceita, nel senso quali assiomi ci garantiscono che i due insiemi sono uguali)

{x X|3x+1 > 4} = {x X|3x+11 > 41} = {x X|3x > 3} = {x X|x >1}Ma ancora un insieme con queste proprieta non ci basta. Infatti Q e un esempio dicampo ordinato e abbiamo gia detto che in Q non e possibile trovare un numero ilcui quadrato sia 2, cioe risolvere lequazione x2 = 2.

Mostriamolo, ripercorrendo piu o meno la prova dei greci per lincommensurabilitadella diagonale del quadrato.

Proposizione 1.1. Non esiste alcun elemento r Q tale che r2 = 2

Prova: Vogliamo provare che per nessun numero razionale mn

si ha (mn)2 = 2.

Supponiamo che al contrario cio sia vero: possiamo supporre che m,n siano primitra di loro (perche?) e quindi di diversa parita. Da m2 = 2n2 deduciamo che mnon puo esser dispari (altrimenti il suo quadrato sarebbe ancora dispari) quindi m2

e divisibile per 4, quindi anche n2 e pari e quindi anche n lo e arrivando ad unacontraddizione..

5

2

Dedekind ( 1875) riprese il punto di vista dei greci e chiese un altro assioma, oggiconosciuto come assioma di continuita o completezza.

16 Assioma di continuita. Se A e B sono due sottoinsiemi non vuoti di X conA B nel senso che a A, b B a b allora esiste in X un elemento c tale che

A c B

nel senso che a A, b B a c bUn insieme verificante tutti i 16 assiomi esposti verra detto campo ordinato com-pleto.

Assunzione: da questo momento supporremo che linsieme X sia un campo ordi-nato completo.

Mostriamo a solo titolo esemplificativo come lassioma di completezza garantiscalesistenza in un campo ordinato completo della radice di 2.

Proposizione 1.2. Sia X un campo ordinato completo. Lequazione x2 = 2 am-mette almeno una soluzione.

Prova: Indichiamo con A = {x X|x > 0 e x2 < 2} e B = {x X|x > 0 e x2 > 2}Dagli assiomi risulta che A < B nel senso che ogni elemento di A e minore di ognielemento di B e pertanto per lassioma 16 esiste un elemento separatore c in X.A c B.Quello che vogliamo provare e che c2 = 2.

Supponiamo che c2 < 2. Se posso trovare in X un > 0 tale che (c + )2 < 2 houna contraddizione perche (c+ )2 < 2 c A e > 0 c+ > c contro il fattoche ogni elemento di A e minore di c.

Il fatto che c2 < 2 implica che esiste un altro elemento X tale che c2 + < 2.Ad esempio posso prendere = 2c

2

2, in quanto c2 < 2 c2 + 2 < 4 e quindi

c2 + 2c2

2< 2.

Risulta, applicando gli assiomi,

(c+ )2 = c2 + 2c + 2 = c2 + (2c+ )

Se posso trovare < c ho

(c+ )2 = c2 + (2c+ ) < c2 + 3c

e se posso trovare un < 3c

risulta

(c+ )2 < c2 + 3c < c2 + < 2

Quindi prendendo = min{c, 3c} si ha c + A che, come abbiamo detto, e in

contraddizione con c A.

6

2

Osserviamo che se chiediamo a tale elemento di essere positivo allora non solo esistema e anche unico. Siano infatti x e y due elementi in X tali che x2 = y2 = 2

Da x2 = y2 otteniamo (x y)(x+ y) = 0 e dalla positivita di x e y otteniamo x = y.Questo ragionamento opportunamente esteso provera che in X per ogni a > 0 e nintero positivo lequazione xn = a ha soluzioni in X.

2 Alcune proprieta (importanti) di R.

Talvolta indicheremo con R un campo ordinato completo X. Tale notazione saragiustificata tra qualche paragrafo quando avremo accennato allunicita di un siffattoX che quindi potremo chiamare il campo dei reali

Proposizione 2.1. N non e limitato in R

Prova: Ragioniamo per assurdo. Sia

M = {x R|x n n N}

e supponiamo che M sia non vuoto.

Essendo ogni elemento di N minore di ogni elemento diM per lassioma di continuitaesiste un elemento c separatore.

N c M ()

Esiste quindi un numero naturale m tale che

c 1 < m c

altrimenti c 1 apparterrebbe a M .Si avrebbe pertanto c < m+ 1 in contrasto con (*) 2

Da qui discende immediatamente

Proposizione 2.2 (Proprieta di Archimede). Siano x, y X con x > 0. Esisteun intero positivo n tale che nx > y

Prova: La Proposizione 2.1 garantisce che esiste un n > yxda cui la proposizione.

2

7

Proposizione 2.3. Per ogni elemento x X esiste (unico) un intero k tale chek x < k + 1

Prova: Suppuniamo x > 0. Linsieme S = {n N| n x} e non vuoto e per laProposizione 2.1 finito. k = maxS verifica le richieste. La prova per il caso in cuix < 0 e del tutto analoga. 2

Lintero la cui esistenza e garantita da questa proposizione viene detto la parte interadi x e viene comunemente indicato con [x]; cioe si ha

[x] x < [x] + 1.Proposizione 2.4. Dato un elemento x X ed un altro elemento X positivo,esiste un numero razionale r Q X tale che

r x < r +

Prova: Per prima cosa scegliamo un naturale m, la cui esistenza e assicurata dallaProposizione 2.1, tale che m > 1

, cioe 1

m< . Per Prop.2.2 esiste un intero n tale

chen mx < n+ 1

e quindin

m x < n

m+

1

m 0 a A : a > L

Prova: La condizione 1 dice che L e un maggiorante mentre la 2 dice che ognielemento inferiore ad L non lo e.

Se L e il supA verifica banalmente le proprieta 1). Se non verificasse la proprieta2) esisterebbe un 0 > 0 tale che L 0 risulti maggiore o uguale ad ogni elementodi A in contraddizione col fatto che L e il minimo dei maggioranti.

9

Viceversa supponiamo che L verifichi le proprieta (1) e (2) della proposizione.Dobbiamo verificare che allora L e il minimo dei maggioranti di A.

Supponiamo che non lo sia cioe L 6= supA. Poiche supA e il minimo dei mag-gioranti ed L e un maggiorante si ha L supA > 0; la condizione (2) prendendo = L supA ci dice che esiste a A con a > L = L L + supA = supAcontraddicendo il fatto che supA e un maggiorante di A. 2

4 Un teorema di unicita.

Un teorema importante a questo punto e quello che ci assicura lunicita di un taleX.

Proposizione 4.1. Siano X1 e X2 due corpi ordinati completi. Allora esiste unaapplicazione biunivoca : X1 X2 che rispetta le operazioni, nel senso che

1. (x+ y) = (x) + (y)

2. (x y) = (x) (y)

3. x y (x) (y)

Lidea della prova e di costruire questa a partire dalle mappe 1 e 2 che rico-noscono Q dentro rispettivamente X1 e X2.

Q1

X1

Q

1>>~~~~~~~~

2

@@@

@@@@

@

Q2 X2

Idea della prova. Siano Q1 e Q2 i razionali in X1 e in X2, cioe i sottoinsiemi i(Q).Lapplicazione = 2 11 da Q1 a Q2 e una applicazione biunivoca che conservale operazioni e lordinamento. E possibile prolungare questa applicazione ponendoper ogni x X1 (x) = sup{(y) y Q1 y < x}. Resta da provare, e viene lasciatocome esercizio, che tale estensione e biunivoca e conserva la struttura.

Questo teorema ci garantisce che comunque noi troviamo un insieme che verificagli assiomi enunciati questo sara un modello di un tale X, insieme che dora in poichiameremo insieme dei numeri reali e che indicheremo con R

10

5 Rappresentazione decimale.

Cerchiamo di esprimere in una forma con cui poter trattare piu agevolmente i numerireali. Innanzitutto ricordiamo che dentro questo insieme R abbiamo una copia deirazionali che continuiamo a scrivere con labituale notazione m

ncon m,n Z.

Per numeri decimali intenderemo i razionali della formaa

10move a e un intero ed

m un naturale.

Osserviamo che i numeri decimali sono un sottoinsieme dei numeri razionali e chesommando o moltiplicando tra loro due numeri decimali si ottiene ancora un numerodecimale. Cioe in questo insieme si possono fare tutte le operazioni che si possonofare sui razionali salvo il fatto che in generale linverso di un decimale non nullo non edetto che sia un decimale. Quindi questo insieme con le operazioni indotte da quelledei razionali verifica tutti gli assiomi di corpo tranne lassioma P4. (Sinteticamente:non formano un campo ma una struttura diversa che viene detta anello .)

Seguendo la prova della Proposizione 2.5 possiamo provare che anche i decimali sonodensi in R: cio ci permettera fissato un n e dato un elemento x R di scegliere undecimale che meglio approssimi per difetto x a meno di 10n, nel senso che si puotrovare un m tale che m

10n x < m+1

10n.

Useremo iterativamente questa osservazione: cio legittimera in R un procedimentodel tutto analogo al procedimento pitagorico per misurare due grandezze pensandolecome lunghezze, procedendo al confronto e dividendo successivamente lintervalloresiduo in 10 parti uguali al fine di cercare un sottomultiplo comune.

Dato x R iniziamo con l individuare come fatto nella Prop 2.3 il massimo interoa0 minore o uguale a r, cioe a0 = [x]. Ponendo r0 = x a0 avremo che 0 r0 < 1.Quindi potremo pensare x = a0 + r0 e se 0 6= r0 ripetiamo il ragionamento edindichiamo con a1 il massimo intero tale che a1 10r0, quindi si avra 0 a1 9.Quindi r0 =

a1101

+ r1 con 0 r1 < 110 .Cioe

x = a0 +a1

10+ r1

con r1 K per ogni n > nK .Infatti essendo |x| > 1 posto |x| = 1 + basta prendere n in modo tale che n > K1

. Quindi se

|x| < 1, | 1x|n cresce definitivamente da cui |x|n decresce definitivamente.

16

progrssione geometrica.4 Quindi porremo

1 + x+ x2 + = 11 x se 0 x < 1

.

A questo punto e facile provare la seguente proposizione

Proposizione 8.1. Sia lespansione decimale a0, a1a2 . . .. Supponiamo che esi-sta una sequenza di cifre b1 . . . bp che a partire da un certo punto in poi si ripetacostantemente, cioe sia della forma

a0, a1 . . . ahb1 . . . bpb1 . . . bpb1 . . . bp . . .5

Allora e lespansione decimale di un numero razionale.

Useremo per un tale la notazione classica = a0, a1 . . . ahb1 . . . bp, chimandob1 . . . bp il periodo e a1 . . . ah lantiperiodo.

Dimostrazione. Una espansione decimale puo essere sempre pensata come la sommadi un intero piu una espansione decimale con a0 = 0. Pertanto dimostreremo la cosaper le espansioni del tipo 0, a1 . . . ahb1 . . . bp.

Iniziamo la prova, per semplicita, con un avente h = 0 e p = 1, cioe della forma0, b1. Dalle considerazioni fatte allinizio del capitolo, abbiamo

0, b1 =b1

10+

b1

102+ . . . =

b1

10(1 +

1

10+

1

102+ . . .) =

b1

10 11 1

10

=b1

9

Se = 0, b1b2 abbiamo

0, b1b2 =b1

10+

b2

102+

b1

103+

b2

104+ . . . =

b1

10(1 +

1

102+ . . .) +

b2

102(1 +

1

102+ . . .) =

=b1

10 11 1

102

+b2

102 11 1

102

=b1 1099

+b2

99=

b1b2

99

A questo punto dovrebbe esser chiaro come dimostrare il caso generale di unaespansione decimale periodica senza antiperiodo.

Per il caso in cui ci sia un antiperiodo, iniziamo dal caso = 0, a1b1.

0, a1b1 = 0, a1 + 0, 0b1 =a1

10+

1

10 0, b1 =

1

10(a1 +

b1

9) =

1

10(a1 9 + b1

9) =

=1

10(a1 (10 1) + b1

9) =

1

10 a1b1 a1

9=

a1b1 a190

4si tornera in seguito piu dettagliatamente su tale concetto.5in altri termini

ah+1 = b1, ah+2 = b2, . . . , ah+p = bp, ah+p+1 = b1, ah+p+2 = b2, . . . , ah+2p = bp, ah+2p+1 = b1 . . .

17

Da queste considerazioni non dovrebbe esser difficile ricavare il noto algoritmo:

La frazione generatrice di un decimale periodico e il numero razionale con al

numeratore il numero ottenuto dalle cifre di sottraendo lantiperiodo e al deno-

minatore tanti 9 quante sono le cifre del periodo seguiti da tanti zeri quante sono le

cifre dellantiperiodo.

Esercizio 8.2. 1. Caratterizzare i razionali che si rappresentano con una espan-sione decimale finita.

2. Calcolare il numero delle cifre del periodo dellespansione decimale di 17e di 1

9

3. Provare come conseguenza dellalgoritmo di divisione che lespansione decimaleche rappresenta un numero razionale e finita o periodica.

18

Complessi.

Indice

1 Definizioni. 1

2 Forma trigonometrica: argomento e funzione arcotangente. 2

3 Potenze e radici. 4

4 Polinomi e radici. 5

5 Estensione di funzioni elementari al campo complesso. 6

6 Appendice per i lettori piu interessati. 7

1 Definizioni.

In questa dispensa vogliamo presentare lestensione del campo dei numeri reali Rdata dal campo dei numeri complessi C e lestensione a tale campo di alcune funzionielementari.

Si vuole quindi un insieme che contenga R, in cui sia possibile fare delle operazionisomma e prodotto che estendano quelle definite su R e in cui sia possibile fare dellecose che in R non si possono fare, segnatamente a proposito delle radici quadratedi numeri negativi. Sara in effetti sufficiente richiedere che 1 abbia una radicequadrata.

Consideriamo come insieme, linsieme delle scritture a + ib, ove a e b sono numerireali e i un simbolo e definiamo su questo insieme due operazioni nel modo seguente

1. (a+ ib) + (c+ id) = (a+ c) + i(b+ d)

2. (a+ ib) (c+ id) = (ac bd) + i(ad+ bc)

Si osservi che con questa definizione risulta immediatamente che i i = 1, che lasomma ed il prodotto cos definiti verificano le proprieta di associativita, distribu-tivita e commutativita come le operazioni in R, che 0 + i0 (che quindi dora il poiindicheremo semplicemente con 0) e lelemento neutro per la somma e che 1 + i0(che quindi dora il poi indicheremo semplicemente con 1)e quello per il prodotto.Chiameremo C tale insieme dotato delle operazioni appena definite.

In tale insieme ritroviamo linsieme dei numeri reali come gli elementi del tipo a+i0:

si vede immediatamente che le operazioni definite inducono quelle dei reali su taleinsieme. 1

E immediato verificare che ogni elemento diverso da 0 ammette un inverso. Infattise a+ ib un elemento non nullo di C, cerchiamo se esiste un elemento x+ iy tale che(a + ib) (x + iy) = 1 + i0. Applicando la definizione otteniamo che x, y debbonoverificare le condizioni

{

ax by = 1bx+ ay = 0

Tale sistema, essendo a2 + b2 6= 0 ammette una ed una sola soluzione, data da{

x = aa2+b2

y = ba2+b2

Coniugio. Dato un numero complesso z = a + ib, si definisce numero complessoconiugato di z il numero complesso a ib e si indica con z. Il numero reale

a2 + b2

viene detto il modulo di z e lo si indica con |z|.Con tale definizione si ha

z + w = z + w

zw = z w

E di immediata verifica che

zz = |z|2

z1 =z

|z|2

Sempre di immediata verifica risulta che un numero complesso z e reale se e solo sez = z e che se z = a+ ib si ha a = z+z

2e b = zz

2iche vengono dette rispettivamente

la parte reale e la parte immaginaria del numero complesso z.

2 Forma trigonometrica: argomento e funzione

arcotangente.

Se z = a + ib e un numero complesso non nullo, i due numeri reali r1 =a

a2+b2e

r2 =b

a2+b2sono tali che r21 + r

22 = 1. Esiste pertanto un numero reale (, ]

tale che z = |z|(cos + i sin ).1In altri termini lapplicazione iniettiva da R a C definita da (r) = r+i0 rispetta le operazioni,

nel senso che (r+ r) = (r) +(r) e (r r) = (r) (r) dove i primi + e sono pensati in Red i secondi in C.

2

Tale viene detto argomento principale (talvolta fase) del numero z e lo si indicacon arg z. Linsieme dei tali che z = |z|(cos + i sin ) e un sottoinsieme di R chesi chiama argomento di z e si indica con Arg z: risulta Arg z = arg z+2k al variaredi k in Z. Pertanto il modulo e largomento di un numero complesso z verificano lerelazioni

{

|z| cos = a|z| sin = b ()

Vogliamo, partendo da queste relazioni, esplicitare per un numero complesso a+ib ilsuo modulo e il suo argomento principale in termini di a e b. Per il modulo si ricava|z| =

a2 + b2. Per ricavare largomento, osserviamo che per a 6= 0 largomento

verifica tan = ba. Si e quindi portati, al fine di esplicitare tale funzione, a risolvere

una una equazione del tipo tan = bae quindi appare naturale esprimere la funzione

argomento in termini della funzione arcotangente.

La funzione arcotangente e la funzione inversa della funzione tangente, che e unafunzione di variabile reale definita su R\{x| cos x = 0} = R\{

2+k}kxZ a valori in

R che non e iniettiva nel suo dominio di definizione e che quindi che non e invertibile.Se consideriamo la funzione tangente ristretta allintervallo (

2,

2) tale funzione e

invertibile, ma restituisce valori appunto compresi tra 2e

2mentre la funzione

arg puo assumere anche altri valori.

Pertanto ricaveremo la funzione argomento su C = C\{0} in termini della funzionearcotangente, a pezzi, cioe sui 4 quadranti e poi vedremo dove le funzioni cos definitesi rincollano.

Per i numeri complessi a+ ib del I e IV quadrante pensati aperti, senza cioe i bordi,in altri termini per i numeri con a > 0, possiamo ricavare arg z dallequazione equindi abbiamo arg(z) = arctan b

a.

Per quel che riguarda i bordi osserviamo che arg(z) =0 se z e un reale positivomentre se z e puramente immaginario, cioe se a = 0 abbiamo arg z=

2o

2a

seconda se b > 0 o b < 0. Ricordiamo che abbiamo escluso lo 0.

Passiamo al II e III quadrante. Se a < 0 poniamo arg(z)= arctan ba+ o arg(z)=

arctan ba a seconda che rispettivamente sia b > 0 (II quadrante) o b < 0 (III

quadrante).

Si osservi che, per i numeri complessi con a < 0 e b > 0, risulta

lima0

[

arctanb

a+

]

= 2+ =

2(L1)

Mentre per i numeri complessi con a < 0 e b < 0, risulta

lima0

[

arctanb

a

]

=

2 =

2(L2)

In conclusione la funzione di a e b cos definita

3

(a, b) =

arctan ba se a < 0, b < 0

2

se a = 0, b < 0

arctan ba

se a > 02

se a = 0, b > 0

arctan ba+ se a < 0, b > 0

se a < 0, b = 0

(1)

e definita su tutti i punti di C: tale funzione e costante lungo le semirette che

escono in direzione radiale dallorigine perche (z) =(

z|z|

)

, e (L1) e (L2) provano

che e continua in tutti i punti di C \ {x < 0, y = 0}. Tale funzione coincide con lafunzione arg(z). 2

Ad esempio se z = 2

2+ i

2

2abbiamo che |z| = 1 e quindi{

cos =

22

sin =

22

da cui tan = 1 che, via le definizioni date, porta a dire che arg(

2

2+ i

2

2

)

=

3

4.

3 Potenze e radici.

Utilizzando la forma trigonometrica, vediamo il significato della moltiplicazione didue numeri complessi.

Se z = (cos + i sin) e w = (cos + i sin ), risulta zw = (cos( + ) +i sin(+ )).

Da questa osservazione ricaviamo subito la formula per la potenza di un numerocomplesso

zn = n(cosn + i sinn)

da cui la formula per le radici n-esime di un numero complesso:

n

(

cos+ 2k

n+ i sin

+ 2k

n

)

(+)

Osserviamo che le radici n-esime di un numero complesso sono n, poiche in (+) nsono i termini che non differiscono per un multiplo di 2.

2Attenzione: pur essendo vero che se 6= 0, tan ba

= tan ba, (a, b) 6= (a, b) se < 0

4

4 Polinomi e radici.

Indichiamo con R[x] linsieme dei polinomi p(x) in una variabile a coefficienti reali,cioe linsieme delle scritture a0 + a1x+ . . .+ anx

n, in cui penseremo definite le ope-razioni di addizione, moltiplicazione tra polinomi e moltiplicazione di un polinomioper un numero reale.

In questo insieme si puo operare la divisione euclidea .

Teorema 4.1. Dati due polinomi a e b con deg a = n e deg b = m, esistono unicidue polinomi q ed r con deg r < deg b tali che a = bq + r.

Lesistenza e data dallalgoritmo di divisione per polinomi appreso nella scuola se-condaria e lunicita sui ottiene dalla condizione deg r < deg b; infatti se q e r sonoaltri due polinomi che verificano la stessa relazione si ha

0 = b(q q) + (r r)ed essendo deg(r r) < deg b si deve avere q q = 0 e di conseguenza r r = 0.Conseguentemente se p ammette come radice, cioe se p() = 0, si ha, dividendoil polinomio p per il polinomio x ,

p(x) = (x )q(x) + r(x)

Poiche deg r < deg(x ) = 1, il polinomio r e una costante e calcolando questaespressione in , si ha che r() = 0 che implica che tale costante e 0. Quindi se e una radice del polinomio p, il polinomio e divisibile per x , da cui deduciamoche un polinomio p puo avere al massimo n = deg p radici.

Iterando questo procedimento abbiamo che in un ambiente ove il polinomio p am-mette tutte le sue radici 1, 2, . . . , h, il polinomio puo scriversi nella forma

p(x) = (x 1)m1(x 2)m2 (x h)mh .

Se p e un polinomio a coefficienti reali una osservazione importante e la seguente:

Teorema 4.2. Se C e una radice del polinomio a coefficienti reali p anche loe.

Questo segue dalle proprieta del coniugio. Infatti se p(x) =n

i=1 aixi si ha

p() =n

i=1

aii =n

i=1

aii =n

i=1

aii =n

i=1

ai i =

n

i=1

ai i = p()

da cui p() = p() = 0.

5

Il teorema fondamentale dellalgebra,3 che qui assumiamo senza prova, implica cheogni polinomio a coefficienti reali assume tutte le sue radici in C, per cui per unpolinomio a coefficienti reali vale il teorema

Teorema 4.3. Ogni polinomio a coefficienti reali ammette in R[x] una decomposi-zione

p(x) = (x a1)m1(x a2)m2 (x ah)mhqn11 qn22 qnkk

ove i polinomi qi sono polinomi di secondo grado senza radici reali.

Gli interi mi vengono dette le molteplicita delle radici ai.

I fattori di tipo x ai seguono direttamente da quanto detto e quelli di tipo qi siottengono accorpando i fattori coniugati, tenedo conto del fatto che se un polinomioreale ammette una radice complessa ammette anche la coniugata e che (x a)(xa) = x2 2(a+ a)x+ aa e un polinomio a coefficienti reali.Ad esempio x4+1 = (x2+

2x+1)(x2

2x+1). Per ottenere questa decomposizione

basta calcolare con la formula di De Moivre le radici quarte di 1 e poi accorparle.Una ultima osservazione.

Dato un polinomio p di grado n in C indichiamo con con a1, a2, . . . , an le sue radicitrascurando il fatto che alcune di esse possano coincidere.

Il polinomio q(x) = (x a1)(x a2) . . . (x an) e un polinomio monico (cioe concoefficiente direttore uguale a 1) di grado n che differisce dal polinomio dato per unfattore costante (perche?).

Indicando con i i coefficienti del polinomio q, cioe q(x) = xn + 1x

n1 + . . . +n1x

1 + n, ed operando un calcolo, si mostra che i i sono le somme di tutti iprodotti a i a i delle ai

4.

Conseguenza immediata di questa osservazione e che la somma delle radici n-esimedellunita vale 0.

5 Estensione di funzioni elementari al campo com-

plesso.

Vogliamo definire su C una funzione che estenda la funzione esponenziale ex definitasu R: indicheremo tale estensione con ez.

Per far questo poniamo, se z = x+ iy

ez = ex(cos y + i sin y)

3Il teorema fondamentale dellalgebra dice che ogni polinomio di grado positivo a coefficenticomplessi ha almeno una radice (e quindi tutte) in C.

4In letteratura le i vengono dette le funzioni simmetriche elementari degli ai.

6

Si vede immediatamente che questa definizione 5 ristretta ai reali coincide con lafunzione esponenziale ex e che per la funzione ez valgono le usuali proprieta dellafunzione esponenziale, come, ad esempio che ez++w = ez ew etc.Notiamo che, sempre da questa definizione, risulta

x, y ex+iy = ex+i(y+2k)

cioe che la funzione esponenziale complessa e una funzione periodica di periodo 2i.

Notiamo infine che tale espressione puo essere usata per estendere al campo com-plesso le funzioni trigonometriche elementari seno e coseno.

Tale espressione per lesponenziale puo essere usata anche per estendere al campocomplesso le funzioni trigonometriche elementari seno e coseno.

Infatti sempre da () risulta che per ogni x reale si ha

cos x =eix + eix

2

sin x =eix eix

2i

Quindi, partendo da queste espressioni, si puo definire per z complesso

cos z =eiz + eiz

2

sin z =eiz eiz

2i.

6 Appendice per i lettori piu interessati.

In questo paragrafo vogliamo provare che la funzione definita in questo modo ve-rifica in campo complesso unaltra proprieta della funzione esponenziale reale e

precisamente quella che, se x e un numero reale allora limn

(

1 +x

n

)n

= ex.

Pertanto, se z e un numero complesso, proveremo che 6 ez = limn

(

1 +z

n

)n

provando

chelimn

(

1 +z

n

)n

= ex(cos y + i sin y) ()

Indichiamo, per brevita, con an la successsione 1 +zn

che, pensandola in formatrigonometrica, scriveremo come an = |an| (cos n + i sin n).

5Questa relazione ed altre analoghe sono conosciute come relazioni di Eulero6La definizione di limite per una successione {an} di numeri complessi e del tutto analoga a

quella del caso reale: L = limn

an se per ogni > 0 esiste un n0 tale che per ogni n > n0 risulta

|an L| < .

7

Pertanto risulta

(an)n =

(

1 +z

n

)n

=

[

(

1 +x

n

)2

+(y

n

)2]

n2

(cosn + i sinn)

Poiche

|(an)n| =[

(

1 +x

n

)2

+(y

n

)2]

n2

=(

1 +x

n

)n

[

1 +

(

y

x+ n

)2]

n2

=

=(

1 +x

n

)n

[

1 +

(

y

x+ n

)2](x+ny )

2

ny2

2(x+n)2

si halimn

|(an)n| = ex

Per calcolare limn

nn osserviamo innanzitutto che per ogni z si ha limn

an = 1 e

quindi definitivamente, cioe per tutti gli n maggiori di un n0 (che dipende anche daz) si ha che |arg an| < 2 . Pertanto per tali n si ha che arg an = arctan

y

x+ne quindi

definitivamente n = arctany

x+n.

Ricordando che limx0

arctanx

x= 1 7, si ha

limn

nn = limn

n arctany

x+ n= lim

nn

(

y

x+ n

)(

x+ n

y

)

arctany

x+ n

= limn

ny

x+ n

arctan yx+n

y

x+n

= y

7In un intorno di 0 si ha limx0

arctanx

x= lim

t0

t

tan t= lim

t0

t

sin tcos t = 1

8

September 30, 2014

PRINCIPIO DI INDUZIONE

Linsieme dei numeri naturali N e bene ordinato; questo significa che il familiare ordinamento deinumeri naturali tale che per ogni n N, n n + 1 (in effetti n < n + 1), verifica le seguenti dueproprieta:

(1) E un ordinamento totale, cioe due arbitrari numeri naturali sono sempre confrontabili, pre-cisamente: dati arbitrariamente due numeri n,m N si ha che n m o m n.

(2) Dato comunque un sottoinsieme A N non vuoto, esso ha un elemento minimo a (necessari-amente unico), cioe a A e per ogni b A si ha che a b.

Questa proprieta fondamentale dei numeri naturali e alla base del cosidetto principio di induzioneche qui descriviamo in termini delle sue principali applicazioni: le dimostrazioni per induzione, ladefinizione di funzioni per induzione.

Dimostrazioni per induzione. Sia n0 N un fissato numero naturale. Supponiamo che P (n) siaunaffermazione che dipende da un parametro n N, ha senso per ogni naturale n n0 e che puoessere vera o falsa. Ad esempio consideriamo:

n0 = 1, P (n) := 2n n .

Supponiamo di essere interessati a dimostrare che P (n) e vera per ogni n n0. In certi casi questopuo essere fatto per induzione applicando lo schema seguente:

Passo iniziale: Si verifica che P (n0) e vera.

Passo induttivo: Per ogni n n0, si dimostra che se P (n) e vera, allora anche P (n+ 1) e vera.

Se riusciamo a realizzare questi due passi, allora possiamo concludere che effettivamente P (n) e veraper ogni n n0.

Infatti, intuitivamente, P (n0) e vera per il passo iniziale, allora P (n0 + 1), P ((n0 + 1) + 1), ,sono tutte vere a cascata, luna di seguito allaltra, applicando ripetutamente infinite volte il passoinduttivo. Vedremo poi piu rigorosamente come questa conclusione segua dal buon ordinamento di N.

Definizione di funzioni per induzione. Sia n0 N un fissato numero naturale. Una funzione

f : {n N|n n0} X

(a valori in qualche insieme X) e definita per induzione se e ottenuta applicando il seguente schema:

Valore iniziale: Assegnamo il valore f(n0).

Passo induttivo: Per ogni n n0, il valore f(n + 1) e completamente specificato in termini delvalore f(n).

In questo modo la funzione f(n) e effettivamente definita per ogni n n0. Come prima il valoreiniziale f(n0) e assegnato, i valori f(n0 + 1), f((n0 + 1) + 1), , sono tutti definiti a cascataapplicando di seguito infinite volte il passo induttivo.

Vediamo alcuni esempi di entrambe le procedure. Cominciamo trattando per induzione lesempioconsiderato prima:n0 = 1, 2

n n.

Passo iniziale: P (1) := 21 = 2 1 che e vera.

Passo induttivo Per ogni n 1, vogliamo dimostrare che 2n+1 n + 1 assumendo di sapere che2n n. Infatti:

2n+1 = 2(2n) 2n n+ 1

dove lultima disuguaglianza vale perche n 1. Dunque possiamo concludere che 2n n per ognin 1.

1

2 PRINCIPIO DI INDUZIONE

Osservazione. In effetti 20 = 1 0, dunque laffermazione e vera anche per n = 0. Pero, se avessimopreso n0 = 0 invece che n0 = 1, la precedente discussione del passo induttivo NON avrebbe funzionatoper tutti gli n n0 = 0 (2n n+ 1 non e vera se n = 0); quindi quella dimostrazione per induzionenon avrebbe funzionato per n0 = 0.

Esempio 1. n0 = 1. Definiamo per induzione

f : {n N| n 1} N

come segue:

- Valore iniziale: f(1) = 1.- Passo induttivo: per ogni n 1, f(n+ 1) = f(n) + (n+ 1).

Calcoliamo alcuni valori della funzione cos definita:

f(1) = 1, f(2) = 1 + 2, f(3) = 1 + 2 + 3, . . . , f(n) = 1 + 2 + + n, . . . .

Quindi, a parole, f(n) e uguale alla somma dei primi n numeri naturali diversi da zero. La definizioneper induzione permette di dare un significato preciso ai puntolini nellespressione f(n) = 1 + 2 + + n. Consideriamo ora la funzione

g : {n N| n 1} N

g(n) =n(n+ 1)

2Vogliamo dimostrare per induzione che g = f , cioe g(n) = f(n) per ogni n 1. Infatti:

- Passo iniziale: g(1) = 1 = f(1).

- Passo induttivo: f(n+1) = f(n)+(n+1) = g(n)+(n+1) =n(n+ 1) + 2(n+ 1)

2=

(n+ 1)(n+ 2)

2=

g(n+ 1).

Osservazione. Un altro modo per dimostrare luguaglianza delle due funzioni, che spiega come lafunzione g sia emersa, e il seguente: 2f(n) = (1+ +n)+(n+ +1) = (n+1)+ (1+n) = n(n+1).

Esempio 2. n0 = 1, f(1) = 1, f(n + 1) = f(n)(n + 1). Si reallizza che per ogni n 1, f(n) =1 2 3 n, cioe il prodotto dei numeri naturali compresi tra 1 e n. E una funzione importante. Lasua notazione corrente e f(n) = n!, si legge n-fattoriale e viene estesa anche in 0, ponendo 0! = 1.

Esempio 3. n0 = 1, f(0) = 1, f(n + 1) = f(n) + (n + 1)2. Si puo riformulare usando il simbolo di

sommatoria:

f(n) =n

i=1

i2 = 1 + 22 + + n2 .

Dimostriamo per induzione che per ogni n 1,

f(n) = g(n) :=n(n+ 1)(2n+ 1)

6.

Passo iniziale: f(1) = 1 = (2 3)/6 = g(1).Passo induttivo:

f(n+ 1) = f(n) + (n+ 1)2 = n(n+ 1)(2n+ 1)/6 + (n+ 1)2 =

(n+ 1)(2n2 + 7n+ 6)/6 = (n+ 1)(n+ 2)(2n+ 3)/6 = g(n+ 1) .

Esempio 4. Fissiamo un numero a 6= 1; n0 = 1; f(1) = a0 = 1; f(n + 1) = f(n) + an. Quindi, per

ogni n 1,

f(n) =

n

i=0

ai = 1 + a2 + + an .

Dimostriamo per induzione che per ogni n 1

f(n) = g(n) :=an+1 1

a 1.

PRINCIPIO DI INDUZIONE 3

Passo iniziale: f(1) = 1 =a1 1

a 1= g(1).

Passo induttivo:

f(n+ 1) = f(n) + an+1 =an+1 1

a 1+ an+1 =

an+2 1

a 1= g(n+ 1) .

Osservazione. Il risultato precedente si puo ottenere in modo leggermente diverso. Il numero 1 e unaradice del polinomio p(X) = Xn+1 1 (cioe p(1) = 0). Dunque p(X) e divisibile per X 1 e facendola divisione tra polinomi (con resto uguale a zero) si ottiene (anche qui procedendo per induzione):

Xn+1 1 = (X 1)(1 +X +X2 + +Xn) .

Dunque sostituendo un numero a arbitrario (anche a = 1), si ha che

an+1 1 = (a 1)(1 + a+ a2 + + an) .

Se a 6= 1 possiamo dividere per a 1 ottenendo lidentita voluta.

Esempio 5. (Disuguaglianza di Bernoulli) Fissiamo un numero x 1. Vogliamo dimostrare cheper ogni n 0,

(1 + x)n 1 + nx .

Procediamo per induzione.Passo iniziale: (1 + x)0 = 1 1 = 1 + 0x.Passo induttivo:

(1 + x)n+1 = (1 + x)n(1 + x) (1 + nx)(1 + x) = 1 + (n+ 1)x+ nx2 1 + (n+ 1)x .

Si osservi che per la prima disuguaglianza non abbiamo usato soltanto che (1 + x)n 1 + nx, maanche che 1 + x 0 (lipotesi x 1). Infatti per esempio la disuguaglianza non vale se prendiamox = 100, n = 2.

Concludiamo facendo vedere, come promesso, che il principio di induzione e una conseguenza delbuon ordinamento di N. Facciamolo nel caso delle dimostrazioni per induzione, per le funzioni definiteper induzione largomento e lo stesso. Nelle ipotesi date, supponiamo di avere verificato i due passi(iniziale e induttivo). Vogliamo allora concludere che laffermazione e vera per ogni n n0. Vogliamocioe dimostrare che linsieme

A = {n n0|P (n) falsa} N

e vuoto. Supponiamo invece per assurdo che non sia vuoto (cioe esiste n n0 tale che P (n) e falsa).Allora, per il buon ordinamento di N, A ammette un elemento minimo a. Poiche P (n0) e vera (passoiniziale), allora a > n0. Quindi a 1 n0 e P (a 1) e vera (perche a e lelemento minimo di A). Peril passo induttivo anche P (a) = P ((a 1) + 1) e vera, ma P (a) e anche falsa perche a A. Questoassurdo dimostra come volevamo che A e vuoto.

October 28, 2014

SUCCESSIONI

In questa dispensa faremo riferimento a nozioni relative alla retta estesa R e ai sistemi di intorni diogni a R che sono definite nella dispensa [TOP].

1. Nozioni generali

Dato un insieme non vuoto X , una successione a valori in X e una funzione della forma:

a : {n N| n n0} X

dove n0 N e un fissato numero naturale. Per semplicita scriveremo {n n0} invece di {n N| n n0}; inoltre, di solito, per ogni n n0, scriveremo an invece di a(n). Ogni an X e detto un terminedella successione, linsieme dei termini e un sottoinsieme di X , infatti non e altro che limmagine dellafunzione a:

Im(a) = {an X | n n0} .

Una successione a e costante se Im(a) = {b} cioe consiste di un solo elemento, cioe per ogni n n0,an = b. E utile fissare la seguente nozione generale:

Successioni che verificano definitivamente una proprieta. Sia a : {n n0} X una suc-cessione. Diciamo che essa verifica definitivamente una certa proprieta P se esiste n N, n n0tale che per ogni n > n, an verifica la proprieta P . Cioe la proprieta puo non valere per un numeroarbitrariamente grande di indici n, ma da un certo indice in poi vale sempre.Ad esempio:- Si consideri la successione a : N N, an = n per ogni n 0. Allora la successione a verificadefinitivamente la proprieta an > 5 (basta prendere as esempio n = 7). Invece a non verificadefinitivamente la proprieta : an e pari. Infatti per ogni n N, n + 2 > n + 1 > n e almeno unotra n + 2 e n + 1 non e pari. Si noti che an e pari per un insieme infinito di indici n; in casi cos sidice a volte che la proprieta e verificata frequentemente, ma questo non basta affinche la proprieta siaverificata definitivamente.

- Una successione a e definitivamente costante se esiste n n0 tale che per ogni m,n > n, an = am.Per esempio la successione a : N N tale che an = min(n, 700) e definitivamente costante, infatti perogni n > 699, an = 700.

2. Successioni di numeri reali

Enunceremo in modo esauriente diverse nozioni e proprieta relative alle successioni di numeri reali.Non le dimostreremo tutte, ma di tutte potremo fare liberamente uso.

Noi saremo particolarmente interessati al caso di successioni di numeri reali, cioe quando X = R. Inquesto caso e conveniente introdurre alcune nozioni che sono definite usando le proprieta di R. Sia

a : {n n0} R

una successione di numeri reali.

La successione a e superiormente (risp. inferiormente) limitata se esiste M R tale che perogni n n0, an M (risp. an M).

La successione a e limitata se e contemporaneamente superiormente e inferiormente limitata. La successione a e crescente (risp. decrescente) se per ogni n,m {n n0}, se n > m alloraan > am (risp. an < am). Una successione e detta strettamente monotona se e crescente odecrescente.

La successione a e non decrescente (risp. non crescente) se per ogni n,m {n n0}, sen > m allora an am (risp. an am). Una successione e detta monotona se e non crescenteo non decrescente.

1

2 SUCCESSIONI

Attenzione. Questa terminologia, benche largamente diffusa, puo essere un po fuorviante.Per esempio la definizione data di successione non crescente NON e la negazione delladefinizione di successione crescente data prima; infatti tale negazione e:

Esistono n,m n0 tali che n > m e an am.

3. Limiti di successioni

Data una successione

a : {n n0} R

dato un elemento della retta estesa L R = R {,+} vogliamo dare un senso alla scrittura

L = limn+

an

che leggeremo:

L R e limite della successione an quando n tende allinfinito.

A volte useremo anche la notazione abbreviata

an L

che leggeremo an tende a L per n che tende allinfinito.

Definizione sintetica del limite di una successione. Ricordiamo che per ogni L R, nelladispensa [TOP] abbiamo definito un sistema di intorni aperti di L. Allora:

limn+

an = L

se per ogni U elemento del sistema di intorni di L, an appartiene definitivamente ad U .

Adesso facciamo lesercizio di esplicitare completamente in modo analitico questa definizione sintetica,distinguendo i casi in cui L R oppure L = .

Supponiamo che il valore limite L R. In questo caso il sistema di intorni di L e formato dagliintervalli I(L, ) di centro L e raggio , dove varia nei numeri reali strettamente positivi. Alloraabbiamo:

limn+

an = L R

se e solo se per ogni > 0, esiste n n0 tale che per ogni n > n, an I(L, ) (cioe, equivalentemente,L < an < L+ ).

Supponiamo che L = + ; In questo caso gli intorni di + sono le semirette (m,+), con m chevaria in R. Allora abbiamo: lim

n+an = + se e solo se per ogni numero reale m , esiste n n0 tale

che per ogni n > n, an (m,+) (cioe an > m).

Supponiamo che L = ; in questo caso gli intorni di sono le semirette (,m), con m chevaria in R. Allora abbiamo:

limn+

an =

se per ogni numero reale m, esiste n n0 tale che per ogni n > n, an (,m) (cioe an < m).

Se esiste L R tale chelim

n+an = L

diremo che la successione e convergente (in R) o anche che e regolare. Se un tale L non esiste diremoche la successione e irregolare.

Esempi

(1) Sia an = n, definita per n 0. Allora an +. Infatti, per ogni reale m esiste n N tale chen > m (proprieta di Archimede), quindi per ogni n > n si ha che n = an > m.

SUCCESSIONI 3

(2) Sia an = min(n, 700), definita per n 0. Allora an 700. Infatti, per ogni > 0, sia n = 699.Allora per ogni n > n, an = 700 I(700, ). In generale ogni successione definitivamente costante euguale a L R tende a L per n che tende a infinito.

(3) Sia an = 1/n, definita per n 1. Allora an 0. Infatti per ogni > 0, 1/n = |1/n| < se e solose n > 1/. Per la proprieta di Archimede, esiste n > 1/, e per ogni n > n, 1/n = |1/n| < 1/n < .Dunque an appartiene definitivamente a I(0, ).

(4) La successione an = (1)n, definita per n 0 e irregolare. Infatti L = non e valore limite

perche la successione e limitata. Supponiamo che L R. Sia = min(2 = | 1 1|, |1 L|, |1 +L|). Poniamo = /3. Allora an appartiene frequentemente a I(1, ) e a I(1, ), quindi non puoappartenere definitivamente a I(L, ) e nessun L puo essere valore limite di an.

3.1. Proprieta dei limiti di successioni. Discutiamo alcune proprieta che sono conseguenza delladefinizione di limite.

Unicita del limite. Data una successione a : {n n0} R, se L R e tale che

L = limn+

an,

allora L e lunico valore limite di an in R. Pertanto scriveremo anche limn+

an = L intendendo che

L e il limite della successione per n che tende allinfinito.

Infatti, supponiamo per esempio che L R e facciamo vedere che non esiste un antro limite L R.Infatti sia = |L L|/3 per cui I(L, ) I(L, ) = . Allora an non puo stare definitivamente inentrambi gli intorni I(L, ) e I(L, ). Facciamo vedere che neanche L = + puo essere limite dellasuccessione. Infatti, fissiamo > 0 e poniamo M = L + 3. Allora I(L, ) (M,+) = e ancorauna volta an non puo stare definitivamente in entrambi gli intorni. Gli altri casi per cui L = sitrattano in modo simile .

Permanenza del segno.

Se limn+

an = L R e L 6= 0, allora an ha definitivamente lo stesso segno di L (dove conveniamo

che + > 0 e < 0).

Infatti, supponiamo per esempio che L R e L > 0. Poniamo = L/3. Se x I(L, ), allora x > 0 ean appartiene definitivamente a I(L, ). Gli altri casi si trattano in modo simile.

Sottosuccessioni. Data una successione

a : {n n0} R

una sottosuccessione di a (detta anche una successione estratta da a) e una successione

b : N R

tale che esiste una successione crescente

j : N {n n0}

per cui b risulta essere la composizione

b = a j .

I termini della successione b vengono spesso indicati ajn , n N, dove jn = j(n). Ad esempio se an = ne j(n) = 2n, allora ajn = 2n, cioe la sottosuccesione e formata dai termini pari di a. Se an = (1)

n,e j(n) = 2n, allora ajn e la successione costante uguale a 1.

Se an L R e ajn e una sottosuccessione di a, allora ajn L. In altre parole: una sottosuccessionedi una successione convergente e a sua volta convergente e le due successioni hanno lo stesso limite.

Infatti, dato un intorno U di L, sia n n0 tale che per ogni n > n, an U . Poiche j e crescente,esiste n1 > 0 tale che j(n1) > n. Quindi per ogni n > n1, ajn U .

Attenzione, una successione irregolare (per esempio an = (1)n) puo avere sottosuccessioni conver-

genti (per esempio la successione costante (1)2n = 1).

4 SUCCESSIONI

Proprieta algebriche dei limiti. Sono familiari le operazioni di somma e prodotto su R. Inoltrese a R, a 6= 0 e definito linverso 1/a R. Prima di enunciare le proprieta algebriche dei limiti disuccessioni, estendiamo parzialmente queste nozioni alla retta estesa nel modo seguente:

Se a R o a = +, poniamo ++ a = a++ = +. Se a R o a = , poniamo + a = a+ = . Poniamo (+) (+) = +, () () = +, () (+) = (+) () = . Se a R, a > 0, poniamo a () = () a = . Se a < 0, poniamo a () =() a = .

Poniamo 1/ = 0.

Attenzione: NON abbiamo definito () + (), 0 (), () 0. Queste sono dette formeindeterminate. Anche / (dove i due simboli possomo prendere indipendentemente i valori), e una forma indeterminata perche possiamo scrivere / = (1/) = 0 e ricondursicos ad una forma indeterminata gia vista.

Possiamo adesso enunciare alcune proprieta algebriche dei limiti di successioni.

(1) (Limite di una somma di successioni.) Siano a, b : {n n0} R due successioni.Supponiamo che

limn+

an = L R

limn+

bn = L R

e che L+ L e definito (cioe non e una forma indeterminata). Allora

limn+

(an + bn) = L+ L R .

(2) (Limite di un prodotto di successioni.) Siano a, b : {n n0} R due successioni.Supponiamo che

limn+

an = L R

limn+

bn = L R

e che L L e definito (cioe non e una forma indeterminata). Allora

limn+

(an bn) = L L R .

(3) (Limite della successione degli inversi.) Sia a : {n n0} R una successione esupponiamo che per ogni n n0, an 6= 0. Supponiamo che

limn+

an = L R

e che 1/L sia stato definito qui sopra. Allora

limn+

1/an = 1/L R .

(4) Nella situazione del punto precedente, supponiamo che L = 0. In generale non possiamo dire

niente sulla convergenza della successione 1/an. Per esempio sia an =(1)n

n, definita per ogni

n 1. Allora limn+

an = 0 (verificarlo per esercizio usando direttamente la definizione di

limite), mentre la successione 1/an = (1)nn e irregolare. Possiamo dire qualcosa se facciamo

un ipotesi piu forte, supponiamo cioe che tutti i termini an abbiano definitivamente lo stessosegno + o (scriveremo che an 0

). Allora

limn+

1/an = .

In particolarelim

n+1/|an| = + .

In altre parole non abbiamo definito 1/0, ma abbiamo definito 1/0 = , e in questo modopossiamo unificare questi due ultimi punti (3) e (4).

SUCCESSIONI 5

A titolo di esempio dimostriamo laffermazione sul limite della somma nel caso in cui L,L R.Fissiamo > 0, vogliamo dimostrare che (an + bn) appartiene definitivamente allintorno I(L+L

, ).Se an appartiene definitivamente a I(L, 1) e bn appartiene definitivamente a I(L

, 2) allora an + bnappartiene definitivamente I(L+ L, 1 + 2), perche definitivamente:

|(L+ L) (an + bn)| |L an|+ |L bn| < 1 + 2 .

Per concludere basta prendere per esempio 1 = 2 = /3.

Esempi. I seguenti limiti si ottengono applicando diverse tra le proprieta algebriche viste sopra (peresercizio dettagliare quali).

(1) Per ogni fissato k N, k > 0, alloraan := nk +; se invece k < 0, allora an := n

k 0.

(2) Fissati numeri reali a, b, c, d, c 6= 0, allora an :=an+ b

cn+ d

a

c.

(3) Sia an = nm +

m1

j=0

cjnj , dove i numeri reali cj sono certi coefficienti fissi. Possiamo riscrivere

an = nm(1 +

m1

j=0

cj(1/nmj). Si ha che an +.

Confronto di successioni. In certi casi si possono ricavare informazioni sulla convergenza di unasuccessione confrontandola con altre successioni di cui il comportamento sia noto.

Confronto 0. Due successioni che sono definitivamente uguali hanno lo stesso comportamento pern +, cioe luna converge se e solo se laltra convege e se sono convergenti allora hanno lo stessolimite L R. Questo e chiaro perche la definizione di limite usa solo proprieta che devono valeredefinitivamente.

Confronto 1. Siano a : {n n0} R e b : {n n1} R due successioni. Supponiamo che

limn+

bn = +

e che definitivamente an bn. Allora

limn+

an = + .

Analogamente se

limn+

bn =

e definitivamente an bn. Allora

limn+

an = .

Confronto 2. Siano a,b,c tre successioni. Supponiamo che:

1) limn+

an = limn+

bn = L R;

2) Definitivamente an cn bn.

Allora:

limn+

cn = L .

Questo risultato e anche noto come teorema dei carabinieri (a e b) che tenendo dai due lati il ladro(c) lo portano con loro in prigione (L).

Esempi.

(1) Fissato un reale a > 1, allora an := an +. Infatti possiamo scrivere a = 1 + b, b > 0.

Sappiamo (Bernoulli) che an = (1 + b)n 1 + bn. Poiche 1 + bn +, lo stesso vale per an.

(2) Come in (1) ma supponendo ora 0 < |a| < 1. Ne segue che 1/|a| > 1, quindi |an| = 1/(1/|a|)n 0.

6 SUCCESSIONI

(3) Fissato come prima a > 1, allora a1/n 1. Infatti possiamo porre a1/n = 1 + bn con bn > 0.Allora (Bernoulli) a = (1 + bn)

n 1 + nbn, da cui 0 < bn (a 1)/n. Per i carabinieri bn 0 e

quindi a1/n 1.

(4) Fissato a, |a| 1, allora an/n 0. Infatti se |a| < 1, an 0 e quindi an/n 0. Se |a| = 1, siha che 0 |an/n| 1/n. Per i carabinieri, an/n 0.

(5) Come in (4) ma supponendo ora che a > 1. Allora a = 1 + d per qualche d > 0.

an = (1 + d)n =

n

k=0

(

n

k

)

dk

(

n

2

)

d2 = n(n 1)d2/2

da cuian/n (n 1)d2/2 ;

poiche (n 1)d2/2 +, lo stesso vale per an/n.

Convergenza delle successioni monotone.

Le successioni monotone sono sempre regolari cioe ammettono sempre limite L R.

Infatti, supponiamo che la successione an, definita per n n0, sia non decrescente (risp. non cres-cente). Allora si hanno due possibilita

1) an e superiormente (risp. inferiormente) limitata con estremo superiore (risp. inferiore) L =sup{an| n n0} R (risp. L = inf{an| n n0} R) . Allora

limn+

an = L

2) an non e superiormente (risp. inferiormente) limitata. Allora: limn+

an = + (risp. limn+

an =

).

Dimostriamo per esempio la prima affermazione nel caso in cui la successione e non decrescente esuperiormente limitata. Per le proprieta dellestremo superiore, per ogni > 0 esiste n n0 tale chean > L . Siccome la successione e non decrescente, per ogni n > n, an an, quindi an > L , dacui an I(L, ). Gli altri casi si trattano in modo analogo.

Esempio importante: il numero di Nepero. Consideriamo la successione an = (1+1

n)n definita

per n 1. Dimostriamo intanto che e una successione crescente. Infatti

an =

n

h=0

(

n

h

)

1

nh=

n

h=0

1

h!

n(n 1)(n 2) (n h 1)

nh

da cui, riorganizzando lultimo termine

an =

n

h=0

1

h!(1

1

n)(1

2

n) (1

h 1

n) .

Se ora ripetiamo il calcolo per an+1 vediamo che ognuno dei termini (che sono positivi) della sommaal secondo membro non diminuisce e il numero di termini aument