Fabio Bellissima - Fondamenti Di Matematica

i a edizione, settembre 2008 © copyright 2008 by Carocci editore S.p.A., Roma

Finito di stampare nel settembre 2008 da Eurolit, Roma

I S B N 978-88-430-4687-4

Riproduzione vietata ai sensi dì legge (art. 171 della legge 22 aprile 1941, n. 633)

Senza regolare autorizzazione, è vietato riprodurre questo volume anche parzialmente e con qualsiasi mezzo, compresa la fotocopia, anche per uso interno 0 didattico.

1 lettori che desiderano informazioni sui volumi pubblicati dalla casa editrice possono rivolgersi direttamente a: Carocci editore

Via Sardegna 50 00187 Roma. T E L 06 42 81 84 17

FAX 06 42 7 4 7 9 3 1

Visitateci sul nostro sito Internet: http://www.carocci.it

http://www.carocci.it

Fabio Bellissima

Fondamenti di matematica

Carocci editore

Indice

1. Gli insiemi numerici 7

1.1. I numeri naturali 7 1.2. Dai numeri naturali ai numeri interi 11 1.3. Dai numeri interi ai numeri razionali 14 1.4. Incompletezza dell'insieme dei numeri razionali 20 1.5. Dai numeri razionali ai numeri reali 23 1.6. Un modello riassuntivo 30

2. Teoria degli insiemi 33

2.1. Infinito attuale e infinito potenziale 33 2.2. Primi elementi della teoria degli insiemi 37 2.3. Espressioni insiemistiche e formule logiche 45 2.4. Prodotto cartesiano 50 2.5. Relazioni 51 2.6. Funzioni 57 2.7. Operazioni 61 2.8. Cardinalità di insiemi infiniti 63

3. Strutture algebriche 77

3.1. Gruppi 78 3.2. Algebre di Boole 102

4. Ritorno agli insiemi numerici 111

4.1. La costruzione insiemistica dei numeri 111 4.2. Le classi numeriche come strutture algebriche 117

Indice analitico e dei nomi 123

l. Gli insiemi numerici

Questo primo capitolo è dedicato ad una rapida riorganizzazione di quei ricordi che ciascuno di noi ha intorno ai vari tipi di numero, ricordi in base ai quali riesce ad impiegare con successo i numeri stessi. In questa fase iniziale, la maggiore attenzione sarà riservata ai passaggi da un insieme numerico all'altro (dai numeri naturali agli interi, poi ai razionali, infine ai reali), approfittando della concisio-ne per avere uno sguardo complessivo della materia. Nel capitolo finale ritorneremo sulle classi numeriche in modo più rigoroso, po-tendo impiegare i concetti insiemistici e algebrici incontrati nel frattempo. Che tanta parte di un testo di fondamenti di matematica sia dedica-ta ai numeri non deve stupire. Gli insiemi numerici non solo rap-presentano la base su cui la matematica si è sviluppata ma anche, considerati singolarmente, le tappe di uno dei più importanti cam-mini della conoscenza sia collettiva sia individuale. Il processo sto-rico attraverso il quale i vari tipi di numero sono stati definiti e il percorso didattico tramite il quale ciascuno di noi li ha appresi dif-feriscono però in modo significativo. Nel primo, che come tutti i processi storici non è lineare, l'introduzione dei numeri negativi è di due millenni successiva alla trattazione dei rapporti razionali e ir-razionali. Nel secondo, frutto di una sistemazione effettuata a poste-riori, si procede invece in modo ordinato, dalle classi più piccole a quelle più grandi, e quindi la presentazione dei numeri interi nega-tivi precede quella dei numeri razionali, che a sua volta precede quella dei numeri irrazionali. Naturalmente, dato il carattere intro-duttivo del testo, seguiremo questa seconda strada, ma cercheremo, per quanto possibile, di presentare i concetti principali anche da un punto di vista storico. Il punto di partenza è comunque, in ogni caso, costituito dall'insieme dei numeri naturali.

1.1. I numeri naturali L'insieme dei numeri naturali N = {1, 2, 3, 4,...} presiede all'operazione del contare. Contare gli elementi di un insieme (finito) A significa infatti porre tali elementi in corri-

spondenza con un segmento iniziale dell'insieme N, descritto ordi-natamente dalla filastrocca uno-due-tre-quattro... . Il numero degli elementi di A, che corrisponde all'ultimo numero pronunciato, vie-ne indicato con Card(A) e definito cardinalità di A. L'espressione n < m indica che il numero naturale n è minore del numero natu-rale m, mentre l'espressione n < m indica che n è minore o uguale a m. Per converso, i simboli > e > indicano le relazioni di maggiore e maggiore o uguale. Il numero 0, di solito, non è considerato un ele-mento di N. L'insieme dei numeri naturali comprendente anche lo 0 è indicato con N 0 . Tra i numeri naturali si stabiliscono le operazioni di addizione, sot-trazione, moltiplicazione e divisione, il cui studio costituisce la base dell'aritmetica. Tali operazioni differiscono tra di loro riguardo al-l'eseguibilità e, come vedremo, sarà proprio questa una delle ragio-ni del passaggio a nuove classi numeriche.

l.l.l. Le anomalie della sottrazione e della divisione Le operazioni di addizione e di moltiplicazione associano ad ogni coppia di numeri naturali uno e un solo numero naturale. Ad esempio, alla coppia (5,3) l'addizione (o somma) associa il numero 8, la moltiplicazione (o prodotto) il numero 15.

( 5 , 3 ) — ^ 8 ; ( 5 ,3 ) -* -* 15.

Anche l'operazione di sottrazione associa a coppie di numeri natu-rali uno e un solo numero naturale, ma non a tutte le coppie, come invece accade per la somma e il prodotto. Ad esempio, alla coppia (5,3) la sottrazione associa il numero 2, ma alla coppia (3,5) non associa alcun numero, non essendo eseguibile, all'interno dei nu-meri naturali, l'operazione 3 - 5 . Infatti, affinché la sottrazione sia eseguibile relativamente alla coppia (x,y) deve valerex>y.

(5,3) ^ - > 2 ; ( 3 , 5 ) - ^ - > ?

Passando all'operazione di divisione, si riscontrano ben due anoma-lie. La prima è che, come la sottrazione, essa non è applicabile a tut-te le coppie di numeri naturali, ma solo ad alcune, e precisamente a

quelle in cui il secondo numero è diverso da 0. La seconda è che la divisione dà come risultato due numeri naturali e non uno solo come accaduto finora. Infatti, ai due numeri della coppia di parten-za, il dividendo e il divisore, vengono associati due numeri: il quo-ziente e il resto. Ad esempio, alla coppia (7,3) la divisione associa la coppia (2,1), essendo "7 diviso 3 uguale a 2 con il resto di 1". Quando il resto, cioè il secondo numero della coppia di arrivo, è 0 allora si dice che il dividendo è divisibile per il divisore (o, equiva-lentemente, che il dividendo è multiplo del divisore).

(7,3) — ^ (2,1) ; (6,3) — ( 2 , 0 ) ; (3,6) (0,3) ; (7,0) ^ ?

La disomogeneità nel comportamento delle quattro operazioni arit-metiche non segnala un difetto della classe dei numeri naturali. Come già detto, il loro ruolo consiste nel contare gli elementi di un insieme. Il fatto che la sottrazione tra numeri naturali non sempre sia eseguibile è una conseguenza dell'impossibilità, altrettanto natu-rale, di prendere 10 mele da un canestro che ne contiene 8. Allo stesso modo, il fatto che il risultato di una divisione lasci talvolta un resto è una conseguenza dell'impossibilità di formare con 15 gioca-tori due squadre equinumerose, a meno di tagliare un giocatore in due. In contesti come questi, in cui non ha senso scendere al di sot-to dello 0 oppure suddividere una unità, le operazioni di sottrazio-ne e divisione sono intrinsecamente diverse da quelle di addizione e moltiplicazione, e le anomalie descritte si limitano a segnalare que-sto fatto. Vi sono tuttavia dei contesti in cui tali differenze possono essere superate; bisogna però, come insegna la storiella seguente, non sbagliare contesto.

1.1.2. La storia del vecchio fienile Un contadino, proprietario di un vecchio fienile sperduto nella campagna, racconta ad un fisico, ad un biologo e ad un matematico di aver visto una volta entrare nel suo fienile due individui e di averne, dopo un po' di tempo, visti uscire tre. Il contadino inoltre afferma con sicurezza che il fienile era vuoto prima dell'ingresso dei due e che nessuno è entrato nel frattempo. Al che il fisico, scrutando il colore del naso del contadi-no, asserisce debba trattarsi di una rilevazione sperimentale errata.

Il biologo, che conosce le cose della vita, non rinuncia all'ipotesi che i due possano aver procreato. Invece il matematico, senza scomporsi, sentenzia: "Caro contadino, aspetta che una persona entri nel tuo fienile. A quel punto esso sarà di nuovo vuoto". Come ha ragionato il matematico? Supponiamo, nella storiella, di avere al posto del fienile un conto bancario e, al posto di ciascuna delle persone che entrano ed escono, una certa somma di denaro, ad esempio un milione. Se in un conto, vuoto, entrano due milioni e ne escono tre allora, affinché sia di nuovo a zero, bisognerà farne entrare uno. Proprio come suggerito dal matematico al contadino. E ancora. Se stiamo galleggiando in mare ( = livello 0), poi saliamo su un trampolino alto 2 metri e, nel tuffo successivo, scendiamo di 3 metri (entrando un metro sott'acqua) allora, per tornare a livello 0, dobbiamo salire di un metro: proprio come suggerito dal mate-matico. Ciò che rende assurda, e forse divertente, la storiella del fie-nile è che il matematico fa intervenire nuovi numeri (i negativi) in un contesto che invece è di pertinenza dei numeri naturali. Ma gli altri esempi che abbiamo proposto (crediti e debiti, altitudine e profondità) mostrano come possano esistere situazioni in cui l'in-tervento di nuovi tipi di numero si rivela utile.

1.1.3. Verso nuovi numeri (e nuovi nomi) Il processo che ha portato ad estendere l'insieme dei numeri naturali per ottenere, di volta in volta, i numeri interi, quelli razionali, quelli reali, e anche quelli complessi (che non tratteremo), può essere interpretato come il su-peramento di limiti preesistenti, al fine di affrontare situazioni in

cui tali limiti non hanno più ragion d'essere. Sulle difficoltà concet-tuali che tale superamento ha comportato ci limitiamo ad un'osser-vazione che riguarda il linguaggio. Ad ogni ingresso di nuovi nu-meri si rende necessario non solo un nome per definirli, ma anche un altro nome per definire quelli vecchi (che prima, rappresentan-do la totalità, non avevano bisogno di essere definiti). I nuovi nu-meri della prima ondata sono stati chiamati negativi, e i vecchi nu-meri (prima semplicemente "numeri") sono stati chiamati naturali o positivi. Con la seconda ondata, detta dei frazionari, i numeri preesistenti (cioè i naturali e i negativi) sono stati chiamati interi. Con l'arrivo dei numeri irrazionali, quelli già sul posto (gli interi e i frazionari) sono stati chiamati razionali; con l'ultima ondata, quella degli immaginari, gli stanziali (cioè i razionali e gli irrazionali) sono stati chiamati reali. Abbiamo dunque oggetti definiti naturali, inte-ri, razionali, reali a cui sono stati contrapposti oggetti definiti nega-tivi, frazionari, irrazionali, immaginari. Senza eccezione, i nomi dei numeri preesistenti esprimono positività, quelli dei nuovi arrivi ne-gatività. Non è difficile scorgere in questo un segno dello sforzo concettuale che questi allargamenti di campo hanno comportato.

1.2. Dai numeri naturali ai numeri interi II passaggio dall'in-sieme N dei numeri naturali all'insieme Z dei numeri interi elimina le anomalie della sottrazione. Il nuovo insieme è ottenibile " raddop-piando" il vecchio. L'insieme originale viene denotato, oltre che con N, anche con Z + , e i suoi elementi sono chiamati, oltre che numeri naturali, anche numeri interi positivi. La copia è denotata con Z", i

FIGURA 2

L'insieme Z dei numeri interi

negativi positivi

- 3 - 2 - 1 0 1 2 3

Z + (-N)

Z

