Fondamenti di matematica

FIGURA 16

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

Q

r

pwq

-1 r

F F F F V V V V

F F V V F F V V

F V F V F V F V

F F V V V V V V

V F V F V F V F

(PV Q) A —,R F F V F V F V F

Vi è un punto che sembra frapporsi alla perfezione della corrispondenza tra operazioni insiemistiche e operatori logici. Che fine ha fatto l'implicazione? Coloro tra noi che hanno già incontrato la logica, 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 c h e p —» 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 connettivo "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 operazioni insiemistiche - e © e i connettivi logici —» e <-> si corrispondono. La risposta è negativa. A — B è definita come A O Bc, e dunque corrisponde a p A —1 q che, a sua volta, è equivalente a —1 (p —» q). Questo appare davvero strano: dal punto di vista insiemistico 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. N o n si tratta infatti di differenze strutturali (ogni espressione insiemistica è traducibile in formula, e viceversa), ma di diverse scelte su dove pun-

FIGURA 17

Tavole di verità dell'implicazione e della doppia implicazione DOPPIA I M P L I C A Z I O N E

IMPLICAZIONE

P

1

F F V V

F V F V

V V F V

P

<7

p
F F V V

F V F V

V F F V

tare l'attenzione. Riprendendo l'immagine usata in precedenza, si tratta di modi diversi di guardare — e descrivere — la stessa costruzione. I concetti di algebra di Boole e di isomorfismo di struttura, che tratteremo nel capitolo 3, ci permetteranno di dare una veste matematica 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 elementi in cui, contrariamente agli insiemi normali, conta l'ordine. La coppia ordinata formata da x e y si indica con (x, y). N o n 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 costituito da tutte le coppie ordinate la cui prima componente appartiene 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 esegue il prodotto possono essere uguali tra loro, cioè è possibile ese-

FIGURA 18

Rappresentazione del prodotto cartesiano fi "

/(e) 1

\

\

,

\

(d) J

(A)

AxB

(a. e)

1

¡la. di fi(b,d) : [c, jd)\

y i(a)

(b.e)

(c.e)i

(

; (b) i Tcp; A

RxR

R

V 0

*

R

(B)

guire il prodotto di un insieme per se stesso. Considerando ancora 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. PROPOSIZIONE

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 sottoinsiemi di U. Di conseguenza lo sono anche tutti i risultati di ogni operazione booleanamente esprimibile. Invece, a meno di casi particolari, il prodottoci X B non è un sottoinsieme di U; infatti i suoi elementi sono coppie ordinate di elementi di U, le quali non è detto che siano a loro volta elementi di U. Non è quindi possibile rappresentare il prodotto cartesiano mediante diagrammi di Venn, come capita ad ogni operazione booleanamente esprimibile, e bisogna ricorrere ad un nuovo tipo di diagrammi che, appunto, si chiamano diagrammi cartesiani. Esprimendoci in termini un po' approssimativi, il diagramma cartesiano di A X B si ottiene sistemando su un asse orizzontale gli elementi 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 viene 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 ragionevolmente 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 discorso, anche non matematico. Esempi di relazioni sono non solo il parallelismo, la similitudine, l'"essere minore di", ma anche la consanguineità, la dipendenza, e ogni forma di parentela e di gerarchia.

In termini intuitivi, una relazione R può essere intesa come un legame 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'Inghilterra 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 difficoltà 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 delle coppie di rette parallele e così via. Questo modo di procedere, definito estensionale, può lasciare insoddisfatti. Identificando una relazione 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 matematico, ciò che è essenziale è sapere se una certa coppia è o no in relazione, ed è proprio a questo tipo di domande che la definizione insiemistica risponde. Identificando una relazione tra elementi di un insieme A con l'insieme 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 elementi di un insieme A con elementi di un insieme B. In tal caso una relazione RdaAaBhnn sottoinsieme di x B. Per esprimere il fatto che un elemento x è in relazione con un elemento y si scrive xRy oppure (x,y) e R. Le relazioni matematicamente 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 conseguenza del fatto che in tale teoria il concetto di relazione è trattato 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 cartesiano di R. In figura 19 mostriamo due esempi. Nel primo (FIG. 19A) le coppie di A x B che appartengono alla relazione sono state evidenziate 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 elementi 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 delle due donne Daniela ed Elisa (d ed e) ed xRy esprimesse la relazione " 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 x 2 + 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 figura, 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 relazioni (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 seguenti, 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 caratterizzare due tipi di relazione che (tra le relazioni che non sono funzioni) sovrastano le altre per importanza. Sono le relazioni di equivalenza 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 relazioni 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 equivalenza) e dato x e A, indichiamo con [x] R il sottoinsieme di A costituito dagli elementi con c u i x è in relazione, cioè [ x ] i = ( y e A: xRy\. Consideriamo poi l'insieme XR = {[x]^ : x € A} di tutti questi sottoinsiemi. 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 relazione 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 qualunque 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 fasci 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 equivalenza 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 relazione 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 incontrato (è 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 è divisore 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). N o n 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 è rappresentato 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 diagrammi di Hasse è dovuta al fatto che essi sono specifici per le relazioni 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 ammettono 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 \Ax A / (C) \ (o.c) (b,c) (c.c) 1 ' •\ 1 • ® ® 1 1

(fa)

1 1

\

(A)

! ! (0, fa) (fa. fa) (c,fa)i •1 1 • ® • ;

(")..' /

\

1 (i}a, a)

ffi(fa,o)

. (c. o) i

C.To)

. (fa) . (cP; A

)

(0)

\

/

(c)

(fa)

(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à è definita dì ordine totale (o lineare)-, altrimenti, cioè se esistono due elementi distinti x ey tali che né xRy n é y R x , la relazione viene detta d'ordine parziale. Ad esempio, la relazione < su una qualunque delle classi numeriche considerate è un ordine totale; infatti per ogni x,y vale x 1, è un ordine parziale in quanto, avendo U almeno due elementi, esistono coppie di sottoinsiemi X,Ydi U tali che n é X c Yné F c l Un altro esempio di ordine 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 discretezza 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 è finito allora R è discreta, mentre se R è densa allora è infinito. 2.6. Funzioni In termini intuitivi, possiamo definire una funzione / 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 è associato l'elemento^ si impiega la scritturaJ{x) =y, ey è detto immagine di x mediante f . È possibile però dare la definizione in termini insiemistici, eliminando l'ambiguo riferimento alla parola "legge". Allo stesso modo in cui una relazione R è stata identificata con l'insieme 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 condizioni. 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 particolare 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 codominio della funzione e, naturalmente, possono coincidere. Molte funzioni 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 qualunque si impiegano scritture quali^x), F(x), g(x) ecc. Poiché le funzioni sono particolari relazioni, è possibile rappresentarle mediante grafici cartesiani, come accade per le relazioni in genere. Il dato che caratterizza i grafici di funzioni è che, per l'unicità dell'elemento y corrispondente ad x, non possono esistere due punti 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 figura 19A (cfr. p. 53) con quella in figura 21. La seconda differisce dalla

