Dispense di Aritmetica

Dispense di Aritmetica Dikran Dikranjan e Maria Silvia Lucido Dipartimento di Matematica e Informatica Università di Udine via delle Scienze 200, I-33100 Udine settembre 2003 Queste dispense nascono per il corso di Aritmetica. Nel capitolo 1 viene presentato il concetto di insieme e di appartenenza, le operazioni tra insiemi, la definizione di insieme finito e un esempio di insieme infinito, i numeri naturali con una loro importante proprietà, il principio di induzione. Nel capitolo 2 vengono illustrate le relazioni su insiemi. Tra queste occupa un posto fondamentale la definizione di applicazione. Vengono poi introdotte anche le relazioni di equivalenza, i coefficienti binomiali, le relazioni d’ordine e preordine e i reticoli. Nel capitolo 3 vengono introdotti le prime nozioni riguardanti l’aritmetica, ovvero lo studio dei numeri. All’interno dell’insieme dei numeri interi, si da’ la definizione di divisibilità e di numero primo. I numeri primi saranno poi gli ”atomi” con i quali si costruiscono tutti i numeri interi. Si danno le nozioni di massimo comun divisore e di minimo comune multiplo. Inoltre viene formalizzata con l’algoritmo di Euclide, la divisione euclidea che si impara alle scuole elementari. Si enuncia e si dimostra il Teorema Fondamentale dell’Aritmetica, che garantisce che ogni numero intero si può fattorizzare in modo essenzialmente unico come prodotto di primi. Si definisce nell’insieme dei numeri interi una relazione di equivalenza, la congruenza modulo n, per un fissato numero intero n. Questa relazione è compatibile con le operazioni di somma e prodotto dei numeri interi. Per questo ritroveremo spesso nei successivi corsi di Algebra (e non solo) l’insieme delle sue classi di equivalenza. Con questi strumenti verranno poi spiegati i criteri di divisibilità per 3, 9, 11 e 101, alcuni dei quali noti fino dalle scuole elementari. Negli ultimi due paragrafi di questo capitolo viene dimostrato un Teorema di Fermat (non l’ultimo...) e una sua generalizzazione dovuta ad Eulero. Viene poi studiata la funzione di Eulero, che conta quanti sono i numeri naturali coprimi con n e minori di n, per un fissato numero naturale n. Nel capitolo 4 vengono presentati gli altri insiemi di numeri, ovvero i numeri razionali, reali e complessi. I numeri reali vengono solo accennati perché sono oggetto di studio approfondito dei corsi di Analisi. Maggiore attenzione viene invece dedicata ai numeri complessi, alle operazioni definite su di essi e alla loro interpretazione geometrica. Questo conclude la parte basilare della Teoria che costituisce il corso di Aritmetica. Seguono due capitoli di complementi sugli insiemi e sull’aritmetica, in cui vengono presentati alcuni risultati che richiedono talvolta delle dimostrazioni un po’ più complesse delle precedenti. Il capitolo 5 contiene complementi alla teoria degli insiemi che riguardano innanzitutto insiemi ordinati, prodotti cartesiani e equipotenza di insiemi (finiti o infiniti). Cominciamo 1 rilevando l’importanza delle applicazioni in tali questioni. Gli insiemi ordinati offrono un linguaggio flessibile e universale, indispensabile sia nei settori della matematica pura (Algebra, Analisi e Geometria), che di quella applicata (Informatica Teorica, Ottimizzazione, Matematica Finanziaria). Concludiamo il capitolo con un paragrafo che contiene un elenco di tutti gli assiomi necessari per sviluppare correttamente la teoria degli insiemi. Questa appendice, assieme ad una parte degli esercizi, denotati con ∗ possono essere tralasciati durante una prima lettura del testo. Una parte degli assiomi è stata ”assorbita” durante i corsi di Aritmetica e Analisi 1 (l’esistenza di un insieme, di unioni, di coppie e l’insieme delle parti). Qui diamo particolare enfasi all’assioma della scelta (che permette di dimostrare l’esistenza di un buon ordine su ogni insieme) e dell’assioma dell’infinito (che permette di dimostrare l’esistenza di N). Dimostriamo anche il lemma di Zorn, uno dei mezzi universali per stabilire l’esistenza di oggetti con proprietà ottimali in Algebra, Analisi e Geometria. Per dare la possibilità di esercitarsi nell’applicazione di quest’arma potente abbiamo incluso diversi esercizi il cui svolgimento richiede il Lemma di Zorn. Nel capitolo 7 vengono introdotti i numeri primi di Fermat e di Mersenne. Vengono inoltre dati alcuni cenni sulla distribuzione dei numeri primi. Concludono le dispense due capitoli di esercizi, suddivisi in esercizi sugli insiemi ed esercizi sull’aritmetica. 2 Contents 1 Insiemi 1.1 Il concetto di insieme e appartenenza . . . . . . . . . . . . . . . . . 1.2 Unione e intersezione . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Differenza di insiemi . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Un esempio di insieme: i numeri naturali e il principio di induzione 1.5 Prodotti cartesiani finiti . . . . . . . . . . . . . . . . . . . . . . . . 2 Relazioni e funzioni 2.1 Definizione rigorosa di applicazione 2.2 Insiemi finiti e infiniti. . . . . . . . 2.3 Composizione di applicazioni . . . 2.4 Relazioni di equivalenza . . . . . . 2.5 Partizioni e coefficienti binomiali . 2.6 Relazioni di ordine e preordine . . 2.7 Reticoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 I numeri interi e l’aritmetica 3.1 I numeri primi . . . . . . . . . . . . . . . . . . . . . 3.2 Massimo comun divisore e minimo comune multiplo 3.3 La divisione euclidea . . . . . . . . . . . . . . . . . . 3.4 Il teorema fondamentale dell’aritmetica . . . . . . . 3.5 Congruenze in Z . . . . . . . . . . . . . . . . . . . . 3.6 Equazioni congruenziali . . . . . . . . . . . . . . . . 3.7 Criteri di divisibilità per 3, 9, 11, 101 . . . . . . . . . 3.8 I teoremi di Fermat e Eulero . . . . . . . . . . . . . 3.9 Funzione di Eulero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 6 8 9 12 . . . . . . . 12 13 15 15 19 20 22 24 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 25 26 27 29 30 32 33 34 36 4 I numeri razionali, reali e complessi 4.1 I numeri razionali e reali . . . . . . . . . . . . . . . . . . . . . . . 4.2 I numeri complessi . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Interpretazione geometrica delle operazioni tra numeri complessi 4.4 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 38 40 43 44 . . . . . . . 46 46 49 49 49 50 51 55 . . . . . 56 56 57 60 61 63 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Complementi su Insiemi 5.1 Assioma della scelta e buoni ordini . . . . . . . . . . . . . . . . . 5.1.1 Principio dell’induzione transfinita . . . . . . . . . . . . . 5.2 Prodotti cartesiani . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Potenze cartesiani . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Prodotti cartesiani di insiemi non necessariamente uguali 5.3 Numeri cardinali. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Assiomi della teoria degli insiemi. . . . . . . . . . . . . . . . . . . 6 Esercizi su Insiemi 6.1 Esercizi e svolgimento di alcuni esercizi precedenti su 6.2 Esercizi sugli insiemi parzialmente ordinati . . . . . 6.3 Esercizi sui prodotti cartesiani . . . . . . . . . . . . 6.4 Esercizi sugli insiemi ordinati e i prodotti cartesiani 6.5 Esercizi sui numeri cardinali . . . . . . . . . . . . . . 3 insiemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Complementi sui numeri primi 7.1 I numeri di Fermat . . . . . . . . . 7.2 Numeri primi di Mersenne . . . . . 7.3 Numeri perfetti e numeri amicabili 7.4 Distribuzione dei numeri primi . . 7.5 Il gioco di Conway . . . . . . . . . . . . . . . . . . . 8 Esercizi di Aritmetica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 67 68 70 71 72 73 4 1 1.1 Insiemi Il concetto di insieme e appartenenza Il concetto di insieme e appartenenza “∈” sono primitivi e non verranno definiti rigorosamente. Un insieme X è determinato dai suoi elementi x, scriveremo x ∈ X e leggeremo x appartiene a X. Scriveremo spesso anche X = {x : vale P (x)}, dove P (x) è qualche proprietà che descrive gli elementi di X. Nel caso in cui X abbia un numero finito di elementi x1 , x2 , . . . , xn scriveremo X = {x1 , x2 , . . . , xn } (cioè X è determinato dalla lista dei suoi elementi, è importante ribadire che questi elementi sono a due a due distinti). In tal caso X si dice un insieme finito e il numero n dei suoi elementi si denota anche con |X|. Vediamone subito qualche esempio. Esempio 1.1 a) L’insieme di tutti gli studenti dell’Università di Udine. b) L’insieme di tutte le rette del piano. c) L’insieme delle lettere dell’alfabeto inglese. d) L’insieme dei colori dell’arcobaleno. Vediamo ora qualche esempio numerico. Esempio 1.2 a) L’insieme N = {0, 1, 2, 3, 4, . . .} dei numeri naturali. b) L’insieme Z = {0, ±1, ±2, ±3, ±4, . . .} dei numeri interi. c) L’insieme Q dei numeri razionali. d) L’insieme R dei numeri reali. e) L’insieme R+ = {x ∈ R : x > 0} dei numeri reali positivi. f) L’insieme dei numeri primi P = {2, 3, 5, . . .}. Esempio 1.3 a) L’insieme {0, 2, 4, . . .} dei numeri naturali pari si può scrivere anche cosı̀: {x ∈ N : x = 2y per qualche y ∈ N}. b) L’insieme R+ = {x ∈ R : x > 0} dei numeri reali positivi. Essendo ogni insieme completamente determinato dai suoi elementi, due insiemi X e Y coincidono, cioè X = Y , se hanno gli stessi elementi, ovvero, per ogni x ∈ X vale anche x ∈ Y e per ogni y ∈ Y vale anche y ∈ X. Se per due insiemi X e Y è verificata solamente la prima delle implicazione, cioè per ogni x ∈ X vale anche x ∈ Y , diremo che X è sottoinsieme di Y (oppure X è contenuto in Y ), e lo denoteremo con il simbolo X ⊆ Y . In questa circostanza diremo anche Y contiene X e lo denoteremo con il simbolo Y ⊇ X. La condizione x 6∈ ∅ determina un insieme ∅, privo di elementi, che chiameremo l’insieme vuoto. Ovviamente, vale ∅⊆X per ogni insieme X. Infatti, basta trovare una proprietà P tale che nessun elemento di X soddisfa P . Per esempio: ∅ = {x ∈ N : 2x = 5}, ∅ = {x ∈ Q : x2 = 2}, 4 ∅ = {x ∈ R : x = −11}, ∅ = {x ∈ X : x 6= x}. Gli elementi di un insieme possono avere natura del tutto arbitraria. In particolare, possono essere insiemi essi stessi. Per esempio, se X ed Y sono insiemi, possiamo considerare l’insieme Z = {X, Y }, che ha come elementi X e Y . Se abbiamo n insiemi A1 , . . . , An , possiamo considerare l’insieme Z = {A1 , . . ., An }. Spesso ci riferiamo a Z dicendo anche “Z è una famiglia di insiemi” (“famiglia” e “insieme” sono sinonimi). Ecco un esempio di una famiglia infinita di insiemi. Per ogni x ∈ R sia Ax l’intervallo ]x, x + 1[ in R. Allora gli insiemi Ax , al 5 variare di x in R formano una famiglia infinita di insiemi, che denoteremo con {Ax : x ∈ R}. Analogamente, quando si ha una famiglia di insiemi Ai , indiciata con gli elementi i di un insieme di indici I, scriveremo {Ai : i ∈ I}. Dato un insieme X consideriamo la famiglia P(X) di tutte le parti (sottoinsiemi) di X. Questa famiglia si chiama l’insieme delle parti di X. Si noti che P(∅) non è più vuoto, essendo P(∅) = {∅}. Si veda inoltre che P({∅}) = {∅, {∅}}. Esercizio 1.4 Si descriva l’insieme P({1, 2, 3}). Esercizio 1.5 Siano A e B due insiemi. Si dimostri che A ⊆ B se e solo se P(A) ⊆ P(B). 1.2 Unione e intersezione Siano X ed Y due insiemi. L’unione di X e Y è l’insieme X ∪ Y che ha come elementi tutti gli x tali che valga x ∈ X oppure x ∈ Y . In altre parole, X ∪ Y = {x : x ∈ X o x ∈ Y }. Non è difficile vedere che X⊆X ∪ Y e Y ⊆X ∪ Y. (1) L’unione X ∪ Y è il più piccolo insieme che soddisfa la proprietà (1). Infatti se Z soddisfa (1), ovvero, se X⊆Z e Y ⊆Z, allora anche X ∪ Y ⊆Z. Infatti, se x ∈ X ∪ Y , allora si ha x ∈ X o x ∈ Y e in entrambi casi segue x ∈ Z. L’operazione unione gode delle seguenti proprietà: (1) (commutativa) X ∪ Y = Y ∪ X per ogni coppia di insiemi X e Y ; (2) (associativa) (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) per ogni terna di insiemi X, Y e Z; (3) A ∪ A = A per ogni insieme A. L’intersezione di due insiemi X e Y è l’insieme X ∩ Y che ha come elementi tutti gli x tali che vale x ∈ X e x ∈ Y . In altre parole, X ∩ Y = {x : x ∈ X e x ∈ Y }. Possiamo descrivere l’intersezione anche come X ∩ Y = {x ∈ X : x ∈ Y } = {x ∈ Y : x ∈ X}. Due insiemi X e Y si dicono disgiunti se X ∩ Y = ∅. Non è difficile vedere che X ∩ Y ⊆X e X ∩ Y ⊆Y. (2) Esercizio 1.6 Dimostrare che l’intersezione X ∩ Y è il più grande insieme che soddisfa la proprietà (2). Più precisamente, se Z soddisfa (2), ovvero, se Z⊆X e Z⊆Y , allora anche Z⊆X ∩ Y . L’operazione intersezione gode delle seguenti proprietà: (1) (commutativa) X ∩ Y = Y ∩ X per ogni coppia di insiemi X e Y ; (2) (associativa) (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) per ogni terna di insiemi X, Y e Z; 6 (3) A ∩ A = A per ogni insieme A. Si può definire l’unione di una famiglia arbitraria di insiemi F ponendo A per qualche A ∈ F }. S A∈F A = {x : x ∈ Esempio 1.7 L’insieme dei reali R si può vedere come un’unione (infinita) di suoi intervalli S R = x∈ ]x, x + 2[. Questa uguaglianza resta vera se gli intervalli ]x, x + 2[ di lunghezza 2 vengono sostituiti con gli intervalli ]x, x + 1[ di lunghezza 1? Come nel caso dell’unione, si può definire l’intersezione di una famiglia arbitraria di insiemi, T ponendo A∈F A = {x : x ∈ A per ogni A ∈ F }. Vediamo ora alcuni esempi di intersezioni infinite. T Esempio 1.8 ∞ n=1 ]n, +∞[= ∅. Supponiamo per assurdo T che questa intersezione non sia vuota, allora esiste un elemento x ∈ R che appartiene a ∞ n=1 ]n, +∞[. Sia n0 la parte intera di x (n0 = [x]). Allora x non appartiene all’insieme ]n0 +1, ∞[ e pertanto non può appartenere a quell’intersezione. Esercizio 1.9 Si provi che T∞ n=1 ] − n1 , + n1 [ = {0}. Svolgimento. Per dimostrare l’uguaglianza tra due insiemi, si dimostra l’inclusione del primo nel secondo e del secondo nel primo, nota come doppia inclusione. Nel nostro caso Questo dimostra l’inclusione “⊇”. Dimostriamo quindi 0 ∈ ]T− n1 , + n1 [ per ogni n ∈ N, n ≥ 1. T∞ ∞ 1 1 che n=1 ] − n , + n [ ⊆ {0}. Sia x ∈ n=1 ] − n1 , + n1 [. Se x 6= 0, sia |x−1 | = |x|−1 il modulo del suo inverso. Sia n0 = [|x−1 |], allora n0 ≤ |x−1 | < n0 + 1, da cui si ricava |x| > n01+1 e quindi x 6∈] − n01+1 , + n01+1 [. Pertanto se x 6= 0 non può appartenere a quella intersezione, da cui si deduce che l’unico elemento contenuto nell’intersezione è 0. Verifichiamo ora le leggi distributive dell’intersezione rispetto all’unione e dell’unione rispetto all’intersezione. Proposizione 1.10 Siano A, B e C tre insiemi, allora valgono: i) (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C); ii) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C). Dimostrazione. i) Sia x ∈ (A ∩ B) ∪ C, allora o x ∈ (A ∩ B) oppure x ∈ C, cioè o x ∈ A e x ∈ B oppure x ∈ C. Se x appartiene ad A e a B, allora x ∈ A ∪ C e x ∈ B ∪ C. Se x ∈ C, allora x ∈ A ∪ C e x ∈ B ∪ C. Pertanto in ogni caso x ∈ (A ∪ C) ∩ (B ∪ C). Supponiamo ora x ∈ (A ∪ C) ∩ (B ∪ C). Allora x ∈ A ∪ C e x ∈ B ∪ C. Se x non appartiene a C, allora da x ∈ A ∪ C si ricava che x ∈ A e da x ∈ B ∪ C si ricava che x deve stare anche in B. Quindi o x ∈ C oppure x ∈ A ∩ B, cioè x ∈ (A ∩ B) ∪ C. ii) Si lascia per esercizio. Definizione 1.11 Una famiglia {A : A ∈ F } di sottoinsiemi non vuoti A di un insieme X è una partizione di X se S i) X = A∈F A, ii) A ∩ B = ∅ se A, B ∈ F e A 6= B. Vediamone qualche esempio. 7 Esempio 1.12 i) Sia X un insieme. Allora {{x} : x ∈ X} è una partizione di X. ii) Consideriamo i seguenti insiemi X = {studenti dell’Università di Udine}, F = {facoltà presenti presso l’Università di Udine} e sia Xf = {studenti iscritti alla facoltà f ∈ F }. Allora {Xf : f ∈ F } è una partizione di X. iii) L’insieme {[n, n + 1[: n ∈ Z} è una partizione di R. Esercizio 1.13 Provare che qualunque siano gli insiemi S e T risulta a) P(S ∩ T ) = P(S) ∩ P(T ) b) P(S) ∪ P(T ) ⊆ P(S ∪ T ) c) P(S) ∪ P(T ) = P(S ∪ T ) se e solo se S ⊆ T oppure T ⊆ S. Svolgimento. a) P(S ∩ T ) ⊆ P(S) e P(S ∩ T ) ⊆ P(T ) per l’Esercizio 1.5. Per dimostrare l’altra inclusione basta notare che ogni A ∈ P(S) ∩ P(T ) è contenuto sia in S sia in T , e quindi A ⊆ S ∩ T per l’Esercizio 1.6. b) Sia A ∈ P(S) ∪ P(T ), allora A ∈ P(S) oppure A ∈ P(T ), cioè A ⊆ S oppure A ⊆ T , in ogni caso A ⊆ S ∪ T . L’inclusione può essere stretta. Infatti se per esempio S = {0, 1, 2}, T = {0, 3} e A = {1, 3}, si ha A ∈ P(S ∪ T ), ma A 6∈ P(S) ∪ P(T ). c) Se, per esempio, S ⊆ T , S ∪ T = T e P(S) ∪ P(T ) = P(T ). Viceversa supponiamo che P(S)∪P(T ) = P(S ∪T ) e che S 6⊆ T . Pertanto esiste s ∈ S \T . Considero A = {s}∪T ⊆ S ∪T . Allora A 6∈ P(T ) e quindi A ∈ P(S), cioè T ⊆ S. 1.3 Differenza di insiemi La differenza di due insiemi X e Y (detta anche complementare di Y in X) è l’insieme X \ Y che ha come elementi tutti gli x ∈ X tali che x 6∈ Y . In altre parole X \ Y = {x : x ∈ X e x 6∈ Y }. (3) Esempio 1.14 i) Il complementare di Q in R è l’insieme dei numeri irrazionali. ii) Il complementare dei numeri pari in N è l’insieme dei numeri dispari. iii) Il complementare dei numeri dispari nell’insieme dei numeri primi P è {2}. È facile vedere che X \ X = ∅ per ogni insieme X. Più precisamente, si ha: Lemma 1.15 X \ Y = ∅ se e solo se X⊆Y . Dimostrazione. Sia X \ Y = ∅. Se x ∈ X, allora non possiamo avere x 6∈ Y , altrimenti x ∈ X \ Y contrariamente all’ipotesi X \ Y = ∅. Questo dimostra l’inclusione X⊆Y . Viceversa, se X⊆Y , allora non esiste un elemento x ∈ X tale che x 6∈ Y . Pertanto, la proprietà (3) definisce l’insieme vuoto. Esercizio 1.16 X \ Y = X se e solo se X e Y sono disgiunti. Vediamo ora alcune proprietà della differenza: Proposizione 1.17 (Leggi di de Morgan) Sia X un insieme e A ∈ P(X) e F ⊆ P(X). Si dimostri che T S i) A \ B∈F B = B∈F (A \ B); S T ii) A \ B∈F B = B∈F (A \ B). 8 T Dimostrazione. i) Se x ∈ A \ B∈F B, allora x ∈ A ed esiste B0 ∈ F tale che x 6∈ B0 . S Pertanto x ∈ A \ B0 e quindi a maggior ragione x ∈ B∈F (A \ B). Supponiamo viceversa T S x ∈ B∈F (A \ B), allora esiste B0 tale che x ∈ A \ B0 . Pertanto x 6∈ B0 e quindi x 6∈ B∈F B, T cioè x ∈ A \ B∈F B. ii) La dimostrazione è analoga. Esercizio 1.18 Siano S, T e V insiemi. Provare che valgono le proprietà distributive della differenza rispetto all’intersezione e all’unione: a) (S ∩ T ) \ V = (S \ V ) ∩ (T \ V ), b) (S ∪ T ) \ V = (S \ V ) ∪ (T \ V ). c) Mostrare con un esempio che non valgono per la differenza le proprietà associativa e commutativa. Suggerimenti. c) Siano a, b, c tre elementi distinti di un insieme X. Si prendano ad esempio gli insiemi S = {a, b}, T = {a, c} e V = {b, c}. Allora (S \ T ) \ V = ∅ = 6 S \ (T \ V ) = {b} e S \ T 6= T \ S. Esercizio 1.19 Siano A e B due insiemi. Si dimostri che {A \ B, B \ A, A ∩ B} è una partizione di A ∪ B. Esercizio 1.20 Siano A e B due insiemi finiti. Si dimostri che |A ∪ B| = |A| + |B| − |A ∩ B|. Esercizio 1.21 Siano A, B e C tre insiemi finiti. Si dimostri che |A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|. 1.4 Un esempio di insieme: i numeri naturali e il principio di induzione I numeri interi maggiori o uguali a 0 si dicono numeri naturali e si denotano con il simbolo N. Assiomi di Peano. Il matematico italiano Peano (1858-1932) ha proposto la seguente descrizione dell’insieme N dei numeri naturali a partire dei concetti di base N, 0 e s (successore): (P1) 0 ∈ N; (P2) se n ∈ N, allora anche s(n) ∈ N; (P3) se n ∈ N, allora s(n) 6= 0; (P4) se l’insieme E contiene 0 ed ha la proprietà che assieme ad ogni n ∈ E anche s(n) ∈ E, allora N ⊆ E; (P5) s è iniettiva. La più importante proprietà dei numeri naturali è senz’altro il seguente: Assioma del buon ordinamento: ogni insieme non vuoto di numeri naturali possiede un elemento minimo. Si usa la parola assioma perché su questa proprietà (assieme a poche altre) si può fondare una precisa definizione di N. Un’importante applicazione del principio del buon ordinamento è la seguente proposizione. 9 Proposizione 1.22 (Principio di induzione) Supponiamo che S sia un sottoinsieme di N tale che 0 ∈ S e per ogni x ∈ S si ha che anche x + 1 ∈ S. Allora S = N. Dimostrazione. Supponiamo per assurdo che S non sia tutto N. Allora l’insieme N \ S degli elementi di N che non stanno in S è diverso dal vuoto. Quindi per l’assioma del buon ordinamento ammette un elemento minimo, cioè esiste m ∈ N \ S, e poiché 0 ∈ S, si avrà m > 0. Pertanto m − 1 ≥ 0 e m − 1 ∈ S. Allora, per ipotesi, si dovrebbe avere anche m ∈ S. Questa contraddizione prova la proposizione. Proposizione 1.23 Principio di induzione (prima forma) Per ogni n ∈ N, consideriamo un’asserzione A(n) e supponiamo che i) A(0) sia vera; ii) se A(k) è vera, allora anche A(k + 1) è vera. Allora l’asserzione A(n) è vera per ogni n ∈ N. Proposizione 1.24 Principio di induzione (seconda forma) Per ogni n ∈ N, consideriamo un’asserzione A(n) e supponiamo che i) A(0) sia vera; ii) per ogni m > 0, se A(k) è vera per ogni 0 ≤ k < m, allora anche A(m) è vera. Allora l’asserzione A(n) è vera per ogni n ∈ N. Esercizio 1.25 Si dimostrino le proposizioni 1.23 e 1.24. Un’ultima osservazione sul Principio di Induzione: nelle Proposizioni 1.23 e 1.24 si può sostituire nelle ipotesi A(0) con A(n0 ), per qualche n0 ∈ N e la tesi sarà quindi A(n) è vera per ogni n ≥ n0 , n ∈ N . Esercizio 1.26 Usando il principio di induzione, provare che per ogni numero naturale n ≥ 1 risulta: (a) 1 + 2 + 3 + . . . + n = n(n+1) . 2 (b) 12 + 22 + 32 + . . . + n2 = (c) 13 + 23 + 33 + . . . + n3 = (d) 14 + 24 + 34 + . . . + n4 = n(n+1)(2n+1) . 6 n(n+1) 2 2 . n(n+1)(2n+1)(3n2 +3n−1) . 30 (e) 15 + 25 + 35 + . . . + n5 = n2 (n+1)2 (2n2 +2n−1) . 12 (f ) 16 + 26 + 36 + . . . + n6 = n(n+1)(2n+1)(3n4 +6n3 −3n+1) . 42 (g) 17 + 27 + 37 + . . . + n7 = n2 (n+1)2 (3n4 +6n3 −n2 −4n+2) . 24 Esercizio 1.27 Usando il principio di induzione, provare che per ogni numero naturale n risulta: 1 1 1 1 1 + 1 + 2 + ...+ n = 2 − n. 0 2 2 2 2 2 Nel seguito scriveremo la somma a1 + a2 + . . . + an brevemente Σnk=1 ak , dove l’indice k varia da 1 a n e può essere sostituito da qualunque altro carattere, per esempio Σni=1 ai o Σnj=1 aj . In particolare, la somma del punto (c) dell’Esercizio 1.26 è Σnk=1 k3 . Diamo ora alcune regole di calcolo che possono essere utili nel seguito. 10 Esercizio 1.28 Sia m > 2 un numero naturale e sia assegnato un reale akν per ogni numero Pm Pm Pk Pm coppia k, ν con 2 ≤ k ≤ m e 2 ≤ ν ≤ k. Allora k=2 ν=2 ( k=ν akν ). ν=2 akν = Suggerimenti. Si può dimostrare per induzione su m. Altrimenti, basta applicare la legge associativa e la legge commutativa per l’operazione + e notare che le somme sono estese sullo stesso insieme di numeri. Questa “regola di scambio” è molto utile quando ogni addendo è della formaakν = cν d kν e Pm Pm Pk la somma Sν = k=ν dkν ha una forma semplice. In tale caso si avrà k=2 ν=2 akν = Pm ν=2 cν Sν . Esercizio 1.29 Scrivere nella forma abbreviata tutte le somme degli esercizi 1.26 e 1.27. Esercizio 1.30 Usando il principio di induzione, provare che: √ (a) Σnk=1 √1 ≥ n per ogni numero naturale n ≥ 1; k 1 ≥ (b) Σnk=1 n+k 7 12 (c) Σnk=2 k21−1 = 3 4 (d) Σnk=1 kq k−1 = n ≥ 1. per ogni numero naturale n ≥ 2; − 2n+1 2n(n+1) per ogni numero naturale n ≥ 2 ; nq n+1 −(n+1)q n +1 , (1−q)2 dove q è un numero razionale fisso diverso da 1, per ogni Esercizio 1.31 Siano n e a1 < a2 < . . . < an numeri naturali. Provare che (Σnk=1 ak )2 ≤ Σnk=1 a3k . n−1 3 2 Suggerimenti. Ragionando per induzione su n supponiamo di avere (Σn−1 k=1 ak ) ≤ Σk=1 ak . Allora (1 + an−1 )an−1 an (an − 1) an−1 Σn−1 ≤ . (∗) k=1 ak ≤ Σk=1 k = 2 2 n−1 2 3 2 Da (*) si ricava 2 Σn−1 k=1 ak + an ≤ an e di conseguenza 2an Σk=1 ak + an ≤ an . Aggiungendo n−1 n−1 2 n 2 2 3 ad entrambi i membri (Σk=1 ak ) si ha (Σk=1 ak ) ≤ (Σk=1 ak ) + an . L’ipotesi induttiva ci 2 3 n 3 permette di proseguire l’uguaglianza (Σn−1 k=1 ak ) + an ≤ Σk=1 ak . La seconda forma del Principio di Induzione è molto più flessibile. Tuttavia, i seguenti esercizi evidenziano anche i suoi limiti. Esercizio 1.32 Dimostrare che tutti i cavalli sono bianchi. Svolgimento. Basterà dimostrare che tutti cavalli sono dello stesso colore. Poiché tutti abbiamo visto almeno un cavallo bianco, la tesi segue immediatamente. Sia A(n) l’affermazione “in ogni insieme di n cavalli tutti i cavalli sono dello stesso colore”. Ovviamente, A(1) è vera. Ora supponiamo che sia vera A(k) per tutti i k < n. Siano C1 , . . ., Cn dei cavalli. Allora per l’ipotesi induttiva tutti i cavalli C1 , . . . , Cn−1 sono dello stesso colore (diciamo bianchi). Ora applichiamo l’ipotesi induttiva ai cavalli C2 , C3 , . . . , Cn−2 , Cn−1 , Cn e ne deduciamo che anch’essi sono dello stesso colore, che per forza deve essere il colore di Cn−1 . Pertanto, tutti i cavalli C1 , . . . , Cn sono dello stesso colore e quindi A(n) è stata dimostrata. Esercizio 1.33 Trovare l’errore nello svolgimento dell’esercizio precedente. Suggerimenti. L’errore consiste nell’applicazione scorretta del principio di induzione nella seconda forma. Nel passaggio da k < n a n si sfrutta implicitamente il fatto che n > 2 (dove ?), in particolare che A(2) è vera. 11 1.5 Prodotti cartesiani finiti Siano X e Y due insiemi non vuoti. Un coppia ordinata (x, y) consiste di un elemento x ∈ X e un elemento y ∈ Y . É importante il fatto che nella coppia ordinata le due componenti x e y abbiano posizioni ben determinate – prima e seconda componente. Il prodotto cartesiano X × Y di X per Y è l’insieme di tutte le coppie ordinate (x, y), dove x ∈ X e y ∈ Y . Nel caso X = Y l’insieme di tutte le coppie (x, x) con x ∈ X si denota con ∆X e si chiama diagonale di X × X. Scriveremo X 2 per denotare X × X. Siano A1 , A2 , . . . , An degli insiemi non vuoti. Definiamo il prodotto cartesiano A1 × A2 × . . . × An come l’insieme che ha come elementi tutte le n-uple ordinate (a1 , a2 , . . . , an ) con a1 ∈ A1 , a2 ∈ A2 , . . ., an ∈ An . Se tutti gli insiemi A1 , A2 , . . . , An coincidono con un dato insieme A, scriveremo brevemente An per il prodotto cartesiano A1 × A2 × . . . × An . 2 Relazioni e funzioni In questo capitolo introduciamo la definizione di relazione e studiamo vari tipi di relazioni binarie, che godono di certe proprietà. Definizione 2.1 Siano X ed Y insiemi non vuoti. Una relazione binaria tra X e Y è un sottoinsieme R di X × Y . Un primo importantissimo esempio di relazione binaria è l’applicazione. La definizione intuitiva di applicazione è nata nell’ambito degli insiemi di numeri, o altri oggetti concreti, dove la “regola” di “calcolare” f (x) a partire da x può avere senso. Intuitivamente, un’applicazione f : X → Y tra due insiemi X e Y è una regola che permette di assegnare ad ogni elemento x ∈ X un unico elemento f (x) di Y . Le due parole evidenziate sono le parole chiave per definire poi rigorosamente un’applicazione tra due insiemi. Notiamo infatti che la posizione f : R → R definita da f (x) = log x non è un’applicazione perché non è definita su ogni elemento di R. Vediamo ora alcuni esempi: Esempio 2.2 (a) Sia X un insieme non vuoto. L’applicazione idX : X → X definita dalla regola idX (x) = x per ogni x ∈ X si dice identità (o applicazione identica) di X. (b) Sia X un insieme non vuoto. un’applicazione. Allora f : X → P(X) definita da f (x) = {x} è (c) Sia X = {studenti dell’Università di Udine}, allora f : X → N che associa ad ogni studente il suo numero di matricola, è un’applicazione. (d) Se X = {rette del piano}, allora f : X → R ∪ {∞} che associa ad ogni retta il suo coefficiente angolare è un’applicazione. Un’importante esempio di applicazioni sono senza dubbio le funzioni numeriche. Esempio 2.3 (a) La funzione quadrata f : R → R definita da f (x) = x2 . (b) La funzione logaritmica f : R+ → R definita da f (x) = log x. (c) La funzione radice quadrata f : R+ → R+ definita da f (x) = 12 √ x. Il grafico G(f ) di una funzione (applicazione) f : X → Y si definisce come l’insieme di tutte le coppie (x, f (x)) ∈ X × Y con x ∈ X, ovvero G(f ) = {(x, y) ∈ X × Y : y = f (x)}. Chiaramente, il grafico della funzione quadrata f : R → R al punto (a) dell’esempio 2.3 è la parabola {(x, y) ∈ R2 : y = x2 } nel piano R2 , mentre il grafico dell’applicazione identica idX : X → X è la diagonale ∆X di X × X. Non è difficile verificare che il grafico G(f ) è un sottoinsieme del prodotto cartesiano X × Y con le seguenti proprietà: (A1) per ogni x ∈ X esiste una coppia (x, y) ∈ G(f ); (A2) se (x, y) ∈ G(f ) e (x, y ′) ∈ G(f ), allora y = y ′ . 2.1 Definizione rigorosa di applicazione Proponiamo ora una forma astratta del tutto rigorosa basata sulle proprietà (A1) e (A2) del grafico G(f ) di un’applicazione, descritte nel paragrafo precedente. Definizione 2.4 Siano X e Y due insiemi non vuoti. Un applicazione f : X → Y è un sottoinsieme G del prodotto cartesiano X × Y (una relazione) con le proprietà (A1) e (A2), ovvero (A1) per ogni x ∈ X esiste una coppia (x, y) ∈ G; (A2) se (x, y) ∈ G e (x, y ′) ∈ G, allora y = y ′ . L’insieme X si dice dominio dell’applicazione f e l’insieme Y si dice codominio dell’applicazione f . Si noti che ogni applicazione, nel senso della Definizione 2.4, determina una “regola” che permette di “calcolare” f (x) ∈ Y come l’unico elemento y ∈ Y tale che (x, y) ∈ Y . Per A⊆X l’insieme f (A) = {f (a) : a ∈ A} è l’immagine di A. Se a ∈ X, f (a) = f ({a}) si chiama immagine di a secondo f (o valore di f in a). L’insieme f (X) di tutte le immagini degli elementi di X si chiama immagine dell’applicazione f . Per b ∈ Y l’insieme {x ∈ X : f (x) = b} si chiama immagine inversa di b o antimmagine di b e si denota con f −1 (b). Chiaramente, f −1 (b) 6= ∅ se e solo se b ∈ f (X). Per B⊆Y l’insieme {x ∈ X : f (x) ∈ B} si chiama immagine inversa di B e si denota con f −1 (B). Definizione 2.5 Siano X, Y due insiemi non vuoti. L’insieme di tutte le funzioni da X in Y si denota con Y X = {f : X → Y, f funzione }. La seguente definizione introduce tre proprietà molto importanti delle applicazioni. Definizione 2.6 Un applicazione f : X → Y si dice: (a) iniettiva, se per ogni x, y ∈ X l’uguaglianza f (x) = f (y) implica x = y; (b) suriettiva, se per ogni y ∈ Y esiste un x ∈ X tale che f (x) = y; (c) biiettiva, se f è iniettiva e suriettiva. Chiaramente, f : X → Y è iniettiva se e solo se elementi distinti di X hanno immagini distinte in Y . In altre parole, f è iniettiva se e solo se f −1 (b) contiene al più un elemento. D’altra parte, f è suriettiva se e solo se f (X) = Y . 13 Esempio 2.7 Sia X un insieme non vuoto. Allora l’applicazione idX è biiettiva, quindi, iniettiva e suriettiva. Esercizio 2.8 Si dica quale delle applicazioni definite negli esempi 2.2 e 2.3 sono iniettive, suriettive o biiettive. Esercizio 2.9 Sia f : R → R una delle seguenti funzioni. Si dica quale di queste funzioni è iniettiva, suriettiva o biiettiva. √ iii)f (x) = sen(x); i)f (x) = 2x ; ii)f (x) = 3x2 − 5; x se x < 0 iv) f (x) = x2 se x ≥ 0. Teorema 2.10 (Teorema di Cantor) Non esiste un’applicazione suriettiva f : X → P (X), dove X è un insieme non vuoto. Dimostrazione. Supponiamo che esista un’applicazione suriettiva f : X → P (X). Sia A = {x ∈ X : x 6∈ f (x)}. Allora per la suriettività di f esiste x0 ∈ X con f (x0 ) = A. Ma per x0 e A non valgono ne’ x0 ∈ A, ne’ x0 6∈ A – assurdo. Vogliamo sottolineare il ruolo importante delle applicazioni rispetto agli insiemi. A questo scopo faremo vedere come, a partire dalle applicazioni, si possano definire: (a) l’insieme delle parti P(X); (b) le relazioni binarie; (c) i prodotti cartesiani; (d) gli insiemi finiti/infiniti. L’insieme delle parti P(X) è in biiezione con l’insieme 2X di tutte le funzioni X → {0, 1}. Infatti, per A ∈ P(X) consideriamo la funzione caratteristica 1, se x ∈ A . χA (x) = 0, se x ∈ X, x 6∈ A Allora definiamo ϕ(A) = χA . Si vede facilmente, che ϕ è una biiezione (vedi l’Esercizio 6.17) che permette di identificare P(X) con l’insieme 2X delle funzioni caratteristiche. Le relazioni binarie si possono definire facilmente tramite le applicazioni, facendo uso di (a). Infatti, sia R ⊆ X × X una relazione su X. Allora l’applicazione χR : X × X → {0, 1} ci permette di dire che per x, y ∈ X si ha xRy se e solo se χR (x, y) = 1. In altre parole, la relazione R si può ”codificare” tramite un’applicazione X × X → {0, 1}. Nel paragrafo 2.2 vedremo come la distinzione tra insiemi finiti/infiniti si possa fare esclusivamente tramite applicazioni. Nel paragrafo 5.1 verranno definiti gli ordini su un’insieme X a partire da un’applicazione f : P(X) \ {∅} → X con la proprietà f (A) ∈ A per ogni A ∈ P(X) \ {∅}. Nel paragrafo 5.2 le applicazione si usano allo scopo di definire in modo efficace prodotti cartesiani anche di famiglie infinite di insiemi. Nei successivi corsi di Algebra vedremo come il concetto primario dell’algebra, l’operazione, non è altro che un’applicazione A × A → A. 14 2.2 Insiemi finiti e infiniti. Diremo che un insieme X è finito, se X è vuoto o esiste un numero naturale n > 0 e una biiezione {1, 2, . . ., n} → X. Diremo in tal caso che X ha cardinalità n e scriveremo |X| = n. Non è difficile dimostrare per induzione su n = |X| che ogni iniezione X → X di un insieme finito X è anche una suriezione. Nel paragrafo 1.4 è stata introdotta la funzione successore s che non è suriettiva, quindi l’insieme N non è finito. Non è difficile vedere che se abbiamo a disposizione solamente la coppia (N, s) e sappiamo che (P3) e (P4) degli Assiomi di Peano valgono per qualche elemento 0 ∈ N, allora {0} = N \ s(N) e quindi 0 è univocamente determinato dalla coppia (N, s). L’esistenza di una coppia (N, s) che soddisfi gli assiomi di Peano descritti sopra non è scontata. Vedremo in seguito quali sono le condizioni che garantiscono l’esistenza di tale coppia (N, s). Un insieme X si dice infinito, se esiste un’applicazione iniettiva, ma non suriettiva f : X → X. Pertanto, un insieme infinito non è finito. Chiaramente, N è infinito. Dimostriamo ora che l’esistenza di un qualunque insieme infinito permette di costruire la coppia (N, s) dei numeri naturali N e la funzione successore s (vedi anche l’Esercizio 6.38 dove si dimostra che ogni insieme infinito contiene una copia di N, assumendo l’esistenza di N). Teorema 2.11 Sia X un insieme infinito. Allora esiste una coppia (N, s) che soddisfa gli assiomi di Peano e un’applicazione iniettiva h : N → X. Dimostrazione. Sia f : X → X un’applicazione iniettiva, ma non suriettiva a sia x ∈ X \ f (X). Sia A la famiglia di tutti i sottoinsiemi A di X contenenti x e tali che f (A) ⊆ A. T Non è difficile vedere che l’insieme C = A∈A A soddisfa f (C) ⊆ C (essendo ovviamente f (C) ⊆ A per ogni A ∈ A). Quindi, C ∈ A in quanto x ∈ C. Pertanto C è il più piccolo elemento di A. Sia s : C → C la restrizione di f a C. Ovviamente s è iniettiva. Dimostriamo che la coppia (C, s) soddisfa (1) e (2) relativamente all’elemento x ∈ C. Infatti, x 6∈ s(C) è ovvia. Per vedere che vale (2) si noti che ogni insieme E ⊆ C con la proprietà x ∈ E e s(E) ⊆ E necessariamente appartiene a A in quanto f (E) = s(E) ⊆ E. Quindi E = C per la proprietà di C di essere il più piccolo elemento di A. Quindi la coppia (C, s) soddisfa gli assiomi di Peano. Ora come h : C → X possiamo prendere l’inclusione. Teorema 2.12 Un insieme X è infinito se e solo se esiste un’applicazione iniettiva h : N → X. Dimostrazione. Se X è infinito, la tesi segue dalla dimostrazione teorema precedente (vedi anche l’Esercizio 6.38). Supponiamo che esista un’applicazione iniettiva h : N → X. Allora possiamo scrivere X = h(N) ∪ Y , dove Y = X \ h(N). Sia s : N → N l’applicazione definita da s(n) = n + 1. Allora l’applicazione f : X → X, che coincide con h ◦ s ◦ h−1 su h(N) ed è l’identità su Y , è iniettiva, ma non suriettiva. 2.3 Composizione di applicazioni Siano f : X → Y e g : Y → Z due applicazioni tali che il dominio di g coincide con il codominio di f . La composizione di f e g è l’applicazione g◦f : X → Z definita da (g◦f )(x) = g(f (x)) per ogni x ∈ X. La composizione g ◦ f è detta spesso anche applicazione composta (o applicazione prodotto) di f per g. Vediamo ora come la composizione di applicazioni preservi la proprietà di essere iniettiva o suriettiva. 15 Lemma 2.13 Siano f : X → Y e g : Y → Z due applicazioni. (1) se f e g sono suriettive, allora anche g ◦ f è suriettiva; (2) se f e g sono iniettive, allora anche g ◦ f è iniettiva. Dimostrazione. i) Per dimostrare la suriettività di g ◦ f , prendiamo un elemento z ∈ Z del codominio e vogliamo dimostrare che esiste x ∈ X tale che g(f (x)) = z. Poiché g è suriettiva, esiste y ∈ Y tale che g(y) = z. Inoltre poiché f è suriettiva, esiste x ∈ X tale che y = f (x). Pertanto sostituendo y nella precedente uguaglianza, otteniamo proprio z = g(y) = g(f (x)), cioè z = (g ◦ f )(x). ii) Per dimostrare che g ◦ f è iniettiva, supponiamo (g ◦ f )(x) = (g ◦ f )(y) e mostriamo che allora x = y. Dal fatto che g è iniettiva e che g(f (x)) = g(f (y)), otteniamo f (x) = f (y). Dal fatto che pure f è iniettiva, otteniamo ora x = y. Possiamo parzialmente invertire questo risultato. In generale non è vero che se g ◦ f è iniettiva o suriettiva allora anche g ed f lo sono. Infatti Esempio 2.14 Sia X = R \ {0} e sia f : X → X definita da f (x) = x2 . Sia ora g : X → R definita da g(y) = log(|y|). Allora g ◦ f è suriettiva, ma f non è suriettiva. Esempio 2.15 Sia f : N → Z la funzione immersione, cioè f (x) = x e sia g : Z → Z la funzione g(x) = x2 . Allora g ◦ f è iniettiva, mentre g non lo è. Vediamo quindi come possiamo invertire il risultato precedente. Lemma 2.16 Siano f : X → Y e g : Y → Z due applicazioni. (1∗ ) se g ◦ f è suriettiva, allora anche g è suriettiva; (2∗ ) se g ◦ f è iniettiva, allora anche f è iniettiva. Dimostrazione. (1∗ ) Se g ◦ f è suriettiva, per ogni z ∈ Z esiste x ∈ X tale che (g ◦ f )(x) = g(f (x)) = z. Sia dunque y = f (x), allora g(y) = g(f (x)) = z. Questo dimostra che g è suriettiva. (2∗ ) Siano x, y ∈ X tali che f (x) = f (y). Allora (g ◦ f )(x) = g(f (x)) = g(f (y)) = (g ◦ f )(y). Dalla iniettività di g ◦ f , otteniamo x = y. Definizione 2.17 Un applicazione f : X → Y si dice invertibile, se esiste un applicazione g : Y → X tale che g(f (x)) = x per ogni x ∈ X e f (g(y)) = y per ogni y ∈ Y . L’applicazione g di questa definizione di dice inversa di f . Un’applicazione g : Y → X è inversa dell’applicazione f : X → Y se e solo se g ◦ f = idX e f ◦ g = idY . Si vede facilmente dalla definizione, che l’applicazione inversa di un’applicazione invertibile f è unica. Infatti se g ′ fosse un’altra inversa, allora per ogni y ∈ Y si avrebbe g(y) = x = g ′ (y) per l’unico x ∈ X con f (x) = y; pertanto g ′ = g. Denoteremo con f −1 tale unica inversa. Lemma 2.18 Ogni applicazione biiettiva è invertibile. Dimostrazione. Sia f : X → Y un applicazione biiettiva. Per ogni y ∈ Y esiste x ∈ X tale che f (x) = y, poiché f è suriettiva. In più, tale x è unico perché f è anche iniettiva. Poniamo g(y) = x. Adesso è chiaro che f (g(y)) = f (x) = y per ogni y ∈ Y per la definizione di g. D’altra parte, per ogni x ∈ X si ha g(f (x)) = x sempre per la definizione di g. 16 Teorema 2.19 Un’applicazione è invertibile se e solo se è biiettiva. Dimostrazione. Sia f : X → Y un’applicazione. Abbiamo dimostrato nel Lemma 2.18 che se f è biiettiva, allora f è invertibile. Ora resta da vedere che se f è invertibile, allora f è biiettiva. Per ipotesi esiste un’applicazione g : Y → X tale che g ◦ f = idX e f ◦ g = idY . Per l’esempio 2.7 g ◦ f è iniettiva, quindi per (2∗ ) del Lemma 2.16 concludiamo che f è iniettiva. Analogamente, l’Esempio 2.7 ci garantisce che f ◦ g è suriettiva, quindi per (1∗ ) del Lemma 2.16 concludiamo che f è suriettiva. Essendo iniettiva e suriettiva, f risulta biiettiva. Le applicazioni biiettive X → X di un insieme X si dicono anche permutazioni di X. Esercizio 2.20 Verificare che il numero di tutte le applicazioni iniettive di un insieme finito X con n elementi in un insieme Y con m elementi è uguale a m · (m − 1) · . . . · (m − n + 1). Svolgimento. Prima di cominciare notiamo che l’asserto è banalmente vero per m < n, perché in tal caso non ci sono applicazioni iniettive di X in Y , mentre il numero m · (m − 1) · . . .· (m − n + 1) è uguale a 0 essendo il fattore (m − m) = 0. Pertanto, assumeremo nel seguito che m ≥ n. Poiché X è un insieme finito, possiamo numerare i suoi elementi, cioè X = {x1 , x2, ..., xn}. Allora contiamo quali sono le possibili immagini di x1 in Y tramite una applicazione iniettiva. Possiamo scegliere tra tutti gli m elementi di Y . Ci sono pertanto m scelte. Ora l’immagine di x2 può essere un qualsiasi elemento di Y , eccetto l’immagine di x1 , perché l’applicazione deve essere iniettiva. Pertanto si hanno m − 1 scelte per l’immagine di x2 . Proseguendo in questo modo, le possibili scelte per le immagini dell’elemento xi (una volta scelte le immagini degli elementi xj , 1 ≤ j < i) sono m(m − 1)(m − 2)...(m − i + 1). Concludiamo con xn , da cui segue l’enunciato. Questo esercizio dà subito come corollario: Esercizio 2.21 Sia X un insieme finito con n elementi. Si dimostri che il numero di tutte le permutazioni di X è n! = 1 · 2 · . . . · n. Esercizio 2.22 Sia f una funzione da un insieme A in sé. Si supponga che f ◦ f ◦ f = idA . Si può concludere che f è biiettiva? Svolgimento. f ◦ (f ◦ f ) = idA implica che f è suriettiva e che f ◦ f è iniettiva, quindi nuovamente f è iniettiva. Allora f è biiettiva. Esercizio 2.23 Sia f una funzione da un insieme A in sé e sia f∗ : P(A) −→ P(A) la funzione cosı̀ definita f∗ (B) = f (B) = {f (b) : b ∈ B}. Si provi che (a) f è iniettiva se e solo se f∗ è iniettiva, (b) f è suriettiva se e solo se f∗ è suriettiva. Svolgimento. a) Supponiamo che f∗ sia iniettiva. Siano a, b ∈ A tali che f (a) = f (b), allora f∗ ({a}) = f ({a}) = {f (a)} = {f (b)} = f ({b}) = f∗ ({b}). Poiché f∗ è iniettiva, si avrà {a} = {b} e quindi a = b. Sia ora f iniettiva. Supponiamo f∗ (B) = f∗ (C), con B, C ∈ P(A). Supponiamo per assurdo che B non sia contenuto in C. Allora esiste un elemento b ∈ B \ C. Poiché f (b) ∈ f (B) = f∗ (B) = f∗ (C) = f (C), esiste un elemento c ∈ C tale che f (b) = f (c), da cui b = c ∈ C, in 17 contraddizione con quanto supposto. Quindi B ⊆ C e analogamente si prova C ⊆ B, da cui la tesi B = C. b) Supponiamo f∗ suriettiva. Sia y ∈ A, considero C = {y}, esiste B tale che f (B) = C, con B 6= ∅. Pertanto esiste b ∈ B tale che f (b) = c. Sia ora f suriettiva e C ⊆ A. Allora f −1 (C) 6= ∅ e pertanto f (f −1 (C)) = f∗ (f −1 (C)) = C. Esercizio 2.24 Sia f : X −→ Y una funzione e B ⊆ Y . a) Si provi che f (f −1 (B)) ⊆ B, b) Si costruisca un esempio per cui f (f −1 (B)) 6= B. c) Quando vale f (f −1 (B)) = B? Svolgimento. a) Sia x ∈ f −1 (B), allora, per definizione di immagine inversa, si ha che f (x) ∈ B. b) Basta prendere una funzione non suriettiva, per esempio f : Z −→ Z tale che f (x) = x2 e un insieme non contenuto nell’immagine di f , per esempio B = {1, 2}. Allora f −1 (B) = {1, −1} e f (f −1 (B)) = {1} 6= B. c) Quando f è suriettiva. Se b ∈ B, esiste x ∈ A tale che b = f (x) e quindi x ∈ f −1 (B). Esercizio 2.25 Sia A insieme e B sottoinsieme di A, ∅ = 6 B 6= A. Sia f : P(A) −→ P(A) la funzione cosı̀ definita f (X) = B \ X per ogni X ∈ P(A). a) Si provi che f non è né iniettiva né suriettiva, b) si descriva f −1 ({B}). Svolgimento. a) f non è suriettiva perché f (X) ⊆ B, pertanto f (X) 6= A, per ogni X ∈ P(A). f non è iniettiva perché A 6= B e f (A) = ∅ = f (B). b) f −1 ({B}) = P(A \ B). Esercizio 2.26 Sia A insieme e B sottoinsieme di A, ∅ = 6 B 6= A. Sia f : P(A) −→ P(A) la funzione cosı̀ definita f (X) = B ∩ X. a) f è iniettiva? b) f è suriettiva? Se no, se ne trovi l’immagine. c) si descriva f −1 ({B, A, ∅}). Svolgimento. a) No, perché A 6= B e f (A) = B = f (B). b) No, perché f (X) ⊆ B e quindi A 6= f (X) per ogni X ∈ P(A). Allora f (P(A)) ⊆ P(B), ma anzi coincidono poiché se X ∈ P(B) si ha f (X) = X. c) f −1 (B) = {X ∈ P(A) : X ⊇ B}, f −1 (A) = ∅, f −1 (∅) = {X ∈ P(A) : X ∩ B = ∅} = P(A \ B). Esercizio 2.27 i) Siano f1 : X → Y e f2 : X → Y due funzioni. Sia g : Y → Z una funzione iniettiva, allora g è cancellabile a sinistra, cioè se g ◦ f1 = g ◦ f2 , allora f1 = f2 . ii) Siano g1 : Y → Z e g2 : Y → Z due funzioni. Sia f : X → Y una funzione suriettiva, allora f è cancellabile a destra, cioè se g1 ◦ f = g2 ◦ f , allora g1 = g2 . Svolgimento. i) Per ipotesi (g ◦ f1 )(x) = g(f1 (x)) = g(f2 (x)) = (g ◦ f2 )(x) per ogni x ∈ X. Poiché g è iniettiva, si deduce f1 (x) = f2 (x) per ogni x ∈ X, che prova f1 = f2 . ii) Per ipotesi (g1 ◦ f )(x) = g1 (f (x)) = g2 (f (x)) = (g2 ◦ f )(x) per ogni x ∈ X. Sia ora y ∈ Y , allora, poiché f è suriettiva, esiste x ∈ X tale che y = f (x) e quindi g1 (y) = g1 (f (x)) = g2 (f (x)) = g2 (y). Questo prova g1 = g2 . 18 Esercizio 2.28 Sia f : X → Y un’applicazione. Allora f è iniettiva se e solo se esiste una funzione g : Y → X tale che g ◦ f = idX . Svolgimento. Se esiste una funzione g : Y → X tale che g ◦ f = idX , allora nuovamente f è iniettiva per il Lemma 2.16, dato che idY è iniettiva. Supponiamo pertanto che f sia iniettiva. Poiché nella definizione di applicazione si suppone che X non sia vuoto, esiste x0 ∈ X. Inoltre, poiché f è iniettiva, per ogni y ∈ f (X) esiste un unico x ∈ X tale che f (x) = y. Definiamo pertanto g : Y → X ponendo g(y) = g(f (x)) = x se y = f (x) ∈ f (X) e g(y) = x0 , se y 6∈ f (X). Allora g(f (x)) = x per ogni x ∈ X. La controparte di questo esercizio che caratterizza le applicazioni suriettive sarà dimostrata più tardi Esercizio 2.29 Sia f : R → R l’applicazione definita da x+1 se x 6= 1 f (x) = x + x−1 , 0 se x = 1. Si determini se f è iniettiva e se f è suriettiva. 2.4 Relazioni di equivalenza Definizione 2.30 Una relazione binaria R su un insieme X si dice relazione di equivalenza, se sono verificate le seguenti proprietà: 1) (riflessiva) (x, x) ∈ R per ogni x ∈ R; 2) (simmetrica) (x, y) ∈ R implica (y, x) ∈ R per ogni coppia x, y ∈ X; 3) (transitiva) (x, y) ∈ R e (y, z) ∈ R implicano (x, z) ∈ R per ogni terna x, y, z ∈ X; Nel seguito scriveremo brevemente xRy al posto di (x, y) ∈ R. Ogni relazione di equivalenza R definisce le classi di equivalenza [a]R , per a ∈ X, nel modo seguente: [a]R = {x ∈ X : xRa}. Si noti che a ∈ [a]R per la proprietà 1), pertanto le classi [a]R sono non vuote. Se due classi di equivalenza [a]R e [b]R hanno elementi in comune, allora esse coincidono. Infatti, supponiamo che [a]R ∩ [b]R 6= ∅. Poiché ogni x ∈ [a]R soddisfa xRz, dove z ∈ [a]R ∩ [b]R, e quindi xRb e x ∈ [b]R ; analogamente si dimostra che [b]R ⊆ [a]R . Quindi risulta una partizione di X in classi di equivalenza (vedi la definizione 1.11) [ X= [a]R . a∈X Proviamo anzi che questo risultato si può invertire. Teorema 2.31 Esiste una corrispondenza biunivoca tra le relazioni di equivalenza definite su un insieme X e le partizioni di X. Dimostrazione. Abbiamo già dimostrato che ogni relazione di equivalenza su X definisce una partizione di X. Supponiamo ora di avere una partizione L = {Xi : i ∈ I} di X. Definiamo una relazione di equivalenza su X nel modo seguente: xRL y se e solo se x, y ∈ Xi per uno stesso insieme Xi di L. Vediamo che tale relazione è di equivalenza. -riflessiva: poiché L è una partizione, ogni elemento x ∈ X appartiene a qualche Xi , i ∈ I, quindi xRL x. 19 -simmetrica: se xRL y, allora x, y appartengono allo stesso insieme Xi , pertanto vale anche yRL x. -transitiva: se xRL y e yRL z, allora x, y ∈ Xi per qualche i ∈ I e y, z ∈ Xj per qualche j ∈ I. Poiché L è una partizione, avremo Xi ∩ Xj = ∅ se i 6= j. Nel nostro caso y ∈ Xi ∩ Xj , che non può pertanto essere vuota. Allora i = j e x, y, z ∈ Xi , quindi xRL z. Ora, data un’equivalenza R, si consideri la partizione in classi di equivalenza LR = {[a]R : a ∈ X} definita prima. Allora la relazione di equivalenza RLR costruita a partire da LR coincide con R: infatti aRLR b se e solo se a, b ∈ [a]R se e solo se aRb. D’altra parte, per ogni partizione L di X la relazione di equivalenza RL genera, tramite le sue classi di equivalenza, la partizione di partenza L. Questo conclude la dimostrazione. Esempio 2.32 Sia f : X → Y un’applicazione. Allora la relazione binaria Rf definita da xRf y se e solo se f (x) = f (y) è una relazione di equivalenza. Ora vedremo che ogni relazione di equivalenza su un insieme X può essere di questa forma. Teorema 2.33 Sia X un insieme non vuoto e sia R una relazione di equivalenza su X. Allora esiste un’applicazione f : X → Y tale che R coincide con la relazione Rf . Dimostrazione. Sia Y l’insieme delle classi di equivalenza {[x]R : x ∈ X}. Definiamo f : X → Y con f (x) = [x]R . Non è difficile verificare che R = Rf . L’insieme delle classi di equivalenza {[x]R : x ∈ X} si dice insieme quoziente di X modulo la relazione di equivalenza R e si denota con X/R. Esercizio 2.34 Calcolare il numero delle relazioni di equivalenza su un insieme di 2,3,4 o 5 elementi. Suggerimenti. Grazie al Teorema 2.31, è sufficiente calcolare il numero delle partizioni su un insieme di 2,3,4 o 5 elementi. Si lasciano al lettore i primi 3 casi (le risposte sono 2,5 e 15 rispettivamente). Sia ora X = {a, b, c, d, e}. Contiamo le partizioni di X: - 1 del tipo {{a}, {b}, {c}, {d}, {e}}; - 1 del tipo {a, b, c, d, e}, - 5 del tipo {{a}, {b, c, d, e}}, - 10 del tipo {{a, b}, {c, d, e}}, - 10 del tipo {{a}, {b}, {c, d, e}}, - 15 del tipo {{a, b}, {c, d}, {e}}, - 10 del tipo {{a, b}, {c}, {d}, {e}}; per un totale di 52 partizioni e relazioni di equivalenza. 2.5 Partizioni e coefficienti binomiali Ci proponiamo adesso di calcolare il numero di tutte le partizioni di un insieme X di n elementi. Per avere una visione più chiara della situazione vediamo ogni partizione di X come una colorazione di X (in altre parole, vedremo classi di equivalenza come “colori”) Il mondo in bianco e nero. Sia n ≥ 1 un numero naturale e sia X un insieme di n elementi. Allora il numero di tutte le colorazioni di X in due colori, bianco e nero, è uguale 20 a 2n . Infatti ogni colorazione di X si potrebbe considerare come applicazione c : X → C, dove C è l’insieme dei due colori {bianco, nero} in modo di poter vedere il valore c(x) assunto in x ∈ X come il colore (bianco o nero) di x. Notiamo che ogni colorazione c di X è completamente determinata dall’insieme Bc = {x ∈ X : c(x) = bianco} dei punti bianchi di c poiché l’insieme Nc = {x ∈ X : c(x) = nero} dei punti neri di c è precisamente il complemento X \ Bc di Bc (per chi preferisce vedere il mondo in nero, aggiungiamo, che anche l’insieme Nc determina completamente la colorazione c). Inoltre, le colorazioni costanti sono le due colorazioni monocolore: (1) b : X → C con Bb = X e Nb = ∅ (cioè tutto bianco) (2) n : X → C con Nn = X e Bn = ∅ (cioè tutto nero). Le colorazioni suriettive sono quelle che hanno effettivamente tutti e due i colori (cioè non sono monocolore) e sono quindi 2n − 2. Osserviamo che ad ogni colorazione c in due colori corrisponde una partizione di X in due parti disgiunte Bc e Nc , ma ad ogni partizione di X in due insiemi disgiunti Y e Z corrispondono due colorazioni di X che danno la partizione X = Y ∪ Z. Per ogni k con 0 ≤ k ≤ n il numero delle colorazioni c, con insieme “bianco” Bc consistente precisamente di k elementi, è uguale al numero delle k-uple non ordinate in X, che denoteremo nel seguito con Ckn . In particolare, C0n = Cnn = 1. Notiamo che se l’insieme “bianco” Bc ha k elementi, allora l’insieme “nero” Nc consiste di n − k elementi. Analogamente, il numero delle colorazioni c, con insieme “nero” Nc di k elementi, è uguale a Ckn . Poiché le colorazioni con k elementi bianchi sono precisamente le colorazioni con n − k elementi neri, si ricava l’uguaglianza n Ckn = Cn−k . (1) n−1 Ckn = Ckn−1 + Ck−1 . (2) La formula si ricava contando le colorazioni con k elementi bianchi di X fissando un elemento x0 ∈ X. Presentando X come X ′ ∪ {x0 } (dove X ′ è il complemento di {x0 } in X) vediamo che ci sono n−1 colorazioni Ckn−1 colorazioni di X con k elementi bianchi in X ′ (cioè diversi da x0 ) e Ck−1 con k elementi bianchi di cui uno è x0 (queste corrispondono alle colorazioni di X ′ con k − 1 elementi bianchi). Alla fine, ponendo come sempre 0! = 1, si può dimostrare che Ckn = n! k! · (n − k)! (3) per induzione su n. (Per n = 1 è ovvio, se n > 1 si supponga (3) vera per n − 1 esi applichi n n (ma (2).) Il numero Ck va chiamato anche coefficiente binomale e denotato anche con k per motivi tipografici qui preferiamo la forma Ckn ). Il nome “coefficiente binomiale” proviene dalla formula binomiale n X n (a + b) = (4) Ckn an−k bk k=0 che si dimostra facilmente per induzione applicando (2). Ponendo in (4) a = −b = 1 si ha n X (−1)k Ckn = 0. (5) k=0 I coefficienti binomiali si possono disporre in un triangolo illimitato (triangolo di Tartaglia– Pascal) dove (1) e (2) hanno un interpretazione geometrica elegante: 21 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 . . . . . . . . Il primo e l’ultimo coefficiente binomiale su ogni riga del triangolo sono uguali a 1, mentre ogni coefficiente binomiale all’interno del triangolo è somma dei due coefficienti binomiali che gli stanno immediatamente sopra. n di tutte le applicazioni Abbiamo calcolato il numero Vmn = n(n − 1) . . .(n − m + 1) = m! · Cm iniettive di un insieme finito X con n elementi in un insieme Y con m > n (vedi l’Esercizio 2.20). , 2.6 Relazioni di ordine e preordine Definizione 2.35 Una relazione binaria R in un insieme X si dice relazione di preordine, se R è riflessiva e transitiva. Chiaramente, ogni relazione di equivalenza è anche una relazione di preordine. Più precisamente, una relazione di preordine è una relazione di equivalenza se e solo se è simmetrica. Definizione 2.36 Una relazione di preordine R in un insieme X si dice relazione di ordine, se è verificata anche la seguente proprietà • (antisimmetrica) (x, y) ∈ R e (y, x) ∈ R implicano x = y per ogni coppia x, y ∈ X. Esempio 2.37 Sia X un insieme non vuoto. Allora: a) la relazione A ≤ B in P(X) definita da A ≤ B se e solo se B ⊆ A è una relazione di ordine. b) la relazione A B in P(X) definita da A B se e solo se la differenza B \ A è finita è una relazione di preordine. Una relazione di (pre)ordine si denota al solito con ≤, ≺ ecc. Un insieme dotato di una relazione d’ordine si dice un insieme ordinato e due elementi x, y di un insieme ordinato (X, ≤) si dicono confrontabili se x ≤ y oppure y ≤ x. Definizione 2.38 Sia ≤ un ordine su di un insieme X e Y un sottoinsieme non vuoto di X. • l’ordine ≤ si dice totale, se per ogni coppia x, y ∈ X vale x ≤ y o y ≤ x. • un elemento y ∈ Y si dice minimo di Y, se y ≤ z per ogni z ∈ Y ; analogamente un elemento y di Y si dice massimo di Y, se y ≥ z per ogni z ∈ Y ; 22 • un elemento y ∈ Y si dice minimale di Y, se per ogni z ∈ Y si ha che z ≤ y implica y = z; analogamente un elemento y di Y si dice massimale di Y, se per ogni z ∈ Y si ha che y ≤ z implica y = z; • un elemento y ∈ Y si dice minorante di Y, se per ogni z ∈ Y si ha che y ≤ z ; analogamente un elemento y di Y si dice maggiorante di Y, se per ogni z ∈ Y si ha che z ≤ y; • un elemento x di X si dice estremo inferiore di Y in X, se x è il massimo dei minoranti di Y ; analogamente un elemento x di X si dice estremo superiore di Y in X, se x è il minimo dei maggioranti di Y ; • l’ordine ≤ si dice buono, se ogni sottoinsieme non vuoto Y di X ha un elemento minimo. Esercizio 2.39 Dimostrare che ogni insieme non vuoto parzialmente ordinato e finito ammette elementi massimali ed elementi minimali. Suggerimenti. Ragionare per induzione. Esercizio 2.40 Sia ≤ un ordine su un insieme X e Y un sottoinsieme non vuoto di X. Si provi che: a) se Y ha un minimo (massimo), esso è unico; b) se Y ha un estremo superiore (inferiore) in X, esso è unico. Svolgimento. a) Sia a un minimo di X. Se b è un altro minimo, allora a ≤ b e b ≤ a, e pertanto per la proprietà antisimmetrica a = b. b) segue da a) e dalla definizione di estremo superiore (inferiore). Esercizio 2.41 Si provi che se A è totalmente ordinato e a ∈ A, allora a è massimo di A se e solo se a è un elemento massimale di A. Svolgimento. Se a è massimo, a ≥ x per ogni x ∈ A, pertanto se si ha a ≤ b si conclude che a = b, cioè massimale. Viceversa supponiamo a massimale. Sia b un elemento di A, poiché l’ordine è totale a ≤ b oppure b ≤ a. Se a ≤ b, dal fatto che a è massimale si deduce che a = b, pertanto in ogni caso si ha b ≤ a. Esercizio 2.42 Sia N l’insieme dei numeri naturali. Si dimostri che N con la relazione di divisione (n|m se e solo se esiste r ∈ N tale che m = rn) è un insieme parzialmente ordinato che ammette massimo e minimo. Svolgimento. Riflessiva: n|n perché n = 1n, antisimmetrica: n|m e m|n implicano m = rn = r(qm), cioè rq = 1 e r, q ∈ N implicano r = q = 1, cioè m = n, transitiva: n|m e m|l implicano l = qm = q(rn) = (rq)n, cioè n|l. Il minimo deve essere un elemento x di N tale che x|n per ogni n ∈ N, cioè x = 1. Il massimo y invece deve essere tale che n|y per ogni n ∈ N, cioè y = 0. Sia (A, ≤) un insieme parzialmente ordinato. Un sottoinsieme C di A si dice una catena, se (C, ≤) è totalmente ordinato. La lunghezza della catena C è il numero cardinale |C|. 23 Esercizio 2.43 Individuare tutte le catene di lunghezza 4 nell’insieme ordinato per divisibilità di tutti i divisori di 20. Dimostrare che le catene di lunghezza 2 sono 12. Suggerimenti. Le catene di lunghezza 4 sono tre: {1, 2, 4, 20}, {1, 2, 10, 20} e {1, 5, 10, 20}. Infine notiamo che tra tutte le coppie (non ordinate!) di due divisori distinti di 20, solo {2, 5}, {5, 4} e {4, 10} non formano una catena. 2.7 Reticoli Definizione 2.44 Un insieme ordinato (X, ≤) si dice reticolo se per ogni coppia a, b ∈ X l’insieme {a, b} ammette estremo superiore, denotato con a ∨ b, e estremo inferiore, denotato con a ∧ b. Se X ha anche elemento minimo e massimo, essi si denotano solitamente con 0 e 1, rispettivamente. In tal caso il reticolo si dice limitato e si denota con (L, ∧, ∨, 0, 1). Ogni insieme totalmente ordinato è banalmente un reticolo. Esercizio 2.45 Dimostrare che ogni reticolo finito è limitato. Esercizio 2.46 Sia X un insieme non vuoto. L’insieme parzialmente ordinato (P(X), ⊆) è un reticolo limitato. Esercizio 2.47 Sia (X, ≤) un reticolo, allora sull’insieme X X definiamo un ordine parziale nel modo seguente: f, g ∈ X X f ≺g ⇐⇒ f (x) ≤ g(x) per ogni x ∈ X. Si dimostri che (X X , ≺) è un reticolo. Svolgimento. Dimostriamo che dati due elementi f, g di X X , questi ammettono massimo e minimo. Definiamo la funzione h(x) = f (x) ∨ g(x): è ben definita perché X è un reticolo e f (x), g(x) sono due elementi del reticolo. Allora h = f ∨ g. Analogamente per l’estremo inferiore. Esercizio 2.48 Sia (X, ≤) un reticolo e a un suo elemento massimale, allora a è massimo. Svolgimento. Se a è massimale, allora se a ≤ x, si ha a = x per ogni x ∈ X. Sia dunque z ∈ X e sia b = a ∨ z. Allora b ≥ a, quindi a = b, cioè a ≥ z. Concludiamo che a è massimo. Esercizio 2.49 Dimostrare che l’insieme ordinato (N∗ , |) è un reticolo. E’ limitato? Svolgimento. Si ha n ∧ m = M.C.D.(m, n) e n ∨ m = m.c.m.(n, m) in entrambi casi. (N∗ , |) non è limitato perché non ammette massimo che avevamo dimostrato essere lo zero di N. Esercizio 2.50 Si dia un esempio di un reticolo che ha un sottoinsieme ordinato che non è un reticolo. Svolgimento. Consideriamo l’insieme Y di tutti i divisori di 15, ordinato per divisibilità: Y = {1, 3, 5, 15} e a b se e solo se a|b. (Y, |) è un reticolo e non è totalmente ordinato perché 3 6 |5 e 5 6 |3. Il sottoinsieme parzialmente ordinato X = {3, 5} non è un reticolo perché 3 ∨ 5 = 15 non esiste in X. 24 3 I numeri interi e l’aritmetica L’insieme dei numeri interi Z = {0, ±1, ±2, ±3, ...} è il sistema numerico che si impara ad usare fin dalle scuole inferiori, cosı̀ come l’addizione e la moltiplicazione definite su Z. Riterremo pertanto note le proprietà delle due operazioni fondamentali, che verranno comunque riprese in seguito, e anche la relazione di ≤ (minore o uguale di) in base alla quale Z viene ordinato linearmente. La divisione in Z: Dati due numeri interi a e b si dice che a divide b (o, a è divisore di b) se esiste c ∈ Z tale che b = ac e scriviamo a|b. Chiaramente, a) a|0 per ogni a ∈ Z, mentre 0|a solo per a = 0. b) ±1|b e ±b|b per ogni b ∈ Z. Allora “a divide b” definisce una relazione binaria in Z che scriveremo a|b. Se a|b, diremo che a è divisore di b. Se a|b e b|a diremo che a è associato a b e lo denoteremo con a ∼ b. È facile vedere che ∼ è una relazione di equivalenza in Z. L’insieme {1, −1} coincide con la classe di equivalenza di 1. Più in generale, la classe di equivalenza di a ∈ Z coincide con {a, −a}, ovvero b ∼ a se e solo se b = ±a. Poiché ogni b ∈ Z ha come divisori a = ±1 e a = ±b, questi divisori sono chiamati divisori impropri di b. Un divisore a di b si dice proprio se non è improprio. Denoteremo con Z∗ l’insieme dei numeri interi non nulli. 3.1 I numeri primi Un numero b ∈ Z∗ si dice primo, se p 6= ±1 e p non ha divisori propri. I numeri primi servono come “atomi” dai quali si possono ottenere (in modo unico!) tutti gli altri numeri di Z tramite moltiplicazioni. É chiaro che un numero intero m > 1 non è primo se e solo se m = ab con 1 < a < m e 1 < b < m. Il seguente metodo, detto crivello di Eratostene, consente di determinare i numeri primi minori di un numero assegnato n (ragionevolmente piccolo, nel caso 40). Scriviamo in ordine tutti gli interi da 2 a 40. Il primo intero 2 risulta primo non potendo avere dei divisori propri < 2 nella lista. Mettiamolo nella lista dei primi e cancelliamo poi con un tratto 6 di penna tutti i numeri pari > 2 (cioè, i multipli di 2 maggiori di 2). Il primo intero che rimane è 3, che risulta primo per lo stesso motivo di 2. Aggiungiamo 3 alla lista dei numeri primi e cancelliamo con un tratto \ di penna tutti i numeri multipli di 3. Il più piccolo intero che rimane, 5, è primo. Aggiungiamo 5 alla lista, cancelliamo poi con tratto − − di penna tutti i numeri multipli di 5 e cosı̀ via. 2 3 6 4 5 6 67 6 8 9\ 16 0 11 16 2 13 6 14 15 \ 16 6 17 18 6 19 20 6 21 \ 22 6 23 26 4 25 −− 26 6 27 \ 28 6 29 30 6 31 32, 6 33 \ 34 6 35 −− 36 6 37386 Cosı̀ i primi minori di 40 risultano essere 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 e 37. Esercizio 3.1 Determinare i numeri primi minori di 250. Per determinare se un numero a > 0 è primo, si può controllare se è divisibile per qualche primo minore di a. In realtà basta verificarlo su un insieme più piccolo. Infatti: Esercizio 3.2 Se un numero intero a > 0 non è primo, allora a ha divisori primi p minori o √ uguali a a. Osserviamo inoltre che il crivello di Eratostene ci permette di dire, al passo corrispondente a p, quali sono i numeri primi fino a (p + 2)2 − 1, se p è un numero primo dispari. Infatti se il più piccolo primo che divide un numero intero a è q > p, si avrà q ≥ p + 2, da cui 25 a ≥ q 2 > (p + 2)2 − 1. Quindi, per esempio, considerando solo i primi 11 primi, cioè tutti i primi minori o uguali a 31, si possono calcolare tutti i primi minori di 1000. Ci si può quindi chiedere se questo procedimento può terminare dopo un numero finito di passi, ed ottenere quindi tutti i numeri primi. Il Teorema 3.16 ci dara’ la risposta. Quello che abbiamo fatto finora è stato di capire se certi numeri interi sono primi o no. Vediamo ora come si possono “costruire” numeri primi. Esercizio 3.3 Si verifichi che il polinomio f (x) = x2 + x + 17 è un generatore di primi per x ∈ N, x ≤ 15. Il polinomio definito nel precedente Esercizio 3.3 è un caso particolare di una definizione più generale che vedremo più avanti (vedi l’Esercizio 8.8). 3.2 Massimo comun divisore e minimo comune multiplo Definizione 3.4 Il massimo comun divisore d dei numeri interi a e b è definito come un divisore comune di a e b (cioè d|a e d|b) per il quale risulti d′ |d per ogni altro divisore comune d′ di a e b. Chiaramente, se d è massimo comun divisore di a e b, lo è anche −d. Quindi, il massimo comun divisore è determinato solo a meno del segno. Tuttavia, spesso prendiamo in considerazione il massimo comun divisore positivo (a, b) di a e b, che coincide anche con il più grande di tutti i divisori comuni di a e b. Diremo che a e b sono coprimi se (a, b) = 1. Definizione 3.5 Il minimo comune multiplo m dei numeri interi a e b è definito come un multiplo comune di a e b (cioè, a|m e b|m) per il quale risulta m|m′ per ogni altro multiplo comune m′ di a e b. Chiaramente, se m è minimo comune multiplo di a e b, lo è anche −m. Quindi, il minimo comune multiplo è determinato solo a meno del segno. Tuttavia, spesso prendiamo in considerazione il minimo comune multiplo positivo mcm(a, b) di a e b, che coincide anche con il più grande di tutti i multipli comuni di a e b. Vediamo ora alcune altre proprietà dei divisori e del massimo comun divisore. Lemma 3.6 (d1 ) Se c|a e c|b, allora c|ka + mb per ogni scelta di k, m ∈ Z. (d2 ) Se a|a′ e b|b′, allora ab|a′ b′ . (d3 ) Se d|a, d|b e d = ka + mb, allora d è massimo comun divisore di a e b (cioè, d = ±(a, b)). (d4 ) Se d = (a, b), allora a = da1 e b = db1 , con a1 , b1 ∈ Z, coprimi. Dimostrazione. (d1 ) Siano a = cx e b = cy, con x, y ∈ Z. Allora ka + mb = c(kx + my), quindi c|ka + mb. (d2 ) Se a′ = ax e b′ = by, allora a′ b′ = ab(xy). (d3 ) Sia d′ un divisore comune di a e b. Allora d′ |d per il punto (d1 ). Quindi d è massimo comun divisore di a e b. (d4 ) Sia d′ = (a1 , b1 ). Allora d′ |a1 e d′ |b1, quindi dd′ |da1 = a e dd′ |db1 = b per il punto (d2 ). Quindi dd′ è un divisore comune di a e b. Quindi dd′|d. Poiché d|dd′, si conclude che dd′ = ±d, cioè, d′ = 1. 26 3.3 La divisione euclidea Vedremo che una via per stabilire l’esistenza del massimo comune divisore è la proprietà che permette di eseguire la “divisone con resto” (detta anche divisone euclidea) nel modo seguente: Teorema 3.7 Se a, b ∈ Z e b 6= 0, possiamo trovare q, r ∈ Z tali che a = q · b + r e 0 ≤ r < |b|. Dimostrazione. Si considera prima il caso a ≥ 0 e b > 0. Allora, per ogni 0 ≤ a < b possiamo prendere q = 0 e r = a. Se a = b si prende semplicemente q = 1 e r = 0. Supponiamo ora a > b e che tali q ed r si possano trovare per a − 1, cioè a − 1 = qb + r con q ∈ Z e 0 ≤ r < b. Se r < b − 1, allora con 0 ≤ r ′ = r + 1 < b abbiamo a = aq + r ′ . Se invece r = b − 1, allora a = (q + 1)b. Lasciamo al lettore la facile riduzione del caso di a o b negativi al caso a ≥ 0 e b > 0. La divisione con resto è rilevante per i numeri interi, ma non per Q, R e C, perché essi sono campi, e quindi la divisibilità b|a c’è sempre quando b 6= 0 (poiché esiste l’inverso b−1 di b e quindi a = b(b−1a)). Teorema 3.8 Se a, b ∈ Z e b 6= 0, esiste il massimo comun divisore d di a e b ed ha la forma d = ua + vb, con u, v ∈ Z. Dimostrazione. Per il Teorema 3.7 esistono q1 , r1 ∈ Z con a = q1 · b + r1 e r1 < b. Se r1 = 0 abbiamo b|a e quindi d = b = 0 · a + 1 · b. Se r1 > 0 possiamo continuare, esistono q2 , r2 ∈ Z con b = q2 · r1 + r2 e 0 ≤ r2 < r1 . Se r2 > 0 possiamo continuare, esistono q3 , r3 ∈ Z con r1 = q3 · r2 + r3 e 0 ≤ r3 < r2 ; e cosı̀ via. Si costruiscono in questo modo due successioni di interi q1 , q2 , . . . , qk , . . . , e b > r1 > r2 > . . . > rk > . . . (∗) rs−1 = qs+1 rs + rs+1 . (1) tali che Chiaramente, la successione degli rk dovrebbe fermarsi allo 0 dopo al più b passi, cioè esiste k con rk+1 = 0. Allora rk−1 = qk+1 rk , quindi rk |rk−1 . Supponiamo k − 1 > s > 1 e rk |rk−s+1 e rk |rk−s , dimostreremo che allora rk divide anche rk−s−1 . Infatti, basta applicare (1), poiché rk−s−1 = qk−s+1 rk−s + rk−s+1 e rk |rk−s+1 e rk |rk−s per ipotesi. Adesso con s = k − 2 e s = k − 1 ricaviamo rk |r2 e rk |r1. Ma allora rk |b = q2 · r1 + r2 e rk |a = q1 · b + r1 . Ora notiamo che r1 = a−q1 b è combinazione lineare di a e b con coefficienti interi. Supponiamo che r1 , . . . , rs (per 1 ≤ s < k) siano combinazioni lineari di a e b, cioè, per 1 ≤ s < k esistono As , Bs ∈ Z tali che rs = As a + Bs b. Allora rs+1 = rs−1 − qs+1 rs = As+1 a + Bs+1 b, dove As+1 = As−1 −qs+1 As e Bs+1 = Bs−1 −qs+1 Bs . In particolare, con s = k, si ha rk = Ak a+Bk b. Allora, per il punto (d3 ) del Lemma 3.6 , rk è massimo comun divisore di a e b. Corollario 3.9 Sia p primo. Se p non divide un numero intero a, allora p e a sono coprimi. Dimostrazione. Per il Teorema 3.8 esiste il massimo comun divisore d = (p, a). Supponiamo per assurdo che p ed a non siano coprimi Poiché d|p e p è primo, avremo come unica possibilità d = ±p. Ma poiché d|a, e p|d, risulterà p|a – assurdo. Esercizio 3.10 Trovare il massimo comun divisore d di 142 e 96 nella forma d = 142u + 96v. Lo stesso per 212 e 176. 27 Per trovare il massimo comun divisore d tra due numeri naturali a e b e la sua espressione come combinazione lineare di a e b, costruiamo una tabella a 3 colonne. Nella prima riga mettiamo 1, 0, a e nella seconda 0, 1, b e poi mostriamo come si costruisce una riga, conoscendo le due precedenti. 1 0 ... x x′ x − qx′ 0 1 ... y y′ y − qy ′ a b ... z z′ r dove z = qz ′ + r e q è il quoziente della divisione di z per z ′ . Allora ogni riga di questa tabella soddisfa ax + by = z: infatti le prime due righe la soddisfano e se due righe la soddisfano, allora la successiva, per costruzione la soddisfa: a(x − qx) + b(y − qy ′ ) = ax − by + q(ax′ − by ′ ) = z − qz ′ = r. Poiché nell’ultima colonna i valori continuano a diminuire, tale tabella si concluderà con z = 0 e la penultima riga ci darà le informazioni richieste. Esempio 1 0 1 -1 7 0 1 -1 2 -13 156 84 72 12 0 Allora si avrà 12 = M CD(156, 84) e 12 = −1 · 156 + 2 · 84 e 0 = 7 · 156 − 13 · 84. Lemma 3.11 Se a, b, c ∈ Z, c e a sono coprimi e c|ab, allora c|b. Dimostrazione. Essendo 1 = (a, c) possiamo scrivere, per il Teorema 3.8 1 = ua + vc con opportuni u, v ∈ Z. Moltiplicando per b si trova b = uab + vcb. Poiché c|ab e c|c, il punto (d1 ) del Lemma 3.6 implica c|b. Vediamo ora una caratterizzazione importante dei numeri primi, cioè un numero è primo se e solo se ogniqualvolta divide il prodotto di due numeri, in realtà divide già uno dei due numeri. Proposizione 3.12 Un numero intero p 6= 0, ±1 è primo se e solo se per ogni coppia a, b ∈ Z con p|ab si ha p|a o p|b. Dimostrazione. Sia p primo e si supponga che p|ab. Se p non divide a, allora p e a sono coprimi per il Corollario 3.9. Quindi, per il Corollario 3.14, p|ab implica p|b. Supponiamo adesso che p non sia primo. Quindi esistono dei divisori propri a e b di p con p = ab. In tal caso p non divide né a né b, ma ovviamente p|ab. Il minimo comune multiplo può essere definito anche utilizzando la definizione del massimo comun divisore. Teorema 3.13 Se a, b ∈ Z∗ e d è un massimo comun divisore di a e b, allora m = minimo comune multiplo di a e b. 28 ab d è un Dimostrazione. Per il punto (d4 ) del Lemma 3.6 possiamo scrivere a = da1 e b = db1 , con a1 , b1 ∈ Z, coprimi. Allora m = a1 b = b1 a risulta ovviamente un multiplo comune di a e b. Sia m′ un altro multiplo comune di a e b. Allora da a|m′ e b|m′ si deduce m′ = ax e m′ = by con x, y ∈ Z. Quindi, ax = by e di conseguenza da1 x = db1 y. Cancellando d 6= 0 si ha a1 x = b1 y. (2) Per il Lemma 3.11 e (a1 , b1 ) = 1 possiamo concludere che a1 |y e b1 |x. Quindi, y = a1 y1 e x = b1 x1 con opportuni z1 , y1 ∈ Z. Pertanto, m′ = ax = ab1 x1 = mx1 e quindi m|m′ . Corollario 3.14 Se a e b sono coprimi, allora mcm(a, b) = |ab|. In particolare, se a|c e b|c, e a e b sono coprimi, allora anche ab|c. 3.4 Il teorema fondamentale dell’aritmetica In questo paragrafo enunciamo e dimostriamo il Teorema fondamentale dell’Aritmetica che garantisce la fattorizzazione unica in prodotto di numeri primi nel senso seguente. Se p1 p2 . . . pk = q1 q2 . . . qs e p1 , p2 , . . ., pk , q1 , q2 , . . . , qs sono dei numeri primi, allora s = k e dopo una permutazione opportuna dei primi p1 , p2, . . . , pk si ha p1 = ±q1 , . . . , pk = ±qk . Teorema 3.15 Tutti i numeri non invertibili di Z∗ hanno una fattorizzazione unica in prodotto di numeri primi. Dimostrazione. Per un numero intero a 6= 0, ±1 dimostriamo che a ha una fattorizzazione unica in prodotto di numeri primi. Basta considerare il caso a > 0. Ragioniamo per induzione su a. Il caso a = 2 è banale perché 2 è primo. Supponiamo a > 2. Se a è primo, abbiamo finito. Altrimenti esistono b e c in Z con a = bc e 1 < b < a, 1 < c < a. Per l’ipotesi induttiva, entrambi b e c, essendo > 1, sono prodotti di numeri primi. Cosı̀ abbiamo dimostrato l’esistenza della fattorizzazione di a in prodotto di numeri primi. Per dimostrare l’unicità supponiamo che a = p1 . . . pn = q1 . . . qs siano due fattorizzazioni di a in prodotto di numeri primi. Ragioniamo per induzione su n. Se n = 1, avremo p1 = q1 . . . qs , che implica s = 1 poiché p1 è primo. Supponiamo adesso n > 1. Allora p1 divide il prodotto q1 . . . qs e quindi divide uno dei fattori, diciamo q1 . Poiché q1 è primo, concludiamo che q1 = ±p1 . Dopo la cancellazione, abbiamo p2 . . . pn = ±q2 . . . qs . Poiché l’elemento a′ = p2 . . . pn è prodotto di un numero di primi inferiore ad n, l’ipotesi induttiva ci dice che la sua fattorizzazione deve essere unica a meno di permutazione dei fattori, cioè si può supporre s = n e q2 = ±p2 , . . . , qs = ±pn . Sia a > 1, allora il teorema principale dell’aritmetica ci permette di scrivere a = pk11 . . . pks s , con p1 , . . . , ps numeri primi distinti. In questa forma l’unicità della fattorizzazione si può esprimere cosı̀: se a = q1m1 . . . qtmt è un’altra fattorizzazione di a, con q1 , . . . , qt numeri primi distinti, allora t = s, esiste un’opportuna permutazione dei primi p1 , p2, . . . , ps con q1 = ±p1 , . . . , qs = ±ps e m1 = k1 , . . . , ms = ks . Poiché a > 0, possiamo considerare fattorizzazioni con pi > 0 e qj > 0, perciò avremo q1 = p1 , . . . , qs = ps , in altre parole, gli insiemi dei primi {p1 , . . ., ps } e {q1 , . . . , qt} coincidono (quindi t = s) e dopo un riordino dei primi (per esempio in ordine crescente), coincidono persino le s-uple (p1 , . . . , ps ) e (q1 , . . . , qs ) e le s-uple (m1 , . . . , ms) e (k1 , . . . , ks). Tuttavia, in certe situazione ci converrà usare anche fattorizzazioni a = pk11 . . . pks s , con p1 , . . . , ps numeri primi distinti, permettendo di avere anche ki = 0 per alcuni i = 1, 2, . . ., s. 29 Questo diventa comodo quando si lavora con più numeri a, b, c, ... per permettere un confronto tra loro. Scriviamo cosı̀ ms 1 e c = pl11 . . . plss a = pk11 . . . pks s , b = pm 1 . . . ps (4) con p1 , . . . , ps numeri primi distinti e ki ≥ 0, mi ≥ 0 e li ≥ 0 per ogni i = 1, 2, . . ., s. Prima di tutto, osserviamo che per il Corollario 3.14, c|a se e solo se li ≤ ki per ogni i = 1, 2, . . ., s. In particolare, c|a e c|b se e solo se li ≤ ki e li ≤ mi per ogni i = 1, 2, . . ., s. In altre parole, se e solo se li ≤ min{ki , mi} per tutti gli i = 1, 2, . . ., s. Per questo, il massimo comun divisore c di a e b è determinato da li = min{ki, mi} per tutti gli i = 1, 2, . . ., s. Analogamente si ragiona per vedere che il minimo comune multiplo c di a e b deve avere ab ). li = max{ki, mi} per ogni i = 1, 2, . . ., s (o basta applicare la formula M CD(a, b) = (a,b) Possiamo ora rispondere alla domanda posta all’inizio del paragrafo sui numeri primi e cioè quanti numeri primi esistono. Teorema 3.16 (Euclide) Esistono infiniti numeri primi. Dimostrazione. Supponiamo che p1 , p2 , . . . , pn siano tutti i numeri primi e consideriamo il numero N = p1 p2 . . . pn + 1. Poiché p1 , p2 , . . ., pn non dividono N (perché?), N deve essere primo e quindi coincide con uno dei p1 , p2, . . . , pn - assurdo. Possiamo addirittura “specializzare” la forma dei numeri primi, chiedendo per esempio quanti primi di un certo tipo esistono, come nei seguenti esercizi. Esercizio 3.17 Si dimostri che esistono infiniti numeri primi della forma 3k + 2. Svolgimento. Supponiamo che p0 = 2, p1 , p2 , . . ., pn siano tutti i numeri primi del tipo 3k + 2 e consideriamo il numero N = 3p1 p2 . . . pn + 2. Poiché 3 non divide N , i divisori primi di N sono dispari e del tipo 3k + 1 e 3k + 2. Prodotto di numeri del tipo 3k + 1 è dello stesso tipo, quindi almeno uno dei divisori primi q di N è del tipo 3k + 2. Di conseguenza, q coincide con uno dei p0 , p1 , p2 , . . . , pn - assurdo, perché nessun pi può dividere N . Esercizio 3.18 Si dimostri che: a) esistono infiniti numeri primi della forma 6k + 5; b) esistono infiniti numeri primi della forma 4k + 3. 3.5 Congruenze in Z Sia m > 1 un intero. Introduciamo nell’insieme Z la relazione binaria a ≡m b detta congruenza modulo m. Diremo, per definizione, che a è congruo a b modulo m se m divide la differenza a − b. Verifichiamo innanzitutto che ≡m è una relazione di equivalenza su Z: • a ≡m a per ogni a ∈ Z poiché m divide 0 = a − a; • se a ≡m b, allora anche b ≡m a per ogni coppia a, b ∈ Z (poiché m|a − b implica m|b − a = −(a − b); • se a ≡m b e b ≡m c, allora anche a ≡m c (poiché m|a − b e m|b − c implica m|a − c = (a − b) + (b − c)). 30 Vediamo ora quali m sono rilevanti. Ovviamente, per m = 0 si ha a ≡0 b se e solo se a = b, quindi la congruenza ≡0 coincide con la solita uguaglianza “=”. Per m = ±1 abbiamo a ≡m b per ogni coppia a, b. Quindi, ≡m ha una sola classe di equivalenza. Per finire, notiamo che m|a − b se e solo se −m|a − b, quindi le relazioni ≡m e ≡−m coincidono. Per questi motivi in seguito considereremo solo m > 1. Denotiamo con [a]m la classe di equivalenza di a, in altre parole, [a]m = {x ∈ Z : esiste y ∈ Z con x = a + my} = {. . . , a − 2m, a − m, a, a + m, . . .} cioè [a]m è la progressione aritmetica bilaterale di ragione m e punto iniziale a. Si noti che la classe [a]m è infinita, mentre ci sono solo un numero finito di classi di equivalenza. Infatti, questo segue subito dal seguente ovvio lemma: Lemma 3.19 Sia r il resto di a modulo m (i.e., a = qm + r, con 0 ≤ r < m). Allora a ≡m r. Adesso è chiaro che l’insieme Zm = {[0]m, [1]m, . . . , [m − 1]m } presenta tutte le classi di equivalenza modulo m e queste classi sono a due a due distinte (perché k 6≡m r quando 0 ≤ k < m e 0 ≤ r < m). Se n|m, allora a ≡m b implica a ≡n b. Se (n, m) = 1, allora a ≡mn b se e solo se a ≡m b a a ≡n b. Infatti, m|a − b e n|a − b implicano mn|a − b poiché m e n sono coprimi (Corollario 3.14). Le seguenti proprietà delle congruenze sono collegate alle operazioni algebriche in Z: Lemma 3.20 i) se a ≡m a′ e b ≡m b′ , allora anche a + b ≡m a′ + b′ e ab ≡m a′ b′ . ii) se ac ≡m bc e (c, m) = 1, allora anche a ≡m b. Dimostrazione. i) Sia ha m|a − a′ e m|b − b′ . Allora (d1 ) del Lemma 3.6 ci permette di concludere che m|(a − a′ ) + (b − b′ ) = (a + b) − (a′ − b′ ), quindi a + b ≡m a′ + b′ . Per quanto riguarda il prodotto presentiamo la differenza ab − a′ b′ come ab − ab′ + ab′ − a′ b′ = a(b − b′ ) + b′ (a − a′ ). Di nuovo il punto (d1 ) del Lemma 3.6 ci permette di concludere che m|a(b − b′ ) + b′ (a − a′ ) = ab − a′ b′ . Quindi ab ≡m a′ b′ . ii) Dai fatti che m divide ac − bc = (a − b)c ed (m, c) = 1, segue m divide a − b per il Lemma 3.11. Usando le classi di equivalenza, possiamo scrivere (a) anche nel modo seguente: (a∗ ) se [a]m = [a′ ]m e [b]m = [b′]m , allora [a + b]m = [a′ + b′ ]m e [ab]m = [a′ b′ ]m . La proprietà (a∗ ) ci permette di introdurre in Zm due operazioni algebriche nel modo seguente: [a]m + [b]m = [a + b]m e [a]m[b]m = [ab]m. (∗) Infatti, (a∗ ) garantisce che la somma [a + b]m dipende solamente dalle classi [a]m e [b]m e non dai singoli rappresentanti a, b. Esercizio 3.21 Dimostrare per induzione che: (a) l’ultima cifra di 74n+1 è 7. (b) le ultime due cifre di 5n+2 sono 25. (c) l’ultima cifra di 24n+3 è 8. (d) l’ultima cifra di 34n+1 è 3. (e) l’ultima cifra di 42n+3 è 4. 31 (f ) l’ultima cifra di 34n+3 è 7. (g) l’ultima cifra di 74n+2 è 9. (h) l’ultima cifra di 92n+1 è 9. (i) l’ultima cifra di 6n+3 è 6. 3.6 Equazioni congruenziali Consideriamo equazioni congruenziali di primo grado ad una variabile. cioè, dati m > 1, a e b numeri interi fissati, cerchiamo le soluzioni x ∈ Z della congruenza ax ≡m b (1). Ovviamente, se x0 è una soluzione di (1), lo sono anche tutti gli x ≡m x0 . Sia d = (a, m). Allora (1) ha soluzione se e solo se d divide anche b. Infatti, se (1) vale per x, allora m divide la differenza ax − b. Quindi, d divide la differenza ax − b e anche a. Quindi, d divide b. Supponiamo adesso che d divida b e quindi b = db1 per qualche b1 ∈ Z. Per (a, m) = d si trovano numeri interi u, v tali che d = au + mv. Ma allora b = db1 = (au + mv)b1 = a(ub1 ) + mvb1 ≡m a(ub1 ). Pertanto x0 = ub1 è una soluzione di (1). Verifichiamo ora che gli elementi del tipo x0 +n·m/d, al variare di n ∈ Z, sono tutte soluzioni di (1). Infatti am a m ≡m b + n · m · ≡m b, a(x0 + n · ) = ax0 + n · d d d poiché d|a e quindi a/d ∈ Z. Applichiamo questo procedimento ad un caso concreto. Esercizio 3.22 Risolvere l’equazione congruenziale 143x ≡57 17. Svolgimento. Dividendo 143 per 57 troviamo 143 = 2·57+29, poi 57 = 29+28 e 29 = 28+1. Di qui 1 = 29 − 28 = 29 − (57 − 29) = 2 · 29 − 57 = 2 · (143 − 2 · 57) − 57 = 2 · 143 − 5 · 57. Quindi x ≡57 2 · 17 = 34. Un modo più veloce di lavorare è di sostituire subito 143 con il suo resto 29 modulo 57, cioè lavorare in partenza con l’equazione congruenziale 29x ≡57 17. Adesso con 29 ≡57 −28 e 17 ≡57 −40 si trova l’equazione congruenziale −28x ≡57 −40. Poiché 4 e 57 sono coprimi possiamo cancellare 4 e si trova −7x ≡57 −10 e di conseguenza 7x ≡57 10. (∗) Poiché 57 = 8·7+1, abbiamo 8·7 ≡57 −1. Quindi, moltiplicando (*) per 8 si trova 8·7x ≡57 80 e pertanto −x ≡57 23 e x ≡57 −23 ≡57 34. Esercizio 3.23 Trovare tutte le soluzioni in Z126 della seguente equazione congruenziale 30x ≡126 42 Svolgimento. Osserviamo che M CD(30, 126) = 6 divide 42. Pertanto 42 = 6 · 7 = (126 − 30 · 4) · 7 ≡126 30 · (−28), da cui si ricava che le soluzioni sono del tipo x = −28 + z · 126/6. Quindi se cerchiamo tutte le soluzioni in Z126 , queste sono 14, 35, 56, 77, 98, 119. 32 Esercizio 3.24 Trovare tutti gli interi positivi minori di 100 che soddisfano la seguente equazione congruenziale 17x ≡29 3 Svolgimento. Si vede facilmente che gli interi che soddisfano quella congruenza sono del tipo x = 36 + 29z e pertanto si avrà x = 7, 36, 65, 94. Esercizio 3.25 Si trovi il minimo numero naturale n per cui risulti simultaneamente n ≡7 2 n ≡6 1 n ≡5 0 Svolgimento. Dalla prima congruenza ricaviamo n = 2 + 7λ, per qualche λ ∈ Z, che sostituita nella seconda porge n = 2 + 7λ ≡6 1. Pertanto 7λ ≡6 1 − 2, cioè λ ≡6 5 e quindi esiste k ∈ Z tale che λ = 5 + 6k. Sostituendo si ottiene n = 2 + (5 + 6k)7 = 37 + 42k che sostituita nell’ultima dà 37 + 42k ≡5 0 ⇒ 2 + 2k ≡5 0 ⇒ k ≡5 −1 ≡5 4, usando il Lemma 3.20, in quanto (2,5)=1. Allora esiste h ∈ Z tale che k = 4 + 5h e quindi n = 37 + 42k = 37 + 42(4 + 5h) = 205 + 210h. Le soluzioni intere sono quindi del tipo n = −5 + 210m e pertanto si avrà n = 205. Esercizio 3.26 Risolvere le seguenti equazioni congruenziali: a) 4x ≡17 −3; b) 29x + 3 ≡12 0; c) 3x − 8 ≡13 0; d) 7x ≡19 4; f )13x ≡153 178; g)18x ≡51 5 e) 37x ≡117 25; Esercizio 3.27 Trovare i numeri interi x che soddisfano le equazioni congruenziali: x ≡ 2(mod 3), x ≡ 1(mod 4) e x ≡ 3(mod 5). Esercizio 3.28 Determinare le ultime due cifre di 71996 e le ultime tre cifre di 71983. Suggerimenti. Notare che 74 ≡25 1 e 74 ≡8 1. Quindi 74 ≡100 1 e quindi le ultime due cifre di 74k sono . . . 01. Dalla congruenza 74 ≡25 1 dedurre che 720 ≡125 1. Di conseguenza 720 ≡1000 1. Esercizio 3.29 Trovare il resto del numero 34117 modulo 72. 34117 ≡72 (−19)17 ≡72 −(19)16 · 19 ≡72 −((19)2 )8 · 19 ≡72 −(1)8 · 19 ≡72 53. 3.7 Criteri di divisibilità per 3, 9, 11, 101 Sia m > 1 intero. Per ogni numero intero positivo a possiamo trovare il resto a0 nella divisione per m, a = q1 m + a0 . Adesso possiamo trovare il resto a1 di q1 modulo m per avere q1 = q2 m + a1 e di conseguenza a = q2 m2 + a1 m + a0 . Proseguendo in questo modo otteniamo una successione di resti a0 , a1 , a2 , a3 , . . . e di dividendi q1 > q2 > . . . tali che qi = qi+1 m + ai per ogni i = 1, 2, . . . e quindi a = a0 + a1 m + a2 m2 + a3 m3 + . . . + ai mi + . . . + ak mk + qk+1 mk+1 . Poiché la successione qi decresce strettamente, avremo qk+1 = 0 per un certo k, per il quale si avrà a = a0 + a1 m + a2 m2 + a3 m3 + . . . + ai mi + . . . + ak mk . I resti a0 , a1 , a2 , a3 , . . . ak si chiamano cifre di a in base m. In particolare, con m = 10 si hanno le cifre decimali. 33 Proposizione 3.30 Siano a0 , a1 , a2 , a3 , . . ., ak le cifre decimali di a e sia S = a0 + a1 + a2 + . . . + ak . Allora a ≡9 S. In particolare: (a) a è divisibile per 3 se e solo se S è divisibile per 3; (b) a è divisibile per 9 se e solo se S è divisibile per 9. Dimostrazione.(a) Ovviamente 10 ≡9 1, quindi 10i ≡9 1 per ogni i = 1, 2, . . ., k. Moltiplicando per ai si ricava ai 10i ≡9 ai per ogni i = 1, 2, . . . , k. Sommando si ricava a = a0 + a1 10 + a2 102 + . . . + ak 10k ≡9 S. Ora (b) segue immediatamente da (a). Proposizione 3.31 Siano a0 , a1 , a2 , a3 , . . ., ak le cifre decimali di a e sia S = a0 − a1 + a2 + . . . + (−1)k ak = Σki=0 (−1)iai . Allora a ≡11 S. In particolare a è divisibile per 11 se e solo se S è divisibile per 11. Dimostrazione. Poiché 10 ≡11 −1, si ha 10i ≡11 (−1)i per ogni i = 1, 2, . . ., k. Moltiplicando per ai si ricava ai 10i ≡11 (−1)iai per ogni i = 1, 2, . . ., k. Sommando si ricava a = a0 + a1 10 + a2 102 + . . . + ak 10k ≡11 S. La seconda affermazione segue dalla prima. Proposizione 3.32 Siano a0 , a1 , a2 , a3 , . . . , an le cifre decimali di a e sia S = a1 a0 − a3 a4 + . . . + (−1)k a2k+1 a2k + . . . . . . + (−1)[n/2]a2[n/2]+1 a2[n/2] = [n/2] = Σk=0 (−1)k a2k+1 a2k . Allora a ≡101 S. In particolare a è divisibile per 101 se e solo se S è divisibile per 101. Dimostrazione. Ovviamente 100 ≡101 −1, quindi 100i ≡101 (−1)i per ogni i = 1, 2, . . . , k. Pertanto a = a0 + a1 · 10 + a2 · 102 + a3 · 103 + . . . + ai · 10i + . . . + ak · 10k ≡101 a0 + a1 · 10 − a2 + a3 · 10 + a4 + a5 · 10 − . . . (−1)k (a2k+1 + a2k · 10) + . . . . . .+ (−1)[n/2](a2[n/2]+1 + a2[n/2] · 10. La seconda affermazione segue dalla prima. 3.8 I teoremi di Fermat e Eulero Il seguente importante teorema è dovuto a Fermat. Vedremo più avanti come questo sia un caso particolare di un teorema più generale dovuto ad Eulero. Teorema 3.33 (Piccolo teorema di Fermat) Sia p un numero primo. Allora ap ≡p a per ogni numero intero a. Dimostrazione. Se p|a, avremo a ≡p 0 e ap ≡p 0, quindi la congruenza ap ≡p a vale. Possiamo quindi supporre che p non divida a. Allora p e a sono coprimi, quindi la congruenza ap ≡p a è equivalente ad ap−1 ≡p 1, che dimostreremo. Sia R = {1, 2, . . ., p − 1} l’insieme dei resti diversi da 0 modulo p. Definiamo un’applicazione α : R → R nel modo seguente. Per k ∈ R eseguiamo la divisione con resto di ak per p. Si ricava cosı̀ un resto rk soddisfacente ak = qp + rk , e quindi 0 ≤ rk < p e ak ≡p rk per k = 1, 2, . . . p − 1. (1) Poiché k e a sono entrambi coprimi con p, p non può dividere ak e concludiamo che rk 6= 0 in (1). Pertanto possiamo definire α(k) := rk ∈ R. Se rk = ri per i, k ∈ R avremo da (1) ak ≡p rk = ri ≡p ai, e quindi ak ≡p ai. Poiché a è coprimo con p, lo possiamo cancellare. 34 Quindi k ≡p i e per la definizione di R, k = i. Abbiamo cosı̀ verificato che α è un applicazione iniettiva. Quindi l’immagine α(R) dovrà avere p − 1 elementi come R stesso. Essendo α(R) anche un sottoinsieme di R, avremo α(R) = {r1 , r2 , . . ., rp−1 } = R. In particolare, il prodotto r1 · r2 · . . . · rp−1 coincide con 1 · 2 · ... · (p − 1), cioè r1 · r2 · . . . · rp−1 = (p − 1)!. (2) Moltiplicando le p − 1 congruenze in (1) otteniamo ap−1 · 1 · 2 · ... · (p − 1) ≡p r1 · r2 · . . . · rp−1 . Ora (2) ci permette di sostituire r1 · r2 · . . . · rp−1 con (p − 1)! in questa congruenza e ottenere ap−1 · (p − 1)! ≡p (p − 1)!. Essendo (p − 1)! coprimo con p possiamo cancellare (p − 1)! e ricavare ap−1 ≡p 1. Esercizio 3.34 Sia p un numero primo e a un intero coprimo con p. Allora per il teorema di Fermat esiste un numero naturale n > 0 con la proprietà an ≡p 1. Sia k il più piccolo di tali n, allora k ha le seguenti proprietà a) aqk ≡p 1 per ogni intero q ≥ 0; b) se an ≡p 1 per un intero n ≥ 0, allora k divide n. Suggerimenti. a) Basta elevare ak ≡p 1 per la potenza q. Per dimostrare b), si divida n per k con resto r, cioè n = qk + r, con 0 ≤ r < k. Adesso per a) avremo 1 ≡p an = aqk+r = aqk · ar ≡p 1 · ar . Di conseguenza ar ≡p 1. Per la scelta di k si ha r = 0, cioè k divide n. Nel seguito denoteremo con op(a) il numero k definito nell’Esercizio 3.34. Esercizio 3.35 Sia p un numero primo e a un intero coprimo con p. Dimostrare che: a) op (a) divide p − 1; p−1 b) se p > 2, allora a 2 ≡p ±1. p−1 c) se a 2 ≡p −1 allora op (a) = p − 1. Suggerimenti.(a) Applicare il Teorema di Fermat e b) dell’Esercizio 3.34. (b) Poiché p è p−1 p−1 primo e divide ap−1 − 1 = (a 2 − 1)(a 2 + 1), concludiamo che p divide uno dei due fattori. Esercizio 3.36 Dimostrare che 67, 97, 193 e 257 sono numeri primi. Calcolare (a) o67 (2), (b) o97 (2), (c) o193 (2) e (d) o257 (2). √ Suggerimenti. Per verificare che 67 sia primo basta controllare che nessun primo p < 67 (cioè, p = 2, 3, 5 e 7 divide 67). Si procede analogamente con 97, 193 e 257. (a) Da 26 ≡67 −3 ricavare, elevando al quadrato, 212 ≡67 9 e 224 ≡67 14. Moltiplicando la prima e l’ultima congruenza si ricava 230 ≡67 25. Ora moltiplicare per 8 per ottenere 233 ≡67 −1 (e quindi, e 233 6≡67 1). Per gli altri divisori propri 6 e 22 di 66 abbiamo 26 6≡67 1 e 222 6≡67 1. D’altra parte, dall’Esercizio precedente sappiamo che o67 (2) divide 66. Questo ci permette di scrivere o67 (2) = 66 perché ogni divisore proprio di 66 divide uno dei divisori 6, 22 e 33. (b) Da 29 ≡97 27 e 27 ≡97 31 ricavare moltiplicando 216 ≡97 61 ≡97 −36 e elevando al quadrato 232 ≡97 35. Moltiplicando le ultime due congruenze si ottiene 248 ≡97 1. Poiché 216 6≡97 1 e 224 6≡97 1 (spiegare perché!) si conclude che o97 (2) = 48. (c) Per 193 notare che partendo da 210 ≡193 59 e moltiplicando tre volte per 4, ricavando 212 ≡193 43 si ottiene 214 ≡193 −21. Pertanto 216 ≡193 −84 e (elevando al quadrato) 232 ≡193 108. Moltiplicando le due congruenze si ottiene 248 ≡193 −1, che permette di affermare o193 (2) = 96. (d) Per 257 = 28 + 1 si ha 28 ≡257 −1 e quindi 216 ≡257 1. Adesso o257 (2) = 16. 35 3.9 Funzione di Eulero Definizione 3.37 Poniamo ϕ(1) = 1 e per un numero naturale n > 1 poniamo ϕ(n) uguale al numero dei numeri naturali k coprimi con n e soddisfacenti 1 ≤ k ≤ n. La funzione ϕ(n) è nota come funzione di Eulero o funzione totiente. Lemma 3.38 Siano m e n due numeri naturali coprimi tra loro. Allora ϕ(m·n) = ϕ(m)·ϕ(n). Dimostrazione. Dobbiamo dimostrare ϕ(m · n) = ϕ(m) · ϕ(n) per ogni coppia di numeri naturali m ed n coprimi tra loro. In altre parole, bisogna vedere che ci sono precisamente ϕ(m) · ϕ(n) numeri interi x tra 1 ed mn coprimi con mn. Poiché m ed n sono coprimi tra loro, basta assicurarsi che x sia coprimo con m e coprimo con n. Infatti, se x è coprimo con mn, ovviamente x è coprimo anche con m e con n. Viceversa, se x è coprimo con m e coprimo con n, allora ogni divisore comune d di x e mn, essendo (x, m) = 1, deve essere coprimo con m. Quindi, d dovrebbe dividere n e di conseguenza d = ±1 poiché anche (x, n) = 1. Possiamo scrivere ogni numero naturale x tra 1 ed mn come x = ym + z, con 1 ≤ z ≤ m, 0 ≤ y < n. (2) Infatti, dividiamo x per m con il resto: x = qm + r con 0 ≤ r < m. Se r > 0 poniamo y = q e z = r, se r = 0, poniamo y = q − 1 e z = m. Notiamo che x dato da (2) è coprimo con m se e solo se z è coprimo con m. Perciò fissiamo da ora in poi un arbitrario z con 1 ≤ z ≤ m, coprimo con m. Ora vogliamo chiarire per quanti valori di y, 0 ≤ y < n, il numero x determinato da (2) sia coprimo con n. Dividendo x per n con il resto ricaviamo x = qn + ry , dove 0 ≤ ry < n. Notiamo che se y 6= y ′ , allora anche ry 6= ry′ , poiché ry = ry′ implica ym ≡n y ′ m. Poiché (m, n) = 1, questo implica y ≡n y ′ e di conseguenza, y = y ′ . Abbiamo cosı̀ verificato che (x, n) = 1 se e solo se (ry , n) = 1. Poiché tra r0 , r1 , . . . , rn−1 ci sono precisamente ϕ(n) resti coprimi con n, ci saranno ϕ(n) dei numeri definiti in (2) coprimi con n (per z fisso!). Quindi, per ogni z fissato precisamente ϕ(n) tra i numeri x definiti da (2) sono coprimi con n. Quindi, in totale ci sono ϕ(m) · ϕ(n) numeri x tra 1 e mn coprimi con mn. Lemma 3.39 Sia p un numero primo e sia n > 0 un numero naturale. Allora ϕ(pn ) = pn − pn−1 . Dimostrazione. Basta contare quanti sono i numeri k ≤ pn che non sono coprimi con pn . Allora k non è coprimo con pn se e solo se k è divisibile per p. Quindi k = pk1 per qualche k1 ∈ Z. Ora k ≤ pn implica k1 ≤ pn−1 . Ci sono pk−1 numeri k tra 1 e pk che non sono coprimi con pn , da cui ϕ(pn) = pn − pn−1 . Gli ultimi due lemmi permettono di dimostrare: Teorema 3.40 Se m = pn1 1 · pn2 2 · . . . · pns s è la decomposizione di m in prodotto di potenze di numeri primi tra loro diversi, allora ϕ(m) = (pn1 1 − pn1 −1 )(pn2 2 − p2n2 −1 ) · . . . · (pns s − pns s −1 ) = m(1 − Esercizio 3.41 Dimostrare la formula n= X d|n 36 ϕ(d). 1 1 ) . . . (1 − ). p1 ps Svolgimento. Si faccia induzione sul numero s di primi che compaiono nella fattorizzazione di n in primi. Se s = 1, allora n = pk e X ϕ(d) = k X ϕ(pi ) = 1 + i=1 i=0 d|n k X pi−1 (p − 1) = 1 + (p − 1)(1 + p + . . . + pk−1 ) = pk . k s−1 Sia ora n = pn1 1 · pn2 2 · . . . · pks s e poniamo m = pn1 1 · pn2 2 · . . . · ps−1 . Allora i divisori di n sono i tutti i divisori di m e poi tutti i divisori del tipo dps , ove d divide m e 0 < i ≤ ks . Possiamo applicare l’ipotesi induttiva ad m e quindi ! ! ks ks X X X X X X i i ϕ(d)ϕ(p ) = ϕ(dp ) = m + ϕ(d) = ϕ(d) + d|n m+ X d|m d|m ϕ(d) ks X i=1 d|m ϕ(pi) ! i=1 d|m i=1   X ϕ(d) (pks s − 1) = m + m · pks s − m = n. =m+ d|m Il seguente fatto, noto come teorema di Eulero, si dimostra in modo analogo al piccolo teorema di Fermat e come preannunciato ne è una generalizzazione. Teorema 3.42 Teorema di Eulero Se a > 1 e m > 1 sono due numeri naturali coprimi, allora aϕ(m) ≡ 1(mod m). Dimostrazione. Sia R = {1, . . . , m − 1} l’insieme dei resti coprimi con m modulo m. Definiamo un’applicazione α : R → R nel modo seguente. Per k ∈ R dividiamo ak per m con resto. Si ricava cosı̀ un resto rk soddisfacente ak = qp + rk , e quindi 0 ≤ rk < m e ak ≡m rk per k = 1, 2, . . .m − 1. (1) Poiché k ed a sono entrambi coprimi con m, m è coprimo con ak e concludiamo che rk ∈ R. Pertanto possiamo definire α(k) := rk ∈ R. Se rk = ri per i, k ∈ R avremo da (1) ak ≡m rk = ri ≡m ai, e quindi ak ≡m ai. Poiché a è coprimo con m, lo possiamo cancellare. Quindi k ≡m i e per la definizione di R, k = i. Abbiamo cosı̀ verificato che α è un applicazione iniettiva. Quindi l’immagine α(R) dovrà avere ϕ(m) elementi come R stesso. Essendo α(R) anche un sottoinsieme di R, avremo α(R) = {r1 , . . ., rϕ(m)} = R. In particolare, il prodotto r1 · . . . · rϕ(m) coincide con il prodotto Π di tutti i resti in R, cioè r1 · r2 · . . . · rϕ(m) = Π. (2) Moltiplicando le ϕ(m) congruenze in (1) otteniamo aϕ(m) · Π ≡m r1 · . . . · rϕ(m) . Ora (2) ci permette di sostituire r1 · . . . · rϕ(m) con Π in questa congruenza e ottenere aϕ(m) · Π ≡m Π. Essendo Π coprimo con m possiamo cancellare Π e ricavare aϕ(m) ≡m 1. Vediamo ora un altro modo per risolvere le equazioni congruenziali del tipo ax ≡m b, nel caso in cui (a, m) = 1. Si ha infatti, grazie al teorema di Eulero, che aϕ(m) ≡m 1, da cui si ricava a(aϕ(m)−1 b) ≡m b, per cui una soluzione si ottiene immediatamente ponendo x0 = aϕ(m)−1 b. Se si vuole ottenere una soluzione dell’equazione congruenziale anche nel caso generale usando il teorema di Eulero, ci si può poi ridurre al caso appena visto “dividendo” l’equazione per d = (a, m). 37 4 I numeri razionali, reali e complessi 4.1 I numeri razionali e reali Denoteremo con il simbolo Q l’insieme dei numeri razionali, cioè Q = { ab con a, b ∈ Z, b 6= 0}. Anche in questo caso si supporranno note le proprietà dell’addizione e della moltiplicazione definite su Q e le proprietà dell’usuale ordinamento ≤ definito su Q. Vogliamo solo osservare che in Q vale la seguente proprietà: Proprietà di densità: dati x, y ∈ Q, tali che x < y, esiste z ∈ Q tale che x < z < y. Basterà infatti prendere z = x+y 2 . Questa proprietà non vale in Z, ma in compenso in Q non vale una proprietà analoga all’assioma del buon ordinamento. Infatti l’insieme dei numeri razionali positivi non ammette minimo. I numeri reali R sono già stati introdotti nei corsi di Analisi. Osserviamo solamente che anche in R sono definite le operazioni addizione e moltiplicazione e un ordinamento. Supponiamo noto il fatto che si può immaginare Q come un sottoinsieme di R. Denotiamo con ]a, b[ l’intervallo aperto di estremi a e b, cioè ]a, b[= {x ∈ R : a < x < b} e con [a, b] l’intervallo chiuso di estremi a e b, cioè [a, b] = {x ∈ R : a ≤ x ≤ b}. Inoltre [a, b[= {x ∈ R : a ≤ x < b}, ]a, b] = {x ∈ R : a < x ≤ b}, ] − ∞, b] = {x ∈ R : x ≤ b}, ] − ∞, b[= {x ∈ R : x < b}, [a, +∞[= {x ∈ R : x ≥ a}, ]a, +∞[= {x ∈ R : x > a}. Ricordiamo una definizione, per poter descrivere una proprietà importante di R. Definizione 4.1 Un sottoinsieme S di R si dice limitato superiormente se ammette maggioranti, vale a dire se esiste un elemento a ∈ R tale che x ≤ a per ogni x ∈ S. In R vale la seguente proprietà, che non vale in Q. Proprietà di completezza: se S è un sottoinsieme di R, non vuoto e limitato superiormente, allora l’insieme dei maggioranti di S ha minimo. Questo minimo si dice l’estremo superiore. Tra le conseguenze della completezza, citiamo le seguenti: (a) Q è denso in R, cioè se x, y ∈ R e x < y, allora esiste z ∈ Q tale che x < z < y; (b) ogni numero reale è l’estremo superiore di un insieme di numeri razionali; (c) ogni numero reale non negativo è un quadrato, cioè per ogni a ∈ R, a ≥ 0, esiste b ∈ R tale che b2 = a. Il seguente esercizio dà un’idea di come si potrebbe dimostrare il punto (a). Esercizio 4.2 Dimostrare che per ogni numero reale ρ esiste un numero intero n ≥ ρ. Svolgimento. Ragioniamo per assurdo e supponiamo che per qualche numero reale ρ si abbia n < ρ per ogni n ∈ Z. Quindi l’insieme Z è superiormente limitato. Sia σ l’estremo superiore di Z, allora σ − 1, essendo minore di σ non è più un limite superiore per Z, pertanto σ − 1 ≤ n per qualche n ∈ Z e quindi σ ≤ n + 1, assurdo poiché σ è un limite superiore per Z. 38 Definizione 4.3 Per ogni numero reale ρ denotiamo con [ρ] l’unico numero intero n determinato da n ≤ ρ < n + 1. Per l’esercizio precedente, questa definizione è corretta. Esercizio 4.4 Dimostrare che non esistono numeri razionali il cui quadrato è 2. Svolgimento. Supponiamo che esista un numero razionale r con r 2 = 2. Allora r 6= 0 e quindi possiamo scrivere r = a/b, dove a e b sono interi, non entrambi pari (altrimenti possiamo semplificare la frazione). Ora (a/b)2 = 2 ci dà a2 = 2b2 , di conseguenza a2 è pari, e quindi anche a è pari. Sia a = 2a1 , con un intero a1 . Allora 4a21 = 2b2 . Di conseguenza 2a21 = b2 , e quindi b2 è pari. Questo implica che anche b è pari, assurdo. L’Esercizio 4.4 ci permette di asserire che l’insieme Q è strettamente contenuto in R. Gli elementi di tale insieme R \ Q si dicono numeri irrazionali. Esercizio 4.5 Usando il principio di induzione, provare che per ogni x ∈ R, tale che x ≥ −1 e per ogni n ∈ N risulta (1 + x)n ≥ 1 + nx. Esercizio 4.6 Dimostrare che la media aritmetica è maggiore o uguale alla media geometrica. cioè, dati ai ∈ R, con ai > 0, per i = 1, 2, . . ., n si dimostri che √ n a1 · a2 · . . . · an a1 + a2 + . . . + an . n ≤ Svolgimento. Eleviamo tutto alla n e quindi dobbiamo dimostrare la seguente proprietà A(n) a1 + a2 + . . . + an n a1 · a2 · . . . · an ≤ vale per ogni n-upla a1 , . . . , an in R+ . n E’ facile verificare che A(1) ed A(2) sono vere. Verifichiamo ora che A(t) implica A(2t) per ogni t ≥ 1. Infatti, siano a1 , a2 , . . . , a2t numeri reali positivi. Essendo A(t) vera si ha a1 · a2 · . . . · at ≤ a1 + a2 + . . . + at t at+1 · at+2 · . . . · a2t ≤ at+1 + at+2 + . . . + a2t t ma anche t , (1) t , (2) Moltiplichiamo tra loro le disuguaglianze (1) e (2) a1 · a2 · . . . · at · at+1 · at+2 · ... · a2t ≤ a1 + a2 + . . . + at t t at+1 + at+2 + . . . + a2t t · (3) t Considerando ora i due fattori del secondo membro della disuguaglianza cosı̀ ottenuta e utilizzando A(2) già dimostrata, sia ha (prima utilizzo A(2) e poi elevo alla t) a1 + a2 + . . . + at t ≤ t at+1 + at+2 + . . . + a2t t · ≤ t a1 + a2 + . . . + at + at+1 + at+2 + . . . + a2t 2t 39 2t . Mettendo assieme l’ultima disuguaglianza e la disuguaglianza (3), si ottiene la tesi. Adesso supponiamo m > 2 e V (k) vera per tutti i k con 1 ≤ k < m. Consideriamo due casi. Se m = 2t, allora 2 ≤ t < m e quindi possiamo supporre che A(t) sia vera. Per il fatto appena dimostrato, questo implica anche A(2t) vera. Si ottiene, dunque, la tesi nel caso m pari. Supponiamo ora m = 2t − 1, allora 2 < m e quindi 2 ≤ t = (m + 1)/2 < m. Possiamo supporre che A(t) sia vera. Per il fatto appena dimostrato, questo implica anche A(2t) vera. +...+a2t−1 La applicheremo ai numeri a1 , a2 , . . ., a2t−1 , s, dove s = a1 +a22t−1 è la media aritmetica. La disuguaglianza per il caso di 2t fattori ci dà: (a1 + a2 + . . . + a2t−1 ) + s 2t . a1 · a2 · . . . · a2t−1 · s ≤ 2t Ora a1 + a2 + . . . + a2t−1 = s(2t − 1) e quindi sostituisco nel secondo membro della precedente disuguaglianza e divido tutto per s, ottenendo a1 · a2 · . . . · a2t−1 · s s(2t − 1) + s 2t s2t = ≤ . s s · 2t s Eliminando s e risostituendo l’espressione per s otteniamo a1 + a2 + . . . + a2t−1 2t−1 2t−1 . a1 · a2 · . . . · a2t−1 ≤ s = 2t − 1 Esercizio 4.7 Si dimostri che 1 a1 + 1 a2 n +...+ 1 an ≤ √ n a1 · a2 · . . . · an . Suggerimenti. Si usi l’Esercizio 4.6. 4.2 I numeri complessi Nell’insieme delle coppie ordinate dei numeri reali C = R × R definiamo due operazioni di addizione e moltiplicazione ponendo, per ogni z = (a, b), z ′ = (a′ , b′) ∈ C: z + z ′ = (a + a′ , b + b′ ) z · z ′ = (aa′ − bb′, ab′ + ba′ ). Valgono le seguenti proprietà per ogni z = (a, b), z ′ = (a′ , b′), z ′′ = (a′′ , b′′) ∈ C: A1. A2. A3. A4. M1. M2. M3. M4. D1. ′′ z + (z ′ + z ′′ ) = (z + z ′ ) + z (associativa dell’addizione); z + z ′ = z ′ + z (commutativa dell’addizione); z + (0, 0) = z (elemento neutro dell’addizione); (a, b) + (−a, −b) = (0, 0) (opposto); z · (z ′ · z ′′ ) = (z · z ′ ) · z ′′ (associativa della moltiplicazione); z · z ′ = z · z ′ (commutativa della moltiplicazione) ; z · (1, 0) = z (elemento neutro della moltiplicazione); (a, b) · (a/(a2 + b2 ), −b/(a2 + b2 )) = (1, 0) (inverso) ; z · (z ′ + z ′′ ) = z · z ′ + z · z ′′ (distributiva della moltiplicazione rispetto all’addizione). Allora C, con queste due operazioni, risulta essere un campo che chiameremo il campo complesso e definiamo i suoi elementi numeri complessi. 40 L’applicazione j : R −→ C tale che j(a) = (a, 0) è un’applicazione iniettiva che conserva le somme e i prodotti. Questo ci permette di identificare i numeri reali con i numeri complessi della forma (a, 0) e di pensare ad R come a un sottoinsieme (sottocampo) di C. Denotiamo con i l’elemento (0, 1) di C e lo chiamiamo unità immaginaria. Osserviamo che i2 = (0, 1) · (0, 1) = (−1, 0) = −1, in base all’identificazione appena vista. Quindi i e’ una radice quadrata di −1. Ora ogni numero complesso si può scrivere nella forma seguente, utilizzando l’identificazione di R in C. z = (a, b) = (a, 0) + (0, b) = (a, 0) + (b, 0) · (0, 1) = (a, b) = a + bi. In questo modo a si dice la parte reale di z e si denota a = Re(z) e b = Im(z) si dice la parte immaginaria di z. Con questa nuova notazione, risulterà più comodo operare utilizzando le usuali regole del calcolo letterale, ricordando che si ha i2 = −1. √ √ √ Esempio 4.8 (1 + i 2)(7 − i) = (7 + 2) + i(−1 + 7 2), √ √ √ 1 + i3 (1 + i3)(4 + i 2) 4−3 2 12 + 2 √ = √ √ = +i . 18 18 4−i 2 (4 − i 2)(4 + i 2) Definiamo la coniugazione di un elemento z = a + ib come z = a − ib. La coniugazione è un’applicazione che conserva le somme e i prodotti. Inoltre è un’applicazione involutoria, cioè z = z e pertanto è biiettiva e la sua inversa coincide con la coniugazione stessa. Valgono inoltre le seguenti proprietà: z + z = 2Re(z) ∈ R; z − z = 2iIm(z) ∈ iR; z · z = a2 + b2 ∈ R. Fissiamo ora un sistema di coordinate cartesiane ortogonali x, y su un piano che chiameremo piano di (Argand)-Gauss. Ogni numero complesso a+ib si può rappresentare geometricamente con il punto P di coordinate (a, b). Questa assegnazione dà luogo ad una corrispondenza biunivoca tra i punti del piano di Gauss e i numeri complessi. ✻ 0 ✱ y ✱ ✱ ✱ ✱ ✱ ✱ • ✱ ✱ P = (a, b) ✲ x L’asse x è detto asse reale e l’asse y è detto asse immaginario. La distanza di P = (a, b) √ dall’origine, cioè il numero reale non negativo ρ = a2 + b2 è detto il modulo del numero complesso z = a + ib e viene denotato con |z|. Il numero reale ϕ che misura l’angolo orientato 41 formato dal semiasse positivo delle x e dalla semiretta di origine 0 e passante per P viene detto argomento o anomalia di z = a + ib. Osserviamo che ϕ non è determinato se P = 0, cioè se z = 0. Concludiamo che un numero complesso diverso da zero individua univocamente il proprio modulo, ma√determina il proprio argomento solo a meno di multipli interi di 2π. Osserviamo che |z| = z · z e quindi l’inverso del numero complesso z è z −1 = z . |z|2 Dalla definizione di seno e coseno si ha a = ρ cos(ϕ), b = ρ sen(ϕ), z = ρ(cos(ϕ) + isen(ϕ)). Questa è la forma trigonometrica del numero complesso z. La scrittura in forma trigonometrica è molto utile per calcolare il prodotto di due numeri complessi z = ρ(cos(ϕ) + isen(ϕ)) e z ′ = ρ′ (cos(ϕ′ ) + isen(ϕ′ )). z · z ′ = ρ((cos(ϕ) + isen(ϕ)ρ′((cos(ϕ′ ) + isen(ϕ′ ) = = (ρρ′ )[(cos(ϕ)cos(ϕ′) − sen(ϕ)sen(ϕ′ )) + i(cos(ϕ)sen(ϕ′) + sen(ϕ)cos(ϕ′ ))] = =(ρρ′)(cos(ϕ + ϕ′ ) + sen(ϕ + ϕ′ )). Pertanto il prodotto di due numeri complessi ha per modulo il prodotto dei moduli e per argomento la somma degli argomenti. Questo semplice calcolo ha però come corollario una formula che si rivelerà molto utile. Corollario 4.9 Formula di De Moivre Se z = ρ(cos(ϕ) + isen(ϕ)) è un numero complesso scritto in forma trigonometrica, e n ∈ N, allora z n = ρn (cos(nϕ) + isen(nϕ)) Dimostrazione. La dimostrazione è per induzione su n e utilizza la formula del prodotto di due numeri complessi. Una conseguenza della formula di De Moivre è il calcolo delle soluzioni dell’equazione in xn = w, w ∈ C. Infatti z è soluzione di quest’equazione, e si dice che z è radice n-esima di w, se e solo se z n = w. Pertanto se 0 6= z = ρ(cos(ϕ) + isen(ϕ)) e 0 6= w = τ (cos(ϑ) + isen(ϑ)), dalla formula di de Moivre si deduce ρ= Pertanto se zk = √ n √ n τ ϕ = (ϑ + 2kπ)/n, k ∈ Z. ϑ + 2kπ ϑ + 2kπ + isen τ cos n n si ha che zk è un radice n-esima di w per ogni k ∈ Z. Sia ora k ∈ Z, facciamo la divisione con il resto tra k ed n, otteniamo k = qn + r, con 0 ≤ r ≤ n − 1 e quindi zk = zr . Inoltre zk = zh se e solo se k − h ∈ nZ. Pertanto z0 , z1 , z2 , . . . , zn−1 sono n radici distinte di w. Abbiamo cosı̀ provato Lemma 4.10 Ogni numero complesso w 6= 0 ammette n radici n-esime distinte, per ogni 0 6= n ∈ N. Esse sono rappresentate nel piano di Argand-Gauss p dai vertici di un poligono n regolare di n lati inscritto nella circonferenza di centro 0 e raggio |w|. Osserviamo infine che w = 0 ha un’unica radice n-esima z = 0. 42 4.3 Interpretazione geometrica delle operazioni tra numeri complessi Ci sono facili interpretazioni geometriche di tutte e tre le operazioni tra numeri complessi. L’addizione corrisponde alla traslazione. Infatti, il punto z + b si ottiene dal punto z tramite la traslazione definita dal vettore con inizio l’origine 0 e con punto finale il punto rappresentato da b. Se a è un numero complesso con |a| = 1, allora la moltiplicazione per a corrisponde alla rotazione (in senso antiorario e con centro 0) di angolo ϕ uguale all’argomento di a. Se invece r = |a| è arbitrario, ma positivo, allora la moltiplicazione per a corrisponde alla rotazione di centro 0 ed angolo ϕ seguita dalla dilatazione di centro 0 e coefficiente r. La coniugazione corrisponde alla simmetria di asse 0x. La retta definita dall’origine e dal punto z è precisamente il luogo determinato da tutti i numeri complessi del tipo λz, dove λ ∈ R. I punti del segmento [0, z] sono ottenuti con 0 ≤ λ ≤ 1, mentre quelli della semiretta con inizio z che non contiene l’origine 0, con λ ≥ 1 (e quelli della semiretta con inizio 0 che non contiene z, con λ ≤ 0). Il punto medio del segmento [0, z] è proprio 12 z. Esercizio 4.11 Siano z1 e z2 due punti distinti del piano di Gauss-Argand. Determinare i numeri complessi che corrispondono ai punti della retta che passa per z1 e z2 . Suggerimenti. Traslando per −z1 la retta l in questione diventa una retta che passa per l’origine e per il punto z2 − z1 , ed è pertanto definita dai punti {λ(z2 − z1 ) : λ ∈ R}. Ora traslando questa retta per z1 troviamo che la retta l è definita dai punti z1 + λ(z2 − z1 ) = (1 − λ)z1 + λz2 per λ ∈ R. I punti del segmento [z1 , z2 ] sono ottenuti con 0 ≤ λ ≤ 1, ecc. Esercizio 4.12 Siano z1 e z2 due punti distinti del piano di Gauss-Argand. Dimostrare che 2 il punto medio del segmento [z1 , z2 ] corrisponde al punto z1 +z 2 . Esercizio 4.13 Usando queste espressioni delle rette dimostrare che le tre mediane di un triangolo si intersecano in un solo punto che le divide in rapporto 2 : 1. Suggerimenti. Rappresentiamo il triangolo nel piano di Gauss-Argand. Traslandolo possiamo supporre, senza ledere la generalità, che uno dei vertici coincida con l’origine 0 e pertanto i vertici del triangolo saranno 0, a e b con a, b ∈ C. Usando gli esercizi precedenti, si vede facilmente che i punti della mediana che passa per 0 sono della forma µ a+b 2 , mentre i punti della mediana che passa per b sono della forma λ a2 + (1 − λ)b, dove µ, λ ∈ R. Il punto m dell’intersezione di queste due mediane corrisponde a valori di µ e λ che soddisfano µ λ a2 + (1 − λ)b = µ a+b 2 . Questo ci dà (µ/2 − λ/2)a + ( 2 + λ − 1)b = 0. Poiché i vettori a e b sono linearmente indipendenti, abbiamo µ/2 − λ/2 = 0 e µ2 + λ − 1 = 0. Di conseguenza µ = λ = 2/3. Si noti che il punto di intersezione m = a+b 3 divide entrambe le mediane in rapporto 2 : 1. b ✑ ✑ ❙ ✑ ❙ ✑ ❙ ✑ m ✑ ❙ a+b PP PP ❙2 0 PP ❙ a PPP ❙ P 2 PP ❙a 43 Analogamente si dimostra che la mediana che passa per il punto a passa anche per il punto m. Esercizio 4.14 Dimostrare che quattro punti a, b, c, d del piano di Gauss-Argand formano un parallelogramma se e solo se a + c = b + d. Esercizio 4.15 Dimostrare che i punti medi dei quattro lati di un quadrangolo formano un parallelogramma. Suggerimenti. Se a, b, c, d sono i quattro vertici di un quadrangolo, i punti medi sono d+a b+c c+d 2 , 2 e 2 . Ora basta applicare l’Esercizio precedente. a+b 2 , Esercizio 4.16 Dimostrare che i punti medi di due lati opposti di un quadrangolo e i punti medi delle sue diagonali formano un parallelogramma. Esercizio 4.17 Siano a e b due punti del piano di Gauss-Argand. Dimostrare che l’area del triangolo determinato da a, b e l’origine coincide con 14 |ba − ab|. ϕ Suggerimenti. L’area S del triangolo coincide con il prodotto |a|·|b|·sin , dove ϕ è l’angolo tra 2 0a e 0b in senso antiorario. L’angolo ϕ coincide anche con l’argomento del numero complesso z = b/a, perciò z −z (b/a − b/a)|a| z = = . sin ϕ = Im |z| 2|z|i 2|b|i Di conseguenza, S = |a|2 ·(b/a−b/a) 4i = ab−ab 4i . Questo è il valore “algebrico” dell’area, che può essere negativo se ϕ < 0. Il valore assoluto dell’area è 4.4 |ab−ab| . 4 Esercizi Esercizio 4.18 Esprimere nella forma x + iy i seguenti numeri complessi Svolgimento. 7 − i6 4 33 = − −i ; 2 + i3 13 13 7−i6 2i 2+i3 , (2+i)2 . 2i 8 6 = + i . (2 + i)2 25 25 Esercizio 4.19 Si scrivano in forma trigonometrica 2−2i 3+3i , √ √ −7 3, (1 + i 3)2 . Svolgimento. 3 3 2 2 2 − 2i =− i= −7 = 7(cosπ + isen(π)); cos π + isen π ; 3 + 3i 3 3 2 2 √ √ 2 √ 3 1 2 2 (1 + i 3) = (1 − 3 + i2 3) = 4 − + i = 4 cos π + isen π . 2 2 3 3 Esercizio 4.20 Si calcolino e si disegnino sul piano di Argand-Gauss le radici quarte dell’unità. Suggerimenti. Le radici quarte dell’unità sono i, −1, −i, 1. √ √ Esercizio 4.21 Si calcolino (1 + i)6 , (1 + i)86, (1 + i 3)42 , ( 3 − i)210. 44 √ √ Svolgimento. Per fare questi calcoli ricordiamo che (1/ 2 + i/ 2) è una radice ottava dell’unità, cos(π/3) + isen(π/3) è radice sesta dell’unità e cos(11π/6) + isen(11π/6) è radice dodicesima dell’unità. √ (1 + i)6 = [ 2(cos(π/4) + isen(π/4))]6 = 8(cos(6π/4) + isen(6π/4) = −8i, (1 + i)86 = [(1 + i)2 ]43 = (2i)43 = −243 i, √ 42 (1 + i 3) = [2(cos(π/3) + isen(π/3)]42 = 242 [(cos(π/3) + isen(π/3)6 ]7 = 242 , √ ( 3 − i)210 = [2(cos(11π/6) + isen(11π/6))]210 = = 2210 [(cos(11π/6)+isen(11π/6)6]35 = 2210 (−1)35 = −2210 . Un modo più veloce di fare questi calcoli è osservando che, per esempio (1 + i)2 = 2i o che √ √ √ (1 + i 3)3 = 1 + 3 3i − 3 · 3 − i3 3 = −8, o infine √ √ √ ( 3 − i)3 = 3 3 − 9i − 3 3 − i = 8i. Esercizio 4.22 Sia z = ρ(cos(ϕ) + isen(ϕ)) ∈ C. Si scrivano in forma trigonometrica z e z −1 . Svolgimento. z = ρ(cos(−ϕ) + isen(−ϕ)) z −1 = ρ−1 (cos(−ϕ) + isen(−ϕ)). Esercizio 4.23 Si calcolino in C e si disegnino sul piano di Argand-Gauss le soluzioni delle seguenti equazioni x4 + i = 0, x3 − 2i = 0. Svolgimento. Sia z = ρ(cos(ϕ) + isen(ϕ)) ∈ C soluzione dell’equazione x4 + i = 0. Allora ρ4 = 1, 4ϕ = 3/2π + 2kπ =⇒ ρ = 1, ϕ = 3π/8 + kπ/2. Sia ora z = ρ(cos(ϕ) + isen(ϕ)) ∈ C soluzione dell’equazione x3 = 2i. Allora √ 3 ρ3 = 2, 3ϕ = π/2 + 2kπ =⇒ ρ = 2, ϕ = π/2 + 2kπ/3. Esercizio 4.24 Si calcolino (1 − i)28, i−1 . √ Esercizio 4.25 Si scrivano in forma trigonometrica i seguenti numeri complessi 3 5i, 5−5i. Esercizio 4.26 Esprimere nella forma x + iy i seguenti numeri complessi √ 1−i3 (2− 5i)2 , . 3−i4 3i Esercizio 4.27 Calcolare (1-i)179. Svolgimento. Sia a = 1 − i, allora a2 = −2i e a4 = −4. Pertanto, a179 = a4·44 · a2 · a = 444 · (−2i) · (1 − i) = −289 (1 + i). Esercizio 4.28 Calcolare (1-i)79 . Esercizio 4.29 Dimostrare che per ogni numero naturale n ≥ 1 risulta: 4n 4n 4n 4n 4n 4n 4n 4n (a) + + +... = + + +. . . . 1 5 9 4n − 3 3 7 11 4n − 1 12n + 6 12n + 6 12n + 6 12n + 6 12n + 6 12n + 6 + + = +. . . + + (b) 1+ 6 2 12n + 4 12 4 8 12n + 6 12n + 6 +... . 10 12n + 6 Suggerimenti. (a) Si applichi la formula del binomio per (1 + i)4n. 45 5 5.1 Complementi su Insiemi Assioma della scelta e buoni ordini Vogliamo dimostrare che ogni insieme non vuoto ammette una relazione di buon ordine. Ovviamente, ogni insieme finito X ammette un buon ordine, quello dato dalla biiezione {1, 2, . . ., n} → X, dove n = |X| (vedi l’Esercizio 6.10 per il caso numerabile). Il caso generale è noto come Teorema di Zermelo. Ogni insieme non vuoto ammette una relazione di buon ordine. La dimostrazione di questo teorema richiede un’assioma detto l’Assioma della scelta. Esso può essere formulato in varie forme equivalenti. Solitamente si usa questa: Assioma della scelta. Sia {Ai }i∈I una famiglia di insiemi non vuoti con I 6= ∅. Allora S esiste un’applicazione f : I → i∈I Ai tale che f (i) ∈ Ai per ogni i ∈ I. Definizione 5.1 L’applicazione f con questa proprietà si chiama funzione di scelta per la famiglia {Ai }i∈I . Quindi, l’Assioma della scelta afferma che ogni famiglia non vuota di insiemi non vuoti ammette una funzione di scelta. Nel 1908 Zermelo propose una versione diversa dell’assioma della scelta, con la richiesta che gli insiemi Ai fossero a due a due disgiunti. Russell provò nello stesso anno che le due forme sono equivalenti. In questo paragrafo utilizzeremo anche la seguente forma equivalente. Lemma 5.2 L’assioma della scelta è equivalente alla seguente affermazione: (∗) per ogni insieme non vuoto X esiste un’applicazione f : P(X)\{∅} → X tale che f (A) ∈ A per ogni ∅ = 6 A ∈ P(X). Dimostrazione. Ovviamente, l’assioma della scelta implica (∗), prendendo come famiglia non vuota di insiemi non vuoti proprio P(X) \ {∅}. Per dimostrare che (∗) implica l’Assioma della scelta basta prendere una famiglia {Ai }i∈I d̀i insiemi non vuoti con I 6= ∅. Sia X = S i∈I Ai e sia j : I → P(X) \ {∅} definita da j(i) = Ai . Allora (∗) applicata a X e composta con j, determina una funzione di scelta per la famiglia {Ai }i∈I . Per capire bene la relazione tra l’Assioma della scelta e il Teorema di Zermelo vediamo che il Teorema di Zermelo implica l’Assioma della scelta. Infatti, se X è un’insieme non vuoto e ≤ è un buon ordine su X, allora basta porre f (A) = min A per ogni A ∈ P(X) \ {∅}. In altre parole, ogni buon ordine ≤ su X determina un’applicazione f : P(X) \ {∅} → X, tale che f (B) ∈ B per ogni B ⊂ X. (1) cioè una funzione scelta per la famiglia P(X) \ {∅} (vedi l’Esercizio 6.45 per un’altra dimostrazione). Possiamo ora dimostrare il Teorema di Zermelo. Dimostrazione del Teorema di Zermelo. Sia X un insieme non vuoto. Per l’assioma della scelta esiste un’applicazione g : P(X) \ {∅} → X tale che g(A) ∈ A per ogni ∅ = 6 A∈ P(X). Sia c : P(X) → P(X) l’applicazione che manda ogni sottoinsieme A di X nel suo complemento X \ A. Allora la composizione f = g ◦ c è un’applicazione P(X) \ {X} → X che soddisfa f (B) 6∈ B per ogni B ⊆ X distinto da X stesso. L’idea è di costruire un ordine ≤ su X tale che per ogni sottoinsieme proprio B di X, posto x = f (B), B risulta essere il segmento iniziale I(x) = {y ∈ X : y < x} di tutti gli elementi di X minori di x. Partendo da 46 questa idea, x0 = f (∅) sarà l’elemento minimo di ≤ (essendo I(x0 ) = ∅), x1 = f ({x0 }) sarà il successore di x0 , x2 = f ({x0 , x1 }) il successore di x1 , x3 = f ({x0 , x1 , x2 }) sarà il successore di x2 e cosı̀ via. L’ordine x0 < x1 < x2 < . . . < xn è un buon ordine per ogni n. Per rendere questo argomento rigoroso bisogna ragionare cosı̀. Abbiamo visto che esistono sottoinsiemi non vuoti A di X che ammettono un buon ordine ≤A per il quale per ogni a ∈ A e per il segmento iniziale IA (a) := {y ∈ A : y <A x} si ha f (IA (a)) = a (per esempio, A = {x0 , x1 , x2 , x3 }). Denotiamo con A la famiglia di tutti i sottoinsiemi A di X, con questa proprietà. Il nostro scopo è di dimostrare che X ∈ A. Passo 1. Dimostrare che se A e B appartengono ad A, allora A ⊆ B e l’ordine ≤B coincide con l’ordine ≤A su A, oppure B ⊆ A e l’ordine ≤A coincide con l’ordine ≤B su B. Consideriamo C = {c ∈ A ∩ B : IA (c) = IB (c)}) e dimostreremo che C coincide con A o B ragionando per assurdo. Cioè supponendo A 6⊆ B (risp. B 6⊆ A) abbiamo A \ C 6= ∅ (risp. B \ C 6= ∅). Sia a il minimo elemento di A \ C e sia b il minimo elemento di B \ C. Allora ogni a′ ∈ IA (a) appartiene a B in quanto a′ < a e a′ ∈ A. Analogamente IB (b) ⊆ A. Pertanto IA (a) ⊆ A ∩ B e IB (b) ⊆ A ∩ B. Ora dimostriamo che IA (a) ⊆ IB (b). Sia a′ ∈ IA (a). Allora a′ ∈ C ⊆ A ∩ B. Notiamo che a′ 6= b poiché b 6∈ C. Per l’Esercizio 6.14 gli elementi a′ , b ∈ B sono confrontabili. Supponiamo a′ >B b. Allora b ∈ IB (a′ ) = IA (a′ ) (perché a′ ∈ C). Quindi b ∈ A e b <A a′ <A a. Di conseguenza b ∈ C, assurdo. Quindi, a′ <B b, cioè a′ ∈ IB (b). Analogamente si dimostra che IB (b) ⊆ IA (a). Ora l’uguaglianza IA (a) = IB (b) implica a = f (IA (a)) = f (IB (b)) = b. Quindi c = a = b ∈ A ∩ B e IA (c) ⊆ IB (c). Pertanto c ∈ C, assurdo. Questo dimostra che C coincide con A o B, di conseguenza abbiamo dimostrato la tesi del Passo 1. Inoltre, se A ⊆ B, A risulta essere il segmento iniziale di B determinato dal minimo elemento b di B che non appartiene ad A. S Passo 2. Sia Y = A∈A A. Se a, b ∈ Y , allora per il Passo 1 esiste A ∈ A, tale che a, b ∈ A. Poniamo a ≤ b se a ≤A b. Dobbiamo ora verificare che questo definisce un buon ordine ≤Y in Y per il quale risulta Y ∈ A. Sia M un sottoinsieme non vuoto di Y . Allora esiste A ∈ A tale che M ∩ A 6= ∅. Quindi M ∩ A ha un elemento minimo m. Per provare che m è un elemento minimo di M , prendiamo y ∈ M . Se y ∈ M ∩ A ovviamente si ha m ≤ y. Supponiamo y ∈ M \ A. Allora esiste B ∈ A tale che y ∈ B. Per il passo 1, A ⊆ B (infatti, y ci fa vedere che B ⊆ A non vale). Per il fatto che A è un segmento iniziale di B e per la scelta di m, concludiamo che m < y. Pertanto, m è un elemento minimo di M . Passo 3. Se risulta Y = X, allora (X, ≤X ) è ben ordinato. Supponiamo per assurdo che Y 6= X. Allora con x = f (Y ) poniamo Z = Y ∪ {x} e estendiamo l’ordine ≤Y di Y su Z ponendo y ≤Z x per tutti gli y ∈ Y . Con questo ordine (Z, ≤Z ) è ben ordinato e appartiene a A in quanto IZ (x) = Y e f (Y ) = x. Ma allora x ∈ Z ⊆ Y , assurdo. • Ora possiamo usare l’assioma della scelta per dimostrare una proprietà delle applicazioni che risulta un’altra forma equivalente dell’assioma della scelta. Teorema 5.3 L’assioma della scelta è equivalente alla seguente proprietà: per ogni applicazione f : X → Y suriettiva esiste una funzione1 g : Y → X tale che f ◦ g = idY . Dimostrazione. Supponiamo che la proprietà sia verificata. Per verificare l’assioma della scelta usiamo la forma di Zermelo. Quindi basta provare che per ogni famiglia nonSvuota A = {Ai }i∈I d̀i insiemi non vuoti a due a due disgiunti esiste un’applicazione h : I → i∈I Ai S tale che h(i) ∈ Ai per ogni i ∈ I. Sia X = i∈I Ai e sia f : X → A l’applicazione definita da f (a) = Ai per ogni i ∈ I e a ∈ Ai . Allora f è suriettiva, e quindi esiste g : A → X tale che 1 Se esiste una tale g con f ◦ g = idY , allora f è suriettiva perché la suriettività di f ◦ g (dato che idY è suriettiva) implica la suriettività di f . Analogamente, la iniettività di idY implica che g è iniettiva. 47 f (g(Ai)) = Ai per ogni i ∈ I. Allora ai = g(Ai) ∈ Ai per ogni i ∈ I. Ora la composizione h S dell’applicazione I → A, definita da i 7→ Ai , e g serve come funzione scelta h : I → i∈I Ai desiderata. Supponiamo che valga l’assioma della scelta e che f : X → Y sia un’applicazione suriettiva. Allora, dato y ∈ Y , esiste x ∈ X tale che f (x) = y. Scelgo un tale x ∈ f −1 (y) e definisco g : Y → X tramite g(y) = x (quell’unico x che ho scelto). Quindi, per costruzione della g, si ha f (g(y)) = f (x) = y. Si noti che l’applicazione g è iniettiva. Quindi, questa proprietà si può enunciare anche cosı̀: esiste un applicazione suriettiva f : X → Y se e solo se esiste un’applicazione iniettiva g : Y → X. La seguente importante proprietà è nota come Lemma di Zorn. Essa trova molte applicazioni nell’Algebra e nell’Analisi per dimostrare l’esistenza di certi oggetti con proprietà estremali (vedi per esempio la dimostrazione del Teorema di Hartogs nel paragrafo 5.3). Per un’applicazione immediata si veda anche lo svolgimento degli Esercizi 6.48 e la dimostrazione del Lemma 5.13. Per poter enunciare il Lemma di Zorn, abbiamo prima bisogno di una definizione: Definizione 5.4 Un insieme parzialmente ordinato (A, ≤) si dice induttivo se ogni catena ha un maggiorante. L’Esercizio 6.8 garantisce l’esistenza di insiemi induttivi, per esempio tutti gli insiemi parzialmente ordinati finiti. Vedremo ora che la dimostrazione di questo lemma usa l’assioma della scelta. D’altra parte, si può dimostrare che il Lemma di Zorn implica l’assioma della scelta. Lemma di Zorn. Ogni insieme parzialmente ordinato e induttivo ammette elementi massimali. Dimostrazione. Sia (X, ≤) un insieme ordinato induttivo. Supponiamo per assurdo che X non abbia elementi massimali e denotiamo con B la famiglia di tutti i sottoinsiemi superiormente limitati di X. Per la nostra ipotesi, X 6∈ B e ogni catena è superiormente limitata, quindi appartiene a B. Per ogni insieme B ∈ B denotiamo con M (B) l’insieme (non vuoto) dei maggioranti di B e notiamo che M (B) 6⊆ B. Infatti, ogni b0 ∈ M (B) ∩ B è un elemento massimo di B. Poiché X non ha elementi massimali, esiste x ∈ X con x > b0 (altrimenti b0 sarebbe massimale). Ora x ∈ M (B) \ B. Abbiamo cosı̀ dimostrato che M (B) \ B 6= ∅ per ogni B ∈ B. Sia f una funzione scelta definita per la famiglia {M (B) \ B : B ∈ B}. Definiamo ora g : B → X con g(B) = f (M (B) \ B). Per x0 = f (X) (si noti che X = M (∅)) il segmento iniziale I(x0 ) nell’insieme ben ordinato ({x0 }, ≤) è vuoto e quindi x0 = g(I(x0)). Sia A la famiglia di tutti i sottoinsiemi A ⊆ X tali che (A, ≤) è ben ordinato e per ogni a ∈ A si ha a = g(IA (a)), dove IA (a) è il segmento iniziale in A determinato da a (ovviamente IA (a) ∈ B). Ovviamente, {x0 } ∈ A, pertanto A non è vuoto. Passo 1. Dimostrare che se A e B ∈ A, allora A ⊆ B, oppure B ⊆ A. Poniamo C = {c ∈ A ∩ B : IA (c) = IB (c)} e dimostreremo che C coincide con A o B ragionando per assurdo. Sia a il minimo elemento di A \ C e sia b il minimo elemento di B \ C. Vogliamo dimostrare che IA (a) = IB (b). Sia x ∈ IA (a). Allora x ∈ A e x < a implica x ∈ C. Quindi x ∈ B e IA (x) = IB (x). Notiamo che x 6= b poiché b 6∈ C. Per l’Esercizio 6.14 gli elementi x, b ∈ B sono paragonabili. Supponiamo x > b. Allora da IA (x) = IB (x) si avrebbe b ∈ A e b < x < a. Di conseguenza b ∈ C, assurdo. Quindi, x < b, cioè x ∈ IB (b). Analogamente si dimostra che IB (b) ⊆ IA (a). Ora l’uguaglianza IA (a) = IB (b) implica a = g(IA (a)) = g(IB (b)) = b. Quindi 48 c = a = b ∈ A ∩ B e IA (c) = IB (c). Pertanto c ∈ C, assurdo. Questo dimostra che C coincide con A o B, di conseguenza abbiamo dimostrato che A ⊆ B, oppure B ⊆ A. S Passo 2. Sia Y = A∈A A. Allora Y è una catena in X in quanto per ogni coppia a, b ∈ Y , esistono A ∈ A e B ∈ A con a ∈ A e b ∈ B. Per il Passo 1, A ⊆ B, oppure B ⊆ A. Pertanto si avrà a, b ∈ A oppure a, b ∈ B. Quindi vale a ≤ b oppure b ≤ a. Essendo Y una catena si ha Y ∈ B. Poniamo z = g(Y ) e notiamo che Z = Y ∪ {z} risulta essere ben ordinato con l’ordine ≤ e g(IZ (z)) = z. Quindi Z ∈ A. Poiché Z contiene propriamente Y , questo contraddice la definizione di Y . 5.1.1 Principio dell’induzione transfinita In un insieme ben ordinato (X, ≤) si può definire il concetto di successore di un elemento x, come il minimo elemento dell’insieme di tutti gli elementi y > x di X. Analogamente, si può definire anche il concetto di successore succ(Y ) di un sottoinsieme Y 6= X quale il minimo elemento del complemento di Y in X. D’altra parte, ogni elemento x determina anche l’insieme IX (x) := {z ∈ X : z < x}, detto segmento iniziale (determinato da x), del quale risulta essere il successore. Di particolare importanza è il seguente Principio di induzione transfinita. Se (X, ≤) è un insieme ben ordinato con elemento minimo x0 ed E è un sottoinsieme di X tale che (a) x0 ∈ E (b) E contiene tutti gli elementi x ∈ X per i quali IX (x) ⊆ E, allora E = X. Dimostrazione. Ragionando per assurdo supponiamo E 6= X. Allora l’insieme X \ E 6= ∅. Quindi, esiste un elemento minimo x di X \ E. Allora y ∈ E per tutti gli y < x in X. In altre parole, IX (x) ⊆ E. Allora la condizione (b) implica x ∈ E, assurdo. Come caso particolare si ricava il principio di induzione. Infatti, poniamo X = N con l’usuale ordine ≤ in N. Allora (N, ≤) risulta ben ordinato e in questo caso il principio di induzione transfinita coincide con il solito principio di induzione. Infatti, la condizione (b) nel caso di N è equivalente alla richiesta n + 1 ∈ E qualora n ∈ E (si noti che in N ogni insieme superiormente limitato ha un elemento massimo, quindi I (x) ha un elemento massimo ovvero il predecessore di x). ✁ 5.2 Prodotti cartesiani Siano X e Y due insiemi non vuoti. Per un elemento x ∈ X e un elemento y ∈ Y l’insieme {{x}, {x, y}} si dice coppia ordinata con prima coordinata x e seconda coordinata y e si denota con (x, y). Non è difficile vedere che due coppie (x, y) e (x1 , y1 ) coincidono se e solo se x = x1 e y = y1 . Il prodotto cartesiano X × Y di X per Y è l’insieme di tutte le coppie ordinate (x, y), dove x ∈ X e y ∈ Y . 5.2.1 Potenze cartesiani Cominciamo con le potenze cartesiane, ovvero prodotti cartesiani di un insieme con se stesso. Nel caso X = Y l’insieme di tutte le coppie (x, x) con x ∈ X si denota con ∆X e si chiama diagonale di X × X. Scriveremo X 2 per denotare X × X. 49 Siano A ed I due insiemi non vuoti. L’insieme di tutte le applicazioni f : I → A si denota con AI . Discuteremo ora la possibilità di vedere l’insieme AI come un prodotto cartesiano. Cominciamo con le potenze cartesiane finite. Lemma 5.5 Sia A un insieme non vuoto. Esiste una biiezione tra A{1,2} ed il prodotto cartesiano A × A. Dimostrazione. All’applicazione f : {1, 2} → A mettere in corrispondenza la coppia ordinata (f (1), f (2)) di A × A. Questo definisce un’applicazione ϕ : A{1,2} → A × A. Inoltre ϕ è invertibile, avendo come inversa l’applicazione ψ : A×A → A{1,2} che alla coppia (a, b) ∈ A×A associa l’applicazione f : {1, 2} → A definita da f (1) = a e f (2) = b. La biiezione ϕ del Lemma 5.5 ci permette di identificare A{1,2} con il prodotto cartesiano A × A e scrivere più brevemente A2 . In questo modo non si distingue più tra una coppia ordinata di elementi di A ed un’applicazione f : {1, 2} → A. Analogamente, per ogni n > 1 esiste una biiezione tra A{1,2,...,n} ed il prodotto cartesiano A | ×A× {z. . . × A} (vedi l’Esercizio n volte 6.16). Grazie a questa biiezione identifichiamo l’insieme A{1,2,...,n} con il suddetto prodotto cartesiano che scriviamo più brevemente An . ✂ Analogamente, possiamo considerare un’applicazione f : N → A, cioè un elemento di A , come una successione infinita a1 , a2 , . . . , an , . . . di elementi di A. Questo dà una interpretazione della potenza cartesiana infinita A . . × A × . .}.. Nel caso generale, la potenza cartesiana AI | × A × . {z infinite volte è semplicemente l’insieme di tutte le applicazioni f : I → A. 5.2.2 Prodotti cartesiani di insiemi non necessariamente uguali Nel caso di prodotti cartesiani di insiemi non necessariamente uguali bisogna ragionare cosı̀: Lemma 5.6 Siano A e B due insiemi non vuoti. Denotiamo con X l’insieme delle applicazioni f : {1, 2} → A ∪ B con la proprietà f (1) ∈ A e f (2) ∈ B. Trovare una biiezione tra X ed il prodotto cartesiano A × B. Dimostrazione. All’applicazione f ∈ X mettere in corrispondenza la coppia ordinata (f (1), f (2)) ∈ A × B. Questo definisce un’applicazione ϕ : X → A × B. Provare che ϕ è invertibile, avendo come inversa l’applicazione ψ : A × B → X che alla coppia (a, b) ∈ A × B associa l’applicazione f : {1, 2} → A ∪ B definita da f (1) = a e f (2) = b. Grazie alla biiezione ϕ identifichiamo il prodotto cartesiano A × B con l’insieme delle applicazioni f : {1, 2} → A ∪ B con la proprietà f (1) ∈ A e f (2) ∈ B. Lo scopo di introdurre un tale punto di vista diventa chiaro quando si passa a prodotti cartesiani di più di due insiemi. Sia n > 1 e siano A1 , A2 , . . . , An degli insiemi non vuoti. Definiamo il prodotto cartesiano A1 × A2 × . . . × An come l’insieme che ha come elementi tutte le n-uple ordinate (a1 , a2 , . . . , an ) con a1 ∈ A1 , a2 ∈ A2 , . . ., an ∈ An definite in modo analogo. Se tutti gli insiemi A1 , A2 , . . . , An coincidono con un dato insieme A, scriveremo brevemente An per il prodotto cartesiano A1 × A2 × . . . × An . Ecco un altro modo di descrivere il suddetto prodotto cartesiano. Denotiamo con X l’insieme delle applicazioni f : {1, 2, . . ., n} → A1 ∪ A2 ∪ . . . ∪ An con la proprietà f (1) ∈ A1 , f (2) ∈ A2 , . . ., f (n) ∈ An , che chiameremo funzione di scelta per la famiglia A1 , . . . , An (vedi anche la definizione 5.1). Allora esiste una biiezione tra X ed il prodotto cartesiano A1 × A2 × . . . × 50 An (vedi l’Esercizio 6.18). Grazie a questa biiezione identificheremo nel futuro il prodotto cartesiano A1 × A2 × . . . × An con l’insieme delle funzioni di scelta per la famiglia A1 , . . . , An . Sia n > 1 e siano A1 , A2 , . . ., An insiemi non vuoti. Per i = 1, 2, . . ., n definiamo la proiezione pi : A1 × A2 × . . . × An → Ai con pi (a1 , a2 , . . . , an ) = ai . Queste applicazioni sono molto importanti per la definizione del prodotto cartesiano (vedi l’Esercizio 6.19). Sia {Ai}i∈I una famiglia non vuota (cioè, I 6= ∅) diSinsiemi non vuoti Ai . Una funzione di scelta per questa famiglia è un’applicazione f : I → i∈I Ai tale che f (i) ∈ Ai per ogni i ∈ I. Nel caso dei prodotti cartesiani finiti siamo riusciti a descrivere il prodotto cartesiano, a meno di una biiezione, come l’insieme di tutte le funzioni scelta (si vedano gli Esercizi 5.5-6.18). Nel caso di prodotto cartesiano di famiglie arbitrarie, questa resta l’unica strada da percorrere: Definizione 5.7 Il prodotto cartesiano della famiglia {Ai }i∈I , denotato con sieme di tutte le funzioni di scelta della famiglia {Ai}i∈I . Esercizio 5.8 Il prodotto cartesiano Q Suggerimenti. Vedi l’Esercizio 6.20. i∈I Q i∈I Ai , è l’in- Ai è non vuoto se I è finito. Vediamo ora l’impatto dell’Assioma della scelta sui prodotti infiniti di insiemi. In generale, Q l’affermazione che il prodotto cartesiano i∈I Ai sia non vuoto è ovviamente equivalente all’Assioma della scelta. Abbiamo costruito una funzione di scelta nel caso di I finito (Esercizio 6.22). Nonostante l’apparente “chiarezza” dell’esistenza della funzione scelta, l’Assioma della scelta non è dimostrabile a partire degli altri assiomi della teoria degli insiemi. Analogamente a quanto fatto nel caso di prodotti finiti di insiemi, si può definire la proiezione Q anche nel caso infinito. Per i ∈ I definiamo la proiezione p : i i∈I Ai → Ai ponendo pi (f ) = Q f (i) per ogni funzione di scelta f ∈ i∈I Ai . 5.3 Numeri cardinali. In analogia con il caso di un insieme finito A, introduciamo qui un concetto di “misura” |A| anche per insiemi infiniti A. Diremo che A e B sono equipotenti, e scriveremo |A| = |B|, se esiste una biiezione A → B. Poiché è naturale avere |A| ≤ |B| per un sottoinsieme A di B, poniamo in generale |A| ≤ |B| se esiste un’applicazione iniettiva2 A → B. Scriveremo |A| < |B| se vale |A| ≤ |B|, ma non vale |B| ≤ |A|. Nel seguente Teorema di Cantor-Bernstein vediamo che |A| = |B| equivale alla validità simultaneamente di |A| ≤ |B| e |B| ≤ |A|. Questo teorema fornisce anche un metodo utile alla determinazione di insiemi equipotenti. Teorema di Cantor-Bernstein. Siano S e T due insiemi non vuoti. Se esistono iniezioni S → T e T → S, allora esiste anche una biiezione S → T . Dimostrazione. Per la dimostrazione di questo Teorema, avremo bisogno del seguente lemma che è praticamente un caso particolare del Teorema di Bernstein, nel quale uno degli insiemi è sottoinsieme dell’altro e la rispettiva iniezione è l’inclusione. Vedremo dopo, che il caso generale si deduce facilmente da questo caso. Lemma. Sia f : X → X un’applicazione iniettiva, ma non suriettiva. Allora per ogni sottoinsieme Y di X, tale che f (X) ⊆ Y ⊆ X, esiste una biiezione h : Y → X. 2 D’altra parte, per il teorema 5.3, esiste un’applicazione suriettiva A → B se e solo se esiste un’applicazione iniettiva B → A (vedi anche l’Esercizio 6.36). Quindi, |A| ≤ |B| se e solo se esiste anche un un’applicazione suriettiva B → A. 51 Cominciamo la dimostrazione del lemma. Per definire una biiezione g : Y → X basta definire una biiezione s : Y → f (X) e comporla con l’inversa di f su f (X). Si consideri in X la relazione R cosı̀ definita: xRy ⇔ esistono n, m ∈ N con f n (x) = f m (y). Si dimostra facilmente che R è una relazione di equivalenza. Siano {Ci }i∈I le classi di equivS alenza. S Allora esse formano una partizione X = i∈I Ci di X e, di conseguenza, una partizione Y = i∈I (Y ∩ Ci ) di Y . Fissiamo un i ∈ I e notiamo che Y ∩ Ci 6= Ci accade se e solo se Ci 6⊆ Y , e in particolare Ci 6⊆ f (X). Vediamo che esiste precisamente un elemento z ∈ Ci \ f (X). Infatti se z, z ′ ∈ Ci \ f (X), allora esistono n, m ∈ N con f n (z) = f m (z ′ ). Per l’iniettività di f si può supporre che almeno uno tra n ed m sia 0. Per la scelta di z, z ′ deduciamo che tutte e due sono 0. Quindi z = z ′ e pertanto Ci = {z} ∪ (f (X) ∩ Ci ). Poiché Ci ⊇ Y ∩ Ci ⊇ f (X) ∩ Ci , l’ipotesi Y ∩ Ci 6= Ci implica Y ∩ Ci = f (Ci ). Pertanto la restrizione fi di f su Ci risulta un biiezione fi : Ci → Y ∩ Ci . Ora definiamo un’applicazione g : X → Y nel modo seguente. Per x ∈ X esiste un unico i ∈ I tale che x ∈ Ci . Se Y ∩ Ci 6= Ci , poniamo g(x) = f (x), se Y ∩ Ci = Ci , poniamo g(X) = x. Verifichiamo che per ogni i ∈ I vale g(Ci) = Y ∩ Ci e g −1 (Y ∩ Ci ) = Ci . (∗) Inoltre g definisce una biiezione tra Ci e Y ∩ Ci . Questo è ovvio quando Y ∩ Ci = Ci , perché allora la restrizione di g su Ci coincide con l’identità di Ci . Se Y ∩Ci 6= Ci , allora la restrizione di g su Ci coincide con la biiezione fi : Ci → Y ∩ Ci . Questo dimostra (∗). Per finire notiamo che g è suriettiva, in quanto y ∈ Y appartiene a qualche Y ∩ Ci e quindi y = g(x) per qualche x ∈ Ci , come visti sopra. Se g(x) = g(z), allora esiste qualche i tale che g(x) = g(z) ∈ Y ∩ Ci . Di nuovo, da (∗) e l’iniettività di g ristretta a Ci , concludiamo x = z. Se Y ∩ Ci = Ci , abbiamo ovviamente anche |Y ∩ Ci | = |Ci |. Supponiamo che Ci 6⊆ Y , in particolare Ci 6⊆ f (X). Notiamo che esiste precisamente un elemento z ∈ Ci \ f (X). Infatti, se z, z ′ ∈ Ci \ f (X), allora esistono n, m ∈ N con f n (z) = f m (z ′ ). Per l’iniettività di f si può supporre che almeno uno tra n ed m sia 0. Per la scelta di z, z ′ deduciamo che tutte e due sono 0. Quindi z = z ′ . Per la dimostrazione del Teorema 2.11 esiste un’applicazione iniettiva h : N → X con h(0) = z. Ora Ci \ {z} ⊆ Y ∩ Ci ⊆ Ci , quindi |Y ∩ Ci | = |Ci | = |N|. A questo punto applichiamo l’Esercizio 6.47 che descrive come si può costruire una biiezione a partire da una famiglia opportuna di biiezioni. Nel nostro caso le biiezioni provengono dalle eguaglianze |Y ∩ Ci | = |Ci |. La conclusione dell’Esercizio citato permette di concludere |Y | = |X|. Questo completa la dimostrazione del lemma. Torniamo alla dimostrazione del Teorema di Cantor–Bernstein. Siano r : S → T e q : T → S due iniezioni. Allora basta applicare il lemma precedente per X = S, Y = q(T ) e f = q ◦ r. L’idea usata nel Teorema di Cantor–Bernstein è costruire biiezioni a partire da applicazioni con proprietà più deboli, quali le iniezioni. Vediamo ora che ci sono iniezioni in abbondanza. Più precisamente, dati due insiemi S e T , si ha sempre la dicotomia |S| ≤ |T | oppure |T | ≤ |S|. Teorema di Hartogs. Siano S e T due insiemi non vuoti. Allora esiste un’iniezione S → T oppure un’iniezione T → S. Dimostrazione. Supponiamo che non esista un’iniezione T → S. Per il Teorema 5.3 questo garantisce che non esiste nemmeno una suriezione S → T . Dimostreremo che esiste una iniezione S → T . 52 La famiglia F di tutte le applicazione iniettive jA : A → T , con A ⊆ S, è ordinata nel modo seguente: si pone jA ≤ jB per un’applicazione jB : B → T se A ⊆ B e jB (a) = jA (a) per ogni a ∈ A. Dimostriamo ora che l’ordine ≤ di F è induttivo. Infatti, sia C = {jBi : i ∈ I} una S catena in F . Poniamo B = i∈I Bi e definiamo jB : B → T con jB (b) = jBi (b), se b ∈ Bi . La definizione è corretta, poiché se b ∈ Bk per un altro k ∈ I, allora si ha jBi ≤ jBk oppure jBk ≤ jBi . In entrambi casi jBk (b) = jBi (b). Cosı̀ abbiamo definito un elemento jB ∈ F tale che jBi ≤ jB per ogni i ∈ I. Quindi jB è un maggiorante per la catena C. Quindi F è induttivo. Pertanto F ha elementi massimali per il Lemma di Zorn. Sia f = jB0 : B0 → T un tale elemento massimale. Se B0 = S abbiamo costruito una iniezione S → T . Supponiamo per assurdo che B0 6= S. Allora esiste un elemento x ∈ S \ B0 . Per la nostra ipotesi non esiste una suriezione S → T . Quindi neanche f : B0 → T è suriettiva (altrimenti si potrebbe facilmente estendere ad una suriezione S → T ). Pertanto f (B0 ) 6= T ed esiste y ∈ T \ f (B0 ). Ora si può estendere f a B ′ = B0 ∪ {x} ponendo jB ′ (b) = b per tutti i b ∈ B0 e jB ′ (x) = y. Allora jB ′ è iniettiva e jB0 < jB ′ , che contraddice la massimalità di jB0 . Questo assurdo dimostra l’uguaglianza B0 = S. Il Teorema di Hartogs garantisce che per due insiemi S e T si ha |S| ≤ |T | oppure |T | ≤ |S|. In altre parole, i numeri cardinali sono sempre paragonabili. Il teorema di Cantor-Bernstein garantisce inoltre che, se abbiamo simultaneamente |S| ≤ |T | e |T | ≤ |S|, allora |S| = |T |. Per il teorema di Cantor vale |X| < |P(X)| (vedi Esercizio 2.10). Definizione 5.9 Un insieme X si dice numerabile, se |X| = |N|. La cardinalità dell’insieme P(N) è nota come cardinalità del continuo e si denota con c (vedi la motivazione nell’Esercizio 6.54). Lemma 5.10 N × N è numerabile. Dimostrazione. A questo scopo troviamo un’applicazione iniettiva h : N×N → N. Definiamo h nel modo seguente: h(0, 0) = 0, h(1, 0) = 1, h(0, 1) = 2, h(0, 2) = 3, h(1, 1) = 4, h(2, 0) = 5, ecc. seguendo le frecce nel seguente diagramma • ··· • · ❅ ✻ ❘ ❅ ·· • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ❅ ■ ❅ ❅ ❘ ··· • ✻❘ ❅ ■ ❅ ■ ❅ ❅ ❅ ❘ • • ❅ ■ ❅ ■ ■ ❅ ❅ ❅ ❅ ❘ ❅ ❘ ✻❘ ❅ ■ ❅ ❅ ❅ ❘ ❅ ■ ❘ ❅ ■ ❅ ❅ ❅ ❅ ❅ ■ ❅ ■ ❅ ■ ❅ ❅ ❘ ❅ ■ ❅ ❘ ❅ ❘ • ❅• • • • • • • ❅ ■ ✻❘ ❅ ■ ❅ ■ ❅ ■ ❅ ❘ ❅ ❘ ❅ ❅ ❘ • • ❅ ■ ❅ ■ ❅ ■ ■ ❅ ❘ ❅ ❅ ❅ ❘ ❅ ❅ ❘ ❅• ■ ✲ • • ✲• • ✲ • • ✲• • ✲• ❘ Poiché ovviamente esiste un’iniezione N → N × N, ora basta applicare il teorema di CantorBernstein. Il 7 Dicembre 1873 Georg Cantor, fondatore della Teoria degli Insiemi, (nato nel 1845 a S. Pietroburgo, morto nel 1918 a Halle) dimostrò che l’insieme dei numeri reali non è numerabile. 53 Aritmetica dei numeri cardinali infiniti. Definiamo adesso somma e prodotto di numeri cardinali seguendo il caso degli insiemi finiti. Ricordiamo che per insiemi finiti X, Y , si ha |X| · |Y | = |X × Y | e |X| + |Y | = |X ∪ Y |, se X e Y sono disgiunti. Adesso estendiamo la definizione del prodotto dei numeri cardinali per due insiemi X, Y arbitrari ponendo |X| · |Y | := |X × Y |. Se almeno uno degli insiemi X, Y è infinito poniamo per definizione |X| + |Y | := |X| ∪ |Y |. Bisogna notare che a differenza del caso degli insiemi finiti non si richiede più che i due insiemi X, Y siano disgiunti. Teorema 5.11 Se almeno uno degli insiemi X, Y è infinito, si ha |X ∪ Y | = max{|X|, |Y |}. Dimostrazione. Per il teorema di Hartogs possiamo supporre che |X| ≥ |Y |. Si può dimostrare che per l’insieme infinito X esiste una partizione X = X1 ∪ X2 , tale che |X1 | = |X2 | = |X| (vedi l’Esercizio 6.50). Quindi esiste un’iniezione X ∪ Y → X1 ∪ X2 = X e possiamo concludere che |X ∪ Y | ≤ |X|. Poiché ovviamente |X ∪ Y | ≥ |X|, il Teorema di Cantor-Bernstein ci permette di concludere che |X ∪ Y | = |X| = max{|X|, |Y |}. Per quanto riguarda il prodotto abbiamo: Teorema 5.12 Se almeno uno degli insiemi X, Y è infinito, si ha |X × Y | = max{|X|, |Y |}. Per la dimostrazione del Teorema 5.12, abbiamo bisogno del seguente Lemma. Lemma 5.13 ∗∗ |X × X| = |X| per ogni insieme infinito X. Dimostrazione. Sia A0 un sottoinsieme numerabile di X. Per il Lemma 5.10, esiste una biiezione iA0 : A0 ×A0 → A0 . Si consideri la famiglia A delle coppie (A, iA), dove A0 ⊆ A ⊆ X e iA : A × A → A è una biiezione che estende iA0 . Si consideri in A la relazione ≤ definita da (A, iA) ≤ (B, iB ) se e solo se A ⊆ B e iB ↾A . Non è difficile provare che ≤ è un ordine per il quale (A, ≤) è un insieme ordinato induttivo. Per il Lemma di Zorn esiste un membro massimale (M, iM ) ∈ A. Chiaramente (M, iM ) ∈ A implica |M × M | = |M |. (1) Se |M | = |X|, allora abbiamo anche |X × X| = |M × M | (vedi l’Esercizio 6.22), e quindi l’uguaglianza (2) assieme alla nostra ipotesi implica |X × X| = |X|. Supponiamo per assurdo che |M | = 6 |X|. Poiché |M | ≤ |X|, resta la sola possibilità |M | < |X|. D’altra parte X = M ∪ (X \ M ), quindi |X \ M | ≥ |M | per il Teorema 5.11. Quindi possiamo trovare un sottoinsieme N ⊆ X \ M con |N | = |M |. Ora M ′ = M ∪ N contiene M propriamente, e M ′ × M ′ = (M × M ) ∪ D, dove D = (M × N ) ∪ (N × M ) ∪ (N × N ). Ora |N × M | = |M × N | = |N × N | = |M | = |N |. Allora esiste una biiezione D → N , che, assieme alla biiezione iM : M × M → M ci da’ una biiezione iM ′ : M ′ × M ′ → M ′ che estende iM . Quindi (M ′ , iM ′ ) ∈ A e (M, iM ) < (M ′ , iM ′ ), assurdo. Pertanto |M | = |X|. Dimostrazione del Teorema 5.12. Per il teorema di Hartogs possiamo supporre che |X| ≥ |Y |. Si può dimostrare che per l’insieme infinito X si ha |X × X| = |X| (vedi il Lemma 5.13). Allora |X| ≥ |X × X| ≥ |X × Y | ≥ |X|. Di conseguenza, se almeno uno degli insiemi X, Y è infinito la somma e il prodotto delle loro cardinalità coincidono: |X| · |Y | = |X| + |Y | = |X × Y | = |X ∪ Y | = max{|X|, |Y |}. 54 (∗) Questo fatto rende molto facile l’aritmetica dei numeri cardinali infiniti. Per esempio, si può dimostrare per induzione che |X1 × . . . × Xn | = |X1 ∪ . . . ∪ Xn | = max{|X1 |, . . ., |Xn|} e |X n| = |X| per ogni ogni numero naturale n > 0 se X e almeno uno degli insiemi X1 , . . . , Xn è infinito. Di conseguenza |X1 | · . . . · |Xn| = |X1 | + . . . + |Xn | = max{|X1 |, . . ., |Xn|} e |X|n = |X| (vedi l’Esercizio 6.43 per i casi concreti). Poniamo 2|X| = |2X | = |P(X)|. Per il teorema di Cantor, si ha sempre 2|X| > |X|. Questo ci permette di trovare degli insiemi di cardinalità sempre più grandi. Il primo numero cardinale infinito |N| si denota con ℵ0 , quello successivo con ℵ1 ecc. Si ottiene cosı̀ una successione infinita di numeri cardinali a partire da quelli finiti 0 < 1 < 2 < . . . < n < . . . < ℵ0 < ℵ1 < . . . < ℵn < . . . 5.4 (3) Assiomi della teoria degli insiemi. 1. (Esistenza) Esiste un insieme. 2. (Estensionalità) Due insiemi coincidono se e solo se hanno gli stessi elementi. 3. (Separazione) Ad ogni proprietà P (di insiemi) e ad ogni insieme X corrisponde un3 insieme Y che ha come elementi precisamente gli elementi y di X che possiedono la proprietà P . 4. (Esiste la coppia) Se X è un insieme e Y è un insieme, allora esiste un insieme Z che ha come elementi X e Y e non ha altri elementi. 5. (Unione) Per ogni insieme 4 X esiste l’insieme Y che ha come elementi gli z che appartengono ad almeno uno degli elementi dell’insieme X. 6. (Fondazione) Per ogni insieme X 6= ∅ esiste un insieme Y ∈ X che non ha elementi comuni con X. 7. (L’insieme della parti) Per ogni insieme X esiste l’insieme P (X) che ha come elementi i sottoinsiemi di X. 8. (Rimpiazzamento) Se R è una relazione binaria tra insiemi tale che ad ogni insieme x corrisponde al più un insieme y con xRy, allora per ogni insieme X esiste l’insieme {y : esiste x ∈ X con xRy}. 9. (Esiste un insieme infinito) Esiste un insieme induttivo.5 L’assioma della Fondazione serve per evitare insiemi patologici con X ∈ X, o catene discendenti infinite . . . ∈ X3 ∈ X2 ∈ X1 ∈ X0 . Per esempio, se X = P(A), allora Y = ∅ ∈ X non ha elementi comuni con X. Paradosso di Russell. Nell’assioma di Separazione si definisce Y = {z ∈ X : z ha la proprietà P }; il fatto di prendere tutti gli z in un insieme X è importante perché altrimenti si rischia di uscire fuori dell’ambito degli insiemi, come accade nel seguente paradosso di Russell. 3 unico, per l’assioma precedente. che è meglio vedere in questo contesto come famiglia di insiemi. 5 cioè un insieme X tale che se z ∈ X allora anche z ∪ {z} ∈ X. 4 55 Sia P la proprietà : “l’insieme non è elemento di se stesso”. Allora la formazione M che consiste di tutti gli insiemi che possiedono la proprietà X 6∈ X non può essere un insieme (perché?). Suggerimento: Notare che non è vero nè M ∈ M nè M 6∈ M. Per evitare questo paradosso è permesso solo di considerare l’insieme degli elementi di un certo insieme che possiedono una certa proprietà P. L’ipotesi del continuo. Chiaramente, la cardinalità del continuo 2ℵ0 si trova nella successione (3) e 2ℵ0 > ℵ0 per il Teorema di Cantor. Quindi, 2ℵ0 ≥ ℵ1 . L’affermazione 2ℵ0 = ℵ1 è nota come Ipotesi del continuo. In altre parole, l’Ipotesi del continuo afferma che ogni insieme non numerabile di numeri reali ha la cardinalità del continuo. I numerosi tentativi di provarla sono falliti per più di 70 anni. Infatti, Gödel ha dimostrato che l’Ipotesi del continuo è soddisfatta in alcuni modelli della teoria degli insiemi, mentre Paul Cohen ha dimostrato che l’Ipotesi del continuo non vale in altri modelli della teoria degli insiemi da lui costruiti tramite il celebre metodo del forcing introdotto da lui a questo proposito6. Di conseguenza, l’Ipotesi del continuo non è dimostrabile, ne è dimostrabile la sua negazione. 6 Esercizi su Insiemi 6.1 Esercizi e svolgimento di alcuni esercizi precedenti su insiemi Esercizio 6.1 Sia X un’insieme e sia jX : X → P(X) l’applicazione definita da jX (x) = {x}. Dimostrare che jX è sempre iniettiva. Esercizio 6.2 Sia f : X → Y un’applicazione e sia f∗ : P(X) −→ P(Y ) la funzione cosı̀ definita f∗ (B) = f (B). Si provi che (a) f∗ ◦ jX = jY ◦ f ; (b) f è iniettiva se e solo se f∗ è iniettiva,, (c) f è suriettiva se e solo se f∗ è suriettiva. Svolgimento. (a) è ovvia. (b) Se f∗ è iniettiva, allora la composizione f∗ ◦ jX è iniettiva per il Lemma 2.13 e l’Esercizio precedente. Per (a) anche la composizione jY ◦ f è iniettiva. Ora dal Lemma 2.16 si conclude che f è iniettiva. Ora supponiamo che f sia iniettiva. Ragionando come nello svolgimento del punto (a) dell’Esercizio 2.23 si conclude che anche f∗ è iniettiva. (c) Supponiamo che f∗ sia suriettiva. Allora esiste A ∈ P(X) con f∗ (A) = f (A) = Y , quindi anche f (X) = Y e pertanto f è suriettiva. Se invece f è suriettiva e C ⊆ Y , allora f (f −1 (C)) = C, quindi C = f∗ (f −1 (C)). Esercizio 6.3 Sia f : X → Y un’applicazione e sia f ∗ : P(Y ) −→ P(X) la funzione cosı̀ definita f ∗ (B) = f −1 (B) = {a ∈ X : f (a) ∈ B}. Si provi che (a) f ∗ è iniettiva se e solo se f è suriettiva, (b) f ∗ è suriettiva se e solo se f è iniettiva. 6 Questo teorema valse per Paul Cohen la medaglia Fields nel 1966, il premio più prestigioso attribuito nell’ambito della matematica. 56 Svolgimento. (a) Supponiamo che f ∗ sia iniettiva. Allora essendo f ∗ (Y ) = f ∗ (f (X)) concludiamo che Y = f (X), cioè f è suriettiva. Viceversa, sia f suriettiva, cioè Y = f (X). Allora f∗ ◦ f ∗ = idP(Y ) essendo f (f −1 (B)) = B per ogni B ∈ P(Y ). Quindi, f ∗ è iniettiva per il Lemma 2.16. (b) Sia f ∗ suriettiva, e supponiamo per assurdo che esistano x 6= y in X con f (x) = f (y). Poiché f ∗ è suriettiva, esiste B ∈ P(Y ) tale che {x} = f ∗ (B). Ma y ∈ f ∗ (B) e quindi si avrebbe x = y. Da questa contraddizione concludiamo che f è iniettiva. Supponiamo ora che f sia iniettiva e A ∈ P(X), allora f −1 (f (A)) = A, cioè A = f ∗ (f (A)). Questo dimostra che f ∗ è suriettiva. Esercizio 6.4 Si considerino le relazioni binarie R1 , R2 , R3 e R4 nell’insieme C dei numeri complessi definite come segue: 1) xR1 y se il numero x − y è naturale; 2) xR2 y se il numero x − y è razionale; 3) xR3 y se il numero x − y è reale e x − y ≥ 0; 4) xR4 y se la parte reale e la parte immaginaria del numero x − y sono ≥ 0. Si determini quali delle relazioni R1 , R2, R3 e R4 sono relazioni di equivalenza, e quali sono ordini o preordini, specificando il tipo di ordine (buon ordine, ordine lineare ecc.). 6.2 Esercizi sugli insiemi parzialmente ordinati Esercizio 6.5 Si disegnino i diagrammi di Hasse degli insiemi parzialmente ordinati per divisibilità dei divisori di 36 e 60. Svolgimento. 60 ✟✟❍❍ 30 ❍ 12 ✟ ✟❍ ❍ 20 ❍✟ ❍❍ ❍❍✟ ❍ ❍10 ✟ 15 ✑ 6 ✑ ❍✟❍✟ 4 ❍❍ ✑ ❍✟ ◗ ◗ ❍✑ ✟ 2❍❍ ✟ 5 ❍✟ 36 12✟✟❍❍18 ✟❍ 6 ✟❍ ✟ ❍ ❍✟ 4 ❍ ✟9 ✟❍ ❍❍ ✟ ✟ ❍ 2 ❍✟✟3 1 1 L’insieme ordinato dei divisori di 36 L’insieme ordinato dei divisori di 60 Esercizio 6.6 Trovare il numero di tutti gli ordini di un insieme di 3 elementi. Svolgimento. Siano a, b, c i tre elementi distinti dell’insieme X. Allora i possibili ordini sono: (1) nessuna coppia di elementi è confrontabile (l’ordine è discreto), cioè dati x, y ∈ X, con x 6= y si ha x 6< y e y 6< x; (2) due elementi sono confrontabili e il terzo non lo è con nessuno degli altri due: ci sono 6 ordini di questo tipo (b ≤ c, c ≤ b, a ≤ b, b ≤ a, a ≤ c e c ≤ a): 57 •c •b • •b a • • c •a a •b • •b c • a • •a c • c • •c b • a • b (3) i tre elementi formano una catena: a ≤ b ≤ c, ci sono 6 ordini di questo tipo: •c •c •b •b •a •a •b •a •c •a •c •b •a • •a •c • •c b b (4) esiste un massimo e l’insieme non è una catena: a ≤ b ≥ c e ci sono 3 ordini di questo tipo oppure esiste un minimo e l’insieme non è una catena: a ≥ b ≤ c e ci sono 3 ordini di questo tipo. •b ✁ • a ✁ ✁❆ ✁ ❆ ❆ • ❆ • c ✁ • b ✁ a ✁❆ ✁ ❆ ❆ • ❆ • c ✁ • a ✁ a • c ✁❆ ✁ ❆ ❆ ❆ ❆ ❆ ❆ • b ❆•✁ ✁ ✁ b • ✁ b • ❆ ❆ b ❆ ✁ ❆•✁ ✁ c • ✁ a • ❆ ❆ a In totale ci sono 19 possibili ordinamenti su un insieme con 3 elementi. ❆ ✁ ❆•✁ ✁ b • ✁ c Esercizio 6.7 Trovare il numero di tutti gli ordini di un insieme di 4 elementi. Suggerimenti. Daremo un suggerimento. Gli ordini che hanno un elemento massimo o un elemento minimo sono facilmente riducibili all’Esercizio precedente. Resta da determinare il numero degli ordini che non hanno nè un elemento massimo nè un elemento minimo. Di questo tipo sono tutti gli ordini che hanno un elemento isolato (non confrontabile con gli altri elementi). Infine, resta un ultimo tipo di ordine, senza elementi isolati, nè minimi nè massimi. Esercizio 6.8 Dimostrare che ogni insieme parzialmente ordinato e finito è induttivo. Esercizio 6.9 Dimostrare che ogni reticolo finito è limitato. Esercizio 6.10 Sia A un insieme non vuoto finito o numerabile. Dimostrare che A ammette una relazione di buon ordine. Suggerimenti. Esiste, per ipotesi, una biiezione f : I → A, dove I = {1, 2, . . ., n} o I = N. In entrambi i casi I ammette un buon ordine ≤, che si trasporta su A ponendo per definizione f (a) ≤ f (b) qualora a ≤ b in I. 58 Esercizio 6.11 Sia X un insieme non vuoto. L’insieme parzialmente ordinato (P(X), ⊆) è un reticolo limitato. Esercizio 6.12 Si dia un esempio di un reticolo che ha un sottoinsieme ordinato che non è un reticolo. Svolgimento. Consideriamo l’insieme Y di tutti i divisori di 15, ordinato per divisibilità: Y = {1, 3, 5, 15} e a b se e solo se a|b. (Y, |) è un reticolo e non è totalmente ordinato perché 3 6 |5 e 5 6 |3. Il sottoinsieme parzialmente ordinato X = {3, 5} non è un reticolo perché 3 ∨ 5 = 15 non esiste in X. Esercizio 6.13 Dimostrare che i) la relazione a b in C definita da a b se e solo se Im a ≤ Im b è una relazione di preordine. ii) la relazione a r b in C definita da a r b se e solo se Re a ≤ Re b è una relazione di preordine. È utile rappresentare un insieme finito ordinato sul piano di Gauss-Argand, nel modo seguente. Sia (X, ≤) un insieme dotato di preordine. Se a, b ∈ X vengono rappresentati da α e β sul piano di Gauss-Argand, allora a < b se e solo se α ≺ β, ove ≺ è la relazione d’ordine definita sui complessi come nel punto (c) dell’esempio 6.13. Se uniamo con una linea i punti tra loro confrontabili, otteniamo un digramma nel piano, noto come il diagramma di Hasse. Osserviamo inoltre che, per rendere meno pesante il diagramma, ogni qualvolta si ha a < b < c e la relazione è transitiva, si omette di disegnare la linea che collega a con c. Ad esempio, se consideriamo l’insieme X = {a, b, c} e la relazione d’ordine definita su P(X) come nel punto (a) dell’esempio 2.37, otteniamo il seguente diagramma: X = {a, b, c} ❅ {a, b} {a, c} ❅ ❅ ❧ {a}❧ ❧ ❅ ❅ ❅ ❅ ❅ {b, c} ❅ ❅{b} ❧ ❧★ ❅ ❅ ★{c} ★ ★ ★ ∅ Diagramma di Hasse di P ({a, b, c}) Esercizio 6.14 Dimostrare che ogni ordine buono è anche totale. Esercizio 6.15 Si determinino gli elementi massimali e minimali nell’insieme parzialmente ordinato per divisibilità dei divisori propri di 30, 56 e 120. 59 Svolgimento. Tra i divisori propri di 30 gli elementi minimali sono 2, 3, 5 e gli elementi massimali sono 6, 10 e 15. Tra i divisori propri di 56 gli elementi minimali sono 2 e 7 e gli elementi massimali sono 8 e 28. Tra i divisori propri di 120 gli elementi minimali sono 2, 3, 5 e gli elementi massimali sono 60, 40 e 24. 30 ❅ 6❅ 10 ❅ ❅ ❍ 2 ❍❍ ❅ ❅ ❅ ❅ ❅ 15 ❅ ❅ 3 ✟✟5 ✟ ❍✟ ❅ 1 L’insieme ordinato dei divisori di 30 6.3 Esercizi sui prodotti cartesiani Esercizio 6.16 Sia A 6= ∅. Trovare una biiezione tra A{1,2,...,n} ed il prodotto cartesiano {z. . . × A}. |A × A × n volte Suggerimenti. Si procede come nel Lemma 5.5, mettendo in corrispondenza all’applicazione f : {1, 2, . . ., n} → A la n-upla ordinata (f (1), f (2), . . ., f (n)). Nel verso opposto, alla n-upla ordinata (a1 , a2 , . . . , an) si associ l’applicazione f : {1, 2, . . ., n} → A definita da f (1) = a1 , f (2) = a2 , . . . , f (n) = an . Esercizio 6.17 Dimostrare che ϕ : P(X) → 2X definita da ϕ(A) = χA è una biiezione. Svolgimento. Per ogni funzione f : X → {0, 1} si ha f = ϕ({x ∈ X : f (x) = 1}), pertanto ϕ è suriettiva. D’altra parte, se χA = χB , allora A = B. Infatti, se a ∈ A, allora χB (a) = χA (a) = 1, perciò a ∈ B e pertanto A ⊆ B. Analogamente si vede che B ⊆ A, e quindi A = B. Questo dimostra che ϕ è anche iniettiva. Esercizio 6.18 Sia n > 1 e siano A1 , A2 , . . . , An insiemi non vuoti. Denotiamo con X l’insieme delle applicazioni f : {1, 2, . . . , n} → A1 ∪ A2 ∪ . . . ∪ An con la proprietà f (1) ∈ A1 , f (2) ∈ A2 , . . ., f (n) ∈ An . Trovare una biiezione tra X ed il prodotto cartesiano A1 × A2 × . . . × An . Suggerimenti. All’applicazione f ∈ X mettere in corrispondenza la n-upla ordinata (f (1), f (2), . . . , f (n)) di A1 ×A2 ×. . .×An . Questo definisce un’applicazione ϕ : X → A1 ×A2 ×. . .× 60 An . Provare che ϕ è invertibile, avente come inversa l’applicazione ψ : A1 × A2 × . . .× An → X che alla n-upla (a1 , a2, . . . , an ) associa l’applicazione f : {1, 2, . . ., n} → A1 ∪ A2 ∪ . . . ∪ An definita da f (1) = a1 , f (2) = a2 , . . ., f (n) = an . Esercizio 6.19 Sia n > 1 e siano A1 , A2 , . . ., An insiemi non vuoti. (a) Dimostrare che la proiezione pi (i = 1, 2, . . ., n) è suriettiva, ma non necessariamente iniettiva. (b) Siano B1 , B2 , . . . , Bn insiemi non vuoti e siano fi : Ai → Bi applicazioni (i = 1, 2, . . ., n). Si definisca l’applicazione f1 × f2 × . . . × fn : A1 × A2 × . . . × An → B1 × B2 × . . . × Bn con (f1 × f2 × . . . × fn )(a1 , a2 , . . . , an ) = (f1 (a1 ), f2 (a2 ), . . . , fn (an )). Dimostrare che: – pi ◦ (f1 × f2 × . . . × fn ) = fi per i = 1, 2, . . ., n; – f1 × f2 × . . . × fn è iniettiva (risp. suriettiva) se e solo se tutte le applicazioni fi sono iniettive (risp. suriettive). Esercizio 6.20 Sia n > 1 e siano A1 , A2 , . . ., An insiemi non vuoti. (a) Trovare una biiezione tra i prodotti (A1 × A2 × . . . × An−1 ) × An e A1 × A2 × . . . × An . (b) In caso di insiemi finiti dimostrare che |A1 × A2 × . . . × An | = |A1 | · |A2 | · . . . · |An |. Suggerimenti. (a) Considerare la corrispondenza ((a1 , a2 , . . .an−1 ), an) 7→ (a1 , a2 , . . . , an ). (b) Daremo una dimostrazione per induzione su n. Sia A(n) l’affermazione che la formula è vera per tutte le n-uple di insiemi finiti A1 , A2 , . . ., An . Ovviamente, A(1) è vera. Supponiamo ora che siano vere tutte le A(k) con k < n. Poniamo B = A1 × A2 × . . . × An−1 . Allora |A1 × A2 × . . . × An−1 × An | = |B × An |. Per l’ipotesi induttiva |B × An | = |B| · |An | e |B| = |A1 | · |A2 | · . . . · |An−1 |. Ora la tesi segue immediatamente. Esercizio 6.21 Trovare l’errore nella dimostrazione al punto b) dell’Esercizio precedente e dare una dimostrazione corretta. Suggerimenti. Cercare di trovare l’errore da soli. Esercizio 6.22 Siano {Ai }i∈I e {Bj }j∈J due famiglie di insiemi non vuoti con I 6= ∅ = 6 J. Se esiste una biiezione ϕ : I → J e per ogni i ∈ I una biiezione ψi : Ai → Bϕ(i) , allora esiste Q Q anche una biiezione i∈I Ai → j∈J Bj . Esercizio 6.23 Sia {Ai }i∈I è una famiglia di insiemi non vuoti con ∅ = 6 J ⊂ I. Dimostrare Q Q Q che esiste una biiezione i∈I Ai → j∈J Aj × i∈I\J Ai . 6.4 Esercizi sugli insiemi ordinati e i prodotti cartesiani Siano (A, ≤) e (B, ≤′ ) due insiemi parzialmente ordinati. Allora sul prodotto cartesiano A × B consideriamo le relazioni binarie ≺ e ⊳ definite come segue (a, b) ≺ (a1 , b1 ) se a < a1 oppure a = a1 e b ≤′ b1 , (1) (a, b) ⊳ (a1 , b1) se a ≤ a1 e b ≤′ b1 . (2) 61 Esercizio 6.24 Dimostrare che ≺ e ⊳ sono ordini parziali (chiamati, rispettivamente, ordine lessicografico e prodotto cartesiano di ≤ e ≤′ ). Esercizio 6.25 Dimostrare che ≺ è totale se ≤ e ≤′ sono totali, mentre ⊳ non è totale se |A| > 1 e |B| > 1. L’altezza di un insieme parzialmente ordinato finito L è il massimo tra le lunghezze delle catene di L e sarà denotata con h(L), dal termine inglese height - altezza. Esercizio 6.26 Siano A = {1, 2, . . ., n} e B = {1, 2, . . . , m} con l’ordine usuale e X = A × B munito dell’ordine ⊳. Dimostrare che h(X) = m + n − 1. Suggerimenti. Supponiamo n ≤ m, allora una catena di lunghezza m + n − 1 è {(1, 1), (2, 1), (3, 1), . . ., (n, 1), (n, 2), (n, 3), . . . , (n, m)}. Ora dimostrare che ogni catena in X ha lunghezza ≤ m + n − 1. Esercizio 6.27 Siano A e B insiemi parzialmente ordinati finiti e X = A × B munito dell’ordine ⊳. Dimostrare che h(X) = h(A) + h(B) − 1. Suggerimenti. Applicare l’Esercizio 6.26. Sia (A, ≤) un insieme parzialmente ordinato. Un sottoinsieme B di A si dice una anticatena, se (B, ≤) ha l’ordine discreto (cioè, se x, y ∈ B con x 6= y allora x 6< y e y 6< x). La larghezza dell’anticatena B è il numero cardinale |B|. Se A è finito, la larghezza di A è il massimo tra le larghezze delle anticatene di A e sarà denotata con w(A), dal termine inglese width - larghezza. Esercizio 6.28 Dimostrare che L è totalmente ordinato se e solo se w(L) = 1. Esercizio 6.29 Individuare tutte le anticatene di larghezza 2 nell’insieme ordinato P ({1, 2, 3}). Esercizio 6.30 Siano A = {1, 2, . . ., n} e B = {1, 2, . . . , m} con l’ordine usuale e X = A × B munito dell’ordine ⊳. Dimostrare che w(X) = min{m, n}. Esercizio 6.31 Siano A e B insiemi parzialmente ordinati finiti e X = A × B munito dell’ordine ⊳. Dimostrare che w(X) ≥ min{h(A), h(B)}. Se A e B sono totalmente ordinati, si ha l’uguaglianza. Trovare esempi dove vale la disuguaglianza stretta. Esercizio 6.32 Sia (L, ≤) un reticolo, allora sull’insieme LX definiamo un ordine parziale nel modo seguente: f, g ∈ LX f ≺g ⇐⇒ f (x) ≤ g(x) per ogni x ∈ X. Si dimostri che (LX , ≺) è un reticolo. Svolgimento. Dimostriamo che dati due elementi f, g di LX , questi ammettono massimo e minimo. Definiamo la funzione h(x) = f (x) ∨ g(x): è ben definita perché L è un reticolo e f (x), g(x) sono due elementi del reticolo. Allora h = f ∨ g. Analogamente per l’estremo inferiore. 62 Esercizio 6.33 Sia (S, ≤) un insieme ordinato e nell’insieme S S delle applicazioni di S in sè si consideri la relazione binaria R, definita ponendo f Rg se e solo se f (x) ≤ g(x) per ogni x ∈ S. Provare che R è una relazione d’ordine e che R risulta totale se e solo se S è costituito da un solo elemento. Suggerimenti. La dimostrazione che R sia una relazione d’ordine deriva dal fatto che ≤ è una relazione d’ordine in S. Vediamo per esempio la dimostrazione della proprietà antisimmetrica: f Rg e gRf implicano che f (x) ≤ g(x) e g(x) ≤ f (x) per ogni x ∈ S. Per la proprietà antisimmetrica di ≤, si ha f (x) = g(x) per ogni x ∈ S, cioè f = g. Supponiamo che R sia di ordine totale e supponiamo che esistano due elementi distinti x ed y in S. Consideriamo la funzione f : S → S tale che f (x) = y , f (y) = x e f (z) = z per ogni altro z in S, z 6= x, z 6= y. Allora f ed id sono due elementi di S S , pertanto devono essere confrontabili rispetto alla relazione R. Allora si avrà o f Rid oppure idRf . Nel primo caso si ha f (x) = y ≤ id(x) = x e f (y) = x ≤ id(y) = y, da cui si ricava x = y. Si conclude allo stesso modo nel secondo caso. Se S contiene solo un elemento, allora anche S S contiene solo un elemento e l’ordine è totale. 6.5 Esercizi sui numeri cardinali Esercizio 6.34 Se un insieme X non è infinito, allora esiste una biiezione X → {1, 2, . . ., n}. Suggerimenti. Ragioniamo per assurdo, supponendo che non esista alcuna biiezione dall’insieme {1, 2, . . ., n} all’insieme X per alcun n e quindi, non esista una suriezione {1, 2, . . ., n} → X per alcun n. Pertanto, esistono almeno n + 1 elementi distinti di X. Possiamo costruire cosı̀ una iniezione N → X nel modo seguente. Scegliamo un elemento arbitrario x0 ∈ X e poniamo f (0) = x0 . Supponiamo di aver già definito f (0), . . ., f (n − 1). Poichè X ha un elemento xn diverso da f (0), . . ., f (n − 1), possiamo porre f (n) = xn ecc. Esercizio 6.35 Se un insieme X ammette una suriezione X → X che non è iniettiva, allora esiste anche una iniezione X → X che non è suriettiva. Esercizio 6.36 Dimostrare che vale |A| ≤ |B| per due insiemi A, B se e solo se esiste un’applicazione suriettiva B → A. Svolgimento. Da |A| ≤ |B| concludiamo che esiste un’iniezione f : A → B. Per definire un’applicazione suriettiva g : B → A scegliamo un elemento arbitrario a0 ∈ A e poniamo g(b) = a se risulta b = f (a) per qualche a ∈ A (che è necessariamente unico). Se b ∈ B \ f (A) poniamo g(b) = a0 . Se esiste un’applicazione suriettiva B → A, allora il Teorema 5.3 implica che esiste un’applicazione iniettiva A → B, e quindi vale |A| ≤ |B|. Esercizio 6.37 Per ogni insieme X si ha |X| < |P(X)|. Dimostrazione. Notiamo che |X| ≤ |P(X)| in quanto esiste l’applicazione jX : X → P(X) che manda ogni elemento x ∈ X nel singoletto {x} e tale applicazione è iniettiva. Per dimostrare che non vale |X| ≥ |P(X)| basta applicare il Teorema di Cantor. Esercizio 6.38 Sia f : X → X un’applicazione iniettiva, ma non suriettiva. Allora per ogni x ∈ X \ f (X) esiste un’applicazione iniettiva h : N → X con h(0) = x. 63 Svolgimento. Scegliamo x ∈ X \ f (X) e definiamo un’applicazione iniettiva h : N → X con h(0) = x. Cominciamo ponendo h(0) = x. Supponendo di aver definito h(n) per qualche n ∈ N, poniamo h(n + 1) = f (h(n)). Allora l’insieme A di tutti gli n ∈ N per i quali h(n) è definito contiene 0 e se n ∈ A, allora anche n + 1 ∈ A. Quindi A = N per il principio di induzione. In questo modo h : N → X è stata definita. Supponiamo per assurdo che h non sia iniettiva. Allora esistono n < m in N con h(n) = h(m). Scegliamo n minimo con questo proprietà (questo è possibile per il principio del minimo applicato all’insieme B = {n ∈ N : h(n) = h(m) per qualche m > n}). Vediamo che questa scelta implica n = 0. Infatti, supponiamo per assurdo n > 0. Allora f (h(n − 1)) = h(n) = h(m) = f (h(m − 1)). Per l’iniettività di f concludiamo che h(n − 1) = h(m − 1) e quindi n − 1 ∈ A contrariamente alla scelta di n come elemento minimale di A. Questo dimostra che la nostra ipotesi per assurdo implica h(0) = h(m) per qualche m > 0. Ora x = h(0) = h(m) = f (h(m − 1)) contraddice la scelta di x con x ∈ X \ f (X). L’assurdo dimostra che h è iniettiva. Esercizio 6.39 Sia X un insieme non vuoto e sia A = {Ai : i ∈ I} una famiglia di sottoinsiemi di S X tali che a) X = i∈I Ai , b) A è chiusa per intersezioni. Allora la relazione ∼ su X definita da x ∼ y se e solo se per ogni i ∈ I si ha x ∈ Ai se e solo se y ∈ Ai , è una relazione di equivalenza. S Esercizio 6.40 Sia X = i∈I Ci una partizione e sia Y un sottoinsieme di X. Se per ogni i ∈ I hi : Ci → Ci ∩ Y è un applicazione iniettiva, allora l’applicazione h : X → Y definita da h(x) := hi (x) per x ∈ Ci è iniettiva. Inoltre, h è biiettiva se e solo se ogni hi è biiettiva. In particolare, se per ogni i ∈ I esiste una biiezione hi : Ci → Ci ∩ Y , allora esiste anche una biiezione h : X → Y . Esercizio 6.41 Sia X un insieme infinito. Dimostrare che: a) per ogni elemento x ∈ X esiste una biiezione fra X e X \ {x}; b) per ogni insieme finito F ⊆ X esiste una biiezione fra X e X \ F . Esercizio 6.42 Dimostrare che esiste una biiezione fra l’intervallo chiuso [0, 1] e l’insieme R dei numeri reali. Costruire esplicitamente una tale biiezione. Esercizio 6.43 Dimostrare che: (a) i seguenti insiemi sono numerabili: Z, Q, Z × Z, Q × Q × Q; S (b) se A1 , A2 , . . ., An , . . . sono insiemi numerabili, allora anche gli insiemi ∞ n=1 An e A1 × A2 × . . . × Ak sono numerabili per ogni k. Suggerimenti. (a) Per vedere che Z è numerabile applicheremo il Teorema di Cantor– Bernstein. Poiché esiste una iniezione di N in Z (l’inclusione), basta vedere che esiste anche una iniezione h : Z ֒→ N. Definiamo h(0) = 0 e h(n) = 2n se n > 0, altrimenti h(n) = 1 − 2n. Non è difficile verificare che h è iniettiva (addirittura biiettiva). Questo dimostra che Z è numerabile e implica anche che Z × Z è numerabile per il Lemma 5.10. Poiché ogni numero razionale r si può scrivere almeno in un modo come r = a/b, con a, b ∈ Z (e b 6= 0), esiste una suriezione Z × Z → Q. Poiché Z × Z è numerabile, allora anche Q risulta numerabile. S S∞ (b) Per vedere che ∞ n=1 An è numerabile basta trovare una suriezione f : N × N → n=1 An . Sia fn : N → An una suriezione che testimonia la numerabilità di An . Definiamo f con f (n, m) = fn (m) per ogni n, m ∈ N. Per la seconda parte si usi induzione su k e il Lemma 5.10. 64 Esercizio 6.44 Sia n > 0 un numero naturale fissato e sia S l’insieme delle soluzioni delle equazioni (a1 x2 + b1 x + c1 )(a2 x2 + b2 x + c2 ) . . . (an x2 + bn x + cn ) = 0, dove a1 , b1 , c1, a2 , b2 , c2, . . . an , bn, cn variano nell’insieme dei numeri razionali. Si dimostri che S è numerabile. Esercizio 6.45∗ Dimostrare che il Teorema di Zermelo implica l’assioma della scelta. Q Suggerimenti. Si fissi un buon ordine ≤ su I e si ponga I0 = {α ∈ I : β≤α Aβ 6= ∅}. Dimostrare che: a) se S Q β ∈ I0 e α ≤ β allora anche α ∈ I0 ; b) β∈I0 Aβ 6= ∅. (Infatti, se fα : {β ∈ I : β ≤ α} → i≤α Ai è definita da fα (β) ∈ Aβ per S β ≤ α, definiamo f : I0 → i∈I0 Ai ponendo f (α) = fα(α).) c) I0 = I. Si ragiona per assurdo, supponendo I0 6= I. Allora esiste il minimo α0 dell’insieme Q Q Q non vuoto I \ I0 . Ora Q β∈I0∪{α0 } Aβ = {β∈I:β≤α0} Aβ 6= ∅ poiché β∈I0 ∪{α0} Aβ è equipotente al prodotto Aα0 × i∈I0 Ai per l’Esercizio 6.23. Quindi, α0 ∈ I0 contrariamente all’ipotesi α0 6∈ I0 - assurdo. Esercizio 6.46 Trovare una forma esplicita per l’applicazione h : N × N → N nell’Esercizio 5.10. S Esercizio 6.47 Siano X ed Y due insiemi che ammettono delle partizioni X = {Xi : i ∈ I} S e Y = {Yi : i ∈ I} rispettivamente, con |Xi| = |Yi | per ogni i ∈ I. Allora X ed Y sono equipotenti. Suggerimenti. Per ogni i ∈ I scegliamo una biiezione hi : Xi → Yi , che proviene dal fatto che |Xi| = |Yi |. Ora definiamo h : X → Y ponendo h(x) = hi (x), se x ∈ Xi. Adesso basta verificare che h è una biiezione. Esercizio 6.48∗ Sia X un insieme infinito. Allora esiste una partizione {Xi : i ∈ I} di X in insiemi numerabili. Svolgimento. Consideriamo la famiglia A di tutte le famiglie A = {Xi : i ∈ I} di sottoinsiemi numerabili a due a due disgiunti Xi di X. Ordiniamo A per inclusione. Allora (A, ⊆) è un S S insieme ordinato induttivo. Infatti, se C è una catena in A, allora C ∈ A, poiché A, B ∈ C implica che A e B appartengono allo stesso membro della catena C e quindi sono disgiunti. S Inoltre, C contiene ogni membro di C e quindi è un maggiorante di C in (A, ⊆). Quindi possiamo applicare il lemma di Zorn ad (A, ⊆) e affermare che esiste una famiglia massimale S M = {Xi : i ∈ I} ∈ A. Sia Y = {Xi : i ∈ I}. Allora X \ Y è finito (altrimenti, si prende un insieme infinito Z ⊆ X \ Y e la famiglia {Z} ∪ M ∈ A e contiene strettamente M, assurdo). Aggiungendo l’insieme finito X \ Y a qualche membro Xi0 di M troviamo una famiglia M′ = {Xi0 ∪ (X \ Y )} ∪ {Xi : i ∈ I, i 6= i0 } ∈ A. Inoltre, M′ è una partizione di X e quindi M′ è la partizione desiderata. Esercizio 6.49 |X| = |X × {0, 1}| per ogni insieme infinito. Suggerimenti. Sia {Xi : i ∈ I} una partizione di X in insiemi numerabili. Allora |Xi × {0, 1}| = |Xi | per ogni i ∈ I per il Lemma 5.10. Poiché {Xi × {0, 1} : i ∈ I} è una partizione di X × {0, 1}, basta applicare l’Esercizio 6.48. 65 Esercizio 6.50 Se X è un insieme infinito, allora esiste una partizione X = X1 ∪ X2 di X con |X1 | = |X2 | = |X|. Suggerimenti. Per l’Esercizio 6.49 esiste una biiezione f : X → X × {0, 1}. Ora se poniamo Xi = f −1 (X × {i − 1}) per i = 1, 2 abbiamo la partizione desiderata. Esercizio 6.51∗ |X| = |X × N| per ogni insieme infinito. Esercizio 6.52 Se X è un insieme infinito, allora esiste una partizione X = con |Xn | = |X| per ogni n ∈ N. S n∈ Xn di X ✄ Suggerimenti. Per l’Esercizio 6.51 esiste una biiezione f : X → X × N. Ora se poniamo Xn = f −1 (X × {n}) per n ∈ N abbiamo la partizione desiderata. Esercizio 6.53 Se X è infinito e per ogni n ∈ N sia ha |An | ≤ |X|, allora anche | |X|. S∞ n=1 An | ≤ Suggerimenti. Per l’Esercizio 6.36 basta trovare un’applicazione suriettiva X → A = S∞ A . Sempre per l’Esercizio 6.36, per ogni n ∈ N esiste un’applicazione suriettiva n=1 n fn : X → An che testimonia il fatto |An | ≤ |X|. Sia f : X × N → A, definita con f (x, n) = fn (x) per ogni n ∈ N e x ∈ X. Allora f è suriettiva. Per l’Esercizio 6.51 esiste un’applicazione suriettiva h : X → X × N. Adesso la composizione f ◦ h : X → A è suriettiva. Esercizio 6.54∗ Dimostrare che |R| = c. Suggerimenti. Sfruttare il fatto che |P(N)| = |2 | e definire un’iniezione di P(N) nell’intervallo [0, 1] (e quindi in R) nel modo seguente. Ogni elemento c ∈ 2 si può pensare come una sucPn −k cessione c1 , c2, c3 . . . cn . . ., dove cn ∈ {0, 1}. Poniamo an = e notiamo che k=1 ck · 10 la successione an è crescente a soddisfa 0 ≤ an ≤ 1. Pertanto esiste il limite a = limn e appartiene all’intervallo [0, 1]. Poniamo f (c) = a. Provare che l’applicazione f : 2 → [0, 1] cosı̀ definita è iniettiva. Questo dimostra che |R| ≥ c. Nell’altro verso, per vedere che |R| ≤ c notiamo che R è unione numerabile degli intervalli [n, n + 1], al variare di n ∈ Z. Quindi, per 6.53 basterebbe dimostrare che [0, 1] ≤ c (essendo |[n, n + 1]| = |[0, 1]| per ogni n ∈ N). Pertanto basta provare che [0, 1] ammette un’iniezione in P(N). Poiché ogni numero irrazionale in [0, 1] ammette un’unica rappresentazione binaria 0, c1 c2 c3 . . . cn . . ., dove cn ∈ {0, 1} e poiché i numeri razionali formano un insieme numerabile, possiamo concludere che [0, 1] ammette un’iniezione in P(N). ✄ ✄ ✄ Esercizio 6.55 ∗∗ |X × X| = |X| per ogni insieme infinito X. Svolgimento. Sia A0 un sottoinsieme numerabile di X. Per il Lemma 5.10, esiste una biiezione iA0 : A0 ×A0 → A0 . Si consideri la famiglia A delle coppie (A, iA), dove A0 ⊆ A ⊆ X e iA : A × A → A è una biiezione che estende iA0 . Si consideri in A la relazione ≤ definita da (A, iA) ≤ (B, iB ) se e solo se A ⊆ B e iB ↾A . Non è difficile provare che ≤ è un ordine per il quale (A, ≤) è un insieme ordinato induttivo. Per il Lemma di Zorn esiste un membro massimale (M, iM ) ∈ A. Chiaramente (M, iM ) ∈ A implica |M × M | = |M |. 66 (1) Se |M | = |X|, allora abbiamo anche |X × X| = |M × M | (vedi l’Esercizio 6.22), e quindi l’uguaglianza (2) assieme alla nostra ipotesi implica |X × X| = |X|. Supponiamo per assurdo che |M | = 6 |X|. Poiché |M | ≤ |X|, resta la sola possibilità |M | < |X|. D’altra parte X = M ∪ (X \ M ), quindi |X \ M | ≥ |M | per il Teorema 5.11. Quindi possiamo trovare un sottoinsieme N ⊆ X \ M con |N | = |M |. Ora M ′ = M ∪ N contiene M propriamente, e M ′ × M ′ = (M × M ) ∪ D, dove D = (M × N ) ∪ (N × M ) ∪ (N × N ). Ora |N × M | = |M × N | = |N × N | = |M | = |N |. Allora esiste una biiezione D → N , che, assieme alla biiezione iM : M × M → M ci da’ una biiezione iM ′ : M ′ × M ′ → M ′ che estende iM . Quindi (M ′ , iM ′ ) ∈ A e (M, iM ) < (M ′ , iM ′ ), assurdo. Pertanto |M | = |X|. Esercizio 6.56∗ Dimostrare che |X| = |X × {0, 1}| per ogni insieme infinito senza far ricorso all’Esercizio 6.48. Suggerimenti. Ragionare seguendo lo svolgimento del Lemma 5.13. A questo scopo considerare la famiglia A delle coppie (A, iA), dove A ⊆ X e iA : A × {0, 1} → A è una biiezione, ordinando A nello stesso modo. Applicando il Lemma di Zorn trovare un membro massimale (M, iM ) ∈ A. Ragionare per assurdo per provare che |M | = |X| e concludere che la tesi vale. Infatti, se |M | < |X| trovare N ⊆ X con |N | = |M |. Ora |N | = |N × {0, 1}| essendo |M | = |M × {0, 1}|. Concludere che per M ′ = M ∪ N esiste una biiezione tra M ′ × {0, 1} = (M × {0, 1}) ∪ (N × {0, 1}) e M ∪ N = M ′ che estende iM e contraddice la massimalità di (M, iM ). 7 Complementi sui numeri primi In questa sezione daremo informazione su due celebri ”generatori” di numeri primi (i numeri di Fermat e i numeri di Mersenne) e sui numeri perfetti ed amicabili, legati in modo del tutto naturale ai numeri primi. Concluderemo con qualche cenno sulla distribuzione dei numeri primi e sul gioco di Conway che permette di generare i numeri primi ragionando solamente sui primi dieci numeri primi 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29 e quattordici frazioni composte da questi. 7.1 I numeri di Fermat n I numeri Fn = 22 + 1 (n = 0, 1, 2, . . .) sono noti come numeri di Fermat. Osserviamo subito che se vogliamo ottenere dei numeri primi aggiungendo 1 a potenze di 2, dobbiamo imporre all’esponente di essere lui stesso una potenza di 2. Infatti: Esercizio 7.1 Dimostrare che se 2m + 1 è primo, allora m = 2n per qualche numero naturale n. Suggerimenti. Se m = q · r, dove r > 1 è un divisore dispari di m, allora 2qr + 1 = (2q + 1)(2q(r−1) − · · · + 1) e 1 < 2q + 1 < 2m + 1, quindi 2m + 1 non può essere primo. Non avendo m dei divisori dispari concludiamo che m = 2n per qualche numero naturale n. Esercizio 7.2 Dimostrare che Fn+1 = (Fn − 1)2 + 1. Di conseguenza, Fn+1 è primo se non ha divisori primi p con p < Fn − 1. Lemma 7.3 Dimostrare che: (a) se p è un divisore primo del numero di Fermat Fn allora p è del tipo 2n+1 m + 1; (b) i numeri di Fermat sono a due a due coprimi. 67 n Dimostrazione. (a) Notare che p|Fn implica 22 ≡p −1 e di conseguenza, elevando al n+1 quadrato, 22 ≡p 1. Quindi, op (2) divide 2n+1 . Ora, per il punto (a) dell’Esercizio 3.34, la prima congruenza dimostra che op (2) non è un divisore di 2n . Poiché tutti i divisori di 2n+1 sono del tipo 2k , concludiamo che op (2) = 2n+1 . Per il teorema di Fermat 2p−1 ≡p 1. Ora (b) dell’Esercizio 3.34 ci permette di concludere che 2n+1 |p − 1. Quindi, p − 1 = 2n+1 m per qualche m ∈ Z. m+1 n (b) Se p|Fn e p|Fm , con n > m, allora 22 ≡p 1 per (a). Poiché m + 1 ≤ n, 22 è potenza m+1 n n di 22 e quindi 22 ≡p 1. D’altra parte, p|Fn implica anche 22 ≡p −1, assurdo. Pertanto nessun numero primo p divide simultaneamente Fn ed Fm , quindi Fn e Fm sono coprimi. Ci si può a questo punto chiedere quali di questi numeri di Fermat sono effettivamente dei primi. La risposta per i primi 5 numeri di Fermat è stata data da Eulero nel 1732. Si osservi che, a parte F0 , F1 , F2 , F3 e F4 non sono noti altri numeri di Fermat primi. Proposizione 7.4 (Fermat) F0 , F1 , F2 , F3 e F4 sono primi, mentre F5 = 641 · 6700417 non è primo Dimostrazione. Per F0 = 3, F1 = 5 e F2 = 17 questo è ovvio. Segue dall’Esercizio 7.2 che per verificare se Fn è primo basta vedere che Fn non ha divisori primi p < Fn−1 − 1. Per F3 = 257 notiamo che i divisori primi di F3 con p < 16 = F2 − 1 possono essere tra 2, 3, 5, 7, 11 e 13. Secondo il Lemma 7.3, i divisori primi di F3 sono del tipo 16k + 1 e quindi nessuno di questi primi divide F3 . Per F4 = 232 + 1 notiamo che per il Lemma 7.3 i divisori primi di F4 sono del tipo 32k + 1. Ma i numeri primi di questo tipo minori di F3 − 1 = 256 sono 33, 65, 97, 129, 161, 193 e 225. Tra questi solo 97 e 193 sono primi. Che nessuno dei primi 97 e 193 divida F4 segue dallo svolgimento dell’Esercizio 3.36. Per F5 sappiamo dal Lemma 7.3 che i divisori primi di F5 sono del tipo 64k + 1. Tra questi 65 e 129 non sono primi. Dal suggerimento all’Esercizio 3.36 segue che nè 193 nè 257 dividono F5 = 232 + 1. Tra i numeri successivi in questa serie 321, 385 e 513 non sono primi, mentre 449 e 577 sono primi ma non dividono F5 . Per 641 si dimostra che divide F5 osservando che da 641 = 24 + 54 = 27 · 5 + 1 seguono le congruenze 24 ≡641 −54 e 27 · 5 ≡641 −1. Elevando l’ultima congruenza alla quarta e sostituendo 54 con −24 si ha 1 ≡641 228 · 54 ≡641 −228 · 24 ≡641 −232 , cioè 641 divide F5 . Esercizio 7.5 Rifare l’Esercizio 3.21, usando il piccolo teorema di Fermat per p = 2 e p = 5. 7.2 Numeri primi di Mersenne I numeri del tipo Mn = 2n − 1 sono noti come numeri di Mersenne, dovuto al fatto che Mersenne (1588-1648) li ha studiati in modo sistematico nel suo trattato ”Cogita physicomatematica”. Tuttavia, questi numeri erano noti anche prima (ai greci, vedi il paragrafo 7.3) e al matematico italiano Cataldi che sapeva che M17 e M19 sono primi. Esercizio 7.6 Siano x, n, m numeri naturali maggiori di 0. Dimostrare che: (i) (xn − 1) = (x − 1)(xn−1 + xn−2 + . . . + x + 1); (ii) se m divide n, allora (xm − 1) divide (xn − 1); (ii) se xm − 1 è primo, allora x = 2 e m è primo. 68 Svolgimento. i) Basta eseguire il prodotto di destra e osservare che si cancellano tutti i termini, eccetto il primo e l’ultimo. ii) Se m|n, allora n = mq, pertanto (xn − 1) = ((xm)q − 1) = (xm − 1)((xm)n−1 + . . . + xm + 1) per il punto i). Da questo si vede che (xm − 1) divide (xn − 1). iii) Se x > 2, allora xm − 1 = (x − 1)(xr−1 + · · · + x + 1) per il punto (i), e quindi è divisibile per x − 1. Se d divide m allora xd − 1 divide xm − 1 per il punto (ii). Abbiamo visto che Mn è primo solo se n è primo (Esercizio 7.6), tuttavia M11 non è primo: si verifica che è divisibile per 23, elevando al quadrato la congruenza 26 ≡23 −5. Il seguente Esercizio chiarisce perché si verifica con 23 il fatto che M11 non è primo (è il più piccolo numero primo che ha resto 1 modulo 11). Esercizio 7.7 Se un primo p divide un numero di Mersenne Mn , allora p ≡n 1 se n è primo. Suggerimenti. Poiché 2p−1 ≡p 1 per il piccolo teorema di Fermat e 2n ≡p 1 per ipotesi, abbiamo n|p − 1 poiché n è primo. Gran parte dei numeri di Mersenne sono composti (per esempio, tutti gli Mn con 2300 ≤ n ≤ 3300). Tuttavia, per lungo tempo, i più grandi numeri primi noti sono stati i numeri primi di Mersenne. Il motivo di questo è il seguente teorema (criterio) scoperto da Lucas che fa uso dei seguenti numeri Ln , detti numeri di Lucas definiti da L1 = 4 e Ln = L2n−1 − 2 per n > 1. Teorema 7.8 Per n > 2 il numero Mn è primo se e solo se Mn divide il numero Ln−1 . Facciamo alcune verifiche. Si vede facilmente che M3 = 7 divide L2 = 14, M5 = 31 divide L4 = L23 − 2 = 1942 − 2 = 37954 (infatti, 194 ≡31 8, e quindi L4 ≡31 82 − 2 = 62 ≡31 0). Per n = 7 si ha M7 = 127, mentre L5 = 1416317954 ≡128 422 − 2, poiché L4 ≡128 672 − 2 ≡128 67 + 66 · 67 − 2 = 65 + 33 · 134 ≡128 65 + 33 · 7 = 65 + 231 ≡128 42. Ora L5 ≡128 126 · 14 − 2 ≡128 −14 − 2 = −16, quindi L6 ≡128 162 − 2 = 2 · 8 · 16 − 2 = 2(8 · 16 − 1) = 2 · 127 ≡128 0. Lasciamo al lettore la verifica del fatto che M11 non divide L10 , non essendo M11 un numero primo. D’altra parte, M13 divide L12 , essendo M13 un numero primo: Esercizio 7.9 Dimostrare che M13 = 213 − 1 è un numero primo. Suggerimenti. Per l’Esercizio 7.7 ogni divisore primo p di M13 è del tipo p = 13k + 1. In più essendo p dispari, si avrà anche p = 26k + 1 (in altre parole k può essere solo pari). D’altra parte, M13 < 912 , quindi p ≤ 89 e quindi k = 1, 2, 3 sono gli unici possibili valori di k. Per k = 1 risulta p = 27 non primo. Resta da verificare che 53 e 79 non dividono M13 . Usando questo criterio, Lucas ha provato nel 1875 che il numero M127 è primo e questo risultato rimase insuperato per 75 anni, data la grandezza di M127 = 2127 = 170141183460469231731687303715884105727. 148 Solo nel 1951, con l’uso dei calcolatori, fu trovato un primo più grande, il numero 2 17+1 (con 44 cifre, mentre M127 ne ha solo 39). I numeri M23209 e M44497 sono primi, ed erano i più grandi numeri primi verso l’inizio degli anni ottanta del secolo scorso. L’importanza dei numeri primi di Mersenne diviene più chiara nel paragrafo successivo. 69 7.3 Numeri perfetti e numeri amicabili Si denoti con σ(n) la somma dei divisori di n. Chiaramente la somma σ(n) − n di tutti i divisori di n minori di n misura, in un certo senso, la quantità di divisori di n. I numeri n con pochi divisori, cioè σ(n) − n < n si dicono scarsi, mentre quelli con molti divisori, cioè σ(n) − n > n si dicono abbondanti. Per esempio, 10 è scarso, tutti i numeri primi sono scarsi, mentre 12 e 60 sono abbondanti. Per questo motivo i matematici antichi preferivano i sistemi di numerazione a base 12 o 60 (per esempio in Babilonia). Da questo punto di vista si capisce perché la scelta del termine numero perfetto nella seguente Definizione 7.10 Un numero naturale n dicesi perfetto se σ(n) = 2n. Esercizio 7.11 Dimostrare che 6, 28 e 496 sono perfetti. I numeri perfetti erano ben noti nell’antica Grecia. Prima di descrivere tutti i numeri perfetti pari vedremo alcune proprietà utili della funzione σ. Esercizio 7.12 Dimostrare che : k+1 (a) se p è primo, allora σ(pk ) = p p−1−1 ; (b) se n = n1 n2 con (n1 , n2 ) = 1 allora σ(n) = σ(n1 )σ(n2 ). (c) se n = pk11 . . . pks s allora σ(n) = k +1 p11 −1 p1 −1 ... pk1s +1 −1 ps −1 . Svolgimento. (a) Tutti i divisori di pk sono del tipo ps per 0 ≤ s ≤ k. (b) Se d divide n1 n2 , allora raccogliendo i primi che compaiono nella fattorizzazione di n1 e quelli che appaiono nella fattorizzazione di n2 troviamo una fattorizzazione d = d1 d2 , con d1 |n1 e d2 |n2 . Quindi    X X X X σ(n1 n2 ) = d= d1 d2 =  d1   d2  = σ(n1 )σ(n2 ). d|n1 n2 (c) Segue da (a) e (b). d1 |n1 ,d2 |n2 d1 |n1 d2 |n2 Il punto (a) del seguente teorema era noto dal famoso trattato di Euclide. Il punto (b) è stato dimostrato da Eulero. Teorema 7.13 perfetto. (a) Sia p = 2n − 1 un numero primo. Allora 21 p(p + 1) = 2n−1 (2n − 1) è (b) Dimostrare che ogni numero perfetto pari è di questo tipo. Suggerimenti. (a) è ovvio perché con 2n − 1 primo σ(2n−1 (2n − 1)) = (2n − 1)σ(2n − 1) = 2n (2n − 1). (b) Sia n = 2s n1 un numero perfetto, con n1 dispari. Allora l’ipotesi σ(n) = 2n ci dà (2s+1 − 1)σ(n1 ) = 2s+1 n1 che implica 2s+1 − 1|n1 . Sia n1 = (2s+1 − 1)k. Allora σ(n1 ) = 2s+1 k. Allora k = 1, perché altrimenti σ(n1 ) ≥ n1 + k + (2s+1 − 1) + 1 = 2s+1 k + 2s+1 > 2s+1 k. Ora σ(n1 ) = n1 + 1 implica che n1 = 2s+1 − 1 è primo. Il teorema dice in sostanza, che i numeri perfetti pari sono del tipo 2n−1 Mn , dove Mn è un primo di Mersenne. Non è ancora noto se esistono numeri perfetti dispari. Nell’antichità conoscevano anche i cosiddetti numeri amicabili, cioè coppie di numeri naturali a e b, tali che ognuno sia uguale alla somma dei divisori dell’altro. In termini precisi, σ(a)−a = b 70 e σ(b) − b = a. Quindi, σ(a) = a + b = σ(b). La prima coppia di numeri amicabili proviene da Pitagora: 220 e 284. Si racconta addirittura che, alla domanda “Che cos’è un amico?”, il grande Pitagora abbia risposto: ”Uno che sia l’altro ‘Io’, come 220 e 284”. Il seguente teorema del matematico arabo Thabit (836–901) ci dà altre coppie di numeri amicabili. Teorema 7.14 Se i numeri p = 3 · 2n−1 − 1, q = 3 · 2n − 1 e r = 9 · 22n−1 − 1 sono primi, allora i numeri A = 2n · p · q e B = 2n · r sono amicabili. La dimostrazione segue facilmente dall’Esercizio 7.12. Con n = 2 troviamo la coppia 220 e 284 di Pitagora. Non è noto se Thabit conoscesse altri casi oltre a questo. Altre coppie si trovano con n = 4 (A = 17296, B = 18416 scoperta da P. Fermat7 ) e n = 7 (scoperta da Cartesio). Entrambi sono arrivati in modo autonomo al teorema di Thabit che nel frattempo è stato completamente dimenticato. Eulero scoprı̀ 59 coppie di numeri amicabili. Il suo record è stato superato solo nel 1929 dal matematico belga Paule Poulet (nel 1929 comparve il suo libro ”La caccia ai numeri” con 62 nuove coppie di numeri amicabili, in totale Poulet ne ha scoperte 108). Un fatto curioso è che Fermat è arrivato al suo teorema (il piccolo Teorema di Fermat) proprio nei tentativi di trovare numeri amicabili. Infatti per questo scopo bisogna fattorizzare in prodotto di primi le somme dei divisori di numeri del tipo pn . Essendo tale n −1 Fermat si è domandato se pn − 1 sia divisibile per n + 1 quando n + 1 somma uguale a pp−1 è primo. 7.4 Distribuzione dei numeri primi La domanda ”Quanti primi ci sono?” è del tutto naturale, ma posta cosı̀ ha l’ovvia risposta (infiniti !) dovuta al teorema di Euclide. Cerchiamo allora di togliere la possibilità di ”speculare” con l’infinito, chiedendo: quanti primi ci sono ≤ n, dove n è un dato numero naturale n > 1. Denotiamo la quantità di questi primi con π(n). Si ha ovviamente π(2) = 1, π(3) = π(4) = 2, π(5) = π(6) = 3, π(7) = π(8) = π(9) = π(10) = 4, π(11) = π(12) = 5, π(14) = π(15) = π(16) = π(17) = 6, π(18) = π(19) = 7, π(20) = π(21) = π(22) = 8, π(23) = π(24) = π(25) = π(26) = π(27) = π(28) = 9, . . .. Si vede che questa distribuzione è molto caotica, lunghi intervalli senza numeri primi si alternano a brevissimi intervalli tra due primi consecutivi a distanza 2 (coppie di primi gemelli). Tuttavia, ci sono certe regole come ci mostra il seguente Postulato di Bertrand. Per ogni n ∈ N+ l’intervallo [n, 2n] contiene almeno un numero primo. Infatti, per ogni n ∈ N maggiore di 3 l’intervallo [n, 2n − 2] contiene almeno un numero primo. Mentre da un teorema più preciso di Chebishev segue che esistono almeno due numeri primi p nell’intervallo [n, 2n] per ogni n ∈ N maggiore di 1. Questo ci permette di dimostrare facilmente per induzione che se p1 , p2 , . . . , pn , . . . sono tutti i numeri primi in ordine crescente, allora pn < 2n : Esercizio 7.15 Sia n > 3 un numero naturale. Dimostrare che ci sono almeno log2 n numeri primi nell’intervallo [2, n]. 7 ma nota molto prima anche a Ibn Al Banna del Marocco (1256-1321). 71 Il rapporto π(n)/n che permette di parlare della densità dei numeri primi è stato dimostrato essere circa 1/ log n (qui il logaritmo è a base e = limn (1 + 1/n)n ). In altre parole, con la crescita di n i primi diventano più ”rari”. D’altra parte, è noto che per ogni n la somma di tutti valori reciproci 1/p, dove p ≤ n è primo, è > log log n − 1 (che dà un’ulteriore dimostrazione del teorema di Euclide dell’infinità dei numeri primi). Per il postulato di Bertrand ogni intervallo del tipo [n, 2n − 2] contiene almeno un numero primo. Vediamo adesso che ci sono intervalli arbitrariamente lunghi di numeri naturali consecutivi che non contengono numeri primi. Esercizio 7.16 Sia n > 1 un intero, allora nessuno degli n − 1 numeri consecutivi n! + 2, n! + 3, . . ., n! + n è primo. Si può osservare la distribuzione dei numeri primi limitandosi a specifiche progressioni aritmetiche. Abbiamo visto (vedi gli Esercizi 3.17 e 3.18) che ciascuna delle progressioni aritmetiche 3k + 2, 4k + 3 e 6k + 5 contiene infiniti numeri primi. Esercizio 7.17 Si dimostri che ci sono infiniti numeri primi del tipo 4k + 1 e infiniti numeri primi del tipo 8k + 1. Svolgimento. Supponiamo per assurdo che ci sia un numero finito di numeri primi del tipo 4k + 1 e li elenchiamo: p1 , p2, . . . , pn . Sia adesso N = 4(p1 p2 . . . pn )2 + 1. Per la nostra ipotesi N non può essere primo essendo maggiore di tutti i pk . Sia p un divisore primo di N . Allora, per l’Esercizio 8.5, p deve essere della forma 4k + 1 e coincidere con qualche pk , assurdo perché nessun pk divide N . Similmente per i primi del tipo 8k + 1. Ragionando allo stesso modo si dimostra Esercizio 7.18 Sia s > 1 un intero. Si dimostri che ci sono infiniti numeri primi del tipo 2s k + 1. Per quanto riguarda le progressioni aritmetiche in generale, vale il seguente risultato. Teorema 7.19 (Teorema di Dirichlet) Siano a e b due numeri naturali relativamente primi. Allora esistono infiniti numeri primi della forma ak + b. Ovviamente, ak + b non può essere primo se a e b non sono relativamente primi. La seguente congettura è rimasta tuttora aperta, dopo più di duecento anni!. Congettura 7.20 (Goldbach) Ogni numero pari maggiore di 3 è somma di due numeri primi. Non è risolta nemmeno la forma più debole della congettura: ogni numero dispari maggiore di 5 è somma di tre numeri primi. 7.5 Il gioco di Conway Questo gioco permette di ottenere consecutivamente i numeri primi a partire da 2. Come base serve la seguente successione di 14 numeri razionali 17 78 19 23 29 77 95 77 1 11 13 15 15 , , , , , , , , , , , , , 55. 91 85 51 38 33 29 23 19 17 13 11 14 2 72 (∗) Si comincia con N = 2 e si rimpiazza ad ogni passo N con aN , dove a è il primo tra i numeri della successione (*) per il quale aN sia un numeri intero. Cosı̀ si ricava la successione 2, 15, 825, 725, 1825, 2275, . . . (∗∗) Infatti, il primo a tale che 2a ∈ Z è 15 2 , perciò il secondo membro di (**) è 15. Ora il primo a tale che 15a ∈ Z è 55, perciò il terzo membro è 825 = 15 · 55. È utile tenere presente anche la fattorizzazione in primi 825 = 3 · 52 · 11 e di tenere conto della fattorizzazione dei denominatori 91 = 7 · 13, 85 = 5 · 17, 51 = 3 · 17, 38 = 2 · 19, 33 = 3 · 11, 14 = 2 · 7 e dei nominatori 78 = 2 · 3 · 13, 77 = 7 · 11, 95 = 5 · 19, 15 = 3 · 5. Questo permette di vedere più 29 e cosı̀ ricaviamo facilmente che al passo successivo 825a ∈ Z accade per prima volta con 33 77 2 725 = 5 · 29. Adesso 725a ∈ Z accade per prima volta con 29 , cosı̀ ricaviamo 1825 = 52 · 7 · 11 ecc. Consigliamo il lettore di verificare che dopo un certo numero di passi si ricava 4 = 22 , poi da 4, dopo un’altra successione di passi, si ricava 8 = 23 e dopo altri passi si trova 32 = 25 . Proseguendo in questo modo, si vede che le potenze di 2 che compaiono in questa successione sono proprio quelle del tipo 2p , dove p è il numero primo di turno, cioè (∗∗) ha la forma 2, 15, . . ., 22 , 30, . . ., 23 , 60, . . ., 25 , 240, . . ., 27 , . . . , 211, . . . , 213, . . . , 217, . . . 8 Esercizi di Aritmetica Esercizio 8.1 Siano a e b due numeri naturali coprimi. Dimostrare che se il prodotto è un quadrato perfetto8 , lo sono anche entrambi i fattori a e b. Esercizio 8.2 Fattorizzare in prodotto di numeri primi i seguenti numeri 120=5!, 6!, 7!, 8!. Esercizio 8.3 Determinare con quanti zeri terminano i numeri 10! e 20! Esercizio 8.4 (a) Sia a = a3 a2 a1 a0 un numero naturale con quattro cifre decimali. Allora a è divisibile per 1001 precisamente quando a2 = a1 = 0 e a3 = a0 . In tal caso a è divisibile anche per 7, 11 e 13. In particolare, (1) 2002 è divisibile per 7, 11 e 13. (2) l’anno futuro più vicino con questa proprietà è 3003. (b) Sia a = a4 a3 a2 a1 a0 un numero naturale con cinque cifre decimali. Allora a è divisibile per 1001 precisamente quando a2 = 0, a4 = a1 e a3 = a0 . In tal caso a è divisibile anche per 7, 11 e 13. (c) Sia a = a5 a4 a3 a2 a1 a0 un numero naturale con sei cifre decimali. Allora a è divisibile per 1001 precisamente quando a5 a4 a3 = a2 a1 a0 . In tal caso a è divisibile anche per 7, 11 e 13. Esercizio 8.5 Sia p > 2 un numero primo. Dimostrare che: (a) se p divide a2 + 1 per qualche numero intero a, allora p è del tipo 4k + 1. (b) se p divide a4 + 1 per qualche numero intero a, allora p è del tipo 8k + 1. p−1 Svolgimento. (a) Essendo p dispari, per t = p−1 = (a2 )t ≡p (−1)t, 2 abbiamo 1 ≡p a quindi (−1)t = 1 e di conseguenza t = 2k è pari. Questo dimostra p = 4k + 1. (b) Dal punto (a) applicato ad a2 concludiamo che p = 4t + 1 per qualche t ∈ Z. Sia t = p−1 2 . Allora 1 ≡p ap−1 = (a4 )t ≡p (−1)t, quindi (−1)t = 1 e di conseguenza t = 2k. Questo dimostra p = 8k + 1. 8 cioè coincide con il quadrato di un altro numero naturale 73 Esercizio 8.6 Si dimostri che ogni numero naturale n > 0 si può scrivere in modo unico nella forma Σni=1 ci · i!, con 0 ≤ ci ≤ i. Svolgimento. Lo dimostriamo usando il principio di induzione nella seconda forma. Se n = 1 allora basterà prendere cn = 0 per ogni n ≥ 1 e c1 = 1. Sia ora n un numero naturale e sia m il massimo dei naturali tali che m! ≤ n, allora (m + 1)! > n. Grazie alla divisione euclidea di n per m!, esistono q, r ∈ N, con 0 ≤ r < m! tali che n = q · m! + r. Applichiamo ora a r < m! ≤ n l’ipotesi induttiva. Otteniamo r = Σri=1 ci · i!, con 0 ≤ ci ≤ i. Poiché r < m!, la sommatoria precedente si arresta ad m − 1, cioè r = Σm−1 i=1 ci · i!, con 0 ≤ ci ≤ i. Pertanto m n = q · m! + r = q · m! + Σm−1 i=1 ci · i! = Σi=1 ci · i! ponendo q = cm ed osservando che 0 ≤ q = cm ≤ m, cioè q < m + 1. Infatti (m + 1)m! = (m + 1)! > n = q · m! + r ≥ q · m!, da cui dividendo per m!, si ottiene q < m + 1. Esercizio 8.7 Sia b0 = 1, b1, b2, . . . bn , . . . una successione di numeri naturali con bn > 1 per n > 0 e sia Mk = b0 . . . bk per ogni k ∈ N. Dimostrare che ogni numero naturale n > 0 si può scrivere in modo unico nella forma Σ∞ i=0 ci · Mi , con 0 ≤ ci < bi+1 . Definiamo ora il seguente polinomio: fb (x) = x2 − x + b, con b ∈ N e b > 1. Allora fb (x) si dice un polinomio di Eulero se per ogni x ∈ N, x < b si ha che fb (x) è un numero primo. Poiché fb (−x + 1) = fb (x), anche tutti i valori fb (x) con −b + 1 < x < 0, x intero, saranno primi. Esercizio 8.8 Dimostrare che (i) se fb (x) = x2 − x + b è un polinomio di Eulero, allora b è primo; (ii) per b = 2, 3, 5, 11, 17, 41 fb (x) è un polinomio di Eulero; (iii) per b ≤ 1000, questi sono gli unici polinomi di Eulero. Suggerimenti. (i) Se esiste d ∈ N con 1 < d < b e d|b, allora d < b è un divisore proprio di fb (d), che pertanto non può essere un primo. (ii) Le prime verifiche sono immediate, per b = 17 si utilizzi l’Esercizio 3.3 e per b = 41 si facciano le opportune verifiche. (iii) Supponiamo b ≥ 7. Notiamo che per x = 2, 3, 4, 5, 6, si ha x(x − 1) = 2, 6, 12, 20, 30 rispettivamente. Se fb (x) = x2 − x + b = x(x − 1) + b è un polinomio di Eulero, allora per il punto i), b è un primo. Inoltre da quanto appena osservato e dalla definizione si ha che anche b + 2, b + 6, b + 12, b + 20 e b + 30 devono essere dei primi. Quindi in particolare b deve essere il più piccolo di una coppia di primi gemelli (due primi p e q si dicono primi gemelli se q − p = 2). Osserviamo che, poiché b è un primo, b ≡6 1 o 5. Ma se fosse b ≡6 1 , allora b + 2 ≡6 3 e quindi b + 2 sarebbe divisibile per 3 e non potrebbe essere un primo. Vediamo quale può essere l’ultima cifra di b. Se fosse b ≡10 5, b sarebbe divisibile per 5 e quindi non potrebbe essere un primo. Se fosse b ≡10 3, b + 2 sarebbe divisibile per 5 e infine b ≡10 9, b + 6 sarebbe divisibile per 5, in contraddizione con quanto richiesto. Concludendo abbiamo b ≡6 5 e b ≡10 1 oppure 7. Questo ci permette di concludere allora che b deve essere del tipo b = 11 + 30k oppure b = 17 + 30k. Gli unici possibili primi che dobbiamo indagare sono: b = 11, 17, 41, 47, 71, 77 se vogliamo fermarci a 100. Ma 77 non è un primo, e 47 non è un primo gemello (infatti 49 non è primo). Per quel che riguarda 71, osserviamo che 71+2= 73 è un primo, ma 71+6=77 non lo è già più. Se vogliamo continuare fino a 1000, è facile scrivere tutti i numeri del tipo descritto e poi basta avere sottomano una lista dei primi 74 minori di 1000 per controllare che gli unici primi della forma b = 11 + 30k oppure b = 17 + 30k con b + 2 primo sono b =101, 107, 137, 191, 197, 227, 281, 347, 431, 461, 491, 521, 617, 641, 821, 827, 857, 88 1. Per questi, un facile controllo mostra che almeno uno dei b + 6, b + 12, b + 20, b + 30, b + 42 o b + 72 non è un primo. Si può dimostrare che non esiste alcun polinomio f (x) con coefficienti interi, tale che tutti i valori f (x) per x ≥ x0 , intero, siano primi. Tuttavia esistono delle funzioni più complesse che danno come valori soli numeri primi (per esempio, è noto che esiste una costante positiva A tale x che per ogni numero naturale x il valore [A3 ] è un numero primo). È molto più facile trovare invece dei polinomi che danno come valori solamente numeri composti, come per esempio n4 + 4. Infatti, n4 + 4 è composto per ogni n ∈ Z essendo n4 + 4 = (n2 + 2n + 2)(n2 − 2n + 2) (il cosı̀ detto Teorema di Sophie Germain). Esercizio 8.9 Dimostrare che per ogni numero n ∈ N+ i numeri 22 sono composti. 10n+1 + 19 e 22 4n+1 +7 Esercizio 8.10 Dimostrare che ci sono infiniti numeri composti del tipo: (a) 10n + 3; (b) (22n + 1)2 + 2. Esercizio 8.11 Dimostrare che nessuna potenza 3k finisce con ...11. Esercizio 8.12 Dimostrare che 213 − 1 è un primo. Esercizio 8.13 Risolvere le equazioni congruenziali: a) 102x ≡21 14; b) 15x ≡87 122; c) 402x ≡57 45; d) 37x ≡16 14; e) 82x ≡13 174. Esercizio 8.14 Risolvere le seguenti equazioni congruenziali: a) 4x ≡17 −3; b) 29x + 3 ≡12 0; c) 3x − 8 ≡13 0; d) 7x ≡19 4; f )13x ≡153 178; g)18x ≡51 5 e) 37x ≡117 25; Esercizio 8.15 Trovare i numeri interi x che soddisfano le equazioni congruenziali: x ≡ 2(mod 3), x ≡ 1(mod 4) e x ≡ 3(mod 5). Esercizio 8.16 Dimostrare che : a) per k dispari 7 divide 13k+1 − 1; b) per k pari 5 non divide 3k+1 − 1; c) per k pari 5 non divide 3k+1 + 1; d) per k pari 5 non divide 13k+1 − 1; e) per k pari 5 non divide 13k+1 + 1; Esercizio 8.17 Trovare il massimo comun divisore d = (244 − 1, 226 − 1). Esercizio 8.18 Trovare il massimo comun divisore d = (252 − 1, 239 − 1). Esercizio 8.19 Trovare il massimo comun divisore d = (263 − 1, 236 − 1). 75 Esercizio 8.20 Siano x, n, m numeri naturali maggiori di 0. Dimostrare che: (xm − 1, xn − 1) = x(m,n) − 1. Svolgimento. Sia d = (xm − 1, xn − 1) e sia c = (m, n). Poiché c divide sia m che n, avremo che xc − 1 divide sia (xm − 1) che (xn − 1) per il punto ii) dell’Esercizio 7.6. Pertanto xc − 1 divide anche d. Poiché c = (m, n), esistono u, v ∈ N tali che c = mu − nv. Allora d divide xm − 1 e quindi per ii) divide anche xmu − 1 e analogamente d divide xnv − 1. Allora d divide anche la loro differenza, cioè d divide (xmu − 1) − (xnv − 1) = xmu − xnv = xnv (xmu−nv − 1). Poiché xm − 1 e x sono due numeri naturali coprimi, e d divide xm − 1, si avrà che d è coprimo con xnv e quindi divide (xmu−nv − 1) = xc − 1. Esercizio 8.21 Dimostrare che 59 divide 229 + 1. Esercizio 8.22 Dimostrare che: (a) 13 divide 270 + 370 ; (b) 11 · 31 · 61 divide 2015 − 1. Esercizio 8.23 Sia a > 1 un numero naturale. Trovare il resto di a100 modulo 125. Esercizio 8.24 Sia a > 1 un numero naturale. Dimostrare che il numero è mai intero. 1 2 + 31 + . . .+ n1 non Esercizio 8.25 Sia n un numero naturale dispari. Dimostrare che n divide an! − 1 se a è coprimo con n. Esercizio 8.26 Sia n > 0 un numero naturale. Dimostrare che il numero non è mai intero. 1 3 + 1 5 +...+ Esercizio 8.27 Sia n un numero naturale dispari. Dimostrare che n divide 2n! − 1. Suggerimenti. Notare che ϕ(n) divide n!. Esercizio 8.28 Trovare le ultime due cifre di (a) 2999 ; (b) a2 , dove a è un numero pari; (c) (. . . (((77)7 )7 )7 . . .)7 (7 compare n volte). (d) 7 .. . 77 (7 compare n volte). Esercizio 8.29 Sia p un numero primo. Dimostrare che p (a) p divide il coefficiente binomiale Ck per ogni 0 < k < p. s s s (b) (x + y)p ≡p xp + y p per ogni x, y ∈ Z e s ∈ N. 76 1 2n+1 (c) la massima potenza pm con la quale p divide n! è data da n n n + 2 + . . . + k + . . .. m= p p p (∗) p! e il fatto che p divide il nominatore ed Suggerimenti. (a) Sfruttare la formula Ckp = k!(p−k)! è coprimo con il numeratore. (b) hSegue i da (a) per induzione su s. h i n (c) p coincide con il numero dei multipli di p nel prodotto che definisce n!. Di questi pn2 h i sono multipli di p2 (e contribuiscono ciascuno con un altro fattore p), pn3 ecc. Esercizio 8.30 Trovare con quanti zeri termina 2000!. Esercizio 8.31 Dimostrare che il numero ((3!)!)! ha più di mille cifre decimali e trovare con quanti zeri termina questo numero. Esercizio 8.32 Se n ∈ N+ , allora (n!)(n−1)! divide (n!)!. Esercizio 8.33 Se n ∈ N è maggiore di 2, allora 2n non divide n!. Esercizio 8.34 Determinare i numeri n ∈ N+ tali che n non divide (n − 1)!. Esercizio 8.35 Sia p > 2 un numero primo. Dimostrare che: (a) se x ≡p y per x, y ∈ Z, allora xp ≡p2 y p . (b) se xp + y p ≡p 0 per x, y ∈ Z, allora xp + y p ≡p2 0. Adesso vediamo che una ”piccola” modifica nel piccolo teorema di Fermat cambia completamente la situazione. Esercizio 8.36 Sia p un numero primo e sia a ∈ Z. Se ap ≡p 1, allora ap ≡p2 1. Esercizio 8.37 Sia p un numero primo. Dimostrare che Ckp−1 ≡p (−1)k per ogni 0 < k < p. 77

Log In

Dispense di Aritmetica

Free related PDFsRelated papers

Free related PDFsRelated papers