suoi elementi sono chiamati numeri interi negativi e sono distinti da-gli originali anteponendo loro il segno "—". L'insieme Z si ottiene dall'unione di Z + e Z~ disponendoli, separati dallo 0, come in figura 2. Ogni elemento è maggiore di tutti gli elementi alla sua sinistra ed è minore di quelli alla sua destra (• • • - 2 < - 1 < 0 < 1 < 2 • • • )• Una volta costruito l'insieme numerico Z, bisogna ridefinire su di esso l'addizione, la moltiplicazione, la sottrazione e la divisione, fa-cendo in modo che le nuove operazioni, se applicate a coppie di in-teri positivi (cioè di numeri naturali), diano gli stessi risultati di quelle vecchie. È pertanto lecito parlare delle nuove operazioni come di "estensioni" delle vecchie sul nuovo dominio. Per poter fare ciò è opportuno disporre di due funzioni: la funzione di pas-saggio all'opposto e la funzione valore assoluto. La funzione di passaggio all'opposto (o funzione opposto) viene indica-ta con il simbolo - ed è definita come segue: - (» ) = —n (cioè: l'op-posto di « è -ri) e - ( - « ) = n (cioè: l'opposto di —n è ri). Ad esem-pio, - ( 5 ) = - 5 e - ( - 5 ) = 5. (Osserviamo che il segno " - " è stato fin qui usato con tre significati distinti: per indicare la sottrazione su N, per contrassegnare gli elementi di Z~ e per indicare la funzio-ne di passaggio all'opposto.) 11 valore assoluto di x è indicato con 1x1, ed è x stesso se x è positivo, il suo opposto se x è negativo (ad esempio, 151 = 5 e 1-51 = 5). Inol-tre, 101 = 0. Possiamo ora definire le operazioni su Z. Momentaneamente, per indicare le operazioni nuove, impieghiamo simboli in grassetto, in modo da poterle distinguere dalle vecchie operazioni su N, di cui già disponiamo.

1.2.1. Addizione Un modo intuitivo ed efficace di presentare la somma su Z consiste nell'interpretarla come la composizione di due movimenti. Dati x,y e Z, la procedura per eseguire x + y può essere descritta nel modo seguente: partendo dallo 0 si compiono Ixl passi verso destra se x > 0, verso sinistra se x < 0; dopodiché, partendo da dove si è giunti, si compiono \y\ passi, verso destra se y> 0, verso sinistra se y < 0. Il punto di arrivo è proprio x + y. In figura 3 è rappresentata la somma (-3) + 5 = 2. Per procedere in modo più formale distinguiamo tre casi.

FIGURA 3 La somma - 3 + 5 come composizione di movimenti

5 passi a destra r *

. . . * * * * * * * - 3 - 2 - 1 0 1 2 3

»t. ^ 3 passi a sinistra

1. Se x ey sono entrambi maggiori o uguali a 0, cioè sono entrambi numeri naturali, allora x + y = x + y. (Si osservi come l'operazio-ne a destra dell'uguaglianza sia la vecchia addizione). 2. Se x e y sono entrambi minori di 0 allora x + y = -(Ixl + l_yl). (Per i numeri naturali, quali sono Ixl e \y,\ già disponiamo, oltre che della somma, anche del valore assoluto e del passaggio all'oppo-sto.) 3. Se x e y sono di segno opposto, ad esempio x > 0 e y < 0, allora bisogna distinguere due sottocasi: se Ixl > \y\ allora x + y = Ixl - \y\, mentre se Ixl < \y\ allora x + y = ~(\y\ - Ixl). (Nelle scritture Ixl -\y\ e lyl — W il segno — indica la sottrazione tra numeri naturali, di cui già disponiamo.) Un esempio riepilogativo:

( N U O V A O P E R A Z I O N E ) ( V E C C H I E O P E R A Z I O N I )

3 + 5 = 3 + 5 ( -3) + ( -5) = - ( 3 + 5) ( -3) + 5 = 5 - 3 ( -5) + 3 = - ( 5 - 3 )

Il punto 1 ci assicura che la nuova somma tra numeri interi, quando applicata ai vecchi elementi (gli interi positivi, cioè i numeri natu-rali) coincide con la vecchia somma. Il fatto che un'operazione nuova, quando applicata agli elementi vecchi, si comporti come l'o-perazione vecchia è, come vedremo, un dato costante di ogni esten-sione della classe dei numeri e ha, ovviamente, un'importanza fon-damentale; ci permette, qualunque sia il contesto numerico a cui ci

si riferisce, di parlare in modo unitario di somma, di prodotto ecc., e di usare gli stessi simboli, senza rischi di ambiguità. Dalle definizioni precedenti si ricava la proprietà che lega la somma tra interi con la funzione opposto: - ( x + y) = (-x) + (-jy).

1.2.2. Sottrazione La sottrazione tra numeri interi è definita in que-sto modo: x— y = x + (—y). Poiché disponiamo sia della funzione opposto che, a questo punto, della somma tra interi, la nuova ope-razione è ben definita. Inoltre, non essendo stato posto alcun vinco-lo alla sua esecuzione, la sottrazione tra interi ha superato l'anoma-lia che caratterizzava la sottrazione tra naturali.

1.2.3. Moltiplicazione Bisogna distinguere due casi. 1. Se x e y sono di segno concorde (cioè entrambi positivi o en-trambi negativi) allora x X y = Ixl X \y\. 2. Se x ey sono di segno discorde allora xX. y = — (Ixl X L_yl). (L'o-perazione è ben definita; infatti, essendo Ixl e \y\ numeri naturali, tra di essi può applicarsi il vecchio prodotto.) Il prodotto soddisfa le seguenti regole:

(-x) X (-y) = x X y (a parole: il prodotto degli opposti di due numeri coincide con il prodotto dei numeri stessi)

(-x) X j/ = x X (-y) = - ( x X y) (a parole: il prodotto di un nu-mero con l'opposto dell'altro coincide con l'opposto del prodotto dei numeri stessi). Per terminare il compito di estendere le quattro operazioni da N a Z bisognerebbe ancora definire la divisione. Ma quello dei numeri interi non è l'ambiente idoneo per tentare di superare le anomalie della divisione. Per farlo, bisogna invece ampliare ulteriormente l'insieme dei numeri, passando dall'insieme Z dei numeri interi al-l'insieme Q d e i numeri razionali, di cui Z è un sottoinsieme. A quel punto la divisione tra due interi diverrà un caso particolare di divi-sione tra razionali.

1.3. Dai numeri interi ai numeri razionali I numeri raziona-li, il cui insieme è indicato con Q, possono essere rappresentati in due modi differenti: in modo decimale (i cosiddetti numeri con la

virgola), e in modo frazionario, come rapporto tra numeri interi di cui il secondo diverso da 0 (ad esempio, 3/2, -5 /8 ) .

1.3.1. La forma decimale Come abbiamo visto, la divisione tra nume-ri naturali, che d'ora in poi chiameremo divisione euclidea, fornisce come risposta una coppia di numeri (quoziente e resto) e non un nu-mero singolo. La presenza del resto indica una sorta di incompiutez-za dell'operazione. Con la divisione con la virgola si supera tale in-compiutezza, in questo modo. Quando la divisione euclidea termi-na, se c'è un resto non nullo (cioè diverso da 0) allora si mette una virgola (un punto nella scrittura anglosassone) al fondo del quozien-te e, dopo aver moltiplicato per 10 tale resto, si procede ancora con l'algoritmo della divisione euclidea, ogni volta moltiplicando per 10 i resti non nulli e arrestandosi solo quando (e se) si incontra un resto uguale a 0. Possono verificarsi tre situazioni diverse. 1. Il resto della divisione euclidea è 0 (il che accade quando il dividen-do è multiplo del divisore). In tal caso il risultato è un numero natura-le e la divisione con la virgola coincide con quella euclidea (FIG. 4A). 2. Il resto della divisione euclidea non è 0, ma il processo si arresta dopo un numero finito di cifre dopo la virgola (dette cifre decima-li), con l'incontro di un resto uguale a 0. In tale caso il quoziente è un numero (positivo) decimale finito (FIG. 4B). 3. Il resto della divisione euclidea non è 0 e il processo non si arre-sta (FIG. 4C). Il terzo caso rappresenta quello in cui più ci si allontana dai numeri naturali. Tuttavia, non è possibile che il quoziente contenga infini-te cifre decimali disposte in modo "imprevedibile". Infatti, o subito

FIGURA 4

Dalla divisione euclidea alla divisione con la virgola

1 4 L_7 14 |_8_ • 14 l i - 1 4 I IL 1 4 IL

0 6 N - 601175 3 n~ 30T2727... 4 0 80

= = 30 80

® ® -, ©

dopo la virgola oppure dopo un numero finito di cifre decimali, le ulteriori cifre devono ripetersi seguendo un ciclo. La sequenza di ci-fre che compone il ciclo si chiama periodo, l'eventuale sequenza di cifre tra la virgola e l'inizio del periodo si chiama antiperiodo, e il numero complessivo che otteniamo come quoziente si chiama nu-mero (positivo) decimale periodico. Le cifre appartenenti al periodo sono identificate mediante una soprallineatura, oppure racchiuden-dole tra parentesi tonde (il risultato dell'esempio in figura 4C si scrive dunque 1,27 oppure 1,(27)). Il fatto che le cifre decimali, se sono infinite, debbano comunque ripetersi in modo ciclico è cru-ciale in quanto, come vedremo, rappresenta l'elemento che distin-gue i numeri razionali da quelli irrazionali. Dall'unione dei numeri naturali con i numeri decimali finiti e con i numeri decimali periodici (che insieme costituiscono tutti i possi-bili risultati delle divisioni tra numeri naturali) si ottiene l'insieme dei numeri razionali positivi, indicato con Q + . L'ordinamento tra due numeri razionali positivi a e b espressi in forma decimale si stabilisce in modo simile a quello tra due parole: si confrontano dapprima le due parti intere Int(tf) e Int(£), cioè i numeri a e b privati della parte decimale. Se Int(^) < Int(£) allora a Int(^) allora a > b\ se invece Int(a) = Int(^) allora si confrontano le pri-me cifre decimali. Se sono diverse allora quella maggiore renderà maggiore il numero a cui appartiene, se sono uguali si passa alle se-conde cifre e così via, fino a trovare la prima coppia di cifre diverse: esse determineranno quale tra a e b è il maggiore. Ad esempio, 32,861 > 32,8549, in quanto 6 > 5; e ancora, 22,63 > 22,6; in questo caso 22,6 e considerato come 22,60 e 3 è maggiore di 0. Le modalità per ottenere Q d a Q + sono analoghe a quelle per otte-nere Z da N (cfr. FIG. 2): (a) si crea una copia di Q + , indicata con Q~, i cui elementi sono detti numeri razionali negativi e sono con-trassegnati con il segno —; (b) si ordina Q~ in modo inverso rispetto a Q + ; (r) si allineano le due copie separandole con il numero 0.

I.3.2. La forma frazionaria I numeri razionali, oltre che in forma de-cimale (cioè come risultato di una divisione tra numeri interi) pos-sono essere rappresentati anche a divisione non avvenuta, indicando

semplicemente il dividendo e il divisore. Ad esempio il numero 1,27, risultato della divisione con virgola tra 14 e 11, può essere espresso dalla coppia ordinata (14, 11), scritta come 14/1 l o - | f . Tale forma si chiama frazionaria; la linea che separa i due numeri si chia-ma linea di frazione e indica appunto un'operazione di divisione; i vecchi dividendo e divisore prendono ora il nome di numeratore e denominatore. Se ci limitiamo a considerare coppie di numeri natu-rali, allora otteniamo i numeri razionali positivi; se invece, più in generale, consideriamo coppie di numeri interi, allora otteniamo tutti i numeri razionali. Il denominatore, cioè il secondo numero della coppia, deve comunque essere diverso da 0. Uno stesso numero razionale può essere rappresentato da infinite frazioni. Infatti, presa una qualunque frazione, se si moltiplicano numeratore e denominatore per uno stesso numero allora il risulta-to della divisione non cambia (a!b = kalkb). Due frazioni albe, dd, con a,b,c,d& Z, b ^ 0 e d ^ 0, rappresentano lo stesso numero ra-zionale quando axd = bxc. E consuetudine scegliere, come rappre-sentante di un numero razionale, la frazione ridotta ai minimi ter-mini, cioè quella in cui il numeratore e il denominatore non hanno divisori comuni e sono primi tra loro. In tal modo i numeri interi corrispondono a quei numeri frazionari che, ridotti ai minimi ter-mini, hanno il denominatore uguale ad 1.

1.3.3. Corrispondenza tra la forma frazionaria e quella decimale Dal momento che i numeri razionali possono essere rappresentati in due forme differenti, è necessario disporre di algoritmi per passare da una forma all'altra. Il passaggio dalla forma frazionaria a quella decimale si realizza semplicemente eseguendo la divisione tra nu-meratore e denominatore. Il passaggio inverso, dalla forma decima-le a quella frazionaria, si ottiene seguendo questa regola. Sia x un numero razionale espresso in forma decimale. Se x non è periodico allora il numero frazionario corrispondente ha come numeratore il numero x stesso privato della virgola e come denominatore 10", dove « è il numero di cifre di x dopo la virgola. Ad esempio, al nu-mero decimale x = 32,71 corrisponde il numero frazionario 3271/IO2 , cioè 3271/100. Se invece x è periodico allora il numero frazionario corrispondente ha come numeratore a - b, dove a è il

numero x senza la virgola e b è il numero x senza la virgola e senza le cifre del periodo, e come denominatore il numero costituito da tan-te cifre 9 quante sono le cifre del periodo di x seguite da tante cifre 0 quante sono le cifre dell'antiperiodo. Ad esempio, al numero x = 3,01(423) corrisponde il numero frazionario 301122/99900, dove 301122 è 301423 - 301.

1.3.4. Operazioni tra numeri razionali Nel paragrafo 1.3.1 abbiamo definito l 'ordinamento tra i numeri razionali riferendoci alla for-ma decimale; la corrispondente definizione in termini di frazioni (-j- < - j se ay.d < bxc) è meno intuitiva. Per definire le quattro operazioni è invece conveniente riferirsi direttamente alla forma frazionaria.

Addizione: "f" + "7 = "^Id' ("cordiamo che b e d devono essere diversi da 0; il simbolo • è equivalente al simbolo X, e spesso viene addirittura omesso) e • a c a-d — b-c

sottrazione: = —Yd—

Moltiplicazione: ~b ' =

Divisione: / -7 = (con c ^ 0).

Alcune osservazioni. • Essendo a,b,c,d numeri interi, le operazioni di somma, differen-za e prodotto che compaiono a destra dei segni di uguaglianza sono le vecchie operazioni tra interi. Così come in precedenza erano state impiegate le operazioni su N per definire le operazioni su Z, ora sono state impiegate le operazioni su Z per definire le operazioni su Q. • Nella definizione delle operazioni non viene fatto cenno a possibili semplificazioni. Pertanto è possibile che -j- e ~7 s ' a n o

dotti ai minimi termini e, ad esempio, " c non lo sia. Quello della semplificazione è infatti un problema a parte, dal momento che una frazione, anche se non ridotta ai minimi termini, identi-fica comunque un unico numero razionale; inoltre, nonostante che ciascun numero razionale possa essere espresso da infinite fra-zioni, il risultato delle operazioni non dipende dalla scelta effet-tuata.

• Le nuove operazioni di somma, sottrazione e prodotto (non la divisione), se applicate ai numeri interi, equivalgono alle vecchie operazioni. Infatti, i numeri interi corrispondono a frazioni che, semplificate, hanno denominatore 1. Pertanto, considerando frazio-ni ridotte ai minimi termini e ponendo b = 1 e d = 1 otteniamo, nell'espressione della somma, -y-+ T = ~T~' ^ m o s t r a la coinci-denza della nuova operazione con la vecchia. Lo stesso vale per le operazioni di sottrazione e prodotto. • La sottrazione coincide con la somma con l'opposto: -j- — =

(—j)- Per la divisione, si ha -j-l-j = H numero è det-to reciproco di (affinché esista, anche c, oltre a d, deve essere di-verso da 0) ed è l'unico numero razionale q tale che -^-q = 1. Tra-mite i concetti di opposto e reciproco, le operazioni di differenza e quoziente sono dunque, in Q, riconducibili a quelle di somma e prodotto. Il rapporto tra la funzione opposto e le operazioni di somma e prodotto è quello già visto nel caso dei numeri interi (cfr. PAR. 1.2.1). Per il quoziente abbiamo: (-d)lb = al(-b) = ~{alb). • È scomparsa la principale anomalia che, nei numeri naturali, distingueva la divisione dalle altre operazioni. Anch'essa ora dà come risultato un singolo numero (razionale) e non più una coppia di numeri. La vecchia divisione euclidea e la divisione con la virgola non sono dunque una l'estensione dell'altra (come è accaduto per addizione, sottrazione e moltiplicazione, in cui la nuova operazio-ne, se applicata ai vecchi numeri, coincideva con la vecchia opera-zione), ma sono due operazioni che differiscono anche quando sono applicate entrambe a numeri naturali (coincidono solo nel caso in cui il divisore sia un multiplo del dividendo). Sussiste ancora un vincolo che distingue la divisione dalle altre tre operazioni, ed è che il secondo elemento della coppia su cui si opera deve essere diverso da 0. Questa limitazione permarrà e non verrà superata dalle successive estensioni numeriche. Semmai, con il con-cetto matematico di limite, si potrà "analizzare" il comportamento della divisione quando il dividendo approssima lo 0; tuttavia, in questo caso non saremo più in aritmetica ma, appunto, in analisi. Per quanto riguarda l'eseguibilità delle quattro operazioni, l'insie-me Q d e i numeri razionali è dunque un punto di arrivo.

1.4- Incompletezza dell'insieme dei numeri razionali Ol-tre al compito di contare, i numeri assolvono anche la funzione di misurare. Classi numeriche come N o Z si prestano male a tale compito. Il loro ordinamento è caratterizzato dal fatto che, per ogni elemento x, esiste sempre un altro elemento y senza terzi ele-menti frapposti tra di essi (ad esempio, non vi è alcun intero tra - 3 e - 2 , oppure tra 3 e 4). I tipi d'ordine aventi tale caratteristica vengono definiti discreti e, per il loro procedere a salti, non sono certamente adatti alla misura. Questo inconveniente è superato dall'insieme Q d e i numeri razionali. Il suo tipo d'ordine non è di-screto ma denso, cioè per ogni x,y e Q tali che x < y esiste co-munque un elemento z e Q t a l e che x<z<y. Ad esempio, il nu-mero z = (x+y)/2 appartiene anch'esso a Q e d è compreso tra x e y (anzi, ne costituisce il punto medio). Ripetendo questa opera-zione tra x e z e tra z e y, e proseguendo ancora con gli elementi via via trovati, si ottiene una quantità arbitrariamente grande di numeri compresi tra x e y. Quindi, due numeri razionali distinti, per quanto vicini, contengono sempre tra loro infiniti altri nume-ri razionali (da qui l'impiego del termine "densità"). Tramite i numeri razionali si possono dunque ottenere misure quanto si vo-glia ben approssimate. Ma è anche possibile ottenere, in ogni caso, misure esatteì

E bene rimarcare che questo è un problema puramente teorico. Con i numeri razionali è possibile scendere al di sotto di ogni mar-gine d'errore, per quanto piccolo sia tale margine, e ciò è più di quanto serva nella pratica effettiva della misura. Tuttavia, da un punto di vista teorico, la domanda precedente è ben posta, e lo fu per i pitagorici, i quali attribuivano alla matematica un ruolo ben più alto che non quello di essere una collezione di strumenti pratici. E la risposta che essi trovarono fu, sorprendentemente, negativa. Vediamo come ciò avvenne.

1.4.1. Corrispondenza tra numeri razionali e punti Ai numeri razionali possono essere fatti corrispondere punti di una retta seguendo que-sta (ben nota) procedura.

I numeri 0 e 1 vengono fatti corrispondere a due distinti punti O e U della retta, scelti in modo arbitrario (anche se, per convenzione, si prende U alla destra di O). Il segmento OU viene detto segmento unitario o unità di misura-, la semiretta avente origine in O e conte-nente U è la semiretta positiva, mentre quella avente origine in O e non contenente Uè la semiretta negativa (cfir. FI6. 5). Dati due nu-meri naturali ae.b (con b & 0), al numero razionale positivo a/bvie-ne fatto corrispondere quel punto P della semiretta positiva che si individua dividendo dapprima OU in b parti uguali e poi, partendo da O, allineando un numero a di tali parti sulla semiretta positiva. II numero a/b esprime la misura (o lunghezza) del segmento OP avendo OU come unità di misura. La figura 5 mostra il punto P corrispondente al numero razionale 5/3. Si vede bene qui la ragione dei nomi "denominatore" e "numeratore": il 3 dà il nome alla par-te, "terzo", mentre il 5 esprime il numero di tali parti. Nel caso di un numero razionale negativo ~{alb), con a,b e N, si procede in modo analogo ma nel verso opposto. In tal modo, i punti corri-spondenti ai numeri a/b e —(a/b) sono simmetrici rispetto ad O.

FIGURA 5

Dal numero 5/3 al punto P

(1) (2) ( 3 ) ( 4 ) ( 5 )

0 1 5 / 3

semiretta negativa 0 U P semiretta positiva (1) (2) ( 3 )

1.4.2. Misure non razionali La procedura appena descritta associa ad ogni numero razionale un punto della retta e, naturalmente, lo fa in modo che a numeri distinti corrispondano punti distinti. Nasce una domanda: ogni punto della retta è il corrispondente di un nu-mero razionale, oppure esistono punti che non sono stati toccati dalla corrispondenza? Ora, l'insieme dei punti della retta è denso (tra due punti esistono infiniti punti); ma anche l'insieme dei nu-meri razionali è denso. È quindi ragionevole pensare di rispondere

positivamente alla domanda, cioè ipotizzare che, nel porre in corri-spondenza i numeri razionali con i punti nel modo appena descrit-to, nessun punto resti escluso. Tuttavia ciò è falso. Possiamo infatti dimostrare che il punto 5 tale che il segmento OS ha lunghezza pari alla diagonale del quadrato costruito sul segmento unitario OUnon è il corrispondente di alcun numero razionale (cfr. FIG. 6). Per il teorema di Pitagora, la misura di 0 5 è V l 2 + l 2 = V2. Dimostria-mo allora che V2 non è un numero razionale. La dimostrazione, an-ch'essa di scuola pitagorica, è per assurdo, il che significa che prende avvio dalla negazione di ciò che si vuole dimostrare e si conclude non appena si perviene ad una contraddizione. Supponiamo quindi che sia falso il fatto che V2 non è razionale, e dunque supponiamo che lo sia, cioè che esistano due numeri naturali a,b tali che V2 = a!b. Sia min = alb con m e n primi tra loro, cioè privi di divisori comuni. Scriviamo l'identità V2 = min nella forma 2n2 = m2. Il numero 2n2 , contenendo il fattore 2, è pari. Dunque anche m2 è pari, e dunque lo è anche m (infatti, il quadrato di un numero di-spari è dispari). È quindi possibile porre m = 2s, dove s è ancora un numero naturale, da cui, sostituendo nell'identità 2n2 = m2, si ri-cava 2n2 = As2 e «2 = Is2. Ripetendo le considerazioni precedenti, abbiamo che Is2 è pari, dunque lo è n2, dunque lo è n. Ma ciò è as-surdo in quanto semen sono entrambi pari allora hanno in comu-ne il fattore 2 e non possono essere primi tra loro, come invece si era supposto. Pertanto V2 non è razionale e il punto S non è il cor-rispondente di alcun elemento di Q.

L'esistenza di un punto con tali caratteristiche non rappresenta un fatto raro. Georg Cantor (1845-1918) ha dimostrato che l'insieme

FIGURA 6

Incompletezza di Q

dei punti della retta che non corrispondono ad alcun numero razio-nale è più grande, in un senso che preciseremo nel paragrafo 2.8, dell'insieme dei punti che vi corrispondono. La densità, che Q pos-siede, non è dunque sufficiente a garantirgli la capacità di etichettare tutti i punti della retta. Per avere un numero in corrispondenza di ogni punto, e dunque per potere misurare esattamente ogni seg-mento, è necessaria una proprietà più forte, che viene chiamata completezza. Q non la possiede, e questo ci impone di passare ad un insieme numerico più ricco: l'insieme R dei numeri reali.

1.5. Dai numeri razionali ai numeri reali Sia i numeri interi sia i numeri razionali sono stati introdotti in termini aritmetici par-tendo dai numeri naturali (i primi come numeri naturali dotati di un verso, i secondi come rapporto di due numeri interi). Anche i numeri reali possono essere definiti a partire dalla classe dei numeri naturali (questo processo prende il nome di aritmetizzazione dell'a-nalisi e verrà descritto nel paragrafo 4.1), ma ciò non è né immedia-to né intuitivo. In effetti, l'immagine intuitiva su cui basarsi per operare con i numeri reali non è in termini aritmetici, ma geome-trici; e se nella costruzione precedente (cfr. FIG. 5) si è partiti dai nu-meri razionali per individuare determinati punti della retta, ora è a partire dai punti della retta che vengono individuati i numeri reali. Il capovolgimento di prospettiva è completo. Dato un qualunque punto P della semiretta positiva di r su cui è stato fissato il segmen-to unitario OU, si assume che esista comunque un numero espri-mente il rapporto tra OP e OU (esprimente cioè la misura di OP, con OU come unità di misura). Se i segmenti OP e OU sono com-mensurabili, cioè se esiste un segmento s contenuto in entrambi un numero esatto di volte, allora a P corrisponde un numero razionale (più precisamente: se s è contenuto b volte in OU e a volte in OP, allora il numero razionale è atb-, cfr. FIG. 5 relativamente al caso alb = 5/3). Se invece OP e OU sono incommensurabili, cioè se non esi-ste un tale segmento (come nel caso del lato e della diagonale di un quadrato), si impone comunque che a P corrisponda ancora un nu-mero, che sarà definito irrazionale. Come in precedenza, se il punto P appartiene alla semiretta negativa, il numero corrispondente a P

sarà l'opposto del numero corrispondente al punto P' simmetrico di P rispetto ad O. L'insieme R dei numeri reali si ottiene dall'unione dell'insieme dei numeri razionali con quello dei numeri irrazionali:

reali = razionali + irrazionali

I numeri reali sono dunque, proprio per come sono stati definiti, in corrispondenza biunivoca con i punti della retta. Questo fatto è or-mai così radicato nella pratica matematica che le espressioni "nu-mero reale" e "punto di R" sono trattate come equivalenti, e lo stesso accade per le espressioni "insieme dei reali" e "retta reale". Naturalmente, in virtù di questa corrispondenza, i numeri reali co-stituiscono il punto di arrivo per quando riguarda il problema della misura; il passaggio all'insieme dei numeri complessi, con l'inser-zione dei numeri immaginari, risponderà ad esigenze di tipo alge-brico e non mensúrale.

1.5.1. Come denotare i numeri irrazionali I numeri interi e i numeri razionali sono stati costruiti a partire dai numeri naturali per cui, in fase di denotazione, è stato possibile impiegare la notazione dei nu-meri naturali, limitandosi ad anteporre o frapporre dei segni ag-giuntivi ( -5 , 7/3 ...). Inoltre, poiché ciascun numero naturale ha un suo proprio nome e una scrittura simbolica che lo denota indivi-dualmente, anche ciascun numero intero e ciascun numero razio-nale hanno ottenuto un loro proprio nome e una scrittura che li de-nota altrettanto individualmente. Per ottenere i numeri reali nella loro generalità siamo invece partiti dai punti di una retta, i quali non hanno un nome per ciascuno. Lo stesso accade dunque a tali numeri. Anzi, è possibile dimostrare che non può esistere, neppure in linea teorica, un algoritmo per deno-minare individualmente tutti i numeri irrazionali. Alcuni di essi (ad esempio V2 o (1 + V5)/2) sono denotati dall'espressione dalla quale scaturiscono; altri possono essere caratterizzati in modo puramente geometrico e ricevono dei nomi ad hoc (ad esempio n per denotare il rapporto tra una circonferenza e un suo diametro). Ma "la mag-gior parte" dei numeri irrazionali sono e rimarranno senza nome.

1.5.2. Operazioni tra numeri reali Come abbiamo detto, in un nu-mero irrazionale la successione delle cifre dopo la virgola è infinita e non periodica: la conoscenza completa di un numero irrazionale è dunque impossibile. Come si può allora operare con esso? Un dato rilevante è costituito dal fatto che l'insieme Q dei numeri razionali è denso rispetto all'insieme R dei numeri reali: data una qualunque coppia di numeri reali (razionali o irrazionali) esistono infiniti nu-meri razionali compresi tra di essi. Pertanto ogni numero irraziona-le può essere approssimato a piacere, sia per difetto sia per eccesso, da numeri razionali. Ad esempio:

1 < 1,4 < 1,41 < 1,414< ... < V 2 < ... 1,415 < 1,42 < 1,5 < 2 3 < 3,1 < 3,14 < 3,141 < ... < ti < ... 3,142 < 3,15 < 3,2 < 4

Anche i calcoli avvengono per approssimazione, identificando un numero irrazionale con un numero razionale che lo approssima in modo opportuno (ad esempio, in situazioni elementari 7t sarà iden-tificato con 3,14, mentre per ottenere risultati più precisi verranno impiegate molte più cifre decimali). Un ausilio viene dal calcolo letterale. Si può indicare il numero irrazionale con una lettera e operare algebricamente su di esso (ad esempio (n + 7t)2/rc = 47i), rimandando la conversione numerica a calcoli avvenuti, in modo da evitare che gli errori si accumulino. In ogni caso, comunque, tutto alla fine si riconduce ai numeri razionali. Tuttavia, dato il modo geometrico con cui sono stati individuati i numeri reali, è possibile definire geometricamente anche le opera-zioni. E poiché l'insieme dei numeri reali include tutti gli insiemi numerici fin qui incontrati ( N c Z c Q c R), tali definizioni si estendono anche ad essi.

1.5.3. Definizione geometrica delle operazioni

• Somma. Il modo più immediato per ottenere geometricamente la somma tra i numeri reali xP e Xq corrispondenti ai punti P e Q consiste nell'allineare i segmenti OP e OQ portando, con un movi-mento rigido del segmento OQ, il punto O in P. L'estremo destro

di questo nuovo segmento indica la somma (cfr. FIG. 7A). Un modo più "euclideo" di procedere, che fa a meno di movimenti rigidi, è rappresentato in figura 7B. La fasi della costruzione sono le seguen-ti, e valgono qualunque sia la disposizione di P e Q rispetto ad O. (1) Si traccia una qualunque retta s incidente r in O, e su di essa vie-ne individuato un qualunque puntovi diverso da O. (2) Si traccia la retta t passante per i punti A e Q. (3) Si traccia la retta u passante pei A e parallela ad r. (4) Si traccia la retta v passante per P e paral-lela ad s, indicando con B l'intersezione tra v e u. (5) Si traccia la retta w passante per B e parallela a t, indicando con Z l'intersezione tra wcr.l triangoli OAQe PBZsono congruenti, e PZè congruen-te ad OQ. Pertanto il numero reale x z corrispondente a Z è la som-ma dei numeri reali xP e XQ, corrispondenti a P e Q. • Prodotto. Siano ancora O, U, P e Q punti di r, e siano xP e Xq i numeri reali corrispondenti a P e Q. La fasi della costruzione per ottenere il punto Z tale che = xP • Xq sono rappresentate in figu-ra 8. (1) Viene tracciata una qualunque retta s incidente r in O, e su di essa viene individuato un qualunque punto A diverso da O. (2) Si congiunge U ad A. (3) Si traccia la retta t passante per P e paralle-la al segmento UA, indicando con B l'intersezione tra t e s. (4) Si congiunge Q con A. (5) Si traccia la retta w passante per B e paralle-

FIGURA 7

Due modi geometrici di rappresentare la somma di OPe OQ

(A)

(B)

« (D

(A) mediante movimento rigido e (B) mediante costruzione di triangoli congruenti.

la al segmento QA. L'intersezione tra w e r è il punto Z cercato, in quanto il reale che gli corrisponde è il prodotto tra quelli corrispon-denti a P e Q. Infatti i triangoli OA U e OBP sono simili, e cosi pure i triangoli OAQe OBZ. Da OP : OU = OB : OA = OZ -.OQ segue Xp-.Xjj = xz : Xq e quindi xP • Xq = xv- xz (il prodotto dei medi è uguale al prodotto degli estremi). Ma, essendo x v = 1 (ricordiamo che OUb il segmento unitario), otteniamo xP • Xq = xz. • Opposto e reciproco. Il passaggio all'opposto (da xP a —xP) si ot-tiene semplicemente per simmetria (FIG. 9A). Il passaggio al recipro-co, per P * 0, si ottiene con la procedura rappresentata in figura 9B. (1) Viene tracciata una qualunque retta s incidente r in 0 e su di essa viene individuato un qualunque punto A diverso da 0. (2)

FIGURA 9

Rappresentazione geometrica dell'opposto (A) e del reciproco (B)

Si congiunge P ad A. (3) Si traccia la retta passante per Ue parallela al segmento AP, indicando con B l'intersezione con s. (4) Si traccia la retta passante per B e parallela zàAU, indicando con P' l'interse-zione con r. Il reale corrispondente a P'è il reciproco di quello cor-rispondente a P. Infatti, applicando la procedura del prodotto a P e /•'perveniamo ad U, e quindi xP • xP' = l e xP• = MxP. A questo punto, disponendo delle procedure per somma, prodotto, opposto e reciproco, siamo in grado di ottenere quelle per la diffe-renza e il quoziente, ponendo x —y = x + (-y) e x/y = x • \/y.

1.5.4. Una differenza tra somma e prodotto Se confrontiamo la figu-ra 7 relativa alla somma con la figura 8 relativa al prodotto, notia-mo che solo nella seconda è intervenuto il punto U che denota il segmento unitario OU. Naturalmente, anche nel caso della som-ma lo stesso punto P, con due diverse unità di misura, rappresenta due numeri diversi, e lo stesso accade per Q. Ma, qualunque sia l'unità di misura adottata, viene comunque individuato lo stesso punto Z. Nel caso del prodotto, invece, se si lasciano invariati i punti P e Q e si cambia il punto U, anche il risultante punto Z cambia. Ciò significa che, mentre la procedura per la somma (e per l'opposto) è invariante rispetto all'unità di misura impiegata, quella per il prodotto (e per il reciproco) non lo è. Questo fatto indica che la descrizione in termini geometrici del prodotto, con-trariamente a quella della somma, non è "naturale". Del resto, mentre la somma di due segmenti è interpretabile in modo natu-rale come un segmento, non altrettanto accade per il prodotto. Ad esempio, nel prodotto 3 - 5 = 15 possiamo interpretare uno dei due fattori, ad esempio 3, come esprimente la misura di un segmento; ma se vogliamo interpretare anche il risultato 15 come misura di un segmento, allora il secondo fattore 5 esprimerà sem-plicemente un contatore: ci dice che il segmento di lunghezza 3 è stato sommato a se stesso 5 volte. Questo prodotto avviene dun-que tra due grandezze disomogenee. Se invece vogliamo interpre-tare anche il numero 5 come una lunghezza, allora è naturale in-tendere il numero 15 come espressione di una superfìcie, quella

del rettangolo "3 per 5". Non vi è dunque, nel prodotto 3 - 5 = 15, un modo intuitivo di interpretare tutti i tre numeri come lunghez-ze. Quella di avere associato i numeri a punti (interpretandoli come misure di segmenti) e avere poi trattato in modo uniforme la somma e il prodotto è stata infatti un'impresa che ha richiesto un notevole grado di astrazione. I Greci non la compirono mai (per loro il prodotto di due numeri esprimeva un'area, quello di tre un volume) e, per vederla realizzata, fu necessario attendere la prima metà del x v n secolo, il tempo di Cartesio e di Fermai.

1.5.5. Classi numeriche e infinito Nel paragrafo 2.8, alla luce della teoria cantoriana, il tipo di infinità delle varie classi numeriche ver-rà analizzato da un punto di vista quantitativo. A conclusione di questo capitolo vogliamo invece rilevare alcuni semplici dati quali-tativi. Incominciando dall'insieme N dei numeri naturali, si può senza dubbio asserire che esso è uno degli esempi intorno a cui si è venuto a formare il concetto stesso di infinito; ne rappresenta infat-ti la versione matematica, così come il tempo e lo spazio ne rappre-sentano la versione fisica. La sua infinità deriva dall'assenza di un ultimo, un più grande, numero naturale; il concetto di infinito è qui legato dunque a quelli di lontananza e di illimitatezza. Per con-tro, N è dotato di un primo elemento (il numero 1, o il numero 0 nel caso di N 0 ) e possiede un tipo d'ordine ben fondato: ogni cam-mino a ritroso ha termine. Questa proprietà si perde passando da N a Z, poiché in Z anche i processi a ritroso possono protrarsi all'infi-nito. Non si tratta comunque di un cambiamento particolarmente rilevante: è come avere due serie di numeri naturali che vanno in verso opposto.

Il cambiamento qualitativamente più avvertibile si ha nel pas-saggio da Z a Q. Se per i numeri interi l'idea di infinità coinci-de con quella di infinitamente lontano e di infinitamente gran-de, nel caso dei numeri razionali intervengono, grazie alla densi-tà, anche i concetti di infinitamente vicino e infinitamente pic-colo. Ai numeri da telescopio si aggiungono così i numeri da microscopio.

L'ulteriore passaggio dall'insieme dei numeri razionali a quello dei numeri reali sembra essere, ad un'analisi superficiale, meno si-gnificativo: ci si limita ad aggiungere dei punti mancanti, i quali però sono avvicinabili a piacere mediante i numeri razionali. Vi è tuttavia un importante elemento di novità. Passando da Q ad R l'infinità diventa una caratteristica individuale oltre che collettiva. In Q e negli insiemi numerici che lo precedono, ad essere infiniti sono gli insiemi. I singoli elementi, cioè i numeri individualmente considerati, non coinvolgono l'infinito. Certo, le cifre decimali di un numero razionale periodico procedono indefinitamente, ma si tratta di un ciclo perfettamente descrivibile in termini finiti senza alcuna perdita di informazioni (basta una semplice sbarretta sopra una sequenza finita di cifre). Nel caso dei numeri irrazionali, in-vece, l'infinità riguarda anche i singoli numeri, dal momento che le infinite cifre decimali di un numero irrazionale possono non se-guire alcuna regolarità, con l'ovvia conseguenza che qualunque descrizione finita risulta incompleta. Cantor dimostrerà (cfr. PAR. 2.8.4) che, per quanto riguarda le conseguenze sulla grandezza complessiva dell'insieme, questo è, tra tutti quelli incontrati, il fatto più rilevante.

1.6. Un modello riassuntivo Qui di seguito proponiamo una rappresentazione dell'insieme R dei numeri reali che permette di ben evidenziare, al suo interno, le classi numeriche N, Z e Q. Pren-diamo un piano infinito suddiviso in quadretti di lato 1. Prendia-mo poi come assi cartesiani due tra le rette che formano la quadret-tatura. Dal fatto che i quadretti hanno i lati di misura 1 segue che i nodi della quadrettatura (con il termine "nodo" intendiamo i punti di intersezione delle rette che formano la quadrettatura) corrispon-dono ai punti del piano a coordinate intere (cfr. FI6. 10A). Conside-riamo infine il fascio di rette F, passante per l'origine e privato della retta verticale (cioè dell'asse Y). A questo punto possiamo stabilire una corrispondenza biunivoca da R ad F associando ad ogni nu-mero reale ria retta di Spassante per il punto (l,r) (si osservi come, in tal modo, la retta verticale x = 1 assuma un ruolo di rilievo). Tale valore r è ciò che viene chiamato coefficiente angolare della retta. Valgono i seguenti fatti:

FIGURA 10

Rappresentazione dei numeri reali mediante un fascio di rette

Y *„»

yi (A)

U 7

K

1/2) <D(p/<?)

' 4>(-l) (B)

(1) Un numero r è razionale se e solo se la corrispondente retta O(r) incontra almeno un nodo della quadrettatura oltre all'origine (0,0). Infatti, supponiamo dapprima r e Q, cioè r = plq conp,q e Z. Poi-ché plq : 1 = p : q, i punti (0,0), (l,p/q) e (q,p) sono allineati (cfr. FIG. 10B). Pertanto Q>(r), che per definizione passa per i punti (0,0) e (1, plq), passa anche per il punto (q,p), il quale, avendo coordinate intere, è un nodo della quadrettatura. Viceversa, se una retta di F passa per un nodo oltre a (0,0), diciamo (q,p), allora, essendo i punti (0,0), (1, plq) e (q,p) allineati, passa anche per il punto (1, plq), e quindi tale retta è <&{plq), corrisponde cioè ad un numero razionale. La (ì) può essere enunciata in questa forma equivalente: r è irrazio-nale se e solo se la retta O(r) non passa per alcun nodo oltre (0,0). Dunque, l'esistenza dei numeri irrazionali coincide, in questo mo-dello, con l'esistenza di rette di F che hanno tale caratteristica. (Data l'intuitività del modello, questa è una domanda facile da por-re: "Dato un foglio infinito quadrettato e un fascio di rette aventi per centro un nodo qualunque, esistono delle rette che non incon-trano nessun altro nodo?" Chi risponde positivamente crede negli irrazionali.)

(2) Se una retta del fascio corrisponde al numero razionaleplq allo-ra non solo passa per il nodo (q,p), ma anche per gli infiniti nodi della forma {kq, kp), con ke Z, che corrispondono a tutte le forme frazionarie il cui il numero p/q può essere espresso. Se, poi, la fra-zione p/q è ridotta a fattori primi, allora la retta corrispondente non incontra alcun nodo tra (0,0) e (q,p), e viceversa. (3) Se r non solo è un numero razionale ma è addirittura un nume-ro intero, allora non solo 3>(r) passa per infiniti nodi ma addirittura incontra in un nodo ogni retta verticale formante la quadrettatura. Infatti, per definizione di O, la retta O(r) passa per (l,r) che, essen-do re. Z, è già un nodo, e quindi per i nodi (2, 2r), (3, òr) e così via. Invece, i numeri le cui rette corrispondenti incontrano in un nodo ogni retta orizzontale formante la quadrettatura sono i reciproci dei numeri interi, cioè i numeri della forma l/k (con k numero intero non nullo). (4) Dal punto (3) segue che i numeri 1 e - 1 , essendo gli unici nu-meri reali che coincidono con il loro reciproco, sono anche gli unici le cui rette corrispondenti incontrano in un nodo ogni retta vertica-le e ogni retta orizzontale.

2. Teoria degli insiemi

2.1. Infinito attuale e infinito potenziale Quando usiamo l'e-spressione "l'insieme dei numeri naturali è infinito", probabilmente stiamo considerando tale insieme come un oggetto matematico in atto. Tuttavia, fino a non molto tempo fa, non è stato questo il modo più comune di esprimersi. Sui testi di matematica non recenti la pa-rola "insieme", come sostantivo, non compariva (e tuttora non com-pare nel linguaggio comune, dove è impiegata solo come avverbio). Per esprimere l'infinità dei numeri naturali si usava, e ancora si può usare, l'espressione "i numeri naturali sono infiniti", la quale però può essere intesa in due sensi: sia come l'asserzione dell'infinità del-l'insieme dei numeri naturali (e quindi in modo analogo alla prece-dente) sia, in senso più debole, come l'asserzione che ogni elenco fi-nito di numeri naturali può essere comunque ampliato. Vi sono così due modi di intendere l'infinito: uno attuale, quando si attribuisce l'infinità ad un insieme considerato non in fieri ma, appunto, in atto; e uno potenziale, quando ci si riferisce alla possibi-lità di crescita illimitata di quantità comunque finite. Naturalmen-te, solo con l'infinito attuale si ha a che fare con una infinità in sen-so proprio.

Nel corso del primo capitolo, solo in un punto l'infinito ha dovuto necessariamente comparire in forma attuale. Non è stato riguardo ai numeri naturali né a quelli interi né a quelli razionali. Come ab-biamo detto, questi tipi di numero, se considerati individualmente e in modo intuitivo, non coinvolgono il concetto di infinito; ad es-sere infiniti sono gli insiemi (dei numeri naturali, dei numeri interi, dei numeri razionali), ma in nessuna occasione abbiamo avuto il bi-sogno di considerare questi insiemi come oggetti compiuti, in atto. La scelta tra attuale e potenziale è stata dunque ad arbitrio del letto-re. Abbiamo invece considerato come oggetti in atto i singoli nu-meri irrazionali e, come osservato, ciascuno di essi richiede, per es-sere espresso compiutamente, un insieme infinito di cifre; se lo si approssima impiegandone una quantità finita, si passa ad un nume-ro razionale e dunque si cambia oggetto.

Del fatto che ciascun numero irrazionale comporti un uso attuale dell'infinito dovettero rendersi ben conto i Greci. La scoperta delle grandezze irrazionali fu la principale causa di crisi della filosofia pi-tagorica, e da allora tutto il pensiero antico ha manifestato una co-stante avversione per l'infinito attuale. La parola greca per definirlo era apeiron, un termine negativo che denota, oltre all'infinita gran-dezza, pure il disordine, il caos, l'indeterminatezza, l'impossibilità di conoscenza. Anche il più famoso dei paradossi di Zenone aveva alla base un problema di infinito attuale: Achille (A) rincorre una tartaruga (T) che dista un metro da lui, e corre con velocità doppia. Quando A avrà percorso un metro, T si sarà allontanata di mezzo metro; quando A avrà coperto tale ulteriore tratto, T sarà ad un quarto di metro di distanza e così via. Zenone concluse, in pieno contrasto con l'evidenza, che A non avrebbe mai raggiunto T, poi-ché per farlo avrebbe dovuto percorrere una infinità (compiuta, quindi in atto) di segmenti non nulli: 1 + V2+ '/4 +... . La natura dei due eventi che abbiamo riferito è ben diversa. La sco-perta delle grandezze incommensurabili, e quindi dei numeri irra-zionali, è stata una fondamentale acquisizione della matematica, anche se dolorosa per gli autori; il paradosso di Zenone nacque in-vece da un pur geniale errore (il ritenere che la somma di una infi-nità di grandezze non nulle sia sempre infinita), dal cui superamen-to ebbe origine, oltre due millenni dopo, il calcolo infinitesimale. Ma ciò che i due eventi ebbero in comune fu il fatto di acuire l'av-versione del pensiero greco verso l'infinito. La sua estromissione si-stematica dall'universo scientifico avvenne soprattutto ad opera di Aristotele, che ideò quella forma di surrogato che è l'infinito poten-ziale. Euclide, intorno al 300 a.C., fece sua questa impostazione po-nendo, al principio dell'opera che per i due millenni successivi sa-rebbe stata il paradigma del pensiero matematico, questo assioma: Il tutto è maggiore della parte (Elementi, Libro 1, Nozione comune vili).

Basta guardare la figura 11 per comprendere che ciò può essere falsi-ficato dagli oggetti (attualmente) infiniti: la semiretta con origine in B è parte di quella con origine in A, ma non ne è minore. L'assioma euclideo, all'apparenza così innocuo, ha quindi il preciso scopo di estromettere l'infinito attuale dalla matematica. In effetti,

per Euclide le rette sono segmenti finiti prolungabili illimitatamen-te (Elementi, Libro i, Postulato n: Una retta terminata è prolungabi-le continuamente in linea retta), e anche gli insiemi numerici dell'a-ritmetica sono trattati con analoga cautela. Il famoso teorema sul-l'infinità dei numeri primi (Elementi, Libro ix, Proposizione 20) è enunciato con parole che, più che mai, mostrano il trionfo dell'infi-nito potenziale: Esistono numeri primi in numero maggiore di quanti numeri primi si voglia proporre. Questa avversione non è terminata con i Greci. Anche il concetto di limite, su cui si fonda la moderna analisi matematica, è la rispo-sta in termini di infinito potenziale alle difficoltà che l'infinito at-tuale aveva creato a Zenone. In scritture quali

1 1 lim — = 0 e lim —- = + °°

x —» + 00 % x —>0 x

il simbolo <», che si legge "infinito", non indica una grandezza ma un punto lontano verso cui tendono, rimanendo sempre al finito, la variabile x nel primo caso e il valore llx2 nel secondo. Alcuni autori ottocenteschi tentarono un recupero dell'infinito at-tuale. Ma affinché tale recupero non si riducesse ad una semplice presa di posizione filosofica ma fosse in grado di produrre un cam-biamento matematicamente rilevante è stato necessario che pren-desse forma il concetto di insieme, e ciò avvenne soprattutto con l'opera di Richard Dedekind (1831-1916) e di Georg Cantor (1845-1918). Il concetto di insieme è dunque entrato in matematica per preparare il posto a quello di infinito. Ciò non significa che la teoria degli insiemi consideri soltanto insie-mi infiniti: essa tratta indifferentemente insiemi infiniti e finiti. Il

FIGURA 11

"Il tutto è maggiore della parte"?

A r B

fatto è che il concetto di insieme si pone ad un livello molto più ge-nerale rispetto a quelli usualmente trattati dalla matematica (nume-ri, enti geometrici ecc.). Costruire tutta una teoria intorno a oggetti indeterminati come gli insiemi (forse solo il temibile concetto di ente vanta una maggiore generalità) ha davvero senso soltanto se ciò rende possibile l'ingresso in matematica degli insiemi infiniti (e, ri-petiamo, essendo ogni insieme considerato come un oggetto com-piuto e non in fieri, la sua eventuale infinità è da considerarsi in atto e non in potenza). Questo ingresso ha determinato a sua volta lo sviluppo di nuove discipline quali ad esempio l'algebra astratta, che si occupa di insiemi per lo più infiniti dotati di operazioni (le strut-ture algebriche, cfr. CAP. 3). Ma ha avuto anche un ulteriore effetto: quello di dotare tutta la matematica di un linguaggio comune.

2.1.1. Il linguaggio della matematica Vi è un buon numero di parole che possono essere considerate specifiche della matematica. Le più comuni sono quelle di numero, punto, retta, e quelle delle figure geometriche: triangolo, quadrato e così via. Altrettanto presenti sono parole quali operazione, relazione, funzione, e quelle più speci-fiche di addizione, parallelismo, logaritmo ecc. Vi è però una netta differenza, da un punto di vista intuitivo, tra le parole del primo gruppo e quelle del secondo. Le prime sono intese come denotanti degli oggetti (gli enti matematici, appunto); non altrettanto le se-conde, dal momento che non si pensa ad una relazione come ad un oggetto ma come a qualcosa di indefinito che lega gli oggetti. Que-sta disomogeneità può ostacolare il raggiungimento di un assetto ri-goroso della matematica. Infatti, non solo vi è la necessità, ben nota già dal tempo dei Greci, di ricondurre gli enunciati matematici ad un ristretto numero di essi (gli assiomi o postulati), che servano come punto di partenza per produrre dimostrazioni-, vi è anche la necessità, altrettanto forte, di ricondurre i concetti matematici ad un ristretto numero di essi (i concetti primitivi), che servano come punto di partenza per produrre definizioni. Così come gli enuncia-ti, anche i concetti devono dunque poter essere trattati in modo uniforme. La teoria degli insiemi è stata lo strumento che ha per-messo la piena realizzazione di questo processo. Al suo interno tutti i concetti matematici - non solo quelli che da un punto di vista in-

tuitivo esprimono oggetti, ma anche quelli che sembrano su un al-tro piano — vengono tutti ricavati da due soli concetti primitivi: quello di insieme (ovviamente) e quello di appartenenza. Il successo della teoria degli insiemi come base fondante e come linguaggio per la matematica sta proprio qui: nella possibilità di definire al suo in-terno i concetti di relazione, funzione e operazione. Inoltre, a ripro-va della forza normalizzante della teoria, questi tre concetti si con-catenano, nel senso che le operazioni diventano particolari funzio-ni, e le funzioni particolari relazioni. A ciascuno di essi dedichere-mo un paragrafo specifico, subito dopo aver introdotto il simboli-smo e i rudimenti generali della teoria.

2.2. Primi elementi della teoria degli insiemi Come antici-pato, tutto prende l'avvio dai concetti di insieme e di appartenenza. L'espressione x e A si legge "x appartiene ad A" oppure "x è ele-mento dell'insieme A" (l'impiego di una lettera minuscola per l'ele-mento e di una lettera maiuscola per l'insieme non è vincolante, né potrebbe esserlo dal momento che, in un medesimo contesto, uno stesso ente può essere sia un insieme di elementi sia un elemento di un insieme). Un generico insieme può essere denotato in modo esplicito, elen-cando i suoi elementi (e ciò, naturalmente, può essere fatto solo per insiemi finiti e "piccoli"), oppure in modo implicito, facendo riferi-mento ad una proprietà P che ne caratterizza gli elementi. Nel pri-mo caso si scrive, ad esempio, A = {a,b,c,d\ per indicare che l'insie-me A è composto dagli elementi a,b,c e d. Nel secondo caso si scrive A = {x : POc:)} per indicare che l'insieme A è composto da tutti e soli quegli elementi che soddisfano la proprietà P. Ad esempio, la scrit-tura {x : x e N e x > 3} denota l'insieme dei numeri naturali mag-giori di 3. La corrispondenza che si stabilisce tra una proprietà P e l'insieme {x : /"(x)} degli elementi che la soddisfano prende il nome di Principio di comprensione. L'ordine con cui gli elementi di un in-sieme vengono elencati è irrilevante. Pertanto due insiemi sono uguali se, e soltanto se, hanno gli stessi elementi (ad esempio, {a, b, c\ = {b, a, c}). Particolare importanza ai fini della teoria riveste l'in-sieme vuoto, cioè l'insieme privo di elementi, che si indica con 0 e

che ha tra gli insiemi un ruolo analogo a quello che ha lo 0 tra i nu-meri. In effetti, 0 è l'unico insieme la cui cardinalità sia 0. Dati due insiemi A e B, diciamo che B è sottoinsieme di A, oppure che B è incluso in A, se ogni elemento di B è anche elemento di A. La scrittura simbolica è B c A, e la relazione c viene detta relazione di inclusione. Si noti come dalla definizione segua che, per ogni in-sieme/1, valgono sia 0 c A che A c A. Se si vuole esprimere il fatto che B qA e B ? A allora si scrive B c A, e si dice che B è incluso strettamente in A. Una precisazione banale che tuttavia può evitare fraintendimenti a chi affronta questi temi per la prima volta è questa: il rapporto che sussiste tra insieme e sottoinsieme non è analogo a quello che sussi-ste tra scala e sottoscala, o tra tenente e sottotenente. Un sottote-nente non è un tenente, un sottoscala non è una scala, ma un sot-toinsieme è, a tutti gli effetti, un insieme. Dato un insieme A, l'insieme di tutti i suoi sottoinsiemi viene de-notato con P(A) e chiamato insieme delle parti di A. In simboli,

P(A) = {B:BqA}.

Ad esempio, se A = {3,7,8} allora P{A) = {0 , {3}, {7}, {8}, (3,7}, {3, 8}, {7, 8}, {3, 7, 8}}. Da questo esempio emerge chiaramente il fatto che essere un elemento o essere un insieme non sono proprietà as-solute di un ente; infatti P{A) ha come suoi elementi i sottoinsiemi dell'insieme A. Si noti inoltre la presenza di sottoinsiemi di un solo elemento, detti singoletti-, il loro inserimento nella categoria degli insiemi è del tutto coerente ma, come già per il vuoto, è un po' in conflitto con il senso comune. Vale il seguente risultato:

P R O P O S I Z I O N E 2.1. Se Card(A) = n allora Card{P{A)) = 2" (a paro-le: un insieme di n elementi ha 2" sottoinsiemi).

2.2.1. Operazioni booleane: intersezione, unione, complemento Dati due insiemi A e B, definiamo le seguenti operazioni: • intersezione: Ac\B = {x : x e A e x e B} • unione: Akj B = {x : xe A o xe B} Se rappresentiamo gli insiemi A e B mediante diagrammi di Venn, cioè mediante nuvolette a forma elissoidale che delimitano gli

(spesso invisibili) elementi dell'insieme, allora l'intersezione e l'u-nione corrispondono alle parti in grigio di figura 12. L'esempio (2) della figura 12 evidenzia il fatto che se A c B allora AuB = BeAniB = A. Gli insiemi A e B dell'esempio (3) si dicono disgiunti; in questo caso A n B = 0 . Sembrerebbe più naturale, in luogo di "A Pi B = 0 " , impiegare l'espressione "A e B non hanno intersezione". In tal caso sarebbe però necessario distinguere tra gli insiemi che hanno intersezione tra loro e quelli che non ne hanno. Invece, disponendo dell'insieme vuoto, questa distinzione si può evitare: l'operazione si applica in ogni caso. Una partizione di un ins ieme^ è un insieme X= {A1( A2,—} di sot-toinsiemi non vuoti di A, a due a due disgiunti e tali che la loro unione è uguale ad A (un esempio in figura 13A). Il concetto matematico di partizione formalizza l'idea naturale di "suddivisione di un insieme" o di "classificazione (cioè divisione in classi) di un insieme". Diamo alcuni tra gli innumerevoli esempi: (1) le classi (non nel senso di aule ma in quello di insiemi di alunni)

FIGURA 12

Intersezione e unione rappresentate mediante diagrammi di Venn

An B Au B

C O E ) <mm An B AuB

,2) ( C D Ì ) • An B AuB

(3) O Q <DQ ••

di cui un istituto scolastico è composto sono una partizione dell'in-sieme degli studenti dell'istituto stesso: infatti ogni classe è non vuota, ogni coppia di classi è disgiunta, e l 'unione di tutte le classi forma l'insieme totale degli studenti dell'istituto; (2) la divisione di un genere (nel senso della biologia) in varie specie costituisce una partizione del genere stesso; (3) gli stati nazionali e le loro colonie costituiscono una partizione delle terre emerse (salvo qualche tratto d'Antartide); (4) un testamento descrive una partizione di un de-terminato insieme di beni. Dato un insieme A il complementare di v4 è l'insieme degli elementi che non appartengono ad A. In simboli, Ac = {x : x £ A}. Riguardo a questa operazione, che viene detta di complemento (e che riguarda un singolo insieme e non due come intersezione e unione), è neces-saria una precisazione. Supponiamo, ad esempio, che A sia l'insie-me dei numeri pari. Allora Ac, per definizione, deve contenere tutto ciò che non è un numero pari e pertanto, oltre ai numeri dispari, anche tutti gli ombrelli, gli alberi e così via. Quasi certamente, inve-ce, parlando del complementare dell'insieme dei numeri pari si vuole semplicemente intendere l'insieme dei numeri dispari. In ef-fetti, l'operazione di complementazione di un insieme è relativa ad un altro insieme, più grande e spesso sottinteso, che costituisce l'u-niverso del discorso (nel nostro esempio l'insieme dei numeri natu-rali). Indicando con U questo insieme universo, allora con il com-plementare di A si intende l'insieme

FIGURA 13

(A) Partizione di un insieme A nei sottoinsiemi AJ-A4

(B) Complementare di un insieme A rispetto ad un insieme universo U

Ac = {x-.xe Ucx£ A]

(A) (B)

(nell'esempio di figura 13B l'universo U è il rettangolo delimitato dal tratteggio). Le operazioni di intersezione, unione e complemento vengono dette operazioni booleane. Un'espressione booleana (o anche espressione insie-mistica) nelle variabili A,B,C,... è un'espressione che, oltre a tali va-riabili, coinvolge solo (ma non necessariamente tutte) le operazioni booleane. Ad esempio, (Ac n B) u A e (A u B)c n (Ac n C) sono espressioni booleane, rispettivamente in due e in tre variabili. Se A,B,C,... denotano sottoinsiemi di un dato insieme universo U, allora ogni espressione booleana mA,B,C,... individua ancora un sot-toinsieme di U. Per trovarlo, si può procedere per gradi, individuan-do via via i sottoinsiemi corrispondenti alle varie sottoespressioni che formano l'espressione booleana. Nella figura 14, dati tre sottoinsiemi A,B,C di U, mostriamo i sottoinsiemi individuati dalle espressioni (A u C) n Bc e (Ac n Bc)c. Per rendere più agevole la ricerca, abbia-mo numerato le parti in cui quei tre insiemi suddividono l'universo U; poi, per ogni sottoespressione coinvolta, abbiamo individuato le parti a cui essa corrisponde. Nel primo caso abbiamo:

AuC: 1-2-4-5; 1-5-6; {A u C) n B< : 1-5 (parte grigia in figura sinistra).

Nel secondo caso abbiamo:

Ac : 3-4-5-6; B< : 1-5-6; Ac n B< : 5-6; (4C n ff)c : 1-2-3-4 (parte grigia in figura destra).

FIGURA 14

Insiemi individuati da espressioni booleane

ì P H B B ^ ^ a p ^ X . 5 \ c 6

In grigio gli insiemi individuati dalle espressioni (A u C ) n Bc, a sinistra, e (Ac n Bc)c, a destra.

Tra gli insiemi possono stabilirsi ulteriori operazioni. L'operazione di differenza (insiemistica), indicata con il simbolo - oppure con \, è definita come segue:

differenza-. A- B = {x: xe Aexg B}.

Essa è esprimibile in termini di intersezione e complemento. Infatti A-B = A rìBT. Un'ulteriore operazione è la differenza simmetrica, indicata con il simbolo ©:

differenza simmetrica-. A® B = (A - B) u (B - A).

Anch'essa è esprimibile mediante le operazioni booleane, essendo A © B= (A n Bc) U (B r\Ac). Operazioni come queste, che sono riconducibili ad un'espressione booleana, sono dette booleanamente esprimibili. Nel paragrafo 2.4 incontreremo la più importante tra le operazioni non booleanamente esprimibili: il prodotto cartesiano.

2.2.2. Identità insiemistiche Consideriamo le due identità A n B = Bc\AzAr\B = A. Istintivamente (e correttamente) chiunque ri-conosce che la prima è valida e la seconda non lo è. Cercando di precisare il concetto, osserviamo che la prima vale universalmente, cioè vale per qualunque coppia di insiemi A e B, mentre la seconda può essere falsificata. Con ciò non si intende dire che sia sempre fal-sa (ad esempio, nel caso in cui A^B, è vero che A n B = A), ma semplicemente che non è sempre vera. Ovviamente, la ricerca delle identità tra espressioni insiemistiche che sono valide è importante, in quanto esse rappresentano leggi generali degli insiemi. Tuttavia, mentre per mostrare che un'iden-tità non è valida è sufficiente esibire un controesempio (cioè un'in-terpretazione delle variabili A,B,C,... che la falsifichi), per mostrare che un'identità è valida bisogna dimostrare che essa vale per tutte le infinite possibili interpretazioni delle variabili. Non potendosi fare ciò in modo diretto, bisogna trovare strategie opportune. Nei casi come A B = B r^ A, o in casi altrettanto semplici quali (A n B) n C=A n (B n C), oppure (AC)C = A, la validità discende in modo pressoché immediato dalle definizioni. Tuttavia, in gene-

rale, ciò non accade. L'eventuale validità di (A O B)c = AC O Bc, oppure di (A n B)c = Ac u Bc, non è immediatamente percepibile (e anzi, in questo caso la risposta che di primo acchito sembra più plausibile è quella sbagliata). Qui di seguito mostriamo un metodo per determinare in modo meccanico la validità di un'identità insie-mistica.

2.2.3. Il metodo delle tavole di appartenenza Iniziamo con le tavole di appartenenza delle tre operazioni booleane:

I N T E R S E Z I O N E U N I O N E C O M P L E M E N T O

A B Ac\B A B A u f i A Ac

€ <2 € £ SÉ <2 £ e É e e e e e e € e e e e é e € e e G e e

Nelle prime due colonne delle tavole dell'intersezione e dell'unione troviamo tutte le possibili situazioni di appartenenza di un generico elemento rispetto ad Ae B,e sono quattro: esso può non appartene-re né ad A né a B, oppure non appartenere ad A ma appartenere a B, oppure appartenere ad A ma non appartenere a B, oppure apparte-nere ad A e a B. A questo punto la lettura delle tavole è immediata. Ad esempio, la prima riga della tavola dell'intersezione ci dice che se un generico elemento non appartiene ad A e non appartiene a B allora non appartiene ad A n B; la seconda riga della tavola dell'u-nione ci dice che se un generico elemento non appartiene ad A e ap-partiene a B allora appartiene ad A u B. Nel caso del complemen-to, essendovi una sola variabile, le situazioni di appartenenza sono solo due; se un elemento non appartiene ad A allora appartiene ad Ac, e se appartiene adv4 allora non appartiene ad Ac. Basandosi sulle precedenti tavole delle operazioni, è possibile co-struire una tavola per qualunque espressione booleana. In figura 15 compare come esempio la tavola dell'espressione (A U B) n C. Trattandosi di un'espressione in tre variabili (A, B e C), le possibili situazioni di appartenenza sono otto. Per ciascuna di esse bisogna considerare l'appartenenza relativamente a tutte le possibili sottoe-

spressioni, fino ad arrivare all'espressione completa. Ad esempio, la lettura della prima riga della tavola è: se un generico elemento non appartiene ad A né a B né a C allora, per la tavola di U, non appar-tiene ad A u B mentre, per la tavola d i c , appartiene a O. A questo punto, poiché non appartiene a (A U B) e appartiene a C esso, per la tavola di n , non appartiene a (A u B) n O. Siamo ora in grado di determinare la validità di un'identità a = P tra due espressioni insiemistiche. Vale che:

P R O P O S I Z I O N E 2 . 2 . L'identità oc = P è valida se le colonne conclusi-ve delle tavole di appartenenza di a e P sono uguali tra loro.

Infatti, poiché nelle tavole vengono contemplate tutte le possibili situazioni di appartenenza, se accade che le colonne conclusive del-le tavole di a e di P sono uguali tra loro, allora significa che se un qualunque elemento appartiene all'insieme individuato dall'e-spressione a allora esso appartiene all'insieme individuato dall'e-spressione p, e viceversa. (Quanto detto vale nel caso in cui a e P abbiano le stesse variabili. Ma è facile trovare un rimedio nel caso in cui ciò non accada. Infatti se, ad esempio, in a compare la varia-bile D e in p non compare, basta sostituire P con l'espressione p' = p u (D n 17). Essendo Z)nZ>' = 0 e P u 0 = P, tale sostitu-zione è ininfluente, e tuttavia p' contiene D.) Due espressioni insiemistiche a e P tali che l'identità a = P è valida si dicono equivalenti (insiemisticamente).