FIGURA 21

Rappresentazione cartesiana di funzioni R

0 c".

(A)

(0)

.

(b)

.

Ù P ;

R

*

(B)

prima solo per avere una coppia in meno. Infatti, in termini insiemistici, 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 relazione non sia una funzione, la seconda invece lo sia. Infatti, nel primo 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 relazionale aRd, bRe e cRd alla scrittura funzionale f a ) = d, j{b) = e e J{c) = e. La stessa situazione ritroviamo tra le relazioni rappresentate in figura 19B e figura 21B. La prima non è una funzione, dal momento 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 pressoché totale dell'analisi matematica. E poiché quest'ultima ha come ambiente privilegiato la classe dei numeri reali, le funzioni sono state altrettanto a lungo identificate con le funzioni reali a variabile reale, cioè da numeri reali a numeri reali. Anche gli argomenti studiati sono stati relativi a questo tipo di funzioni: crescenza, continuità, derivabilità, integrabilità, somme, prodotti e così via. Con l'avvento 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 prodotto 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 è immagine 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 biunivoca) è una funzione che è contemporaneamente iniettiva e suriettiva. Queste proprietà si visualizzano efficacemente rappresentando le

funzioni, anziché in modo cartesiano, in modo sagittale, come in figura 22. Nei diagrammi sagittali l'informazione f x ) =y viene esibita 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 converte nella richiesta che da ogni punto di A parta una e una sola freccia. Tutti 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 suriettività si converte nel fatto che ad ogni punto di B arriva almeno una freccia. Pertanto, la funzione 1 di figura 22 non è iniettiva ed è suriettiva (è 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 /biettiva, 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 invertendo il verso delle frecce. Data una f u n z i o n e / d a 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'ordine di scrittura, la funzione g(J{x)) viene indicata con g o f ; in altri, 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 concetto di operazione sembra essere un concetto primitivo del linguaggio 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 numeri naturali un numero naturale e (2) ottiene questo risultato mediante una serie di azioni. Come già avvenuto per relazioni e funzioni, anche il concetto di operazione può essere espresso nel linguaggio della teoria degli insiemi. Tuttavia, la traduzione insiemistica formalizza solo il punto (1), mentre il punto (2), quello dinamico, viene staccato dal concetto 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 giustificare questo abbandono si può osservare che, anche di fronte a metodi diversi per eseguire la somma, se i risultati coincidono non è corretto parlare di operazioni diverse, ma di diversi modi (algoritmi) per eseguire la stessa operazione. La definizione è dunque la seguente: 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 sottoinsieme 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 sottrazione 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 interpretato come il tentativo di rendere operazioni, nel senso appena definito, 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 simbolo di operazione tra i due elementi della coppia: ad esempio, per indicare 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 generica 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 associativa 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 g e n e r e , / 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 parentesi". 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 indicare l'ordine: la scrittura (a*b)*c indica che prima dobbiamo eseguire l'operazione a*b, mentre la scrittura a*(b+c) indica che dobbiamo 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 questo 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 rispetto 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 torniamo allo scopo originario della teoria degli insiemi e, ricollegandoci 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 concetto di numero naturale, da quello di funzione. Descriviamo dapprima 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 funzioni 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 suriettiva 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 intuitivo. 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), stabilendo una corrispondenza biunivoca tra l'insieme A dei piatti e l'insieme B dei cucchiai. Se, in una corriera da 50 posti, vediamo dei posti vuoti e non vediamo nessuno in piedi (e nessuno seduto sulle ginocchia 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 passeggero 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 erano 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 determinata 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 cardinalità 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 provvisoria e in attesa di una definizione più rigorosa (cfr. PAR. 4.1), chiamare 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 numero 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 questo insieme-tipo indica la cardinalità di A. Riassumendo, la costruzione del concetto di cardinalità di un insieme finito può seguire questo cammino: Passo 1. Si determina, in base alle funzioni che è possibile stabilire, 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 riferendosi all'insieme-tipo con il quale è equinumeroso. Questa strategia, che abbiamo descritto applicandola ad insiemi finiti, può essere applicata anche agli insiemi infiniti, e dà luogo a quella parte della teoria degli insiemi che va sotto il nome di aritmetica 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 familiarizzarsi con essi, far precedere la trattazione dal seguente esempio figurato. 2.8.2. L'albergo di Hilbert e i dubbi di Galileo Supponiamo che un albergatore possieda un albergo con infinite stanze, una per ogni numero 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 occupante è 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 arrivi, 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. È sufficiente che, per ogni n, egli sposti il cliente della stanza n nella stanza In. Anche in questo caso nessuno dei vecchi ospiti perde l'alloggio 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 funzione suriettiva e non iniettiva. Nel caso di insiemi infiniti è invece

FIGURA 25

L'albergo di Hilbert |V IV

(A)

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

aaa

| V IV

IV |v |v |v |v ¡V

aaaaa (B)

aaa

1 Ivi

Ivi

|v|

!»!

1 a | v| a| v| a| v |ar :

possibile che le (1M3) si verifichino simultaneamente. Lasciando l'immagine dell'albergo ed esprimendoci in termini di funzioni numeriche, prendiamo ad esempio l'insieme A dei numeri pari, l'insieme 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 rapporto 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 ritenere 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 riferendosi 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 quadrato). 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 te "minore" di S? A: 2

4 6 8 10 12 14 ...

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

e:

46

8

10 12 14 ...

1 2 3 4 5 6 7 -

A: 2 4 6 8

1/

10 12 14 ...

