logica matematica (155)

7/31/2019 logica matematica (155)

1/155

Appunt i da l l e l ezion i de l co rso d i

LOGICA MA TEMAT ICAp e r s t u d e n t i d i I n fo r m a t i c a

a cura di A. Labella e G.T. Bagni

Roma, 2002


2/155

2

Il frontespizio di unedizione di De Coelo e De Mundo di Aristotelecon i commenti di Jandun stampata a Venezia nel 1589

__________


3/155

3

Indice

Parte prima Insiemi e funzioni p. 7 1. Teoria degli insiemi

1.1. Insiemi1.2. Sottoinsiemi e inclusione1.3. Operazioni con gli insiemi: unione,

intersezione, differenza1.4. Il prodotto cartesiano di due insiemi

2. Relazioni e propriet2.1. Sottoinsiemi del prodotto cartesiano2.2. Relazioni tra un insieme e se stesso

e loro propriet2.3. Relazioni di equivalenza e insieme quoziente2.4. Relazioni dordine2.5. Relazioni dordine totale e dordine parziale

3. Funzioni3.1. La definizione di funzione3.2. Funzioni iniettive, suriettive, biiettive

4. Funzioni composte e funzioni inverse4.1. La funzione composta4.2. Lapplicazione della definizione di funzione

composta4.3. Il dominio della funzione composta4.4. La funzione identit4.5. La relazione inversa

5. Cenni sulle antinomie della teoria degli insiemi


4/155

4

5.1. Le antinomie5.2. Gottlob Frege e Bertrand Russell

Parte seconda Numeri naturali p. 39 6. Linsieme dei numeri naturali

6.1. I numeri naturali: approccio cardinale6.2. I numeri naturali: approccio ordinale6.3. La rappresentazione dei numeri naturali6.4. Propriet di operazioni aritmetiche

e insiemistiche: lalgebra di Boole7. Dimostrazioni per induzione

7.1. Proposizioni dipendenti da un naturale7.2. Dimostrazioni per induzione

8. I numeri primi8.1. Divisibilit e numeri primi8.2. La scomposizione in fattori primi8.3. Quanti sono i numeri primi?8.4. Condizioni di primalit

9. Confronto di insiemi infiniti9.1. La potenza del numerabile9.2. La potenza del continuo

Parte terza Logica degli enunciati p. 71 10. Enunciati, connettivi, valori di verit

10.1. Verit10.2. Enunciati10.3. Connettivi e valori di verit10.4. Interpretazioni, equivalenze logiche, validit

11. Il metodo dei tableaux proposizionali11.1. La confutazione di un enunciato composto11.2. La costruzione di un tableau proposizionale

11.3. Correttezza e completezza12. Il sistema di Gentzen

12.1. Il sistema deduttivo di Gentzen12.2. Deduzione di Gentzen e tableau

13. Cenni sul sistema di Hilbert 13.1. Il sistema di Hilbert


5/155

5

13.2. Regole derivate del sistema di Hilbert

Parte quarta Logica dei predicati p. 99 14. Formule predicative e quantificatori

14.1. Dalla segnatura alle formule predicative14.2. I quantificatori14.3. Variabili vincolate e variabili libere14.4. Modelli e validit

15. Il metodo dei tableaux e il calcolo dei predicati15.1. Tableaux e quantificatori15.2. Regole per la costruzione di un tableau

predicativo15.3. Esempi di formule valide nel calcolo

dei predicati15.4. Correttezza e completezza del metodo

dei tableaux16. I sistemi di Gentzen e di Hilbert, la risoluzione

e il calcolo dei predicati

16.1. Sistema di Gentzen per il calcolo dei predicati16.2. Correttezza e completezza del sistema

di Gentzen16.3. Cenni sul sistema di Hilbert per il calcolo

dei predicati16.4. Correttezza e completezza del sistemadi Hilbert

Parte quinta Procedimenti di risoluzione p. 121 17. Forme normali congiuntive e risoluzione

17.1. Forme normali congiuntive17.2. Risoluzione17.3. Correttezza e completezza della risoluzione17.4. Quali prospettive?

Appendice A Il sistema assiomatico di Zermelo p. 129per la teoria degli insiemi

Appendice B Teorie aritmetiche e modelli p. 135

Appendice C Complementi sui numeri primi p. 141


6/155


7/155

7

Il frontespizio di unedizione delle opere di Aristotele con i commentidi San Tommaso dAquino stampata a Venezia nel 1550

__________


8/155

7

I

Insiemi e funzioni

1. TEORIA DEGLI INSIEMI

1.1. Insiemi

Intuitivamente, il concetto di insieme pu essere fatto corrispondere allatto mentalemediante il quale associamo alcuni elementi in un tutto unico dettoinsieme . La teoriadegli insiemi pu essere introdotta assiomaticamente e linsieme unconcetto

primitivo : storicamente, lapplicazione del metodo assiomatico alla teoria degliinsiemi ebbe in Ernest Zermelo (1871-1953) il principale protagonista; dedicheremoa tale argomento lappendice A.

In questa fase ci limiteremo ad introdurre le principali nozioni insiemistichemantenendo un punto di vista intuitivo. Non richiesta alcuna particolare omogeneittra gli elementi che costituiscono un insieme: possibile associare nello stesso insiemeun numero qualsiasi di elementi di qualsiasi genere (anche se nel paragrafo 5.2 cioccuperemo della questione delleventuale appartenenza di un insieme a se stessocome elemento).

Esempio. possibile parlare di un insieme a cui appartengono il nome del monte pialto della Terra, lultima lettera dellalfabeto italiano e le soluzioni dellequazione:

x+6 = 5 x. Tale insieme ha elementi: Everest, Z, 2, 3.

Un insieme privo di elementi si diceinsieme vuoto ; si indica col simbolo .

Esempio.Linsieme costituito dalle soluzioni intere di: x = 2 linsieme vuoto, :ci equivale ad affermare che lequazione data non ha radici intere.

Affinch una collezione di elementi possa essere classificata come un insieme veroe proprio, deve sempre essere possibile stabilire se un qualsiasi elemento appartiene(o non appartiene) allinsieme cos introdotto.


9/155


10/155

9

condizione necessaria e sufficiente per lappartenenza di un elemento allinsiemeconsiderato. La scrittura dellinsieme avr forma:

{ x: x rispetta unassegnata condizione}

nella quale il simbolo : (talvolta sostituito da |) si legge tale che.

Esempio.Indichiamo linsieme I di interi il cui quadrato minore di 15: rappresentazione tabulare: I = {3;2;1; 0; 1; 2; 3}; rappresentazione caratteristica: I = { x: x un numero intero e3 x3}.

Nellesempio precedente abbiamo scritto (usando parole tratte dalla lingua

italiana) che lelemento x un numero intero, cio appartiene allinsiemecostituito dai numeri interi . Questo insieme generalmente indicato con il simboloZ. Anche altri insiemi numerici sono di uso frequente:

N insieme dei numeri naturaliN0 insieme dei numeri naturali non nulli

Z insieme dei numeri interiZ0 insieme dei numeri interi non nulliZ+ insieme di numeri interi positiviZ- insieme dei numeri interi negativi

Q insieme dei numeri razionaliQ0 insieme dei numeri razionali non nulliQ+ insieme dei numeri razionali positiviQ- insieme dei numeri razionali negativi

R insieme dei numeri realiR0 insieme dei numeri reali non nulliR+ insieme dei numeri reali positiviR- insieme dei numeri reali negativi

C insieme dei numeri complessi

e dunque linsieme dei numeri interi il cui quadrato minore di 15 pu scriversi { x: xZe 2 x2} oppure { x Z:2 x2}.

1.2. Sottoinsiemi e inclusione


11/155

10

Fissato un insieme A, diremo sottoinsieme B di A un insieme al qualenon

appartengono elementi non appartenenti ad A : dunque B pu essere costituito daalcuni elementi di A, o da tutti gli elementi di A, o da nessun elemento.

Definizione.Linsieme B si dicesottoinsieme dellinsieme A se ogni elemento di B elemento di A; si dice anche che B incluso in A e si scrive: BA.

Tra tutti i sottoinsiemi di un insieme dato A troviamo sempre linsieme A stesso elinsieme vuoto : essi sono dettisottoinsiemi impropri di A; un sottoinsieme di Adiverso da A stesso e da si dicesottoinsieme proprio di A.

Linsieme vuoto ammette uno ed un solo sottoinsieme (improprio):. Un insieme

costituito da un solo elemento, A = {a}, ammette due sottoinsiemi impropri,ed Astesso, e non ammette alcun sottoinsieme proprio.

Definizione.Si dice insieme delle parti di un insieme I linsieme (I) avente perelementi tutti i sottoinsiemi (propri ed impropri) di I:(I) = {J: J I}.

Si pu verificare che se linsieme I costituito dan elementi (si dice anche che lacardinalit di I n: riprenderemo ed amplieremo il concetto di cardinalit nellasezione II), linsieme delle parti di I costituito da 2n elementi (ovvero: la cardinalitdi (I) 2n: dimostreremo ci nel capitolo 7).

Esempio.Consideriamo linsieme (avente cardinalit 3): I = {5;w; z}. I suoisottoinsiemi propri sono:

{5}, {w}, { z}, {5;w}, {5; z}, {w; z}

I suoi sottoinsiemi impropri sono:, {5;w; z}.Linsieme delle parti (proprie e improprie) dellinsieme I ha cardinalit 23 = 8 ed

, in rappresentazione tabulare:

(I) = { , {5}, {w}, { z}, {5;w}, {5; z}, {w; z}, {5;w; z}}

Il concetto di inclusione ci permette di riprendere quello diuguaglianza di dueinsiemi . Diremo dunque che i due insiemi A e B sonouguali , e scriveremo A = B,quando A sottoinsieme di B e contemporaneamente B sottoinsieme di A, cioquando: A B e B A.


12/155


13/155

12