FIGURA 15

Tavola di appartenenza dell'espressione booleana W u B I n C

A B C Au B (A u 8) n C

€ £ E e G E SÉ <2 G € E É E e £ G G G e e G G E É G E E G G G G £ G G <2 E G £ G G G G G G G G €

Possiamo ora risolvere la questione posta a p. 43 , facendo le tavole delle tre espressioni coinvolte nelle identità (A n B)c = AcC\B: e (A O B)c = AckjBc (per concisione, abbiamo evitato di riscrivere ogni volta tutte le colonne).

A B AnB Ac r\Bc Ac Bc AcnBc Ac\JBc

£ É e e e e e € e £ e e £ € G

e £ e € £ e E G

e e e £ € e

Le colonne relative a (A O B)c e Ac u Bc sono uguali tra loro, mentre quella relativa a Ac n Bc è diversa. Quindi, (A n B)c = AC O Bc non è un'identità valida, mentre (A n B)c = Ac u Bc è valida e le due espressioni che vi compaiono sono equivalenti (a parole: il comple-mentare dell'intersezione è uguale all'unione dei complementari).

2.3. Espressioni insiemistiche e formule logiche La teoria degli insiemi si intreccia continuamente con la logica, essendo que-ste le due teorie su cui si fonda la matematica: la prima fornisce la materia di base, la seconda gli schemi dimostrativi. Una corrispon-denza elementare tra insiemi e logica (elementare non solo nel sen-so che è semplice da descrivere, ma anche nel senso che avviene a li-vello dei primi elementi) è quella che si stabilisce tra le operazioni insiemistiche booleane e i connettivi logici. Consideriamo le se-guenti proposizioni p e q:

p : " x appartiene ad A" q : "x appartiene a B"

Vale che: (1) la proposizione "x appartiene ad A O B" è vera quando è

vera p e è vera q\ (2) la proposizione "x appartiene ad A U 5 " è vera quando è

vera p o è vera q\ (3) la proposizione "x appartiene ad Ac" è vera quando non è

vera p.

Vi è dunque una corrispondenza tra intersezione, unione e comple-

mento da un lato, e le parole e, o, non (che abbiamo sottolineato) dall'altro. Queste si comportano come operazioni tra proposizioni, nel senso che, applicate a proposizioni, formano nuove proposizio-ni. Quando sono considerate sotto questo aspetto, le parole e, o, non vengono chiamate connettivi logici (o anche operatori logici). I loro nomi individuali sono, nell'ordine, congiunzione, disgiunzione e negazione, e solitamente sono rappresentate mediante i simboli A, v e —i. Il legame che sussiste tra la verità di una qualunque coppiap e q di proposizioni e quella delle proposizioni composte p A q, p v q e —i\p è molto naturale, ed è continuamente applicato a livello intuiti-vo. Può essere descritto ricorrendo alle seguenti tavole di verità, dove F e V indicano rispettivamente la falsità e la verità di una proposizione.

C O N G I U N Z I O N E D I S G I U N Z I O N E

p 1 p^q P ? pvq P ^P F F F F F F F V F V F F V V V F V V F V F V V V V V V V

N E G A Z I O N E