S: 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 quadrato; 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 esser minore di quella di tutti i numeri, né questa maggiore di quella, ed in ultima conclusione, 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 grandezza gli insiemi infiniti. Almeno in questo, il maestro pisano fu d'accordo con Aristotele, che proprio per evitare un simile confronto 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 equinumeroso ad una propria parte dovesse essere presa proprio come definizione dell'infinità di un insieme. Era il passo d'inizio nella costruzione della teoria degli insiemi, quel paradiso dal quale, secondo 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 seguente. 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 collegamenti tra il concetto di cardinalità (finita) e l'esistenza di determinate 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, superflua 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ò dimostrare 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 comunque. Pertanto, la relazione < che si ricava dalle ( 1' ) -(3' ) è una relazione 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, desideroso di combattere i draghi, aveva deciso di prepararsi al difficile compito studiando prima tutta la letteratura al riguardo. Q u a n d o 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 rivelati biettivi tra loro (quali l'insieme dei numeri pari e quello dei

numeri naturali), e quindi che soddisfano la (1). Se dovesse verificarsi che, per gli insiemi infiniti, vale sempre la (1) allora non vi sarebbe 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, ritenne 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 stabilire equivale ad un potenziale drago che svanisce. Egli mostrò dapprima 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 numeri razionali, che è denso, è equinumeroso all'insieme dei numeri interi e quindi a quello dei numeri naturali, che sono discreti: PROPOSIZIONE

2.7. Card{Z) = CardiQ)-

Per dimostrare questa uguaglianza si costruisce dapprima una funzione biettiva/tra l'insieme Z + dei numeri interi positivi (cioè N) e l'insieme Q + dei numeri razionali positivi. Si dispongono le frazioni come in figura 27A, formando una matrice infinita. In essa è presente ogni numero razionale positivo. Anzi, uno stesso numero compare infinite volte: ad esempio, il numero 1/2 lo troviamo, oltre 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" mediante numeri naturali) i numeri razionali che si incontrano, igno-

rando però quelli già incontrati precedentemente sotto altra forma. Si costruisce così la seguente funzione biettiva/tra i numeri naturali 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 considerata 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 (infatti, 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 numerazione ogni razionale positivo viene fatto corrispondere ad un numero 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 numero finito di passi. Ottenuta così la funzione biettiva/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 dunque esistono, e a trovarli fu ancora Cantor. Il primo drago è costituito dalla coppia di insiemi N e R, che soddisfano la (2):

FIGURA 27

Biettività tra N e Q+

(A)

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

(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 sottoinsieme 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..., aggiungendo 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 infinita 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ò esistere alcuna biezione tra di essi. Procediamo per assurdo e supponiamo 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„ ... a / 2 ) = 0, ¿2,1 ¿2,2 ¿2,3 2,4 ••• a2,n Ai) = °> aò,\ aò,2 ai,i / 4 ) = 0,

a

òA ^3,5 ••• ai,n •••

&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, med i a n t e / di un naturale. Ma consideriamo il numero x e B così definito: 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 decimali di x sarebbero 1101, cioè avremmo 0,1101... . Pur appartenendo 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 generale, 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, è immediato 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,,, invertendo le quali x viene costruito, sono in "diagonale" (cfr. FIG. 28). Lo stesso metodo è alla base del seguente teorema: (Teorema di Cantor) Per ogni insieme A, Card{P[A)).

P R O P O S I Z I O N E 2.9.

Card(A) <

Il risultato vale per tutti gli insiemi, finiti e infiniti (è quindi una generalizzazione della Proposizione 2.1 di p. 38). Partendo da un insieme infinito, ad esempio N, e applicando reiteratamente il passaggio 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 insiemi-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... /(4) = 0,01100100100...

sulla diagonale: 0 010...

x = o. 1 101...

uno di essi (i cardinali transfiniti). Questa scelta non può essere fatta 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 dalle "usuali" proprietà insiemistiche, per cui, se la si desidera, deve essere posta come assioma (prende il nome di ipotesi del continuo); più in generale, anche la non esistenza, quando A è infinito, di cardinalità 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 sequenza possono rappresentare una buona scelta per gli insiemi-tipo infiniti. Tuttavia, ne costituiscono solo il tratto iniziale, poiché esistono 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 diventi 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'interpretazione 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 relazioni 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 oggetti con cui ci si trova ad operare, ma sul modo in cui essi si rapportano l'un l'altro. Nel corso del xix secolo emerge infatti la consapevolezza 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 capitare 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 concetto 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 accingiamo a fare. Considereremo strutture di due tipi: i gruppi e le algebre di Boole. I primi costituiscono senza dubbio il più importante esempio di struttura, oltre che il più antico. Nati in un contesto combinatorio ad opera di Evariste Galois (1811-1832), hanno progressivamente esteso la loro influenza in ogni angolo della matematica. 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 determinante. 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 evitare 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 generale si cerca di ricorrere a caratteri nuovi, come *, ©, _L, o o. Spesso però, per ragioni di semplicità tipografica, si utilizzano anche i simboli aritmetici + , -, X O i simboli logici A e v, con funzione di variabile. Ciò comporta il rischio di trasferire inconsciamente ad un'operazione denotata, ad esempio, con il simbolo + , le proprietà 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 condizioni 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 definito a p. 62. Questa condizione si esprime sinteticamente richiedendo 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ù semplicemente 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 ulteriore 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 G4.

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 numeri interi è ancora un numero intero. (G2, G5) L'operazione di somma è 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 inverso. 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 George Boole nel passo citato a p. 77; a sinistra compaiono simboli "astratti" che denotano enti generici, a destra compare la loro concretizzazione nello specifico esempio. ESEMPIO 2G.

(Q, +) e (R, +) sono gruppi commutativi. La prova è come la precedente. Invece, (N 0 , +) non è un gruppo, poiché viene meno la condizione G4. Preso un elemento a e N 0 , 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 N 0 . I prossimi esempi trattano ancora di classi numeriche, ma con riferimento 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 numeriche che siano gruppi rispetto al prodotto, bisogna quantomeno privarle dello 0. Risulta allora che: E S E M P I O 3G.

(Q-{0}, •) è un gruppo commutativo. Mostriamo che le condizioni G1-G5 sono soddisfatte. (Gì) Q—{0} è chiuso rispetto 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 elemento 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 ESEMPIO 4G.

R - { 0 } è un gruppo rispetto al prodotto. Per la dimostrazione è 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) allora (Y,*) è sottogruppo di (X,*). Riferendoci ai gruppi fin qui incontrati, abbiamo che (Z, + ) è sottogruppo di (Q, +). Infatti Z C Q e la somma su Z è la stessa somma su Q ristretta a Z. Allo stesso modo (Z, + ) e (Q, +) sono sottogruppi 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 elemento 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 sottogruppi sono definiti propri. Tornando al caso di ( Z , + ) , l'unico suo sottogruppo finito è il sottogruppo 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 sottogruppi 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 ammette 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 riconosciuta 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'insieme di tutte le funzioni biettive da A ad A 5(v4) è un gruppo rispetto 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 funzioni, e quello degli elementi dell'insieme A, che costituiscono il dominio 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'elemento neutro rispetto alla composizione. Per ogni / e 5(v4) vale infatti 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 / a p p a r t e n e n t e a 5(^4) è biettiva, essa ammette funzione inversa/ - 1 (cfr. p. 6 0 ) . / - 1 è ancora una funzione dav4 ad^4, ed è biettiva; q u i n d i / - 1 e 504). Inoltre,/ - 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 definizione d i / - 1 , (f of~1)(x), cioè/ _ 1 (/(*)), è uguale ad x. Ma anche i(x) = x. P e r t a n t o / o / " ' = i. Lo stesso accade per / _ 1 o / Dunque, (5(^4), o ) è un gruppo, e l'interpretazione è stata la seguente: X

