APPUNTIEDESERCIZIDIMATEMATICADISCRETAMargherita RoggeroA.A.2005/2006M.Roggero-AppuntiedEsercizidiMatematicaDiscretaIntroduzioneQuestenotecontengonogliappuntidelcorsodiMatematicaDiscretadelprimoannodellaLaureatriennaleinMatematicadellA.A.2005/06.Gli argomenti sonoquasi semprepresentati nellostessoordineeconlostessogradodiapprofondimentoconcuisonopresentatialezione,percuiilcontenutodiquestenotepu`oessereconsideratoatuttiglieettiilprogrammadesame.Gli esercizi chesi trovanoal terminedi ogni capitolononsonoinvece, ingenerale,glistessichevengonosvoltidurateleorediesercitazioneinclasse,puressendoditipoegradodidicolt`adeltuttoanaloghi;loscopo`equellodilasciareallostudente,durantetutta la durata del corso, materiale per quel momento di lavoro autonomo, che riteniamoindispensabile per un ecace ed eettivo apprendimento (e controllo della comprensione)degliargomentiteoriciarontatialezione.Inne, gli esercizi di riepilogoproposti nellultimocapitolosonoripresi dacompitidesameeintendonofornireallostudente,oltrealloccasioneperunavericanaledellapreparazione,ancheunsaggiodirettodiquantovienerichiestoinsededesame.Dialcunidiquestiesercizi `efornitaancheunapropostadirisoluzione.Desideroringraziaretutti colorochemi hannoaiutatodurantelastesuradi questiappunti, in modo particolare il Dott. Mario Valenzano, per laccurato lavoro di revisione,eilDott.AndreaMori,cuisidevonomoltideglieserciziproposti.Universit` adiTorinoIndice1 Illinguaggiodegliinsiemi 51.1 Insiemiedelementi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Sottoinsiemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Unione,intersezione,complementare . . . . . . . . . . . . . . . . . . . . . 71.4 Insiemedellepartiepartizioni . . . . . . . . . . . . . . . . . . . . . . . . . 81.5 Prodottocartesiano. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.6 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Corrispondenzeerelazioni 132.1 Corrispondenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Relazionidordine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3 Relazionidiequivalenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 Lefunzioni 223.1 Generalit`asulleapplicazioniofunzioni . . . . . . . . . . . . . . . . . . . . 223.2 Funzionicomposte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Funzioniinverse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 NumerinaturalieCardinalit`a 334.1 Linsiemedeinumerinaturali Nelinduzione. . . . . . . . . . . . . . . . . 334.2 Lacardinalit`adiuninsieme . . . . . . . . . . . . . . . . . . . . . . . . . . 364.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 Elementidicalcolocombinatorio 415.1 Permutazioniedisposizioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.2 Combinazioniebinomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.3 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476 Lanellodeinumeriinteri 496.1 Costruzionedellinsiemedeinumeriinteri. . . . . . . . . . . . . . . . . . . 496.2 Generalit`asuglianelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506.3 Ladivisioneeuclidea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543M.Roggero-AppuntiedEsercizidiMatematicaDiscreta6.4 Ilteoremafondamentaledellaritmetica. . . . . . . . . . . . . . . . . . . . 576.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597 Glianellidelleclassidiresto 617.1 Denizioneeprimepropriet`adi Zn. . . . . . . . . . . . . . . . . . . . . . 617.2 Congruenzeesistemidicongruenzelineari . . . . . . . . . . . . . . . . . . 637.3 LafunzionediEulero. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677.4 Crittograa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 697.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738 Ilcampo Qdeinumerirazionali 768.1 Costruzionedellinsiemedeinumerirazionali . . . . . . . . . . . . . . . . . 768.2 Lanotazioneposizionaledeinumerirazionali . . . . . . . . . . . . . . . . . 788.3 Generalit`asuipolinomi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808.4 Polinomiacoecientiinterierazionali . . . . . . . . . . . . . . . . . . . . 838.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 859 Ilcampo Rdeinumerireali 879.1 Cenniallacostruzioneformaledeinumerireali . . . . . . . . . . . . . . . . 879.2 Scritturadeinumerireali. . . . . . . . . . . . . . . . . . . . . . . . . . . . 919.3 Numerialgebricienumeritrascendenti . . . . . . . . . . . . . . . . . . . . 929.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9510Ilcampo Cdeinumericomplessi 9710.1 Laformaalgebricadeinumericomplessi . . . . . . . . . . . . . . . . . . . 9710.2 IlTeoremaFondamentaledellAlgebra . . . . . . . . . . . . . . . . . . . . 9910.3 Formapolareotrigonometricadeinumericomplessi . . . . . . . . . . . . . 10210.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10511Esercizidiriepilogo 10812Risposteadalcuniesercizi 11912.1 Qualcheeserciziosvolto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12713Appendice:Contributideglistudenti 13013.1 Relazionidordine. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13013.2 Insiemiinniti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13013.3 Binomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13113.4 SistemidiCongruenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132Universit` adiTorinoCapitolo1Illinguaggiodegliinsiemi1.1 InsiemiedelementiIndicheremoabitualmentegliinsiemiconletteremaiuscoleA, B, . . . eglielementidiuninsiemeconlettereminuscole.(Notabene:NONdiamounadenizioneformalediinsieme.)a `eunelementodellinsiemeAsiscriveinsimbolia AesileggeaappartieneadA.Idea intuitiva: un insieme `e costituito e caratterizzato esclusivamente dai suoi elementi,ossia:dueinsiemisonougualiseesolosecontengonoglistessielementi.Pur nonavendoli ancoradeniti inmodorigoroso, useremogi`adaoragli insieminumerici N (numeri naturali), Z (numeri interi relativi), Q (numeri razionali) ed R (numerireali),soprattuttoperpotercostruirequalcheesempiosignicativo.Uninsiemepu`oessereassegnatoelencandoisuoielementi.Esempio1.1.1. A = 0, 1`elinsiemecostituitodaiduenumeri0e1.Unaltro modo per assegnare uninsieme `e quello di indicare una sua propriet`acaratteristicaossiaunapropriet`asoddisfattadatutti gli elementi dellinsiemeesolodaessi:B= x X [xsoddisfalapropriet`aP.Sesiusalapropriet`acaratteristica:- `e semprenecessarioindicare esplicitamente linsiemeXdeglielementidaprendereinconsiderazione;-lapropriet`aPusatanondeveessereinalcunmodovagaoambigua.Esempio1.1.2. Nonhannoalcunsensoespressioniquali:X= multiplidi2,Y= numerinaturaligrandi,Z= soluzionidellequazionex41 = 0.LinsiemeV= x R [x2+ 1 = 0`einveceperfettamentedenito.56 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaPoiche nessun numero reale ha quadrato negativo, linsieme Vora considerato `e privodielementi:V sichiamainsiemevuotoesidenota .Linsiemevuoto `eunico: x R [x2+ 1 = 0 = = n N [n > n.Nei paragra successivi vedremo come a partire da insiemi noti se ne possano costruirealtrimediantealcunecostruzionistandard(unione,intersezione,complementare,insiemedelleparti,prodottocartesiano,quoziente).PerindicarecheunelementoanonappartieneaduninsiemeAscriviamoa/ A.Presounqualsiasi elementoa, anonappartiene allinsieme vuoto. Insimboli: a:a/ .signicaperogni,ogni,pertutti. . .Adeccezionedellinsiemevuoto,tuttiglialtriinsiemicontengonoqualcheelemento.Insimboli:A ,= atalechea A.Ilsimbolo signicaesiste,c`ealmenoun/o/a...;avoltesiusaancheilsimbolo!colsignicatodiesisteunoedunsolooesisteununico.si leggeseesoltantoseesignicachelaermazionecheloprecedeelaf-fermazionecheloseguesonoequivalenti ossiachesonoentrambevereoppureentrambefalse.1.2 SottoinsiemiSi dicechelinsiemeA`eunsottoinsiemedellinsiemeB, oppurecheA`econtenutoinB,seesoloseognielementodiA `eancheelementodiB.Insimboli:A B (a A =a B).Il simbolo=si leggeimplica. SeF1eF2sonodueaermazioni, limplicazioneF1=F2signicachese(oppureognivoltache)laermazioneF1`evera,allora`everaancheF2.Quindilimplicazione`ecorrettaquandoF1eF2sonoentrambevereedanchequandoF1`efalsa(indipendentementedalfattocheF2siaveraofalsa).Esempio1.2.1. Limplicazione n N(n > 3 =2n`epari)`ecorretta.Invece n N(n>3=n2>20)`efalsapercheesistealmenouncasoincui laprimaaermazione`everaelasecondano:4 > 3,ma42 20.NOTA BENE: Unaaermazione `everaseesoltantose `everaintuttiicasi;ladimostrazione deve comprendere tutti i casi possibili e nonsoltantoalcunicasiparticolari.Una aermazione `e falsa se e solo se `e falsa in almeno un caso; per provarlo`esucienteesibireesplicitamenteuncontroesempio.Universit`adiTorinoCapitolo1Illinguaggiodegliinsiemi 7Linsieme vuoto `e sottoinsieme di ogni insieme; ogni insieme `e sottoinsieme di se stesso:seA `euninsieme,allora AeA A.1.3 Unione,intersezione,complementareDenizione1.3.1. SianoA,B,Cinsiemi.Si diceunionedi AeBesi denotaA Blinsiemei cui elementi sonotutti glielementichestannoinalmenounotraAeB:x A B (x Aoppure x B).Si diceintersezionedi AeBesi denotaA Blinsiemei cui elementi sonotutti glielementichestannocontemporaneamenteinAeinB:x A B (x Aex B).DueinsiemiAeBsidiconodisgiuntiseA B= .Lunione e lintersezione di insiemi non dipendono dallordine in cui gli insiemi vengonoconsideratiesoddisfanoleseguentipropriet`adistributive:(A B) C= (A C) (B C) (A B) C= (A C) (B C).Esempio1.3.2. SianoA = x R [x21 = 0eB= x R [x2+ 3x + 2 = 0.Allora:A B= x R [(x21)(x2+ 3x + 2) = 0A B= x R [_x21 = 0x2+ 3x + 2 = 0 Unione,intersezioneerelativepropriet`apossonoesseregeneralizzatiafamigliequal-siasidiinsiemi.Denizione1.3.3. SiaIuninsiemenonvuotoe,perognii I,siaAiuninsieme:a _iIAi (i It.c.a Ai), a

iIAi (i Isiha a Ai).Esempio1.3.4. Il dominiodellafunzionerealedivariabilerealey= tan(x)`e:_kZ(2+ k,2+ k).Esempio1.3.5. Perognin NindichiamoconAnlinsiemedeinumeriinterirelativichesonomultiplidin.Allora

nNAn= 0 e

nNAn= Z.QuaderniDidatticidel DipartimentodiMatematica8 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDenizione1.3.6. SianoXuninsiemeeAunsuosottoinsieme.Sidicecomplemen-tare di AinXe si indica con (X(A) linsieme di tutti gli elementi di Xche nonappartengonoadA:(X(A) = x X [x/ A.Il complementaredi Asi denotaanchecon ((A)sedal contesto`echairoqualeinsiemeXsistaconsiderando.Linsiemecomplementare (X(A) `elunicoinsiemechevericaleduecondizioniA (X(A) = e A (X(A) = X.ValgonoinoltreleLeggidiDeMorgan:seAeBsonosottoinsiemidiX,allora:(X(A B) = (X(A) (X(B) e (X(A B) = (X(A) (X(B).Propriet`a analoghe valgono relativamente ad unioni ed intersezioni di famiglie di insiemi.Denizione1.3.7. DatigliinsiemiAeB,sidiceinsiemedierenzadiBedA,esidenotaB A, linsiemeformatodatutti gli elementi di BchenonappartengonoadA,ossia:x B A x Bex/ A ovvero B A = (AB(A).1.4 InsiemedellepartiepartizioniGliinsiemipossonoalorovoltaessereconsideraticomeelementidialtriinsiemi.Esempio 1.4.1. Linsieme A= 1, 2, 3hadue elementi: il numero1e linsiemeformatodainumeri2e3.LinsiemeX= 5, 5hadueelementi:ilnumero5elinsiemecheha5comeunicoelemento(uninsiemecome 5chehaunsoloelementosidiceanchesingleton).Denizione1.4.2. SidiceinsiemedellepartidiuninsiemeX,linsieme T(X)icuielementisonoisottoinsiemidiX:A T(X) A X.Attenzioneallenotazioni:a A a A a T(A).Esempio 1.4.3.Sia A = 0, 5, 7. Allora T(A) = , 0, 5, 7, 0, 5, 0, 7, 5, 7, A.Linsieme delle parti di uninsieme non`e mai linsieme vuotopoiche inogni casocontienealmenolelemento .Inparticolare T() = ha1elemento.Se X`e un insieme con n elementi, linsieme delle parti T(X) ha 2nelementi. Vedremoinseguitounadimostrazione(anzitrediversedimostrazioni)diquestaaermazione.Universit`adiTorinoCapitolo1Illinguaggiodegliinsiemi 9Denizione 1.4.4.Si dice partizione di Xuna famiglia di suoi sottoinsiemi tali che:- nessunodiessi`evuoto,- sonodueaduedisgiunti,- lalorounione`etuttoX.Inmodopiuformalepossiamodirecheunapartizione Qdi X`eunsottoinsiemediT(X)taleche:- / Q- Y, Y

QsihaY Y

= oppureY= Y

-

Y QY= X.Uninsieme QsiattosidiceanchequozientediX.Esempio1.4.5. a. IsottoinsiemiP= n Z [n`eparieD= n Z [n`edisparicostituisconounapartizionedi Z.Il quoziente Q = P, Dhadueelementi.b. I sottoinsiemi A = n Z [n < 0, B= 0, 1, 2 e C= n Z [n 3 costituisconounapartizionedi Z.Il quoziente Q = A, B, Chatreelementi.c. Perogninumeronaturalek 1siconsideriil sottoinsiemeYkdi Ndenitoda:Yk= x N [ lanotazioneposizionaledixinbase10hakcifre.I sottoinsiemi Ykformano una partizione di N. Il quoziente Q = Yk [k N, k 1hainnitielementi.d. I sottoinsiemi Yp= x Z [x `e multiplo di p, al variare di p nei numeri primi positividi Z, noncostituisconounapartizionedi Z, poichelalorounionenoncontieneilnumerointero1(oppureperchenonsonodueaduedisgiunti).Il Paradossodi Russell.Secondoladenizioneinformale-intuitivapercui uninsieme`edatosemplicemente dai suoi elementi (senza ulteriori condizioni), risulta essere un insieme anche quelloi cui elementi sonotutti i possibili insiemi: indichiamountaleinsieme conX. Per Xvalelastrana proprieta:X X.Potremmo allora classicare tutti gli insiemisecondo i due tipi:- insiemiA tali cheA/ A- insiemiA tali cheA A.Gli insiemi del primo tipo formano un sottoinsieme YdiX. A quale dei due tipi apparterr`aY ?SeY YalloraY`e un insieme del primo tipo e quindiY / Y .Daltra parte seY / Y , alloraY`e un insieme del secondo tipo ossiaY Y .Daquestacontraddizionenonc`eviaduscita, senonquelladi denirecongrandeattenzioneilconcetto di insieme, in modo da evitare che cosecomeXeYsiano degli insiemi.QuaderniDidatticidel DipartimentodiMatematica10 M.Roggero-AppuntiedEsercizidiMatematicaDiscreta1.5 ProdottocartesianoDenizione1.5.1. SianoA,B,A1, . . . , Aninsiemi.Si diceprodottocartesianodi AeBesi denotaABlinsiemei cui elementisonolecoppieordinate(a, b)doveavariatratutti gli elementi di AebtraquellidiB:A B= (a, b) [a A, b B.(Osserviamochelacoppiaordinata(a, b)pu`oesseredenitainmodorigorosonellinguaggiodegli insiemi comelinsieme a, b,a , diversodallinsieme a, b,b checorrispondeallacoppia(b, a).)Analogamente il prodotto cartesiano di A1, . . . , An `e linsieme delle nuple di elementipresiordinatamenteunoinciascuninsieme:A1A2 An= (a1, a2, . . . , an) [ a1 A1, a2 A2, . . . , an An.SeA ,= eB ,= ,alloraancheA B ,= .Infattiesistealmenounelementoa0 Aealmenounelementob0 Bequindiilprodottocartesianocontienealmenolelemento(a0, b0).Lostessovaleperilprodottocartesianodininsieminonvuoti.Deniremoinseguitoil prodottocartesianodi unafamigliaqualsiasi di insiemi (cfr.Esempio3.1.6g.).1.6 EserciziGli esercizi contrassegnati conunasterisco, inquestoenei capitoli seguenti,sonodiunadicolt`amaggiorerispettoaglialtri.Nei seguenti problemi A, B, C, . . . denotano sottoinsiemi arbitrari di un insieme Xssato.1.1. SianoX = R,A = x R [x2+x 2 = 0,B = 1, 1, 2 eC = 1, 2, 3.a. Determinare linsieme delle parti diBe linsieme delle parti diC.b. Dire quali delle seguenti aermazioni sono vere e quali false:1 , A 1 C 1 A 2 C 1 A 3 C1 A 1 C A B 2, 3 C B A 2 C1.2. SianoX = N,A = x N [x < 20 eB = x N [x 10. Calcolare:A B, A B, A B, B A, (X(A), (X(B).1.3. SianoX= R, Y= x R [x 3 eZ= x R [ 5 x< 21. Determinare (R(Y Z), (R(Y ),(R(Z) e vericare che (R(Y Z) = (R(Y ) (R(Z).1.4. Provare che le seguenti aermazioni sono false esibendo dei controesempi espliciti:Universit`adiTorinoCapitolo1Illinguaggiodegliinsiemi 11i) A B = A C =B = C;ii) (B A) C = B (A C);iii) A (X(B) = (X((X(A) B).1.5.Enunciareevericarelepropriet`adistributiveperlunionenitaelintersezionenitadiinsiemi.Generalizzare allunione e intersezione di famiglie qualsiasi di insiemi.1.6.EnunciareevericareleLeggi di DeMorganperlunionenitaelintersezionenitadi insiemi.Generalizzare allunione e intersezione di famiglie qualsiasi di insiemi.1.7.SianoX= R, Y = x R [x aeZ= x R [b x2intermini dei sottoinsiemiA = x R [x < 0,B = x R [x > 1.1.31. Esprimere linsieme delle soluzioni reali della disequazione x21 > x 2 in termini dei sottoin-siemiA = (1, 1),B = x R [x > 5/4 eC = x R [x < 2.1.32. Si generalizzi la discussione del problema precedente esprimendo linsieme delle soluzioni reali delladisequazione _P(x)>Q(x)interminidegliinsiemi A= x R [P(x) 0, B= x R [P(x)>Q(x)2 eC = x R [Q(x) < 0.1.33. SiaXlinsieme dei punti del piano cartesianoOxy.i) Provare che le rette parallele allassex formano una partizione del pianoX.ii)`E vero che le rette passanti per lorigine formano una partizione diX?iii) Si pu`o ottenere una partizione del piano mediante circonferenze con centro nellorigine?1.34.SianoA= 1, 0, 1eB= 1, 2. ScrivereesplicitamenteAB, AA, (AA) (AB),A(A B), (AA) (AB),A(A B), T(B B) e T(B) T(B).1.35. SianoA, Bdue insiemi non vuoti e siano A1, A2 una partizione diA, B1, B2 una partizionediB.i) Provare che A1B1, A2B2 non `e una partizione diAB.ii) Provare che A1B1, A1B2, A2B1, A2B2 `e una partizione diAB.iii) Mostrare che esistono sempre altre partizioni diABoltre a quella del punto ii).Universit`adiTorinoCapitolo2Corrispondenzeerelazioni2.1 CorrispondenzeDenizione2.1.1. SianoA,Bdueinsiemi.SidicecorrispondenzadaAaBunqualsiasisottoinsiemeRdel prodottocartesianoA B.SeA = B,unacorrispondenzainA AsidiceancherelazioneinA(oinA A).Per indicare che una certa coppia appartiene alla corrispondenza R, invece che (a, b) R,usualmentescriveremoaRbediremochea `eincorrispondenzaconb.Esempio2.1.2.- SianoA= 1, 4, 17eB= 0, 1, 2. Il sottoinsiemeR= (1, 1), (4, 0), (4, 1)diA B`eunacorrispondenzadaAaB.- LinsiemeT= (n, m) N Z[n = m2`eunacorrispondenzada Na Z.- R = (n, m) Z Z [n + m`epari`eunarelazionein Z.- Il semipianoS= (x, y) R2[x ydel pianocartesianoR2`eunarelazioneinR R.Spessounacorrispondenzaounarelazionesonoassegnateindividuandoilsottoinsie-meRmedianteunasuapropriet`acaratteristica; intal casospessosi confondonolacorrispondenza(orelazione)conlapropriet`acaratteristicastessa.Esempio2.1.3.- Lacirconferenzadel pianocartesiano R2di equazionex2+ y2=1`eunarelazioneinR2= R R.- La relazione essere multiplo in N `e (n, m) NN [m = nkper un qualche k N.1314 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDenizione2.1.4. DatouninsiemeA, larelazione= (a, a) AA [a Asidicediagonale(orelazioneidentica)diA A.Denizione 2.1.5.Sia R una corrispondenza in AB. Si dice corrispondenza inversadiR(relazioneinversanel casoA = B)lacorrispondenzainB AdatadaR1= (b, a) B A [(a, b) R.Di particolare interesse nello studio di una relazione `e stabilire se verica alcuneparticolaripropriet`a.DiremocheunarelazioneRinAsoddisfala:R) Propriet`ariessivase a Asiha(a, a) RS) Propriet`asimmetrica se a, b A : (a, b) R=(b, a) RA) Propriet`aantisimmetrica se a, b A : (a, b) R e (b, a) R =a = bT) Propriet`atransitivase a, b, c A : (a, b) R e (b, c) R =(a, c) REsempio2.1.6. Vediamoqualidellepropriet`aR,S,A,Tsoddisfanoalcunerelazioni:a. nellinsiemedellerettedel piano, larelazioneessereincidenteossiaavereesatta-mente1puntoincomunesoddisfasoltantoS;b. nellinsiemedelleparti T(A)diuninsiemeAlarelazioneesseresottoinsiemegodedellepropriet`aR,AeT;c. nellinsiemeZdei numeri interi larelazioneaveresommadisparisoddisfasoloSmentreaveresommaparisoddisfaR,S,T.2.2 RelazionidordineDenizione2.2.1. UnarelazioneRinAsidicerelazionedordinesesoddisfalepropriet`ariessiva,antisimmetricaetransitiva(RAT).Una relazione dordine R in A si dice ordine totale se due elementi qualsiasi a, b Asonosempreconfrontabili,ossiavalesempre(almeno)unatraaRbe bRa.Unarelazionedordinenontotalesidiceordineparziale.Esempio2.2.2.a. Larelazionedividein N`eunarelazionedordine,ma`eparziale:inumeri2e3,adesempio,nonsonoconfrontabili tra loro inquanton`e2divide3,n`e 3divide2in N.b. La relazione divide in Z non `e una relazione dordine perche non soddisfa la propriet`aantisimmetrica:2e 2sonodivisorilunolaltroin Z,manonsonouguali.Universit`adiTorinoCapitolo2CorrispondenzeeRelazioni 15c. SeA`euninsiemechehaalmeno2elementi, linclusionein T(A)`eunarelazionedordine parziale. Se infatti ae b sono due elementi distinti di A, allora i duesingleton ae bnonsonoconfrontabilitraloro.d. In ZlarelazionesuccessorenRmsem = n+1non `eunarelazionedordineperchenonsoddisfalapropriet`atransitiva.e. R = (n, m) ZZ [m = n +2kconk N `eunarelazionedordineparzialein Z.f. Se R `e una relazione dordine in A allora anche la relazione inversa R1`e una relazionedordine.InoltreseR`eunordinetotale,ancheR1lo`e.Propriet`aimportante(cheapprofondiremoinseguito).Gliinsieminumerici N, Z,Q, Rconlerispettiverelazionidordinesonototalmenteordinati.Denizione2.2.3. SiaRunarelazionedordineinXesiaA X.Sidicechem`eilminimo diAsem Ae x AsihamRx.SidicecheM`eil massimodiAseM Ae x AsihaxRM.Esempio2.2.4.a. In Zdotatodellarelazionedordine , il sottoinsiemedei numeri pari nonammetten`emassimon`eminimo.b. In Rdotatodellarelazionedordine ,linsiemedeinumeristrettamentepositivinonammetten`eminimon`emassimo.c. SiaAuninsieme.ConsideriamoX= T(A)dotatodellarelazionedordine .AlloraXhaminimo emassimoA.Proposizione2.2.5. SianoRunarelazionedordineinXeA X.SeesisteunminimomdiA,allora`eunico.SeesisteunmassimoMdiA,allora`eunico.Dim: Supponiamochemem

soddisnoentrambi lecondizioni peressereminimodiA.Allorainparticolaresceltox =m

A,avremochemRm

;allostessomodo,presox = m A, avremo che m

R m. Poiche R`e una relazione dordine, R soddisfa la propriet`aantisimmetricaequindim = m

.Lavericarelativaalmassimo `edeltuttoanaloga. Denizione2.2.6. UninsiemeXdotatodi unarelazionedordineRsi dicebenordinatoseognisottoinsiemenonvuotodiXammetteminimo.QuaderniDidatticidel DipartimentodiMatematica16 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDenizione2.2.7. SiaAunsottoinsiemediuninsiemeXdotatodiunarelazionedor-dineR. Unelementox Xsi diceunminorante di Aseperogni a Asi haxRa;analogamenteunelementoy Xsidiceunmaggiorante diAseperognia AsihaaRy.Risultaevidentedalladenizionecheilminimodi A(seesiste)`eunminorantediAedanzi`elunicominorantedi AcheappartieneadAstesso. Analogamente, il massimodiA(seesiste) `eunmaggiorantediAedanzi `elunicomaggiorantediAcheappartieneadA.2.3 RelazionidiequivalenzaDenizione2.3.1. UnarelazioneRinuninsiemeAsidicerelazionediequivalenzasesoddisfalepropriet`ariessiva,simmetricaetransitiva(RST).SeR `eunarelazionediequivalenza,spessosiscrivea binveceche(a, b) RoppureaRb.Esempio 2.3.2. Larelazione di parallelismonellinsieme delle rette del piano`e unarelazionediequivalenza,mentrelarelazionediortogonalit`anonlo`e.Denizione2.3.3. Sia unarelazionediequivalenzainuninsiemeXesiaaunele-mento di X. Si dice classe di equivalenza di a, e si denota [a] (oppure a) il sottoinsiemediXdeglielementichesonoinrelazionecona,ossia:[a] = b X [a b.Un elemento a che appartiene ad una classe di equivalenza si dice anche unrappresentantediquellaclasse.Sinotichetraglielementicheappartengonoa[a]vi`eancheastesso,poiche,grazieallapropriet`ariessiva,sihaa a;quindia `einognicasounrappresentantedi[a].Lerelazioni di equivalenzainuninsiemeXoradenitecorrispondonoesattamenteallepartizionidiX,dicuisi `egi`aparlato,comemostranoiduerisultatiseguenti.Teorema2.3.4. Sia Q= Yi [i Iunapartizionedi X. AlloralarelazioneinXdenitada:aRb Yi Qtalechea, b Yi`eunarelazionediequivalenzainX.Dim: Dobbiamovericarechesonosoddisfattelepropriet`aRST.R)Poiche

Yi=X, presounqualsiasi a XesistesempreunsottoinsiemeYitalechea YiequindiaRa.S) Lavalidit` adellapropriet`asimmetrica`e del tuttoevidente: se a, bYiallorab, a Yi.Universit`adiTorinoCapitolo2CorrispondenzeeRelazioni 17T) Siano a, b, c elementi di Xe supponiamo che a R b e che b R c, ossia che esistano YieYjin Qtalichea, b Yieb, c Yj.Allorab Yi Yj;poicheduesottoinsiemidistintiinunapartizionenonpossonoavereelementi incomune,alloraYi=Yjea, c YiossiaaRc. Teorema2.3.5. Sia unarelazionediequivalenzainX.Alloraleclassidiequivalenzasoddisfanoleseguenticondizioni:i) a X[a] ,= ;ii) a, b Xsiha[a] = [b]oppure[a] [b] = ;iii)

aX[a] = X.Dim: Verichiamoletrecondizioni.i)[a] ,= poiche,comegi`avisto,a [a].ii)Supponiamo[a] [b] ,= esiacunelementodi[a] [b].Proviamoche[a] [b].Sex [a],ossiasea x,allorasiha:x a(ottenutausandolapropriet`asimmetrica)a cperchec [a]eb cperchec [b]equindic b(dinuovousandolapropriet`asimmetrica).Daquesterelazioni, applicandoduevoltelapropriet`atransitiva, seguex bossiax [b].Inmodoanalogosiprova[b] [a]equindiluguaglianzadelleclassi.iii)`E del tutto evidente che lunione delle classi `e contenuta in X. Proviamo allora chevaleanchelaltrainclusione.Sia x X; come gi`a visto x [x] e quindi x appartiene allunione di tutte le classi. Corollario 2.3.6.Se `e una relazione di equivalenza in X, allora le classi di equivalenzacostituisconounapartizionediX: Q = [a] [a X.Denizione 2.3.7.Sia una relazione di equivalenza in X. Si dice insieme quozientedi Xrispettoa(oppuremodulo) lequivalenza , denotatoX/, lapartizione Qi cuielementisonoleclassidiequivalenza:X/= [a] [a X.Esempio2.3.8.a. Larelazionedi similitudinetrai triangoli del pianoeuclideo`eunarelazionedi equi-valenza. Sea`euntriangoloconangoli interni , , , allora[a] = triangoli conangoliinterni, , .b. Larelazionein Z:n msen m `epari, `eunarelazionediequivalenza.Laclassediunnumeron`e:[n] = . . . , n 4, n 2, n, n + 2, n + 4, . . . ;leclassidistintesonoquindidue,unacontenentetuttiinumeriparielaltratuttiidispari.QuaderniDidatticidel DipartimentodiMatematica18 M.Roggero-AppuntiedEsercizidiMatematicaDiscreta2.4 Esercizi2.1. SiaA = 1, 2, 3, 4, 5, 6 e siano e le relazioni inA date da:xy se e solo se 2x + 3y `e multiplo di 5 e xy se e solo se 2x 3y `e multiplo di 5.a. Vericare che `e una relazione di equivalenza e scrivere esplicitamente tutte le classi di equivalenza.b. Provare che invece non `e una relazione di equivalenza.`E una relazione dordine?2.2. SianoA = 1, 0, 1 eB = 1, 2.a. Scrivere esplicitamente tutti gli elementi diAB,AA e della diagonale inAA.b. DatalarelazioneR= (1, 1), (1, 0), (1, 1), (1, 1), (0, 0)inAA,direqualidellepropriet`aR, S, T, A tale relazione soddisfa.c.`E una relazione dordine?`E un ordine totale?d. Scrivere la relazione inversaR1.2.3. Eseguire tutte le veriche necessarie a completare quanto aermato nellEsempio 2.2.2.2.4. SiaXun insieme,A un suo sottoinsieme eR una relazione inX. Indichiamo con la relazione inA indotta daR ossia:a, b A si haab se e solo seaRb.Vericare la validit`a delle seguenti propriet`a:i) seR `e una relazione di equivalenza, anche lo `e,ii) seR `e una relazione di ordine, anche lo `e,iii) seR `e un ordine totale, anche lo `e.iv)`E vero che seX`e ben ordinato medianteR, ancheA lo `e mediante?v)`E vero che se Xi,i I `e una partizione diX, allora Ai = Xi A,i I `e una partizione diA?2.5. Trovare esplicitamente esempi di sottoinsiemi di Z, Q ed R tali che, rispetto allordinamento usuale:a. non ammettono n`e minimo n`e massimo;b. non ammettono minimo, ma hanno massimo;c. ammettono minimo e massimo;d. ammettono minimom e massimoMtali chem = M.2.6. In N si consideri la relazione:xy sex dividey ossia se k N tale chey = kx.a. Vericare che `e una relazione dordine.b.`E un ordine totale?`E un buon ordinamento?c. Dire se i sottoinsiemi A = 1, 2, 3, 4, 5, 6 e B = 2, 3, 4, 12 di N ammettono minimo e/o massimorispetto alla relazione.d. N ammette minimo e/o massimo rispetto alla relazione?2.7. In Z si consideri la relazione:xy sex dividey ossia se k Z tale chey = kx.a. Provare che non `e n`e una relazione dordine n`e una relazione di equivalenza.Universit`adiTorinoCapitolo2CorrispondenzeeRelazioni 19b. SiaR= (x, y) ZZ [xyossiail sottoinsiemediZZcheindividua(`e)larelazione.Determinare esplicitamenteS = R R1e provare cheS `e una relazione di equivalenza.2.8. In Z si consideri la relazione:xy se k N tale chey = kx.a. Vericare che `e una relazione dordine.b.`E un ordine totale?`E un buon ordinamento?c. Esiste un elemento di Z confrontabile con tutti gli altri?d. Quali elementi sono confrontabili con 3?e. Trovare oppure provare che non esistono il massimo e il minimo rispetto a dei seguenti sottoin-siemi:x Z [x 0, x Z [x 0, x Z [x < 0,P= x Z [x `e pari, D = x N [x `e dispari.2.9. Sia A un insieme dotato di una relazione dordine rispetto alla quale A risulta ben ordinato. Provareche `e necessariamente un ordine totale.2.10. Trovare esempi di relazioni in N che godano:i) della propriet`a R e non di S, T, A;ii) della propriet`a S e non di R, T, A;iii) della propriet`a T e non di R, S, A;iv) della propriet`a A e non di R, S, T.2.11. In N si consideri la relazionexy sex = y oppure se 2x dividey.a. Provare che si tratta di una relazione dordine.`E un ordine totale?b. Provare che 2k[k N `e un sottoinsieme totalmente ordinato rispetto a.c. SiaDil sottoinsiemedi Ndei numeri dispari. Provareche ristrettaaD`eunarelazionediequivalenza e caratterizzare le classi di equivalenza.2.12. In N N si consideri la relazione (a, b)(c, d) sea +b < c +d oppurea +b = c +d ea c.i) Vericare che si tratta di una relazione dordine totale;ii) provare che (0, 0) `e il minimo di N N;iii) scrivere le 6 coppie successive a (0, 0) rispetto allordine;iv) provare che per ogni coppia (a, b) ci sono solo un numero nito di coppie che la precedono rispettoalla relazione2.13. In NN si consideri la relazione (a, b)(c, d) sea < c oppurea = c eb d. Vericare che si trattadi una relazione dordine totale e provare che (0, 0) `e il minimo di NN. Provare che ogni coppia ha unsuccessore immediato, ma che non esiste nessuna coppia di cui (3, 0) sia il successore.2.14. Dire quali delle propriet`a R, S, T, A soddisfa la relazione inA nei seguenti casi:a. A = Z , xy sex y = n2per un qualchen Z;b. A = Z , xy sex y = n5per un qualchen Z;c. A = R , xy se [x[ = [y[;d. A = R , xy se [x[ [y[;QuaderniDidatticidel DipartimentodiMatematica20 M.Roggero-AppuntiedEsercizidiMatematicaDiscretae. A = Q 0 , xy sexy1pu`o essere scritto come frazionemnconm, n interi dispari;f. A = N , xy sex y = 3n per un qualchen N;g. A = N , xy sex y = 3n per un qualchen Z.Incasositrattidiunarelazionedordine,diresesitrattadiunordinetotale.Incasositrattidiunarelazione di equivalenza, determinare esplicitamente gli elementi di una classe a scelta.2.15. Si consideri in R la relazione xy se e solo se xy Z. Vericare che `e una relazione di equivalenzaescrivereesplicitamente[1], [2], [1.5]. Provarecheogni classedi equivalenza[x] haunoedunsolorappresentantex0tale che 0 x0< 1.2.16. Si consideri in R la relazione xy se e solo se xy Q. Vericare che `e una relazione di equivalenzaescrivereesplicitamente[1], [2], [1.5].`Everocheogni classedi equivalenza[x] haunoedunsolorappresentantex0tale che 0 x0< 1?2.17. SianoXun insieme non vuoto e una relazione inX(ossia X X). Provare che:a. soddisfa le 4 propriet`a R, S, T, A = ;b. `e riessiva ;c. `e simmetrica = 1;d. `e antisimmetrica 1= .2.18.SianoAuninsiemeconalmeno3elementieX=AAA.ConsideriamolarelazioneinXdata da:(a, b, c)(a

, b

, c

) se a, b, c = a

, b

, c

.a. Vericare che`e una relazione di equivalenza.b. Fissati 3 elementi distinti a, b, c di A determinare esplicitamente le classi di equivalenza di (a, b, c),(a, b, a) e (c, c, c).c. postoA = 1, 2, 3, elencare tutti gli elementi diXe scrivere la partizione diXassociata a.Lerelazionipresentateneiseguentiesercizipermettonodidenireoggettidiparticolarerilevanzaingeometria.2.19. Nel piano cartesiano R2consideriamo la relazione (x1, y1)(x2, y2) sex21 +y21 = x22 +y22.Provarechesi trattadi unarelazionedi equivalenzaecaratterizzaregeometricamenteleclassi diequivalenza.2.20. Nel piano cartesiano privato dellorigine = R2 O consideriamo la relazione:PQ se esiste una retta passante per lorigine che contienePeQ.a. Provare che `e una relazione di equivalenza.b. Caratterizzare geometricamente la classe di equivalenza [P] di un puntoP .c. SiaCla circonferenza del piano di centro lorigine e raggio 1 e siaP= (a, b) un punto qualsiasi.Determinare le coordinate di tutti i punti diC [P].d. Siar una retta del piano non passante per lorigine. Dire quanti elementi har [P], al variare diPin.e. Trovare un sottoinsieme di che contenga esattamente 1 rappresentante per ciascuna classe diequivalenza.Universit`adiTorinoCapitolo2CorrispondenzeeRelazioni 212.21.Nel pianocartesianoR2consideriamolacirconferenzadi centrolorigineeraggio1einlarelazione(x1, y1)(x2, y2) sex1 = x2ey1 = y2oppure (x1, y1) = (x2, y2).i) Provare che si tratta di una relazione di equivalenza e caratterizzare geometricamente le classi diequivalenza.ii) Vericare che coincide conlarelazione inindottadallarelazione in dellesercizioprecedente.Ilquoziente/sichiamarettaproiettiva.2.22. Nell spazio cartesiano R3consideriamo la supercie sferica di centro lorigine e raggio 1 e in la relazione(x1, y1, z1)(x2, y2, z2) sex1 = x2,y1 = y2ez1 = z2oppure (x1, y1, z1) = (x2, y2, z2) .Provarechesi trattadi unarelazionedi equivalenzaecaratterizzaregeometricamenteleclassi diequivalenza.Ilquoziente/sichiamapianoproiettivo.2.23. Nel piano cartesiano R2consideriamo la relazione(x1, y1)R(x2, y2) sex1x2 Z ey1y2 Z.i) Provare che si tratta di una relazione di equivalenza.ii) Vericare che Z Z `e la classe di (0, 0).iii) Determinare la classe di (0.5, 2.3).iv) Provare che ogni classe di equivalenza ha un rappresentante che appartiene al quadrato con vertici(0, 0), (0, 1), (1, 0) e (1, 1).Ilquoziente R2/Rsichiamatoro.2.24. SiaElinsieme i cui elementi sono le equazioni lineari in due incognite a coecienti in R ossia leequazioni del tipoax + by + c = 0 cona, b, c R. Si considerino la relazioneinEdata da e1e2see1ede2hanno le stesse soluzioni e la relazionePinEdata da e1Pe2se esiste R, ,= 0 tale chee1 = e2. Vericare che ePcoincidono e sono relazioni di equivalenza inS.2.25. SiaSlinsiemedei sistemi lineari di dueequazioni indueincognite. Vericarechelarelazioneavere le stesse soluzioni `e una relazione di equivalenza inS.QuaderniDidatticidel DipartimentodiMatematicaCapitolo3Lefunzioni3.1 Generalit`asulleapplicazioniofunzioniDenizione3.1.1. Unaapplicazioneofunzionef`eunaternaf=(A, B, ), doveAeBsonoinsieminonvuotie`eunacorrispondenzadaAaB(cio`eunsottoinsiemedel prodottocartesianoAB)che`eovunquedenitaefunzionaleossiachegodedellaseguentepropriet`a:a A !b Btaleche(a, b) .Notazioni e terminologia: A si dice dominio di f, Bsi dice codominio di fe si dice graco di f. Per indicare che f`e una funzione da A in Binvece che f= (A, B, )abitualmente si usa la notazione f :A B. Fissato un elemento a A, per indicare cheb `e lunico elemento di Btale che (a, b) si scrive b = f(a) e si dice che b `e limmaginedia.Denizione3.1.2. Si diceimmaginedi unafunzionef : A Besi denotaImfoppuref(A)il sottoinsiemedi Bdeglielementi chesonoimmaginedi qualcheelementodiAossia:Imf= b B [b = f(a)perqualchea A.Pi` ugeneralmente,datounsottoinsiemeCdiA,sidiceimmaginediCil sottoinsiemediB:f(C) = b B [b = f(a)perqualchea C.NOTABENE Spessoperassegnareunafunzionef :A Bsifornisceunaleggeossiaunaqualcheformulachepermettedi associareaciascunelementodel dominiolasua immagine. Si faccia per`o attenzione al fatto che la funzione `e caratterizzata soltantodal dominio A, dal codominio Be dal graco e non dalla eventuale formulazione dellalegge.22Capitolo3Lefunzioni 23Idueesempiseguentimostranocomeunastessaleggepu`odenirefunzionidiverseecome,daltraparte,leggidiversepossonodenirelastessafunzione.Esempio 3.1.3.La funzione f : Z N data da f(n) = n2e la funzione g : N Z datadag(n)=n2sonodiverse, perchenonhannolostessodominioelostessocodominio,ma, oltre aquesto, hannoanche propriet`amoltodiverse. Usandolaterminologiachedeniremoinseguito,fnon`einiettiva,mentreglo`e.Esempio3.1.4. SianoA = 0, 1, 2edf, g :A Rlefunzionideniterispettivamenteda f(x) = x7 e g(x) = x33x2+3x7. Queste funzioni, per quanto espresse medianteleggidiverse, sonolastessafunzione, ossiaf=g, poichehannolostessodominioA,lostessocodominio Relostessograco:f= g= (0, 7), (1, 6), (2, 5).NOTABENEParticolareattenzione`enecessarioprestarealladenizionedifunzionimediante legginel caso incui il dominiosiauninsieme quoziente. Inquesti casi`esempreopportunocontrollarecheperogni elementodel dominio, che`eunaclassediequivalenza, la sua immagine sia univocamente determinata, ossia non cambi se si cambiarappresentantedellaclasse.Esempio3.1.5. Sialarelazionedi equivalenzain Zdatadaxysex y`emultiplodi3.Indichiamocon[x]laclassediequivalenzadiunelementoxnel quoziente Z/.Allora[x] [2x] nondenisceunafunzionef : Z/ Z/, poiche[0] =[3], ma[20] =[1] ,=[23] =[8]. Inveceg : Z/ Z/datada[x] [x2] `ebendenita. Sianoinfatti aebduerappresentanti di unastessaclasse[a] =[b], ossiaaebsianotali chea b = 3kperunqualchek Z.Allorag([a]) = [a2] = [(b +3k)2] = [b2+3(2bk +3k2)] =[b2].Una riessione importante suggerita dallesempio precedente: esibire un esempio espli-citodi classelacui immaginenon`eunivocamentedenitamostrainmodorigorosoecompleto che quella di fnon `e una buona denizione. Per provare che la funzione g `e bendenita, invece,`estatonecessarioesaminaretutti gli elementi del dominiodimostrandocon un ragionamento generale che le immagini sono univocamente determinate; un modoalternativo, (possibile soltanto perch`e il dominio `e un insieme nito) sarebbe stato quellodiesaminaresingolarmente,ossiaunoallavolta,tuttiglielementideldominio.Quellicheseguonosonoesempidifunzioniparticolarmenteimportantiechecapiter`aspessodiusare.Esempio3.1.6.a. Le funzioni costanti. Siano A e Binsiemi e b0 Bun elemento ssato. La funzionecostanteb0`efb0:A Bdenitadafb0(a)=b0perognia A.SeA=B= R,lafunzionecostanteb0hacomegracolarettaorizzontalediequazioney= b0.QuaderniDidatticidel DipartimentodiMatematica24 M.Roggero-AppuntiedEsercizidiMatematicaDiscretab. Lefunzioni identit`a. SiaAuninsieme; lafunzioneidentit`adi A`eidA:A AdenitadaidA(a)=aperognia A.SeA=B= R,lafunzioneidentit`aidRhacomegracolarettabisettricedel primoeterzoquadrantedi equazioney=x. Sifacciaattenzioneanonconfonderelafunzioneidentit`aconlafunzionecostante1.c. Le funzioni proiezione su un fattore. Siano A e Binsiemi e ABil loro prodottocartesiano; si dice proiezionesulprimofattorela funzione1:AB A de-nita da 1((a, b)) = a. Analogamente la proiezione sul secondo fattore `e la fun-zione2:A B Bdatada2((a, b)) = b.Se`eil gracodi unafunzionef realedi variabilereale, allora1()`eil campodiesistenzadife2()`elimmaginedif.d. Lefunzioni proiezionesul quoziente. SiaAuninsiemedotatodi unarelazionediequivalenza;indichiamoconA/ilrelativoquoziente.SidiceproiezionediAsul quozientelafunzione:A A/denitada(a) = [a],dove[a] indicalaclassediequivalenzadellelementoa.e. Leoperazioni.UnaoperazionebinariainternainuninsiemeA`eunafunzione:A A A.Limmaginediunelemento ((a1, a2))disolitosidenotaa1 a2.f. Lesuccessioni.Unasuccessione`eunafunzionef : N R;il terminenesimoandellasuccessione`elimmaginef(n)del numeronaturalen.g. SiaIuninsiemequalsiasi(chechiameremoinsiemedi indici)eperognii IsiaAiuninsieme.IlprodottocartesianodegliinsiemiAidenotatoiIAi`elinsiemeicuielementisonolefunzionif :I Aitalichef(i) Aiperognii I.Lassiomadellascelta Contariamenteaquantoaccadenel casodel prodottocartesianodi dueinsiemi non `e possibile dimostrare che iIAi `e un insieme non vuoto quando tutti gliAisono nonvuoti. Anzi laermazione:(i I : Ai ,= ) = iIAi ,= (3.1)non`en`everan`efalsa. Taleaermazionesi chiamaAssiomadellasceltaeogni matematicopu`o liberamente scegliere se accettarlo come vero oppure riutarlo (con le relative conseguenze). Nelseguito noi assumeremo come vero lAssioma della scelta.Denizione 3.1.7. Siano f : ABuna funzione, b un elemento di Be DunsottoinsiemediB.Sidicecontroimmaginedibil sottoinsiemediAcos`denito:f1(b) = a A [f(a) = b.AnalogamentesidicecontroimmaginediDil sottoinsiemediA:f1(D) = a A [f(a) D.Universit`adiTorinoCapitolo3Lefunzioni 25La controimmagine di un elemento b del codominio non `e altro che la controimmaginedel sottoinsieme singleton b, ossia f1(b) = f1(b). La controimmagine di un elemento`equindi sempredenita(ossia esistesempre)ed`eunsottoinsiemedel dominioche, aseconda dei casi, pu`o essere linsieme vuoto , oppure un singleton (ossia un sottoinsiemeconunsoloelemento),oppureunsottoinsiemeconpi` uelementi.Esempio3.1.8. SianoA = 0, 1, 2, 3,B= Reg :A Rlapplicazionedenitada:g(0) = 5, g(1) =5, g(2) = , g(3) = .Consideriamo i seguenti sottoinsiemi di R: D1= [3, +), D2= (, 0), D3= [10, 8].Allora:f1(D1) = 0 ,f1(D2) = 2, 3 ,f1(D3) = ,f1() = 2, 3 ,f1(5) = 1 ,f1(27) = .Denizione3.1.9. Unafunzionef :A Bsidice:iniettivase a1, a2 A: a1 ,= a2=f(a1) ,= f(a2);suriettivaseImf= Bossiase b B a Atalechef(a) = b;biunivocaobiiettivase`esiainiettivasiasuriettiva.Una funzione biunivoca si dice anche biiezione oppure corrispondenza biunivocaooppurecorrispondenza1 1.Possiamoriformulareleprecedentidenizioniusandolecontroimmagini.Proposizione3.1.10. Siaf :A Bunafunzione.Allora:1) f`einiettiva b B f1(b)contieneal massimounelemento.2) f`esuriettiva b B f1(b)contienealmenounelemento.3) f`ebiunivoca b B f1(b)contieneunoeunsoloelemento.Dim: 1)Supponiamofiniettivaesiabunelementoqualsiasi di B. Seb / Imfalloraf1(b)= ; seinveceb Imf ossiaseb=f(a)perunqualchea A, alloraperognia

,= asihaf(a

) ,= f(a) = bequindif1(b) = acontieneunsoloelemento.Supponiamoorachelacontroimmaginedi ciascunelementodel codominiocontengaal massimounelemento; sea1,a2sonoelementi distinti di A, alloraleloroimmaginib1= f(a1)eb2= f(a2)sonodistintepercheincasocontrariof1(b1)conterrebbepi` udiunelemento.2)Lequivalenzaseguesubitodallosservazionechef1(b) ,= seesoloseb Imf.Inne3)siottieneimmediatamentedalleprecedenti. QuaderniDidatticidel DipartimentodiMatematica26 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaEsempio3.1.11.a. LefunzionicostantidaAinBnonsonomain`einiettive(trannenelcasomoltoparti-colareincuiAabbiaunsoloelemento)n`esuriettive(trannenelcasomoltoparticolareincuiBabbiaunsoloelemento).b. Lefunzioniidentit`aidA:A Asonosemprebiunivoche.c. Lefunzioniproiezionesuunfattore1e2dalprodottocartesianoABsuAesuBrispettivamente,sonosempresuriettive.Inoltre1(risp.2)`eancheiniettivasoltantoincasoB(risp.A)abbiaunsoloelemento.d. Lafunzioneproiezionesul quoziente: A A/`esempresuriettiva, poiche(perdenizione)leclassi di equivalenzanonsonomai vuote. Lunicocasoincui risultaanche iniettiva `e quello che riguarda la relazione identit`a: a1 a2se e solo se a1= a2.3.2 FunzionicomposteDenizione 3.2.1. Siano f : ABe g : BC funzioni. Si dice funzionecompostadifeglafunzione:g f :A Cdatada(g f)(a) = g(f(a)).La lettura corretta di gf`e fcomposto gin quanto f`e la prima funzione che agisceeglaseconda;perevitareuna(pernoi)poconaturaleletturadadestraversosinistrae,nellostessotempo, rispettareil signicatomatematicodel simbolo, evitandoconfusioneederrori,sipu`oleggereg fanchegdopof.Sinotichelacomposizionediduefunzioni `edenitasolonelcasoincuiilcodominiodellaprimacoincidecoldominiodellaseconda.Proposizione3.2.2. (Propriet`aassociativadellacomposizione)Sianof :A B, g :B Ceh:C Dfunzioni.Allora: (h g) f= h (g f).Dim: Perlaverica`esucienteosservarecheleduefunzioni hannolostessodominioA, lostessocodominioDe assegnanoaciascunelementoadi Alastessaimmagineh(g(f(a))). Grazie a tale propriet`a associativa, potremo scrivere senza ambiguit`a la composizionedipi` ufunzionicomeh g f,senzalusodiparentesi.Nonvalgonoinvece per lacomposizione di funzioni quelle che potremmochiama-re propriet`acommutativae propriet`adi cancellazione, come mostranogli esempi cheseguono.Esempio 3.2.3.Siano A, Be Cinsiemi due a due distinti e siano f :A B, g :B Ce h:B A funzioni. La composizione gf`e denita, mentre non lo `e la composizionef gpoicheil codominiodigeil dominiodifnoncoincidono.Universit`adiTorinoCapitolo3Lefunzioni 27Lecomposizionih fef hsonoentrambedenite,masonofunzionidiverse,perchelaprimahadominioAelasecondahadominioB.Esempio3.2.4. Sianof, g : N Nlefunzioni datedaf(n)=n2eg(n)=n + 3. Lefunzioni composteg f ef gsonoentrambedenite, sonoentrambefunzioni da NinN,masonofunzionidiversepoicheadesempio(g f)(0)=g(f(0))=g(0)=3,mentre(f g)(0) = f(g(0)) = f(3) = 9.Esempio3.2.5. Siaf : N Nlafunzionef(n) =n + 1. Per ogni ssatonumeronaturalek, consideriamolafunzionegk: N Ndatadagk(m) =m 1sem>0,gk(0) = k. Al variare del numero naturale k, si ottengono tante funzioni gkdiverse (poichegk(0)=kvariaal variaredi k);per`olefunzionicompostegk fsonotuttecoincidenti,inquantogk f= idNperognik.Allora,perh ,= ksihagh f= gk fmagh ,= gk.Daltrapartesef7: N N `elafunzionecostante7,alloraperh ,= ksihaf7 gh=f7 gkmagh ,= gk.I risultati seguenti stabilisconolegami tralepropriet`adi unafunzionedenitenelparagrafoprecedenteelacomposizione.Proposizione3.2.6. Sianof :A Beg :B Cduefunzioni.Allora:i) g finiettiva=finiettiva;ii) g fsuriettiva=gsuriettiva.Dim: i)Proviamochesefnon `einiettiva,neppureg fpu`oesserlo.Supponiamochea1,a2sianoelementidistintidiAtalichef(a1)=f(a2)=b;allorasiha:(g f)(a1) = g(f(a1)) = g(b) = g(f(a2)) = (g f)(a2)equindig fnon `einiettiva.ii)Supponiamog fsuriettiva; vogliamoprovarecheImg=C, ossiache c Csihac Img.Peripotesi esistea Ataleche(g f)(a) =c. Intal caso, postob=f(a), si hag(b) = c,comevolevasi. Dalliniettivit`a della funzione composta, invece, nulla segue riguardo alliniettivit`a del-lasecondafunzionee, allostessomodo, dallasuriettivit`adellafunzionecompostanullasegueriguardoallasuriettivit`adellaprimafunzione.Esempio 3.2.7. Sianof : N Z, g : Z Nle funzioni date rispettivamente daf(n)=n2eg(m)= mse m`eunnumerointero, g(m)=5incasocontrario. Lafunzionecompostag fnon `ealtrochelafunzioneidentit`aidN: N Ned `equindisiainiettivasiasuriettiva.Per`ofnon `esuriettiva,inquantoadesempio2/ Imfegnon `einiettivainquantoadesempiog(2) = g(3) = 5.I due esempiseguenti mostrano il comportamento di due funzioniimportanti rispettoallacomposizione.QuaderniDidatticidel DipartimentodiMatematica28 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaEsempio3.2.8. SianoA, Binsiemi,idAeidBlerispettivefunzioniidentit`aesiainneg :A Bunafunzionequalsiasi.AllorasihaidB g= gedancheg idA= g.Esempio3.2.9. SianoAuninsieme,aunsuoelementossatoefa:A Alacorri-spondentefunzionecostante.Seg :A A `eunafunzionequalsiasi,allorafa g= faeg fa= fg(a).3.3 FunzioniinverseDenizione3.3.1. Sidicefunzioneinversadiunafunzionef :A Bunafunzioneg :B Atalechevalganoleduecondizionig f= idAef g= idB.Teorema3.3.2. Siaf :A Bunafunzione.Sonoequivalenti:1) esisteunafunzioneginversadif;2) f`ebiunivoca;3) esistonoduefunzionih1,h2:B Atalicheh1 f= idAef h2= idB.Dim: Per provarelequivalenzadellecondizioni seguiremoloschema: 1) =3) =2) =1).Perprovareche1) =3)bastascegliereh1= h2= g.Limplicazione3) =2) seguedallaProposizione3.2.6, ricordandochelefunzioniidentit` asonoiniettiveesuriettive.Proviamoinne2)=1). Supponiamof biunivocaecostruiamoesplicitamentelafunzione inversa g :B A, assegnando limmagine ad ogni elemento b del dominio. Peripotesilinsiemecontroimmagine dibcontiene unoedunsoloelementoaossiaesisteunoedunosoloa Atalechef(a) =b. Poniamoallorag(b) =a. Per costruzionesi ha(g f)(a) = g(f(a)) = g(b) = a per ognia A e (f g)(b) = f(g(b)) = f(a) = bper ognib B. Notiamochelafunzioneinversacostruitaesplicitamentenelladimostrazionedelpre-cedenteteoremanon`ealtrochelacorrispondenzainversadellafunzionef : A Bpensata come corrispondenza in AB. Non sempre la corrispondenza inversa di una fun-zione risulta essere a sua volta una funzione; il teorema precedente mostra che ci`o accadeseesoltantosef`ebiunivoca.Disolitolafunzioneinversadif(naturalmenteseesiste)vienedenotatacolsimbolof1.Universit`adiTorinoCapitolo3Lefunzioni 29NOTABENE Conlanotazioneoraintrodottalimmaginedi unelementob Bmediantelafunzionef1siscriver`a,seguendolanotazionegenerale,f1(b).Purtroppoquestostessosimbolo`estatousatoancheperdenotarelinsiemecontroimmaginedi brispettoallafunzionefelanotazionerisultaquindiambigua.Perevitarepasticcisitengasemprepresenteche:-linsiemecontroimmaginef1(b)esistesempre, mentrenonsempreesistelafunzioneinversa: inmancanzadi indicazioni esplicite,`esempremegliointerpretaref1(b)comeinsiemecontroimmagine;-incasolafunzioneinversaesista, ossiaquandof`ebiunivoca, avremof1(b)= a,se interpretiamo il simbolo come insieme controimmagine di b rispetto alla funzione f, ef1(b) = a se interpretiamo il simbolo come immagine di b rispetto alla funzione inversaf1.Osservazione3.3.3. Risultachiarodalladimostrazionedel teoremaprecedente, chelafunzioneinversa, seesiste,`eunica.Inparticolaresipu`onotarecheseesistonoduefunzioni h1eh2comenellacondizione3)del teorema, alloratali funzioni conincidonotraloroesonopropriolafunzioneinversaf1.Sihainfattih1= h1 idB= h1 (f h2) = (h1 f) h2= idA h2= h2.Osservazione3.3.4. Perpoteraermarecheunafunzionef :A Bammettelin-versa,non`esucienteprovarechevi`eunafunzioneh1:B Atalecheh1 f= idA(oppureunafunzioneh2:B Atalechef h2=idB). Si vedaaquestopropositolafunzionef : N NdellEsempio3.2.5:fnonammetteinversainquantonon`esuriet-tiva,macisonoaddiritturainnitefunzionigkchesoddisfanolacondizionegk f= idN.Oppure si vedano le funzionife gdellEsempio 3.2.7:gnon ammetteinversa perche non`einiettiva,masihag f= idN.Concludiamoconunapropriet`achecisar`autileinseguito.Proposizione 3.3.5.Sia g :B Cuna applicazione. Prese comunque due applicazionibiunivochef :A Beh:C D,leseguentiaermazionisonoequivalenti:i) g`einiettiva(risp.suriettiva,biunivoca);ii) g f`einiettiva(risp.suriettiva,biunivoca);iii) h g`einiettiva(risp.suriettiva,biunivoca);iv) h g f`einiettiva(risp.suriettiva,biunivoca).Dim: Osserviamoinnanzi tuttochesar`asucienteprovarelequivalenzaperquel cheriguardaliniettivit`aelasuriettivit`a.QuaderniDidatticidel DipartimentodiMatematica30 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaPer liniettivit`aricordiamocheiii) =i) seguedallaProposizione3.2.6elimpli-cazione inversa i) =iii) segue dalla precedente osservando che esiste h1e si hag= h1 (h g).Proviamooradirettamenteii) =i).Sianob1, b2elementi distinti di B. Peripotesi f`ebiunivoca, quindi esistonoesonounicia1ea2inAtalichef(a1) = b1ef(a2) = b2cona1 ,= a2.Alloraperliniettivit`adig fsihag(b1) = g(f(a1)) = (g f)(a1) ,= (g f)(a2) = g(f(a2)) = g(b2)ossiag`einiettiva.Limplicazioneinversai) =ii)seguedallaprecedenteosservandocheesistef1esihag= (g f) f1.Inneusandoinsequenzaledueequivalenzegi`aprovatesiottienei) iv).Lavericaperlasuriettivit`a `eanalogaed `elasciatacomeesercizioallettore. 3.4 EserciziNel seguitoZ2indicail quozientedi Zrispettoallarelazionedi equivalenzan msen m`epari.3.1. Si consideri la corrispondenza in Z2Z costituita dalle coppie ([n], n) per ognin Z. Si tratta delgraco di una funzione Z2 Z? La corrispondenza inversa `e il graco di una funzione Z Z2?3.2. Perchef([n]) = 3n +1 non denisce una funzionef : Z2 Z?`E vero cheg([n]) = [3n +1] denisceuna funzione di Z2in se stesso?3.3. Vericare chef(n) = [n] denisce una funzionef : Z Z2. Determinare limmagine dellelemento7, limmagine dellelemento 8, limmagine di f, limmagine dellinsieme 2, 1, 0, 1, la controimmaginedi [7] e la controimmagine dellinsieme [7], [1].3.4. Dire se le seguenti operazioni in Z2sono ben denite:a. [n] [m] = [n +m2];b. [n] [m] = [nm];c. [n] [m] = [n];d. [n] [m] = [nm];e. [n] [m] = [k] dovek `e il minore tran em.3.5. SiaXil quoziente di R rispetto alla relazione di equivalenzax y sex y Z.Dire se le seguenti operazioni inXsono ben denite:a. [a] [b] = [a +b];b. [a] [b] = [ab];c. [a] [b] = [2a b].Universit`adiTorinoCapitolo3Lefunzioni 313.6. Si determini in ciascun caso la terna (A, B, ) che denisce le funzioni presentate negli esempia.,b., c., d. del primo paragrafo di questo capitolo.3.7. Siaf : Z Zdatadaf(n)=n2 3n + 5. Determinaref(0), f1(5), f1(0). Si trattadi unaapplicazione iniettiva? Si tratta di una applicazione suriettiva?3.8.Siaf : Z Zdatadaf(n)=2n2 3n + 5. Determinaref(0), f1(5), f1(0). Si trattadi unaapplicazione suriettiva? Si tratta di una applicazione iniettiva?3.9. Siaf : N N N la funzione data daf((n, m)) = minm, n.a. Determinare limmagine dei sottoinsiemi N 0 e 0 N.b. Determinare gli insiemi controimmaginef1(n) pern = 4 e poi per unn generico.c. Dire sef`e iniettiva, suriettiva, biunivoca.3.10. Siaf : Z Z Z la funzione data daf((n, m)) = m2+n.a. Determinare Imfe limmagine dei sottoinsiemi Z 0 e 0 Z.b. Determinare gli insiemi controimmaginef1(4) ef1(Z), dove Z `e linsieme dei numeri interistrettamente negativi.c. Dire sef`e iniettiva, suriettiva, biunivoca.3.11. Siaf : Z Z Z Z lapplicazione data da:f((x, y)) = (y, 2) sex `e dispari ef((x, y)) = (y, x)sex `e pari.a. Dire sef`e iniettiva, suriettiva, biunivoca.b. Determinaref1((1, 1)),f1((1, 2)),f1((11, 12)),f1((4, 6)),f1((4, 7)).c. Determinaref(2Z 2Z) ef1(2Z 2Z), dove 2Z `e linsieme dei numeri interi pari.3.12. Determinare tutte le applicazionif :A BdoveA = 1, 2, 3 eB = , . Quante sono quellesuriettive? Quante sono quelle iniettive?3.13. Esiste una applicazione f : R R tale che f(1, 2) = 1,2, ? Esiste una applicazione g : R Rtale cheg(1,2, ) = 1, 2? (motivare le risposte; in caso aermativo esibire un esempio.)3.14. La successione diFibonacci `e la funzionef : N N data daf(0) = 1, f(1) = 1 ef(n + 1) =f(n) + f(n 1) per ogni n 2. Determinare le immagini dei primi 6 numeri naturali. Si tratta di unafunzione suriettiva? iniettiva?3.15. Determinare limmagine della funzione: NN N data da((m, n)) = mn. Vi sono elementidel codominiolacui controimmaginesiaunsingleton?Trovaretutti gli elementi di 1(p), perogninumero primop.3.16. Provare che la funzione: R2R2data da((x, y)) = (x +y, x y) `e biunivoca e determinarela sua inversa.3.17. SianoAuninsieme, Bunsuosottoinsieme, X= T(A)e: XXlapplicazionedatada(C) = C B. Dire se `e iniettiva, suriettiva, biunivoca e determinare Im().QuaderniDidatticidel DipartimentodiMatematica32 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaRispondere alle stesse domande relativamente a:X Xdata da(C) = C B.3.18. SianoX,YeZinsiemi ef :X Y ,g :Y Zdelle applicazioni.Si determini la composizioneg f :X Zin ciascuno dei casi seguenti:a. X = Y= Z = R,f(x) = x2+ 1 eg(x) = (x 1)2.b. X = Z = R,Y= R+,f(x) = x2,g(x) =x.c. X = R 0,Y= R ,Z = Z,f(x) = x/[x[ eg(x) = il pi` u piccolo numero pari x.3.19. Siaf : N N lapplicazione denita daf(n) = n2.Provare che non esiste una applicazione g : N N tale che f g = idN. Costruire due diverse applicazionih: N N tali cheh f= idN.3.20. Siaf : Z Nlapplicazionedenitadaf(n)=n2 nsen>0ef(n)= n + 1sen 0.Provare che non esiste una applicazione g : N Z tale che g f= idZ. Costruire due diverse applicazionih: N Z tali chef h = idN.3.21. Sia f : Z Z lapplicazione data da f(n) = 4n+1 se n `e pari e f(n) = 3n2 se n `e dispari. Diresesi trattadi unaapplicazioneiniettiva, suriettiva, biunivoca. Determinareesplicitamentegli insiemicontroimmagine di 0, 1, 3.3.22. SianoXeYinsiemi arbitrari (non vuoti) edf :X Yuna data funzione. Deniamo inXunarelazione secondo la regola: xx

f(x) = f(x

). Dimostrare che `e una relazione di equivalenza e chela funzione([x]) = f(x) denisce una biiezione tra linsieme quozienteX/ e limmagine dif.3.23.Siaf : Z Nlapplicazionedenitadaf(n)=n4. Costruireesplicitamenteil quozientedi Zelapplicazione come nellesercizio precedente.3.24. Sianof :A Beg :B Cdue funzioni biunivoche. Vericare che anche la funzione inversaf1e la funzione compostag fsono funzioni biunivoche.3.25. Trovare un esempio di insiemeA e applicazionef :A A tali chef f= f(che non siaidA).3.26.Siaf=(A, B, )unafunzioneesiano1e2leproiezioni sui fattori del prodottocartesianoAB. Provare che1() = A e2() = Imf.3.27. Siaf : R R ciascuna delle funzioni date da:1)x2, 2)ex, 3)sen(x) , 4)cos(x) , 5)arctan(x).Dire se si tratta di una funzione iniettiva, suriettiva, biunivoca.Esiste la funzione inversa?Quali modiche bisogna introdurre anche la funzioneg(x) data rispettivamente da:1) _(x) , 2)ln(x) , 3)arcsen(x) , 4)arccos(x) , 5)tan(x).sia linversa dif.Calcolareg(f(32)).Universit`adiTorinoCapitolo4NumerinaturalieCardinalit`a4.1 Linsiemedeinumerinaturali NelinduzioneLinsieme dei numeri naturali N`e lunicoinsieme numericodi cui ci occuperemocherisulta essere ben ordinato rispetto alla relazione dordine . Linsieme N non pu`o esserecostruitoapartiredagli assiomi dellateoriadegli insiemi, madeveesserepostulatoedi talepostulazionelesserebenordinato`eunadellerichiestefondamentali. Inltre N`eil primo insiemeinnitocheincontriamo; ogni altracostruzionedi insiemeinnitopartir`adirettamenteoindirettamentedaN. Vogliamosottolinearechenessuninsiemeinnitopu`oesserecostruitoapartiredallateoriadegli insiemi, maalmenounodi essideveesserepostulatoconunnuovosaltoconcettuale.Assiomi di Peano.Linsiemedei numeri naturali N`euninsiemenonvuotodotatodiunafunzione: N N(dettasuccessore)chegodedelleseguentipropriet`a:i) esisteunelementoin N,denotato0,talecheIm= N 0;ii) `einiettiva;iii) Principiodiinduzione:seU`eunsottoinsiemedi Ntaleche1) 0 U(basedellinduzioneopassoiniziale)2) n U =(n) Uossia(U) U(passoinduttivo)alloraU= N.Nonintendiamoapprofondireladenizioneassiomaticadi N;diciamosoltantocheapartire dagli assiomi si pu`o costruire in modo formalmente perfetto tutto ci`o che sappiamosu N,comeleoperazionidisommaeprodottoeleloropropriet`a.Adesempion + 0 = nen + (0) = (n)ecc.Intalmodo,comesuggerisceilnomestesso,ilsuccessorediunnumeronaturalenossiailnumeron

taleche(n)=n

,non`ealtrochen + 1:dorain3334 M.Roggero-AppuntiedEsercizidiMatematicaDiscretapoiscriveremoappunton + 1inveceche(n).Unaltradenizioneassiomaticadi N(deltuttoequivalenteaquesta)siottienesosti-tuendolacondizioneiii)conlacondizione:iii) N `e dotato di un buon ordinamento tale che n (n) per ogni elemento n N.Proviamosolounapartedellequivalenzatraiduesistemidiassiomi.Proposizione4.1.1.Se N `e un insieme che soddisfa i), ii), iii), allora N soddisfa ancheiii).Dim: SiaUunsottoinsiemedi Nchesoddisfalecondizioni 1) e2) del principiodiinduzione. Procediamoper assurdo. SupponiamoU ,=Neproviamochenediscendeunacontraddizione.PoniamoV = (N(U); per ipotesi V ,= e quindi, invirt` udel buonordinamento(assiomaiii))di N,V ammetteminimocheindicheremoconm.Nonpu`oesserem = 0inquanto0 Uequindi0/ V .Allora(assiomai))esistek Ntalechem=(k).Poichek`eminoredi mche`eilminimodiV ,allorak/ V ossiak U.Invirt` udelleipotesifattesuU,sek Ualloraanche(k) =m Uequindi m/ V : ci`onon`e, per`o, possibileperchem, essendoilminimodiV ,stainV . Unadelleprincipaliapplicazioniditaleprincipio `eladimostrazioneperinduzione.SiaP(n)unapropriet`arelativaadungenericonumeronaturalenesiaU= n N [lapropriet`aP(n) `everaSevalgonoleduecondizioniseguenti:1)0 U(basedellinduzione)2)n U =n + 1 U(passoinduttivo)alloraperilprincipiodiinduzioneU= N,ossialapropriet`a `everapertuttiglin N.Esempio4.1.2. SiaXuninsiemeconnelementi. ProviamomediantelinduzionecheT(X)ha2nelementi.Dim: Passoiniziale:seXha0elementi,ossiaseX= ,allora T(X)= ha1=20elementi.Passoinduttivo: supponiamochelassertosiaveroper gli insiemi chehannon 1elementieproviamoloperX,chehan > 0elementi.Fissato unelementox0 X,abbiamoX= Y x0 dove Y= X x0 `e uninsiemecon n1 elementi. Possiamo suddividere i sottoinsiemi di Xtra quelli che non contengonox0e quelli che lo contengono: quelli del primo tipo sono tutti i sottoinsiemi diYe quindiil loronumero`e, grazieallipotesi induttiva, 2n1; quelli del secondotiposi ottengonoaggiungendox0aciascuninsiemedelprimotipo.Otteniamocos`lunionedisgiunta:T(X) = T(Y ) A x0 [A T(Y ).Universit`adiTorinoCapitolo4NumerinaturalieCardinalit`a 35Allora T(X)ha2n1+ 2n1= 2nelementi. Alcunevarianti(equivalenti)dellinduzione:I.Sevalgonolecondizioni:1)k0 U2)n U =n + 1 Ualloralapropriet`aP(n) `evera n k0.II.(Detta:formafortedellinduzione)Sevalgonoleduecondizioni:1)k0 U2)(k U k t.c. k0 k n) =n + 1 Ualloralapropriet`aP(n) `evera n k0.Esempio4.1.3. Proviamocheperogninumeronaturalestrettamentepositivonsiha1 + + n =n

k=1k =n(n + 1)2.Passoinizialen = 1:laformulavalepoiche1 =1(1+1)2.Passoinduttivo: suppostaveralaformulaperuncertonumeron 1, proviamochevaleancheperil successivon + 1.Siha:1 + + n + (n + 1) = (1 + + n) + (n + 1) =n(n + 1)2+ (n + 1) =(n + 1)(n + 2)2.Esempio4.1.4. Proviamochein Nesisteladivisioneconrestoossiachepresi duequalsiasi numeri a, b N, b ,=0, esistonoq N(quoziente)edr N(resto)tali chea = bq + rer < b.Dim: Procediamoperinduzionesuldividendoa.Passoiniziale:a = 0:lassertovaleponendoq= r = 0.Passoinduttivo:supponiamolassertoveroperognicoppiadinumerinaturali(a

, b

)cona

< aeproviamochevaleancheperlacoppia(a, b).Sea < b,alloralassertovaleponendoq= 0er = a.Se a b, grazie allipotesi induttiva sappiamo che lasserto vale per la coppia (ab, b)echequindiesistonoq

edr

r `e da-ta mediante una formula che coinvolge f(n1), o, pi` u genericamente, f(0), f(1), . . . , f(n1).`Epropriograzieal principiodi induzionechelaricorsionedenisceunasuccessione,ossiaunafunzioneilcuidominio `etutto N.QuaderniDidatticidel DipartimentodiMatematica36 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaEsempio4.1.5. Sianoa,beknumerirealiqualsiasi.Sidicesuccessionearitmeticao lineare la successione denita ricorsivamente da a0= a e, per ogni n 1, an+1= an+k.Si dicesuccessionegeometrica oesponenzialelasuccessionedenitaricorsivamentedab0= be,perognin 1,bn+1= bnk.Esempio4.1.6. LasuccessionediFibonacci`elasuccessionedenitaricorsivamentedaf0= 1,f1= 1eperognin 2,fn+1= fn1 + fn.4.2 Lacardinalit`adiuninsiemeComeapplicazionedellecosevisteriguardoallefunzioni vogliamooradenireinmodorigoroso il numero di elementi di un insieme, anche nel caso in cui linsieme sia innito.Primadipoterfareci`o,`enecessarioprecisarecosaintendiamodicendocheuninsieme`enitooppureche `einnito.Denizione4.2.1. Si dicechedueinsiemi AeBsonoequipollenti oppurehannolastessacardinalit`aseesisteunafunzionebiunivocaf :A B.ConsideriamouninsiemeXicui elementisonoinsiemi. Larelazionedi equipollenzainX`eunaequivalenza.LaclassediequivalenzadiuninsiemeAsiindicaconCard(A).IntuitivamentepossiamodirecheCard(A) = Card(B)seAhatantielementiquantiB. Vogliamooramettere aconfrontotralorole cardinalit`a, per poter dire anche seuninsiemehapi` uelementi (oppurehamenoelementi) di unaltro. Molti dei risultatiche useremo(contrassegnati conunasterisco) sarannosoltantoenunciati, poiche unalorodimostrazionerigorosarichiedenozionietecnichenonelementari(comeadesempiolassiomadellascelta).Lemma*4.2.2. SianoAeBinsiemi.Allora:esisteunafunzioneiniettivai :A B esisteunafunzionesuriettivap:B A.Denizione4.2.3. DatidueinsiemiAeB,diciamocheAhacardinalit`aminoreougualedi Bseesisteunaapplicazioneiniettivai :A Boppure(equivalentemente)se esiste unaapplicazione suriettivap: BA. Intal casoscriveremoCard(A) Card(B).Teorema*4.2.4. SianoAeBinsiemi.Allora:Card(A) = Card(B) Card(A) Card(B)eCard(B) Card(A).Universit`adiTorinoCapitolo4NumerinaturalieCardinalit`a 37Denizione4.2.5. UninsiemeAsidicenitoseperognifunzionef :A Asiha:f`einiettiva f`ebiunivoca f`esuriettiva.Asidiceinnitoincaso contrario,ossiaseesisteunafunzionef :A Ainiettivamanonsuriettiva,oppuresuriettivamanoniniettiva.Possiamo riformulare tali denizioni dicendo che un insieme `e innito se `e equipollenteadunsuosottoinsiemeproprioed `enitosequestononcapita.Esempio 4.2.6.Linsieme dei numeri naturali N `e un insieme innito poiche la funzionesuccessore: N N,(n) = n+1 `einiettivamanonsuriettiva(AssiomidiPeano).Possiamoanchevederechelafunzionedoppiof : N P(P= numerinaturalipari)datadaf(n)=2n, `ebiunivocaequindi Card(N)=Card(P), ancheseP`eunsottoinsiemepropriodi N.Nel seguitodel capitoloindicheremoconIn(n 1) linsiemedei numeri naturali1, . . . , n.Ilrisultatoseguente,tuttaltrocheevidentecomepotrebbesembrareaprimavista, `econosciutocomeprincipiodeicassettioprincipiodellapiccionaia.Lemma4.2.7. 1)Sen malloraCard(In) Card(Im);2)Card(In) = Card(Im)seesolosen = m.Dim:1)Lafunzionef :In Imdatadaf(i) = iperognii In`einiettiva.2)ProviamosololimplicazionenonbanaleCard(In) = Card(Im)=n = m.Sia A linsieme dei numeri naturali m per cui questa implicazione `e falsa per un qualchen N. VogliamoprovarecheA`evuoto, ossiachelapropriet`a`everapertutti i numerinaturali 1.Supponiamo (per assurdo) A ,= ; allora, in virt` u del buon ordinamento di N, esiste ilminimodi Acheindichiamoconm0.Poichem0 A,esisteunnumeron ,=m0talecheCard(Im0) = Card(In):siaquindif :In Im0unafunzionebiunivoca.Il minimo m0 non pu`o essere 1, poiche lunica applicazione f :In I1 `e lapplicazionecostante1;sen ,= 1,allora1, 2 Inequindifnon `einiettivapoichef(1) = f(2) = 1.Supponiamoalloram0 ,= 1:intalcasom01 ,= 0ed `edenitoIm01.Siak=f(n)esiag :Im0 Im0lafunzionebiunivocadatadag(i)=isei ,=kei ,= m0,g(k) = m0,g(m0) = k.Lafunzioneh = g f :In Im0`ebiunivocaetalecheh(n) = m0.Mediantehpossiamocostruirelafunzionebiunivocah