La lettura delle tavole è ovvia; ad esempio, la prima riga della tavola della congiunzione esprime il fatto che se p è falsa e q è falsa allora p A q è falsa. Se sostituiamo i valori di verità F e V con i simboli di appartenenza g e e allora le tavole di verità dei connettivi coincidono con le ta-vole di appartenenza delle tre operazioni insiemistiche (cfr. p. 45). Pertanto le precedenti corrispondenze (1M3) (ricordando che in quell'esempio p e q stanno per "x appartiene ad A" e "x appartiene a B") possono essere riscritte in questo modo:

(1) la proposizione "x appartiene ad A o B" è vera quando è vera p/\q\

(2) la proposizione "x appartiene ad A\J B" è vera quando è vera pvq;

(3 ) la proposizione "x appartiene adAc" è vera quando è vera —>/>.

A questo punto, la corrispondenza tra gli operatori n , u , da un lato e A, v , —i dall'altro è completa e può estendersi a oggetti più complessi. Sostituendo uniformemente le variabili insiemistiche A,B,C con variabili proposizionali p,q,r, e sostituendo i simboli PI, U , f con A, v , —i, accade che: a) un'espressione insiemistica si trasforma in ciò che viene definito una formula proposizionale (nella trasformazione occorre un po' di cautela, per il fatto che mentre il segno di complementazione segue ciò che si vuole complementare, il corrispondente segno di negazio-ne precede ciò che si vuol negare); b) la tavola di appartenenza di un'espressione si trasforma nella ta-vola di verità della formula corrispondente; c) l'equivalenza insiemistica tra due espressioni si trasforma nellV quivalenza logica tra le due formule corrispondenti. Tale equivalen-za viene indicata con il simbolo =, e il criterio diretto per stabilirla si ottiene traducendo in termini logici la Proposizione 2.2 di p. 44:

P R O P O S I Z I O N E 2.3. Due formule proposizionali cp e vy sono logica-mente equivalenti se le colonne conclusive delle tavole di verità di cp e Y|/ sono uguali tra loro.

Facciamo alcuni esempi. Riguardo al punto a\

(A U B) n C si trasforma in (p v q) A r

Riguardo al punto b, la tavola di appartenenza dell'espressione in-siemistica {A u B) n O (cfr. FIG. 15) si trasforma nella tavola di verità della corrispondente formula (pvq)A—ir (cfr. FIG. 16). Così come la prima tavola ci informa dell'appartenenza a (AuB)n Cìn funzione dell'appartenenza a.dA, B, C, allo stesso modo la seconda ci informa della verità di (p v q) a —ir in funzio-ne della verità di p, q, r. Infine, riguardo al punto c, l'identità valida {A n B)c = AC U Bc (cfr. p. 45) si trasforma nell'equivalenza logica —1 (p A q) = —1p v —1 q.

Ac

AnBT ( .AuA c) c

si trasforma in —1p si trasforma in p A —1 q si trasforma in —1 (p v —1p)

Quali vantaggi si ottengono dal rapporto tra espressioni insiemisti-che e formule logiche? Quello più facilmente percepibile è il se-guente: grazie al legame tra equivalenza insiemistica ed equivalenza logica siamo spesso in grado di intuire la validità di un'identità in-siemistica senza ricorrere alle tavole di appartenenza o ad altri algo-ritmi. Facciamo un esempio. A p. 45 abbiamo stabilito, mediante tavole, la validità dell'identità (A n B)c = AC U Bc. Ma avremmo potuto convincerci anche argomentando in questo modo: "se un elemento appartiene al complementare dell'intersezione tra A e B, allora non appartiene a tale intersezione, cioè non appartiene (con-temporaneamente) ad A e B. Ma se non appartiene ad A e B allora non appartiene ad A oppure non appartiene a B". Se evidenziamo il comportamento delle parole e, 0, non nell'argomentazione posta tra virgolette, vediamo come la validità di (A n B)c = AC u Bc sia stata ricavata dall'equivalenza —1 (/> A q) = —<p v —¡q. Quest'ultima, che è la traduzione logica dell'identità insiemistica, è stata quindi ritenu-ta più intuitiva. A questo livello iniziale, dunque, l'intuizione logica viene in aiuto a quella insiemistica. Ma a livello meno elementare, il fatto che gli insiemi possano, al contrario delle formule, essere vi-sualizzati mediante rappresentazioni grafiche, inverte il senso della dipendenza, e permette ai concetti logici di appoggiarsi ai corri-spondenti concetti insiemistici. La scambio è comunque continuo, al punto che, a volte, quello logico e quello insiemistico sembrano due modi diversi di descrivere la stessa costruzione.

FIGURA 16

Tavola di verità della formula proposizionale (p v q) A - . r

P Q r pwq -1 r (PV Q) A —,R

F F F F V F F F V F F F F V F V V V F V V V F F V F F V V V V F V V F F V V F V V V V V V V F F

Vi è un punto che sembra frapporsi alla perfezione della corrispon-denza tra operazioni insiemistiche e operatori logici. Che fine ha fatto l'implicazione? Coloro tra noi che hanno già incontrato la lo-gica, sanno dell'esistenza di questo ulteriore connettivo, indicato con —> o z>, e della sua problematica tavola di verità (cfr. FIG. 17). Diciamo subito che l'implicazione non si è persa. Le tavole di verità di p —> q e di —ip v q sono uguali tra loro, e quindi le due formule sono logicamente equivalenti. Ciò significa chep —» qh esprimibile in termini di v e —i, e può essere introdotta come abbreviazione di —i\p v q. Ancora esprimibile in termini di A, v e —i è l'altro connetti-vo "storico" mancante, la doppia implicazione: infatti, le formule p q e (—p v q) A (—Iq v p) sono logicamente equivalenti. La situazione di —» e <-> è pertanto analoga a quella delle operazioni insiemistiche di differenza e differenza simmetrica, esprimibili in termini di O, u e c (cfr. p. 42). Semmai ci si può chiedere se le ope-razioni insiemistiche - e © e i connettivi logici —» e <-> si corrispon-dono. La risposta è negativa. A — B è definita come A O Bc, e dun-que corrisponde a p A —1 q che, a sua volta, è equivalente a —1 (p —» q). Questo appare davvero strano: dal punto di vista insie-mistico risulta interessante un'operazione che non corrisponde ad un altrettanto interessante operatore logico, ma alla sua negazione. Lo stesso accade alla differenza simmetrica, che non corrisponde alla doppia implicazione ma alla sua negazione. Ma tutto questo non è in conflitto con quanto asserito in precedenza. Non si tratta infatti di differenze strutturali (ogni espressione insiemistica è tra-ducibile in formula, e viceversa), ma di diverse scelte su dove pun-

FIGURA 17

Tavole di verità dell'implicazione e della doppia implicazione

I M P L I C A Z I O N E DOPPIA IMPLICAZIONE

P 1 P <7 p<r+q

F F V F F V F V V F V F V F F V F F V V V V V V

tare l'attenzione. Riprendendo l'immagine usata in precedenza, si tratta di modi diversi di guardare — e descrivere — la stessa costruzio-ne. I concetti di algebra di Boole e di isomorfismo di struttura, che tratteremo nel capitolo 3, ci permetteranno di dare una veste mate-matica a questa immagine intuitiva.

2.4. Prodotto Cartesiano II concetto che consente di trattare le relazioni, le funzioni e le operazioni come particolari insiemi è quello di prodotto cartesiano, che a sua volta si fonda sul concetto di coppia ordinata. Una coppia ordinata è un insieme di due ele-menti in cui, contrariamente agli insiemi normali, conta l'ordine. La coppia ordinata formata da x e y si indica con (x, y). Non si esclude il caso in cui le due componenti siano uguali: anche (x,x) è quindi una coppia ordinata. Dato il rilievo che ha l'ordine, si ha, nel caso in cui x^y, che (x,y) ^ (y,x) (mentre {x,y} = {y,x}). Dati due insiemi A e B, il prodotto cartesiano Ax Bè l'insieme costi-tuito da tutte le coppie ordinate la cui prima componente appartie-ne ad A e la cui seconda componente appartiene a B. In simboli:

AxB = ((x,j/):xe Aeye Bj.

Ad esempio, se A = {a,b,c\ e B= {d,e} allora A x B= {(a,d), (a,e), (b,d), (b,e), (c,d), (c,e)}. Naturalmente, i due insiemi tra cui si ese-gue il prodotto possono essere uguali tra loro, cioè è possibile ese-

FIGURA 18

Rappresentazione del prodotto cartesiano

fi " \ , AxB /(e) \ ( (a. e) (b.e) (c.e)i R

R x R

V 1 (d) J 1 ¡la. di i(b,d) : [c, d)\ \ f j V

y i(a) ; (b) i Tcp; A 0 * R

(A) (B)

guire il prodotto di un insieme per se stesso. Considerando anco-ra A = {a,b,c), abbiamo AxA = {(a,a),(a,b),(a,c),(b,a),(b,b),{b,c), (c,a),(c,b),{c,c)}. Al posto dì A xA si scrive anche A2.

P R O P O S I Z I O N E 2.4. Dati due insiemi finiti A e B, se Card{A) = n e Card(B) = m allora Card(A X B) = n • m.

Il prodotto cartesiano non è booleanamente esprimibile, cioè non è riconducibile alle operazioni di n , u e c, ma si pone su di un piano diverso. Se A e B sono sottoinsiemi di un insieme U, anche la loro intersezione, la loro unione e i loro complementari sono sottoinsie-mi di U. Di conseguenza lo sono anche tutti i risultati di ogni ope-razione booleanamente esprimibile. Invece, a meno di casi partico-lari, il prodottoci X B non è un sottoinsieme di U; infatti i suoi ele-menti sono coppie ordinate di elementi di U, le quali non è detto che siano a loro volta elementi di U. Non è quindi possibile rappre-sentare il prodotto cartesiano mediante diagrammi di Venn, come capita ad ogni operazione booleanamente esprimibile, e bisogna ri-correre ad un nuovo tipo di diagrammi che, appunto, si chiamano diagrammi cartesiani. Esprimendoci in termini un po' approssimativi, il diagramma carte-siano di A X B si ottiene sistemando su un asse orizzontale gli ele-menti di A, su uno verticale quelli di B e ponendo, per ogni x e A e y e B, la coppia (x,y) nel punto di intersezione tra la retta verticale passante per x e la retta orizzontale passante per y. In figura 18A vie-ne rappresentato il prodotto cartesiano A x B, con A = \a,b,c\ e B= {d,e}. Naturalmente, nella pratica la rappresentazione completa di A X B è possibile solo nel caso in cui A e B siano finiti e ragione-volmente piccoli; negli altri casi ci si limita ad una rappresentazione parziale, che comunque può essere utile per aiutare l'intuizione. Nel caso del prodotto R X R la rappresentazione è quella ben nota del piano cartesiano (cfr. FIG. 18B).

2.5. Relazioni Mediante il prodotto cartesiano definiamo ora il concetto di relazione. Questa parola è presente in ogni genere di di-scorso, anche non matematico. Esempi di relazioni sono non solo il parallelismo, la similitudine, l'"essere minore di", ma anche la con-sanguineità, la dipendenza, e ogni forma di parentela e di gerarchia.

In termini intuitivi, una relazione R può essere intesa come un lega-me che sussiste tra certe coppie di elementi e non tra altre. Ad esempio, la relazione "esser minore di" sussiste tra 3 e 5, ma non tra 5 e 3. E ancora, la relazione "essere padre di" sussiste tra Filippo n di Macedonia e Alessandro Magno, ma non tra Enrico v m d'In-ghilterra ed Enrico Fermi (tra i quali esiste invece la relazione di omonimia). Certamente, per quanto questi esempi siano ben noti, il concetto generale rimane ancora vago, dal momento che la parola "legame" che abbiamo impiegato per definirlo è sostanzialmente un sinonimo. La definizione insiemistica supera questo tipo di dif-ficoltà e identifica direttamente una relazione con l'insieme delle coppie che la soddisfano. Ad esempio, relazione "essere padre di" viene identificata con l'insieme delle coppie (x,y) tali che x è padre diy; la relazione di parallelismo viene identificata con l'insieme del-le coppie di rette parallele e così via. Questo modo di procedere, de-finito estensionale, può lasciare insoddisfatti. Identificando una rela-zione con l'insieme delle coppie che essa lega sembra di perdere qualcosa, come ad esempio il "senso" della relazione o i modi con cui determinarla. Tuttavia, almeno da un punto di vista matemati-co, ciò che è essenziale è sapere se una certa coppia è o no in relazio-ne, ed è proprio a questo tipo di domande che la definizione insie-mistica risponde. Identificando una relazione tra elementi di un insieme A con l'in-sieme delle coppie che essa lega, tale relazione si trova ad essere un sottoinsieme del prodotto cartesiano A x A , che è l'insieme di tutte le coppie di elementi di A. La definizione insiemistica di relazione è dunque la seguente: una relazione R su A è un sottoinsieme di AxA. È possibile, più in generale, che una relazione leghi tra loro elemen-ti di un insieme A con elementi di un insieme B. In tal caso una re-lazione RdaAaBhnn sottoinsieme di x B. Per esprimere il fatto che un elemento x è in relazione con un ele-mento y si scrive xRy oppure (x,y) e R. Le relazioni matematica-mente più importanti hanno un simbolo specifico: ad esempio, < per la relazione "essere minore o uguale di", c; per la relazione di inclusione, // per la relazione di parallelismo. Invece, l'impiego di variabili come la nostra R per denotare relazioni qualunque può es-

sere considerato una novità della teoria degli insiemi, ed è una con-seguenza del fatto che in tale teoria il concetto di relazione è tratta-to nella sua generalità. Poiché una relazione R da A a B è, per definizione, un sottoinsieme del prodotto A x B, possiamo impiegare la rappresentazione di tale prodotto (il diagramma cartesiano) per visualizzare R, e ciò si può fare evidenziando, in un qualunque modo, l'insieme dei punti (x,y) di A x B tali che xRy. Questa rappresentazione è detta grafico carte-siano di R. In figura 19 mostriamo due esempi. Nel primo (FIG. 19A) le coppie di A x B che appartengono alla relazione sono state evi-denziate circolettandole. La relazione rappresentata è R={(a,d), (b,d), (b,e), (c,e)}, cioè la relazione tra A e B tale che aRd, bRd, bRe e cRe. Come si vede, si tratta di una definizione astratta, tra elemen-ti di cui si ignora la natura. Se A fosse l'insieme dei tre uomini Aldo, Bruno e Carlo (rispettivamente a,b e c), B fosse l'insieme del-le due donne Daniela ed Elisa (d ed e) ed xRy esprimesse la relazio-ne "x va matto per y" allora R ci informerebbe che Aldo va matto per Daniela, Carlo va matto per Elisa, e Bruno va matto per tutte e due. Il secondo esempio, in figura 19B, rappresenta la relazione R sull'insieme R dei numeri reali espressa dalla seguente condizione: xRy se x^+y1 < 1. Infatti, per il teorema di Pitagora, i punti (x.jO tali che x2 + y1 = 1 sono esattamente quei punti la cui distanza dal centro O è uguale ad 1, cioè i punti che formano la circonferenza di centro O e di raggio 1. Pertanto, i punti (x,y) tali che x1 -I-y2 < 1

FIGURA 19

Rappresentazione cartesiana di relazioni

R

(A) (B)

sono quelli che stanno all'interno di tale circonferenza. Nella figu-ra, i punti di R X R che appartengono alla relazione, cioè i punti (x,y) tali che xRy, sono stati anneriti.

2.5.1. Proprietà di relazioni su un insieme Alcune proprietà delle re-lazioni (prima fra tutte quella di essere una funzione) si applicano indifferentemente sia a relazioni da un insieme ad un altro insieme, sia a relazioni da un insieme a se stesso. Altre proprietà, come le se-guenti, sono invece specificamente riferite a relazioni da un insieme a se stesso, cioè su un insieme. Una relazione R su un insieme A è • riflessiva se, per ogni x e A, vale xRx; • simmetrica se, per ogni x,y e A, se xRy allora yRx-, • antisimmetrica se, per ogni x,y e A, se xRy e yRx allora x =y\ • transitiva se, per ogni x,y,z e A, se xRy eyRz allora xRz. Queste proprietà sono significative in quanto servono a caratteriz-zare due tipi di relazione che (tra le relazioni che non sono funzio-ni) sovrastano le altre per importanza. Sono le relazioni di equiva-lenza e le relazioni d'ordine.

2.5.2. Relazioni di equivalenza Una relazione R su un insieme A è di equivalenza se è riflessiva, simmetrica e transitiva. Esempi di rela-zioni di equivalenza sono il parallelismo tra rette (è riflessiva: x II x, per ogni retta x; è simmetrica: se x II y allora ^ Il x; è transitiva: se x 1/ y e y // z allora x II z), la congruenza e la similitudine tra figure geometriche. Data una qualunque relazione R su A (non necessariamente di equi-valenza) e dato x e A, indichiamo con [x] R il sottoinsieme di A costi-tuito dagli elementi con cu ixè in relazione, cioè [ x ] i = ( y e A: xRy\. Consideriamo poi l'insieme XR = {[x]^ : x € A} di tutti questi sot-toinsiemi. Vale questo fatto:

P R O P O S I Z I O N E 2.5. XR è una partizione di A se e solo se R è una re-lazione di equivalenza.

L'importanza delle relazioni di equivalenza risiede proprio nel loro legame con il concetto di partizione (cfr. p. 39). Ad ogni partizione X corrisponde una e una sola relazione di equivalenza R (definita in questo modo: xRy se x e y appartengono allo stesso sottoinsieme

della partizione) e, viceversa, ad ogni relazione di equivalenza R corrisponde una e una sola partizione XR, formata dalle classi [x]^ definite precedentemente. Nel caso in cui R sia una relazione di equivalenza, l'insieme [x]^ viene definito classe di equivalenza di x e soddisfa questa proprietà: y e [x]R se e solo se [x]^ = \y\R (e dunque se e solo se x e [y]/j).Una classe di equivalenza può così essere rappresentata da uno qualun-que dei suoi elementi. Ad esempio, sia A l'insieme delle rette di un piano e R la relazione di parallelismo (che è di equivalenza) tra esse. Data una retta x, l'insieme [x]^ è l'insieme, detto fascio, costituito da tutte le rette di A parallele ad x. Presa una qualunque retta y € [x] R, cioè tale che xRy, accade che il fascio [y] R coincide con il fascio [x]*. L'insieme XR= {[x]^ : x e A} di tutti i fasci costituisce poi una partizione di A. Infatti, ciascun fascio è non vuoto, due fa-sci distinti non hanno alcuna retta in comune e l'unione di tutti i fasci è l'insieme di tutte le rette del piano. Relazioni e classi di equi-valenza saranno gli strumenti con i quali, nel capitolo conclusivo, definiremo in modo rigoroso le classi numeriche.

2.5.3. Relazioni d'ordine Una relazione R su un insieme A è una re-lazione d'ordine se è riflessiva, antisimmetrica e transitiva. Questa terna di proprietà vale ogniqualvolta una relazione su un insieme descrive una qualche forma di gerarchia. Sono relazioni d'ordine la relazione < su ciascuna delle classi numeriche che abbiamo incon-trato (è riflessiva: per ogni x vale x < x; antisimmetrica: se x < y e y < x allora x =y-, transitiva: se x < ^ e ^ < z allora x < z), la relazione C tra insiemi, la relazione "essere divisore di" tra numeri naturali (è riflessiva: un numero è divisore di se stesso; antisimmetrica: se n è divisore di m ed m è divisore di n allora n = m\ transitiva: se n è divi-sore di m ed m è divisore di s allora n è divisore di s), la relazione "essere antenato di" su un insieme di individui (considerando tra gli antenati di un individuo anche l'individuo stesso). Un fatto rilevante è che una relazione d'ordine non ammette cicli (la cui esistenza impedirebbe lo stabilirsi di una gerarchia). Non esistono cioè n elementi distinti ax, a2,..., a„, con n > 1, tali che axRa2R ... RanRax. Infatti, se così fosse, avremmo, per transitività,

a2Rax da cui, valendo axRa2, si otterrebbe, per antisimmetria, ax = a2, contraddicendo l'ipotesi che gli elementi fossero distinti. Oltre alle usuali rappresentazioni cartesiane, una relazione d'ordine R su un insieme finito A può essere rappresentata da un diagramma di Hasse. La costruzione è la seguente: a) ogni elemento di A è rap-presentato da un punto; b) se y è un successore immediato di x (cioè xRy, x * y e non esiste z, diverso da x ey, tale che xRz e zRy) allora il punto y viene posto sopra il punto x e i due punti vengono collegati da un segmento. Ad esempio, consideriamo la relazione d'ordine R={{a,a), (b,b), (c,c), (b,a), {b,c)} sull'insieme A = \a,b,c\. A sinistra di figura 20 ne abbiamo il diagramma cartesiano, a destra un diagramma di Hasse. È facile osservare come la seconda rappresentazione evidenzi con più immediatezza i fatti salienti di R, cioè che aec sono irrelati tra loro e b è sottoposto ad entrambi. Questa maggiore espressività dei dia-grammi di Hasse è dovuta al fatto che essi sono specifici per le rela-zioni d'ordine. Infatti, l'impiego delle categorie "sopra" e "sotto" per indicare il verso della relazione è possibile nelle relazioni d'ordine in quanto esse, ordinando gerarchicamente gli elementi, non am-mettono cicli; per altri tipi di relazioni ciò sarebbe privo di senso. Esempi ben noti di diagrammi di Hasse sono gli alberi genealogici, che rappresentano la relazione d'ordine "essere antenato di".

FIGURA 20

Rappresentazione di una medesima relazione d'ordine mediante (A) diagramma cartesiano e (B) diagramma di Hasse

a / \ 1 \ A x A / (C) \ (o.c) (b,c) (c.c) 1

' • \ 1 • ® ® 1 1 (fa) ! ! (0, fa) (fa. fa) (c, fa) i 1 • 1 1 • ® • ; (0) (c) 1 (")..' 1 (i}a, a) ffi(fa,o) . (c. o) i \ / \ ) \ /

C.To) . (fa) . (cP; A ( f a )

(A) (B)

Vi sono diversi tipi di relazioni d'ordine, caratterizzati dal valere o meno di ulteriori proprietà. La più significativa è la linearità-, per ogni x,y e A, xRy oyRx. Una relazione d'ordine che soddisfa questa nuova proprietà è defi-nita dì ordine totale (o lineare)-, altrimenti, cioè se esistono due ele-menti distinti x ey tali che né xRy néyRx, la relazione viene detta d'ordine parziale. Ad esempio, la relazione < su una qualunque del-le classi numeriche considerate è un ordine totale; infatti per ogni x,y vale x <y oppure ^ < x. Invece la relazione C tra i sottoinsiemi di un certo insieme U, con Card(U) > 1, è un ordine parziale in quanto, avendo U almeno due elementi, esistono coppie di sottoin-siemi X,Ydi U tali che n é X c Yné F c l Un altro esempio di or-dine parziale è la relazione "essere divisore di" sull'insieme N dei numeri naturali. Anche in questo caso esistono coppie di numeri diversi tra loro, ad esempio 2 e 3, tali che nessuno dei due è divisore dell'altro. Le relazioni d'ordine totale possono essere a loro volta suddivise tra ordini discreti e ordini densi (cfr. p. 20). La relazione < su N e su Z è discreta, quella su Q e su R è densa. Le proprietà di densità e di di-scretezza sono incompatibili, nel senso che non è possibile che una relazione le soddisfi entrambe. È possibile però che nessuna delle due sia soddisfatta, cioè che un ordine totale non sia né discreto né denso. Tuttavia, data una relazione d'ordine totale R suv4, se A è fi-nito allora R è discreta, mentre se R è densa allora è infinito.

2.6. Funzioni In termini intuitivi, possiamo definire una fun-zione / d a A a B come una legge che associa ad ogni elemento di A uno e un solo elemento di B. Per indicare che all'elemento x è asso-ciato l'elemento^ si impiega la scritturaJ{x) =y, ey è detto immagi-ne di x mediante f . È possibile però dare la definizione in termini in-siemistici, eliminando l'ambiguo riferimento alla parola "legge". Allo stesso modo in cui una relazione R è stata identificata con l'in-sieme delle coppie (x,y) tali che xRy, così una funzione f può essere identificata con l'insieme di coppie (x,y) tali c h e / * ) =y. Dunque: una funzione fda A a Be un sottoinsieme di Ax B tale che per ogni x e A esiste uno e un solo y e B per il quale (x,y) e f .

Con questa definizione le funzioni divengono particolari relazioni; infatti, una relazione è un generico sottoinsieme di A X B, mentre una funzione è un sottoinsieme di A x B che soddisfa ulteriori con-dizioni. Ciò può lasciare perplessi, dal momento che l'usuale prassi matematica tratta le relazioni e le funzioni in modo ben diverso. Il fatto è che la proprietà che caratterizza le funzioni all'interno delle relazioni, cioè l'unicità dell'elementoy in relazione con un dato x, è talmente rilevante da consentire un trattamento del tutto particola-re anche dal punto di vista linguistico. Fissato x, infatti, j{x) diviene il nome di un elemento di B. Gli insiemi A e B vengono detti rispettivamente dominio e codomi-nio della funzione e, naturalmente, possono coincidere. Molte fun-zioni hanno un simbolo proprio: ad esempio, il seno: y = sen(x), il coseno: y = cos(x), il valore assoluto: y=\x\, le funzioni potenza: y = x", le funzioni logaritmiche: y = log^x. Per indicare una funzione qua-lunque si impiegano scritture quali^x), F(x), g(x) ecc. Poiché le funzioni sono particolari relazioni, è possibile rappresen-tarle mediante grafici cartesiani, come accade per le relazioni in ge-nere. Il dato che caratterizza i grafici di funzioni è che, per l'unicità dell'elemento y corrispondente ad x, non possono esistere due pun-ti appartenenti al grafico allineati verticalmente, perché in tal caso esisterebbero due diverse y per uno stesso x. Vediamo più da vicino questo fatto ponendo a confronto la relazione rappresentata in figu-ra 19A (cfr. p. 53) con quella in figura 21. La seconda differisce dalla

FIGURA 21

Rappresentazione cartesiana di funzioni

R

c " . ( 0 ) . ( b ) . Ù P ; *

0 R

(A) (B)

prima solo per avere una coppia in meno. Infatti, in termini insie-mistici, la prima relazione è {{a,d), (b,d), (b,e), (c,e)}, la seconda è {(a,d), (b,e), (c,e)\. Questa differenza fa però sì che la prima rela-zione non sia una funzione, la seconda invece lo sia. Infatti, nel pri-mo caso abbiamo bRdt bRe, e quindi ad uno stesso elemento di A, cioè b, corrispondono più elementi di B, e precisamente ded e\ nel secondo caso, invece, ad ogni elemento di A corrisponde uno e un solo elemento di B, e possiamo quindi passare dalla scrittura rela-zionale aRd, bRe e cRd alla scrittura funzionale f a ) = d, j{b) = e e J{c) = e. La stessa situazione ritroviamo tra le relazioni rappresenta-te in figura 19B e figura 21B. La prima non è una funzione, dal mo-mento che ad ogni x compreso tra - 1 e 1 corrispondono infiniti^, mentre la seconda è una funzione (da A = {x : x e R e - 1 1| ad R). Ad ogni x di A corrisponde infatti uno ed un solo j/ di R, e precisamente ^ = Il concetto di funzione è stato per lungo tempo appannaggio pres-soché totale dell'analisi matematica. E poiché quest'ultima ha come ambiente privilegiato la classe dei numeri reali, le funzioni sono sta-te altrettanto a lungo identificate con le funzioni reali a variabile re-ale, cioè da numeri reali a numeri reali. Anche gli argomenti studia-ti sono stati relativi a questo tipo di funzioni: crescenza, continuità, derivabilità, integrabilità, somme, prodotti e così via. Con l'avven-to della teoria degli insiemi e dell'algebra astratta, il concetto di funzione ha notevolmente allargato il suo campo di applicazione, uscendo dall'ambito numerico. Al di fuori di tale ambito, parlare di continuità o crescenza di una funzione, oppure di somma e prodot-to tra funzioni, può essere totalmente privo di senso. Per contro, vi sono proprietà e operazioni che sono pertinenti per qualunque tipo di funzione. Tra le proprietà, un ruolo fondamentale all'interno della teoria degli insiemi lo hanno l'iniettività e la suriettività; tra le operazioni lo ha la composizione. Vediamole in ordine. Una funzione/da A a B è iniettiva se ogni elemento di B è immagi-ne di al più un elemento di A. Una funzione/"da A a B è suriettiva se ogni elemento di B è immagine di almeno un elemento di A. Una funzione biettiva (o anche biezione, o corrispondenza biunivo-ca) è una funzione che è contemporaneamente iniettiva e suriettiva. Queste proprietà si visualizzano efficacemente rappresentando le

funzioni, anziché in modo cartesiano, in modo sagittale, come in fi-gura 22. Nei diagrammi sagittali l'informazione f x ) =y viene esibi-ta tramite una freccia che va da x ad y. Quindi, la condizione che caratterizza le funzioni all'interno della classe delle relazioni (cioè che per ogni x e A esiste uno e un solo y e B tale che xRy) si con-verte nella richiesta che da ogni punto di A parta una e una sola freccia. Tutt i e quattro i diagrammi di figura 22 la soddisfano, e dunque rappresentano funzioni. L'iniettività si converte nel fatto che ad ogni punto di B arriva al più una freccia, mentre la suriettivi-tà si converte nel fatto che ad ogni punto di B arriva almeno una freccia. Pertanto, la funzione 1 di figura 22 non è iniettiva ed è su-riettiva (è la stessa funzione che in figura 21A è stata rappresentata in modo cartesiano), la funzione 2 non è né iniettiva né suriettiva, la 3 è iniettiva ma non suriettiva, la 4 è iniettiva e suriettiva, quindi biettiva. Se una funzione / d a a 5 è biettiva allora è possibile ottenere una funzione g da B ad A, ponendo g(y) = x se/fa) =y (si osservi che tale scrittura ha senso in quanto, essendo /biet t iva, esiste uno e un solo x la cui immagine mediante / è y). La g viene detta funzione inversa di / e indicata c o n / - 1 . Naturalmente, anche/""1 è biettiva, e la sua inversa è / In termini sagittali il passaggio d a / a / " 1 si ottiene inver-tendo il verso delle frecce. Data una funz ione /da A a B e una funzione g da B a C, si definisce composizione d i / e ^ l a funzione h àzA a Ctale che h(x) = gifx) ). In termini intuitivi, la composizione si ottiene applicando p r i m a / e

FIGURA 22

Rappresentazione sagittale di funzioni

¡X sur. X ìtf in. s H in. sur.

FIGURA 23

Composizione delle funzioni / e g

h( = hg)

h(a) =g(f(a)) =g(a') =c" hlbì • g(f(bìì • gta'f • c" h(c) = g(/(c)) = g(b'l = b"

A B C

poi g al risultato ottenuto (cfr. FIG. 23). Naturalmente, gli insiemi A, B e C possono coincidere. In alcuni testi, privilegiando l'ordi-ne di scrittura, la funzione g(J{x)) viene indicata con g o f ; in al-tri, privilegiando l'ordine di applicazione, viene indicata con

2.7. Operazioni Quello di operazione è uno dei primi termini matematici che ciascuno di noi ha incontrato. Una sua definizione informale, analoga a quella data per le funzioni, non esiste: il con-cetto di operazione sembra essere un concetto primitivo del lin-guaggio comune. Comunque, se analizziamo la più familiare delle operazioni matematiche, cioè la somma tra due numeri naturali, vediamo che essa comporta una serie di azioni (incolonnamento, scrivo-e-riporto) che producono come risultato un nuovo numero naturale. Tale operazione quindi (1) associa ad ogni coppia di nu-meri naturali un numero naturale e (2) ottiene questo risultato me-diante una serie di azioni. Come già avvenuto per relazioni e funzioni, anche il concetto di operazione può essere espresso nel linguaggio della teoria degli in-siemi. Tuttavia, la traduzione insiemistica formalizza solo il punto (1), mentre il punto (2), quello dinamico, viene staccato dal concet-to di operazione e associato a quello di algoritmo (allontanandosi così dal linguaggio comune, dove il termine operazione indica

un'azione mirata all'ottenimento di un certo risultato). Per giustifi-care questo abbandono si può osservare che, anche di fronte a me-todi diversi per eseguire la somma, se i risultati coincidono non è corretto parlare di operazioni diverse, ma di diversi modi (algorit-mi) per eseguire la stessa operazione. La definizione è dunque la se-guente: un'operazione binaria su un insieme A è una funzione da A X A ad A, cioè una funzione che associa ad ogni coppia ordinata di elementi di A uno e un solo elemento di A. Si osservi come in tal modo un'operazione binaria sia un sottoinsie-me del prodotto cartesiano ( A x A ) x A . L'aggettivo "binaria" è quasi sempre omesso. Somma e prodotto sono operazioni su N nel senso appena definito; infatti la somma associa ad ogni coppia di numeri naturali uno e un solo numero naturale, e lo stesso accade per il prodotto. La sottra-zione su N, invece, non è conforme alla definizione, in quanto se x < y non è possibile, rimanendo nell'ambito dei numeri naturali, eseguire l'operazione. Non lo è neppure la divisione. Lo sviluppo, descritto nel capitolo 1, che ha portato alla progressiva estensione della classe dei numeri naturali, può essere a questo punto interpre-tato come il tentativo di rendere operazioni, nel senso appena defi-nito, anche la sottrazione e la divisione. Come abbiamo visto, la conclusione è stata che la sottrazione è un'operazione su Z, su Q e su R, mentre la divisione, a causa della non superata "impossibilità" di dividere per 0, è un'operazione soltanto su Q—{0} e su R—{0}. Pur essendo possibile impiegare, per le operazioni, sia la notazione funzionale sia quella relazionale, abitualmente si inserisce il simbo-lo di operazione tra i due elementi della coppia: ad esempio, per in-dicare una somma si scrive 3 + 5 = 8 e non, come si farebbe con una funzione, +(3,5) = 8. Nel seguito, la scrittura x*y = z indicherà una generica operazione binaria, così come/(x) =y indica una gene-rica funzione e xRy una generica relazione.

2.7.1. Proprietà di operazioni Un'operazione » su un insieme vi è • associativa se, per ogni a,b,c e A, (a*b)*c = a*(b*c); • commutativa se, per ogni a,b e A, a*b = b*a. Operazioni associative e commutative sono la somma e il prodotto tra numeri, e anche l'unione e l'intersezione tra insiemi. Un esem-

pio di operazione non associativa né commutativa è quello della sottrazione; infatti, per x^y, accade che x—y^y — xc, per z ^ 0, accade che (x - y) - z * x - (y - z). Un esempio di operazione asso-ciativa e non commutativa è la composizione di funzioni: per ogni f,g,h si h a / o ( £ o h) = (f o g) o h) ma, in genere , / o g^g o f ) . Esistono anche operazioni commutative e non associative, ma non tra gli esempi più comuni. Dalla proprietà associativa deriva la possibilità di "abolire le paren-tesi". Data una qualunque operazione binaria *, la scrittura a*b*c è scorretta: dobbiamo infatti sapere se eseguire prima l'operazione tra a e b o prima quella tra b e c. Le parentesi servono appunto ad indi-care l'ordine: la scrittura (a*b)*c indica che prima dobbiamo ese-guire l'operazione a*b, mentre la scrittura a*(b+c) indica che dob-biamo eseguire per prima l'operazione b*c. Se * non è associativa le due procedure possono portare a risultati differenti: ad esempio (5 - 4) - 6 = - 5 , mentre 5 - (4 - 6) = 7. Se invece l'operazione è associativa la scelta è irrilevante in quanto (a*b)*c = a*(b*c). In que-sto caso la scrittura a*b*c, in cui le parentesi sono state abolite, non è ambigua e può essere accettata. Lo stesso accade passando da tre a un qualunque numero n di elementi. Siano *, e *2 due operazioni su A Diciamo che l'operazione è • distributiva rispetto all'operazione *2 se, per ogni a,b,c e A, a #! (b *2 c) = (a *ib) *2 {a*ic). Ad esempio, il prodotto è distributivo rispetto alla somma. Infatti, per ogni terna di numeri a,b,c, vale che a • (b + c) = (a • b) + (a • c). Per contro, la somma non è distributiva rispetto al prodotto, dal momento che, in genere, a + (b • c) ^ (a + b) • (a + c). Le operazioni di intersezione e di unione sono invece ciascuna distributiva rispet-to all'altra; infatti, data una qualunque terna di insiemi X,Y,Z, valgono sia Xn (Yv Z) = (Xn V) (J (Xn Z) che Xu{YnZ) = (Xv Y) n (XuZ).

2.8. Cardinalità di insiemi infiniti In questo paragrafo tor-niamo allo scopo originario della teoria degli insiemi e, ricollegan-doci al paragrafo 2.1, parliamo di cardinalità di insiemi infiniti. Nel caso di un insieme finito A, la cardinalità Card{A) è stata definita come il numero degli elementi di A, facendola quindi dipendere dal

concetto di numero. Mancandoci i numeri per gli insiemi infiniti, una definizione simile non può essere estesa a tali insiemi. Per poter parlare di cardinalità di un insieme infinito è necessario partire più da lontano, dai fondamenti, e prendere l'avvio, anziché dal concet-to di numero naturale, da quello di funzione. Descriviamo dappri-ma questa nuova strategia riferendoci ancora ad insiemi finiti; nel paragrafo 2.8.3 e s s a s a r a estesa agli insiemi infiniti.

2.8.1. Confronto di insiemi finiti tramite funzioni I seguenti risultati, molto intuitivi, pongono in relazione da un lato le cardinalità di due insiemi finiti A e B e, dall'altro, l'esistenza di determinate fun-zioni da A a B.

(1) Card(A) = Card{B) se e solo se esiste una funzione biettiva daAaB.

(2) Card(A) < Card(B) se e solo se esiste una funzione iniettiva e non suriettiva da A a B.

(3) Card(A) > Card{B) se e solo se esiste una funzione surietti-va e non iniettiva àzA a B. Ad esempio, per gli insiemi A e C di figura 22/4 (cfr. p. 60) vale Card(A) = Card(C); per gli insiemi A e D di figura 22/3 vale Card{A) < Card{C), mentre per gli insiemi A e B di figura 22/1 vale Card(A) > Card(B). Le proprietà (1M3) sono continuamente applicate a livello intuiti-vo. Se vi sono sei piatti su una tavola, anche un bambino che non sa contare potrà mettere sei cucchiai, semplicemente accostando un cucchiaio ad ogni piatto; in tal modo avrà applicato la (1), stabilen-do una corrispondenza biunivoca tra l'insieme A dei piatti e l'insie-me B dei cucchiai. Se, in una corriera da 50 posti, vediamo dei posti vuoti e non vediamo nessuno in piedi (e nessuno seduto sulle gi-nocchia di qualcun altro) allora, anche senza contare, sappiamo che i passeggeri sono in numero minore di 50; in questo caso abbiamo applicato la (2), stabilendo tra l'insieme A dei passeggeri e l'insieme B dei sedili una funzione/consistente nell'associare ad ogni passeg-gero il sedile su cui è seduto, funzione che risulta essere iniettiva e non suriettiva. Se, dopo una distribuzione di posta in un collegio di 50 ragazzi, nessuno è rimasto a mani vuote e qualcuno ha avuto più

di una lettera, allora sappiamo, applicando la (3), che le lettere era-no in numero maggiore di 50. I metodi di confronto ( 1 M 3 ) , che qui abbiamo presentato come un'alternativa al contare, ne costituiscono in realtà il fondamento. In effetti, non sono le relazioni "avere cardinalità uguale a" e "aver cardinalità minore di' che dipendono dalla proprietà "avere una de-terminata cardinalità", ma è questa proprietà che dipende da quelle relazioni, le quali a loro volta si basano esclusivamente sul concetto di funzione. Riferendoci ancora agli esempi precedenti, possiamo stabilire che i piatti sono tanti quanti i cucchiai, che le persone sono meno dei sedili della corriera, che le lettere sono più degli studenti del collegio, senza conoscere alcun numero, anzi, senza possederne il concetto. II passaggio dalle relazioni "avere cardinalità uguale a" e "aver cardi-nalità minore di" alla proprietà "avere una determinata cardinalità" avviene isolando particolari insiemi. In genere, quando contiamo gli elementi di un insieme, lo facciamo ponendo tale insieme in corrispondenza biunivoca con insiemi-tipo che hanno la forma {uno}, {uno, due}, {uno, due, tre}, {uno, due, tre, quattro}..., cioè con insiemi formati da parole la cui recitazione chiamiamo contare. Ognuno di questi insiemi-tipo è sottoinsieme proprio di tutti quelli successivi (esiste quindi una funzione iniettiva e non suriettiva da ognuno di essi a ciascuno dei successivi). È possibile, in via provvi-soria e in attesa di una definizione più rigorosa (cfr. PAR. 4.1), chia-mare questi insiemi-tipo numeri cardinali indicandoli, nell'ordine,

FIGURA 24

La cardinalità di A è 4

1 2 3 A 5

{uno}, {uno,due}, {uno,due,tre}, {uno,due,tre,quattro}, {uno.due,tre,quattro,cinque}...

con 1, 2, 3, 4... . Un numero cardinale (finito) è dunque un nume-ro naturale nella sua funzione di contare gli elementi di un insieme finito A. Poiché esiste esattamente un insieme-tipo che può essere posto in corrispondenza biunivoca con un dato A, il nome di que-sto insieme-tipo indica la cardinalità di A. Riassumendo, la costruzione del concetto di cardinalità di un insie-me finito può seguire questo cammino:

Passo 1. Si determina, in base alle funzioni che è possibile stabi-lire, quando due insiemi sono "equinumerosi" o quando uno ha "cardinalità minore dell'altro".

Passo 2. Si definisce una successione di insiemi-tipo (i numeri cardinali), ciascuno dei quali ha cardinalità minore del successivo e tali che ogni altro insieme finito sia equinumeroso ad uno di essi. A questo punto si definisce la cardinalità di un qualunque insieme ri-ferendosi all'insieme-tipo con il quale è equinumeroso. Questa strategia, che abbiamo descritto applicandola ad insiemi fi-niti, può essere applicata anche agli insiemi infiniti, e dà luogo a quella parte della teoria degli insiemi che va sotto il nome di aritme-tica transfinita. Si tratta tuttavia di un'estensione non semplice (ci limiteremo a descriverne le fasi iniziali) e, soprattutto, non è esente da sorprese. Gli insiemi infiniti permettono infatti dei "trucchi" che sono impossibili al finito. Può allora essere utile, per familiariz-zarsi con essi, far precedere la trattazione dal seguente esempio fi-gurato.

2.8.2. L'albergo di Hilbert e i dubbi di Galileo Supponiamo che un al-bergatore possieda un albergo con infinite stanze, una per ogni nu-mero naturale. Anche se sono tutte occupate, egli può fare a meno di esibire il cartello "pieno". Nel caso, ad esempio, di 3 nuovi arrivi è sufficiente che, per ogni n, sposti il cliente della stanza n nella stanza n + 3. A questo punto, pur continuando ciascuno dei vecchi occupanti ad avere una stanza tutta per sé (infatti, chi occupava il 2 è andato al 5, il cui occupante a sua volta è andato all'8, il cui occu-pante è andato all'I 1 ecc.), si liberano le prime 3 stanze, nelle quali l'albergatore può ospitare i nuovi arrivati (cfr. FIG. 25A, dove con v si sono indicati i vecchi ospiti e con a i nuovi arrivati). Ovviamente

questo artifìcio può essere impiegato per ogni numero di nuovi ar-rivi, purché finito. Ma anche se giungono infiniti nuovi clienti, tanti quante le stanze dell'albergo, l'albergatore è ancora in grado, cambiando strategia, di ospitarli tutti senza mandare via alcuno dei vecchi clienti. È suf-ficiente che, per ogni n, egli sposti il cliente della stanza n nella stanza In. Anche in questo caso nessuno dei vecchi ospiti perde l'al-loggio e ha ancora una stanza tutta per sé (l'occupante della 5 va nella 10, il cui occupante a sua volta va nella 20, il cui occupante va nella 40 ecc.), ma le infinite stanze con numero dispari rimangono libere, pronte per accogliere i nuovi venuti (FIG. 25B). L'albergatore riesce dunque nell'ardua impresa di far passare il suo albergo dallo stato di "tutto esaurito" a quello di "posti disponibili" senza dover costruire nuove camere o buttar fuori clienti, ma semplicemente spostandoli. Esprimendoci in termini di funzioni dall'insieme delle camere a quello dei clienti, egli riesce a passare da una funzione biettiva ("tutto esaurito") ad una funzione iniettiva e non suriettiva ("posti disponibili"), senza alterare né dominio né codominio. L'estensione delle (i)-(3) di p. 64 dagli insiemi finiti a quelli infiniti incontra dunque un ostacolo imprevisto. Quando sono applicate ad insiemi finiti, esse si escludono vicendevolmente, nel senso che se tra A e B esiste, ad esempio, una funzione biettiva, allora non può esistere una funzione iniettiva e non suriettiva, né una funzio-ne suriettiva e non iniettiva. Nel caso di insiemi infiniti è invece

FIGURA 25

L'albergo di Hilbert

| V I V I v |v |v |v |v 'v^

a a a (A)

a a a

| V IV IV |v |v |v |v ¡V 1 Iv i Ivi | v | !» ! 1 a | v| a| v| a| v |ar :

a a a a a (B)

possibile che le (1M3) si verifichino simultaneamente. Lasciando l'immagine dell'albergo ed esprimendoci in termini di funzioni nu-meriche, prendiamo ad esempio l'insieme A dei numeri pari, l'in-sieme B dei numeri naturali e consideriamo le tre funzioni da. A a B di figura 26. La funzione j{x) =x/2 è biettiva; la funzione g(x) = x è iniettiva e non suriettiva; la funzione h tale che se x è un multiplo di 4 allora h(x)=x/4, mentre se x non è un multiplo di 4 allora h{x) = 2)1 A, è suriettiva ma non iniettiva. Ovviamente, la domanda cruciale è questa: come giudicare il rappor-to tra la grandezza di A e quella di Bì Le opzioni possibili sono tre. a) Dal momento che A è un sottoinsieme proprio di B dobbiamo ri-tenere che "la parte sia minore del tutto", cioè Card(A) < Card{B)ì b) Oppure, essendo possibile la biezione f , dobbiamo ritenere che A e B siano equinumerosi, cioè CardiA) = Card{B) ? c) Oppure ancora, essendo possibile avere contemporaneamente f , g e h, dobbiamo ritenere che confrontare per grandezza gli insiemi infiniti sia privo di senso? Qui di seguito riportiamo la posizione che assunse Galileo riferen-dosi al caso, del tutto simile al precedente, dei numeri quadrati, che sono una parte dei numeri naturali, ma contemporaneamente sono equinumerosi ad essi (essendo ogni naturale la radice di un quadra-to). Il passo è tratto dalla Prima Giornata dei Discorsi intorno a due nuove scienze, pubblicato nel 1638 (il corsivo e il testo tra parentesi quadre sono nostri).

