APPUNTI DI ALGEBRA Marialuisa J. de Resmini Capitolo 1 Elementi di teoria degli insiemi 1.1 Premessa, nozioni primitive, prime definizioni e proprietà Premettiamochequantosaràespostosullateoriadegliinsiemiriguardala cosiddetta teoria ”ingenua” degli insiemi, dedotta dalla teoria cantoriana, chesicontrapponeallateoriaassiomatica,perilsemplicefattoche,purba- sandosistrettamentesuiprincipielementaridellalogicabinaria(cioèdella logicaaduevalori: veroofalso,sìono),faspessoricorsoall’intuizione. Comeinogniteoriamatematica,ovverosistemaipotetico-deduttivo,ri- sultaessenzialeassumerecomeprimitivialcuniconcetti,concetti,cioè,che non vengono definiti, ma che (traducendo nozioni comuni facilmente ac- cessibilialivellointuitivo)vengonocaratterizzatimedianteleloroproprie- tà. Evidentemente, dal punto di vista di un’impostazione il più assioma- tica possibile, risulta conveniente assumere il numero minimo di nozioni primitive. Pertanto nella teoria ingenua degli insiemi assumeremo come concetti primitivilanozionediclasseelarelazionediappartenenza. Intenderemo per classe un qualunque aggregato, collezione di enti di natura qualsiasi, che chiameremo elementi o oggetti della classe stessa. Ne segueche,assegnataunadataclasse,ècontemporaneamentedatalapossi- bilitàdidecidereseunqualunqueoggettoesistenteopensabilesiaomeno oggettodiquellaclasse. Se allora A è una qualunque classe ed a è un elemento della classe A, diremoche a appartieneallaclasse A ovvero,insimboli: a ∈ A. Restacosìgiustificatalasecondanozioneprimitiva,cioèlarelazionedi appartenenza. 1 2 CAPITOLO1. ELEMENTIDITEORIADEGLIINSIEMI Inoltre,perdenotareilfattocheuncertooggettobnonappartieneaduna certaclasseA,siscriverà: b 6∈ A. Per assegnare una classe, è necessario specificare gli elementi che essa contiene;ciòpuòesserefattointremodiapparentementediversi: 1) sispecificanoinparoleleproprietàdellequalidevegodereunogget- toperappartenereallaclasseinquestione; ades., dicendocheAèla classedituttiitriangolidiuncertopiano,laclasserestaperfettamen- teindividuata; 2) sielencanoglielementidellaclasseA;ades.,seAèlaclassecostituita datuttiidivisori(positivi)delnumeronaturale30,siscriverà: A = {1, 2, 3, 5, 6, 10, 15, 30}; 3) siscrivonosimbolicamenteleproprietàdellequalidevonogoderegli elementidellaclasse; ades., seAèlaclassedituttiinumerinaturali divisibiliper5,siscriverà: A = {x ∈ N : 5|x} N dovecon indicheremoperilmomentolaclassedituttiinumerina- turali(cioègliinteripositivi)zeroescluso(anchesespessosiinclude N lozeroin ;perdenotarelaclassedeinaturalizerocompreso,usere- molanotazioneN ); ilsimbolo”:”staadindicarel’espressione”tale 0 che”(perlamedesimaespressionesiusaancheilsimbolo|);infinela scrittura ”5|x” traduce simbolicamente la frase ”5 divide x”, ovvero ”5 è un divisore di x” (il fatto che ”|” si usa per ”divide” fa preferire lascrittura”:”per”taleche”). Ora, la nozione di classe è estremamente generale; siamo interessati a classiparticolari,icosiddettiinsiemi. Precisamente,diremocheunaclasseAèuninsiemeseesisteunaclasse B dellaqualeAèunoggetto. Notiamo che tutte le classi dei precedenti esempi risultano, di fatto, insiemi. Sembra allora inutile fare questa distinzione tra insieme e classe; l’inu- tilitàèsoltantoapparente,inquantoladistinzioneèresanecessariaalfine dievitarealcuniparadossi,come,adesempio,ilseguente. ConsideriamolaclasseΣdituttigliinsiemipensabili;sorgelaquestio- ne di decidere se Σ è o meno un insieme. Se Σ fosse un insieme, allora esisterebbeunaclasseΣ0 dellaqualeΣsarebbeunelemento,eciòcontrad- direbbeladefinizionediΣ;pertantoΣèunaclasse(antinomiadellaclasse totale). 1.2. INCLUSIONETRAINSIEMI.EGUAGLIANZADISUEINSIEMI... 3 Lanascitadellateoriadegliinsiemi(GeorgeCantor,1845-1918)hacon- temporaneamente dato luogo alla scoperta di numerose ”antinomie” rela- tive alla teoria stessa, che mostravano la sua possibilità di definire in ma- niera rigorosa un insieme, onde la soluzione ”ingenua” che è stata adot- tata1. Comunque, un esame approfondito della questione, oltre ad essere tutt’altro che semplice, esula dai limiti di questa esposizione; per l’esame, rimandiamoaitestidilogicaedicriticasuifondamentidellamatematica. Osserviamocheleclassicheavremooccasioneditrattaresarannoqua- si sempre insiemi; quindi, d’ora in avanti, salvo esplicito avviso, conside- riamoesclusivamenteinsiemi,descrivibilipertantoneimodidetti,conl’au- siliodialtrisimbolichesarannoviaviaintrodotti. Notiamopurecheilter- mine”classe”verràancheadottatoconunaltrosignificato(comeabbrevia- zione sia di ”classe di equivalenza”, che di ”classe laterale”); dal contesto appariràsemprechiaro,però,ilsignificatodelterminestesso. 1.2 Inclusione tra insiemi. Eguaglianza di sue insie- mi. Insieme vuoto. Insieme universale. SianoAeB dueinsiemiqualsivoglia. Seaccadecheognielementodell’in- siemeB èancheelementodell’insiemeA,diremocheB ècontenutoinA;in simboli: B ⊆ A La ”relazione” che intercorre tra B ed A prende il nome di relazione di inclusione (in senso lato); se poi esiste qualche elemento di A che non è elementodiB (ilchenonèimplicitonelladefinizioneprecedente),diremo cheBèstrettamentecontenutoinA(inclusioneinsensostretto)escriveremo: B ⊂ A Introducendo alcuni simboli (dei quali faremo ampiamente uso), pos- siamoscrivereinmanierapiùcontrattaquantogiàdettoinparole;precisa- mente: B ⊆ A ⇐⇒ [∀x ∈ B ⇒ x ∈ A] 1Indefinitiva, inmoltediquesteantinomiesivieneanegareilprincipiodel”terzoe- scluso”,basilarenellalogicabinaria,cheprevedeche,seP èunaqualunqueaffermazione, P nonpuòesserecontemporaneamenteveraefalsa.Seunateoriamatematicacontieneuna qualunqueproposizioneP,talechesianovere(cioèdimostrabili)tantoP quantolasuane- gativa,allorataleteoriaèindecidibile,perchècontieneunacontraddizione.Piùingenerale, siottieneunaantinomia,oparadosso,quandol’enunciatocontieneunadefinizioneimpre- dicativa; precisamentequandouninsiemeM edunoggettomsonodefinitiinmodotale chemèunelementodiM,maèdefinitosoltantofacendoriferimentoadM,ladefinizione diM,odim,sidiceimpredicativa. 4 CAPITOLO1. ELEMENTIDITEORIADEGLIINSIEMI chesilegge: ”B contenutoinAse,esoltantose,qualesiaxappartenentea B,risultachexappartieneadA”. Analogamente B ⊂ A ⇐⇒ [∀x ∈ B ⇒ x ∈ A e ∃y ∈ A : y 6∈ B] cioè ”B è contenuto in senso stretto in A se, e soltanto se, ogni elemento x di B è elemento di A ed esiste almeno un elemento y di A che non sia elementodiB”. Spieghiamooraisimboliintrodotti: ⇒ èilsimbolodell’implicazionesemplice: seP eQsonodueproposizioni (affermazioni),scrivendoP ⇒ Q,intendiamochel’affermazioneQèlogica conseguenza dell’affermazione P (ma non è necessariamente vero il vice- versa); adesempio,seP èl’affermazione: ”aèunparallelogramma”eQè l’affermazione: ”a è un quadrilatero”, si può scrivere P ⇒ Q ma Q 6⇒ P (unquadrilaterononènecessariamenteunparallelogramma). ⇐⇒ è il simbolo della doppia implicazione: Se P e Q sono due afferma- zioni, scrivendo P ⇐⇒ Q, intendiamo dire che esse sono logicamente equivalenti(se,esoltantose; occorreebasta; ènecessarioesufficiente); ad esempio,”nèunnumeropari”ed”nèdivisibileper2”(nessendounnu- meronaturale)sonodueaffermazioniequivalenti. ∀ èilsimboloperindicareespressionideltipo”perogni”,”qualechesia”, ecc.;edèunodeicosiddetti”quantificatori”,precisamenteilquantificatore universale. ∃ è il quantificatore esistenziale; con tale simbolo si identificano tutte le vocidelverbo”esistere”;sepoisivuolprecisarecheuncertooggetto,oltre adesistere,èunico,siusalascrittura∃!. Useremo poi la congiunzione ”e” per indicare che due affermazioni devonovalerecontemporaneamente. Notiamoinfinechesinegaunsimbolo,barrandolo,adesempio: 6 ∃ significa ”nonesiste” 6∈ significa ”nonappartiene” 6⇒ significa ”nonimplica” ecosìvia. Infine, dato che la frase ”se e soltanto se” ricorre frequentemente in matematica,abbrevieremotaleespressionecon”sse”. Passiamo ora a definire l’ ”eguaglianza” di due insiemi, tenendo pre- sentechevogliamo”migliorare”lanozioneintuitivadieguaglianza;infatti, l’unico tipo di eguaglianza che logicamente abbia significato è la cosidetta ”identitàlogica”: dueoggettisonoegualissesonolostessooggetto. Diconseguenza,seAeB sonodueinsiemi,diremocheAèegualeaBe scriveremo: A = B 1.2. INCLUSIONETRAINSIEMI.EGUAGLIANZADISUEINSIEMI... 5 sse ogni elemento di A è elemento di B e viceversa. Con la simbologia precedentementeintrodotta,scriveremo: A = B ⇐⇒ [∀x ∈ A ⇒ x ∈ B e ∀y ∈ B ⇒ y ∈ A] oppure A = B ⇐⇒ [x ∈ A ⇐⇒ x ∈ B] (le parentesi quadre vengono adottate per precisare la proposizione che vieneimplicata). Ora, la seconda scrittura risulta indubbiamente più concisa della pri- ma, ma questa, tenendo presente la definizione di inclusione, permette di scrivere: A = B ⇐⇒ [A ⊆ B e B ⊆ A] Quest’ultimaespressionedellaeguaglianzadidueinsiemièquellache sideveimpiegareperverificareodimostrarechedueinsiemisonodifatto eguali,cioèsonolostessoinsieme. Se non si precisa alcuna inclusione, e se non è A = B, si dirà che A è diversodaB,esiscriveràA 6= B. Siano ora A e B due insiemi, e sia A ⊆ B; diremo che A è una parte di B,ovverocheAèunsottoinsieme(abbreviatoins.i.) diB. SepoiA ⊂ B,di- remocheAèuns.i. propriodiB. Pertanto,ogniinsiemesipuòinterpretare comes.i. diséstessoesidiràs.i. improprio. Se dati A e B, non risulta nè A ⊆ B nè B ⊆ A, A e B si dicono anche inconfrontabili. Dal punto di vista logico, ha significato considerare insiemi che non contengonoalcunoggetto(adesempiol’insiemedeitriangolicon4vertici); un insieme di questo tipo prende il nome di insieme vuoto ed è convenzio- nalmentedenotatoconilsimbolo∅. Dunque: ∅ = x : x 6= x xessendounqualunqueoggetto. Poichèx = x,perdefinizionediidentità logica, x 6= x rappresenta una contraddizione, onde ∅ non può contenere alcunoggetto. Notiamochel’insiemevuotoèunico,cioènonesistono”diversiinsiemi vuoti”,eciòinbasealladefizione. Assumiamochel’insiemevuotosiasottoinsiemediqualunqueinsieme; taleaffermazionepuòperòvenirprovatainmanieraabbastanzasemplice. Talvoltasihalanecessitàdiconsiderarecontemporaneamentepiùinsie- mi,erisultaconvenientepoterinterpretarequesticomes.i. diunmedesimo insieme,atalscoposiintroduceilcosidettoinsiemeuniversale(rispettoaun datoproblema: laproprietàdiessereuniversaleèrelativaalproblema),che èuninsiemetaledacontenerecomesuoisottoinsiemi(proprieøimpropri) tutti gli insiemi che interessa prendere in considerazione. Per esempio se 6 CAPITOLO1. ELEMENTIDITEORIADEGLIINSIEMI si considerano vari insiemi di poligoni di un piano, si può assumere come insiemeuniversalel’insiemedituttiipoligonidelpiano. Notiamo che il simbolo ”⊆” si può invertire. Precisamente, se A ⊆ B, cioè ”A è comtenuto in B”, allora è evidente che ”B contiene A” e per esprimerequestofattosiscriverà B ⊇ A 1.2. INCLUSIONETRAINSIEMI.EGUAGLIANZADISUEINSIEMI... 7 Esercizi Esercizio1.2.1. Determinarealcunideisottoinsiemidell’insiemeAdeiquadrila- teridiunpianoeleeventualirelazionidiinclusionetraessi. Sol.: SonosottoinsiemidiA: I = insiemedeiquadrilateriinscrittibiliinunacirconferenza; C = insiemedeiquadrilatericircoscrittibiliadunacirconferenza; P = insiemedeiparallelogrammi; R = insiemedeirettangoli; L = insiemedeirombi; Q = insiemedeiquadrati. (Questi sottoinsiemi di A non esauriscono, ovviamente, la ttalità dei sot- toinsiemidiA). Lerelazionidiinclusionetraessisonoleseguenti, comeè immediatoverificareinbasealledefinizionidellageometriaelementare: Q ⊆ R ⊆ I; Q ⊆ R ⊆ P; Q ⊆ L ⊆ P; Q ⊆ L ⊆ C Esercizio1.2.2. Determinareisottoinsiemipropri6= ∅deitreseguentiinsiemi: S = {a}; S = {a,b}, (a 6= b); S = {a,b,c}, (a 6= b, a 6= c, b 6= c) 1 2 3 Sol.: I sottoinsiemi di S sono ∅ ed S , onde S non possiede sottoinsiemi 1 1 1 propri,distintida∅. Isottoinsiemipropri6= ∅diS sono: {a},{b}. 2 Infine,isottoinsiemipropridiS sono: {a},{b},{c},{a,b},{a,c},{b,c}. 3 Esercizio1.2.3. Dimostrareche,seAèunsottoinsiemedell’insiemevuoto,allora A = ∅. Dim.: Osserviamo innanzitutto che, per provare che due insiemi X e Y coincidono,bisognamostrarechevalgonoentrambelerelazionidiinnclu- sione: X ⊆ Y ed Y ⊆ X. Ora, per ipotesi, A ⊆ ∅; d’altra parte l’insieme vuotoèsottoinsiemediogniinsieme,cioè∅ ⊆ A. NesegueA = ∅. Esercizio 1.2.4. Tenendo presente la seguente definizione di insieme contenente unsoloelemento: Def.: UninsiemeS ècostituitoesattamentedaunelementose: 1) S 6= ∅ 2) l’unicos.i. propriodiS è∅, sidefiniscainmanieraanalogauninsiemecostituitoesattamentedadueelementi. 8 CAPITOLO1. ELEMENTIDITEORIADEGLIINSIEMI Sol.: La seguente definizione traduce in maniera rigorosa la nozione intui- tivadiinsiemecostituitodadueelementi: Def.: Diremochel’insiemeS ècostituitoesattamentedadueelementise: 1) S hauns.i. propriodistintoda∅; 2) ognis.i. propriodiS distintoda∅,ènecessariamentecostituitodaun soloelemento. Si noti che è immediato estendere la precedente definzione, ottenendo quelladiinsiemecontenenteesattamentenelementi. 1.3. INTERSEZIONEEDUNIONEDIINSIEMI... 9 1.3 Intersezione ed unione di insiemi e loro proprietà. Assegnati due o più insiemi, è possibile costruire, a partire da questi, dei nuovi insiemi, e ciò in più modi (ottenendo - evidentemente - insiemi dif- ferenti). Dati due insiemi A e B, i più semplici insiemi che, mediante essi, si possono costruire sono l’insieme intersezione di A e B e l’insieme unione diAeB,cheorapassiamoadefinire. Precisamente,datiAeB,definiamoinsiemeintersezione,osemplicemen- teintersezione,diAeB,elodenotiamoconilsimbolo: A∩B (daleggersi”AintersezioneB”),l’insiemedescrittoda: A∩B = {x : x ∈ A e x ∈ B}; A∩Bèquindil’insiemedituttiglielementicheappartengonocontempora- neamente all’insieme A ed all’insieme B (si noti la congiunzione ”e” nella definizione). Ad esempio, se A è l’insieme dei divisori di 30 e B è l’insieme dei divisoridi20,allora A∩B = {1,2,5,10} Evidentemente, è possibile che non esista alcun elemento che appartenga contemporaneamenteadAeB;intalcaso,risulta: A∩B = ∅ ed A e B si dicono disgiunti. Ad esempio, se A è l’insieme dei triangoli di unpianoeB l’insiemedeiquadratidiunpiano,risultaA∪B = ∅. Dalladefinizionediinsiemeintersezioneseguesubitoche: A∩B = B∩A eciòesprimelaproprietàcommutativadell’intersezione. Ancoradalladefinizionesegueche: ∀x ∈ A∩B ⇒ x ∈ A ∀x ∈ A∩B ⇒ x ∈ B PertantoA∩B èunsottoinsiemesiadiAchediB. SupponiamoorachesiaB ⊆ A;risultaalloraA∩B = B. Inparticolare, seA = B,essendoA ⊆ Asiavrà: A∩A = A cheesprimel’idempotenzadell’intersezione.