:In1 Im01datadah

(i) = h(i).Alloram01 A,incontrastoconlaminimalit`adim0. Grazie a questo risultato potremo indicare senza ambiguit` a la cardinalit`a di Incon n.Diremoinoltrechelinsiemevuotohacardinalit`a0.Condensiamo nel risultato seguente una serie di altri fatti di non facile dimostrazione.Teorema*4.2.8. a. Perogninumeron N,In`euninsiemenito.QuaderniDidatticidel DipartimentodiMatematica38 M.Roggero-AppuntiedEsercizidiMatematicaDiscretab. OgniinsiemenitoA`eequipollenteadunInoppure`e :quindiCard(A) N.c. SeB`einnito,alloraCard(B) > nperognin N:quindiCard(B)/ N.Lacardinalit`adellinsiemeinnitoNnon`equindi unnumeronaturale. Card(N)`edettacardinalit`anumerabileevieneindicatacon 0(`elaletteraebraicaalef).Uninsiemeequipollentea Nsidiceinsiemenumerabile.Teorema*4.2.9. SianoA,Bdueinsiemi.a. Le cardinalit`a di Ae Bsono sempre confrontabili, ossia vale sempre Card(B) Card(A)oppureCard(A) Card(B).b. SeA`euninsiemeinnito, alloraCard(A) 0, ossia 0`eil pi` upiccolocardinaleinnito.Esempio4.2.10. Card(Z) = 0. Unaapplicazione biunivocaf : Z N`e datadaf(n) = 2nsen 0,f(n) = 2n 1sen < 0.Esempio4.2.11. Card(Q) = 0.Non`esemplicedenireunafunzionebiunivocaZ Q;costruiamonealloraunainiettivaeunasuriettiva.Unafunzioneiniettiva`e,adesempio,n n.Costruiamooraquellasuriettiva.Consideriamoin N N( N= N 0)larelazionedordinetotale:(a, b) (c, d)sea + b < c + doppuresea + b = c + dea c.Concretamentesiha:(0, 1) < (0, 2) < (1, 1) k.4.5.Siconsiderinonelpianoeuclideonrettegeneriche(ossiatalichetraessenoncisianocoppiedirette parallele oppure terne di rette passanti per uno stesso punto). Provare che tali rette suddividono ilpiano inn2+n+22parti.4.6. Per ogni coppia di numeri naturalin em poniamo: 0 +m = m ,(n) +m = (n +m).Provare mediante linduzione che in questo modo si denisce una operazione +: N N N.4.7. Per ogni coppia di numeri naturalin em poniamo: 0m = 0 ,(n)m = nm+m.Provare mediante linduzione che in questo modo si denisce una operazione: N N N.Vericare che per ogni coppia di numeri naturalin, m,n ,= 0, 1,m ,= 0 si hanm > m.4.8. Esistono due applicazioni dierenti di N in N aventi la stessa immagine?4.9. Indichiamo con 6Z il sottoinsieme di Z dei multipli interi di 6. Provare cheCard(6Z) = Card(Z).QuaderniDidatticidel DipartimentodiMatematica40 M.Roggero-AppuntiedEsercizidiMatematicaDiscreta4.10. Indichiamo conQ il sottoinsieme di N dei numerin2, tali chen N. Provare cheCard(Q) = 0.4.11. SiaA un insieme nito con 3 elementi. Provare cheCard(AN) = 0. Generalizzare il risultatoal caso in cuiA abbiak elementi conk N.4.12. Siano(0, 1)e(3, +)unintervalloapertoeunasemirettadi R. Provarechehannolastessacardinalit`a di R.4.13. Sianoe le circonferenze del piano cartesiano con centro lorigine e raggio rispettivamente 1 e2. Provare che e hanno la stessa cardinalit`a, che `e anche la stessa cardinalit`a della retta reale.`E veroche nellinterno divi sono inniti punti a coordinate razionali?4.14. In un teatro vi sono 500 persone. Provare che ce ne sono almeno 2 che festeggiano il compleannolo stesso giorno.Quante persone bisogna riunire per essere sicuri che almeno tre tra esse festeggino il compleanno lo stessogiorno?4.15. Provare che in Italia esistono sicuramente due persone che festeggiano il compleanno nello stessogiorno, hanno lo stesso numero di scarpe ed anche la stessa altezza espressa in centimetri. E a Torino?Universit`adiTorinoCapitolo5Elementidicalcolocombinatorio5.1 PermutazioniedisposizioniIndichiamoconSXlinsiemedituttelefunzionibiunivochediuninsiemeXins`e.Lacomposizionedifunzioni `eunaoperazioneinSXchegodedelleseguentipropriet`a:- associativa:h (g f) = (h g) f;- esistenzadellidentit`aidXtaleche f SX(f idX= idX f= f);- esistenzadellinverso: f SX, f1 SXtalechef f1= f1 f= idX.Uninsiemedotatodiunaoperazionechegodeditalipropriet`asidicegruppo:(SX, ) `edunqueungruppo.La teoria generale dei gruppi sar`a arontata nel corso di Algebra. Per ora ci limitiamoacontarequantielementihaSXnelcasoincuiX`euninsiemenito.Osserviamointantochelacardinalit`adi SXnondipendedallanaturadegli oggettidellinsiemeX,masolodallacardinalit`adiX.Valeinfattilaseguentepropriet`a:Proposizione 5.1.1.Siano A, A

, B, B

insiemi tali che Card(A) = Card(A

) e Card(B) =Card(B

).Vi `ealloracorrispondenzabiunivocatragliinsiemi Hdellefunzionih:A Be H

delle funzioni h

: A

B

, corrispondenzache trasformafunzioni iniettive(risp.suriettive,biunivoche)infunzioniiniettive(risp.suriettive,biunivoche).Dim: Per ipotesi esistonoduefunzioni biunivoche f : A A

eg : BB

. Unacorrispondenzatra He H

`edatadah g h f1; talecorrispondenza`ecertamentebiunivoca,poichehacomeinversah

g1 h

f.LultimapartedellassertosegueimmediatamentedallaProposizione3.3.5. In virt` u di tale propriet`a, nel seguito potremo , senza perdere in generalit`a, considerare,alpostodiungenericoinsiemeXconcardinalit`an,linsiemeIn= 1, . . . , n.4142 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDenizione5.1.2. Sidicepermutazione dinelementiogniapplicazionebiunivocadiInins`e.LinsiemeSndituttelepermutazionidiIn(conloperazionedicomposizione)sidicegruppodellepermutazionidinelementiogrupposimmetrico.OgnielementodiSn`eunafunzionebiunivocafdiInins`eed `equindiunivocamenteindividuatadalleimmagini(f(1), f(2), . . . , f(n)),checostituisconounanuplaordinataincuiinumerida1ancompaionotuttiunaeunasolavolta,inunbenprecisoordine.Daorainpoicapiter`aspessodiidenticarelafunzionefcontalenuplaordinata.Notazione. Sianunnumeronaturale 1.Colsimbolon!,chesileggenfattoriale,sidenotailprodottodituttiinaturalida1noadn:n!=12. . . (n 1)n.`Eutiledaresignicatoadn!anchenelcason = 0ponendoperconvenzione0! = 1.Proposizione5.1.3. Lacardinalit`aPndel grupposimmetricoSn`en!.Dim:Proviamoloperinduzionesun.Sen=1, lunicapermutazionedi I1`elafunzioneidentit` aequindi S1ha1! =1elemento.Supponiamo la formula vera per un certo n e proviamola per lintero successivo n+1.Perogninumeronaturalej,1 j n + 1,glielementifdiSn+1talichef(n + 1)=jsono tanti quanti le applicazioni biunivoche tra Ine linsieme In+1j che ha n elementi.Invirt` udellaProposizione5.1.1edellipotesiinduttiva,taliapplicazionisonoPn= n!equindiglielementidiSn+1sonoPn+1= (n + 1)Pn= (n + 1)n! = (n + 1)!. Esempio 5.1.4.Lordine di arrivo di una gara a cui partecipano 20 corridori (escludendolapossibilit`adi ritiri edi piazzamenti ex-aequo)`eunapermutazionedei partecipanti. Ipossibiliordinidiarrivodiversisonoallora20!.Intuitivamente possiamo dire che ci sono 20 possibili primi classicati; per ciascuno diquesti ci sono 19 possibili secondi classicati (tutti meno il primo classicato), 18 possibiliterziclassicati,ecos`via. . . .Denizione5.1.5. Sianokedndueinteri, 1 k n, esianoAeBinsiemi concardinalit`arispettivamentekedn. Linsiemedelleapplicazioni iniettivef :A Bsidiceinsiemedelledisposizioni(semplici)dinelementiakak.Comegi`adettoperlepermutazioni, possiamosupporresenzaperdereingeneralit`ache A sia Ike Bsia In. Una disposizione f :Ik In`e allora univocamente determinatadalla kupla ordinata delle immagini (f(1), . . . , f(k)) che `e costituita da numeri compresitra1en,nessunodeiqualiripetuto.Universit`adiTorinoCapitolo5Elementidicalcolocombinatorio 43Proposizione5.1.6. Linsiemedelledisposizionidinelementiakakhacardinalit`aDn,k=n!(n k)!= n(n 1)(n k + 1).Dim: Procediamoperinduzionesuk.Sek=1, leapplicazioni, tutteiniettive, di I1inInsonotantequantelepossibiliimmaginidellunicoelementodeldominio,ossiasonoDn,1= n =n!(n1)!.Sedaltrapartek = n,alloraDn,n= Pn= n! =n!0!=n!(nn)!.Supponiamolaformulaveraperuncertok r1> r2>> rk> 0) esifermanonappenasitrovaunrestonullo.IlMCD(a, b) `elultimorestononnullotrovato.Procedendoaritrosodark=rk2 rk1qk1edutilizzandolerelazionetrovateadognidivisioneri= ri1qi1 + ri2,siricavalidentit` adiBezout.Esempio6.3.9. ProcedimentopercalcolareMCD(6852, 3997):1) 6852 = 39971 + 28552) 3997 = 28551 + 11423) 2855 = 11422 + 5714) 1142 = 5712 + 0AlloraMCD(6852, 3997) = 571.Procedimentopercalcolarelidentit`adiBezout:3) 571 = 2855 114222) 1142 = 39972855 da cui, sostituendo nella precedente, 571 = 2855(39972855) 2ossia571 = 28553 + 3997(2)1) 2855=6852 3997dacui, sostituendonellaprecedente, 571=(6852 3997)3 +3997(2)ossia571 = 68523 + 3997(5).Corollario6.3.10. Sianoa, b, c Z,(a, b) ,= (0, 0).Allora:x, y Ztalichec = ax + by MCD(a, b)/c.Dim: Sianod=MCD(a, b)ed=ax