FIGURA 26

» è un sottoinsieme di B. Ma è and

A: 2 4 6 8 10 12 14 ...

1 1 1 1 i 1 1 1 / 6: 1 2 3 4 5 6 7 • •

te "minore" di S?

A: 2 4 6 8 10 12 14 ...

S: 1 2 3 4 5 6 7 -

/)- 2 4 6 8 10 12 14 ...

e: 1 2 3 4 5 6 7 -

Salviati. Onde se io dirò, i numeri tutti, comprendendo i quadrati e i non quadrati, esser

più che i quadrati soli dirò proposizione verissima: non è così?

Simplicio. Non si può dire altrimenti, [risposta a, dunque]

Salviati. Ma se io domanderò quante siano le radici, non si può negare che elle siano

quante tutti i numeri, poiché non vi è numero alcuno che non sia radice di qualche qua-

drato; e stante questo converrà dire che i numeri quadrati siano quanti tutti i numeri,

[risposta b, che contraddice la a]

Sagredo. Che dunque si ha da determinare in questa occasione?

Salviati. lo non veggo che ad altra decisione si possa venire, che a dire infiniti essere

tutti i numeri, infiniti i quadrati, infiniti le loro radici, né la moltitudine dei quadrati es-

ser minore di quella di tutti i numeri, né questa maggiore di quella, ed in ultima conclu-

sione, gli attributi di uguale, maggiore e minore non aver luogo negl'infiniti, ma solo

nelle quantità terminate, [risposta c]

Galileo, per bocca del suo alter ego Salviati, non ha dubbi: poiché le risposte a e b sono ugualmente plausibili ma sono contraddittorie tra loro, la risposta giusta è c: non ha senso confrontare per gran-dezza gli insiemi infiniti. Almeno in questo, il maestro pisano fu d'accordo con Aristotele, che proprio per evitare un simile confron-to aveva eliminato dalla scienza l'infinito attuale surrogandolo con l'infinito potenziale (cfr. PAR. 2.1). Tuttavia, due secoli e mezzo dopo Galileo, Cantor ritenne che la risposta giusta fosse b e che il principio "il tutto è maggiore della parte" dovesse essere limitato solo agli insiemi finiti. Anzi, ritenne che la possibilità di essere equi-numeroso ad una propria parte dovesse essere presa proprio come definizione dell'infinità di un insieme. Era il passo d'inizio nella co-struzione della teoria degli insiemi, quel paradiso dal quale, secon-do le parole di Hilbert, nulla ci avrebbe più cacciato.

2.8.3. Confronto di insiemi infiniti tramite funzioni Proviamo dunque ad estendere agli insiemi infiniti le condizioni (1M3) di p. 64. Alla luce delle difficoltà emerse, esse devono essere riscritte nel modo se-guente. Dati due insiemi A e B

(1) Card{A) = Card(B) se da A a B esiste una funzione biettiva. (2) Card(A) < Card(B) se da A a B non esiste alcuna funzione

biettiva ed esiste una funzione iniettiva e non suriettiva.

(3 ) Card(A) > Card{B) se da A a B non esiste alcuna funzione biettiva ed esiste una funzione suriettiva e non iniettiva. Alcune osservazioni. • Mentre le (1M3) erano dei teoremi che mostravano collega-menti tra il concetto di cardinalità (finita) e l'esistenza di determi-nate funzioni, le (i')-(3 ) sono delle definizioni, e si riferiscono ad insiemi di qualunque genere, finiti e infiniti. In particolare, la (1) definisce il concetto di "essere equinumeroso", cioè "avere uguale cardinalità", la (2) e la (3') definiscono il concetto di "avere minore [maggiore] cardinalità". • Le condizioni (2) e (3') contengono anche la richiesta, super-flua nel caso di insiemi finiti, che i due insiemi non possano essere posti in corrispondenza biunivoca. Ciò è stato fatto per rendere tali condizioni incompatibili con la condizione (1). Poiché si può di-mostrare che anche (2) e (3') sono incompatibili tra loro, risulta che (1), (2) e (3) sono mutuamente escludentesi. Oltre a ciò, le tre condizioni sono esaustive, nel senso che una delle tre si realizza co-munque. Pertanto, la relazione < che si ricava dalle ( 1' ) -(3' ) è una re-lazione d'ordine totale.

2.8.4. Esistono insiemi infiniti non biettivi tra loro? Giunti a questo punto, il Passo 1 di p. 66 è stato realizzato: dati A e B, sappiamo cosa significa dire che Card(A) = Card(B), oppure Card(A) < Card(B), oppure Card(A) > Card{B). Rischiamo però di trovarci nella stessa situazione di quel prode cavaliere medioevale che, desi-deroso di combattere i draghi, aveva deciso di prepararsi al difficile compito studiando prima tutta la letteratura al riguardo. Quando finalmente, dopo lunghi anni di studio, iniziò a percorrere le terre in lungo e in largo alla ricerca dei draghi, non ne trovò alcuno (la storia poi continua narrando che egli fece ritorno al suo castello e fondò una scuola su come combattere i draghi, ma questo epilogo non ci riguarda). I nostri draghi sono costituiti dalle coppie di insiemi infiniti che soddisfino la (2') o la (3'), cioè che non siano equinumerosi tra loro. In effetti, non sappiamo ancora se esistono o no. Fino a questo punto abbiamo incontrato esempi di insiemi infiniti che si sono ri-velati biettivi tra loro (quali l'insieme dei numeri pari e quello dei

numeri naturali), e quindi che soddisfano la (1). Se dovesse verifi-carsi che, per gli insiemi infiniti, vale sempre la (1) allora non vi sa-rebbe motivo di procedere: tutti gli insiemi infiniti sarebbero uguali dal punto di vista cardinale e, dal momento che non si fa aritmetica con un numero solo, l'aritmetica transfinita non avrebbe ragione di nascere. Quella che abbiamo formulato è tutt'altro che un'ipotesi retorica. La disinvoltura con cui gli insiemi infiniti incontrati negli esempi precedenti si lasciano sdoppiare in parti grandi quanto l'originale spinge in questo senso, e lo stesso Cantor, per un certo periodo, ri-tenne che la situazione dovesse essere proprio questa. Riuscì infatti a stabilire funzioni biettive tra insiemi apparentemente molto diversi tra loro per grandezza, e ogni funzione biettiva che si riesce a stabili-re equivale ad un potenziale drago che svanisce. Egli mostrò dappri-ma la (a questo punto poco sorprendente per noi) equinumerosità tra l'insieme dei numeri naturali e quello dei numeri interi:

P R O P O S I Z I O N E 2.6. Card{N0) = Card{Z). Una possibile funzione biettiva tra N 0 e Z è la seguente:^«) = ni2 se n è pari , j{n) = —(n + l ) /2 se « è dispari (si tratta della stessa idea da cui ha origine l'esempio dell'albergo di Hilbert).

Ben più stupefacente fu la scoperta che anche l'insieme Q dei nu-meri razionali, che è denso, è equinumeroso all'insieme dei numeri interi e quindi a quello dei numeri naturali, che sono discreti:

P R O P O S I Z I O N E 2.7. Card{Z) = CardiQ)-

Per dimostrare questa uguaglianza si costruisce dapprima una fun-zione biettiva/tra l'insieme Z + dei numeri interi positivi (cioè N) e l'insieme Q + dei numeri razionali positivi. Si dispongono le frazio-ni come in figura 27A, formando una matrice infinita. In essa è pre-sente ogni numero razionale positivo. Anzi, uno stesso numero compare infinite volte: ad esempio, il numero 1/2 lo troviamo, ol-tre che nella prima riga, anche nella riga sottostante, nella forma 2/4, nella riga ancora sotto, nella forma 3/6 e così via. Iniziamo a percorrere la matrice a "zig-zag" per diagonali successive, come in figura 27B, numerando ordinatamente (cioè "etichettando" me-diante numeri naturali) i numeri razionali che si incontrano, igno-

rando però quelli già incontrati precedentemente sotto altra forma. Si costruisce così la seguente funzione biett iva/tra i numeri natura-li e i numeri razionali positivi (cfr. ancora FIG. 2 7 B ) : / 1 ) = 1 / 1 = 1, / 2 ) = l/2,y(3) = 2 , / 4 ) = 3 , / 5 ) = 1/3 (infatti, dopo 3/1 si incontra, procedendo nel modo indicato, la frazione 2/2 che non viene consi-derata in quanto 2/2 = 1/1 e tale numero è già stato preso), / 6 ) = 1/4, / 7 ) = 2 / 3 , / 8 ) = 3/2,7(9) = 4 , / I O ) = 5 , / l 1) = 1/5 (in-fatti, dopo 5/1 si incontrano, nell'ordine, 4/2, che è stato già preso nella forma 2 / 1 , 3 / 3 che è stato già preso nella forma 1/1, e 2/4 che è stato preso nella forma 1/2) e così via. Con questo tipo di nume-razione ogni razionale positivo viene fatto corrispondere ad un nu-mero naturale. Infatti, mentre ciascuna riga (e ciascuna colonna) della matrice contiene infiniti elementi e quindi esaurirebbe da sola tutti i numeri naturali, ogni diagonale è finita e quindi, procedendo per diagonali, ogni punto della matrice è raggiungibile in un nume-ro finito di passi. Ottenuta così la funzione biet t iva/da Z + a Q + si estende tale funzione biettiva ponendo / 0 ) = 0 e passando da / w ) = q a / - « ) = —q. Questa estensione d i / è una funzione biettiva da Z a Q e quindi, per la ( i ) , Card{Z) = Card(Q). Nonostante queste impreviste possibilità di biezione, l'ipotesi che tutti gli insiemi infiniti siano biettivi tra loro è falsa. I draghi dun-que esistono, e a trovarli fu ancora Cantor. Il primo drago è costi-tuito dalla coppia di insiemi N e R, che soddisfano la (2):

FIGURA 27

Biettività tra N e Q+

1/1 1/2 1/3 1/4 1/5

2/1 2/2 2/3 2/4 2/5

3 / 1 3 / 2 3 / 3 3 / 4 3 / 5

4/1 4 / 2 4 / 3 4 / 4 4 / 5

5 / 1 5 / 2 5 / 3 5 / 4 5 / 5

(A) (B)

P R O P O S I Z I O N E 2.8. Card{N) < Card{R).

Dimostriamo dapprima che Card{N) < Card(B), dove B è il sot-toinsieme di R costituito da tutti i numeri reali compresi tra 0 e 1 le cui cifre sono soltanto 0 e 1 (ad esempio, 0,10001010110....). Nel caso in cui un numero di B sia un decimale finito, ad esempio 0,1101, lo si considera nella forma 0,1101000000000..., aggiun-gendo in coda un'infinità di 0. In questo modo ogni numero di B è rappresentato da uno 0 seguito da una virgola e da una sequenza in-finita di cifre. Negli esempi precedenti, dovendo dimostrare che due insiemi avevano la stessa cardinalità, è stato sufficiente esibire una funzione biettiva tra loro. In questo caso, invece, dovendo provare che N e B non sono biettivi, dobbiamo dimostrare che non può esi-stere alcuna biezione tra di essi. Procediamo per assurdo e supponia-mo che una funzione biettiva/da N a B esista. Essa allora può essere rappresentata nel modo seguente, dove ciascun a¿j è 0 o 1 :

/ i ) = 0, axx au2 a 13 alA ... ah„ ... / 2 ) = 0, ¿2,1 ¿2,2 ¿2,3 a2,4 ••• a2,n -

Ai) = °> aò,\ aò,2 ai,i aòA ^3,5 ••• ai,n ••• / 4 ) = 0 , &4t2 ^4,3 ^4,4 ^4,5 ••• ^4>n •••

j{n) = 0, an ì an 2 an ì an A anò ... a„ n ...

Poiché abbiamo supposto che/sia biettiva, ogni elemento di B deve comparire nel precedente elenco, deve cioè essere immagine, me-d i a n t e / di un naturale. Ma consideriamo il numero x e B così defi-nito: x = 0, bx b2 ¿3 ¿4 ••• bn ... dove, per ogni i, ^ ai it e cioè = 0 se at l = 1, e b{ = 1 se ata = 0. Ad esempio, se/iniziasse come in figura 28 allora, essendo ^1,1^2,2^3.3^4.4 = 0010, le prime quattro cifre deci-mali di x sarebbero 1101, cioè avremmo 0,1101... . Pur apparte-nendo a B,x non è immagine mediante / di alcun numero naturale, in quanto, essendo # al h x differisce d a / i ) per almeno la prima cifra decimale (bx ? a l y ì) , d a / 2 ) per almeno la seconda e, in gene-rale, d a / « ) per almeno l'«-esima cifra. Risulta quindi c h e / n o n è suriettiva, e dunque non è biettiva, contro quanto si era supposto. Non esiste così alcuna funzione biettiva da N a B. Per contro, è im-mediato costruire una funzione iniettiva da N a B. Basta porre, per

ogni n e N, g(n) = 0,11...110000000..., dove la parte decimale è composta da n cifre 1 seguite da infiniti 0. Pertanto, per la (2), Card{N) < Card(B) e quindi, essendo B c R, Card(N) < CardiR). Gli insiemi infiniti equinumerosi a N vengono detti numerabili. Poiché si può dimostrare che nessun insieme infinito ha cardinalità minore di N, ogni insieme infinito non equinumeroso ad N, quale è appunto R, sarà dunque più che numerabile. Il metodo impiegato nella dimostrazione precedente prende il nome di metodo di diagonalizzazione, per il fatto che le cifre ¿z,,, in-vertendo le quali x viene costruito, sono in "diagonale" (cfr. FIG. 28). Lo stesso metodo è alla base del seguente teorema:

P R O P O S I Z I O N E 2 . 9 . (Teorema di Cantor) Per ogni insieme A, Card(A) < Card{P[A)).

Il risultato vale per tutti gli insiemi, finiti e infiniti (è quindi una generalizzazione della Proposizione 2.1 di p. 38). Partendo da un in-sieme infinito, ad esempio N, e applicando reiteratamente il passag-gio all'insieme dei sottoinsiemi, otteniamo una successione infinita di insiemi infiniti a due da due non equinumerosi tra loro, e quindi una successione infinita di cardinalità differenti:

C W ( N ) < Card(P{N)) < Card(I\P{N))) < Card(P{P(P(N)))) < ...

L'aritmetica transfinita può dunque prendere avvio. Il passo successivo (il Passo 2 di p. 66) consiste nella scelta di insie-mi-tipo infiniti tali che ogni altro insieme infinito sia biettivo ad

FIGURA 28

Il metodo di diagonalizzazione

/(1) = 0,01100101001...

/( 2) = 0,10100000000...

/( 3) = 0,1 noi 110001... sulla diagonale: 0 010. . .

/(4) = 0,01100100100... x = o. 1 101...

uno di essi (i cardinali transfiniti). Questa scelta non può essere fat-ta adeguatamente nella teoria ingenua degli insiemi, quella cioè in cui il concetto di insieme e le sue proprietà fondamentali vengono lasciate all'intuizione, ma richiede la presenza di assiomi specifici. Ad esempio, la non esistenza di cardinalità intermedie tra Card{N) e Card(P{N)) non può essere né dimostrata né negata a partire dal-le "usuali" proprietà insiemistiche, per cui, se la si desidera, deve es-sere posta come assioma (prende il nome di ipotesi del continuo); più in generale, anche la non esistenza, quando A è infinito, di car-dinalità intermedie tra Card(A) e Card{P{A)) deve essere posta come assioma (prende il nome di ipotesi generalizzata del continuo). Accettando queste ipotesi, allora gli insiemi della precedente se-quenza possono rappresentare una buona scelta per gli insiemi-tipo infiniti. Tuttavia, ne costituiscono solo il tratto iniziale, poiché esi-stono insiemi la cui cardinalità è maggiore di quella di ciascun (P(P(P....P(N)))....). In questa corsa al sempre più grande, solo la presenza di un rigido sistema di assiomi può evitare che la teoria di-venti contraddittoria e crolli sotto il peso di gravi paradossi.

3. Strutture algebriche

Coloro che hanno familiarità con lo stato attuale della teoria dell'algebra simbolica,

sono consapevoli che la validità dei procedimenti dell'analisi non dipende dall'inter-

pretazione dei simboli che vi sono impiegati, ma soltanto dalle leggi che regolano la

loro combinazione. Ogni sistema di interpretazione che non modifichi la verità delle re-

lazioni che si suppone sussistano tra tali simboli è egualmente ammissibile, ed è cosi

che il medesimo processo può, secondo uno schema di interpretazione, rappresentare

la soluzione di una questione riguardante le proprietà dei numeri, secondo un altro

schema quella di un problema di geometria, e, secondo un altro ancora, quello di un

problema di dinamica o di ottica.

Questo passo, tratto daWAnalisi matematica della logica di George Boole (1815-1864), ben rappresenta lo spirito che anima Yalgebra astratta (o simbolica): concentrare l'attenzione non sul tipo di og-getti con cui ci si trova ad operare, ma sul modo in cui essi si rap-portano l'un l'altro. Nel corso del xix secolo emerge infatti la con-sapevolezza che ciò che è fondamentale, in una teoria matematica, non è tanto la natura degli enti che vi compaiono, quanto piuttosto le relazioni tra essi. Questo insieme di relazioni costituisce una sorta di telaio, di struttura, a cui gli oggetti si applicano. Può allora capi-tare di scoprire che enti molto diversi tra loro si strutturano allo stesso modo e possono essere studiati simultaneamente. Questo compito è svolto dall'algebra astratta, partendo proprio dal concet-to di struttura algebrica. Le modalità con cui tale prospettiva si è imposta, e i vantaggi che essa ha comportato, possono essere chiariti solo disponendo di un buon numero di esempi di strutture algebriche. Ed è ciò che ci ac-cingiamo a fare. Considereremo strutture di due tipi: i gruppi e le algebre di Boole. I primi costituiscono senza dubbio il più impor-tante esempio di struttura, oltre che il più antico. Nati in un conte-sto combinatorio ad opera di Evariste Galois (1811-1832), hanno progressivamente esteso la loro influenza in ogni angolo della mate-matica. Le seconde, che da Boole hanno preso il nome, non si sono rivelate altrettanto pervasive, e sono rimaste fortemente legate ai

due contesti nei quali hanno avuto origine: la teoria degli insiemi e la logica. Ma in questi ambiti hanno svolto un ruolo davvero de-terminante. Un'avvertenza preliminare. Nello studio delle strutture algebriche l'impiego delle variabili raggiunge livelli del tutto particolari. Ogni cosa, nella definizione di una struttura, è "qualunque": non solo gli oggetti dell'insieme ma anche le operazioni e le relazioni su di essi. Alcuni fastidi, per chi affronta questo studio per la prima volta, vengono dall'uso delle variabili per operazioni. Già da un punto di vista concettuale, l'idea di "generica operazione" non è familiare come invece lo sono quelle di "generico elemento" o di "generica funzione". Riguardo poi all'uso dei simboli, quello di operazione si trova, per tradizione consolidata, tra quelli degli operandi; per evi-tare di avere tre variabili letterali consecutive, tale simbolo non è in genere una lettera, bensì un carattere "aggiuntivo". Poiché i simboli tradizionali quali + , -, X sono impegnati su operazioni ben definite (la somma e il prodotto tra numeri), nel caso delle strutture in ge-nerale si cerca di ricorrere a caratteri nuovi, come *, ©, _L, o o. Spesso però, per ragioni di semplicità tipografica, si utilizzano an-che i simboli aritmetici + , -, X O i simboli logici A e v, con funzio-ne di variabile. Ciò comporta il rischio di trasferire inconsciamente ad un'operazione denotata, ad esempio, con il simbolo + , le pro-prietà della somma tra numeri. È invece importante, nell'affrontare lo studio di una struttura algebrica, comportarsi come una "tabula rasa". Bisogna cioè trattare ogni simbolo, vecchio o nuovo che sia, come se nascesse insieme alla definizione del tipo di struttura che lo coinvolge, e conseguentemente attribuire all'ente denotato da tale simbolo solo le proprietà che sono esplicitamente richieste.

3.1. Gruppi Sia X un insieme non vuoto e sia * una operazione binaria. La coppia (X,*) è un gruppo se soddisfa le seguenti condi-zioni G1-G4: Gì) se a e b appartengono a X allora anche a * b appartiene ad X (ciò equivale a chiedere che »sia un'operazione su A'nel senso defi-nito a p. 62. Questa condizione si esprime sinteticamente richie-dendo che A'sia chiuso rispetto all'operazione *); G2) l'operazione * è associativa;

G3) l'operazione * ha elemento neutro, cioè esiste un elemento e e X tale che, per ogni a e. X,a*e = aee*a = a-, G4) per ogni a e X esiste b e X tale che a * b = e e b * a = e. Tale elemento b viene detto inverso di a e, in genere, denotato con a1.

L'insieme X viene detto dominio o sostegno del gruppo; nel caso in cui sia finito, il numero dei suoi elementi viene detto ordine del gruppo. Spesso, al posto di "(X,*) è un gruppo" si usa più semplice-mente dire che "X è un gruppo rispetto a *" o anche, se è chiaro a quale operazione ci si sta riferendo, che "Xè un gruppo". Un gruppo si dice commutativo (o abeliano) se vale la seguente ulte-riore condizione: G5) l'operazione * è commutativa. In questo caso ciascuna delle due identità a*e = aee*a = a che compaiono in G3 implica l'altra, per cui è sufficiente verificarne una sola; lo stesso accade per le condizioni a*b = etb*a = e di G 4 .

3.1.1. Esempi di gruppi tra le classi numeriche Iniziamo con una serie di esempi di gruppi i cui elementi sono numeri. Questi gruppi, pur non essendo né quelli intorno ai quali il concetto si è formato, né quelli a cui sono legati i risultati più significativi della teoria, sono però i più semplici da descrivere.

E S E M P I O I G . La coppia (Z, +) , dove Z è l'insieme dei numeri interi e + è l'usuale somma su di essi, è un gruppo commutativo (o, come si dice più comunemente, Z ì un gruppo commutativo rispetto alla somma). Mostriamo che le condizioni G1-G5 sono soddisfatte. (Gì) Z è chiuso rispetto alla somma. Infatti la somma di due nume-ri interi è ancora un numero intero. (G2, G5) L'operazione di som-ma è associativa (per ogni a,b,c e Z, vale a + (b + c) = (a + b) + c) e commutativa (per ogni a,b e Z, a + b = b + a). (G3) Il numero 0 è l'elemento neutro, in quanto per ogni a e Z, vale a + 0 = a. (G4) Per ogni a e Z esiste un elemento b e Z che ne è l'elemento inver-so. Tale b è -a. Infatti a + (-a) = 0.

Il passaggio dalla definizione generale di gruppo a questo esempio particolare è dunque avvenuto in questo modo:

Il simbolo => rappresenta quell'"interpretazione" di cui parla Geor-ge Boole nel passo citato a p. 77; a sinistra compaiono simboli "astratti" che denotano enti generici, a destra compare la loro con-cretizzazione nello specifico esempio.

E S E M P I O 2 G . (Q, +) e (R, +) sono gruppi commutativi. La prova è come la precedente.