Esempio.La differenza di A = { x R: 1< x


14/155

13

Evidentemente la proiezione di tutto linsieme (non vuoto) AB su A A stesso esu B B stesso.

Esempio.Sia S il sottoinsieme diNN costituito dalle coppie (n; m) tali chen+m =3. Lasciamo al lettore di verificare che S = {(0; 3); (1; 2); (2; 1); (3; 0)}.

La proiezione di S suN U = {0; 1; 2; 3}.In questo caso conN indichiamo indifferentemente sia il primo che il secondo

degli insiemi dei quali viene considerato il prodotto cartesianoNN. Tuttavia ingenerale necessaria una loro distinzione, come apparir chiaro dallesempioseguente.

Esempio.Sia T il sottoinsieme diNN costituito dalle coppie (n; m) tali che 2n+m = 4. Lasciamo al lettore di verificare che T = {(0; 4); (1; 2); (2; 0)}.La proiezione di S sul primo degli insiemiN U1 = {0; 1; 2}.

La proiezione di S sulsecondo degli insiemiN U2 = {0; 2; 4}.

2. RELAZIONI E LORO PROPRIET

2.1. Sottoinsiemi del prodotto cartesiano

Siano dati gli insiemi A, B, AB. Come sappiamo, ad AB appartengono tutte lecoppie ordinate costituite da un primo elemento tratto da A e da un secondoelemento tratto da B. Pu essere opportuno, in alcuni casi, evidenziare alcuniparticolari sottoinsiemi di AB: ad esempio, per sottolineare che alcune coppie di AB rispettano una qualche propriet, verificano una legge.

Definizione.Si dice relazione tra gli insiemi A e B un sottoinsieme del prodottocartesiano AB.

Esempio.Consideriamo gli insiemi:

A = {Arno; Po; Tevere} B = {Firenze; Pisa; Torino}

e il loro prodotto cartesiano:


15/155

14

AB = {(Arno; Firenze); (Arno; Pisa); (Arno; Torino);(Po; Firenze); (Po; Pisa); (Po; Torino);

(Tevere; Firenze); (Tevere; Pisa); (Tevere; Torino)}Tra tutte le coppie aventi per primo elemento un elemento di A (in questo caso,

un fiume) e per secondo un elemento di B (una citt), individuiamoquelle costituitedal nome di un fiume e da quello di una citt bagnata da tale fiume :

R = {(Arno; Firenze); (Arno; Pisa); (Po; Torino)}

Limportanza del sottoinsieme R di AB evidente: esso sottolinea che tutte (esoltanto) le coppie ad esso appartenenti verificano una determinata propriet, ovvero

sono costituite da un fiume e da una citt bagnata da esso.Il sottoinsieme R ora indicato uno dei possibili sottoinsiemi di AB: altrisottoinsiemi possono essere individuati da altre considerazioni (tutte ugualmentevalide dal punto di vista insiemistico).

Quando si considera la coppia (a ; b) appartenente ad un dato sottoinsieme R diAB, si dice che lelementoa A ha per corrispondenteb B nella relazione R,oppure che gli elementia , b sono in relazione fra loro .

Una relazione, come ogni sottoinsieme del prodotto cartesiano di insiemi, puessere rappresentata graficamente.

Esempio.Il grafico rappresenta la relazione introdotta nel precedente esempio.

Torino

Pisa

Firenze

Arno Po Tevere

2.2. Relazioni tra un insieme e se stesso e loro propriet

Per la definizione del prodotto cartesiano di due insiemi, sopra introdotta, non necessario che gli insiemi in questione siano distinti: cio possibile parlare del


16/155


17/155

16

Cio: una relazione definita tra gli elementi di un insieme gode della propriettransitiva (si dice anche: transitiva) quando, perogni terna di elementia , b, c

dellinsieme considerato, accade che sea in relazione conb e b in relazione conc, alloraa in relazione conc.

Esempio.Consideriamo nellinsieme I delle rette del piano la RII:

R = {(r ; s):r coincidente o parallela as}

Tale relazione gode delle propriet: riflessiva , perch ogni retta coincidente o parallela a se stessa (nel caso

specifico: coincidente);

simmetrica , perch se la rettar coincidente o parallela alla rettas, alloraanches coincidente o parallela ar ; transitiva , perch se la rettar coincidente o parallela alla rettas e la retta s

coincidente o parallela alla rettat , allora la rettar risulta coincidente o parallela at .Il lettore verificher che la relazione R non gode delle altre propriet sopra

esaminate (antiriflessiva, antisimmetrica).

Esempio.Consideriamo, nellinsieme J delle lunghezze dei segmenti del piano, laS JJ:

S = {(a ; b): la lunghezzaa non minore di quellab}

Tale relazione gode delle propriet: riflessiva , perch la lunghezza di ogni segmento non minore di se stessa; antisimmetrica , perch se la lunghezza di un primo segmento non minore

della lunghezza di un secondo ed inoltre la lunghezza del secondo segmento nonminore di quella del primo, allora i due segmenti considerati hanno la stessalunghezza;

transitiva , perch se la lunghezzaa di un segmento non minore di quellabe la lunghezzab non minore di quellac, allora la lunghezzaa non minore di quellac.

La relazione S non gode delle altre propriet sopra esaminate (antiriflessiva,simmetrica).

Esempio.Consideriamo, nellinsieme I delle rette del piano, la TII:

T = {(r ; s):r perpendicolare as}


18/155


19/155


20/155

19

Linsieme quoziente costituisce una partizione di I in classi di equivalenza: con ciintendiamo che tali classi, non vuote, sono a due a due disgiunte (come sopra

dimostrato) e che lunione di tutte le classi I.Esempio. Consideriamo, nellinsieme I delle rette del piano, la relazione diequivalenza:

R = {(r ; s):r coincidente o parallela a s}

gi esaminata in precedenti esempi. Le classi di equivalenza rispetto a tale relazionesono i sottoinsiemi di I del tipo:

[s] = {r I:r coincidente o parallela as}Ciascuno degli elementi dellinsieme quoziente I/R costituito da un insieme di

rette parallele: esso pu dunque essere identificato con la comunedirezione di esse.

2.4. Relazioni dordine

Definizione.Una relazione RII si dicerelazione dordine (o di ordine largo ) segode delle propriet riflessiva, antisimmetrica e transitiva.

Definizione.Una relazione RII si dicerelazione di ordine stretto se gode dellepropriet antiriflessiva e transitiva.

Esempio.Consideriamo nellinsieme J dei segmenti del piano la SJJ:

S = {(a ; b): la lunghezza dia non minore di quella dib}

gi esaminata in un precedente esempio. La relazione data una relazione dordine

(o di ordine largo) in quanto gode delle propriet riflessiva, antisimmetrica etransitiva.

Esempio.Consideriamo nellinsieme J dei segmenti del piano la UJJ:

U = {(a ; b): la lunghezza dia maggiore di quella dib}


21/155

20

La relazione data gode delle propriet: antiriflessiva , perch nessun segmento pu avere lunghezza maggiore della

propria stessa lunghezza; transitiva , perch se un segmentoa ha lunghezza maggiore di quella di unsegmentob ed il segmentob ha lunghezza maggiore di quella di un segmentoc, alloraa ha lunghezza maggiore dic.

La relazione U non gode delle altre propriet esaminate nel paragrafo precedente; una relazione dordine stretto.

Notiamo che se utilizziamo la rappresentazione di relazioni mediante grafico, unarelazione dordine largo comprende tutti gli elementi individuati dai punti individuatidalla diagonale del quadrante considerato, come illustrato nellesempio seguente.

Esempio.Il grafico seguente rappresenta una relazione di ordine largo.

e

d

c

b

a

a b c d e

Invece una relazione dordine stretto non comprende tutti gli elementi individuatidai punti individuati dalla diagonale del quadrante considerato, come illustratonellesempio seguente.

Esempio.Il grafico seguente rappresenta una relazione di ordine stretto.

e

d

c


22/155


23/155

22

totale ; una relazione dordine S che non per tutte le coppie consenta tale confronto,ovvero tale che per almeno una coppia di elementic, d dellinsieme considerato

accada che (c; d ) S e che (d ; c) S, si dicerelazione dordine parziale .Osservazione.Il problema, ora presentato nel caso di una relazione dordine largo,si pu estendere alle relazioni dordine stretto, come la U presentata nellesempioprecedente. Le possibilit, in questultimo caso, non sono pi due, ma tre: alle (a ; b)

U, (b; a) U, corrispondenti ai casi in cui la lunghezza dia maggiore di quella dib e viceversa, deve essere aggiunto il caso in cui le lunghezze sono uguali.

Esempio.Sia I linsieme avente per elementi tutti i sottoinsiemi diR (cio linsiemedelle parti diR); definiamo la relazione SII:

S = {(A; B): AB}

Tale relazione una relazione dordine, in quanto gode delle propriet: riflessiva , perch per ogni A : AA; antisimmetrica , perch da (AB) e (B A) segue A = B; transitiva , perch da (AB) e (B C) segue A C.La S una relazione dordine parziale: infatti possibile trovare coppie di

sottoinsiemi C, D diR tali che (C; D)S e (D; C) S.Ad esempio se C, D sono definiti da:

C = { x R: 0< x


24/155

23

primo insieme D e quelli del secondo insieme B indotta da una funzione si realizzaquando:

ogni elemento di D ha un corrispondente in B; nessun elemento di D ha pi di un corrispondente in B.

Definizione.Una relazione RDB si dice funzione (o applicazione ) se per ogniaD esisteuno ed un solo b B tale che: (a ; b) R.

Osservazione.Se f DB una funzione e seb1 B, b2 B, b1 b2, in base alladefinizione data risulta:

( x; b1) f ( x; b2) f

( x; b2) f ( x; b1) f

Possibile invece che esistanob B, x1 D, x2 D, x1 x2 tali che:

( x1; b) f e ( x2; b) f

Una funzione si indica spesso con la lettera f ; si scrive: f DB, o: f : DB; ilprimo insieme, D, si dicedominio della funzione f . A ciascun elemento x del dominiodella f corrisponde un(unica)immagine , indicata da f ( x) B, e si scrive: f : x f ( x).Analogamente, si dice che x D controimmagine di f ( x) B.

Talvolta linsieme B si indica con il terminecodominio .

Definizione.Data la funzione f : DB, linsieme CB costituito dalle immagini deglielementi di D si diceinsieme delle immagini della f .

Pertanto linsieme delle immagini della funzione f : DB quel sottoinsieme di Bcostituito dagli elementi di B aventi (almeno) una controimmagine in D.

Esempio.Consideriamo le relazioni rappresentate da:

a b i j s t e

c h q ym x

d n r p z

A R1 B I R2 J S R3 T


25/155

24

La prima di esse una funzione, mentre le altre due non rispettano la definizionedi funzione.

Infatti, in R1 AB, ad ogni elemento di A corrisponde una ed una sola immaginein B; linsieme delle immagini della funzione R1 C = {b; m}.Nella relazione R2 IJ, a q I non corrisponde alcun elemento in J, contro la

definizione di funzione. Nella relazione R3 ST, allo stesso elemento x Scorrispondono i distinti elementi y T e z T, contro la definizione di funzione.

Esempio.Sia P linsieme dei punti del piano e sia Z linsieme delle circonferenzetracciate nel piano. Consideriamo le relazioni RPZ e S ZP:

R = {( p; z): il punto p P il centro della circonferenza z Z}S = {( z; p): la circonferenza z Z ha per centro il punto p P}

Esaminiamo la R: in essa, ad ogni punto p del piano corrispondono infinitecirconferenze z, in quanto ogni punto pu essere centro di infinite circonferenze(concentriche): la R non rispetta la definizione di funzione.

Nel caso della S, invece, ad ogni circonferenza z corrisponde (in qualit di centro)uno ed un solo punto p: pertanto, la S una funzione.

Osservazione.La definizione di funzione richiede che, per assegnare una funzione f :DB, siano assegnati un insieme D, detto dominio, un secondo insieme B al qualeapparterranno le immagini, e una legge che ad ogni x D fa corrispondere una ed unasola f ( x) B. Spesso, per, quando si considerano funzioni definite in un sottoinsiemeD diR ed aventi immagini reali, una funzione f viene assegnata indicando la legge chead ogni x D fa corrispondere la f ( x) R, senza fissare esplicitamente il dominio ;anzi, frequentemente la determinazione del dominio viene lasciata come esercizio. Inquesto caso, con il termine dominio si intende il pi grande DR tale che per ogni x

D sia possibile calcolare f ( x) R.

Esempio.Se la funzione f viene indicata con la scrittura:

f : x x

allora il pi grande DR tale che per ogni x D sia possibile calcolare x R { xR: x0}. Dunque si dice che il dominio della f : x x { x R: x0}.


26/155

25

Questo modo di procedere spesso accettato: per opportunospecificareesplicitamente il dominio nei casi in cui possano sorgere malintesi .

(Contro)esempio.Consideriamo la funzione x f ( x) espressa da:

f ( x) = x x 1

Qual il dominio di questa funzione? Se cerchiamo un dominio DR affinch il denominatore sia non nullo e la radice

quadrata sia reale, dobbiamo imporre la condizione: x>1.Ma attenzione: a x = 0 (considerato come numero complesso) corrisponde f (0) =

00 1 = 0/ i = 0 (dovei = 1, i C; il lettore ricorder dagli studi secondari chelo 0 complesso diviso per un complesso non nullo d sempre come quoziente lo 0complesso).

Abbiamo dunque visto che f (0) = 0 (lo zero inC), e ci potrebbe indurre aconsiderare 0 come appartenente al dominio di f ; ma non si dimentichi che pereseguire il calcolo di f (0) necessario considerare lo 0 come elemento diC edestrarre quindi (sempre inC) la radice quadrata di1: e tutto ci porta anon considerare 0 come appartenente al dominio di f .

In situazioni come quella ora descritta evidentemente consigliabile precisare a

priori il dominio in cui definita la funzione, al fine di evitare ambiguit.

3.2. Funzioni iniettive, suriettive, biiettive

Nel paragrafo precedente abbiamo dato la definizione di funzione: abbiamo cioprecisato che una relazione tra due insiemi detta funzione quando ad ogni elementodel primo insieme (dominio) corrisponde una ed un sola immagine nel secondoinsieme.

Riflettiamo ora su di una funzione gi esaminata precedentemente:

a be

c hm

d n


27/155

26

A R1 B

Dal suo esame, appare evidente che la definizione di funzione: non impone che due distinti elementi del dominio abbiano immagini distinte(ricordiamo losservazione posta dopo la definizione di funzione);

non impone che tutti gli elementi del secondo insieme abbiano unacontroimmagine nel dominio (ovvero che linsieme delle immagini dellafunzione coincida con lintero secondo insieme).

Quelle (particolari) funzioni che rispettano una di queste due ulteriori condizioni(oppure entrambe) vengono indicate con denominazioni specifiche.

Definizione.La funzione f : DB si diceiniettiva se per ogni x1 D e per ogni x2D, con x1 x2 e conb B: ( x1; b) f ( x2; b) f.

Dunque una funzione f : DB si dice iniettiva se adogni coppia di elementidistinti di D corrisponde una coppia di elementidistinti di B, ovvero se nessunelemento di B dotato di pi di una controimmagine in D.

Definizione.La funzione f : DB si dicesuriettiva se per ognib B esiste (almeno)un x D tale che: ( x; b) f.

Dunque una funzione f : DB si dice suriettiva seogni elemento dellinsieme B ha(almeno) una controimmagine nel dominio ovvero se linsieme delle immagini di f coincide contutto linsieme B.

Definizione.La funzione f : DB si dice biiettiva se contemporaneamenteiniettiva e suriettiva.

Una funzione biiettiva viene talvolta indicata con i terminibiiezione ocorrispondenza biunivoca .

Esempio.La funzione R1: AB introdotta in un precedente esempio non iniettiva,in quanto ai due (distinti) elementi del dominioc A, d A corrisponde la stessaimmaginem B. Essa non suriettiva, in quanto gli elementi del secondo insiemeeB, h B, n B non hanno alcuna controimmagine nel dominio A (cio: linsieme delleimmagini della funzione, C = {b; m}, non coincide con tutto B). Non essendoiniettiva n suriettiva, la funzione non certamente biiettiva.


28/155

27

Esempio.Consideriamo la funzione S introdotta in un esempio precedente. Sia Plinsieme dei punti del piano e sia Z linsieme delle circonferenze tracciate nel piano

stesso. La relazione SZP:S = {( z; p): la circonferenza z Z ha per centro il punto p P}

rispetta la definizione di funzione; iniettiva, suriettiva, biiettiva?Essa non iniettiva: esistono coppie di circonferenze distinte aventi lo stesso

centro (concentriche). suriettiva: ogni punto del piano centro di (almeno) unacirconferenza (di infinite circonferenze, ma la precisazione ininfluente per quantoriguarda la suriettivit). Non biiettiva, non essendo iniettiva.

Esempio.Sia f : RR la funzione che ad ogni x R fa corrispondere il doppio di x,2 x R (si verifichi innanzitutto per esercizio che essa rispetta la definizione difunzione). Si tratta di una funzione iniettiva. suriettiva, biiettiva?

La risposta a tutte le domande : s.La funzione f iniettiva, in quanto ad ogni coppia di reali distinti corrispondono

coppie di doppi distinti: se le immagini 2a e 2b coincidessero, non potrebbero checoincidere anchea e b. La funzione f inoltre suriettiva, in quanto ogni elemento delsecondo insieme ha una controimmagine nel dominio: ovvero ogni reale y il doppiodi un (opportuno) reale y /2. Essendo iniettiva e suriettiva, la funzione f biiettiva.

4. FUNZIONI COMPOSTE E FUNZIONI INVERSE

4.1. La funzione composta

Consideriamo tre insiemi A, B, C e le funzioni: f : AB, g: BC. La f facorrispondere ad ogni x A uno ed un solob B; a tale elementob, la g facorrispondere uno ed un soloc C. Possiamo riassumere quanto detto nello schema:

a f b g c

ovvero, con riferimento allelementoa A da cui trae origine la corrispondenza:

a f f (a) g g[ f (a)]


29/155

28

possibile considerare unanuova funzione che faccia direttamente corrispondere

allelementoa A lelementog[ f (a)] C. Essa denominata funzionecomposta delledue funzioni considerate e si indica con la scrittura:

g f oppure: gf

Attenzione: per convenzione,si indica per prima la funzione che opera per ultima ! Ci viene scelto per analogia con la scritturag[ f (a)] dellelementocorrispondente dia nella funzione compostag f .

Definizione.Date le funzioni f : AB eg: BC, si dice funzione composta g f lafunzione che ad ogni elementoa A fa corrispondere lelementog[ f (a)] C.

Esempio.Siano date le funzioni f :RR e g:RR definite da:

f : x3 x g: x x+2

Determiniamo le funzioni composte f g e g f . Ricordiamo che, nelle funzionicomposte, la funzione componente ad operare per prima quella scritta perseconda. Iniziamo quindi con il ricavo dellespressione di f g:

f g: x g x+2 f 3( x+2)

Osserviamo che la f , che allelemento del dominio fa corrispondere il suo triplo,non opera sulla x, bens sullelemento ( x+2), gi trasformato dalla precedente azionedella funzioneg. Per quanto riguarda lag f , otteniamo:

g f : x f 3 x g 3 x+2

Le due funzioni composte richieste sono quindi:

f g: x3 x+6 g f : x3 x+2

Confrontando le funzioni f g e g f : ricavate nellesempio precedente, possiamonotare che la composizione di funzioninon gode della propriet commutativa . Siverifica invece che la composizione di funzionigode della propriet associativa ;ovvero, assegnate le tre funzioni f , g, h, risulta:


30/155

29

( f g)h = f (gh)

4.2. Lapplicazione della definizione di funzione composta

La definizione afferma che, date le funzioni f : AB e g: BC, si dice funzionecompostag f la funzione che ad ogni elementoa A fa corrispondere lelementog[ f (a)] C. Talvolta lapplicabilit di tale definizione richiede cautela. Non sempre,infatti, saremo chiamati a comporre due funzioni f : AB eg: BC, ovvero tali chelinsieme delle immagini di f (che essendo f : AB un sottoinsieme di B) sia inclusonel dominio (linsieme B) dig.

(Contro)esempio.Siano date le funzioni f : RR e g: DgR, essendo Dg = { xR: x 1}:

f : x x g: x x 1

Vogliamo considerare la compostag f ; teniamo per presente che linsieme delleimmagini di f : CD f = { x R: x0} non un sottoinsieme del dominio dig, Dg = { xR: x1}: lapplicazione della definizione richiede alcune precisazioni.

Quanto esposto nel precedente esempio conferma che lapplicabilit delladefinizione pu richiedere qualche modifica della situazione proposta. Il problema far s che linsieme delle immagini di f sia un sottoinsieme del dominio dig. A talescopo, dobbiamo effettuare la composizionenon tra f : DR con insieme delleimmagini D eg: DgC, bens tra f 0: D0R con insieme delle immagini CD0 e g,essendo f 0 una funzione definita dallastessa legge che definisce la f , maristretta ad un dominio D0 D, in modo tale che linsieme delle immagini di f 0 sia unsottoinsieme del dominio dig. Sceglieremo f 0: D0R con insieme delle immaginiCD0 in modo che D0 sia il massimo dominio possibile tale che CD0 Dg.

La funzione f 0: D0R si dicerestrizione della funzione f : DR, con D0 D.

Esempio.Siano date le funzioni f :RR, g: DgR, con Dg = { x R: x 1}:

f : x x g: x x 1

come nellesempio precedente. Per definireg f , restringiamo prima la funzione:


31/155

30

f : x x f :RR, con insieme delle immagini: { x R: x0}

(che non un sottoinsieme di Dg = { x R: x1}) alla funzione: f 0: x x f 0: { x R: x1 x1}R con insieme delle immagini: { x R: x1}

che un sottoinsieme (improprio) di Dg = { x R: x1}.La definizione ora applicabile e la funzione composta richiesta :

g f : x x2 1

Il suo dominio : { x R: x1 o x1}.Osservazione.Non sempre i passaggi indicati nel presente paragrafo (la restrizionedella prima funzione che opera in una composizione di funzioni) vengonoesplicitamente espressi in esercizi ed in applicazioni. Talvolta, cio, per trovare lafunzione compostag f date le f : x x e g: x x 1, ci si limita a scrivere:

g f : x x2 1

sottintendendo che il dominio { x R: x1 o x1}.

4.3. Il dominio della funzione composta

Quanto notato nel paragrafo precedente (e nellosservazione conclusiva) indica che necessario prestare attenzione alla determinazione del dominio di una funzionecomposta, questione che, in alcuni casi, pu rivelarsi assai delicata.

Infatti, non sempre i domini (e gli insiemi delle immagini) di entrambe le funzionicomponenti vengono indicati esplicitamente. Ci potrebbe talvolta portare asituazioni problematiche: come abbiamo rilevato nel precedente paragrafo, affinchad un elementoa A corrisponda un elementog[ f (a)] attraverso la funzionecomposta, necessario che limmagine dia attraverso la funzione f , f (a), appartengaal dominio della funzioneg. Ebbene, se questo dominio indicato esplicitamente, ilcontrollo immediato; ma nellesempio seguente illustreremo un caso in cui richiesta una qualche cautela.


32/155

31

(Contro)esempio.Siano date le funzioni f : DR (dove : DR) e g: RR definite da:

f : x x g: x(1 x)

Determiniamo (se possibile) la funzione composta f g.Attenzione: il dominio della funzione f (che la funzione che, essendo scritta per

prima in f g, opera per seconda) :

D f = { x R: x0}

in quanto la radice quadrata non calcolabile reale per radicandi negativi.

Notiamo inoltre che linsieme delle immagini dellag (che opera per prima) :CDg = { x R: x1}

in quanto, per ogni x R, risulta:

1 x 1

Concludendo: linsieme delle immagini della funzione che opera per prima costituito dai reali non maggiori di1; il dominio della funzione che opera perseconda costituito dai reali non negativi. Pertanto tale dominio e tale insieme delleimmagini sono disgiunti, e nessun elemento x del dominio dellag che opera per primaavr immagine appartenente al dominio della f che opera per seconda: quindi nessunelemento x avr immagine nella funzione composta f g.

Quanto affermato pu essere confermato dal ricavo (inutile) dellespressioneanalitica della funzione composta f g:

f g: x g (1 x) f x 1 2

Al lettore il semplice compito di verificare che il dominio di f g sarebbe (nellambito dei numeri reali).

Generalizzando quanto osservato nellesempio precedente, possiamo ribadire cheaffinch la funzione composta f g abbia dominio non vuoto necessario e sufficienteche linsieme delle immagini dig, CDg, e il dominio di f , D f , non siano disgiunti,ovvero che sia: D f CDg .


33/155

32

4.4. La funzione identit

Definizione.Dato un insieme I, si diceidentit , e si indica coni, la funzione di IIche ad ogni elementoa I associa se stesso:i = {(a ; a):a I}.

Lasciamo al lettore il compito di rendersi conto che lai cos introdotta unafunzione biiettiva. Considerata la funzione (qualsiasi) f : AB, si verifica che:

f i = i f = f

4.5. La relazione inversa

Si consideri una relazione tra gli elementi degli insiemi A e B: RAB.Consideriamo quindi unanuova relazione, che indicheremo con R1, tra gli

elementi degli insiemi B e A: R-1 BA definita nel modo seguente:

( y; x) R1 ( x; y) R

Tale nuova relazione R-1 denominatarelazione inversa della relazione R, comeespresso dalla definizione seguente.

Definizione.Data la relazione RAB, si dicerelazione inversa R1 della R larelazione R1 BA tale che:

R1 = {(b; a): (a ; b) R}

Esempio.Sono dati gli insiemi A = {1; 2; 5}, B = {1; 3} e la relazione RAB:

R = {(a ; b):ab} = {(1; 1); (1; 3); (2; 3)}

La relazione inversa R1 la seguente:

R1 = {(b; a):ba} = {(1; 1); (3; 1); (3; 2)}


34/155

33

Spesso richiesto di determinare la relazione inversa di una funzione espressanella forma: x f ( x). Nellesempio seguente illustrato il procedimento per ricavare

lespressione della relazione inversa di una funzione data.Esempio.Consideriamo la funzione f :RR definita da:

f : x2 x3

Ricaviamo lespressione della relazione inversa.Indichiamo con: y = 2 x3 limmagine dellelemento x. La data relazione si indica

ora con la scrittura:

( x; y) f Per ricavare la cercata espressione della relazione inversa, in base alla definizione,

dobbiamo ottenere una scrittura del tipo:

( y; x) f 1

ovvero scambiare le posizioni ed i ruoli di x e y. Nel passaggio dalla funzione dataalla sua relazione inversa, lespressione y = 2 x3 diventer quindi x = 2 y3, dallaquale, esplicitando la y, ricaviamo:

y = x +32

che limmagine di x nella relazione inversa. Pertanto la relazione inversa dellafunzione: f : x2 x3 espressa dalla (nuova) funzione:

f -1: x x +32

Osservazione. Concludiamo notando che nel caso esaminato nellesempioprecedente la relazione inversa di una funzione unaltra funzione (cio una relazioneche rispetta la definizione di funzione). Ma non sempre accadr ci.

Abbiamo introdotto la relazione inversa di una relazione data. Sappiamo chealcune relazioni (non tutte), in base alle loro caratteristiche, soddisfano anche ladefinizione di funzione; in questo paragrafo ci occuperemo di una questione che si


35/155

34

riveler di notevole importanza: in base alla definizione di relazione inversa, linversadi una funzione una relazione, ma addirittura una funzione ?

In generale la risposta : no. Nei due esempi seguenti potremo esaminare duediverse situazioni: nella prima, la relazione inversa di una funzione data sar ancorauna funzione; nella seconda, ci non accadr: la relazione inversa della funzioneproposta non rispetter la definizione di funzione.

Esempio.Si consideri la funzione f :RR definita da:

f : x2 x

si ricavi lespressione della relazione inversa e si dica se tale relazione rispetta la

definizione di funzione.La relazione inversa della funzione che ad ogni x fa corrispondere il suo doppio quella che ad ogni x fa corrispondere la sua met. Ovvero:

f 1 : x x /2

Non difficile rendersi conto che questa relazione rispetta la definizione difunzione: ad ogni x reale corrisponde infatti una ed una sola met x /2.

(Contro)esempio.Si consideri la funzioneg:RR definita da:

g: x x

si ricavi lespressione della relazione inversa e si dica se tale relazione rispetta ladefinizione di funzione.

In questo caso, la situazione pi delicata: infatti la relazione inversa associa adogni elementonon negativo la sua radice quadrata, ma sia con il segno + che conil segno . Insomma, se:

g = {( x; x): x R} g1 = {( x; x): x R}

risulta: (9; 3)g1, ma anche: (9;3) g1.Possiamo concludere che questa relazione inversanon rispetta la definizione di

funzione. E ci per ben due ragioni: primo, non per tutti i numeri reali possibilecalcolare (reale) la radice quadrata (ma soltanto per i reali non negativi); in secondoluogo, per ogni reale positivo x, esistono due reali (e non uno solo) che elevati alquadrato danno come risultato x: essi sono + x e x .


36/155

35

Abbiamo constatato che in alcuni casi la relazione inversa di una funzione

ancora una funzione, mentre in alcuni casi non lo . Ebbene, perch accade ci?Quali caratteristiche deve avere una funzione affinch anche la sua relazione inversarispetti la definizione di funzione?

Non difficile rispondere a questa domanda, se si tiene presente quanto richiestodalla stessa definizione di funzione: affinch una relazione tra due insiemi sia unafunzione bisogna che ogni elemento del primo insieme (dominio) abbia una ed unasola immagine.

Ricordiamo che linversione di una relazione comporta lo scambio dei due insiemi:il primo insieme diventa il secondo e viceversa. Quindi, per stabilire se la relazioneinversa rispetta la definizione di funzione dobbiamo esaminare:

se ogni elemento del primo insieme (nella relazione inversa) dotato dialmeno una immagine. Ovvero: se ogni elemento del secondo insieme (nellarelazione originaria) dotato di almeno una controimmagine. E pertanto: lafunzione originaria deve esseresuriettiva .

se ogni elemento del primo insieme (nella relazione inversa) dotato di unasola immagine. Ovvero: se ogni elemento del secondo insieme (nellarelazione originaria) dotato di una sola controimmagine. E pertanto: lafunzione originaria deve essereiniettiva .

Possiamo concludere che le condizioni affinch la relazione inversa di una funzione f rispetti la definizione di funzione sono liniettivit e la suriettivit della funzione

originaria f : tale funzione, quindi, deve esserebiiettiva .Definizione.Una funzione si diceinvertibile quando anche la sua relazione inversarispetta la definizione di funzione.

Proposizione.Una funzione invertibile se e soltanto se biiettiva .

Dunque si identifica una funzione biiettiva f : AB in una relazione che adogni elemento di A fa corrispondereuno ed un solo elemento di Be viceversa .

Ricordando la definizione di identit e indicate una funzione invertibile e la propriafunzione inversa rispettivamente con f , f 1, semplice ricavare:

f f 1 = f 1 f = i

5. CENNI SULLE ANTINOMIE DELLA TEORIA DEGLI INSIEMI


37/155

36

5.1. Le antinomieConcludiamo la sezione dedicata alla teoria degli insiemi presentando alcuneimportanti considerazioni storiche, dedicate ad uno degli argomenti pi affascinantidella logica matematica: ci riferiamo alla questione delle antinomie, frasiapparentemente ingannevoli, strane ma eleganti, nelle quali sembrano convivereverit e falsit (la letteratura su antinomie e paradossi vastissima; ci limitiamo adindicare: Hamblin, 1970; Falletta, 1989).

Il termine antinomia deriva dal greco anti (contro) e nomos (legge, norma);esso utilizzato per indicare il verificarsi di una contraddizione, ovvero, ad esempio,

la presenza di una particolare proposizione che al contempo risulta essere vera efalsa, nellambito di una teoria. Limproponibile contrasto tra i valori di verit risultaallora inevitabile, finendo cos per ledere la stessa validit del sistema logico nel qualeviene scoperta lantinomia in questione.

Verso la fine delXIXsecolo, vengono proposte numerose antinomie sulla teoriadegli insiemi. Alcune di esse sono antinomie semantiche, ovvero collegate alsignificato attribuito a particolari termini del linguaggio; altre invece sono antinomielogiche, ovvero connesse alla struttura delle frasi in questione, come la celebreantinomia di Russell, che esamineremo nel paragrafo seguente.

Lenunciato che segue falso . Lenunciato che precede vero.Congiuntamente questi enunciati danno lo stessorisultato del paradosso di Epimenide. Eppure,separatamente, sono enunciati innocui e perfinopotenzialmente utili.

Douglas R. Hofstaedter

Una delle pi celebri antinomie semantiche lantinomia del mentitore (o di Epimenide ), nota sino dallantichit (Koir, 1947; Rivetti Barb, 1964; Martin,1970; Maracchia, 1990). Essa sintetizzata nella frase: Io sto mentendo.

Riflettendo su questa affermazione, ci rendiamo conto che: se chi pronuncia tale frase dice la verit, allora egli sta effettivamentementendo, e questa una contraddizione;

se chi pronuncia tale frase mente, allora egli non sta mentendo e, diconseguenza, sta dicendo la verit: anche questa una contraddizione.

Illustriamo unaltra semplice ed elegante antinomia semantica (detta di Berry-Russell, ma la proposta originale di Richard).


38/155

37

noto che il numero delle sillabe dei nomi con i quali si indicano, nella linguainglese, i numeri interi positivi tende a crescere al crescere del numero nominato.

Pertanto, i nomi di alcuni numeri interi positivi devono essere costituiti da almenodiciannove sillabe; fra questi, ne esister uno pi piccolo di tutti gli altri. Chiameremotale numero (che, in inglese, 111777) il pi piccolo intero non definibile con menodi diciannove sillabe. Ma...il pi piccolo intero non definibile con meno didiciannove sillabe (in inglese) una definizione costituita da diciotto sillabe!

La contraddizione appare evidente: il pi piccolo intero non definibile con menodi diciannove sillabe stato definito con sole diciotto sillabe. Anche in questo caso,per, le radici dellantinomia vanno ricercate nel significato attribuito ai terminiutilizzati, e segnatamente al valore assunto dal termine definire: anche lantinomiaora proposta, quindi, unantinomia semantica.

5.2. Gottlob Frege e Bertrand Russell

Il progetto culturale di Gottlob Frege (1848-1925), uno dei massimi logici dellinterastoria della cultura, pu essere sintetizzato nel tentativo di ricondurre interamente lamatematica alla logica (attraverso la teoria degli insiemi). Nel 1902, proprio allavigilia della pubblicazione della seconda parte della grande opera logica fregeana(Princpi dellAritmetica derivati ideograficamente ), il trentenne Bertrand Russell(1872-1970) rilev una contraddizione nel capolavoro del logico tedesco: essa

riassunta nella celebreantinomia di Russell o antinomia degli insiemi normali (Garciadiego, 1992).La formulazione originale dellantinomia di Russell basata sulla definizione di

insieme normale, che illustreremo. Lidea di insieme, come sappiamo, non introdotta da una definizione, ma un concetto primitivo; non ci sono particolarirestrizioni al tipo di elementi che possono appartenere allinsieme dato. quindipossibile (perch no?) richiedere che ad un certo insieme appartenga se stesso comeelemento.

Ecco dunque la definizione di Russell: un insieme I si definiscenormale quandoha la propriet di non contenere se stesso come elemento.

Esempio.Linsieme: I = { x N: x


39/155

38

Consideriamo ora linsieme N avente per elementi tutti e soltanto gli insieminormali: Ncontiene se stesso come elemento?

Una prima possibilit che N contenga se stesso come elemento. Ma N linsieme formato da tutti e soltanto gli insiemi normali, ovvero da tutti esoltanto quegli insiemi che non contengono se stesso come elemento;perci dovremmo concludere che se N appartiene a N risulta che N nonpu contenere se stesso come elemento! La nostra prima risposta finiscequindi per essere contraddittoria.

La rimanente possibilit che N non contenga se stesso come elemento.Ma in tale caso N risulterebbe essere un insieme normale e, diconseguenza, dovrebbe proprio appartenere a N. Ed anche questarisposta contraddittoria.

In simboli, la definizione dellinsieme N : N = {I: II} e le due possibili ipotesisullappartenenza dellinsieme N a N stesso portano alle implicazioni:

N N N N N N N N

ovvero a uninevitabile contraddizione.

Osservazione. Per molti versi analoga allantinomia degli insiemi normali lantinomia del barbiere (lo stesso Bertrand Russell la ricorda come pressochequivalente alla propria antinomia: si veda ad esempio: Aimonetto, 1975).

In un paese isolato, uno degli abitanti il barbiere e rade tutti (e soltanto) coloroche non si radono da s. Domanda: in quel paese, chi rade il barbiere?Ammettiamo che il barbiere si rada da s; ma allora proprio il barbiere che lo

rade, mentre avevamo affermato che il barbiere rade tutti e soltanto coloro che non siradono da s! Questa prima risposta quindi contraddittoria.

Ammettiamo allora che il barbiere non si rada da s; ma in tale caso dovrebbeessere proprio il barbiere a raderlo, in quanto avevamo affermato che il barbiererade tutti e soltanto coloro che non si radono da s: quindi egli si rade da s. Edanche questa seconda risposta si rivela contraddittoria.


40/155

39

La tavola di Lettres une princesse d'Allemagne ( Lettere ad una principessa d'Alemagna sopra diversi soggetti di fisica e di

filosofia : Napoli 1787) in cui Leonhard Euler ha introdotto larappresentazione, oggi diffusissima, per indicare gli insiemi

__________


41/155

39

II

Numeri naturali

6. LINSIEME DEI NUMERI NATURALI

6.1. I numeri naturali: approccio cardinale

Alla fine delXIX secolo, lintero mondo matematico venne impegnato nellapuntualizzazione rigorosa dei fondamenti della disciplina: le teorie di George Boole(1815-1864) e di Georg Cantor (1845-1918) e le approfondite ricerche logico-matematiche di Gottlob Frege sono testimonianze chiare dello spirito che pervase unampio settore della ricerca matematica di quel periodo.

Ci siamo gi occupati dellopera di Frege nella presentazione dellantinomia diRussell; nel 1884, Frege pubblic Die Grundlagen der Arithmetik , lopera in cui sitrova la fondamentale definizione di numero. Egli introduce il numero zerofacendolo corrispondere al concetto di diverso da se stesso (ovvero ad unacondizione di impossibilit): potremmo dire che, per Frege, zero la quantit dielementi che verificano una condizione impossibile.

A partire dallo zero, Frege introduce ricorsivamente ogni altro naturale, ciascunosulla base del precedente: cos il numero 1 associato al (solo) concetto di zero (sitratta dunque diun concetto, considerato singolarmente), il numero 2 ai (due )concetti di zero e di uno, il numero 3 ai (tre ) concetti di zero, di uno e didue, e cos via.

Illustreremo una costruzione diN sulla base della teoria degli insiemi.

Definizione.Due insiemi A, B si diconoequipotenti se sono in corrispondenzabiunivoca, cio quando esiste una funzione biiettiva di dominio A ed insieme delleimmagini B.

Esempio.Considerato un triangolo qualsiasi, linsieme A dei suoi lati e linsieme Bdelle sue mediane sono equipotenti.


42/155

40

Per verificare tale affermazione sufficiente considerare la relazione RAB chead ogni latoa A fa corrispondere la medianab B avente per estremi il vertice

opposto al latoa ed il punto medio dello stesso latoa .La relazione R una funzione: infatti, ad ogni lato del triangolo corrisponde, nellarelazione introdotta, una ed una sola mediana. Questa funzione inoltre suriettiva,giacch ogni mediana corrispondente, nella R, di un lato (quello avente come puntomedio lestremo della mediana non coincidente con un vertice del triangolo); inoltreiniettiva, in quanto a due lati distinti corrispondono due distinte mediane (i loroestremi non coincidenti con un vertice sono i punti medi di due lati distinti): R unafunzione biiettiva.

In base alla definizione concludiamo che A e B sono equipotenti.

(Contro)esempio.Linsieme I = {0; 1} e linsieme J = {10; 11; 12}non sonoequipotenti. Se consideriamo, ad esempio, la funzione f : IJ definita da:

x x+10

ci rendiamo conto che una funzione iniettiva manon suriettiva (il suo insieme delleimmagini {10; 11} enon coincide con lintero J), quindinon biiettiva.

Non esiste alcuna funzione biiettiva IJ. Gli insiemi I e J non sono dunqueequipotenti.

Nel seguito considereremo gli insiemi di cui ci siamo finora occupati (ed altriinsiemi che possiamo immaginare) come elementi di un insieme U. Importantimotivazioni ci impediscono per assolutamente di parlare di insieme costituito datutti gli insiemi: dunque, linsieme U dovr essere considerato soltanto un insieme alquale appartengono, come elementi, altri insiemi, senza alcuna pretesa di totalit.

Osservazione.Tale questione merita sin dora un cenno di approfondimento.Indichiamo con #I il cardinale di un insieme I che identificher linsieme degli insiemi Jequipotenti con I (torneremo pi avanti su questa importante nozione). Ad esempio,se:

A = {3; 7} B = {; } C = {; }

possiamo scrivere:

#A = #B = #C


43/155

41

Se #D#E significa che D equipotente ad un sottoinsieme di E.Ricordiamo che linsieme delle parti (I): linsieme costituito da tutti i

sottoinsiemi di I. Sussiste ilteorema di Cantor , secondo il quale per ogni insieme I,: #I < # (I).Immaginiamo ora di poter parlare dellinsieme totale (insieme di tutti gli

insiemi) T; risulterebbe:

(T) T (infatti T linsieme totale!): #(T)#T

contro il teorema di Cantor, che porta invece a: #T < #(T).

Definiamo in U la relazione di equipotenza, precedentemente introdotta.

Verificheremo che essa una relazione di equivalenza, cio che riflessiva,simmetrica e transitiva.

Proposizione.La relazione di equipotenza tra insiemi una relazione di equivalenza.

Dimostrazione. Verifichiamo direttamente le tre propriet della relazione diequivalenza.

La relazione di equipotenza tra insiemi riflessiva . Infatti, ogni insieme IU equipotente a se stesso: si consideri, a tale riguardo, lidentit, ovveroquella relazione che ad ogni elemento di x I fa corrispondere x stesso. semplice verificare che si tratta di una funzione biiettiva (il lettore pu farlo,per esercizio): conseguentemente, in base alla definizione 1, ogni insieme Irisulta equipotente a se stesso.

La relazione di equipotenza tra insiemi simmetrica . Infatti, se IU equipotente a JU, significa (per definizione) che esiste una funzione biiettiva

f : IJ; essendo f biiettiva, f risulta invertibile, e la funzione inversa f 1: JI, anchessa biiettiva (ad ogni elemento di J fa corrispondere uno ed un soloelemento di I e viceversa). Pertanto, anche J equipotente ad I (per ladefinizione).

La relazione di equipotenza tra insiemi transitiva . Infatti, se IU equipotente a JU ed inoltre JU equipotente a LU, significa (perdefinizione) che esistono due funzioni biiettive f : IJ e g: JL.Consideriamo la funzione compostag f : IL: anchessa biiettiva (ad ognielemento di I fa corrispondere uno ed un solo elemento di L e viceversa).Pertanto, anche I equipotente a L (per la definizione).n


44/155

42

Ripercorreremo, in questo paragrafo, la costruzione dellinsieme quoziente.Dovremo inizialmente sviluppare tale procedimento nellambito degli insiemi finiti ;

escluderemo quindi dalle nostre considerazioni, in questa prima fase, gli insiemiinfiniti , dei quali ci occuperemo specificamente in seguito.Lintroduzione dei concetti di insieme finito e di insieme infinito si basa su di una

constatazione: in molti casi, un insieme non equipotente ad un suo sottoinsiemeproprio. Il lettore pu rendersi conto di ci verificando direttamente tale impossibilit:ad esempio, non si pu definire alcuna funzione biiettiva f : AB, essendo A = {0;1} e B il suo sottoinsieme proprio {1}.

Questo comportamento, per, non caratteristico ditutti gli insiemi: esistonoinfatti insiemi che sono equipotenti ad alcuni loro sottoinsiemi propri.

(Contro)esempio.Consideriamo linsieme P = {0; 2; 4; 6; 8; ...} dei numeri naturali pari (considerando pari anche lo zero) ed il suo sottoinsieme I = {2; 4; 6; 8; ...} deinumeri naturalipari e diversi da zero . Mostreremo che, sebbene I sia unsottoinsieme proprio di P, i due insiemi P e I sono equipotenti.

Consideriamo infatti la funzione f : PI cos definita:

f : x x+2

Tale funzione biiettiva: ad ogni x P corrisponde, infatti, attraverso la funzione f ,uno ed un solo x+2 I; viceversa, ad ogni elemento di I corrisponde uno ed un solo

elemento di P attraverso la funzione inversa: f 1: x x2

Pertanto P ed I sono equipotenti (per definizione); sottolineiamo ancora che I unsottoinsieme proprio di P: infatti :

P\I = {0}

Le definizioni di insieme finito e di insieme infinito si baseranno proprio sui duediversi comportamenti ora illustrati: in particolare, diremo finito ogni insieme che sicomporter analogamente a {0; 1}, diremo infinito ogni insieme che si comporteranalogamente a P. Possiamo dunque formalizzare quanto sopra introdotto nellaseguente definizione.


45/155

43

Definizione.Un insieme si diceinfinito se equipotente ad un suo sottoinsiemeproprio. Un insieme si dice finito se non equipotente ad alcun suo sottoinsieme

proprio.

Come sopra anticipato, concentriamo la nostra attenzione, in un primo momento,sugli insiemi finiti . Se indichiamo, come gi sopra fatto, con U un insieme avente perelementi insiemi (finiti ed infiniti), possiamo indicare con Uf U un insieme avente perelementi (soltanto) insiemi finiti . In Uf consideriamo la relazione di equipotenza trainsiemi: la dimostrazione della proposizione 1 (inizialmente formulata nel caso diinsiemi qualsiasi) assicura che tale relazione una relazione di equivalenza.

La cercata introduzione dellinsiemeN ora assai semplice: consideriamo infattile classi di equivalenza determinate in Uf dalla relazione di equipotenza; e

consideriamo, infine, linsieme quoziente avente tali classi di equivalenza comeelementi. Non difficile identificare ciascuna di tali classi di equivalenza con unnumero naturalen (intuitivamente: il numeron degli elementi appartenenti a ciascunodegli insiemi della classe di equivalenza); si dice che ogni elemento appartenente allaclasse di equivalenza in questione ha potenza (o cardinalit ) n. Linsieme quozientepu dunque essere interpretato come linsiemeN dei numeri naturali.

Il naturale zero dunque identificabile con la classe di equivalenza avente qualeunico elemento linsieme vuoto; potremo dire che linsieme vuoto ha potenza 0.

Esempio.Il numero naturale 2 si identifica con la classe di equivalenza (riferita allarelazione di equipotenza tra insiemi) alla quale appartiene linsieme I = {0; 1} epertanto anche tutti gli insiemi ad esso equipotenti (linsieme delle lenti di un comunepaio di occhiali, linsieme delle ruote di una bicicletta etc.).

Ogni insieme appartenente alla classe di equivalenza sopra indicata ha potenza 2.

6.2. I numeri naturali: approccio ordinale

Nel paragrafo precedente abbiamo descritto un possibile modo di introdurrelinsieme dei numeri naturali. Esso non per lunico: molto interessante, anche peralcune implicazioni applicative, il seguente, che viene fatto risalire (1891) alloperadi Giuseppe Peano (1858-1932). Egli propose unintroduzione assiomaticadellaritmetica, basata su tre concetti primitivi e su sei assiomi.

Nella teoria di Peano, cos come essa fu definitivamente enunciata in Aritmetica ,seconda parte del secondo volume diFormulaire de mathematiques (1898), i treconcetti primitivi sono:


46/155

44

lo zero ; ilnumero ;

il successivo.Gli assiomi sono:

Assioma zero.I numeri formano una classe. Assioma I.Lo zero un numero. Assioma II.Sea un numero, il suo successivoa+ un numero. Assioma III.Se s una classe contenente lo zero e, per ogni a, sea

appartiene as, il successivoa+ appartiene as, allora ogni numero naturale ins (Peano chiama tale proposizione principio di induzione ).

Assioma IV.Se a e b sono due numeri e se i loro successivia+, b+ sonouguali, alloraa e b sono uguali. Assioma V.Sea un numero, il suo successivoa+ non zero.

Osservazione.Sulla necessit dellAssioma zero notiamo che esso spiega chealla classe dei numeri naturali possiamo applicare il calcolo delle classi che Peanostesso aveva sviluppato precedentemente nel proprio libro.

La relazione introdotta da Peano dunque unapplicazione:aa+ avente perdominioN e per codominioN \{0}; si pu facilmente dimostrare che essa una

biiezione. Dall'esame di tali assiomi, e segnatamente ricordando il concetto disuccessivo, si pu dimostrare che Peano introduce inN un ordine stretto.Applicando opportunamente i propri assiomi, ed approntando le necessarie

dimostrazioni, Peano giunse ad introdurre le operazioni aritmetiche con i numerinaturali, nonch a descrivere ed a dimostrare le loro propriet formali.

Esempio. Sar interessante osservare che Peano introdusse una simbologiaoriginale. Gli assiomi sopra riportati, in tale simbologia, si scrivono:

0 N0 Cls1 0 N0 2 a N0 . . a+ N0 3 s Cls . 0 s : a s . a . a+ s : . N0 s Induct4 a , b N0 . a+ =b+ . . a = b 5 a N0 . . a+ -= 0


47/155

45

Osservazione.Dal punto di vista storico, Campano, nella sua traduzione-edizionedegli Elementi di Euclide (risalente alla seconda met delXIII secolo) introdusse

uninteressante assiomatizzazione dei naturali. Nella definizioneIII del libroVII,lAutore introduce come serie naturale dei numeri la successione numerica i cuielementi si ottengono per addizione ripetuta dellunit ( Naturalis series numerorumdicitur, in qua secundum unitatis additionem fit computatio ipsorum ) ed indicaalcune propriet dei naturali in quattro petitones (Labella, 2000).

6.3. La rappresentazione dei numeri naturali

La moderna rappresentazione dei numeri naturali, ottenibile mediante le dieci cifre 0,

1, 2, 3, 4, 5, 6, 7, 8, 9, viene detta posizionale in base dieci. Ci significa che ilvalore di ogni singola cifra che compone la rappresentazione di un numeron dipendedalla posizione di tale cifra in quella rappresentazione; il valore (totale)n del naturalerappresentato da una sequenza ordinata di cifre:

{am, am1, ...,a 2, a 1, a0}

calcolabile mediante lespressione:

n = am 10m + am1 10m1 + ... +a2 102 + a 1 101 + a 0 100

Esempio.Il valore del numero 35206 (scritto in notazione decimale, cio in basedieci) dato dalla somma:

3104 + 5103 + 2102 + 0101 + 6100 = 30000 + 5000 + 200 + 0 + 6

Osservazione.La storia della matematica registra, lungo il corso dei secoli, ilsusseguirsi di metodi diversi per la rappresentazione dei naturali. Il sistema di scritturadei numeri nelle matematiche del mondo antico (con leccezione dellaritmeticababilonese) non si avvale della notazione posizionale: il valore di un numero risultasemplicemente dalla somma dei valori associati ai simboli che, indicati uno di seguitoallaltro, vengono a costituire il numero stesso; tali valori sono fissi, cio nondipendono (a parte rare eccezioni) dalla posizione del simbolo nella scrittura delnumero. Una rappresentazione di questo genere per i naturali, dettaadditiva , caratteristica dellaritmetica romana.


48/155


49/155

47

Un confronto tra le operazioni aritmetiche di addizione e di moltiplicazione e leoperazioni insiemistiche di unione e di intersezione ci consentir di evidenziare

analogie (e differenze) che potranno essere utilmente riprese in studi ulteriori.Agli allievi ben noto, a partire dalle scuole primarie, che le operazioniaritmetiche di addizione e di moltiplicazione godono delle proprietassociativa ecommutativa ; cio per ogni scelta dei numeri naturalia , b, c risulta:

(a+b)+c = a+(b+c) (propriet associativa delladdizione)a+b = b+a (propriet commutativa delladdizione)(ab )c = a(bc) (propriet associativa della moltiplicazione)ab = ba (propriet commutativa della moltiplicazione)

Non sar inutile ribadire che anche le operazioni insiemistiche di unione e diintersezione godono di analoghe propriet, come precedentemente visto:

(A B) C = A (B C) (propriet associativa dellunione)A B = B A (propriet commutativa dellunione)(AB)C = A(BC) (propriet associativa dellintersezione)AB = BA (propriet commutativa dellintersezione)

Va segnalato che unanalogia tra le operazioni aritmetiche e insiemistiche deveper tenere presente alcune differenze; ad esempio, ricordiamo le due seguenti

propriet che coinvolgono sia lunione che lintersezione:A (BC) = (A B)(A C)A(B C) = (AB) (AC)

solo la seconda ha un analogo in ambito aritmetico (dettadistributiva ):

a(b+c) =ab +ac

mentre ci non accade per la prima: infattia+bc non (in generale) uguale a

(a+b)(a+c).Quanto ora osservato ci d loccasione di introdurre lealgebre di Boole (dalnome di George Boole). Come primo esempio, introduttivo ma fondamentale,consideriamo linsieme (I) delle parti di un insieme I.

Esempio.Sia ( (I), ) linsieme delle parti di un insieme I, parzialmente ordinatomediante la relazione di inclusione.


50/155

48

Dati due elementi di (I), A e B, possiamo costruire la loro intersezione, AB,e la loro unione, AB.

Dal punto di vista dellinclusione, AB il pi grande sottoinsieme di I incluso siain A che in B; ci si esprime dicendo che AB lunico sottoinsieme di I chesoddisfa:

(1) AB A e AB B(2) per ogni CA, C B si ha che CAB

Analogamente, AB il pi piccolo sottoinsieme di I in cui sono inclusi sia A cheB; ci si esprime dicendo che AB lunico sottoinsieme di I che soddisfa:

(1) A B A e A B B(2) per ogni DA, D B si ha che DA B

Analoghe operazioni possono essere introdotte anche in altri insiemi ordinati: adesempio, nel caso diN e della relazione di divisibilit, le operazioni risultano essere ilmassimo comune divisore e il minimo comune multiplo.

Generalizziamo ora quanto visto e consideriamo un insieme ordinato (X,).

Definizione.In un insieme parzialmente ordinato (X,) si dicemassimo comuneminorante ab per una coppia di elementi (a ; b) un elemento tale che:aba ,abb e per ognica , cb si ha checab.

Si dice minimo comune maggiorante a b un elemento tale che:a ba ,a bb e per ognid a , d b si ha ched a b.

Naturalmente la precedente definizione non assicura lesistenza, allinterno di uninsieme parzialmente ordinato (X,), di un massimo comune minorante e di unminimo comune maggiorante per ogni coppia di elementi di X.

Definizione.Un reticolo (X,, , ) un insieme parzialmente ordinato nel qualeper ogni coppia di elementi (a ; b) esistono un massimo comune minoranteab e unminimo comune maggiorantea b.

Applicando le definizioni si verifica facilmente che in un reticolo (X,, , ) ledue operazioni binarie, godono delle seguenti propriet:


51/155

49

aa = a a a = a ab = ba a b = b a

(ab)c = a(bc) (a b) c = a (b c)a(a b) =a a (ab) =a

Le definizioni seguenti introducono importanti tipi particolari di reticoli.

Definizione.Un reticolo (X,, , ) si dicedistributivo se per ognia , b, c X:

(a b)c = (ac) (bc)(ab) c = (a c)(b c)

Definizione.Un reticolo (X,, , ) si dice complementato se possiede unminimo che indicheremo con 0, un massimo che indicheremo con 1 e se per ognia X esistea X (dettocomplemento dia) tale che:

aa = 0 e a a = 1

Si dimostra (per assurdo) che in un reticolo distributivo con massimo e minimo ilcomplementoa di un elementoa , se esiste, unico.

Possiamo ora dare la definizione conclusiva.

Definizione.Si dicealgebra di Boole un reticolo distributivo complementato.

Esempio.Linsieme (I) delle parti di I con le operazioni di intersezione e diunione, presentato nel precedente esempio. unalgebra di Boole.

Esempio.Linsieme {0; 1} con le operazioni +,cos definite:

0+0 = 0 0+1 = 1+0 = 1 1+1 = 100 = 0 01 = 10 = 0 11 = 1

unalgebra di Boole.

Le stesse regole algebriche valgono per i connettivi logici dei quali tratteremo piavanti esplicitamente: infatti se, dato un insieme A consideriamo due suoisottoinsiemi, definiti mediante propriet, X={ x A|P ( x)} e Y={ y A| Q( y)}, si avr:


52/155

50

XY = { z A| P( z) e Q( z)}X Y = { z A| P( z) o Q( z)}

complementare di X X = { z A| non P( z)}Lo stesso comportamento si ha per le porte dei circuiti logici.Una porta or opera nel modo seguente:

ingressi uscita

0 0 00 1 11 0 1

1 1 1Una porta and opera nel modo seguente:

ingressi uscita

0 0 00 1 01 0 01 1 1

Una porta not opera nel modo seguente:

ingresso uscita

0 11 0

Nelle sezioni dedicate alla logica degli enunciati e alla logica dei predicati avremomodo di riprendere queste osservazioni.

7. DIMOSTRAZIONI PER INDUZIONE

7.1. Proposizioni dipendenti da un numero naturale


53/155

51

Frequentemente, in aritmetica, definizioni, esercizi e teoremi dipendono da un numero

n variabile nellinsiemeN dei naturali (o in un suo sottoinsieme). Ad esempio, unacelebre formula dellaritmetica quella che fornisce lasomma di tutti i naturali nonmaggiori di n , conn naturale fissato:

Sn =n n +( )1

2

Nellespressione precedente sono riassunte infinite somme di naturali, una perciascun indice naturalen. Verifichiamo la formula proposta in alcuni casi:

S0 =0 0 1

2 +( )

= 0 essendo: S0 = 0S1 =

1 1 12

+( ) = 1 essendo: S1 = 0+1 = 1

S2 =2 2 1

2 +( ) = 3 essendo: S2 = 0+1+2 = 3

S3 =3 3 1

2 +( ) = 6 essendo S3 = 0+1+2+3 = 6

Le considerazioni precedenti provano che la formula proposta valida finoallindicen = 3; ma appare evidentemente impossibile verificare direttamentetutte le

(infinite! ) somme di naturali ottenibili. Una dimostrazione completa della formulaproposta dovrebbe per prendere in considerazionetutti i casi possibili: essa,quindi, non pu essere tentata attraverso una verifica di ogni singolo caso,corrispondente ad ogni indice naturalen.

La dimostrazione di tale risultato pu essere impostata direttamente,considerando cio la formula generale, come illustrato nellesempio seguente.

Esempio.Sia n un numero naturale. Dimostriamo che la somma Sn di tutti i numerinaturali non maggiori din data dalla formula:

Sn = n n +( )12

Elenchiamo ordinatamente in una prima tabella di una riga tutti i naturali da 1 an (possiamo escludere lo 0, la cui addizione non modifica la somma):

1 2 3 4 ... (n2) (n1) n


54/155

52

In una seconda riga, elenchiamo i naturali considerati in ordine inverso:

1 2 3 4 ... (n2) (n1) n n (n1) (n2) (n3) ... 3 2 1

Se sommiamo in colonna le due righe scritte, otteniamo:

(n+1) (n+1) (n+1) (n+1) ... (n+1) (n+1) (n+1)

ovvero:n volte il numero (n+1). La somma di questin numeri,n (n+1), il doppiodella quantit Sn cercata, essendo stata ottenuta addizionando due volte ciascun

naturale compreso tra 1 en. Possiamo pertanto concludere che:

Sn =n n +( )1

2

Il procedimento illustrato ricordato in relazione ad un aneddoto riguardante CarlFriedrich Gauss (1777-1855) che, fanciullo, durante unesercitazione scolasticacalcol velocemente la somma dei naturali da 1 a 100 giungendo a:

S100 = 50502

)1100(100 =+

Questa dimostrazione elementare non per lunica possibile per la formula data.

7.2. Dimostrazioni per induzione

La regolarit osservata nel precedente paragrafo delle infinite dimostrazioni cheservirebbero a provare una propriet (o delle infinite espressioni che servirebbero afornire una definizione) sui numeri naturali ha portato a formulare un principio

generale che va sotto il nome diPrincipio di induzione . In sostanza esso affermache se una propriet vale per il primo numero e, valendo per un certo numero, alloravale anche per il successivo, allora vale per tutti i numeri (analogamente per ledefinizioni). Usiamo un tale principio anche nella logica di tutti i giorni quando ciriferiamo allinfinito come in frasi del tipo:

Il mio bambino sa contare


55/155

53

che vuol direTutti i numeri naturali sono conosciuti dal mio bambino

Naturalmente ci non vuol dire che il mio bambino abbia effettivamente nominatotutti i numeri naturali, e nemmeno li abbia pensati; ma egli in grado di cominciare laserie e, se qualcuno gli nomina un numero, di dire il successivo. Conosce, cio, loschema che permette di nominare qualunque numero a partire dal precedente. Lapermanenza dello schema al variare del numero considerato, permette di ridurre gliinfiniti passaggi necessarii a due soltanto.

Indichiamo dunque con il simboloP (n) una proposizione che vogliamo provare,sottolineando in tale modo che si tratta di unaffermazione dipendente dallindicenN. Presenteremo ora la dimostrazione per induzione diP (n) in due fasi distinte,

entrambe indispensabili : prima fase: si verifica direttamente la verit diP (0); nel caso in cui laproposizione da dimostrare valga pernn0>0, si verifica che essa valga peril minimo degli indici,n = n0;

seconda fase: si ammette la verit diP (n1) e, sulla base di ci, si dimostrache la proposizioneP vera anche per lindicen; ovvero: si prova che lavalidit della proposizione per un indice (qualsiasi) comporta la validit perlindice successivo.

Se possibile completare la verifica dientrambi i punti sopra illustrati, la

proposizioneP (n) pu dirsi dimostrata (pertutti gli indici n N): la prima fase,infatti, ci consente di affermare che la proposizioneP (n) vera pern = 0; sulla basedi ci, la seconda fase ci assicura cheP (n) vera anche pern = 1 (ovvero per ilsuccessivo di 0). Appurato ci, possiamo affermare cheP (n) vera anche pern = 2(per il successivo di 1) e cos di seguito per tutti gli indici naturali.

Illustriamo il procedimento dimostrativo attraverso un esempio nel qualeproporremo una dimostrazione alternativa della formula sopra provata.

Esempio.Sia n un numero naturale. Dimostriamo che la somma Sn di tutti i numerinaturali non maggiori din data dalla formula (gi proposta e dimostrata nel

precedente esempio):

Sn =n n +( )1

2

Procediamo per induzione sullindicen.


56/155

54

Prima fase : mostriamo che la formula verificata per il naturalen = 0. Risulta, inquesto caso: S0 = 0, e nella formula proposta: S0 =

0 0 1

2

+( ) = 0.Seconda fase : ammettiamo ora che la formula in questione sia verificata per

lindice (n1); ammettiamo cio che sia vera:

Sn-1 =( )n n 1

2

Dovremo, sulla base di ci, provare la validit della formula anche per lindicen.Ricaviamo dunque Sn (utilizzando quanto sopra ammesso):

Sn = Sn-1 + n =( )n n 1

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

2 =n n +( )1

2

Pertanto la validit della formula per lindice (n1) comporta la validit dellaformula per lindicen. Ci, unito alla provata validit della formula pern = 0,completa la dimostrazione per induzione.

Nella sezione precedente abbiamo anticipato una propriet dellinsieme delle partidi un insieme dato, propriet che riprendiamo nellesempio seguente.

Esempio.Sia I un insieme al quale appartengonon elementi (avente cardinalitn).Dimostriamo che linsieme delle parti di I,(I), contiene 2n elementi (ha cardinalit2n).

Per comodit di notazione, indichiamo con #(I) la cardinalit dell'insieme I;procediamo per induzione sun.

Prima fase : sen = 0, allora : I = e dunque #( (I)) = #({ }) = 1 = 20. Latesi quindi valida per questo primo caso.

Seconda fase : Ammettiamo la validit della tesi da dimostrare qualora I siacostituito dan1 elementi, dunque quando sia #(I) =n1; cio ammettiamo che sia#( (I)) = 2n1.

Sia oraa I; consideriamo quindi linsieme I{a} la cui cardinalit n. Qual lacardinalit di (I {a})?Ricordiamo che (I {a}) costituito da tutti i sottoinsiemi (propri e impropri)

di I {a}. Elenchiamo tali sottoinsiemi in una tabella nel modo seguente: nella primacolonna scriviamo tutti i sottoinsiemi di I{a} ai quali non appartienea (in pratica:tutti e soltanto i sottoinsiemi di I):, B, C, D, ..., I; in una seconda colonna,


57/155


58/155

56

[(n+1)(n1)][(n+1)+(n1)] = 4n (n+1)2(n1)2 = 4n

che la formula che si doveva dimostrare. La precedente dimostrazione ancora inaccettabile in quanto incompleta :

manca infatti lindispensabile verifica della formula da provare pern = 0.Verifichiamo la formula proposta pern = 0:

(0+1)2(01)2 = 11 = 0 = 40

La tesi dunque verificata in questo primo caso. A questultima verifica puessere fatto seguire quanto sopra stabilito: ci completa la dimostrazione per

induzione sun.Osservazione.La formula proposta in questultimo esempio avrebbe potuto esseredimostrata anche direttamente (e forse facendo meno fatica), senza ricorrere alladimostrazione per induzione: sarebbe stato infatti sufficiente sviluppare i quadrati alprimo membro.

Notiamo infine che se non fossimo ancora convinti che il principio di induzione cipermette di raggiungere tutti i casi possibili, potremmo ragionare come segue:supponiamo che esista un numerom per il quale, nonostante la dimostrazione per

induzione,P (m) non sia valida. Intantom non pu essere lo 0, perch sappiamo cheP(0) vera per la prima condizione. AlloraP (m) non sarebbe vera per un numeropi grande di 0; ma allora non sarebbe vera nemmeno per il caso precedente,diciamoP (m1), perch la seconda condizione ci assicura che la verit diP (m1)implica la verit diP (m). Cos, a ritroso,dopo un numero finito di passi ,proveremmo la falsit diP (0).

Come si vede, il principio di induzione si fonda sul fatto che nei numeri naturali sipu andare sempre avanti con la funzione successore, ma dato un numero, da questosi torna allo 0 in un numero finito di passi.

Questa osservazione ci permette di formulare il principio in modo diversi, ma chesottintendono sempre in realt la struttura dei numeri naturali.

Una prima apparente generalizzazione il seguente principio: Se valeP (0) e, seper ognin


59/155

57

precedente (la dimostrazione formale si potr fare come esercizio una volta studiato ilcalcolo degli enunciati). In realt sui numeri naturali i due principi sono equivalenti.

Abbiamo un altro caso che utilizzeremo spesso in logica, che introdurremo conlesempio seguente.

Esempio.Supponiamo di dover provare che ogni numero decomponibile in unprodotto di fattori primi. In questo caso l'induzione non pu essere applicatadirettamente ai numeri in quanto tali, perch nel passaggio da un numero alsuccessore la situazione e la dimostrazione cambiano drasticamente. Dovremo alloratrattare i nostri numeri come oggetti ai quali assegnato un altro numero che devevariare in modo da rendere parametrica la dimostrazione. Possiamo pensare diassociare ad ogni numero un albero di decomposizione, cio porre il numero alla

radice dell'albero e, se possibile, generare due figli, usando una possibiledecomposizione non banale del numero:

12 / \

4 3

Abbiamo due possibilit: o il numero gi primo e ci fermiamo al primo nodo(radice), o si pu decomporre in due fattori diversi da 1 e da lui stesso; a questopunto il gioco si ripete per i due fattori e deve terminare prima o poi perch i fattori

ogni volta sono strettamente minori del numero dato e perci, prima o poi cifermeremo.

Abbiamo cos costruito in un numero finito di passi un albero binario con ilnumero dato alla radice. Associamo allora al numero originario un altro numero,l'altezza dell'albero, cio il numero massimo dei passi che occorrono per andare dallaradice ad una foglia (nodo senza figli); proviamo allora che qualunque sia l'altezzadell'albero, il numero dato il prodotto dei numeri primi che sono sulle foglie. Sedunque lalbero associato al numero ha altezza 0 vuol dire che il numero dato era giprimo e siamo arrivati; supponiamo che la propriet sia vera per numeri che hanno unalbero di decomposizione di altezzan e dimostriamolo per per numeri che hanno unalbero di decomposizione di altezzan+1. Per un tale numeron esistono due numeripi piccolir ed s tali chen = rs ed essi hanno un albero di decomposizione di altezzaal pi n. Quindi per essi vale il fatto che sono decomponibili in numeri primi; maallora il prodotto delle due decomposizioni sar una decomposizione din.

Questo modo di procedere si dice perinduzione strutturale ed operasostanzialmente associando ad oggetti (non necessariamente numeri) che sono


60/155

58

decomponibili in oggetti pi semplici, un numero naturale che ne rappresenta lacomplessit, in modo che le componenti abbiano un numero pi piccolo. La

dimostrazione avverr poi per induzione su questi indici di complessit. Talvolta,quando la diminuzione della complessit sar evidente, si potr addirittura ometteredi specificare l'indice.

8. I NUMERI PRIMI

8.1. Divisibilit e numeri primi

In questa sezione presenteremo le principali nozioni collegate ai numeri primi edindicheremo alcune dimostrazioni; in particolare:

ci chiederemo innanzitutto: che cosa sono i numeri primi? Daremo ladefinizione e illustreremo il crivello di Eratostene. Mostreremo lesistenza elunicit della scomposizione in fattori primi di un numero naturale.

inoltre, quanti sono i numeri primi? Come essi sono distribuiti nella sequenzadei numeri naturali?

daremo quindi alcuni risultati: una condizione necessaria di primalit (teoremadi Fermat); una condizione necessaria e sufficiente di primalit (teorema di

Wilson). presenteremo infine alcuni problemi aperti, come le congetture di Goldbach edei primi gemelli.

Iniziamo a presentare la nozione di divisibilit.

Definizione.Un naturalea si dice divisibile per un naturaleb se esiste unnaturalec tale chea = b c. Si dice allora cheb undivisore dia . Si scrive:b|a .

Si tratta di una nozione elementare: su di essa si basano tecniche e concetti diprimaria importanza. La illustreremo con alcuni esempi.

Esempio.Dimostriamo che la somma di cinque numeri naturali consecutivi sempredivisibile per 5.

Indicati infatti i numeri in questione con:a , a+1,a+2,a+3,a+4, la loro somma :

a+(a+1)+(a+2)+(a+3)+(a+4) = 5a+10 = 5(a+2)


61/155

59

e tale naturale, avendo 5 come fattore, divisibile per 5.

Esempio.Dati tre numeri naturali non nulli tali che la differenza tra il secondo ed ilprimo e la differenza tra il terzo ed il secondo sia 2, dimostrare che uno di essi divisibile per 3.

Sianon, n+2,n+4 i tre naturali in questione, conn 0.La dimostrazione pu essere scritta sinteticamente utilizzando le congruenze

(ricordiamo chea b (modn) significa chen divideba):

se n 0 (mod 3), allora la tesi subito provatase n 1 (mod 3), alloran+20 (mod 3)se n 2 (mod 3), alloran+40 (mod 3)

Altrimenti necessario esprimere diversamente il ragionamento (la dimostrazionepu apparire meno chiara): sen divisibile per 3, la tesi subito provata. Sen non divisibile per 3, effettuando tale divisione avremo un resto non nullo che potr esserer = 1 oppurer = 2. Se r = 1, alloran+2 divisibile per 3; se r = 2, alloran+4 divisibile per 3.

Esempio.Per alcuni naturali non nullin, m, possibile chen sia divisore dim econtemporaneamentem sia divisore din: ci accade se (e solo se) n = m.

Se n divisore dim e m divisore din scriviamo:

m = b n e n = a m (1)

cona , b naturali (diversi da zero, essendo, per ipotesi, diversi da zero i naturali datin, m). Scriviamo allora:

n m = (a m) (b n) =a b m n a b = 1

Tale prodotto di naturali verificato solamente nel caso:a = b = 1. Possiamoconcludere allora, sostituendo nella formula (1), che:n = m.

Esempio.Sianoa , b due naturali multipli del naturalen (n0): dimostriamo che ogninaturale della forma a+ b, con, naturali, anch'esso multiplo din.

Se a e b sono multipli din, esistono due naturalih, k tali che:

a = h n b = k n


62/155


63/155


64/155

62

Dimostrazione (Lindemann). Chiamiamonumeri anormali i numeri che possonoessere fattorizzati in prodotti di primi in pi modi (a parte permutazioni). Sian il

minimo numero anormale.Lo stesso primo p non pu apparire in due diverse fattorizzazioni din: se cosfossen / p sarebbe anormale en / p < n, contro la minimalit din. Allora:

n = p1 p2 p3 =q1q2q3

dove i p e i q sono primi, nessun p uguale a unq e nessunq uguale a un p.Sia p1 il minimo dei p; risulta: p1 n.Siaq1 il minimo deiq; risulta:q1 n.Da ci, ricordando che p1 q1: p1q1 < n.

Se poniamo N = n p1q1 abbiamo che 0< N


65/155

63

Dimostrazione. Sia p1, p2, , p r unassegnata quantit di numeri primi.Poniamo:P = p1 p2... pr +1 e sia p un numero primo che dividaP ; allora p non pu

essere alcuno dei p1, p2, , p r , altrimenti p dividerebbe la differenzaPp1 p2... pr =1 che impossibile. Dunque questo p un altro primo, e p1, p2, , p r non sono tuttii numeri primi.n

Proposizione (Euler).La serie dei reciproci dei numeri primi diverge.

Ci permette di far seguire immediatamente il risultato euclideo: se linsieme deinumeri primi fosse finito, tale sarebbe anche la somma dei reciproci di tutti i primi (ladimostrazione di L. Euler che riporteremo nellappendice C si pu trovare in:Tenenbaum & Mends France, 1997; per unelegante dimostrazione di P. Erds si

pu vedere: Aigner & Ziegler, 1998).Un classico problema riguarda la distribuzione dei primi tra i numeri naturali. Perogni naturalen, sia An il numero di primi non maggiori din. Ad esempio:

A1 = 0 (nessun primo minore o uguale a 1)A2 = 1 il primo considerato 2A3 = 2 i primi considerati sono 2, 3A4 = 2 i primi considerati sono 2, 3A5 = 3 i primi considerati sono 2, 3, 5 etc.

Consideriamo ad esempio la successione din 103, 106, 109, e la tabella:

n An / n 1/logn (An / n)/(1/logn)

103 0,168 0,145 1,159106 0,078 0,062 1,084109 0,050 0,048 1,053

Sulla base di una verifica empirica Gauss ipotizz che:

1log

1lim =+n

n Ann

La dimostrazione completa di ci venne data nel 1896 (da Hadamard e de laValle Poussin).


66/155

64

8.4. Condizioni di primalit

Enunciamo ora alcune classiche condizioni di primalit.Una condizione necessaria affinch un numero naturale sia primo espressa dal

piccolo teorema di Fermat (dimostrato da Euler).

Proposizione.Sea un intero e p un numero primo:a pa 0 (mod p).

Dunque: se p un primo,a pa un multiplo di p. Una sua diversa formulazione:se p un primo che non dividea , alloraa p11 un multiplo di p (il lettore invitatoa fare qualche verifica).

La precedente condizione necessaria, ma non sufficiente: dunque tutti i numeriprimi certamente soddisfano quanto espresso dal piccolo teorema di Fermat, ma nontutti i numeri che soddisfano tale condizione sono primi.

Una condizione necessaria e sufficiente espressa dalteorema di Wilson (risalente al 1770, poi dimostrato da Lagrange e da Euler):

Proposizione.( p1)!+10 (mod p) se e solo se p un numero primo.

Dunque: ( p1)!+1 un multiplo di p se e soltanto se p un primo.Pu essere interessante fare qualche verifica. Occupiamoci ad esempio del

numero primo 7: (71)!+1 = 721 un multiplo di 7 (7103); ma gi la verificarelativa ai primi successivi (11, 13) appare difficoltosa per il calcolo del fattoriale (illettore provi a calcolare 10! e 12!). E nel caso di applicazione a primi pi grandi, ilcalcolo del fattoriale si rivela un ostacolo molto serio.

Il teorema di Wilson quindi un risultato elegante e importante, ma praticamenteben poco utile, in quantonon conosciamo alcun algoritmo in grado di calcolareil fattoriale con sufficiente rapidit! Da ci segue che la velocit di un test diprimalit basato sul teorema di Wilson sarebbe minore di quella di un test basato sulcrivello di Eratostene.

Molte formule sono basate sul teorema di Wilson; ad esempio la formula diWillans (1964) fornisce il numero primon-esimo:


67/155


68/155

66

Dimostrazione. Sia P linsieme dei numeri naturali pari:

P = {m N: m=2n e n N}

Per dimostrare che P, sottoinsieme proprio diN, equipotente aN, necessarioindividuare una funzione biiettiva f : PN. Tale funzione :

logica matematica (155)

Documents

Transcript of logica matematica (155)