=>

*

=>

e a-

o

=> 1

= >

/ -

1

Contrariamente ai precedenti, questo esempio ci permette di ottenere 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 cardinalità di A Nel caso banale in cui .<4 sia un insieme di uno o due elementi, 5(yl) è commutativo. Se invece A ha più di due elementi allora 5(.Ì4) è non commutativo. Infatti, se a,b,c sono tre distinti elementi dì A e / e g sono due funzioni di 5(^1) tali che: j{a) = t> g(a) = b

j{b) = c g(b) = a

J{c) = 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 ordinamento degli elementi di A, e ciò risulta chiaro se la rappresentiamo 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 permutazioni di A. Se, come nel nostro esempio, A ha 4 elementi allora le permutazioni sono 24: a bcd bacd

ca bd d a bc

a bd c bade c adb da c b

ac b d b cad c b ad db ac

a ed b b c da c b da db ca

ad bc b da c cda b de a b

ade b bd ca cd ba de b a

Il numero 24 è il fattoriale di 4, cioè il prodotto di 4 per tutti i numeri naturali che lo precedono (in simboli 4! = 4 • 3 • 2 • 1). Infatti, dovendo ordinare quattro elementi, abbiamo 4 possibilità di scegliere chi porre al primo posto (a,b,e oppure d). Una volta fissato il primo, abbiamo 3 possibilità di scegliere il secondo, e dunque abbiamo 4 • 3 modi diversi di scegliere i primi due. Per ciascuna di queste scelte, abbiamo 2 possibilità di scegliere il terzo e, scelti i primi 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 elementi 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 organizzarle nel modo che poi sarebbe diventato quello di gruppo è emersa soltanto verso la fine del x v m secolo, in connessione con il problema della risoluzione delle equazioni di grado superiore al 4°. Il legame tra i due ambiti è nascosto e complesso; lo descriviamo soltanto 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, oltre 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 analoghe per risolvere le equazioni di 5° grado. Nel 1770 Lagrange ipotizzò che il successo nella soluzione delle equazioni di 4° grado e gli insuccessi per le equazioni di 5° grado potessero trovare una spiegazione nel diverso comportamento dei rispettivi insiemi di soluzioni rispetto alle permutazioni su di essi. Se indichiamo con x1,x2, x 3 , x 4 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, x 4 }, non cambiano di valore. Ad esempio, l'espressione X! • x 2 + x 3 • x 4 non cambia di valore in seguito alla permutazione x 4 x3 x, x2 in quanto, per la commutatività del prodotto e della somma tra numeri, Xi • x2 + x 3 • x4 è uguale ax4 • x3 + xl • x2 (l'espressione cambia invece di valore in seguito alla permutazione x 4 Xj x 3 x2, essendo, in generale, xl • x 2 + x 3 • x 4 ^ x 4 • X! + x 3 • x 2 ). 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, x 2 , x 3 , x 4 , x 5 che, sottoposta alle 120 (=5!) permutazioni di tali variabili, cambiasse valore solo 3 o 4 volte, sarebbe anche possibile trovare il modo di risolvere una equazione di 5° grado riconducendola a equazioni di 3° o 4° grado. M a 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 isolò 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 [1] 4 [2] 4 [3] 4

= = = =

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

L'insieme di queste quattro classi viene denotato con Z 4 . 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 Z 4 = {[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 disgiunte e la loro unione è uguale a Z. Se x è un numero naturale allora, 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 relazione 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 congruenza 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 Z 4 un'operazione di somma, denominata somma modulo 4, che indichiamo con + 4 : [x]4 + 4 \y}4 è uguale alla classe di Z 4 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. (Z 4 , + 4 ) è un gruppo commutativo. (Gì) Alla somma di due elementi di Z 4 corrisponde ancora un elemento di Z 4 . (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 M 4 + 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 numeri) e quindi i due risultati coincidono. Lo stesso accade per la commutatività. (G3) La classe [0] 4 è l'elemento neutro. Infatti M 4 + 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 mostra la tabella di figura 29 gli inversi di [0] 4 , [1] 4 , [2] 4 e sono rispettivamente[0] 4 , [3] 4 , [2] 4 e [1] 4 . Ciò conclude la dimostrazione del fatto che (Z 4 , + 4 ) è un gruppo commutativo.

In modo del tutto analogo si dimostra che, per ogni numero naturale n, ESEMPIO 7G.

(Z„, + „) è un gruppo commutativo, dove Z„ = {[0]„, [1 ]„, ...,[« - 1]„} è l'insieme delle classi di resto modulo n e l'operazione + „ è la somma modulo n.

FIGURA 29

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

CTZr (A)

A *

• x*y

AV

+«

M,

[l]t

[2]t

[3)4

[0],

[o],

[1],

[2]t

lì],

[1]«

[l]t

[2]t

[3)4 [<*)„

[2]4

[2],

[3]«

[0],

[3]«