Invece, (N0, +) non è un gruppo, poiché viene meno la condizione G4. Preso un elemento a e N0 , se a è diverso da 0 allora non esiste b e N 0 tale che a + b = 0. Infatti, tale uguaglianza è soddisfatta solo se b = -a e, per a^0,-a non appartiene ad N0 . I prossimi esempi trattano ancora di classi numeriche, ma con rife-rimento all'operazione di prodotto. Accade però che nessuno degli insiemi Z, Q e R sia un gruppo rispetto a tale operazione. Il motivo è che l'unico elemento in grado di svolgere il ruolo di elemento neutro rispetto al prodotto è il numero 1; infatti, l'equazione a • x- ah soddisfatta per ogni a appartenente ad R (e quindi a Q e a Z) solo nel caso in cui x = \ . Ma, a questo punto, il numero 0, che appartiene a tutte le classi considerate, risulta privo di inverso, dal momento che non esiste in R (né quindi in Q o in Z) un elemento b tale che 0 • = 1. Pertanto, se si vogliono ottenere classi numeri-che che siano gruppi rispetto al prodotto, bisogna quantomeno pri-varle dello 0. Risulta allora che:

E S E M P I O 3 G . (Q-{0}, •) è un gruppo commutativo. Mostriamo che le condizioni G1-G5 sono soddisfatte. (Gì) Q—{0} è chiuso ri-spetto al prodotto, poiché il prodotto di due razionali non nulli è ancora un razionale non nullo. (G2 e G5) Il prodotto è associativo e commutativo. (G3) Il numero 1 è l'elemento neutro. Infatti, per ogni a e Q-{0}, a • 1 = a. (G4) Per ogni a e Q - { 0 } esiste un ele-mento b e Q - { 0 } che è l'inverso di a rispetto al prodotto. Tale elemento b è Ma. Infatti, essendo a ^ 0, l /a è un numero e

a • {Ma) = 1; inoltre, essendo a razionale, anche Mah razionale. Il seguente schema riassume il passaggio dalla definizione generale di gruppo all'esempio particolare:

Q-{0}

1

Ma

E S E M P I O 4 G . R - { 0 } è un gruppo rispetto al prodotto. Per la dimo-strazione è sufficiente sostituire R a Q nell'esempio precedente.

Invece, Z - { 0 } non è un gruppo rispetto al prodotto poiché non soddisfa G4. I soli elementi di Z che ammettono inverso (in Z) sono 1 e —1. Ogni altro numero intero a non lo ammette, in quanto Ma non è intero. Lo stesso accade per N.

3.1.2. Sottogruppi Sia (X, *) un gruppo e sia F c X. Se Kè ancora un gruppo rispetto all'operazione * (limitata agli elementi di Y) al-lora (Y,*) è sottogruppo di (X,*). Riferendoci ai gruppi fin qui incontrati, abbiamo che (Z, +) è sot-togruppo di (Q, +). Infatti Z C Q e la somma su Z è la stessa som-ma su Q ristretta a Z. Allo stesso modo (Z, +) e (Q, +) sono sotto-gruppi di (R, +). A sua volta (P, +) , dove P è l'insieme dei numeri interi pari (positivi e negativi) è un sottogruppo di (Z ,+) . Invece, l'insieme D dei numeri dispari non costituisce un sottogruppo di (Z, +) , in quanto non soddisfa né Gì (la somma di due dispari non è dispari, e quindi D non è chiuso rispetto alla somma) né G3 (lo 0, che è l'elemento neutro, non appartiene a D). Dato un qualunque gruppo X, l'insieme {e} costituito dal solo ele-mento neutro è sempre un sottogruppo, in quanto soddisfa G1-G4. E detto sottogruppo improprio. L'altro sottogruppo improprio di un gruppo è costituito dal gruppo stesso. Gli altri eventuali sottogrup-pi sono definiti propri. Tornando al caso di (Z ,+) , l'unico suo sottogruppo finito è il sot-togruppo improprio {0}, in quanto se un insieme F c Z contiene un elemento x ^ 0 allora, per soddisfare Gì, deve contenere x + x,

(x + x) + x, ((x + x) + x) +x, e così via all'infinito, e questi sono tutti elementi di Z distinti tra loro. Tra i sottogruppi infiniti di (Z, +) il ruolo principale lo hanno quelli i cui elementi sono tutti multipli, positivi e negativi, di uno stesso numero (il sottogruppo P è uno di questi, essendo costituito da tutti i multipli di 2). Consideriamo invece il gruppo moltiplicativo (R—{0}, •)• Ha sot-togruppi infiniti, quali Q-{0} , ma ha anche un sottogruppo finito proprio. Infatti l'insieme Y= {1 , -1} è un gruppo: è chiuso rispetto al prodotto, dal momento che (1 • 1) = ( -1 • - 1 ) = 1 e (1 • - 1 ) = ( -1 • 1) =—1, contiene l'elemento neutro 1, e ogni elemento am-mette inverso; anzi, ciascuno dei due elementi di Y è autoinverso, cioè inverso di se stesso.

3.1.3. Gruppi di permutazioni I primi insiemi su cui è stata ricono-sciuta la struttura di gruppo non sono stati insiemi di numeri, ma insiemi di funzioni.

E S E M P I O 5G. Siav4 un qualunque insieme non vuoto e sia 5 0 4 ) l'in-sieme di tutte le funzioni biettive da A ad A 5(v4) è un gruppo rispet-to all'operazione o di composizione di funzioni (cfr. p. 60), e prende il nome di gruppo simmetrico su A. Dimostriamo la validità di G1-G4, prestando attenzione al fatto che ci troviamo ad operare su due livelli: quello degli elementi dell'insieme S(A), che sono funzio-ni, e quello degli elementi dell'insieme A, che costituiscono il domi-nio di tali funzioni. (Gì) S e f g e S(A) a l l o r a / o g e S(A), in quanto è ancora una funzione biettiva da A ad A. Infatti, presi due elementi x,y e A, se x^y allora, essendo / biettiva, f(x) ^ f{y) e, essendo g biettiva, g(f(x)) ^ gif(y)), cioè (f og)(x) * (f °g)(y). Dunque anche f ogè biettiva. (G2) ((f °g) ° h) e ( / o (g o h)) fanno corrispondere a ciascun elemento x lo stesso elemento h(g(f(x))). Dunque sono uguali tra loro. (G3) La funzione identica su A, cioè la funzione i tale che i(x) =x per ogni x e A, è biettiva (quindi i e 504)) ed è l'ele-mento neutro rispetto alla composizione. Per ogni / e 5(v4) vale in-fatti che / o i =f e i ° / = / essendo, per ogni x e A, i(f(x)) =f(x) e f{i(x)) =f(x). (G4) Poiché ogni funzione /appar tenente a 5(^4) è biettiva, essa ammette funzione inversa/ - 1 (cfr. p. 6 0 ) . / - 1 è ancora una funzione dav4 ad^4, ed è biettiva; qu ind i / - 1 e 504). Inol t re , / - 1

è l'inversa di / anche nel senso della teoria dei gruppi, in quanto / o / - ' = i e / " 1 o / = i. Ciò si dimostra osservando che, per definizio-ne d i / - 1 , (f of~1)(x), cioè/_ 1 (/(*)), è uguale ad x. Ma anche i(x) = x. Per tan to /o / " ' = i. Lo stesso accade per / _ 1 o / Dunque, (5(^4), o ) è un gruppo, e l'interpretazione è stata la seguente:

X => * = > o

e => a - 1

= > / - 1

Contrariamente ai precedenti, questo esempio ci permette di otte-nere un'infinità di gruppi, uno per ogni insieme non vuoto A (a p. 99 compare la descrizione completa del gruppo nel caso in cui A ha tre elementi). La commutatività di tali gruppi dipende dalla cardi-nalità di A Nel caso banale in cui .<4 sia un insieme di uno o due ele-menti, 5(yl) è commutativo. Se invece A ha più di due elementi al-lora 5(.Ì4) è non commutativo. Infatti, se a,b,c sono tre distinti ele-menti dì A e / e g sono due funzioni di 5(^1) tali che:

j{a) = t> j{b) = c J{c) = a g(a) = b g(b) = a g(c) = c

allora a b b i a m o / g ° / in quanto ( / °g)(c) =g(f(c)) =g(a) = b mentre (g of)(c) = f(g(c)) = f(c) = a. Una biezione da A ad A può essere interpretata anche come un or-dinamento degli elementi di A, e ciò risulta chiaro se la rappresen-tiamo in forma tabulare. Ad esempio, dato l'insieme A = {a,b,c,d} e la biezione/tale e h e f ( a ) = b,f(b) = d,f(c) = a ef(d) = c, è possibile

scrivere/nella forma ^ ^ ponendo gli elementi di A

nella prima riga e ponendo sotto ciascun elemento x l'elemento f(x). Come si vede, la seconda riga della tabella indica un possibile riordinamento degli elementi di A. Ciascuno di questi ordinamenti è una permutazione su A che, una volta fissato l'ordine originario degli elementi — nel nostro caso a b c d — può essere rappresentata scrivendo soltanto la seconda riga della tabella - nel nostro caso b d

a c. 5(v4) può dunque essere inteso come il gruppo delle permutazio-ni di A. Se, come nel nostro esempio, A ha 4 elementi allora le per-mutazioni sono 24:

a b c d bacd

c a b d d a b c

a b d c bade c adb da c b

ac b d b cad c b ad db ac

a e d b b c da c b da db ca

a d b c b da c cda b de a b

ade b b d c a c d b a de b a

Il numero 24 è il fattoriale di 4, cioè il prodotto di 4 per tutti i nu-meri naturali che lo precedono (in simboli 4! = 4 • 3 • 2 • 1). Infatti, dovendo ordinare quattro elementi, abbiamo 4 possibilità di sce-gliere chi porre al primo posto (a,b,e oppure d). Una volta fissato il primo, abbiamo 3 possibilità di scegliere il secondo, e dunque ab-biamo 4 • 3 modi diversi di scegliere i primi due. Per ciascuna di queste scelte, abbiamo 2 possibilità di scegliere il terzo e, scelti i pri-mi tre, abbiamo un'unica scelta per il quarto. Complessivamente, dunque, vi sono 4 • 3 • 2 • 1 = 24 modi diversi di ordinare i quattro elementi di A. Allo stesso modo si dimostra che se A ha n elementi, allora il numero delle permutazioni su A, cioè il numero degli ele-menti di 504), è n\ = n • {n - 1) • (n - 2) • ... • 2 • 1. Il concetto di permutazione è presente in matematica fin dal xvi secolo, nell'ambito del calcolo delle probabilità. Ma l'esigenza di considerare tutte le permutazioni su un dato insieme e organizzar-le nel modo che poi sarebbe diventato quello di gruppo è emersa soltanto verso la fine del x v m secolo, in connessione con il pro-blema della risoluzione delle equazioni di grado superiore al 4°. Il legame tra i due ambiti è nascosto e complesso; lo descriviamo sol-tanto per sommi capi. Tutti ricordiamo che la formula risolutiva delle equazioni di 2° grado, cioè aventi la forma ax2 + bx + c = 0, è

-b± V b2 - 4ac x =

la

Si tratta di una soluzione "per radicali", nel senso che coinvolge, ol-tre alle quattro operazioni aritmetiche, solo l'operazione di radice. Nel xvi secolo furono scoperte le formule risolutive, sempre per ra-

dicali, delle equazioni di 3° e di 4° grado. Da allora, per duecento anni, i matematici hanno tentato invano di trovare formule analo-ghe per risolvere le equazioni di 5° grado. Nel 1770 Lagrange ipo-tizzò che il successo nella soluzione delle equazioni di 4° grado e gli insuccessi per le equazioni di 5° grado potessero trovare una spiega-zione nel diverso comportamento dei rispettivi insiemi di soluzioni rispetto alle permutazioni su di essi. Se indichiamo con x1,x2, x3, x4

le quattro soluzioni (radici) di una equazione di 4° grado, abbiamo che esistono espressioni algebriche di tali radici che, per qualcuna delle 24 possibili permutazioni dell ' insieme^ = {xltx2, x3, x4}, non cambiano di valore. Ad esempio, l'espressione X! • x2 + x3 • x4 non cambia di valore in seguito alla permutazione x4 x3 x, x2 in quanto, per la commutatività del prodotto e della somma tra numeri, Xi • x2 + x3 • x4 è uguale ax4 • x3 + xl • x2 (l'espressione cambia invece di valore in seguito alla permutazione x4 Xj x3 x2, essendo, in genera-le, xl • x2 + x3 • x4 ^ x4 • X! + x 3 • x2). I cambi di valore che tale espressione assume in seguito all'applicazione delle 24 permutazioni sono solo 3, e a ciò è legata la possibilità di risolvere un'equazione di 4° grado risolvendo preliminarmente opportune equazioni ausiliarie di 3° grado. A questo punto, se fosse possibile trovare un'opportuna espressione nelle 5 variabili xx, x2, x3, x4, x5 che, sottoposta alle 120 (=5!) permutazioni di tali variabili, cambiasse valore solo 3 o 4 vol-te, sarebbe anche possibile trovare il modo di risolvere una equazio-ne di 5° grado riconducendola a equazioni di 3° o 4° grado. Ma ciò non è possibile, e da questo consegue che le equazioni di grado uguale o maggiore al 5° non sono risolvibili per radicali. Una prima, parziale, dimostrazione fu trovata da Paolo Ruffìni ( 1 7 6 5 - 1 8 2 2 ) , ma il problema nella sua generalità venne affrontato da Augustin-Luis Cauchy ( 1 7 8 9 - 1 8 5 7 ) e da Galois. Fu quest'ultimo che per primo iso-lò il concetto di gruppo e ricondusse la risolvibilità per radicali di una qualunque equazione algebrica ad un problema relativo ad un certo gruppo di permutazioni delle sue radici. Da allora, tale gruppo è chiamato gruppo di Galois dell'equazione.

3.1.4. Classi di resto modulo n Un'importante famiglia di gruppi si ottiene dalle classi di resto modulo n, dove » è un numero naturale. Consideriamo dapprima come esempio il caso in cui n = 4 (la gene-

raJizzazione per un numero n qualunque è ovvia e immediata). Le classi di resto modulo 4 sono le seguenti:

[0]4 = { . . . -16 , -12 , -8 , -4 ,0 ,4 ,8 , 12, 16...} [1]4 = { . . . -15 , -11 , -7 , -3 ,1 ,5 ,9 ,13 ,17 . . . } [2]4 = { . . . -14 , -10 , -6 , -2 ,2 ,6 , 10, 14, 18...} [3]4 = { . . . -13 , -9 , -5 , -1 ,3 ,7 , 11, 15, 19...}

L'insieme di queste quattro classi viene denotato con Z4. Come si vede, la classe [0]4 è stata ottenuta partendo dallo 0 e sommando o sottraendo reiteratamente 4. Per cui [0]4 = { x e Z : x= 0 + k • 4, per k E Z}. Lo stesso accade per le altre classi, partendo rispettivamente da 1, 2 e 3. L'insieme Z4 = {[0]4, [1]4, [2]4, [3]4} costituisce una partizione di Z (cfr. p. 39), in quanto le classi sono a due a due di-sgiunte e la loro unione è uguale a Z. Se x è un numero naturale allo-ra, per comprendere a quale classe appartenga, è sufficiente dividere x per 4; il resto della divisione, che è un numero compreso tra 0 e 3, ci indica la classe di appartenenza. Questo spiega il nome "classi di resto". Ad esempio, per x= 127, abbiamo che 127 : 4 è uguale a 31 con il resto di 3, cioè 127 = 3 + 31 -4, per cui 127 e [3]4. A p. 54 abbiamo visto come ad ogni partizione corrisponda una re-lazione di equivalenza R che lega tra loro due elementi se e solo se essi appartengono alla stessa classe della partizione. Nel nostro caso, tale relazione R su Z viene indicata con =4, prende il nome di con-gruenza modulo 4 ed è esprimibile in questi termini:

x=4y sex-y = k • 4.

Infatti, x —y è un multiplo (positivo o negativo) di 4 se e solo se x e y appartengono alla stessa classe. Ora definiamo su Z4 un'operazione di somma, denominata somma modulo 4, che indichiamo con + 4:

[x]4 + 4 \y}4 è uguale alla classe di Z4 a cui appartiene x + y.

Ad esempio [3]4 + 4 [2]4 = [ 1 ]4 , dal momento che 3 + 2 = 5 e 5 e [1]4. La figura 29B contiene la "tabellina" completa di tale opera-

zione (la figura 29A mostra i criteri con cui si rappresenta la tabella di una generica operazione * su un generico insieme A). Abbiamo ora tutti gli ingredienti per definire un nuovo gruppo.

E S E M P I O 6G. (Z4, + 4 ) è un gruppo commutativo. (Gì) Alla somma di due elementi di Z4 corrisponde ancora un elemento di Z4 . (G2 e G5) L'operazione +4 è associativa e commutativa. Infatti ( M 4 + 4

[y]4) + 4 [z] 4 è, per definizione, la classe a cui appartiene (x+y) +z, mentre M4 + 4 ([y]4 + 4 [z]4) è la classe a cui appartiene x+ (y + z). Ma (x+_y) +z = (y + z) (qui si tratta dell'usuale somma tra nume-ri) e quindi i due risultati coincidono. Lo stesso accade per la com-mutatività. (G3) La classe [0]4 è l'elemento neutro. Infatti M4 + 4 [0]4 è la classe a cui appartiene x+ 0, cioè [x]4. (G4) Ogni elemento ha inverso. L'inverso di [x]4 è la classe a cui appartiene -x; come mo-stra la tabella di figura 29 gli inversi di [0]4, [1]4, [2]4 e sono ri-spettivamente[0]4, [3]4, [2]4 e [1]4. Ciò conclude la dimostrazione del fatto che (Z4, + 4) è un gruppo commutativo.

In modo del tutto analogo si dimostra che, per ogni numero natu-rale n,

E S E M P I O 7 G . (Z„, + „) è un gruppo commutativo, dove Z„ = {[0]„, [1 ]„, ...,[« - 1]„} è l'insieme delle classi di resto modulo n e l'opera-zione + „ è la somma modulo n.

FIGURA 29

(A) Rappresentazione di una generica operazione (B) La somma modulo 4

simbolo dell'operazione +« M, [l]t [2]t [3)4 C T Z r

[0], [o], [1], [2]t lì], [1]« [l]t [2]t [3)4 [<*)„ [2]4 [2], [3]« [0], [1], [3]« [3lt [0|4 [1], [2]t

(A) A

* • x*y

AV (B)

L'aritmetica che impiega Z„ viene chiamata aritmetica modulo n o, più generalmente, aritmetica modulare. Per la sua ciclicità, si com-porta come un'"aritmetica dell'orologio". Infatti se disponiamo gli elementi di Z„ in cerchio, come le ore su un quadrante di orologio, otteniamo un buon modello per tale aritmetica. Per sapere la classe di appartenenza di un qualunque numero x e Z è sufficiente parti-re da [0]„ e percorrere 1*1 passi, in senso orario se x è positivo, in senso antiorario se x è negativo; il punto di arresto è la classe a cui x appartiene. Per eseguire all'orologio la somma [*]„ + „ [y]„ si parte invece da [x]n e si percorrono y passi in senso orario (si ricordi che 0 < j / < « - l ) ; i l punto di arresto è la classe [z]n = [x]„ + „ \y]„

3.1.5. Gruppi di trasformazioni Descriviamo, dapprima in termini intuitivi, l'insieme MT dei movimenti che portano un triangolo equilatero a coincidere con se stesso. Supponiamo di avere un trian-golo equilatero di vertici a,b,c, costruito in materiale rigido, e di ap-poggiarlo su un piano. Indichiamo con 1, 2, 3 i punti del piano corrispondenti ad a,b,c. I movimenti che appartengono ad Mr sono quelli che fanno corrispondere i vertici del triangolo ai punti 1,2,3, e sono i sei rappresentati in figura 30. Partendo dalla posizione iniziale m0, che possiamo intendere come "movimento nullo", vediamo che mx e m2 corrispondono ad una rotazione in senso orario, rispettivamente di 120° e di 240°, mentre mò, m4 e m5 corrispondono a ribaltamenti lungo una delle tre biset-trici. Ciascuno di questi movimenti può essere ottenuto "fisica-mente" in infiniti modi. Ad esempio, mx può essere ottenuto, oltre che con una rotazione in senso orario di 120°, anche con una rota-zione oraria di 480° (= 120 + 360), oppure con una rotazione an-tioraria di 240° ecc. Dicendo che i movimenti di Mr sono sei abbia-mo di fatto identificato due movimenti fisici se essi producono lo stesso risultato, cioè la stessa corrispondenza tra a,b,c e 1,2,3. Defi-niamo ora un'operazione di composizione di movimenti, che indi-chiamo con il simbolo ©:

Dati due movimenti mi e mj, il movimento © m^ è quello che si ottiene partendo dalla posizione originaria (quella in cui a è in 1, b in 2 e c in 3) ed eseguendo prima m, e poi m-.

Ad esempio, m ì © m 2 = m0\ infatti compiendo prima una rotazione di 120° (mx) e poi una di 240° (m2), si compie una rotazione di 360°, e quindi i vertici ritornano nella posizione originaria m0. E ancora: m2

© m4 = mò\ infatti una rotazione in senso orario di 240° porta a in 3, b in 1 e c in 2, e il successivo ribaltamento lungo l'asse passante per 2 scambia tra loro i vertici in 1 e in 3, cioè b e a. Risultano così a in 1, b in 3 e c in 2, e questo è m}. In figura 30 è rappresentata la tabella del-l'operazione (le modalità di lettura sono descritte in figura 29A).

E S E M P I O 8 G . ( M t , ©), dove MT- {m0, ml, m2, mò, m4, m5} e © è l'operazione appena definita, è un gruppo. (Gì) Componendo due elementi di M T otteniamo ancora un elemento di M T , che dunque è chiuso rispetto a ©. (G2) L'operazione è associativa. (G3) Il mo-vimento nullo m0 è l'elemento neutro. (G4) Come mostra la tabel-la, ciascun elemento ha inverso. Abbiamo m{ 1 - m 2 e m 2

x = mx\ infatti, dopo aver compiuto una rotazione oraria di 120°, per torna-re alla posizione originaria m0 bisogna compiere un'ulteriore rota-zione di 240°. Invece i movimenti mò, m4 e m5 sono autoinversi, cioè ciascuno di loro è l'inverso di se stesso; compiendoli due volte si torna infatti nella posizione originaria m0. Infine (e questo vale in tutti i gruppi) anche l'elemento neutro m0 è autoinverso. Questo

FIGURA 30

I movimenti che portano un triangolo equilatero su se stesso

1 1 1

m0 m0 m1 m2 m^ m^ m ffi] m2 m0 m^ m* m

rr>2 ir>2 mo m5 m3 m

ffij mj w^ m4 m0 m2 m ni. m m m mi m0 m /rie m rr>7 "i, m.

®

<0

'0

gruppo non è commutativo: ad esempio, m 3 ® m4 = m2, mentre m4

© m} = mv

Nella precedente descrizione abbiamo potuto, grazie al supporto offertoci dalla figura geometrica, trattare il concetto di movimento in termini completamente intuitivi, muovendo solo il triangolo e lasciando fermo tutto il resto. Ma da Eulero (1707-1783) in poi, la matematica ha interpretato i movimenti come trasformazioni che riguardano l'intero piano o l'intero spazio e che fanno corrisponde-re ad ogni punto P un punto P'. Questa corrispondenza è descritta da opportune leggi, cioè funzioni. Alcuni insiemi significativi di trasformazioni sono gruppi rispetto alla composizione di movi-menti.