+ by

lidentit` adi Bezout. Sec=ax + by, ognidivisorecomuneadaebdivideanchec;inparticolared/c.Viceversa,sec = dt,allorac = ax + by,dovesipongax = x

t,y= y

t. Osseriviamo inne che il minimo comune multiplo di due numeri si ottiene facilmente apartire dal loro massimo comun divisore come: mcm(a, b) =abMCD(a,b)e quindi pu`o essere,anchesso,calcolatomediantelalgoritmoeuclideo.6.4 IlteoremafondamentaledellaritmeticaInquestoparagrafoproveremocheogni numerointero, nonnulloenoninvertibile, sifattorizzainmodoessenzialmenteunico(ossiaamenodi permutazioni dei fattori edicambiamentidisegno)nelprodottodinumeriprimi.Cisar`autilelaseguenteQuaderniDidatticidel DipartimentodiMatematica58 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDenizione6.4.1. Siaaunelementodi unanelloAcommutativoconidentit`a. Duefattorizzazioni a=b1 bkea=c1 chsonoessenzialmentelastessafattorizza-zionedi asek=heperogni i=1, . . . , ksi habi=uic(i), doveleuisonounit`adiAe`eunaopportunapermutazionedegliindici.Inaltreparoleduefattorizzazionisonoessenzialmentelastessasedierisconosoloperlordinedeifattoriepereventualifattorimoltiplicativiinvertibili.Lemma 6.4.2. Siaaunnumerointero ,=0, 1, 1. Alloraapu`oessere scrittocomeprodottodinumeriinteriirriducibilia = a1 ak.Dim: Senzaperdereingeneralit`a, possiamosupporrea 2econsideraresolofattori 2.Procediamoperinduzionesua.Sea = 2,alloraa`eirriducibile,k= 1,a =a1enonc`enulladaprovare.Supponiamolassertoveropertuttigliinterin,2 n < aeproviamochevaleanchepera.Sea`eirriducibile,comeprimak=1,a=a1.Seinveceasipu`oscriverecomeprodottoa=bc, conb, cnoninvertibili, allorai fattori sonotali che2 b, c 9:[a] = [c0 + 10c1 + + 10ncn] = [c0] + [10][c1] + + [10n][cn] = [c0 +c1 + +cn] = [a1]con0 a1 1.Dim: 1) [a]`eunaunit`ain Znb Ztaleche[a][b] = [ab] = [1]in Znb Ztalecheab 1 nZ b, t Ztaliche1 = ab + nt MCD(a, n)/1(cfr.Lemma6.3.10) MCD(a, n) = 1.2)[a] `ezero-divisorein Zn [b] Zn, [b] ,=[0], taleche[a][b] =[ab] =[0] inZn b Z, 0 0,ladivisioneconrestodiaperbd`aa = bq + rcon0 r< b.Alloraab= q +rbconq Ze0 rb< 1.Quindid = q`elaparteinteradix =ab.Fissiamolabasekelinsiemedellekcifre. Vogliamoscrivereogni numerorazionalemedianteunasequenzadiquestecifre,generalizzandoquantofattoperinumeriinteri.Lanotazioneposizionalediunnumerorazionalepositivox`ecompostadadueparti:la scrittura posizionale della sua parte intera, formata da un numero nito di cifre, e unasequenzainnitadi cifreq1q2. . . qi. . . (i N), chedi solitosepariamodalleprecedentimedianteunavirgola.Se d `e la parte intera di x, la parte dopo la virgola sar`a quindi la scrittura posizionaledel numero x d, compreso tra 0 e 1. In caso la base scelta sia 10, le cifre dopo la virgolasichiamanodecimali.Lascritturaposizionaledi unnumerorazionalenegativoysi ottienepremettendoilsegnomenoallascritturaposizionaledi y; si noti cheintal casolaparteinteradi ydierisceperunaunit`adallaparteprimadellavirgolanellascritturaposizionalediy.Vediamooracomesi procedepercalcolarelecifredellascritturaposizionaledi x(x 0).Universit`adiTorinoCapitolo8Ilcampo Qdeinumerirazionali 79i) Scegliamocomesuorappresentanteunafrazioneab,cona, b > 0.ii) Eseguita la divisione con resto di a per b: a = bd +r0, la parte prima della virgola diab`elascritturaposizionaleinbasekdellaparteinterad.iii) Lecifredopolavirgolasiottengonoricorsivamentenelmodoseguente:q1`eilquozientedelladivisionedir0kperb:r0k = bq1 + r1;qi`eilquozientedelladivisionediri1kperb:ri1k = bqi + ri.Notiamochesi ha0 ri1k 2eA = (Q(B).Osservazione 9.1.6.Le seguenti propriet`a ci saranno utili per denire lordine, la sommae il prodotto in R. Lasciamo le veriche per esercizio al lettore, poiche non richiedono altrocheladenizionedisemirettaelenozionielementarisugliinsiemi.a) Unnumerorealex=(A, B)`eperfettamenteindividuatoanchedallasolasemirettasinistraAoppuredallasolasemirettadestraB;infattiB`eil complementarein QdiA,eventualmenteprivatodelminimo,e,viceversa,A `eilcomplementarein QdiB,eventualmenteprivatodel massimo.Potremoallorascrivereanchex = (A, . . . )oppurex = (. . . , B).b) SeBeB

sonosemirettedestredi Q,ancheB +B

= b +b

[b B,b

B

`eunasemirettadestradi Qe B= b [b B`eunasemirettasinistra.c) Sex=(A, B)`eunnumeroreale, alloralinsiemeB A= b a [b B, a Acoincidecon Q+.d) Se Be B

sono semirette destre contenute in Q+, anche B B

= bb

[b B,b

B

`eunasemirettadestracontenutain Q+.e) Se B(variabile inuninsieme I qualsiasi) sono semirette destre di Q, anche

I B`eunasemirettadestradi Q.Denizione9.1.7. Sianox = (A, B)ey= (A

, B

)duenumerireali.Allora:x yseB B

(o,equivalentemente,seA A

)QuaderniDidatticidel DipartimentodiMatematica90 M.Roggero-AppuntiedEsercizidiMatematicaDiscretax + y= (. . . , B + B

)Sex, y 0,alloraxy= (. . . , BB

).Proposizione9.1.8. Linsieme Rdotatodellordinamentoedelleoperazionisoprade-nite`euncampoordinatocheestende Q.Dim: Ladimostrazionecompletadiquestoenunciatorichiedemolteveriche,comples-sivamentelunghe,anchesenessunaparticolarmentecomplicata.Vediamonesoloalcune.Lepropriet`aassociative, commutative, distributivedi sommaeprodottodi-scendonoimmediatamentedaquelledi Q.Adesempiovalex +y= y +x,poiche,perlapropriet`acommutativadellasommainQ,sihaB + B

= b + b

[b B,b

B

= b

+ b [b B,b

B

= B

+ B.Esistenzadellopposto.Sex = (A, B),allorailsuoopposto `e x = (B, A).Dalladenizionedi sommasi hainfatti x + (x)=(. . . , B A); maB A= Q+(cfr.Osservazione9.1.6c)equindix + (x) = (. . . , Q+) = 0.Lesistenzadelloppostopermette di estendere atutte le coppie di numeri reali ladenizionediprodottoponendoxy= (x(y)) = ((x)y) = (x)(y).Esistenza dellinverso. Se x=(A, B) `e unnumeroreale strettamente positivo,alloraA Q+`enonvuotoelinsiemeC= a1[a A Q+`eunasemirettadestra.Allorax1= (. . . , C) `elinversodix. Proviamoinneinmodocompletolapropriet`afondamentaledeinumerireali.Teorema9.1.9.R`euncampoordinatocompleto.Dim: Siano Xe Ydue sottoinsiemi non vuoti di R tali che x Xe y Ysi ha x y.Proviamocheesiste(almeno)unelementoz Rtalechex z y, x Xe y Y .Indichiamoconx = (Ax, Bx)ey= (Ay, By)glielementidiXeY rispettivamente.Poniamoz =(. . . ,

yYBy) everichiamochesi hax z yper duequalsiasielementix Xey Y .Ladiseguaglianzaz y`eovviapoichepercostruzioneBy

yYBy.Inoltresihaanchex z,poicheperipotesix y,ossiaBx By, y Y ,equindiBx

yYBy. Dal punto di vista algebrico R non ha propriet`a signicativamente migliori di Q, poichele operazioni hanno in R le stesse propriet`a che hanno in Q. Riguardo alla risolubilit`a delleequazioni polinomiali, il campo Rpresentavantaggi esvantaggi rispettoa Q. Infatti, cisonomoltepi` uequazioni risolubili in Rchein Q(adesempiotutti i polinomi di gradodispariammettonoin Ralmenounaradice:cfr.Esempio9.1.11eCorollario10.2.5),manontutteleequazioni polinomiali sonorisolubili in R(adesempioX2+ 1=0nonlo`e).Daltrapartenonesistepi` uunmetodogeneralechepermettadicalcolarelesoluzionireali, analogo a quello visto per le soluzioni razionali. Rimandiamo ai paragra successivilatrattazionepi` udettagliatadiquestiargomenti.La completezza di R ha, per`o, come conseguenza di estrema importanza la convergenzadellesuccessionidiCauchy,fondamentodituttalAnalisimatematica.Universit`adiTorinoCapitolo9Ilcampo Rdeinumerireali 91I due esempi seguenti mostranocome, reciprocamente, risultati di analisi possanoessereusatiperprovarepropriet`aalgebrichedeipolinomi.Esempio9.1.10. Siano ReF(X)unpolinomioacoecientireali.Allora`eunaradicemultipladi F(X) seesolose`eunaradicecomuneaF(X) eal polinomioderivatoF

(X).Seinfatti`eunaradicemultipladiF(X),ossiaF(X) = (X )nG(X)conn 2,alloraF

(X) = (X )n1G(X) + (X )nG

(X)conn 1 1equindiF

() = 0.Viceversase `e unaradice semplice di F(X), ossiaF(X) =(X )G(X) conG() ,= 0,alloraF

() = G() ,= 0equindinon`eradicediF

(X).MediantelalgoritmoeuclideopossiamocalcolareM(X) =MCD(F(X), F

(X)): leradicimultiplediF(X)sonoesattamenteleradicidiM(X).Esempio 9.1.11. Sia F(X) unpolinomioa coecienti reali (che possiamosupporremonico)digradoddispari.AlloraF(X)haalmenounaradicein R.Infatti,lafunzionepolinomialey= F(x) `eunafunzionecontinua,denitasututto Retaleche:limx+F(x) = limx+Xd= + e limxF(x) = limxXd= .Quindiy= F(x)assumesiavaloripositivisiavalorinegativi.Peril teoremadiWeierstrasslafunzioney=F(x)assumetuttiivaloriintermediequindi,inparticolare,assumeancheil valore0incorrispondenzadiunqualche R.9.2 ScritturadeinumerirealiLadenizioneastrattadanoi datadi numerorealepermettedi introdurreinmodona-turalelasuascritturaposizionale. Perdenirelascritturaposizionaledel numerorealepositivox=(A, B)(lascritturaposizionaledi unnumeronegativoysi ottienepremet-tendo il segno alla scrittura di x = y) ssiamo, come gi`a fatto per Z e Q, la base kelinsiemedellekcifre.La scrittura posizionale di x `e la sequenza di cifre cr . . . c0, q1. . . qi. . . (i N) deniteinduttivamenteda:cr . . . c0= minparteintera (scrittainformaposizionale)dib [b Bq1= minprimacifradopolavirgoladib [b Bdeltipocr . . . c0, . . . qi= mini esimacifradopolavirgoladib [b Bdeltipocr . . . c0, q1. . . qi1. . . In questo modo si ottengono tutte le possibili sequenze di cifre; se infatti cr . . . c0, q1. . . qi. . .`eunasequenzaqualsiasi,essarappresentailnumerorealex = (A, B),doveB= b Q [b cr . . . c0, q1. . . qkperunqualchek N .QuaderniDidatticidel DipartimentodiMatematica92 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaDal puntodi vistaoperativolascritturaposizionaledei numeri reali nonrazionali, cio`euna scrittura non nita e non periodica, `e quasi sempre inutilizzabile. Ci sono per`o numerilecui cifredopolavirgola, anchesenonperiodiche, sonocomunqueottenibili inmodosucientementesemplicemedianteunaqualcheformulamatematica.Esempio9.2.1. Il seguentenumeroirrazionale`enotocomenumerodiLiouville.Fissatalabase10(maunaqualsiasi altrabaseandrebbeugualmentebene), laparteinteradi `e0esono0anchetuttelecifredopolavirgolatrannequelledi poston!, alvariaredinin N,chesonodegli1: = 0, 1100010000 . . . .Peralcuninumerirealilecifredopolavirgolapossonoesserecalcolateunaallavoltainmodoricorsivo,eseguendocontichesifannoviaviapi` ulunghi:adesempio,mediantelutilizzo di potenti calcolatori, sono state calcolate migliaia di cifre decimali di (ma nontutte!).Solitamenteper`oi numeri reali nonrazionali nonvengonoindicati mediantelaloroscritturaposizionale, mausandometodi diversi che fornisconodescrizioni del numerostesso,descrizionichepossonoessereditipovario:algebrico,geometrico,analitico,. . .Cos`ilsimbolo2signicailnumerorealepositivoilcuiquadrato `e2(descrizionedi tipo algebrico), `e il nome del rapporto tra la lunghezza della circonferenza e quelladel diametro(descrizionegeometrica), eindicail limitedellasuccessioneSn=(1 +1n)n(descrizioneanalitica).Apartiredainumerirazionaliedaalcuninumerirealiimportanti(quellisopraintro-dottiepochialtri)altrinumerirealipossonoessereindividuatimediantescritturemiste,incuiintervengonooperazionie/ofunzioni,deltipo: + e2,1 152, e2, sin(1), log(2),7 32, e, e.Potremmocontinuarealungoafareesempiviaviapi` ucomplicatidiscritturedinumerireali; ma nonostante i nostri sforzi la maggior parte dei numeri reali rimane totalmente aldi fuori della nostra possibilit`a di scrittura esplicita o di descrizione mediante una qualchepropriet`a!9.3 NumerialgebricienumeritrascendentiLascritturaposizionaledei numeri reali permettedi dimostrarechelacardinalit`adi R`epi` uchenumerabile(cfr. Esempio4.2.12)equindi cheesistonomolti numeri realinonrazionali.Inumerirealinonrazionalisidicononumeriirrazionalieformanouninsieme I= R Qdicardinalit`api` uchenumerabile.Se,infatti,siavesseCard(I) 0,allorasiavrebbeancheCard(R) = Card(Q I) Card(Z+ Z) = Card(Z) = 0.Universit`adiTorinoCapitolo9Ilcampo Rdeinumerireali 93Per ulteriori approfondimenti consigliamo la lettura del libricino di Ivan Niven Numerirazionaliedirrazionali(Ed.Zanichelli),checontienemolteinformazioniinteressanti,purtrattandolargomentoinmodoelementare.Una dierente suddivisione dellinsieme dei numeri reali si ottiene a partire dallaseguentedenizione.Denizione9.3.1. Unnumerorealexsi dicealgebricose`eradicedi unpolinomioacoecienti razionali (o, equivalentemente, di unpolinomioacoecienti interi).IndicheremoconAlinsiemedeinumerirealialgebriciecon TilsuocomplementareinR,icuielementisidicononumeritrascendenti.Trainumerialgebricicisonotuttiinumerirazionali(seq Q,alloraq`eradicedelpolinomio a coecienti razionali Xq) ed anche altri numeri (2 `e radice dellequazioneacoecientirazionaliX22)equindiAcontienestrettamente Q.Pi` u complicato `e provare che A non coincide con tutto R; in modo particolare `e dicilevericaredirettamentelatrascendenzadiuncertonumeroreale,anchedioppurediechesonoinumeritrascendentipi` ufamosi.Sulgi`acitatoNivensipu`otrovareunaprovadiretta, elementare anche se non breve, della trascendenza del numero di Liouville. Non `einvece ancora nota la trascendenza o meno di alcuni numeri del tipo di quelli elencati allanedelprecedenteparagrafo;adesempionon`etuttoranotosee + oppureeoppureesianoalgebriciotrascendenti.Lesistenzadeinumeritrascendentipu`o,daltraparte,esseredimostratainmodopi` usemplice,ancheseindiretto,facendonuovamentericorsoallateoriadellacardinalit`a.Proposizione9.3.2. i)Linsiemedeipolinomiacoecientiinterihacadinalit`anume-rabile.ii)Linsiemedeinumerirealialgebricihacardinalit`anumerabile.Dim: i)SiaF(X)=adXd+ ad1Xd1++ a0unpolinomiononnulloacoecientiinteri di gradod. Chiamiamoaltezzadi F(X) il numeronaturaleh(F) =d + [ad[ +[ad1[ ++ [a0[.Perogninumeronaturalenvi`esolounnumeronitodipolinomidialtezzan.Gliunicipolinomidialtezza1sonoipolinomicostanti1e 1.Ipolinomidialtezza2sonoX, X,2, 2.Ecos`via.Si pu`oalloracostruireunaapplicazionebiunivocaf : N Z[X] nel modoseguente:f(0) = 0Z[X];f(1)ef(2)sonoiduepolinomidialtezza1;f(3),f(4),f(5)ef(6)sonoiquattropolinomidialtezza2,ecos`via.AlloraCard(Z[X]) = Card(N) = 0.ii) Intanto Card(A) 0, poiche tutti i numeri razionali sono algebrici. Proviamo chevaleancheladiseguaglianzaopposta.Ricordiamo che i polinomi a coecienti interi possono essere pensati anche come par-ticolaripolinomiacoecientirealiedhannoquindiunnumerodiradicirealiminoreodugualeallorogrado.QuaderniDidatticidel DipartimentodiMatematica94 M.Roggero-AppuntiedEsercizidiMatematicaDiscretaFissatounnumeronaturaleh ,= 0,cisonosolounnumeronitodipolinomiacoe-cientiinteridialtezzahequindiunnumeronitok(h)dinumerirealialgebricichesonoradici di tali polinomi. Possiamo allora costruire una applicazione g : N A facendo cor-rispondere i primi k(1) naturali alle k(1) radici reali dei polinomi di altezza 1; i successivik(2)naturaliallek(2)radicirealideipolinomidialtezza2,ecos`via.Tale applicazione non `e iniettiva (poiche uno stesso numero algebrico `e radice di tantipolinomi, anche di altezze diverse), ma `e suriettiva per costruzione. Se infatti x `e radice diuncertopolinomioacoecientiinteriF(X)dialtezzah,allorax `eimmaginedialmenounnumeronaturaler k(1) + k(2) + + k(h).AllorasihaCard(A) Card(N) = 0equindiCard(A) = 0. Corollario9.3.3. Inumeri reali algebrici Aformanounsottoinsiemepropriodi Redanziesisteuninnit`api` uchenumerabiledinumerirealitrascendenti.Possiamoriepilogarequantovistoinquestoparagrafoconleseguenti relazioni insie-mistiche:R = Q I = A Tcon Q A Requindi T I R.Osserviamoper`ochementre Ie Tsonosemplici sottoinsiemi, A, cos` come Q,`eunsottocampodi R,ossiahalastrutturadicampomediantelestesseoperazionidisommaeprodottodi R.Proposizione9.3.4. A`euncampoconleoperazioni di sommaeprodottoindottedaquelledi R.Dim: In questa dimostrazione facciamo ricorso a propriet`a degli spazi vettoriali che sonotrattatinelcorsodiGeometria2.Proviamo che opposti, inversi, somme e prodotti di numeri algebrici sono ancoranumerialgebrici.Sex`eradicedel polinomioacoecienti interi adXd+ ad1Xd1++ a1X+ a0,allora x `e radice di adXd+(1)ad1Xd1+ +(1)d1a1X+(1)da0e analogamentex1`eradicediad + ad1X + + a1Xd1+ a0Xd.Sianooraxey duenumeri algebrici radici rispettivamentedei polinomi monici acoecienti razionali F(X) = Xd+bd1Xd1+ +b1X +b0e G(X) = Xr+cr1Xr1+ +c1X+c0. Si ha allora F(x) = 0 da cui xd= bd1xd1 b1xb0 e analogamenteG(y) = 0dacuiyr= cr1yr1 c1y c0.LinsiemeV dellecombinazioni lineari acoecienti in Qdi elementi del tipoxy,, N,`eunospaziovettorialesu Q,che,graziealleprecedentirelazioni,risultaaveredimensione dr.Infatti, ogni potenzadi xconesponente d(ogni potenzadi yconesponente r)pu`o essere scritta come combinazione lineare di potenze di x (risp. di y) di grado inferioreequindi xy[0 d 1, 0 r 1`euninsiemedi generatori di V condrelementi.Alloradr + 1elementiqualsiasidiV sonolinearmentedipendenti.Universit`adiTorinoCapitolo9Ilcampo Rdeinumerireali 95In particolare sono linearmente dipendenti gli elementi (x +y)dr, (x +y)dr1, . . . , (x +y), 1ossiaesisteunarelazioneconcoecientirazionalinontuttinulliqdr(x + y)dr+ qdr1(x + y)dr1+ + q1(x + y) + q0= 0equindix + y`ealgebrico.Allostessomodosiprovache `ealgebricoilprodottoxy. 9.4 Esercizi9.1. Caratterizzaretuttelecoppiedi numeri razionali (a, b)t