[3lt

[0|4

[1], [2]t (B)

[1],

L'aritmetica che impiega Z„ viene chiamata aritmetica modulo n o, più generalmente, aritmetica modulare. Per la sua ciclicità, si comporta 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 partire 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 triangolo equilatero di vertici a,b,c, costruito in materiale rigido, e di appoggiarlo 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 m 0 , che possiamo intendere come "movimento nullo", vediamo che mx e m 2 corrispondono ad una rotazione in senso orario, rispettivamente di 120° e di 240°, mentre m ò , m 4 e m 5 corrispondono a ribaltamenti lungo una delle tre bisettrici. Ciascuno di questi movimenti può essere ottenuto "fisicamente" in infiniti modi. Ad esempio, mx può essere ottenuto, oltre che con una rotazione in senso orario di 120°, anche con una rotazione oraria di 480° (= 120 + 360), oppure con una rotazione antioraria di 240° ecc. Dicendo che i movimenti di Mr sono sei abbiamo di fatto identificato due movimenti fisici se essi producono lo stesso risultato, cioè la stessa corrispondenza tra a,b,c e 1,2,3. Definiamo ora un'operazione di composizione di movimenti, che indichiamo 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° (m x ) e poi una di 240° (m 2 ), si compie una rotazione di 360°, e quindi i vertici ritornano nella posizione originaria m 0 . E ancora: m 2 © m 4 = 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 dell'operazione (le modalità di lettura sono descritte in figura 29A). ( 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 movimento nullo m 0 è l'elemento neutro. (G4) Come mostra la tabella, ciascun elemento ha inverso. Abbiamo m { 1 - m 2 e m 2 x = m x \ infatti, dopo aver compiuto una rotazione oraria di 120°, per tornare alla posizione originaria m 0 bisogna compiere un'ulteriore rotazione di 240°. Invece i movimenti m ò , m 4 e m 5 sono autoinversi, cioè ciascuno di loro è l'inverso di se stesso; compiendoli due volte si torna infatti nella posizione originaria m 0 . Infine (e questo vale in tutti i gruppi) anche l'elemento neutro m 0 è autoinverso. Questo ESEMPIO 8G.

FIGURA 30

I movimenti che portano un triangolo equilatero su se stesso 1

1

1

® m0 m0 m1 m2 m^ m^ m ffi] m2 m <0 0 m^ m* m

m m m rr>2 ir>2 mo 5 3 ffij mj w^ m4 m0 m2 m

ni.

m

/rie m

m m

mi m0 m

rr>7 "i,'0m.

gruppo non è commutativo: ad esempio, m 3 ® m 4 = m 2 , 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 corrispondere 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 movimenti. 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 dunque la seguente forma:

T:

\x

= x + a

j'

=y

+

b

E facile verificare che l'insieme delle traslazioni è un gruppo commutativo. ( G l ) Se Tx è { y l * ^

e T2 è { y Z ^ g

allora, appli-

candóle consecutivamente, abbiamo che il punto P = (x,y) viene spostato 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

¿ 3 , con a3 = a, +a2 e b3 = bx + b2.

Pertanto Tl © T2 è

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 traslazione; in fatti, se

{ x' = x~ a ^ y'=y+b

lora

è

Í x' = x-f- ( 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 è quello delle dilatazioni. Una dilatazione può essere intesa immaginando 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 rimane fisso è l'origine). In termini algebrici, una dilatazione ha la seguente 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 dimostrazione che l'insieme delle dilatazioni costituisce un gruppo commutativo è analoga a quella fatta precedentemente per le traslazioni. 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 k < è la dilatazione < \y'=h • y \y'=-r-y h

Il gruppo delle dilatazioni ha importanti sottogruppi. Il più significativo è 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 delle dilatazioni è costituito dalle quattro dilatazioni in cui \k\ = \h\=\.

Ì

x' =

\ x' = x

X

\ x' =

\ x' =

—X

—X

A: [y , = -y D2: [y , = y Dy < 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 poligono serve soltanto a mettere in evidenza l'effetto ottenuto). L'operazione di composizione sull'insieme S= {D0, D2, D}} è descritta dalla tabella, che mostra come S sia chiuso rispetto all'operazione. La presenza costante, sulla diagonale discendente, dell'elemento neutro D0 segnala che ogni elemento del gruppo è autoinverso. Il fatto poi che la tabella sia simmetrica rispetto a tale diagonale indica che il gruppo è commutativo.

FIGURA 3 1

Simmetrie Y

V

\

D=]

' - - - '

X

A

[ P

Dn

D,

Y

Y r -|

1

n X

02

X

®

D0

D,

d2

d3

D0

D0

Di

d2

D,

D,

D,

D0

D,

d2

d2

d2

D3

DJ

°3 d2

D„

D,

D,

D0

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 seguente gruppo. ESEMPIO IIG.

Una trasformazione affine (o affinità) ha la forma

x' = a + kx + ty y' = b + rx + hy

con a,b,k,r,t,h 6 R e k • h — t • r^ 0.

L'insieme delle trasformazioni affini è un gruppo rispetto all'usuale composizione di movimenti. L'elemento che maggiormente differenzia queste trasformazioni rispetto alle traslazioni e alle dilatazioni è che x'dipende non solo da x, ma anche d a y e, analogamente, 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 affine abbia la sua inversa (dimostrazione nei cui dettagli non entriamo) 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 ottiene 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 sugli scopi della teoria dei gruppi e dell'algebra astratta in generale. Come abbiamo visto, gli strumenti dell'algebra classica si erano rivelati 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 preesistenti 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, simili 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 "proprietà che tutti i gruppi possiedono" sono esattamente i teoremi della teoria dei gruppi, cioè quei risultati che derivano dall'impiego delle 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 dimostrazione in algebra astratta. Diversamente dalle usuali dimostrazioni aritmetiche o geometriche, in questo caso non parliamo di oggetti specifici e conosciuti (numeri, figure ecc.). Parliamo invece di oggetti completamente indefiniti, "qualunque". Ogni ausilio derivante 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 aggrapparsi, oltre alle regole universali della logica, sono gli assiomi G1-G4 della teoria. Tuttavia, man mano che si dimostrano teoremi, essi possono essere impiegati per la dimostrazione di risultati ulteriori. Si viene così a formare un insieme di conoscenze che generano un nuovo tipo di intuizione, caratteristica dell'algebra astratta, i cui enti di riferimento sono le strutture stesse.

i (Unicità dell'inverso). Sia (X,*) un gruppo. Allora un elemento non può avere più di un elemento inverso (ed è per questo 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 inversi b e c. Allora vale questa catena di uguaglianze (il secondo membro di ciascuna uguaglianza coincide con il primo della successiva): TEOREMA

b-b*e b * e= b * (a * c)

(perGj) (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 (perGj). 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.

(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 .(Analogamente, b * a'1 è l'unica soluzione dell'equazione x * a = b). TEOREMA 3

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 tutto banali. In effetti, è immediato rilevare che l'unica soluzione dell'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, allora 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\ •\b d a c)

Z:\b

(a

b c

c d

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 considerare l'insieme 5(^4) delle funzioni biettive consideriamo l'insieme F(A) di tutte funzioni da A ad A, allora è possibile trovare equazioni / °X =
(Isi) (Is2)

è biettiva; (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 (*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 0(a) *2 &(&) =
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) *2 4»( ò) y <J>( 0 f») X,

esprime dunque l'identità strutturale, e le proprietà invarianti per isomorfismo 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 elementi a e b tali che a * b^ b * a), e dunque un gruppo non commutativo non può essere isomorfo ad uno commutativo. (Più dettagliatamente: 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 (b) appartengono aX 2 , che in tal modo non è commutativo). Pertanto, il gruppo commutativo 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 abbiano lo stesso numero di elementi e sia quindi possibile definire funzioni biettive tra loro. Anche la presenza o meno di elementi autoinversi 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 Z 4 delle classi di resti modulo 4 (Esempio 6G) e il gruppo delle simmetrie S= {D0, DX, D2, D}} (cfr. p. 92) non possono 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. ESEMPIO

11. Il primo esempio riguarda il gruppo (M^©) dei movimenti 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 sufficiente) che i due gruppi abbiano lo stesso numero di elementi. Nel nostro caso, entrambi i gruppi hanno 6 elementi. Infatti gli elementi di MT sono {m 0 , m x , m 2 , m 3 , m 4 , m 5 }, come descritto in figura 30, mentre S(y4) contiene le sei biezioni elencate qui sotto (per comodità indichiamo la funzione identica i con f0):

e la o:U

b b

c\ c)

r [a h''\b

b c

c\ a)

h:\c

r

Ia

b a

c\ b)

¿ • l a b e ] h'-\a c b)

r [a /¿[e

b b

c\ a)

h:\b

£

[a

b a

c\ c)

Le tabelle della composizione tra movimenti e quella della composizione di funzioni sono riportate in figura 33. Come si può facilmente 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 significato di identità strutturale, che possiamo esprimere in questo modo: in due strutture isomorfe, le tabelle che descrivono le operazioni possono differire per i nomi che vi compaiono e per gli oggetti che trattano ma, tradotti i nomi, devono coincidere. Invece, il fatto che nella 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 avuto un isomorfismo, anche se in forma meno palese. Sempre analizzando le tabelle di figura 33, vediamo che l'insieme {m 0 , m x , m 2 } costituisce un sottogruppo di M T . L'insieme è in-

FIGURA 33 Confronto di tabelle per stabilire un isomorfismo +

©

m0 m, m 2 m 3 m X m 5

m0 m1 m2\ m^ m^ w^ m0 m1 m2\ffijm^ m^ m2 m0 m^ m^ m^ m2 ma ; m^ m^ m^ ffij mg m^ m0 m2 ml m^ffjjm^ ffij m0 w2 m^ m^ m^ m2 w^ ni0 \Mt.®)

3 [o]3 WJ [2lj

[0]3 [0]3 [1]3 [2]j

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

e fo A h h U h

fo fo A h h u k

A h' h A h h fo h io A k h u fo h h A u h A (SIA).

u h h h h fo A

k h h u A h fo

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 sottogruppo di S(v4) e i due sottogruppi sono isomorfi. Entrambi sono inoltre isomorfi al gruppo Z 3 delle classi di resto modulo 3. Questi isomorfismi hanno una giustificazione intuitiva. {m 0 , m l , m 2 } costituisce il gruppo delle rotazioni del triangolo, rispettivamente di 0, 120 e 240 gradi (i restanti movimenti m 3 , m 4 , m 5 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 composizione di rotazioni del triangolo è quindi una simulazione della somma modulo 3; da qui l'isomorfismo di ({m 0 , m x , m 2 },©) con (Z 3 ,+ 3 ). Ma gli stessi movimenti m 0 , m x , m 2 possono essere descritti, oltre che in termini di rotazioni, anche come permutazioni di vertici, cioè come funzioni che a determinati vertici fanno corrispondere 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

({w 0 , mx, m2},@) con ({/ò./ì»/}» ° )• Ancora una volta vediamo dunque che cosa siano due strutture isomorfe: interpretazioni diverse 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 somma, 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 =
rispondenza biunivoca con un suo sottoinsieme proprio (e anzi, questa possibilità caratterizza e quindi può definire gli insiemi infiniti). Ora vediamo che questa corrispondenza biunivoca può anche, in presenza di operazioni, diventare un isomorfismo. L'esempio ci mostra infatti un caso di un gruppo isomorfo ad un suo sottogruppo proprio. Aggiungiamo ancora un'osservazione di carattere 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 rispetto alla somma. Se su tali insiemi consideriamo altre operazioni oltre alla somma, la precedente funzione non è tenuta a conservarle; prendendo ad esempio il prodotto, abbiamo 0 ( x • y) ^ O(x) • 0(y), poiché
$ ( x - y ) = log a (x-y) = l o g ^ + l o g ^ = O(x) + O ^ ) . Is2 esprime la proprietà fondamentale dei logaritmi, cioè la conversione del prodotto in somma; l'impiego dei logaritmi coincide dunque con l'impiego di questo isomorfismo. Sembra però difficile vedere (R + ,•) e (R, + ) come "diverse interpretazioni di una stessa situazione strutturale", dal momento che le operazioni • e + appaiono 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 numeri è 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ù nascosto. 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 "realizzazione" in forma d i regolo) sono state i più efficaci calcolatori prima dell'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, rispettivamente 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 simboli 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 Boole 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 A V )

1 0

=> => => => => =>

W) n u c U 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 rispetto 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) È sottoinsieme 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'insieme 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, indica 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 verificare infatti che l'insieme {0,U} è chiuso per intersezione, unione 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 parallelismo tra le operazioni insiemistiche N , U e f e gli operatori logici A, v e —1. Alla luce di questo sembrerebbe plausibile, così come abbiamo 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 simboli 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 proposizionali 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 insiemistica è l'equivalenza logica, due formule diverse tra loro ma logicamente 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 insiemistiche 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 formule 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 partizione dell'insieme delle formule proposizionali in classi di equivalenza, ciascuna delle quali contiene tutte le formule equivalenti ad una formula data. Denotiamo con [(p]= la classe di equivalenza della formula cp. L'insieme F di tutte le classi di equivalenza (in simboli, F = {[(p]s :

v

v L

zifoL =[-.*].. 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 qualunque altra tautologia). Analogamente, l'elemento neutro dell'operazione v deve essere costituito da una classe [v|/]= dove V|/ è un tipo di formula falsa per qualunque valore di verità attribuito alle sue variabili (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 contraddizioni-, 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 contraddizione, segue che AB6 è soddisfatta. La seguente tabella interpretativa riassume quanto detto:

A

F A

V

V

X

J

1 0

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

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

gli stessi segni nella colonna destra, t r a p e —ip, indicano i connettivi logici). L'algebra di Boole (F, a , v, ^n) che abbiamo costruito è infinita: esistono infatti infinite formule a due a due non logicamente equivalenti, e quindi infinite classi di equivalenza. Ma è possibile costruire algebre di Boole finite i cui elementi siano ancora classi di formule. Ad esempio è sufficiente considerare, anziché l'intero insieme 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 2 2 , 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 soddisfa le seguenti condizioni: O è biettiva; <5>{a A j b) = Q>{a) A 2 (£), per ogni a,b E <ì>(a v , b) = <$>(a) v 2 O(^), per ogni a,b e Xx\ O U ' 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 algebre di Boole deve invece riguardare le tre operazioni A, v e '. Il seguente risultato esprime una proprietà che caratterizza fortemente 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ò significa che le operazioni in una qualunque algebra di Boole si comportano esattamente come le operazioni n , U e c in un campo di insiemi. 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 è strutturalmente identica ad un campo di insiemi, allora questi sono adatti a rappresentare l'intera classe delle algebre di Boole. La Proposizione 3.1 ha inoltre le seguenti conseguenze (non immediate), che riguardano specificamente le algebre di Boole finite: 3.2. Ogni algebra di Boole finita ha un numero di elementi pari ad una potenza di 2. PROPOSIZIONE

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

Queste due proposizioni, insieme, ci dicono che, dato un qualunque numero naturale n, se n non è una potenza di 2 allora non esiste 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 varietà, 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 algebre di Boole siano necessariamente confinati nell'ambito della logica 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 esempio, 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 A V > a 1 0

=> => =>

=> =>

=>

Dn MCD mcm ni a n 1

(massimo comun divisore) (minimo comune multiplo)

otteniamo un'algebra di Boole. (Ecco un altro punto critico per la notazione: l'elemento neutro dell'operazione v, indicato genericamente con il simbolo 0, è in questo esempio il numero 1. Il simbolo 1, con cui si indica l'elemento neutro dell'operazione A, corrisponde 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 seguendo la tabella precedente diventa MCD(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 tra P{U) e Dn è la seguente: 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 condizione $>(a AJ b)=<S>(a) A 2 <&(£) diventa 0({2,5} N {5,11}) = MCD(({2,5} n {5,11}) =
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 comuni 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 conclusione, le algebre P(U) e Dn differiscono solo per il fatto che in un caso abbiamo l'indicazione dei fattori, nel secondo il prodotto eseguito. Ma questo, riprendendo l'immagine precedente, è un particolare 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 capitolo 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 segmenti. 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 matematica non dovevano essere posti i concetti geometrici ma il concetto di numero. Una prova del ruolo fondante assunto da questo concetto è che le varie scuole di filosofia della matematica (realismo, nominalismo, intuizionismo, formalismo ecc.) si differenziano maggiormente proprio nel modo in cui considerano i numeri. Una simile varietà di punti di vista non significa che vi siano definizioni di numero 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 è rivolta alla definizione diretta ed esplicita dei numeri in quanto oggetti singoli; la seconda è rivolta a definire assiomaticamente le classi numeriche 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 realismo; la seconda si svolge all'interno delle strutture algebriche, e riflette maggiormente un'impostazione di tipo formalistico. Le trattiamo 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 numero naturale. A p. 65 abbiamo, in via provvisoria, definito un numero 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 particolari insiemi-tipo (i numeri naturali con funzione cardinale). Come elementi di tali insiemi-tipo avremmo potuto scegliere oggetti qualunque, 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 extramatematici (e tanto meno a parole di una lingua nazionale), perché in questo modo la matematica si troverebbe a dipendere da qualcosa che le è estraneo. Dovendo quindi rimanere nell'ambito degli oggetti matematici si incontra un problema. Se, con la teoria degli insiemi, dobbiamo costruire prima i numeri e poi gli altri oggetti matematici, 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 costruire i numeri successivi. Il modo è il seguente. L'insieme-tipo per il numero 1, dovendo contenere un elemento, conterrà l'unico elemento 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, disponiamo, lo 0 e l'I, e sarà quindi {0,{0}}; il numero 3 conterrà tre elementi, lo 0, l'I e il 2, e sarà {0,{0},{0,{0}}}, e cosi via per qualunque numero n, che sarà definito come l'insieme di tutti i suoi predecessori. La seguente tabella riassume le definizioni date: 0 1 2 3 4 n 112

= = = = =

0 {0} {0,1} {0,1,2} {0,1,2,3}

{0} {0,{0}} {0,{0},{0,{0}}} {0,{0},{0,{0}},{0,{0},{0,{0}}}}

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

{0,{0},-.

•••}}}}

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 naturali sono serviti per definire ulteriori classi numeriche ma, come attesta l'aggettivo "naturali", non sono mai sembrati essi stessi bisognosi di definizione. Ciò che appare strano è dunque il fatto stesso di averli definiti, fondando il concetto di numero su qualcosa di ancor 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 maggiormente 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 ordinata 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 N x N , su cui si definisce la seguente relazione 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 partizione 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 nell'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à incontrato, 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 anche 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 avevamo creato ex novo un insieme infinito di nuovi numeri, indicato con Z". Si trattava semplicemente di una copia di N e, per distinguere 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 naturali. 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 direttamente 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 semplicemente 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 mediante 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 x N 0 ) / 5 ) . Le nuove operazioni di somma e prodotto tra i numeri 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 = 4-7, 6-7 + 4-2}s = [(40,50)] 5 . In effetti, le classi [(6,4)] 5 , e [(40,50)]5 definiscono rispettivamente i numeri 2 (cioè 6 (cioè 2 - 7) e - 1 0 (cioè 40 - 50); vediamo così che 2 • - 5 Ciò conclude la costruzione di Z.

[(6-2 + [(2,7)] 5 - 4), - 5 = -10.

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. Infatti 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 successione 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 impiegata 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 successione 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 potremmo dimostrare che, in R, una successione è convergente se e solo se è di Cauchy. Ma non li abbiamo ancora, e ciò che possiamo fare è definire i numeri reali mediante le successioni razionali di Cauchy. Sull'insieme di tali successioni si stabilisce una relazione di equivalenza T che (a posteriori) lega due successioni (sn) e

(s'„) quando individuano lo stesso reale. La definizione, che fa riferimento solo a numeri razionali, è : (s„) T (s'n) se per ogni numero 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 simboli [(*„)] r)> e l'insieme dei numeri reali come l'insieme di queste classi. A questo punto, i numeri reali sono stati definiti in termini di numeri razionali, questi in termini di numeri interi, e questi ultimi in termini di numeri naturali. Ogni numero reale è dunque rappresentabile mediante una lunga espressione che vede coinvolti solo numeri naturali. Poiché i numeri reali sono lo strumento dell'analisi matematica e i numeri naturali quello dell'aritmetica, il processo di riduzione dei reali ai naturali è stato chiamato aritmetizzazione dell'analisi. Ma, a loro volta, i numeri naturali sono stati definiti all'interno della teoria degli insiemi basandosi solo sull'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 conquista teorica.

4.2. Le classi numeriche come strutture algebriche

In

questo secondo modo di definire le classi numeriche non è più necessario seguire un percorso prestabilito, in cui ogni nuova classe si basa sulla precedente e la estende, ma è possibile introdurre ciascuna classe indipendentemente dalle altre. Per comprendere l'idea di base ricordiamo come, nel capitolo 3, sia emersa la "maggiore varietà" 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 singola 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 nostra 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 termini 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 matematico. 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 hanno valore di variabili. • La struttura (X, +, •) è un campo (nessun legame, tranne l'omonimia, 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 (insieme 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 isomorfismo, l'unico campo esistente. Vi è anche (Q, + , •)> che non può essere 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 concetto 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; 0 3 ) 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 renda 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'unico campo ordinato. Lo è anche, tra gli altri, Q. Nel paragrafo 1.4.1 abbiamo rilevato, in termini intuitivi, che la principale differenza tra Q ed R risiede nel fatto che se si pongono in corrispondenza 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 verso la fine dell'Ottocento. Dato un insieme X totalmente ordinato 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 esiste 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 aggiunto ad uno di essi. Ma se lo aggiungiamo ad A allora A viene a possedere elemento massimo (appunto V2), mentre se lo aggiungiamo a B allora B avrà elemento minimo (sempre V2). Definiamo 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 elemento, e per ogni sezione (A,B) di X, A ha massimo elemento oppure 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 matematica. Ciò è accaduto per il semplice motivo che essi costituiscono delle risposte ad una domanda che di certo la filosofia della matematica non può eludere: che cosa sono i numeri? Nel paragrafo precedente abbiamo spiegato che cosa è un numero costruendolo 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 invece una risposta, come quella descritta in questo paragrafo, che si limita ad elencare una serie di proprietà generali relative ad operazioni e relazioni, lasciando che qualunque insieme che le soddisfa vada bene per essere l'insieme dei numeri reali. Una simile risposta 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'insieme dei numeri reali insiemisticamente definiti soddisfa tutti gli assiomi 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 reali rappresenta una sintesi delle proprietà di cui i numeri reali (insiemisticamente definiti) godono, ed è quindi una base per produrre le dimostrazioni che li riguardano. Si tratta dunque di due costruzioni 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

contraddizione, 105

algebra di Boole, 102

coppia ordinata, 50

antiperiodo, 16

corrispondenza biunivoca, 59

Aristotele, 34, 69 aritmetica modulare, 88 aritmetica modulo n, 88

Dedekind R., 35, 119

aritmetizzazione, 23, 1 1 7

denominatore, 17, 21 diagonalizzazione (metodo di), 74 diagramma

biezione, 59

cartesiano, 51

Boole G . , 77, 80

di Hasse, 56 di Venn, 38 sagittale, 60

campo, 118

differenza, 42

ordinato, 119

differenza simmetrica, 42

ordinato continuo, 120

dilatazione, 91

campo di insiemi, 102

disgiunzione, 46

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

dividendo, 9

cardinalità, 8

divisione

Cartesio, 29

con la virgola, 15

Cauchy A. L., 85, 116

euclidea, 15

classe

tra numeri naturali, 8

di equivalenza, 55 di resto modulo n, 86-7

tra numeri razionali, 17 tra numeri reali, 28

codominio, 58

divisore, 9

coefficiente angolare, 30

dominio

commensurabili (grandezze), 23 complemento, 40 completezza, 23

di un gruppo, 79 di una funzione, 58 doppia implicazione, 49

composizione di funzioni, 60 di movimenti, 88 congiunzione, 46

elemento autoinverso, 82 equivalenza

congruenza modulo n, 86

insiemistica, 44

connettivo logico, 46

logica, 47

espressione

insieme

booleana, 41

complementare, 40

insiemistica, 41

numerabile, 74

Euclide, 34-5, 111

più che numerabile, 74 universo, 40

fattoriale, 84 Fermar P. de, 29 formula proposizionale, 47 funzione, 57 biettiva, 59 identica, 82 iniettiva, 59

vuoto, 37 insiemi disgiunti, 39 intersezione, 38 inverso, 79 isomorfismo di algebre di Boole, 106 di gruppi, 96

inversa, 60 opposto, 12

leggi di assorbimento, 102

suriettiva, 59 negazione, 46 Galilei G . , 68

numeratore, 17, 21

Galois E., 77, 85

numero

grafico cartesiano, 53

decimale, 14

gruppo, 78

decimale finito, 15

abeliano, 79

decimale periodico, 16

commutativo, 79

frazionario, 15

delle permutazioni, 84

intero,11

di Galois, 85

irrazionale, 23

simmetrico, 82

naturale, 7 negativo, 11

Hilbert D „ 66

positivo, 11 razionale, 14 reale, 24

identità insiemistica, 42 identità valida, 42 implicazione, 49

omotetia, 91

inclusione, 38

operatore logico, 46

inclusione stretta, 38

operazione

incommensurabili (grandezze), 23

associativa, 62

infinito

binaria, 62

attuale, 33

booleana, 41

potenziale, 33

booleanamente esprimibile, 42

segmento unitario, 21

commutativa, 62 distributiva, 63 ordine, cfr. relazione

sezione, 119 d'ordine

singoletto, 38 somma

parte intera, 16 partizione, 39 periodo, 16 permutazione, 83 Principio di comprensione, 37 prodotto cartesiano, 50 tra numeri interi, 14 tra numeri naturali, 8 tra numeri razionali, 18 tra numeri reali, 26 proprietà di struttura, 98

modulo n, 86-7 tra numeri interi, 12 tra numeri naturali, 8 tra numeri razionali, 18 tra numeri reali, 25 sottogruppo, 81 improprio, 81 proprio, 81 sottoinsieme, 38 sottrazione tra numeri interi, 14 tra numeri naturali, 8 tra numeri razionali, 18 tra numeri reali, 28

quoziente, 9

successione convergente, 116

rappresentazione cartesiana, 53, 58 reciproco, 19

di Cauchy, 116 fondamentale, 116 successore immediato, 56

relazione, 51 antisimmetrica, 54

tautologia, 105

di equivalenza, 54

tavola

d'ordine, 55 d'ordine ben fondato, 29

di appartenenza, 43 di verità, 46-7

d'ordine denso, 20, 57

trasformazione affine, 93

d'ordine discreto, 20, 57

traslazione, 90

d'ordine lineare, 57 d'ordine parziale, 57

unione, 38

d'ordine totale, 57

unità di misura, 21

riflessiva, 54 simmetrica, 54 transitiva, 54

valore assoluto, 12

resto, 9 Ruffini P „ 85

Zenone, 34