E S E M P I O 9 G . Iniziando da un caso semplice e riferendoci al piano, otteniamo un gruppo dall'insieme delle traslazioni. Una traslazione può essere descritta come un movimento rigido e privo di rotazioni del piano su se stesso. In termini di coordinate cartesiane, al generico punto P = (x,y) una traslazione fa corrispondere il punto P'= {x',y), dove x'=x + a e y =y+b, con a e b fissati numeri reali. Una traslazione T ha dun-que la seguente forma:

T: \x = x + a

j ' = y + b

E facile verificare che l'insieme delle traslazioni è un gruppo com-

mutativo. ( G l ) Se Tx è { y l * ^ e T2 è { y Z ^ g allora, appli-

candóle consecutivamente, abbiamo che il punto P = (x,y) viene spo-stato in P = ( ( x + ^ j + a2> (y-\-bx) + b2) che, per l'associatività della somma tra numeri reali, è uguale a (x+ia^+a^, y+(b¡ + b2)).

90

Pertanto Tl © T2 è ¿ 3 , con a3 = a, +a2 e b3 = bx + b2.

La composizione di traslazioni è dunque ancora una traslazione. (G2) L'operazione è associativa. (G3) Il movimento nullo, in cui x'=x e y'=y, è una traslazione (si ottiene ponendo a = 0 e b = 0). (G4) Il movimento inverso di una traslazione è ancora una trasla-zione; in fatti, se

{ x' = x~ a Í x' = x-f- ( a) y'=y+b ^ l o r a è \y' = y+{-b) • Infine- daila com"

mutatività della somma tra numeri reali segue che Tx © T2 = T2® e quindi il gruppo è commutativo.

E S E M P I O 1 0 G . Un altro gruppo di trasformazioni del piano è quel-lo delle dilatazioni. Una dilatazione può essere intesa immaginan-do di sottoporre un piano elastico, dotato di assi cartesiani, a due trazioni: una orizzontale che tenga fisso l'asse Ye una verticale che tenga fisso l'asse X (in tal modo, alla fine, l'unico punto che rima-ne fisso è l'origine). In termini algebrici, una dilatazione ha la se-guente forma:

I x' = k ' x

con k,h E R-{0} y = h • y

dove kb il fattore di dilatazione orizzontale e h quello verticale. La di-mostrazione che l'insieme delle dilatazioni costituisce un gruppo commutativo è analoga a quella fatta precedentemente per le trasla-zioni. In sintesi: la composizione di due dilatazioni Z), e D2 porta un punto P= (x,y) nel punto P'= ((kx • k2) • x, (A, • A2) •)>)•> ed è quindi ancora una dilatazione; il movimento nullo è una dilatazione, che si ottiene ponendo k = 1 e h = 1, e l'inversa di una dilatazione

\x'=k x . . \x' = -L-x < è la dilatazione < k

\y'=h • y \y'=-r-y h

Il gruppo delle dilatazioni ha importanti sottogruppi. Il più signifi-cativo è costituito dalle omotetie, che sono quelle dilatazioni in cui k = h, cioè in cui i fattori di dilatazione orizzontale e verticale coin-

cidono. Se k e h sono maggiori di 1, allora una omotetia costituisce ciò che in termini fotografici è un ingrandimento. Un altro importante sottogruppo, questa volta finito, del gruppo del-le dilatazioni è costituito dalle quattro dilatazioni in cui \k\ = \h\=\.

Ì x' = X \ x' = x \ x' = —X \ x' = —X

A: , D2: , Dy < , y = y [y = -y [y = y [ y = -y D0 è il movimento nullo, Dx è la simmetrìa rispetto all'asse Y, D2 la simmetria rispetto all'asse X e D} la simmetria rispetto all'origine. Queste quattro trasformazioni sono rappresentate in figura 31 (e, come detto, riguardano tutti i punti del piano; la presenza del poli-gono serve soltanto a mettere in evidenza l'effetto ottenuto). L'ope-razione di composizione sull'insieme S= {D0, D2, D}} è de-scritta dalla tabella, che mostra come S sia chiuso rispetto all'opera-zione. La presenza costante, sulla diagonale discendente, dell'ele-mento neutro D0 segnala che ogni elemento del gruppo è autoin-verso. Il fatto poi che la tabella sia simmetrica rispetto a tale diago-nale indica che il gruppo è commutativo.

FIGURA 3 1

Simmetrie

V Y

D = ] \ ' - - - '

X A

Dn

[ P D,

® D 0 D, d 2 d 3

D0 D 0 Di d 2 D,

Y Y D, D, D0 D, d 2

1 n r -| d 2

D3

d 2

DJ ° 3 d 2

D„

D,

D, D 0

X X

02

Il gruppo delle traslazioni e il gruppo delle dilatazioni (Esempi 9 e 10) sono tra loro inconfrontabili, nel senso che nessuno dei due è sottogruppo dell'altro. Entrambi però sono sottogruppi del seguen-te gruppo.

E S E M P I O I I G . Una trasformazione affine (o affinità) ha la forma

x' = a + kx + ty con a,b,k,r,t,h 6 R e k • h — t • r^ 0. y' = b + rx + hy

L'insieme delle trasformazioni affini è un gruppo rispetto all'usua-le composizione di movimenti. L'elemento che maggiormente dif-ferenzia queste trasformazioni rispetto alle traslazioni e alle dilata-zioni è che x'dipende non solo da x, ma anche d a y e, analogamen-te, y ' dipende non solo da y ma anche da x. La strana condizione k • h — t • r^ 0 serve a garantire il fatto che ogni trasformazione af-fine abbia la sua inversa (dimostrazione nei cui dettagli non entria-mo) e può essere espressa, nel linguaggio delle matrici, dicendo

che la matrice | jf ^ J ha determinante non nullo. Naturalmente,

il sottogruppo delle traslazioni si ottiene dal gruppo delle affinità ponendo k = h= 1 t t=r= 0, mentre quello delle dilatazioni si ot-tiene ponendo a=b = t=r=Qe.h,k^Q.

3.1.6. La teoria dei gruppi A questo punto possiamo, alla luce degli esempi fin qui proposti, fare qualche osservazione sullo spirito e su-gli scopi della teoria dei gruppi e dell'algebra astratta in generale. Come abbiamo visto, gli strumenti dell'algebra classica si erano ri-velati insufficienti per risolvere il problema della risoluzione delle equazioni algebriche di grado superiore al 4°, ed era stato necessario costruire strumenti più astratti (che poi diventarono i gruppi di permutazioni, cfr. PAR. 3.1.3). Analoga origine da problemi preesi-stenti hanno avuto i gruppi delle classi di resti (PAR. 3.1.4) e i gruppi di trasformazioni (PAR. 3.1.5). Noi, a posteriori, abbiamo usato il termine "gruppo" in ciascuno di questi contesti. Tuttavia non è stato facile accorgersi che questi contesti erano, per certi aspetti, si-mili tra loro e dunque potevano essere studiati da un'unica teoria

che si ponesse in modo trasversale rispetto alle tradizionali divisioni tra analisi, algebra, e geometria. La lentezza con cui ciò è avvenuto non è da attribuirsi tanto alla difficoltà di superare le barriere tra le varie discipline (la matematica c'è abituata da sempre), quanto alla difficoltà, nuova, di svincolare le teorie dai loro enti tradizionali (numeri, figure, funzioni ecc.) per concentrarsi solo sulle relazioni tra tali enti. La gradualità con cui il concetto generale di gruppo si è formato è testimoniata dal fatto che per un lungo periodo, dopo che i gruppi di permutazioni e i gruppi di trasformazioni erano stati studiati, nessuno si preoccupò di osservare che anche gli insiemi Z, Q, R erano gruppi rispetto alla somma, o che Q-{0}e R-{0} lo erano rispetto al prodotto (PAR. 3.1.1). Ma da quando, al termine del xix secolo, si è giunti finalmente alla definizione generale di gruppo, si sono aperte nuove prospettive. Studiando le proprietà che tutti i gruppi possiedono è possibile applicare tali proprietà ad ogni contesto in cui una struttura di gruppo è presente. E le "pro-prietà che tutti i gruppi possiedono" sono esattamente i teoremi del-la teoria dei gruppi, cioè quei risultati che derivano dall'impiego del-le condizioni G1-G4 nel ruolo di assiomi della teoria. Qui di seguito mostriamo tre semplici esempi. Del primo di essi diamo anche la dimostrazione, non tanto per l'interesse intrinseco dell'enunciato (davvero povero), ma per far vedere che cosa significhi una dimo-strazione in algebra astratta. Diversamente dalle usuali dimostrazio-ni aritmetiche o geometriche, in questo caso non parliamo di og-getti specifici e conosciuti (numeri, figure ecc.). Parliamo invece di oggetti completamente indefiniti, "qualunque". Ogni ausilio deri-vante da intuizioni legate ad una buona comprensione della natura degli oggetti trattati (intuizione numerica, intuizione geometrica ecc.), è qui precluso a priori. Gli unici appigli a cui è lecito aggrap-parsi, oltre alle regole universali della logica, sono gli assiomi G1-G4 della teoria. Tuttavia, man mano che si dimostrano teore-mi, essi possono essere impiegati per la dimostrazione di risultati ulteriori. Si viene così a formare un insieme di conoscenze che ge-nerano un nuovo tipo di intuizione, caratteristica dell'algebra astratta, i cui enti di riferimento sono le strutture stesse.

T E O R E M A i (Unicità dell'inverso). Sia (X,*) un gruppo. Allora un elemento non può avere più di un elemento inverso (ed è per que-sto motivo che, anticipando i tempi, abbiamo parlato fin dall'inizio ¿¿•//inverso di a e non di un inverso di a). Dimostrazione. Supponiamo che un elemento a di X abbia due in-versi b e c. Allora vale questa catena di uguaglianze (il secondo membro di ciascuna uguaglianza coincide con il primo della suc-cessiva):

b-b*e (perGj) b * e= b * (a * c) (per ipotesi, c è inverso di a, e dunque

a * c = e) b * {a * c) = (b * a) * c (per G2) (b*a)*c = e*c (per ipotesi, b è inverso di a, e dunque

b * a = e) e*c = c ( pe rGj ) .

A questo punto, per la transitività dell'uguaglianza, otteniamo b = c.

T E O R E M A 2 (Leggi di cancellazione). Sia (X,*) un gruppo. Per ogni a,b,c e A", da a * c = b * c (oppure da c * a = c * b) segue a = b.

T E O R E M A 3 (Esistenza ed unicità della soluzione delle equazioni di 1° grado) Sia (X,*) un gruppo. Per ogni a,b e X, l'equazione a * x = b ammette una e una sola soluzione, data da x = a * b~l .(Analoga-mente, b * a'1 è l'unica soluzione dell'equazione x * a = b).

Se riferiamo i risultati precedenti a gruppi quali (R, +) o ( R - { 0 ) , •)> cioè se pensiamo ad a,b,c come a numeri e all'operazione * come alla somma o al prodotto tra numeri, allora essi ci sembrano del tut-to banali. In effetti, è immediato rilevare che l'unica soluzione del-l'equazione a + x=b è x=b + (-a), o che l'unica soluzione di a • x= b è x= b • (1 la). Tuttavia, se ci riferiamo ad altri gruppi, allo-ra questi stessi teoremi, pur se molto semplici, diventano meno ovvi. Consideriamo ad esempio il gruppo (5(^4), o ) delle funzioni biettive da A ad A, con A = {a, b, c, d] (cfr. p. 82). Consideriamo poi le due seguenti funzioni f,g di S(v4):

~ I a b c d\ ( a b c d\ •\b d a c) Z:\b c d a)

Dal Teorema 3 veniamo a sapere che esiste una e una sola funzione

X e 504) tale c h e / ° X = £• Essa è X = / " ' ° S = [ d ì a t \

La non ovvietà di un simile risultato è testimoniata dal fatto che basta "spostarsi di poco" perché cessi di valere. Se invece di consi-derare l'insieme 5(^4) delle funzioni biettive consideriamo l'insie-me F(A) di tutte funzioni da A ad A, allora è possibile trovare equazioni / °X = <? P r i v e di soluzioni, e altre con più di una solu-zione. Ma ciò può accadere perché F(A) non è un gruppo. Ugual-mente non del tutto banale è il Teorema 3 se riferito a gruppi infi-niti di trasformazioni, quali quelli delle dilatazioni o delle affinità (Esempi 10 e 11); la conoscenza che acquisiamo è che, prese due dilatazioni o due trasformazioni affini qualunque, ne esiste una e una sola la quale, composta con la prima, dà come risultato la se-conda. I teoremi della teoria dei gruppi sono dunque quelle proprietà che, dimostrate una volta, valgono in tutti i gruppi. Ma tra due gruppi possono esistere gradi di parentela più forti rispetto a quel-lo di essere, appunto, entrambi gruppi. In questi casi le proprietà comuni aumentano, e aumentano le possibilità di passare da un contesto all'altro. Il grado di parentela più forte di tutti (tra quelli esprimibili in forma algebrica) è quello di isomorfismo. Nel para-grafo successivo lo definiremo relativamente ai gruppi, ma le os-servazioni che faremo possono essere estese a qualunque altro tipo di struttura algebrica. Poiché, come vedremo, l'isomorfismo rap-presenta l'identità strutturale, la comprensione di questo concetto si rivela un passo obbligato per ben comprendere il concetto di struttura algebrica.

3.1.7. Isomorfismi Due gruppi G^ = (Xlt *i) e G2 = (X2, *2) sono iso-morfi se esiste una funzione da Xy a X2 che soddisfa le seguenti condizioni:

(Isi) è biettiva; (Is2) <t>(a *! b) = O(a) *2 ®(b), per ogni a,b e Xv

Una tale funzione si chiama isomorfismo. La figura 32 esemplifica la condizione Is2. Il tratteggio grosso rappresenta il calcolo di <b(a *! b): prima si opera su a e b mediante *! e poi, mediante <5, si trasferisce il risultato nel secondo gruppo. Il tratteggio fine rappre-senta il calcolo di <J>(*z) *2 Q>(b)\ prima, mediante 3>, si trasferiscono a e b nel secondo gruppo e poi si opera con *2

s u l l e l ° r o immagini. Il fatto che le due procedure portino allo stesso punto rappresenta l'uguaglianza Is2. Un modo alternativo ma equivalente di rappresentare la condizione Is2 è il seguente:

(Is2') per ogni a,b e Xv a *! b = c s e e solo se

La forma Is2 è più utile dal punto di vista operativo; la forma Is2' mostra con più chiarezza la natura dell'isomorfismo, che può essere sintetizzata in questo modo: in un isomorfismo, se c'è corrispondenza tra gli operandi, c'è corrispondenza tra i risultati. Pertanto, anche se la natura degli elementi di due strutture isomorfe può essere profondamente diversa, il modo in cui questi elementi sono strutturati deve essere lo stesso. La relazione di isomorfismo

FIGURA 32

Isomorfismo tra due gruppi

0(a) *2 &(&) = <D(f).

X,

<D(o) \

- - • > : <tut] \

/ <!>( 0) *2 4»( ò) y <J>( 0 f»)

esprime dunque l'identità strutturale, e le proprietà invarianti per iso-morfismo prendono il nome di proprietà di struttura. Tali proprietà devono essere descrivibili riferendosi solamente al comportamento degli elementi rispetto alle operazioni. Ad esempio, la commutatività è una proprietà di struttura (riguarda l'esistenza o meno di due ele-menti a e b tali che a * b^ b * a), e dunque un gruppo non commu-tativo non può essere isomorfo ad uno commutativo. (Più dettaglia-tamente: se (A^,*,) non è commutativo allora esistono a e b tali che a*xb*b a. Quindi, essendo biettiva, b) ^ {b *, a) e, per Isz, <S>(d) *2 <&(£) * <&(£) *2 &(a). Ma <&(*) e <t>(b) appartengono aX2, che in tal modo non è commutativo). Pertanto, il gruppo com-mutativo Z 6 delle classi di resto modulo 6 (Esempio 7G) e il gruppo non commutativo MT dei movimenti del triangolo equilatero in se stesso (Esempio 8G) non possono essere isomorfi, nonostante abbia-no lo stesso numero di elementi e sia quindi possibile definire fun-zioni biettive tra loro. Anche la presenza o meno di elementi autoin-versi diversi dall'elemento neutro è una proprietà di struttura (è esprimibile con l'espressione "esiste a^e tale che a* a = e"). Per tale motivo il gruppo Z4 delle classi di resti modulo 4 (Esempio 6G) e il gruppo delle simmetrie S= {D0, DX, D2, D}} (cfr. p. 92) non posso-no essere isomorfi, nonostante abbiamo entrambi ordine 4: il primo non ha elementi autoinversi oltre all'elemento neutro, il secondo li ha (anzi, ogni suo elemento è autoinverso). Dopo questi casi negativi mostriamo ora alcuni esempi di isomorfismo.

E S E M P I O 11. Il primo esempio riguarda il gruppo (M^©) dei movi-menti di un triangolo equilatero in se stesso (Esempio 8G) e il gruppo (S(A), 0 ) delle permutazioni su un insieme A = {a, b, e} di 3 elementi (l'Esempio 5G descrive il caso generale). Si tratta di due strutture finite e quindi, essendo un isomorfismo una funzione biettiva, è necessario (ma, come abbiamo appena visto, non suffi-ciente) che i due gruppi abbiano lo stesso numero di elementi. Nel nostro caso, entrambi i gruppi hanno 6 elementi. Infatti gli elemen-ti di MT sono {m0, mx, m2, m3, m4, m5}, come descritto in figura 30, mentre S(y4) contiene le sei biezioni elencate qui sotto (per co-modità indichiamo la funzione identica i con f0):

e la b c\ r [a b c\ r I a b c\ o:U b c) h''\b c a) h:\c a b)

¿ • l a b e ] r [a b c\ £ [a b c\ h'-\a c b ) /¿[e b a) h:\b a c)

Le tabelle della composizione tra movimenti e quella della compo-sizione di funzioni sono riportate in figura 33. Come si può facil-mente verificare, la funzione O da MT a 5(^4) tale che è una funzione biettiva e converte la prima tabella nella seconda; le condizioni di isomorfismo sono dunque soddisfatte. Questo esempio ci fornisce un'efficace rappresentazione del signifi-cato di identità strutturale, che possiamo esprimere in questo modo: in due strutture isomorfe, le tabelle che descrivono le opera-zioni possono differire per i nomi che vi compaiono e per gli ogget-ti che trattano ma, tradotti i nomi, devono coincidere. Invece, il fatto che nella <t> del nostro esempio si corrispondano addirittura gli indici (®(wz0) =yò, $(#2,) =fx ecc.) è frutto della nostra particolare numerazione; con una numerazione diversa avremmo lo stesso avu-to un isomorfismo, anche se in forma meno palese. Sempre analizzando le tabelle di figura 33, vediamo che l'insieme {m0, mx, m2} costituisce un sottogruppo di M T . L'insieme è in-

FIGURA 33 Confronto di tabelle per stabilire un isomorfismo

+3 [0]3 [1]3 [2]j (Z, [o]3 [0]3 [l]j Uh WJ [1]3 Wj [0]3

m0 m1 m2\ m^ m^ w^ [2lj [2]j [0]3 [1]3 fo A h ' h u k © m0 m1 m2\ m^ m^ w^ e fo A h ' h u k

m0 m0 m1 m2\ ffij m^ m^ fo fo A h h h m, m2 m0 m^ m^ m^ A A h fo h h h m2 m2 ma ; m^ m^ m^ h h io A k h u m3 ffij mg m^ m0 m2 ml h h h u fo h A mX m^ ffjj m^ ffij m0 w2 U u h h A fo h m5 m^ m^ m^ m2 w^ ni0 h k u h A A fo

\Mt.®) (SIA).

fatti chiuso per l'operazione (delimitata dal tratteggio) e contiene l'elemento neutro e l'inverso di ogni suo elemento. Allo stesso modo, (O(w 0 ) , $>(mx), <S>(m2)}, cioè { f 0 , f x , f 2 } . è un sottogrup-po di S(v4) e i due sottogruppi sono isomorfi. Entrambi sono inol-tre isomorfi al gruppo Z3 delle classi di resto modulo 3. Questi isomorfismi hanno una giustificazione intuitiva. {m0, m l , m2} co-stituisce il gruppo delle rotazioni del triangolo, rispettivamente di 0, 120 e 240 gradi (i restanti movimenti m3, m4, m5 sono invece ribaltamenti). D'altro canto, come abbiamo visto, l'aritmetica modulo n può essere presentata come l'aritmetica dell'orologio e, nel caso di n = 3, gli scatti vanno di 120° in 120°. La composizio-ne di rotazioni del triangolo è quindi una simulazione della som-ma modulo 3; da qui l'isomorfismo di ({m0, mx, m2},©) con (Z3 ,+ 3). Ma gli stessi movimenti m0, mx, m2 possono essere de-scritti, oltre che in termini di rotazioni, anche come permutazioni di vertici, cioè come funzioni che a determinati vertici fanno cor-rispondere altri vertici — ad esempio, il movimento mx manda, nell'ordine, i vertici a,b,c al posto dei vertici b, c, a e può esser

descritto dalla funzione ^ ^J. Da qui l'isomorfismo di

({w0, mx, m2},@) con ({/ò./ ì»/}» ° )• Ancora una volta vediamo dunque che cosa siano due strutture isomorfe: interpretazioni di-verse di situazioni strutturalmente identiche.

E S E M P I O 21. Il gruppo (Z, + ) dei numeri interi rispetto alla somma e il gruppo (P, + ) dei numeri interi pari, sempre rispetto alla som-ma, sono isomorfi. Infatti la funzione O da Z a P definita da *&(*) = ix è un isomorfismo. Essa è biettiva e, per ogni x,y e. Z, vale Is2:

<&(* + y) = 2(x + y) = 2x + 2y = <D(x) + <D(y).

In questo esempio le operazioni e *2 sono indicate con lo stesso segno, essendo entrambe la somma tra interi. Inoltre, il gruppo

è sottogruppo di (Z, +). Nel paragrafo 2.8 abbiamo visto che, nel caso di insiemi infiniti, un insieme può essere posto in cor-

rispondenza biunivoca con un suo sottoinsieme proprio (e anzi, questa possibilità caratterizza e quindi può definire gli insiemi infi-niti). Ora vediamo che questa corrispondenza biunivoca può an-che, in presenza di operazioni, diventare un isomorfismo. L'esem-pio ci mostra infatti un caso di un gruppo isomorfo ad un suo sot-togruppo proprio. Aggiungiamo ancora un'osservazione di caratte-re generale. L'uguaglianza strutturale tra due strutture isomorfe vale limitatamente alle operazioni considerate nelle strutture stesse. Nel nostro caso, l'isomorfismo è tra Z e P intesi come gruppi ri-spetto alla somma. Se su tali insiemi consideriamo altre operazioni oltre alla somma, la precedente funzione non è tenuta a conser-varle; prendendo ad esempio il prodotto, abbiamo 0 (x • y) ^ O(x) • 0(y), poiché <D(x • y) = 2(x • y) = 2xy e O(x) • = 2x • 2y = 4xy.

L'ultimo esempio che presentiamo sembra, ad una prima impres-sione, contraddire alcune affermazioni fatte finora.

E S E M P I O 31. Il gruppo (R + , ) dei reali positivi rispetto al prodotto e il gruppo (R, +) dei reali rispetto alla somma sono isomorfi. L'iso-morfismo è dato dalla funzione <&(x) = log^x, qualunque sia la base logaritmica a che si considera. Infatti, il logaritmo è una funzione biettiva da R + ad R e, per ogni x,y e R + , vale Is2:

$ ( x - y ) = loga(x-y) = log^ + log^ = O(x) + O ^ ) .

Is2 esprime la proprietà fondamentale dei logaritmi, cioè la conver-sione del prodotto in somma; l'impiego dei logaritmi coincide dun-que con l'impiego di questo isomorfismo. Sembra però difficile ve-dere (R+ ,•) e (R, + ) come "diverse interpretazioni di una stessa si-tuazione strutturale", dal momento che le operazioni • e + appaio-no diverse proprio da un punto di vista strutturale. Il fatto è che la funzione che pone in corrispondenza R + con R non è né intuitiva né alla superficie delle cose. A parte questo, il prodotto di due nu-meri è simulato dalla somma tra i loro logaritmi allo stesso modo in cui, nell'Esempio li, la somma di due movimenti è simulata dalla composizione delle corrispondenti funzioni. Dunque, se questo esempio sembra in contrasto con gli altri è soltanto perché è più na-scosto. Per contro, la difficoltà nel calcolo dei logaritmi non è stata

senza compenso, visto che loro scoperta ha rappresentato un evento eccezionale nella storia della matematica. Una delle due operazioni in gioco, la somma, è infatti molto più semplice da eseguire rispetto all'altra, e per questo le tavole logaritmiche (e la loro "realizzazio-ne" in forma di regolo) sono state i più efficaci calcolatori prima del-l'avvento dell'elettronica.

3.2. Algebre di Boole Sia X u n insieme non vuoto, siano A e v due operazioni binarie e sia ' una funzione. La quadrupla (X , A, V, ') è un'algebra di Boole se soddisfa le seguenti condizioni: ABi) Xè chiuso per A, v e ' (cioè, se a,b e X, allora a A b, av b, d, b'eX). AB2) A, v sono operazioni associative e commutative. AB3) A,V sono l'una distributiva rispetto all'altra. AB4) Per ogni a,b e X, valgono a v (a A b) = a e a A (a v b) = a. Queste identità vengono dette leggi di assorbimento. AB5) A e v sono operazioni dotate di elemento neutro, rispettiva-mente indicati con 1 e 0. AB6) Per ogni a e X, valgono a/\a'= 0eav a' = 1. L'insieme Xviene detto dominio dell'algebra. Osserviamo che i sim-boli A e v sono impiegati in logica come connettivi proposizionali; qui invece indicano due generiche operazioni e sono denominati inf e sup. Inoltre, ci si riferisce con il termine di operazione anche alla funzione che abbiamo indicato con il simbolo '.

3.2.1. Campi di insiemi Gli esempi più immediati di algebre di Boo-le si ottengono prendendo come dominio un insieme di insiemi e come operazioni le operazioni booleane su di essi.

ESEMPIO IAB. Sia Uun insieme non vuoto e P{U) l'insieme di tutti i suoi sottoinsiemi. Secondo queste corrispondenze:

X => W ) A => n V => u ) => c

1 => U 0 => 0

risulta che (P{U), O, U , c ) è un' algebra di Boole. Mostriamo che le condizioni AB1-AB6 sono soddisfatte. (ABi) Intersezione, unione e complemento di sottoinsiemi di U sono ancora sottoinsiemi di U. Dunque P{U) è chiuso per tali operazioni. (AB2-3) Intersezione e unione sono associative e commutative, e sono una distributiva ri-spetto all'altra (cfr. p. 63). (AB4) Per ogni coppia di insiemi A,B vale A u (A n B) = A, dal momento che (A n B) c A, e vale anche A n (A u B) =A, essendo A c (A kj B). (AB5) L'elemento neutro dell'intersezione è U. Infatti ogni appartenente a P{U) È sottoin-sieme di U e quindi A C\U=A. Dall'identità A u 0 =A segue che 0 è l'elemento neutro dell'unione. Infine, (AB6) per ogni A e P(U), si ha A nAc = 0 e AuAc = U.

Per avere un'algebra di Boole non è necessario considerare tutti i sottoinsiemi di un dato insieme, come abbiamo fatto nell'esempio precedente. È anche possibile prenderne solo alcuni, purché l'insie-me di sottoinsiemi che si considera sia chiuso per le operazioni di intersezione, unione e complemento. Le algebre di Boole costituite da insiemi di sottoinsiemi di un certo insieme vengono dette campi di insiemi (nessun legame con la parola "campo" che, da sola, indi-ca un altro tipo di struttura algebrica, cfr. p. 118). Naturalmente, dato un insieme U, il più grande campo di insiemi su U è proprio P{U). Il più piccolo è invece costituito dai soli 0 ed U. È facile ve-rificare infatti che l'insieme {0,U} è chiuso per intersezione, unio-ne e complemento, e che ( { 0 , t / } , u , n , f ) è un'algebra di Boole.

3.2.2. Algebre di Boole in logica Nel paragrafo 2.3 abbiamo trattato del rapporto tra logica e insiemi, e in particolar modo del paralleli-smo tra le operazioni insiemistiche N , U e f e gli operatori logici A, v e —1. Alla luce di questo sembrerebbe plausibile, così come abbia-mo costruito algebre di Boole aventi per elementi degli insiemi e per operazioni n , u e c, costruire un'algebra di Boole avente per elementi formule proposizionali e per operazioni A, v e —1 (i simbo-li A e v indicano qui gli operatori logici). Ma non è precisamente così. Considerando con attenzione le corrispondenze analizzate nel paragrafo 2.3 si vede come a corrispondersi con le formule proposi-zionali non siano gli insiemi bensì le espressioni insiemistiche. Due

espressioni a e (3 insiemisticamente equivalenti, ad esempio A n B e (Ac U Bc)c, pur essendo diverse tra loro, denotano sempre lo stesso insieme e quindi lo stesso elemento di un campo di insiemi. Allo stesso modo, poiché il corrispondente logico dell'equivalenza insie-mistica è l'equivalenza logica, due formule diverse tra loro ma logi-camente equivalenti, come p A q e —1(—\p v —Iq), devono denotare lo stesso elemento della costituenda algebra. Tale elemento deve dunque essere il supporto comune a formule equivalenti tra loro, così come un determinato insieme lo è per le varie espressioni insie-mistiche che lo denotano. Una scelta potrebbe essere quella di prendere come elementi le colonne conclusive delle tavole di verità, che rappresentano, per definizione, ciò che hanno in comune for-mule equivalenti. Ma anche se questa strada è, con alcune cautele, perfettamente percorribile, si preferisce evitare l'intervento di enti estranei e prendere invece come elementi dell'algebra le classi di equivalenza formate dalle formule stesse. La procedura è standard in matematica (l'abbiamo già incontrata nel paragrafo 3.1.4 per le classi di resti modulo n). Poiché la relazione s di equivalenza logica è (ovviamente) una relazione di equivalenza, essa attua una parti-zione dell'insieme delle formule proposizionali in classi di equiva-lenza, ciascuna delle quali contiene tutte le formule equivalenti ad una formula data. Denotiamo con [(p]= la classe di equivalenza del-la formula cp. L'insieme F di tutte le classi di equivalenza (in simbo-li, F= {[(p]s : <P è una formula proposizionale}) è il dominio della costituenda algebra.

Come operazioni non possiamo prendere gli operatori logici A, v e —1, in quanto essi operano su formule e non su classi di formule. De-finiamo dunque tre nuove operazioni A , v e n nel modo seguente (si noti la completa analogia con il passaggio da + a + „ di p. 86):

[<p]= A [\|/]s = [9 A V|/L

[<p]= Y [ v L = [9 v v L

z i foL =[- .*] . .

E finalmente ESEMPIO 2AB. (F , A, V , = !) è un'algebra di Boole. La dimostrazione che le condizioni AB1-AB4 sono soddisfatte è di routine. Per soddi-

sfare AB5 dobbiamo individuare gli elementi neutri di A e v . Nel primo caso ci occorre una classe [\)/]= tale che, per ogni classe [cp]=, accada [cp]= A [\|/]s = [cp]=. Per come A è stata definita, ciò equivale a trovare un tipo di formula V|/ tale che, per ogni formula cp, valga cp A = cp. L'unico caso in cui, per ogni 9, il valore di verità di cp A V)/ è uguale a quello di cp è quello in cui ijf è vera per qualunque valore di verità attribuito alle sue variabili (in tal caso, infatti, se cp è vera allora cp A \j/ è vera e se cp è falsa allora cp A \|/ è falsa). Formule vy siffatte esistono e si chiamano tautologie-, l'esempio più semplice è costituito dalla formula p v —1p. L'elemento neutro di A è dunque [p v —i/>]= (si osservi che, essendo tutte le tautologie logicamente equivalenti tra loro, la classe non cambia se si sceglie una qualun-que altra tautologia). Analogamente, l'elemento neutro dell'opera-zione v deve essere costituito da una classe [v|/]= dove V|/ è un tipo di formula falsa per qualunque valore di verità attribuito alle sue varia-bili (in tal caso, infatti, se cp è vera allora cp v è vera e se cp è falsa allora cp v vj/ è falsa). Formule siffatte esistono e si chiamano con-traddizioni-, l'esempio più semplice è costituito dalla formula p A —1p. L'elemento neutro di v è dunque [p A —1/»]= (anche questa volta, essendo tutte le contraddizioni logicamente equivalenti tra loro, la classe non cambia anche se si sceglie una qualunque altra contraddizione). Pertanto, AB5 è soddisfatta. Infine, dal fatto che, per ogni cp, cp v —icp è una tautologia e cp A —iCp è una contraddizio-ne, segue che AB6 è soddisfatta. La seguente tabella interpretativa riassume quanto detto:

X A

V J

1 0

(ecco un caso in cui di fronte ai simboli è necessaria quella caute-la di cui abbiamo discusso a p. 78: mentre i simboli A, V nella co-lonna sinistra indicano le generiche operazioni booleane infe sup,

F A V

[p ^ p\ = [p A-i/>]5

gli stessi segni nella colonna destra, t r a p e —ip, indicano i connet-tivi logici). L'algebra di Boole (F, a , v, ^n) che abbiamo costruito è infinita: esistono infatti infinite formule a due a due non logicamente equi-valenti, e quindi infinite classi di equivalenza. Ma è possibile co-struire algebre di Boole finite i cui elementi siano ancora classi di formule. Ad esempio è sufficiente considerare, anziché l'intero in-sieme delle formule proposizionali, solo quelle in cui compaiono al più n diverse variabili. In questo caso, le classi di equivalenza di tali formule non sono più infinite ma sono 22 , e costituiscono ancora un'algebra di Boole rispetto alle operazioni A, V E N .

3.2.3. Isomorfismi Due algebre di Boole (A^, A 1 ; V „ e (X 2 , A2, v 2 , '2) sono isomorfe se esiste una funzione ® da X^ a X2 che soddi-sfa le seguenti condizioni:

O è biettiva; <5>{a A j b) = Q>{a) A2 <!>(£), per ogni a,b E <ì>(a v , b) = <$>(a) v 2 O(^), per ogni a,b e Xx\ OU' 1 ) = (O(d))'2, per ogni a s X v

Una tale funzione O si chiama isomorfismo. Valgono le osservazioni fatte riguardo all'isomorfismo tra gruppi (PAR. 3.1.7). In sintesi: due strutture isomorfe sono strutturalmente indistinguibili tra loro. Nel caso dei gruppi ciò riguardava la sola operazione *; nel caso delle al-gebre di Boole deve invece riguardare le tre operazioni A, v e '. Il seguente risultato esprime una proprietà che caratterizza fortemen-te questa classe di algebre.

P R O P O S I Z I O N E 3. 1 . Ogni algebra di Boole è isomorfa ad un campo di insiemi.

Dato che l'isomorfismo rappresenta l'identità strutturale, ciò signi-fica che le operazioni in una qualunque algebra di Boole si compor-tano esattamente come le operazioni n , U e c in un campo di insie-mi. In tal modo il legame tra logica e insiemi ne esce rafforzato, dal

momento che non possono esistere caratteristiche strutturali che siano peculiari delle algebre della logica. Risultati come la Proposizione 3.1 prendono il nome di Teoremi di rappresentazione. Il perché è chiaro: se ogni algebra di Boole è strut-turalmente identica ad un campo di insiemi, allora questi sono adatti a rappresentare l'intera classe delle algebre di Boole. La Pro-posizione 3.1 ha inoltre le seguenti conseguenze (non immediate), che riguardano specificamente le algebre di Boole finite:

P R O P O S I Z I O N E 3.2. Ogni algebra di Boole finita ha un numero di elementi pari ad una potenza di 2.

P R O P O S I Z I O N E 3.3. Due algebre di Boole finite aventi lo stesso nu-mero di elementi sono isomorfe tra loro.

Queste due proposizioni, insieme, ci dicono che, dato un qualun-que numero naturale n, se n non è una potenza di 2 allora non esi-ste alcuna algebra di Boole di n elementi, mentre se n è una potenza di 2 allora esiste, a meno di isomorfismo, una sola algebra di Boole con n elementi. Riscontriamo dunque una notevole carenza di va-rietà, specie se paragonata con quella dei gruppi. Chiaramente, a rendere le algebre di Boole così "rare" e cosi simili tra loro è il fatto che le operazioni coinvolte nella definizione sono ben tre, e regolate da assiomi molto forti. Ciò non significa che tutti gli esempi di al-gebre di Boole siano necessariamente confinati nell'ambito della lo-gica e della teoria degli insiemi. Significa però che i nuovi esempi non possono spingersi oltre un "cambio di veste".

E S E M P I O 3AB. Sia n un numero naturale nella cui scomposizione in fattori primi ogni fattore compare non più di una volta (ad esem-pio, n = 2 • 5 • 11 e non n = 2 • 5 • 5 • 11) e sia Dn l'insieme dei suoi divisori (compresi 1 ed « stesso). Con la seguente interpretazione

X => Dn A => M C D (massimo comun divisore) V => mcm (minimo comune multiplo)

> a => ni a 1 => n 0 => 1

otteniamo un'algebra di Boole. (Ecco un altro punto critico per la notazione: l'elemento neutro dell'operazione v, indicato generica-mente con il simbolo 0, è in questo esempio il numero 1. Il simbolo 1, con cui si indica l'elemento neutro dell'operazione A, corrispon-de invece al numero ri). Per la verifica delle condizioni AB1-AB6, ci limitiamo ad osservare che il M C D di due divisori di « è ancora un divisore di n, e lo stesso accade per il mcm. Inoltre se a è un divisore di n anche ni a lo è. In tal modo ABi è soddisfatta. La richiesta che n sia o primo o prodotto di numeri primi distinti serve per soddisfare la condizione a A a = 0 (AB6), che tradotta seguen-do la tabella precedente diventa MCD(<z, ni a) = 1. Questa identità può infatti essere falsificata se nella scomposizione in fattori primi di n compare più di una volta lo stesso fattore. Ad esempio, se « = 1 2 = 2 - 2 - 3 allora, prendendo a = 2, abbiamo a = 12/2 = 6 e a A = MCD(2,6) = 2 * 1. In questo esempio, la sensazione di essere davvero lontani dai cam-pi di insiemi è netta, ma fallace. Il campo di insiemi a cui quest'al-gebra è isomorfa (campo che, in base alla Proposizione 3.1, deve esi-stere) è (P{U), n , U, 0, dove Uè l'insieme {pi>p2>—>ps} dei fattori primi della scomposizione di n. La funzione <& di isomorfismo è quella che associa ad ogni sottoinsieme di U il prodotto dei suoi elementi (i quali sono numeri). Ad esempio, s e » = 1 1 0 = 2 - 5 - l l , allora U={2, 5, 11} e la corrispondenza <t> tra P{U) e Dn è la se-guente:

0 ( 2 } {5} {11} {2,5} {2,11} {5,11} {2,5,11} (elementi di P{U)

1 2 5 11 10 22 55 110 {elementi di DJ

Tralasciamo i dettagli della dimostrazione che O è un isomorfismo tra (P(U), o , u , f ) e (D„, MCD, mcm, ni a). Mostriamo solo, come esempio, che prendendo a = {2,5} e b = {5,11} abbiamo che la con-dizione $>(a AJ b)=<S>(a) A2 <&(£) diventa 0({2,5} N {5,11}) = MCD(<D({2,5}), <£({5,11})), ed è soddisfatta. Infatti ({2,5} n {5,11}) = <D({5}) = 5, e MCD(<D({2,5}), <D({5,11})) = MCD(10, 55) = 5. Del resto, se ricordiamo la definizione di M C D e mcm, non è poi così strano che tali operazioni vengano simulate da PI ed u . In-

fatti il M C D di a e b si ottiene "prendendo con il minimo esponente i fattori comuni di a e b", e ciò equivale (tenendo presente che nella scomposizione del nostro n ogni fattore compare una sola volta) a fare l'intersezione tra l'insieme dei fattori di a e quello dei fattori di b\ il mcm lo si ottiene invece "prendendo fattori comuni e non co-muni con il massimo esponente" e, in questo caso, equivale a fare l'unione dell'insieme dei fattori di a e quello dei fattori di b. In con-clusione, le algebre P(U) e Dn differiscono solo per il fatto che in un caso abbiamo l'indicazione dei fattori, nel secondo il prodotto ese-guito. Ma questo, riprendendo l'immagine precedente, è un partico-lare del vestito esterno dell'algebra, non della sua struttura, che è identica nei due casi.

4. Ritorno agli insiemi numerici

In queste pagine conclusive riprendiamo le classi numeriche del ca-pitolo 1, impiegando però i concetti acquisiti nei capitoli 2 e 3 per poterle trattare in modo più rigoroso e formale. Negli Elementi di Euclide i numeri sono rappresentati come segmen-ti. Da allora, e per duemila anni, è stato sulla geometria che si sono fondate tutte le discipline della matematica, aritmetica compresa. Tuttavia, a partire dal xix secolo, questo atteggiamento è cambiato in modo radicale e si è affermata l'idea che a fondamento della mate-matica non dovevano essere posti i concetti geometrici ma il concet-to di numero. Una prova del ruolo fondante assunto da questo con-cetto è che le varie scuole di filosofia della matematica (realismo, no-minalismo, intuizionismo, formalismo ecc.) si differenziano mag-giormente proprio nel modo in cui considerano i numeri. Una simi-le varietà di punti di vista non significa che vi siano definizioni di nu-mero matematicamente in conflitto tra loro: è un dato acquisito che la matematica non conosce questo tipo di conflitti. È vero però che nel definire le classi numeriche sono state seguite due vie le quali, seppur coerenti tra loro, sono profondamente diverse. La prima è ri-volta alla definizione diretta ed esplicita dei numeri in quanto oggetti singoli; la seconda è rivolta a definire assiomaticamente le classi nu-meriche come enti collettivi, dalle cui proprietà strutturali i singoli numeri ricevono una definizione indiretta ed implicita. La prima strada si svolge prevalentemente all'interno della teoria degli insiemi, ed è quella più in sintonia con le impostazioni filosofiche vicine al re-alismo; la seconda si svolge all'interno delle strutture algebriche, e ri-flette maggiormente un'impostazione di tipo formalistico. Le trattia-mo separatamente nei due paragrafi successivi.

4.1. La costruzione insiemistica dei numeri II punto di par-tenza nella costruzione insiemistica dei numeri è la definizione di nu-mero naturale. A p. 65 abbiamo, in via provvisoria, definito un nume-ro naturale, ad esempio il numero 4, identificandolo con un insieme di parole avente la forma {uno, due, tre, quattro}. Quella definizione

serviva solo a chiarire le caratteristiche del contare, che consistono nel collegare l'insieme di cui si vuole determinare la cardinalità con parti-colari insiemi-tipo (i numeri naturali con funzione cardinale). Come elementi di tali insiemi-tipo avremmo potuto scegliere oggetti qua-lunque, purché distinti tra loro (dal momento che in un insieme non è previsto considerare più volte lo stesso oggetto). Tuttavia, se si vuole procedere in modo rigoroso, non è opportuno ricorrere ad oggetti ex-tramatematici (e tanto meno a parole di una lingua nazionale), per-ché in questo modo la matematica si troverebbe a dipendere da qual-cosa che le è estraneo. Dovendo quindi rimanere nell'ambito degli oggetti matematici si incontra un problema. Se, con la teoria degli in-siemi, dobbiamo costruire prima i numeri e poi gli altri oggetti mate-matici, allora non abbiamo oggetti matematici preesistenti ai numeri. Per fortuna c'è un'eccezione. La teoria dispone infatti di un oggetto di sua esclusiva proprietà, nel senso che la sua esistenza non dipende da alcuna assunzione extramatematica: è l'insieme vuoto. Ad esso è assegnato un duplice compito: in quanto insieme, viene preso come insieme-tipo per rappresentare il numero 0 (dunque 0 = 0 ) ; in quanto possibile elemento (l'essere insieme o elemento non è una proprietà intrinseca, ma è dettata dal contesto) è impiegato per co-struire i numeri successivi. Il modo è il seguente. L'insieme-tipo per il numero 1, dovendo contenere un elemento, conterrà l'unico elemen-to di cui fino a questo punto disponiamo, che è lo 0 (cioè il 0 ) , e sarà dunque {0}; il numero 2, dovendo contenere due elementi distinti, conterrà i soli due elementi di cui, a questo nuovo punto, disponia-mo, lo 0 e l'I, e sarà quindi {0,{0}}; il numero 3 conterrà tre ele-menti, lo 0, l'I e il 2, e sarà {0,{0},{0,{0}}}, e cosi via per qualun-que numero n, che sarà definito come l'insieme di tutti i suoi prede-cessori. La seguente tabella riassume le definizioni date:

0 = 0 1 = {0} {0} 2 = {0,1} {0,{0}} 3 = {0,1,2} {0,{0},{0,{0}}} 4 = {0,1,2,3} {0,{0},{0,{0}},{0,{0},{0,{0}}}}

n {0,1,2,...,«-!} = {0 ,{0} , - . •••}}}}

112

Una simile costruzione, di primo acchito, può sembrare strana. Ma, se l'intento è quello di definire i numeri naturali e immergere l'aritmetica nella teoria degli insiemi, allora non sembrano esistere valide alternative. Inoltre, lo stupore non è del tutto imputabile al modo in cui la definizione si è sviluppata. Da sempre, i numeri na-turali sono serviti per definire ulteriori classi numeriche ma, come attesta l'aggettivo "naturali", non sono mai sembrati essi stessi biso-gnosi di definizione. Ciò che appare strano è dunque il fatto stesso di averli definiti, fondando il concetto di numero su qualcosa di an-cor più generale. Il passaggio dai numeri naturali agli altri tipi di numero avviene come descritto nel capitolo 1, salvo l'intervento di alcuni concetti insiemistici per rendere rigorosi quei punti che erano stati mag-giormente affidati all'intuizione. Nel definire i numeri razionali positivi espressi in forma frazionaria, abbiamo osservato come coppie diverse tra loro, ad esempio (4,3) e (8,6), indicassero lo stesso numero razionale (4/3 = 8/6). Ciò rendeva impossibile identificare un numero razionale positivo con una coppia ordina-ta di numeri naturali. Nel capitolo ì la difficoltà era stata superata stabilendo dapprima quando due coppie (a, b) e (a, b') denotano lo stesso numero razionale (il che accade quando a • b' = d • b) e poi ricorrendo all'artificio di dire che un numero razionale è "ciò che hanno in comune" tutte le coppie che lo denotano. Questo passaggio può essere salvato nella sostanza ma reso rigoroso nella forma impiegando i concetti di prodotto cartesiano, relazione di equivalenza e classe di equivalenza (cfr. PARR. 2.4 e 2 .5.2) . Si parte dal prodotto cartesiano NxN, su cui si definisce la seguente rela-zione R:

(a,b) R (d,b ' ) se a • b' = a • b

Essendo R una relazione di equivalenza, ciascuna classe [{a,b)\R

contiene tutte e sole le coppie che stanno tra loro nella relazione R (cioè, nella vecchia terminologia, le coppie che denotano lo stesso numero razionale) e l'insieme di tali classi di equivalenza è una par-tizione di N X N. A questo punto, un singolo numero razionale viene identificato con una classe di equivalenza e l'insieme Q + con

l'intera partizione (in simboli, Q + = (NxN)/./?). Pertanto, se nel-l'impostazione intuitiva un numero razionale poteva essere denotato da ciascuna delle coppie di una classe ma rimaneva un'entità a parte (peraltro non definita), ora un numero razionale è tale classe (si tratta di quel modo di procedere estensionale che abbiamo già in-contrato, ad esempio, nelle definizioni dei concetti di relazione e di funzione, cfr. PARR. 2.6 e 2.7). A questo punto, le operazioni tra i nuovi numeri si definiscono nel modo seguente, provvedendo an-che a dimostrare che il risultato non dipende dalle coppie scelte a rappresentare le classi:

[{a,b)]R + [{c,d)]R = [(,a-d + b-c, b-d)]R

[{a,b)]R- i(c,d)]R = [(a-c,b-d)]R

Ciò conclude la costruzione di Q + . Un procedimento simile può essere impiegato per passare da N 0 a Z, cioè per definire i numeri interi negativi. Nel paragrafo 1.2 ave-vamo creato ex novo un insieme infinito di nuovi numeri, indicato con Z". Si trattava semplicemente di una copia di N e, per distin-guere gli elementi appartenenti all'originale da quelli appartenenti alla copia, avevamo introdotto un segno (- ) da anteporre a questi ultimi. Già allora avevamo osservato che questo segno, nonostante coincidesse con quello impiegato per l'operazione di sottrazione tra numeri naturali e per la funzione di passaggio all'opposto, aveva un significato diverso. Funzioni e operazioni descrivono rapporti tra oggetti che già esistono, mentre quel segno, usato per differenziare le copie dagli originali, di fatto generava nuovi oggetti. L'idea che permette di superare questa anomalia è la seguente. Come i numeri razionali positivi hanno origine da una divisione tra naturali, così i numeri interi negativi hanno origine da una sottrazione tra natura-li. E come i primi sono stati identificati con le classi delle coppie di naturali che hanno lo stesso rapporto, così i secondi possono essere identificati con le classi delle coppie di naturali che hanno la stessa differenza. E ancora: nel caso dei razionali non abbiamo parlato di-rettamente di "stesso rapporto", in quanto ciò non può esser fatto prima di disporre dei numeri razionali; è stata invece trovata una relazione R che vale tra quelle coppie di numeri naturali dei quali, a

posteriori, possiamo dire che hanno lo stesso rapporto. Lo stesso dobbiamo fare ora: trovare una nuova relazione S che vale tra quelle coppie di naturali dei quali, a posteriori, possiamo dire che hanno la stessa differenza. La relazione è questa (ed è ottenuta da R semplice-mente scambiando il • con il + ):

{a,b) S (a,b') se a + b' = a + b.

Anche S è una relazione di equivalenza, e quindi si può parlare di classi di equivalenza. Ad esempio, la coppia (6,4) sta nella relazione S con le coppie (7,5), (8,6), (5,3) ecc. Come si vede, sono tutte e sole le coppie (a,b) tali che a — b = 2, per cui si può assumere che la classe [(6,4)]5 rappresenti il numero 2. In questo caso, essendo 2 ancora un numero naturale, avremmo potuto caratterizzare la classe richiedendo direttamente a — b = 2. Ma consideriamo la coppia (4,6). La classe [(4,6)]5 contiene le coppie (5,7), (6,8), (3,5) ecc. Se già disponessimo del numero negativo - 2 , potremmo dire che [(4,6)]^ contiene tutte e sole le coppie (a,b) tali che a - b = —2. Ma non possiamo farlo. Possiamo invece definire il numero - 2 median-te tale classe. In generale, quindi, un singolo numero intero viene identificato con una classe di equivalenza di S, e l'insieme Z viene identificato con l'insieme di tutte queste classi di equivalenza, cioè con la partizione indotta da S su N 0 x N 0 (in simboli: Z = (N 0 xN 0 ) /5) . Le nuove operazioni di somma e prodotto tra i nume-ri interi sono così definite:

[{a,b)}s + [(,c,d)}s = [(a + c,b + d)]s

[{a,b)]s- [(c,d)]s = [{a-c + b-d, a-d + b-c\s

Mostriamo un esempio di prodotto: [(6,4)]5 • [(2,7)]s = [(6-2 + 4-7, 6-7 + 4-2}s = [(40,50)]5. In effetti, le classi [(6,4)]5, [(2,7)]5

e [(40,50)]5 definiscono rispettivamente i numeri 2 (cioè 6 - 4), - 5 (cioè 2 - 7) e - 1 0 (cioè 40 - 50); vediamo così che 2 • - 5 = - 1 0 . Ciò conclude la costruzione di Z. Il passaggio dai numeri razionali ai numeri reali è più complesso: lo è stato da un punto di vista intuitivo (cfr. PAR. 1.5) e lo è anche da

un punto di vista rigoroso. Si impiegano ancora relazioni e classi di equivalenza, ma non più coppie ordinate e prodotti cartesiani. In-fatti la relazione da cui scaturiscono i numeri reali non si applica a coppie di numeri (come nei passaggi da N a Q + e da N a Z) ma a successioni infinite di numeri. Nel paragrafo 1.5.2 abbiamo visto in termini intuitivi come un numero reale possa essere identificato da una successione di numeri razionali; ad esempio, la successione 1, 1.4, 1.41, 1.414, 1.415, ... identifica il (converge al) numero reale irrazionale V2. Se indichiamo con su s2> s3, ... gli elementi della suc-cessione e con (sn) l'intera successione (intendendo che n percorra tutti i numeri naturali), allora il fatto che una successione converga ad un certo numero a viene espresso dalla ben nota definizione di limite: (s ) è una successione convergente ad a (in simboli lim s„ = a)

n—>00

se per ogni numero reale e ("piccolo a piacere") esiste un numero naturale m tale che, per ogni n>m, Isn - al < e. La definizione di successione convergente non può essere impie-gata per definire i numeri reali, in quanto in essa intervengono già numeri reali che possono non esser razionali: a ed e. La presenza di e non crea difficoltà: dato che per ogni numero reale esiste sempre un numero razionale minore di lui, la definizione rimane equivalente se si richiede che e sia un numero razionale. Ma, per quanto riguarda a, visto che è ciò che dobbiamo definire, non possiamo certo farlo intervenire nella definizione stessa. E però possibile stabilire la convergenza di una successione di numeri razionali senza fare intervenire nella definizione il punto a cui converge. Si tratta della definizione di successione di Cauchy (o suc-cessione fondamentale)-, la successione (s„) è di Cauchy se per ogni numero razionale e esiste un numero naturale m tale che, per ogni n > m c t > m,\sn - st\ < Come si vede, questa definizione rimane interamente nell'ambito dei numeri razionali. Se già disponessimo dei numeri reali po-tremmo dimostrare che, in R, una successione è convergente se e solo se è di Cauchy. Ma non li abbiamo ancora, e ciò che possia-mo fare è definire i numeri reali mediante le successioni razionali di Cauchy. Sull'insieme di tali successioni si stabilisce una relazio-ne di equivalenza T che (a posteriori) lega due successioni (sn) e

(s'„) quando individuano lo stesso reale. La definizione, che fa ri-ferimento solo a numeri razionali, è : (s„) T (s'n) se per ogni nu-mero razionale e esiste un numero naturale m tale che, per ogni n>m, \ s„ - ì'„I <e. Infine, un singolo numero reale è definito come la classe di equivalenza di una successione di Cauchy di razionali (in sim-boli [(*„)] r)> e l'insieme dei numeri reali come l'insieme di que-ste classi. A questo punto, i numeri reali sono stati definiti in termini di nu-meri razionali, questi in termini di numeri interi, e questi ultimi in termini di numeri naturali. Ogni numero reale è dunque rap-presentabile mediante una lunga espressione che vede coinvolti solo numeri naturali. Poiché i numeri reali sono lo strumento del-l'analisi matematica e i numeri naturali quello dell'aritmetica, il processo di riduzione dei reali ai naturali è stato chiamato aritme-tizzazione dell'analisi. Ma, a loro volta, i numeri naturali sono sta-ti definiti all'interno della teoria degli insiemi basandosi solo sul-l'insieme vuoto. L'espressione "fondare tutto sul nulla" è dunque qui vera alla lettera e, quel che più conta, non è impiegata per smascherare un'illusione ma per sintetizzare una significativa con-quista teorica.

4.2. Le classi numeriche come strutture algebriche In questo secondo modo di definire le classi numeriche non è più ne-cessario seguire un percorso prestabilito, in cui ogni nuova classe si basa sulla precedente e la estende, ma è possibile introdurre ciascu-na classe indipendentemente dalle altre. Per comprendere l'idea di base ricordiamo come, nel capitolo 3, sia emersa la "maggiore va-rietà" dei gruppi rispetto alle algebre di Boole. Ne abbiamo anche, e facilmente, trovato la causa: tanto più forti sono gli assiomi (le condizioni) che definiscono un tipo di struttura, quanto più rare saranno le strutture che li soddisfano. Per caratterizzare una singo-la struttura (nel nostro caso una classe numerica) si può dunque provare a spingere all'estremo questo processo di rarefazione. Ciò si può fare partendo da una base di assiomi che, ovviamente, siano veri nella struttura stessa, aggiungendone via via dei nuovi. Se si

riesce a raggiungere un punto in cui, a meno di isomorfismo, la no-stra struttura sia l'unica a soddisfarli tutti, allora questi assiomi la caratterizzano completamente e definiscono, in modo indiretto, gli oggetti (nel nostro casi i numeri) che le appartengono. In ter-mini un po' grossolani, questa strategia accetta che ciascuno di noi immagini di costruire il modello di una data classe numerica come meglio preferisce, purché ciò avvenga nel rispetto di determinate condizioni; la ragione di tanta tolleranza è che, se ciò accade, le eventuali differenze tra un modello e l'altro non hanno rilievo ma-tematico. Vediamo nei dettagli l'esempio di R. Sappiamo (cfr. pp. 80-1 e 63) che (R, + ) è un gruppo commutativo, (R — {0}, •) è un gruppo commutativo, e il prodotto è distributivo rispetto alla somma. Si definisce allora un nuovo tipo di struttura con due operazioni, che per comodità continuiamo a indicare con + e • , anche se qui han-no valore di variabili. • La struttura (X, +, •) è un campo (nessun legame, tranne l'o-monimia, con i campi di insiemi introdotti a p. 102) se: Ci) (X, + ) è un gruppo commutativo; C2) (X - {e0}, •) è un gruppo commutativo, dove e0 è l'elemento neutro dell'operazione + . C3) Per ogni a,b,c e X, vale a • {b + e) = (a • b) + {a • c). Quella di campo è un tipo di struttura di grandissimo interesse (in-sieme a quella di gruppo e quella di anelb, intermedia tra le due, costituisce il nucleo dell'algebra astratta) ma, per quanto riguarda il nostro obiettivo, certamente (R, + , •) non è, a meno di isomorfi-smo, l'unico campo esistente. Vi è anche (Q, + , •)> che non può es-sere isomorfo ad R in quanto di diversa cardinalità (cfr. PAR. 2.8.4), vi sono le strutture finite (Z„, + •„) quando « è un numero primo (il prodotto •„ è definito in modo analogo alla somma + „, cfr. p. 86), e infiniti altri esempi. Se vogliamo isolare R dobbiamo allora aggiungere ulteriori condizioni, facendo intervenire le proprietà della relazione <, di cui R è dotato. Si perviene in tal modo al con-cetto di campo ordinato (dove il simbolo < indica una qualunque relazione d'ordine).

• La struttura (X, + , - , < ) è un campo ordinato se (X, + , •) è un campo e: 01) la relazione < è di ordine totale su X; 0 2 ) per ogni a,b,c e X, se a < b allora a + c < b + c; 03) per ogni a,b,c e X, se a < b e e0 < c allora a • c < b • c.

Molti campi non ammettono una relazione su di essi che li ren-da campi ordinati (ad esempio, i campi finiti Z„). La schiera dei campi ordinati è dunque ben più ridotta di quella di tutti i campi. Tuttavia R non è ancora, a meno di isomorfismo, l'uni-co campo ordinato. Lo è anche, tra gli altri, Q. Nel paragrafo 1.4.1 abbiamo rilevato, in termini intuitivi, che la principale dif-ferenza tra Q ed R risiede nel fatto che se si pongono in corri-spondenza i numeri con i punti della retta, vi sono punti che rimangono senza numero razionale corrispondente, mentre ciò non accade se si passa ai numeri reali. Ora però non possiamo più appoggiarci all'immagine geometrica, e la differenza tra Q e R deve poter essere espressa in termini puramente algebrici. A ciò provvede il concetto di sezione, introdotto da Dedekind ver-so la fine dell'Ottocento. Dato un insieme X totalmente ordina-to dalla relazione <, diciamo che la coppia (A,B) di sottoinsiemi non vuoti di X è una sezione, o taglio, di X se soddisfa queste condizioni: {\) A C\ B = 0, (2) se x e A e y e B allora x < y, (3) A u B = X. Gli insiemi A e B vengono detti rispettivamente sezione inferiore e sezione superiore. Questo concetto permette di differenziare R da Q. Infatti è possibile attuare delle sezioni (A,B) di Q senza che A abbia un elemento massimo e B un elemento minimo, mentre ciò non è possibile in R. Ad esempio, sia A = {x e Q: * < V2} e B = {x e Q: x > V2}. I due sottoinsiemi A e B sono disgiunti, ogni elemento di A è minore di ogni elemento di B, e A u B = Q (dal momento che V2, che sarebbe l'unico escluso, non è un elemento di Q). Dunque (A,B) è una sezione di Q, e inoltre la sezione inferiore A non ha massimo elemento (non esiste il massimo razionale minore di V2) e la sezione superiore B non ha minimo elemento (non esi-ste il minimo razionale maggiore di <2). Per contro, la coppia di insiemi A = {x e R: x < V2} e B = {x e R: x > V2} non

costituisce una sezione di R, dal momento che V2 appartiene ad R ma non appartiene né ad A né a B. Deve quindi essere ag-giunto ad uno di essi. Ma se lo aggiungiamo ad A allora A viene a possedere elemento massimo (appunto V2), mentre se lo ag-giungiamo a B allora B avrà elemento minimo (sempre V2). De-finiamo dunque questo ulteriore tipo di struttura algebrica. • La struttura (X, + , - , < ) è un campo ordinato continuo se è un campo ordinato e soddisfa la seguente condizione: O4) la relazione < è un ordine denso, senza primo né ultimo ele-mento, e per ogni sezione (A,B) di X, A ha massimo elemento op-pure B ha minimo elemento.

Finalmente R è, a meno di isomorfismo, l'unico campo ordinato continuo. Le condizioni C1-C3 e O1-O4 costituiscono dunque quello che si chiama un sistema di assiomi per i numeri reali. I risultati descritti in questo e nel precedente paragrafo sono stati coinvolti nella disputa filosofica intorno ai fondamenti della ma-tematica. Ciò è accaduto per il semplice motivo che essi costitui-scono delle risposte ad una domanda che di certo la filosofia della matematica non può eludere: che cosa sono i numeri? Nel para-grafo precedente abbiamo spiegato che cosa è un numero co-struendolo passo passo. Una risposta di questo tipo è senz'altro la più soddisfacente per chi rivolge il suo interesse agli oggetti della matematica intesi come enti astratti ma reali. Consideriamo inve-ce una risposta, come quella descritta in questo paragrafo, che si limita ad elencare una serie di proprietà generali relative ad opera-zioni e relazioni, lasciando che qualunque insieme che le soddisfa vada bene per essere l'insieme dei numeri reali. Una simile rispo-sta lascerà forse insoddisfatto chi vuole sapere che oggetto sia un numero reale, ma soddisferà chi concepisce la matematica come studio delle relazioni. Tuttavia, come abbiamo detto all'inizio del capitolo, questi due modi di definire le classi numeriche, anche se sono stati fatti propri da correnti filosofiche antagoniste, non sono, da un punto di vista matematico, né in conflitto né in concorrenza. Per un verso, l'insie-me dei numeri reali insiemisticamente definiti soddisfa tutti gli as-siomi di campo ordinato completo, e costituisce così una prova del-

la coerenza di tale sistema (i sistemi contraddittori sono infatti privi di modelli). Nel verso opposto, il sistema di assiomi dei numeri rea-li rappresenta una sintesi delle proprietà di cui i numeri reali (insie-misticamente definiti) godono, ed è quindi una base per produrre le dimostrazioni che li riguardano. Si tratta dunque di due costru-zioni che, dal punto di vista matematico, sono complementari e che, insieme, fondano in modo rigoroso le classi numeriche e la matematica che su di esse si basa.

Indice analitico e dei nomi

affinità, 93

algebra di Boole, 102

antiperiodo, 16

Aristotele, 34, 69

aritmetica modulare, 88

aritmetica modulo n, 88

aritmetizzazione, 23, 1 17

biezione, 59

Boole G . , 77, 80

campo, 118

ordinato, 119

ordinato continuo, 120

campo di insiemi, 102

Cantor G. , 22, 30, 35, 71-2, 74

cardinalità, 8

Cartesio, 29

Cauchy A. L., 85, 116

classe

di equivalenza, 55

di resto modulo n, 86-7

codominio, 58

coefficiente angolare, 30

commensurabili (grandezze), 23

complemento, 40

completezza, 23

composizione

di funzioni, 60

di movimenti, 88

congiunzione, 46

congruenza modulo n, 86

connettivo logico, 46

contraddizione, 105

coppia ordinata, 50

corrispondenza biunivoca, 59

Dedekind R., 35, 119

denominatore, 17, 21

diagonalizzazione (metodo di), 74

diagramma

cartesiano, 51

di Hasse, 56

di Venn, 38

sagittale, 60

differenza, 42

differenza simmetrica, 42

dilatazione, 91

disgiunzione, 46

dividendo, 9

divisione

con la virgola, 15

euclidea, 15

tra numeri naturali, 8

tra numeri razionali, 17

tra numeri reali, 28

divisore, 9

dominio

di un gruppo, 79

di una funzione, 58

doppia implicazione, 49

elemento autoinverso, 82

equivalenza

insiemistica, 44

logica, 47

espressione

booleana, 41

insiemistica, 41

Euclide, 34-5, 111

fattoriale, 84

Fermar P. de, 29

formula proposizionale, 47

funzione, 57

biettiva, 59

identica, 82

iniettiva, 59

inversa, 60

opposto, 12

suriettiva, 59

Galilei G. , 68

Galois E., 77, 85

grafico cartesiano, 53

gruppo, 78

abeliano, 79

commutativo, 79

delle permutazioni, 84

di Galois, 85

simmetrico, 82

Hilbert D „ 66

identità insiemistica, 42

identità valida, 42

implicazione, 49

inclusione, 38

inclusione stretta, 38

incommensurabili (grandezze), 23

infinito

attuale, 33

potenziale, 33

insieme

complementare, 40

numerabile, 74

più che numerabile, 74

universo, 40

vuoto, 37

insiemi disgiunti, 39

intersezione, 38

inverso, 79

isomorfismo

di algebre di Boole, 106

di gruppi, 96

leggi di assorbimento, 102

negazione, 46

numeratore, 17, 21

numero

decimale, 14

decimale finito, 15

decimale periodico, 16

frazionario, 15

intero,11

irrazionale, 23

naturale, 7

negativo, 11

positivo, 11

razionale, 14

reale, 24

omotetia, 91

operatore logico, 46

operazione

associativa, 62

binaria, 62

booleana, 41

booleanamente esprimibile, 42

commutativa, 62

distributiva, 63

ordine, cfr. relazione d'ordine

parte intera, 16

partizione, 39

periodo, 16

permutazione, 83

Principio di comprensione, 37

prodotto

cartesiano, 50

tra numeri interi, 14




proprietà di struttura, 98

quoziente, 9

rappresentazione

cartesiana, 53, 58

reciproco, 19

relazione, 51

antisimmetrica, 54

di equivalenza, 54

d'ordine, 55

d'ordine ben fondato, 29

d'ordine denso, 20, 57

d'ordine discreto, 20, 57

d'ordine lineare, 57

d'ordine parziale, 57

d'ordine totale, 57

riflessiva, 54

simmetrica, 54

transitiva, 54

resto, 9

Ruffini P „ 85

segmento unitario, 21

sezione, 119

singoletto, 38

somma

modulo n, 86-7





sottogruppo, 81

improprio, 81

proprio, 81

sottoinsieme, 38

sottrazione





successione

convergente, 116

di Cauchy, 116

fondamentale, 1 16

successore immediato, 56

tautologia, 105

tavola

di appartenenza, 43

di verità, 46-7

trasformazione affine, 93

traslazione, 90

unione, 38

unità di misura, 21

valore assoluto, 12

Zenone, 34

Fabio Bellissima - Fondamenti Di Matematica

Documents

Transcript of Fabio Bellissima - Fondamenti Di Matematica