Indicheremo abitualmente gli insiemi con lettere maiuscole e gli elementi di un insieme con lettere minuscole. NOTA BENE: NON diamo una definizione formale di insieme. “ è un elemento dell’insieme ” si scrive in simboli “” e si legge “ appartiene ad ”.
Idea intuitiva: un insieme è costituito e caratterizzato esclusivamente dai suoi elementi, ossia: due insiemi sono uguali se e solo se contengono gli stessi elementi.
Useremo spesso gli insiemi numerici (numeri naturali), (numeri interi relativi), (numeri razionali) ed (numeri reali), soprattutto per poter costruire qualche esempio significativo.
Un insieme può essere assegnato elencando i suoi elementi. Gli elementi dell’insieme sono quelli presenti nell’elenco, non ha importanza se sono elencati più volte o in quale ordine.
Esempio 1.1. è l’insieme costituito dai due numeri e . Anche e sono l’insieme , perchè l’ordine e le ripetizioni sono irrilevanti.
Un altro modo per assegnare un insieme è quello di indicare una sua proprietà caratteristica ossia una proprietà soddisfatta da tutti gli elementi dell’insieme e solo da essi:
Se si usa la proprietà caratteristica:
Esempio 1.2. Non hanno alcun senso espressioni quali: multipli di , numeri naturali grandi , soluzioni dell’equazione .
L’insieme è invece perfettamente definito. Poichè nessun numero reale ha quadrato negativo, l’insieme ora considerato è privo di elementi: si chiama insieme vuoto e si denota . L’insieme vuoto è unico: .
Nei paragrafi successivi vedremo come a partire da insiemi noti se ne possano costruire altri mediante alcune costruzioni standard (unione, intersezione, complementare, insieme delle parti, prodotto cartesiano, quoziente).
Per indicare che un elemento
non appartiene ad un insieme
scriviamo
. Preso un
qualsiasi elemento
,
l’affermazione che
non appartiene all’insieme vuoto si scrive in simboli:
:
.
significa “per ogni”,
“ogni”, “per tutti”
Ad eccezione dell’insieme vuoto, tutti gli altri insiemi contengono qualche
elemento. In
simboli:
tale
che
. Il
simbolo
significa “esiste”, “c’è almeno un/o/a...”; a volte si usa anche il simbolo
col significato di “esiste uno ed un solo” o “esiste un unico”.
si legge “se
e soltanto se” oppure “se e solo se” e significa che l’affermazione che lo
precede e l’affermazione
che lo segue sono equivalenti ossia che sono entrambe vere oppure entrambe false. Per ogni
insieme
,
scriveremo
oppure
se
ha un numero
finito
di
elementi oppure
se ne ha infiniti.
si ha ed anche .
Si dice che l’insieme è un sottoinsieme dell’insieme , oppure che è contenuto in , se e solo se ogni elemento di è anche elemento di . In simboli: . Il simbolo si legge “implica”. Se e sono due affermazioni, l’implicazione significa che se (oppure ogni volta che) l’affermazione è vera, allora è vera anche . Quindi l’implicazione è corretta quando e sono entrambe vere ed anche quando è falsa (indipendentemente dal fatto che sia vera o falsa).
Esempio 1.4. L’implicazione è pari è corretta. Invece è falsa perchè esiste almeno un caso in cui la prima affermazione è vera e la seconda no: , ma . Sono vere anche affermazioni piuttosto strane per il senso comune come: è pari
è dispari
NOTA BENE: Una affermazione è vera se e soltanto se è vera in tutti i casi; la dimostrazione deve comprendere tutti i casi possibili e non soltanto alcuni casi particolari. Una affermazione è falsa se e solo se è falsa in almeno un caso; per provarlo è sufficiente esibire esplicitamente un controesempio. Le strane affermazioni dell’esempio precedente sono considerate corrette poichè non ammettono controesempi: non vi sono infatti numeri naturali minori di da poter usare come controesempi. Se è un sottoinsieme proprio di , ossia se è un sottoinsieme di diverso da stesso, si può anche scrivere , oppure ancor più chiaramente , invece di . Quindi: se ogni elemento di è anche elemento di , ma vi è almeno un elemento di che non è elemento di . Anche in questo caso una sbarra sul simbolo indica la sua negazione: significa che l’insieme non è un sottoinsieme dell’insieme , ossia che esiste almeno un elemento di che non è elemento di . In simboli:
La seguente proprietà viene usata molto spesso per provare l’uguaglianza tra due insiemi. Doppia inclusione
Il simbolo abbrevia la congiunzione “e”. Dunque, due insiemi sono diversi se differiscono almeno per un elemento, ossia se vi è almeno un elemento nel primo che non appartiene al secondo oppure vi è almeno un elemento nel secondo che non appartiene al primo:
Il simbolo abbrevia la congiunzione “o”, “oppure”. Se è un sottoinsieme proprio di e ha un numero finito di elementi, ossia , allora anche ha un numero finito di elementi, strettamente minore di , ossia:
Invece se , può avere un numero finito di elementi o anche infiniti elementi come . Ad esempio , ma .
Definizione 1.6. Siano , insiemi. Si dice intersezione di e e si denota l’insieme i cui elementi sono tutti gli elementi che stanno contemporaneamente in e in :
Due insiemi e si dicono disgiunti se . Si dice unione di e e si denota l’insieme i cui elementi sono tutti gli elementi che stanno in almeno uno tra e :
NOTA BENE: L’espressione oppure comprende anche il caso degli eventuali elementi che appartengono ad entrambi gli insiemi. Quindi:
Talvolta useremo l’espressione “l’unione disgiunta di e ” per indicare semplicemente l’unione , ma sottolineando che i due insiemi e considerati sono disgiunti. Non è dunque un diverso tipo di unione, ma è solo un modo abbreviato per “l’unione dei due insiemi e (che sono insiemi disgiunti)”. L’unione e l’intersezione di insiemi non dipendono dall’ordine in cui gli insiemi vengono considerati e soddisfano le seguenti proprietà distributive:
Unione, intersezione e relative proprietà possono essere generalizzati a famiglie qualsiasi di insiemi.
Esempio 1.9. Per ogni indichiamo con l’insieme dei numeri interi relativi che sono multipli di . Allora e . Dimostriamo l’ugualianza utilizzando il metodo della doppia inclusione. L’inclusione “” è ovvia perchè tutti gli insiemi sono contenuti in e quindi anche la loro unione lo è. Per dimostrare l’inclusione opposta “” proviamo che ogni numero intero è contenuto in almeno uno degli insiemi . Possiamo ad esempio scegliere ed osservare che ogni numero intero è multiplo di 1. Oppure possiamo scegliere (dove è il valore assoluto di ). Allora se e se : in entrambi i casi è un multiplo di e quindi .
Esempio 1.10. Il dominio della funzione reale di variabile reale è :
Un modo alternativo di scrivere il dominio della funzione tangente è quello di dire che è costituito da tutti i numeri reali tranne i multipli interi di .
Definizione 1.11. Siano un insieme e un suo sottoinsieme. Si dice complementare di in e si indica con l’insieme di tutti gli elementi di che non appartengono ad :
Quindi il dominio della funzione tangente è .
L’insieme complementare è l’unico insieme che verifica le due condizioni
Valgono inoltre le Leggi di De Morgan: se e sono sottoinsiemi di , allora:
Proprietà analoghe valgono relativamente ad unioni ed intersezioni di famiglie di insiemi. Data una famiglia , di sottoinsiemi di un insieme si ha:
Definizione 1.12. Dati gli insiemi e , si dice insieme differenza di ed , e si denota , oppure , l’insieme formato da tutti gli elementi di che non appartengono ad , ossia:
Talvolta si considera anche l’insieme costituito dagli elementi di due insiemi che non siano elementi comuni.
Definizione 1.13. Dati gli insiemi e , si dice differenza simmetrica di e , e si denota , l’insieme formato da tutti gli elementi che appartengono ad uno solo tra e , ossia:
ovvero
Gli insiemi possono a loro volta essere considerati come elementi di altri insiemi.
Esempio 1.14. L’insieme ha due elementi: il numero e l’insieme formato dai numeri e . L’insieme ha due elementi: il numero e l’insieme che ha come unico elemento (un insieme come che ha un solo elemento si dice anche singleton).
Definizione 1.15. Si dice insieme delle parti di un insieme , l’insieme i cui elementi sono i sottoinsiemi di :
Attenzione alle notazioni:
L’insieme delle parti di un insieme non è mai l’insieme vuoto poichè in ogni caso contiene almeno l’elemento . In particolare ha elemento. Se è un insieme con elementi, l’insieme delle parti ha elementi. Dimostreremo in seguito questa affermazione.
Vogliamo ora suddividere un insieme in parti, ciascuna costituita da un suo sottoinsieme, in modo che riunendole tutte riotteniamo l’insieme di partenza. Se non poniamo altre condizioni che questa, otteniamo un ricoprimento di . Ponendo alcune condizioni ulteriori otteniamo ricoprimenti speciali, che vengono utilizzati in numerose costruzioni matematiche.
Definizione 1.17. Si dice partizione di una famiglia di suoi sottoinsiemi tali che:
In modo piu formale possiamo dire che una partizione di è un sottoinsieme di tale che:
Un insieme siffatto si dice anche quoziente di .
I sottoinsiemi formano una partizione di . Il quoziente ha infiniti elementi.
Solo per curiosità : il Paradosso di Russell. Secondo la “definizione informale-intuitiva” per cui un insieme è dato semplicemente dai suoi elementi, risulta essere un insieme anche quello i cui elementi sono tutti i possibili insiemi: indichiamo un tale “insieme” con . Per vale la strana proprietà : .
Potremmo allora classificare tutti gli “insiemi” secondo i due tipi:
Gli insiemi del primo tipo formano un “sottoinsieme” di . A quale dei due tipi apparterrà ?
Da questa contraddizione non c’è via d’uscita, se non quella di definire con grande attenzione il concetto di insieme, in modo da evitare che ”cose“ come e siano degli insiemi.
Definizione 1.19. Siano , insiemi. Si dice prodotto cartesiano di e e si denota l’insieme i cui elementi sono le coppie ordinate dove varia tra tutti gli elementi di e tra quelli di :
Analogamente il prodotto cartesiano di è l’insieme delle uple di elementi presi ordinatamente uno in ciascun insieme:
Se e , allora anche . Infatti esiste almeno un elemento e almeno un elemento e quindi il prodotto cartesiano contiene almeno l’elemento . Lo stesso vale per il prodotto cartesiano di insiemi non vuoti.
Definizione 1.20. Ogni sottoinsieme del prodotto cartesiano si dice anche corrispondenza tra e . Se e , diremo anche che gli elementi e sono in corrispondenza. Spesso le corrispondenze, come i sottoinsiemi in genere, vengono definite mediante una proprietà caratteristica. Se le corrispondenze in si chiamano relazioni in .
Nei seguenti problemi , , , …denotano sottoinsiemi arbitrari di un insieme fissato.
1.1 Determinare nei seguenti casi:
.
1.2 Sia un insieme con 3 elementi e un insieme con 2 elementi. Quanti elementi ha ? Quanti elementi ha ? Per ogni caso possibile scrivere un esempio esplicito. 1.3 Sia l’insieme dei numeri naturali dispari, l’insieme dei numeri naturali multipli di 3 ed l’insieme dei numeri naturali maggiori di 0. Scrivere in simboli i tre insiemi e stabilire se le seguenti affermazioni sono giuste o sbagliate (nel secondo caso esibire un controesempio):
.
.
.
1.4 Siano , , e .
Determinare l’insieme delle parti di e l’insieme delle parti di .
Dire quali delle seguenti affermazioni sono vere e quali false:
1.5 Siano , e .
Volendo calcolare possiamo scegliere tra le due definizioni equivalenti:
Quale delle due è più semplice? Dare una motivazione e quindi calcolare .
Determinare la lista degli elementi di .
Scrivere come unione di due insiemi disgiunti.
1.6 Indichiamo con e con gli insiemi delle soluzioni reali delle equazioni e .
Determinare esplicitamente gli elementi dei due insiemi.
Esprimere mediante e ed elencare esplicitamente gli elementi dell’insieme delle soluzioni reali dell’equazione .
Esprimere mediante e ed elencare esplicitamente gli elementi dell’insieme delle soluzioni reali del sistema di equazioni .
1.7 Indichiamo con l’insieme delle soluzioni dell’equazione . Quale è l’insieme delle soluzioni dell’equazione ?
1.8 Siano , e . Calcolare:
1.9 Sia . Verificare che gli insiemi , e costituiscono una partizione di .
1.10 Siano , e . Determinare , , e verificare che .
1.11 Dimostrare le uguaglianze e
1.12 Provare che le seguenti affermazioni sono false esibendo dei controesempi espliciti:
;
;
.
1.13 Siano e . Determinare , , , . Quali sono i sottoinsiemi di che sono anche sottoinsiemi di ?
1.14 Per ogni , sia . Calcolare e .
1.15 Siano , , e . Determinare
.
1.16 Per ogni poniamo . Calcolare e .
1.17 Dimostrare la seguente affermazione: se e solo se .
1.18 Trovare esplicitamente dei sottoinsiemi , , di tali che , , , e .
1.19 Siano e i sottoinsiemi di conteneti rispettivamente i numeri dispari e i numeri pari. Dimostrare che è una partizione di .
1.20 Per ogni si definisca come il sottoinsieme dei numeri naturali la cui divisione per dà resto . Dimostrare che la famiglia è una partizione di .
1.21 Sia l’insieme di tutti i numeri naturali multipli di 3. Scrivere una partizione di costituita da 2 sottoinsiemi. Scrivere una partizione di costituita da infiniti sottoinsiemi.
1.22 Siano e . Scrivere esplicitamente , , , , , , e .
Definizione 2.1. Una applicazione o funzione è una terna , dove e sono insiemi non vuoti e è una corrispondenza da a (cioè un sottoinsieme del prodotto cartesiano ) che è ovunque definita e funzionale ossia che gode della seguente proprietà :
Notazioni e terminologia: si dice dominio di , si dice codominio di e si dice grafico di . Per indicare che è una funzione da in invece che abitualmente si usa la notazione . Fissato un elemento , per indicare che è l’unico elemento di tale che si scrive e si dice che è l’immagine di .
Definizione 2.2. Si dice immagine di una funzione e si denota oppure il sottoinsieme di degli elementi che sono immagine di qualche elemento di ossia:
Più generalmente, dato un sottoinsieme di , si dice immagine di il sottoinsieme di :
NOTA BENE Spesso per assegnare una funzione si fornisce una “legge” ossia una qualche formula che permette di associare a ciascun elemento del dominio la sua immagine. Si faccia però attenzione al fatto che la funzione è caratterizzata soltanto dal dominio , dal codominio e dal grafico e non dalla eventuale “formulazione della legge”. I due esempi seguenti mostrano come una stessa “legge” può definire funzioni diverse e come, d’altra parte, “leggi” diverse possono definire una stessa funzione.
Esempio 2.3. La funzione data da e la funzione data da sono diverse, perchè non hanno lo stesso dominio e lo stesso codominio, ma, oltre a questo, hanno anche proprietà molto diverse. Usando la terminologia che definiremo in seguito, non è iniettiva, mentre lo è.
Esempio 2.4. Siano ed le funzioni definite rispettivamente da e . Queste funzioni, per quanto espresse mediante “leggi” diverse, sono la stessa funzione, ossia , poichè hanno lo stesso dominio , lo stesso codominio e lo stesso grafico:
Esempio 2.5. Elenchiamo ora alcune funzioni particolarmente importanti e che capiterà spesso di usare.
Definizione 2.6. Una funzione si dice:
iniettiva se : ;
suriettiva se ossia se tale che ;
biunivoca o biiettiva se è sia iniettiva sia suriettiva.
Una funzione biunivoca si dice anche biiezione oppure corrispondenza biunivoca oppure corrispondenza 1–1. Possiamo riformulare le precedenti definizioni usando il concetto di controimmagine.
Definizione 2.7. Siano una funzione, un elemento di e un sottoinsieme di . Si dice controimmagine di il sottoinsieme di cosè definito:
Analogamente si dice controimmagine di il sottoinsieme di :
La controimmagine di un elemento del codominio non è altro che la controimmagine del sottoinsieme singleton , ossia . La controimmagine di un elemento è quindi sempre definita (ossia esiste sempre ) ed è un sottoinsieme del dominio che, a seconda dei casi, può essere l’insieme vuoto , oppure un singleton (ossia un sottoinsieme con un solo elemento), oppure un sottoinsieme con più elementi.
Esempio 2.8. Siano , e l’applicazione definita da: , , , . Avremo allora . Consideriamo poi i seguenti sottoinsiemi di : , , . Allora: , , .
Proposizione 2.9. Sia una funzione. Allora:
Proof. 1) Supponiamo iniettiva e sia un elemento qualsiasi di . Se allora ; se invece ossia se per un qualche , allora per ogni si ha e quindi contiene un solo elemento. Supponiamo ora che la controimmagine di ciascun elemento del codominio contenga al massimo un elemento; se sono elementi distinti di , allora le loro immagini e sono distinte perchè in caso contrario conterrebbe più di un elemento. 2) L’equivalenza segue subito dall’osservazione che se e solo se . Infine 3) si ottiene immediatamente dalle precedenti. □
Le funzioni costanti da in non sono mai nè iniettive (tranne nel caso molto particolare in cui abbia un solo elemento) nè suriettive (tranne nel caso molto particolare in cui abbia un solo elemento).
Le funzioni identità sono sempre biunivoche.
Le funzioni proiezione su un fattore e dal prodotto cartesiano su e su rispettivamente, sono sempre suriettive. Inoltre (risp. ) è anche iniettiva soltanto in caso (risp. ) abbia un solo elemento.
La funzione proiezione sul quoziente è sempre suriettiva, poichè (per definizione) le classi di equivalenza non sono mai vuote. L’unico caso in cui risulta anche iniettiva è quello che riguarda la relazione “identità “: se e solo se .
La lettura corretta di è “ composto ” in quanto è la prima funzione che agisce e la seconda; per evitare una (per noi) poco naturale lettura da destra verso sinistra e, nello stesso tempo, rispettare il significato matematico del simbolo, evitando confusione ed errori, si può leggere anche come “ dopo ”. Si noti che la composizione di due funzioni è definita solo nel caso in cui il codominio della prima coincide col dominio della seconda.
Proof. Per la verifica è sufficiente osservare che le due funzioni hanno lo stesso dominio , lo stesso codominio e assegnano a ciascun elemento di la stessa immagine . □
Grazie alla proprietà associativa, potremo scrivere senza ambiguità la composizione di più funzioni come , senza l’uso di parentesi. Non valgono invece per la composizione di funzioni la proprietà commutativa e la proprietà di cancellazione, come mostrano gli esempi che seguono.
Esempio 2.13. Siano , e insiemi due a due distinti e siano , e funzioni. La composizione è definita, mentre non lo è la composizione poichè il codominio di e il dominio di non coincidono. Le composizioni e sono entrambe definite, ma sono funzioni diverse, perchè la prima ha dominio e la seconda ha dominio .
Esempio 2.14. Siano le funzioni date da e . Le funzioni composte e sono entrambe definite, sono entrambe funzioni da in , ma sono funzioni diverse poichè ad esempio , mentre .
I due esempi seguenti mostrano il comportamento di due funzioni importanti rispetto alla composizione.
Esempio 2.16. Siano insiemi, e le rispettive funzioni identità e sia infine una funzione qualsiasi. Allora si ha ed anche .
Esempio 2.17. Siano un insieme, un suo elemento fissato e la corrispondente funzione costante. Se è una funzione qualsiasi, allora e .
I risultati seguenti mostrano il comportamento di due funzioni importanti rispetto alla composizione.
Proof. i) Proviamo che se non è iniettiva, neppure può esserlo. Supponiamo che siano elementi distinti di tali che ; allora si ha:
e quindi non è iniettiva. ii) Supponiamo suriettiva; vogliamo provare che , ossia che si ha . Per ipotesi esiste tale che . In tal caso, posto , si ha , come volevasi. □
Dall’iniettività della funzione composta, invece, nulla segue riguardo all’iniettività della seconda funzione e, allo stesso modo, dalla suriettività della funzione composta nulla segue riguardo alla suriettività della prima funzione.
Definizione 2.19. Si dice funzione inversa di una funzione una funzione tale che valgano le due condizioni e .
Non tutte le funzione hanno una funzione inversa. Infatti:
Proof. “” segue dalla Proposizione 2.18, ricordando che le funzioni identità sono iniettive e suriettive. “” Supponiamo biunivoca e costruiamo esplicitamente la funzione inversa come corrispondenza inversa. Dunque poniamo dove è l’unico elemento di tale che . Per costruizone, le due composizioni di e coincidono con l’identitàdi e di rispettivamente. □
Notiamo che è sempre possibile costruire la corrispondenza inversa di una funzione , ma essa non è in generale una funzione a meno che, come prima dimostrato, sia biunivoca. Se infatti non è suriettiva, la corrispondenza inversa non risulta ovunque definita e se non è iniettiva, la corrispondenza inversa non risulta funzionale. Proviamo ora che la funzione inversa, se esiste, è unica.
Proof. Intanto e hanno lo stesso dominio e codominio. Ci basterebbe allora provare che hanno lo stesso grafo. Scegliamo invece un ragionamento di tipo più formale: calcoliamo la composizione “a tre” nei due modi diversi permessi dalla proprietà associativa:
□
Dunque non possono esistere due diverse funzioni inverse di una stessa funzione . Di solito l’unica funzione inversa di (naturalmente se esiste) viene denotata col simbolo . ATTENZIONE: le notazioni di funzione inversa e di controimmagine possono essere confuse una con l’altra.
Come applicazione delle cose viste riguardo alle funzioni vogliamo ora definire in modo rigoroso il “numero di elementi” di un insieme, anche nel caso in cui l’insieme sia “infinito”. Prima di poter fare ciò, è necessario precisare cosa intendiamo dicendo che un insieme è finito oppure che è infinito.
Definizione 2.22. Si dice che due insiemi e sono equipollenti oppure hanno la stessa cardinalità se esiste una funzione biunivoca .
Intuitivamente possiamo dire che se ha tanti elementi quanti . Vogliamo ora mettere a confronto tra loro le cardinalità, per poter dire anche se un insieme ha più elementi (oppure ha meno elementi) di un altro.
Definizione 2.23. Dati due insiemi e , diciamo che ha cardinalità minore o uguale di se esiste una applicazione iniettiva oppure (equivalentemente) se esiste una applicazione suriettiva . In tal caso scriveremo .
Definizione 2.25. Un insieme è infinito se è equipollente ad un suo sottoinsieme proprio ossia se ossia se esiste una funzione iniettiva ma non suriettiva, oppure suriettiva ma non iniettiva. Un insieme è finito se questo non capita.
Esempio 2.26. L’insieme dei numeri naturali è un insieme infinito poichè la funzione “successore” , è iniettiva ma non suriettiva (Assiomi di Peano). Possiamo anche vedere che la funzione “doppio” ( numeri naturali pari ) data da , è biunivoca e quindi , anche se è un sottoinsieme proprio di .
Dalla definizione di insieme finito segue la seguente proprietà ,
Nel seguito del capitolo indicheremo con l’insieme dei numeri naturali . Diremo inoltre che l’insieme vuoto ha cardinalità 0.
La cardinalità dell’insieme infinito è detta cardinalitè numerabile e viene indicata con ( è la lettera ebraica alef). Un insieme equipollente a si dice insieme numerabile.
Esempio 2.29. . Una applicazione biunivoca è data da se , se . Anche ha cardinalità numerabile, ma non è semplice costruire esplicitamente una funzione biunivoca
Solo per curiosità: la cardinalità dei numeri reali. , detta anche cardinalità del continuo, è strettamente maggiore di . L’applicazione mostra che . Proviamo che non vale l’uguaglianza mostrando che nessuna funzione può essere suriettiva. Identifichiamo ogni numero reale con la sua scrittura posizionale in base e indichiamo con la esima cifra decimale del numero . Costruiamo un numero reale che non appartiene a . Sia il numero reale con parte intera tale che se e se . Tale numero differisce da ciascun numero reale appartenente a in almeno una cifra decimale e quindi . Vi sono tuttavia insiemi che hanno cardinalità più grande di quella del di , ad esempio , l’insieme delle parti di . Possiamo provare infatti, più in generale, che per ogni insieme , finito o infinito, si ha . La funzione iniettiva prova che . Proviamo che non vale l’uguaglianza. Supponiamo per assurdo che esista una funzione biunivoca e indichiamo con il sottoinsieme di degli elementi tali che . Essendo suriettiva, esiste un elemento tale che . Si perviene allora alla contraddizione:
Dalla definizione di insieme finito e dalle proprietà che abbiamo enunciato nella sezione precedente segue la proprietà conosciuta come principio dei cassetti o principio della piccionaia. Se è un insieme finito con elementi e è un suo sottoinsieme con elementi, allora e inoltre è strettamente più piccolo di se e solo se . Questa proprietà appare meno evidente quando i numeri coinvolti sono grandi.
Esempio 2.30. In una grande città, come Milano Roma, vi sono sicuramente due persone con lo stesso numero di capelli in testa. Sappiamo infatti che il numero di capelli che un individuo può possedere non supera i . Se tutti gli abitanti di Roma (o di Milano) avesso un diverso numero di capelli, l’insieme costituito dai numeri di capelli di ciascun individuo avrebbe tanti elementi quanti sono gli abitanti (e quindi più di un milione di elementi), pur essendo un sottoinsieme dell’insieme dei numeri interi da a che ha solo elementi.
Possiamo enunciare il Prinipio dei cassetti anche coinvolgendo le nozioni di iniettività e suriettività delle funzioni: sia una funzione tra gli insiemi di cardinalità e di cardinalità .
Si faccia attenzione al fatto che queste proprietà contengono delle implicazioni, non delle bi-implicazioni.
Esempio 2.31. Consideriamo una funzione da un insieme con elementi ad un insieme con elementi. Possiamo affermare con totale sicurezza che non è suriettiva in quanto . Possiamo inoltre affermare che potrebbe essere iniettiva, ma senza ulteriori informazioni non possiamo sapere se lo è oppure no.
2.1 Sia data da . Determinare , , . Si tratta di una applicazione iniettiva? Si tratta di una applicazione suriettiva?
2.2 Sia data da . Determinare , , . Si tratta di una applicazione suriettiva? Si tratta di una applicazione iniettiva?
2.3 Sia la funzione data da .
Determinare l’immagine dei sottoinsiemi e .
Determinare gli insiemi controimmagine per e poi per un generico.
Dire se è iniettiva, suriettiva, biunivoca.
2.4 Sia la funzione data da .
Determinare e l’immagine dei sottoinsiemi e .
Determinare gli insiemi controimmagine e , dove è l’insieme dei numeri interi strettamente negativi.
Dire se è iniettiva, suriettiva, biunivoca.
2.5 Sia l’applicazione data da: se è dispari e se è pari.
Dire se è iniettiva, suriettiva, biunivoca.
Determinare , , , , .
Determinare e , dove è l’insieme dei numeri interi pari.
2.6 Determinare tutte le applicazioni dove e . Quante sono quelle suriettive? Quante sono quelle iniettive?
2.7 Esiste una applicazione tale che ? Esiste una applicazione tale che ? (motivare le risposte; in caso affermativo esibire un esempio.)
2.8 Determinare l’immagine della funzione data da . Vi sono elementi del codominio la cui controimmagine è un singleton? Trovare tutti gli elementi di , per ogni numero primo .
2.9 Siano un insieme, un suo sottoinsieme, e l’applicazione data da . Dire se è iniettiva, suriettiva, biunivoca e determinare . Rispondere alle stesse domande relativamente a data da .
2.10 Sia l’applicazione definita da . Provare che non esiste una applicazione tale che .
2.11 Sia l’applicazione definita da se e se . Provare che non esiste una applicazione tale che . Costruire due diverse applicazioni tali che .
2.12 Sia l’applicazione data da se è pari e se è dispari. Dire se si tratta di una applicazione iniettiva, suriettiva, biunivoca. Determinare esplicitamente gli insiemi controimmagine di , , .
2.13 Siano e due funzioni biunivoche. Verificare che anche la funzione inversa e la funzione composta sono funzioni biunivoche.
2.14 La successione di Fibonacci è la funzione data da , e per ogni . Determinare le immagini dei primi numeri naturali. Si tratta di una funzione suriettiva? iniettiva?
2.15 In un teatro vi sono persone. Provare che ce ne sono almeno che festeggiano il compleanno lo stesso giorno. Quante persone bisogna riunire per essere sicuri che almeno tre tra esse festeggino il compleanno lo stesso giorno?
2.16 Provare che in Italia esistono sicuramente due persone che festeggiano il compleanno nello stesso giorno, hanno lo stesso numero di scarpe ed anche la stessa altezza espressa in centimetri. E a Torino?
Vogliamo contare il numero di elementi dell’unione di due o più insiemi finiti. In questo capitolo per indicare il numero di elementi di un insieme scriveremo invece : si tratta di un altro modo di indicare la cardinalità che spesso si incontra sui libri. Iniziamo cl caso di 2 insiemi. Siano e due insiemi finiti di cardinalità finita ed rispettivamente, che siano disgiunti ossia privi di elementi comuni. Allora:
La formula si generalizza al caso di insiemi finiti , , con , disgiunti due a due:
Se invece e hanno elementi in comune (ossia ), allora la formula diventa:
Il termine correttivo si inserisce poichè i elementi comuni ad e compaiono tra gli del primo insieme e gli del secondo e sarebbero pertanto contati due volte in . Questa formula più generale è nota come principio di inclusione-esclusione. Tralasciamo la sua generalizzazione al caso di insiemi poichè decisamente più complicata. La riportiamo solo per il caso , con un esempio di applicazione:
Esempio 3.1. Su 25 studenti, 15 hanno superato l’esame di
Matematica, 12 quello
di Chimica e 5 hanno superato entrambi gli esami. Quanti studenti hanno superato
almeno un esame? Quanti studenti hanno fallito entrambi gli esami? Sia
l’insieme degli studenti che hanno superato l’esame di Matematica:
Sia
l’insieme degli studenti che hanno superato l’esame di Chimica,
è l’insieme degli studenti che hanno superato entrambi gli esami:
La risposta alla prima domanda è l’ordine dell’insieme
,
dato da
.
Non hanno superato nessuno dei due esami
studenti.
Esempio 3.2. Sia
.
Quanti sono i numeri di
divisibili per
o per
?
Sia
l’insieme dei numeri pari di
:
l’ordine di
è 10.
Sia
l’insieme dei multipli di 3 in
:
ha ordine 6.
è l’insieme dei multipli di 6 minori di 20:
ha ordine 3.
I numeri di
divisibili per 2 o per 3 sono
.
Esempio 3.3. In un gruppo di amici tutti hanno visto almeno uno dei film : 8 hanno visto il film , 12 il film e 9 il film . Inoltre 6 hanno visto e , 4 hanno visto e , 7 hanno visto e e soltanto uno di essi ha assistito alle tre proiezioni. Da quante persone è formato il gruppo? Con ovvio significato delle notazioni si ha: , , , , , , . Quindi :
Consideriamo come primo caso quello del prodotto cartesiano.
Proof. Se , consideriamo gli sottoinsiemi di a due a due disgiunti formati ognuno dalle coppie aventi come prima componente. Per la formula della cardinalità dell’unione di insiemi disgiunti abbiamo
□
Osserviamo che disponendo in colonna e in riga gli elementi di e gli elementi di , il prodotto cartesiano può essere visualizzato come una tabella di quadretti. Possiamo utilizzare il ragionamento precedente anche in situazioni più generali. Se una scelta può essere compiuta in modi diversi e, per ciascuno di essi, una seconda scelta può essere compiuta in modi diversi, allora la successione delle due scelte può essere effettuata in modi distinti. Nel caso del prodotto cartesiano la scelta del secondo elemento avviene sempre tra quelli di uno stesso insieme. Come vedremo, in situazioni più generali si costruiscono coppie scegliendo il primo elemento in un insieme fisso con elementi e il secondo elemento in un insieme di cardinalità che però può dipendere dal primo elemento scelto. Mediante l’induzione quanto visto relativamente a due scelte si estende al caso di un numero finito di scelte consecutive.
Proposizione 3.5. Supponiamo di dover eseguire scelte consecutive e che la scelta -esima possa avvenire in modi diversi. Allora le sequenze di scelte possibili sono
Proof. Procediamo per induzione su . Per la dimostrazione è quella presentata precedentemente. Supponiamo che l’asserto sia vero per un certo numero di scelte e proviamo che allora è vera per scelte. Per l’ipotesi induttiva possiamo eseguire le prime scelte in modi. Possiamo pensare la nostra procedura di scelte come costituita da due momenti: in un primo momento eseguiamo le prime scelte in modi e nel secondo momento eseguiamo l’ultima scelta in modi possibili. Applicando il caso in tutto avremo modi. Possiamo quindi concludere che la formula vale anche nel caso scelte poichè
□
Il principio di moltiplicazione delle scelte (anche nella sua forma estesa a più di due scelte) ci permette di risolvere molti problemi combinatorici.
Esempio 3.6. Quante etichette si possono formare con un numero di due cifre (da 00 a 99) e una lettera (dell’alfabeto di 26 lettere)? Le etichette sono tanti gli elementi del prodotto cartesiano dove è l’insieme dei numeri da 0 a 99 (che ha 100 elementi) e è l’insieme delle lettere dell’alfabeto, che ha quindi elementi. Allora le etichette possibili sono .
Esempio 3.7. Quanti oggetti possiamo differenziare con delle targhe costituite da 3 simboli di cui il primo è una lettera scelta tra , il secondo è una cifra da 1 a 5 e il terzo è una lettera dell’alfabeto? Le lettere greche possono essere scelte in 4 modi, le cifre in 5 modi, la lettera finale in 26 modi: in tutto possiamo costruire targhe diverse.
Esempio 3.8. Supponiamo che il menù di un ristorante consista di 5 antipasti, 6 primi, 6 secondi e 4 dolci: quanti pasti completi (di quattro portate) possiamo ordinare? Le quaterne ordinate (e quindi le scelte possibili) sono .
Esempio 3.9. Scegliamo due persone in un gruppo di 7 come responsabile della cassa comune e addetto alle comunicazioni. In quanti modi può essere effettuata la scelta? La scelta di responsabile della cassa può essere effettuata in 7 modi diverse: scegliamo un elemento qualsiasi nell’insieme costituito dalle 7 persone. La scelta dell’addetto alle comunicazioni può essere effettuata in 6 modi diversi: scegliamo un elemento qualsiasi nell’insieme , dove è la persona a cui è stata affidata la prima mansione; come si vede il secondo insieme, pur avendo in tutti i casi 6 elementi, cambia a seconda della prima scelta effettuata.
Il principio delle scelte successive può essere utilizzato per determinare alcune formule di calcolo combinatorico. Vediamone alcune.
Diciamo disposizioni con ripetizione di elementi scelti in un insieme di ordine ogni ordinamento o disposizione di elemnti scelti in con la possibilità di usare più volte uno stesso elemento. In modo più formale:
Definizione 3.10. Chiamiamo disposizioni con ripetizione di ordine di elementi di un insieme tutte le funzioni oppure equivalentemente gli elementi del prodotto cartesiano di per se stesso volte.
Esempio 3.11. Le funzioni di in sono identificabili con le terne , , , , , , , . La prima è la funzione costante di valore 1, la seconda è la funzione tale che , , , …, l’ultima è la funzione costante di valore 2.
Il metodo delle scelte successive prova che il numero delle disposizioni con ripetizione di elementi a a è
Esempio 3.12. Vogliamo contare i sottoinsiemi di un insieme di ordine . Possiamo immaginare di costruire un sottoinsieme di esaminando ciascun elemento di e decidendo se vogliamo metterlo nel sottoinsieme oppure no. Dobbiamo così eseguire per volte una scelta tra possibilità. Quindi il numero di possibili sottoinsiemi è dato dal prodotto delle scelte e quindi, come già detto, è .
Esempio 3.13. Vogliamo calcolare il numero delle colonne tra loro diverse che si possono giocare al totocalcio. Come è noto, il gioco consiste nell’assegnare uno dei tre simboli , , ad ognuna delle 13 partite. Ogni colonna può essere identificata con una sequenza ordinata di elementi scelti tra , , e quindi con una funzione da (i numeri da 1 a 13 corrispondono nell’ordine della schedina alle 13 partite) in un insieme con 3 elementi (i tre simboli citati). Le colonne possibili sono quindi . Giocando tutte queste colonne si ha la certezza del tredici (purtroppo con una spesa superiore alla vincita !!).
Si dice permutazione di oggetti distinti un qualunque loro ordinamento o allineamento. Per contare il numero delle permutazioni è utile il simbolo di fattoriale. In modo più formale:
Esempio 3.15. Se scriviamo le funzioni biunivoche di in sè elencando ordinatamente le immagini come terne , otteniamo le 6 terne:
Osserviamo che in ogni terna compaiono i 3 numeri esattamente una volta sola e che ciò nelle varie terne viene fatto in tutti gli ordini possibili: abbiamo ordinato (allineato) in tutti i modi possibili i nostri elementi.
Dato un numero naturale , chiamiamo fattoriale di il numero:
Si pone inoltre . È una convenzione, ma come vedremo ha una motivazione ben precisa. Notiamo che cresce rapidamente al crescere di . Ne diamo i primi dieci valori:
Il numero complessivo delle permutazioni di oggetti è:
Possiamo infatti scegliere in modi diversi l’elemento da mettere al primo posto, in modi quello da mettere al secondo (tutti gli elementi vanno bene, tranne quello scelto per il primo posto), in modi quello da mettere al terzo posto e così via. Per il principio delle scelte successive, complessivamente si possono dunque effettuare scelte.
Esempio 3.16. Scriviamo tutte le permutazioni di 3 palline di colore (bianco), (rosso), (verde). Abbiamo due allineamenti che mettono la pallina al primo posto, altrettanti per e
Esempio 3.17. Scriviamo alcune delle permutazioni di 5 palline di colore (bianco), (rosso), (verde), (giallo) e (nero). Possiamo iniziare scrivendo tutte quelle che hanno al primo posto (che saranno , come le permutazioni dei elementi , , , ); tra queste possiamo iniziare da quelle che hanno al secondo posto (che saranno come le permutazioni di , , ):
Potremo poi cambiare l’elemento al secondo posto in tutti i modi possibili. Elencate tutte le permutazioni che iniziano con , passeremo poi a quelle che iniziano con , ecc. Procedere ordinatamente in questo modo ci permette di non dimenticarne nessuna e di non scrivere più volte una stessa permutazione.
Si dice disposizione semplice di oggetti a a (con ) ogni allineamento di oggetti distinti scelti in un insieme di . In modo più formale:
Definizione 3.18. Chiamiamo disposizioni semplici di ordine degli elementi di un insieme tutte le funzioni iniettive .
Osserviamo che se , è necessario supporre poichè in caso contrario, per il principio dei cassetti, non ci sarebbero funzioni iniettive da a . Il numero totale di disposizioni semplici di elementi a a è:
Possiamo infatti scegliere in modi diversi l’oggetto da mettere al primo posto, in modi quello da mettere al secondo posto (vanno bene tutti, tranne quello messo al primo posto), in modi quello da mettere al terzo posto e così via fino all’ultimo posto; poichè i posti sono , all’ultimo posto potremo scegliere tra oggetti (tutti meno i già utilizzati).
Esempio 3.19. Sia l’insieme formato da tre palline di colore verde ( ), rosso ( ), nero ( ). Le disposizioni di queste tre palline a due a due sono , e precisamente, sono gli allineamenti:
Possiamo vedere ogni disposizione anche come una funzione iniettiva dall’insieme (o più generalmente da un insieme di ordine ) in che associa ad il primo elemento della disposizione e a il secondo, ossia:
Esempio 3.20. Consideriamo una funzione : come già osservato nel capitolo precedente, alcune sono iniettive e altre no. Contiamo quante sono quelle non iniettive. Ordiniamo in un modo qualsiasi gli elementi , siano . Ogni funzione è individuata dalla lista ordinata delle 7 immagini , lista che in genere può contenere anche elementi ripetuti. Le funzioni sono quindi , come le disposizioni con ripetizione dei 18 elementi di in liste di . Le funzioni iniettive sono quelle corrispondenti a liste senza ripetizioni: il loro numero è quindi . Di conseguenza le funzioni non iniettive sono .
Affrontiamo ora il problema quello da cui il calcolo combinatorio prende il nome. Vogliamo contare in quanti modi si possono scegliere oggetti (diversi, ma senza un ordine precisato) in un insieme di oggetti diversi. poichè non vogliamo precisare l’ordine con cui scegliamo i elementi, ma solo quali sono, quello che vogliamo considerare è un sottoinsieme di con elementi.
Definizione 3.21. Chiamiamo combinazioni di ordine di elementi di un insieme tutti i sottoinsiemi di con elementi.
Anche in questo caso se è necessario supporre . Per contare le combinazioni possiamo immaginare di costruire per prima cosa tutte le disposizioni di ordine degli elementi di (che sono ) e poi di raggruppare tra loro tutte quelle costituite dagli stessi elementi; ogni gruppetto contiene disposizioni (le permutazioni dei elementi che compaiono in ciascuna disposizione del gruppetto). I gruppetti corrispondono alle combinazioni (ossia ai sottoinsiemi con elementi) e il loro numero è quindi .
Esempio 3.22. Se è l’insieme formato da tre palline di colore verde ( ), rosso ( ), nero ( ), le disposizioni di queste tre palline a due a due sono , e, precisamente, sono gli allineamenti: Le combinazioni di queste tre palline a 2 a 2 sono 3: Notiamo che ciascuno di essi corrisponde a diverse disposizioni.
Per esprimere in modo generale la formula del numero di combinazioni utilizziamo il simbolo binomiale. Si dice coefficiente binomiale su , ( ), il numero:
Potremo quindi scrivere sinteticamente:
Esempio 3.23. Aggiungiamo all’insieme dell’esempio precedente una pallina gialla e scriviamo tutte le combinazioni delle palline a a . Otteniamo sottoinsiemi: .
Esempio 3.24. In una lotteria vengono assegnati premi uguali mediante estrazione a sorte tra i partecipanti. Il terzetto di vincitori è un insieme di persone sorteggiate, che non tiene conto dell’eventuale ordine di estrazione. I possibili terzetti di vincitori sono allora tanti quante le possibili scelte di elementi in un insieme di , ossia sono .
Vediamo ora alcune proprietà dei binomiali. Siano ed numeri interi, .
Proof. Dimostriamo la formual di Stiefel in due modi diversi. La prima dimostrazione usa la definizione algebrica del simbolo binomiale. Vogliamo provare che è corretta l’uguaglianza
La correttezza o meno non si modifica se moltiplichiamo i due membri per il numero e li dividiamo per il numero (che sono entrambi ):
è evidente che l’uguaglianza è corretta. Proviamo ora la stessa uguaglianza ricordando che i binomiali contano le combinazioni semplici. Consideriamo un insieme con elementi, uno dei quali è l’elemento . Consideriamo i sottoinsiemi di con elementi. Possiamo suddividere tali sottoinsiemi in due tipi distinti: quelli che non contengono e quelli che lo contengono. Quelli che non contengono sono i sottoinsiemi di (insieme con elelemnti) di cardinalità : il loro numero è quindi . Ogni sottoinsieme del secondo tipo può essere ottenuto considerando un sottoinsieme di elementi di (a cui viene poi aggiunto ): il numero di tali sottoinsiemi è quindi . Quindi il primo membro della formual di Stiefel fornisce il numero dei sottoinsiemi di di cardinalità sommando il numero di sottoinsiemi del primo tipo e il numero di sottoinsiemi del secondo tipo, mentre il secondo membro della formual fornisce direttamente numero di tutti i sottoinsiemi di con elementi. Quindi i due membri sono uguali □
Il nome dei coefficienti binomiali deriva dal fatto che essi sono appunto i coefficienti che compaiono nello sviluppo della potenza esima di un binomio mediante la formula del binomio di Newton.
Proof. Dimostriamo questa formula in due modi diversi. Per la prima dimostrazione usiamo l’induzione su . Per abbiamo . Notiamo che il coefficiente 1 di X coincide proprio con e il coefficiente di coincide con . Supponiamo ora che la formula valga per un certo numero e proviamo che allora vale anche per il numero . Possiamo scrivere come prodotto . Usando l’ipotesi induttiva otteniamo
Eseguiamo quindi il prodotto e raccogliamo i monomi simili. Otteniamo una volta sola il monomio moltiplicando per : dunque il suo coefficiente sarà . Lo stesso vale per il monomio . Otteniamo invece due volte ogni altro monomio , con : una volta moltiplicando per e una volta moltiplcando per . Dunque nel risultato il suo coefficiente sarà
che per la formula di Stiefel coincide proprio con . Per seconda dimostrazione utilizzamo le combinazioni. Numeriamo da 1 a gli fattori che corrispondono a . Eseguendo il prodotto mediante la proprietà distributiva otteniamo un monomio se scegliamo l’addendo in fattori e nei rimanenti l’addendo : i modi di scegliere fattori tra gli elencati è dato da . Quindi nello sviluppo della potenza troveremo monomi simili tutti con coefficiente : raccogliendoli il coefficiente è pertanto . □
Spesso i coefficienti binomiali si scrivono nel modo seguente detto Triangolo di Tartaglia (o Triangolo di Pascal):
Notiamo che il primo e l’ultimo coefficiente binomiale in ogni riga del triangolo sono uguali a 1 (per la prima proprietà vista), il triangolo è simmetrico rispetto alla retta verticale centrale (per la seconda proprietà) e ogni coefficiente binomiale all’interno del triangolo è la somma dei due coefficienti binomiali alla sua destra e alla sua sinistra nella riga precedente (per la formula di Stiefel). Queste osservazioni ci permettono di riscrivere il triangolo di Tartaglia calcolando molto facilmente i numeri di ogni riga:
Solitamente ben noti sono gli sviluppi delle potenze fino al terzo grado:
Se nei due membri della formula dello sviluppo della potenza del binomio sostituiamo e otteniamo un’altra interessante proprietà dei binomiali: iv) la somma della riga -esima del triangolo di Tartaglia è ossia:
Le proprietà viste dei binomiali possono essere motivate osservando che:
c’è un solo un sottoinsieme con 0 elementi (l’insieme vuoto ) e un solo sottoinsieme con elementi (tutto l’insieme );
scegliere elementi tra è come isolare i restanti ;
fissato un certo elemento in un insieme che ha elementi, i sottoinsiemi di con elementi possono essere di due tipi: quelli che non contengono e quelli che lo contengono. Quelli del primo tipo sono tanti quanti i modi di scegliere elementi nell’insieme (che ha elementi); quelli del secondo tipo sono tanti quanti i modi di scegliere elementi in (a cui aggiungere poi stesso);
la somma di tutti i binomiali della riga -esima del triangolo di Tartaglia è poichè, come abbiamo già visto, tutti i possibili sottoinsiemi di un insieme con elementi sono .
Esempio 3.26. Ad un appello d’esame si presentano 16 studenti, ma solo 10 possono essere interrogati il primo giorno. Ci sono più oppure meno di 1000 modi di scegliere i 6 che dovranno ritornare il giorno successivo? I modi di scegliere 6 elementi in un insieme di 16 sono:
Esempio 3.27. Dobbiamo scegliere 3 cavie maschio (tra le 10 a disposizione) e 4 cavie femmina (tra le 12 a disposizione) per un esperimento. In quanti modi può avvenire la scelta della coppia di cavie? La scelta è quella di 3 elementi in un insiem di 10 seguita dalla scelta di 4 elementi in un insieme di 12. Si ha quindi:
Alcuni problemi che sembrano richiedere l’uso di un insieme in verità utilizzano qualcosa
di diverso che sarà chiamato un multi-insieme.
Per esempio le lettere dell’alfabeto contenute nella parola torino sono, in ordine alfabetico,
. La
notazione con le parentesi graffe ricorda quella di un insieme, ma un insieme non contiene
elementi ripetuti. Siamo quindi in presenza di qualcosa di diverso.
Definizione 3.28. Un multi-insieme scelto da un insieme è una funzione da all’insieme degli interi non negativi. Per ogni , è detta la molteplicità di nel multi-insieme. La cardinalità del multi-insieme è la somma delle molteplicità degli elementi di S.
Esempio 3.29. Qual è la molteplicità di ciascuna lettera dell’alfabeto nella parola torino? Qual è la cardinalità del multi-insieme delle lettere di torino? La molteplicità di , , , è 1, la molteplicità di è 2 mentre la molteplicità di ogni altra lettera dell’alfabeto è . In simboli la funzione di molteplicità è data da , , . La cardinalità del multi-insieme è .
Esempio 3.30. Ad un gioco a premi partecipano 4 concorrenti. La prima prova consiste in 12 domande: per ogni domanda, il primo concorrente che dà la risposta giusta ottiene un punto. Supponendo vengano assegnati tutti i 12 punti, quanti sono i possibili esiti del primo gioco? Sappiamo che ogni concorrente ottiene un punteggio da 0 a 12, e che la somma dei punteggi dei concorrenti è 12. Possiamo immaginare di visualizzare l’esito come una lista di 1 (1 punto per ciascuna domanda) scrivendo prima quelli ottenuti dal primo concorrente, poi quelli del secondo e così via, inserendo un segno di separazione tra quelli di un concorrente e quelli del successivo. Ad esempio se il primo ha ottenuto 5 punti, il secondo 2, il terzo 4 e l’ultimo 1, avremo
e se i punteggi sono stati 9, 0, 3, 0, avremo
In tutti i casi ci saranno caselline (dove è il numero di concorrenti meno uno) in cui sistemare i separatori e i 12 numeri 1: quindi i possibili esiti corrispondono a scegliere dove mettere i 3 separatori sceglinedo 3 posizioni tra (oppure a scegliere le 12 posizioni in cui sistemare gli ). In formule:
Proof. (Metodo dei separatori). Indichiamo con gli elementi di . Per ogni multi-insieme su di cardinalità , cioè per ciascuna funzione definita da in tale che , possiamo definire una sequenza di numeri e come segue:
Ora è la cardinalità del multi-insieme e quindi una sequenza come quella precedente contiene volte il numero 1 e volte il numero , quindi in totale elementi. Inoltre, data una sequenza come sopra, si individua un multi-insieme scelto da S utilizzando gli 0 per suddividere la sequenza in n gruppi di numeri 1, dove per ogni gruppo il numero di 1 che compaiono rappresenta la molteplicità dell’elemento corrispondente. Quindi le sequenze del tipo precedente sono tante quanti i multi-insiemi scelti da S. poichè il numero di tali sequenze è il numero di modi di scegliere gli elementi in cui posizionare i numeri 0, questo numero è dato da
cioè dal numero dei sottoinsiemi con elementi di un insieme con elementi e quindi questo è anche il numero dei multi-insiemi di cardinalità scelti in . □
Esempio 3.32. Una pasticceria produce 5 tipi, , , , , di paste ricoperte al cioccolato. In quanti modi diversi si può confezionare un vassoio con 8 di queste paste? Ogni confezione di 8 paste può essere pensata come un multi- insieme di cardinalità 8 scelto da un insieme di cardinalità 5. Quindi ci sono
confezioni diverse. Se ad ogni confezione associamo la sequenza di numeri e con numeri , la confezione contiene 0 paste di tipo , 0 paste di tipo , 3 paste di tipo , 2 paste di tipo e 3 paste di tipo .
3.1 Siano e ; scrivere tutti gli elementi del prodotto cartesiano .
3.2 In una regione vi sono venti città, collegate a coppie da una strada comunale. Quante strade comunali possiede la regione in questione?
3.3 Quante diagonali ha un poligono convesso di lati?
3.4 Per anagramma di una certa parola, si intende un qualunque riordinamento delle lettere che costituiscono quella parola. Contrariamente a quanto succede in enigmistica, in matematica NON si richiede che il nuovo riordinamento delle lettere formi una parola di senso compiuto. Calcolare quanti sono gli anagrammi delle parole seguenti:
3.5 Quanti sono gli anagrammi della parola PADRE? E della parola MAMMA?
3.6 Scrivere tutti i numeri di due cifre (non necessariamente diverse) scelte tra .
3.7 In quanti modi 3 oggetti possono essere colorati con 5 colori diversi?
3.8 Ad un campionato di calcio partecipano 20 squadre. Ogni squadra gioca una prima volta contro tutte le altre (girone di andata) e poi una seconda (girone di ritorno). Quante partite in totale si disputano nel girone d’andata? Qual’è la risposta per un torneo a squadre, se ?
3.9 Vogliamo calcolare in quanti modi diversi si può scegliere una terna di numeri compresi tra e ordinati in ordine crescente .
3.10 Calcolare il numero di modi distinti in cui può essere servito un giocatore di scala quaranta in una singola mano.
3.11 (a) Quanti insiemi di 5 carte si possono avere con un mazzo da poker di 52 carte? (b) Quanti poker di assi si possono formare ? (c) Quanti poker diversi si possono formare ?
3.12 Una classe è formata da 10 ragazzi e 10 ragazze. Dividiamo a caso la classe in due squadre composte da 10 persone ciascuna. In quanti modi questo può avvenire? Quanti sono i casi in cui le due squadre hanno lo stesso numero di ragazze e ragazzi? Quale è il rapporto tra tali due valori scritto in forma percentuale?
3.13 Dire quanti sono gli anagrammi della parola LOGICA e della parola ILLOGICA.
3.14 Scrivere tutti i numeri (di 3 cifre) formati dalle cifre 1 , 2 , 3 non ripetute.
3.15 Quattro giocatori di tennis vogliono giocare un doppio. Quante coppie distinte si possono formare?
3.16 Nel gioco del Super-enalotto bisogna indovinare 6 numeri scelti tra il numero 1 e il numero 90. Quanti insiemi di 6 numeri si possono formare ?
3.17 Quanti sono i possibili prodotti di 6 fattori che si possono formare con i numeri 7, 17 e 37?
3.18 Uno studente deve seguire 3 corsi di lingue tra i seguenti: inglese, francese, tedesco, spagnolo, russo. Quante possibili scelte ha? quante se vuole includere il corso di inglese?
3.19 Verificare mediante le formule la validità della Formula di Stiefel.
3.20 (Da un compito d’esame) Quanti sono gli anagrammi della parola PROBLEMA che contengono almeno una tra le sequenze di lettere PR, RMAE, EP?
3.21 Dati 5 punti del piano, a 3 a 3 non allineati, quante sono le rette che passano per 2 di tali punti? Cambia la risposta se anzichè nel piano i 5 punti sono scelti nello spazio? Qual’è la risposta nel caso generale di punti, con la medesima condizione che siano a 3 a 3 non allineati?
3.22 Sia l’insieme . Quante sono le applicazioni iniettive tali che ? Quante le suriettive con ?
3.23 Si hanno a disposizione 6 vernici di colori diversi, con cui si vogliono dipingere le 4 pareti di una stanza, usando un solo colore per parete. In quanti modi si possono dipingere le pareti se si decide di non usare più volte uno stesso colore? In quanti modi se si decide che è possibile usare più volte uno stesso colore? In quanti modi se si decide che è possibile usare più volte uno stesso colore, purchè non su pareti adiacenti? Generalizzare le risposte dei precedenti quesiti al caso di una stanza poligonale con pareti.
3.24 Nove persone si presentano ad un concorso per 4 posti. Quante sono le possibili graduatorie dei vincitori, se si escludono gli ex-aequo?
3.25 Quanti sono i numeri naturali che sono multipli di almeno uno tra 2, 3, 5?
3.26 Quanti sono i numeri naturali che sono multipli di almeno uno tra 7, 17, 37?
3.27 Quanti sono i numeri naturali che sono multipli di almeno uno tra 10, 55, 22?
3.28 Siano , , .
Determinare il numero di applicazioni di in e il numero di applicazioni tali che .
Si fissi una applicazione suriettiva a scelta. Quante sono le applicazioni tali che ? È vero che lo stesso numero si sarebbe ottenuto per ogni altra applicazione suriettiva ?
Si fissi una applicazione suriettiva a scelta. Quante sono le applicazioni tali che ? È vero che lo stesso numero si sarebbe ottenuto per ogni altra applicazione suriettiva ?
Si fissi una applicazione iniettiva a scelta. Quante sono le applicazioni tali che ? È vero che lo stesso numero si sarebbe ottenuto per ogni altra applicazione iniettiva ?
Si fissi una applicazione iniettiva a scelta. Quante sono le applicazioni tali che ? È vero che lo stesso numero si sarebbe ottenuto per ogni altra applicazione iniettiva ?
Iniziamo ora a studiare una alla volta alcune delle principali strutture algebriche, iniziando dalla struttura di monoide e di gruppo. Enunceremo e dimostreremo alcune delle loro principali proprietà e soprattutto impareremo a conoscere alcuni gruppi particolarmente significativi.
Ricordiamo che una operazione binaria (ne esistono anche di più complicate) in un insieme è una funzione . Di solito non indicheremo una operazione con una lettera, come fatto ora, ma con un simbolo (ad esempio , , o più in astratto ). Inoltre, se indica l’operazione, per l’immagine di una coppia useremo la scrittura (come siamo abituati a fare con le operazioni tra numeri), invece della notazione tipica delle funzioni, ossia . Chiameremo tale immagine risultato dell’operazione tra e . Questa definizione di operazione racchiude una classe molto vasta di funzioni, alcune delle quali decisamente poco interessanti e altre ben note fino dai tempi della scuola elementare.
Esempio 4.1. La funzione costante è una operazione in . Il risultato dell’operazione tra due qualsiasi numeri reali è sempre .
Esempio 4.2. L’addizione tra numeri naturali è una operazione in è una operazione in . Per ogni coppia di numeri naturali l’immagine è il numero naturale .
Elenchiamo ora alcune proprietà interessanti relative alle operazioni (che possono essere soddisfatte oppure anche non soddisfatte) da una certa operazione). Sia una operazione nell’insieme :
Esempio 4.5. Gli insiemi con l’usuale operazione somma sono tutti semigruppi. Analogamente se invece della somma consideriamo il prodotto.
Esempio 4.6. Sia un insieme, sia l’insieme delle funzioni e sia la composizione di funzioni. Possiamo considerare come un’operazione su :
L’operazione è associativa:
Si verifica osservando come agiscono e su un qualsiasi elemento di :
Quindi è un semigruppo.
Esempio 4.7. Consideriamo e la funzione : . La funzione è un’operazione, ma non è associativa: infatti, è possibile trovare almeno una terna per cui . Per esempio : . Quindi l’operazione non dà su la struttura di semigruppo.
Definizione 4.9. Se è un semigruppo, possiamo definire le potenze di un elemento mediante l’induzione:
Proof. Dimostriamo per induzione su che . Se , si ha per come abbiamo definito . Supponiamo la proprietà sia vera per un certo , ossia che valga , e dimostriamo che allora vale la proprietà anche per l’intero successivo , ossia che si ha . Si hanno le uguaglianze:
dove
Dimostriamo ora per induzione su che . Per , . Supponiamo ora che sia vero che e otteniamo la catena di uguaglianze
dove
Quando l’operazione che si considera è l’addizione tra numeri, oppure più in generale se usiamo il simbolo per indicare una operazione, le potenze di un elemento si denotano in modo diverso: l’operazione con notazione additiva diventa ed è quindi naturale indicarla con dove .
Proof. Supponiamo che in vi siano due elementi che soddisfano la proprietà che definisce l’elemento neutro. Eseguendo l’operazione troviamo come risultato , poichè composto con ogni altro elemento di lo lascia invariato; d’altra parte abbiamo anche , poichè la stessa proprietà vale per . Quindi .
Definizione 4.13. Sia un insieme e un’operazione su . Si dice che è un monoide se è associativa ed esiste l’elemento neutro. In altre parole è un semigruppo dotato di elemento neutro.
Esempio 4.14. Gli insiemi con l’usuale operazione somma sono tutti monoidi, l’elemento neutro è sempre . Analogamente se invece della somma consideriamo il prodotto, abbiamo struttura di monoide per tutti gli insiemi sopra citati, con elemento neutro .
Esempio 4.15. Consideriamo e l’operazione . Verifichiamo se è un semigruppo. Prendo in .
Quindi è un semigruppo. Verifichiamo se esiste un elemento neutro rispetto all’operazione . Cerchiamo tale che per ogni .
L’elemento neutro esiste ed è 2. Quindi è un monoide.
Esempio 4.16. Definiamo su l’operazione . L’operazione è associativa (si veda esercizio 5.1). è un monoide perchè esiste l’elemento neutro, .
Sia un insieme, che chiamiamo alfabeto. Chiamiamo parola nell’alfabeto una qualsiasi sequenza di elementi (ed anche la parola vuota, sequenza di 0 simboli).
Per ogni , definiamo come l’insieme delle parole nell’alfabeto formate da esattamente elementi di :
Per , contiene un solo elemento, la parola vuota che non contiene nessun elemento di . Invece .
Definiamo un’operazione su : siano e due parole di ,
è una parola di e è un’operazione, quindi è una struttura algebrica. Chiamiamo la concatenazione.
Proof. Dobbiamo verificare che la concatenazione sia un’operazione associativa e che esista l’elemento neutro. Per l’associatività è sufficiente osservare che se e allora
Inoltre l’elemento neutro rispetto a esiste, ed è la parola vuota . □
Definizione 4.20. Siano un insieme e un’operazione in . Diremo che è un gruppo se:
Esempio 4.21. con la somma è un gruppo, mentre con la somma non lo è (manca l’inverso degli elementi rispetto a ). Se consideriamo l’operazione prodotto usuale, nessun insieme tra e è un gruppo: infatti l’elemento 0 non possiede inverso rispetto al prodotto. Otteniamo invece un gruppo se consideriamo l’operazione prodotto negli insiemi , dove il simbolo di insieme numerico con stellina ad esponente indica l’insieme stesso privato dello zero. Quindi ad esempio .
Esempio 4.22. Sia un insieme e sia l’insieme di tutte le funzioni . Come già visto nell’Esempio 4.6, con la composizione di funzioni è un semigruppo. Inoltre è anche dotato di elemento neutro rispetto a : la funzione identità e costituisce quindi un monomide.
però, se , non è un gruppo, poichè ad esempio le funzioni costanti non hanno inverso. Se infatti sono due elementi diversi e indichiamo con la funzione costante data da , allora la composizione di una qualsiasi funzione con , coincide con ed è quindi diversa da : si ha ad esempio .
Definizione 4.23. Un gruppo si dice gruppo abeliano se l’operazione è anche commutativa, ossia si ha .
Da ora in poi indicheremo abitualmente l’operazione di un generico gruppo mediante il simbolo e chiameremo “prodotto” tale operazione, ossia adotteremo la notazione moltiplicativa. Per coerenza, l’unica identitàdi sarà denotata con e l’unico inverso di un elemento sarà denotato . Spesso il simbolo di prodotto si sott’intende. Nel caso dei soli gruppi abeliani potremo indicare l’operazione di gruppo col simbolo e chiamarla somma, ossia useremo la notazione additiva; in tal caso indicheremo con l’identità del gruppo e con l’inverso di un elemento (che chiameremo opposto di ).
Proposizione 4.24. Sia un gruppo. Allora:
Proof. i) Abbiamo già dimostrato l’unicità dell’identità parlando dei semigruppi. ii) Supponiamo che per un dato elemento esistano due elementi e che si comportano come suoi inversi, ossia tali che ed anche . Eseguendo il prodotto a tre ed utilizzando la proprietà associativa otteniamo:
Dal confronto del primo e dell’ultimo membro otteniamo allora e quindi i due inversi sono in realtà lo stesso elemento. ii) Verifichiamo che quello scritto è proprio l’inverso di applicando la definizione (tralasciamo ora il simbolo di operazione) :
ed anche
□
Proof. i) Se le altre due uguaglianze valgono per definizione. Supponiamo allora che e moltiplichiamo i due membri a sinistra per (che esiste poichè siamo in un gruppo). Otteniamo allora: . Per definizione di identità il secondo membro è , mentre per la proprietà associativa il primo membro diventa . Pertanto . La dimostrazione dell’altra implicazione è analoga: basterà moltiplicare a destra per . ii) Se , allora le altre due uguaglianze si ottengono per definizione di identit‘a. Supponiamo allora e moltiplichiamo i due membri a destra per (che esiste poichè siamo in un gruppo). Otteniamo così: ossia . L’altra implicazione si ottiene in modo analogo moltiplicando a sinistra per . iii) Anche la verifica della proprietà di cancellazione si ottiene come le precedenti, moltiplicando opportunamente (ossia a sinistra oppure a destra) per l’inverso di , l’elemento che vogliamo “cancellare ”. □
Esempio 4.27. Sia un insieme e sia l’insieme di tutte le funzioni . Come già visto negli Esempi 4.6 e 4.22, con la composizione di funzioni è un monoide. non è in generale un gruppo: infatti le funzioni biunivoche da in sono tutte e sole quelle che possiedono inverso rispetto a . Le funzioni non biunivoche invece non hanno inverso. Inoltre, per non possono in generale valere le proprietà dei gruppi quali ad esempio la cancellazione. Per vederlo esplicitamente, possiamo pensare a , e considerare la funzione , . Questa funzione non ha inversa rispetto a . Per quel che riguarda la cancellazione, sia la funzione definita come . Allora
Esempio 4.28. Sia un insieme e consideriamo . Osserviamo che possiamo considerare l’operazione di composizione di funzioni come un’operazione su : infatti, componendo funzioni biunivoche, otteniamo ancora una funzione biunivoca. è un gruppo. Infatti
Definizione 4.29. Sia un gruppo e sia un suo elemento. Definiamo le potenze di con esponente intero (positivo, nullo o negativo) nel modo seguente:
Le proprità delle potenze che abbiamo dimostrato nei semigruppi relativamente al caso degli esponenti positivi valgono nel caso dei gruppi anche per gli esponenti minori o uguali a e si estendono a proprietà che riguardano gli inversi.
4.1 Consideriamo su l’operazione . Verificare che è associativa.
4.2 Sia un insieme, il suo insieme delle parti e sia la differenza simmetrica:
è un’operazione? ‘Eè commutativa? Esiste elemento neutro? Esiste inverso per ogni elemento di ?
4.3 Consideriamo su l’operazione quoziente: per ogni , è un numero reale. Verificare se l’operazione quoziente è commutativa, associativa, se esiste elemento neutro in rispetto a tale operazione e eventualmente se esiste inverso di ogni elemento in rispetto all’operazione quoziente.
4.4 Si consideri su l’operazione . Stabilire se è un monoide.
4.5 Sia e consideriamo il monoide delle parole . Quante sono le parole di che contengono solo e ?
4.6 Si pone e si definisce la seguente legge di composizione interna:
4.7 Considerati gli insiemi e con le operazioni definite dalle tabelle seguenti
4.8 Si consideri la struttura algebrica , dove l’operazione interna è definita come segue:
4.9 Si consideri la struttura algebrica , dove l’operazione è definita come segue:
Fissiamo un numero intero positivo . Denotiamo con l’insieme dei numeri naturali .
Definizione 5.1. Sia una funzione che ha come dominio e codominio . Se è biunivoca, allora è una permutazione. L’insieme di tutte le permutazioni definite su si denota con .
NOTA BENE: se è un insieme finito, per ogni funzione , si ha
iniettiva suriettiva biunivoca.
Esempio 5.2. Consideriamo in la permutazione data da:
Per scrivere in modo veloce , utilizzeremo una tabella costituita da due righe: nella prima sono elencati ordinatamente gli elementi di e al di sotto di ciascuno di essi, la seconda riga contiene le loro immagini. Otteniamo così la seguente tabellina
Possiamo utilizzare una tabellina analoga a quelle presentata nell’esempio per scrivere in modo sintetivo qualsiasi permutazione. Nella prima riga elenchiamo gli elementi di e al di sotto di ciascuno scriviamo la sua immagine:
Le permutazioni sono funzioni, possiamo quindi anche comporre due permutazioni.
Esempio 5.3. Consideriamo in la permutazione dell’esempio 5.2 e la seguente permutazione :
Possiamo comporre (con l’usuale legge di composizione tra funzioni) e . poichè la composizione di funzioni non è commutativa, eseguiamo entrambe le composizioni (ottenendo risultati diversi).
Riassumendo con la scrittura “a tabellina ”:
Analogamente, possiamo calcolare , ottenendo:
Ricordiamo ora due proprietà della composizione tra funzioni Intanto, la composizione di funzioni gode della proprietà associativa. Inoltre, la composizione di due funzioni biunivoche è una funzione biunivoca. In particolare, se componiamo due permutazioni, otteniamo ancora una permutazione. Possiamo quindi affermare che con l’operazione di composizione di funzioni è un semigruppo. però se l’operazione NON è commutativa (vedi Esempio 5.3). Nell’Esempio 4.28, abbiamo già verificato che l’insieme delle funzioni biunivoche da un insieme nell’insieme è un gruppo con la composizione . Questo vale quindi anche per l’insieme delle permutazioni con . Vediamo esplicitamente come si scrivono nella nostra notazione l’identità e l’inverso in . L’identità (o elemento neutro) è
cioè è la funzione identità definita come per ogni . Si verifica facilmente che per ogni . Per poter affermare che con l’operazione è un gruppo resta da dimostrare che per ogni esiste la permutazione inversa tale che . Possiamo costruire con facilità la funzione nel modo seguente:
Esempio 5.4. Consideriamo la tabellina della permutazione di Esempio 5.2
Per ottenere la permutazione inversa di , scambiamo le due righe della tabella precedente
e poi riordiniamo le colonne
Si verifica facilmente che la permutazione ottenuta col metodo illustrato è proprio la funzione inversa. Infatti, l’inversa di una funzione biunivoca è la funzione che associa ad un elemento l’unico elemento tale che . Quindi l’immagine di un elemento è l’unico elemento tale che , ossia è il numero che nella tabellina di si trova al di sopra di .
Notazione 5.5. Per le permutazioni si usa sempre la notazione moltiplicativa. Quindi l’identità si denota con (oltre che con e con ) e la permutazione inversa di si denota con . Infine, la composizione si denota semplicemente con , sottindendendo il simbolo di composizione
Riassumendo, abbiamo dimostrato che:
Teorema 5.6. Sia l’insieme delle permutazioni di . Allora in è definita un’operazione, la composizione di permutazioni, che ha le seguenti proprietà :
Corollario 5.7. L’insieme delle permutazioni di con l’operazione di composizione è un gruppo (non abeliano).
Definizione 5.8. Siano un intero, , e siano elementi distinti di . Si dice -ciclo di e si indica con la permutazione tale che , , , , e per ogni . I 2-cicli si dicono anche scambi o trasposizioni. Due cicli e di si dicono disgiunti se . Dato un ciclo , diciamo che è la lunghezza di .
Esempio 5.9. In il simbolo indica la permutazione . Anche e indicano la stessa permutazione . Il termine ciclo si riferisce appunto alla natura circolare di questa permutazione. Infatti in un ciclo conta l’ordine in cui compaiono gli elementi, e non chi è il primo elemento. Invece il ciclo che si scrive invertendo l’ordine degli elementi della scrittura di ossia il ciclo è la permutazione inversa di . Infatti e si ha . Il simbolo indica la funzione che scambia tra loro e e lascia fissi , , e ossia .
Il risultato seguente raccoglie alcuni fatti importanti sulle permutazioni; per ciascuno di essi diamo una dimostrazione algoritmica, per mostrare come si può operare concretamente.
Teorema 5.10. Sia un intero positivo.
Proof. Dimostriamo innanzi tutto che due cicli disgiunti commutano tra loro. Dimostreremo poi le affermazioni i), iii) e iv) che riguardano l’esistenza di particolari decomposizioni in cicli, fornendo per ciascuna un algoritmo che costruisce tali decomposizioni. ii) Se e sono disgiunti, la loro composizione, nei due modi, è la funzione data da , e se . i) Per costruire la decomposizione di una permutazione in cicli disgiunti consideriamo il più piccolo intero tale che e iniziamo a costruire un ciclo . poichè gli elementi in sono solo , dopo al più applicazioni della funzione troveremo un elemento già insierito nel ciclo. Tale elemento non può essere che il primo, ossia , poichè è iniettivo. Chiudiamo così il primo ciclo. Se abbiamo esaurito tutti gli elementi di che non sono fissati da (ossia quelli tali che ), ci fermiamo. Altrimenti prendiamo uno degli elementi di non ancora inseriti nel ciclo già costruito e non fissati da e iniziamo a costruire un secondo ciclo, fino a “chiuderlo”. Ripetiamo la procedura fino ad esaurire gli elementi non fissati da . Il ciclo si scrive allora come composizione (in un ordine qualsiasi) dei cicli disgiunti costruiti. iii) Una decomposizione in scambi di una permutazione qualsiasi si otterrà componendo le decomposizioni in scambi dei cicli della sua decomposizione in cicli. Il ciclo si ottiene come composizione di scambi in tanti modi, ad esempio nel modo seguente:
iv) si ottiene come conseguenza delle precedenti. □
Osservazione 5.11. La decomposizione di una permutazione in cicli disgiunti è essenzialmente unica, poichè l’unica variante possibile riguarda l’ordine con cui elenchiamo i cicli; si tratta di una variante poco significativa in quanto, come abbiamo provato, la composizione di cicli disgiunti gode della proprietà commutativa. Un’altra possibile variante riguarda la scrittura dei cicli; infatti possiamo elencare gli elementi che costituiscono un ciclo iniziando da uno qualsiasi di essi. Non si tratta di una diversa decomposizione in cicli, ma solo di simboli leggermente diversi per indicare uno stesso ciclo.
Esempio 5.12. Per decomporre in cicli disgiunti cominciamo da , poichè . Costruiamo il primo ciclo applicando ripetutamente fino a ritrovare stesso: , . . Otteniamo dunque il ciclo . Osserviamo ora che non compare in questo ciclo e che . Costruiamo quindi un secondo ciclo partendo da , che si fermerà quando troveremo nuovamente : , . Otteniamo un secondo ciclo . Controlliamo ora che l’unico numero non considerato nei due cicli è , ma . Dunque la decomposizione è terminata: . Le uniche varianti alla scrittura della decomposizione di sono l’odine dei cicli oppure il punto di inizio dei cicli stessi:
Una decomposizione di in scambi è ad esempio ma lo è anche . Quindi una decomposizione in scambi di è . Una diversa decomposizione in scambi di è .
Raccogliamo nel corollario seguente alcuni fatti utili da ricordare, che sono conseguenza di quanto già detto ed in particolare del Teorema 5.10.
La prima affermazione si prova eseguendo direttamente il calcolo di . Per provare la seconda basta osservare che per la commutatività della composizione di cicli disgiunti abbiamo e che ciascuna potenza coincide con poichè è un multiplo della lunghezza di .
Proof. □
Una stessa permutazione può essere decomposta in scambi in tanti modi diversi, anche costituiti da un diverso numero di scambi.
Definizione 5.14. Una permutazione si dice pari se si può scrivere come composizione di un numero pari di scambi e si dice dispari se si può scrivere come composizione di un numero dispari di scambi.
Una tale terminologia non avrebbe alcun senso se una stessa permutazione potesse essere contemporaneamente pari e dispari.
Proof. Per ottenere la tesi è sufficiente provare che che ogni decomposizione in scambi della permutazione identica è costituita da un numero pari di scambi. Infatti se ci fosse una permutazione che può essere scritta mediante scambi ed anche mediante scambi, allora anche avrebbe la stessa proprietà e quindi potrerbbe essere scritta mediante , scambi, componendo gli scambi che danno con gli scambi che danno . La nostra dimostrazione è un algoritmo che partendo da una qualsiasi decomposizione in scambi di ne costruisce un’altra con scambi. Ripetendo la procedura arriveremo alla decomposizione con scambi. Avremo così provato che , ossia che è pari. A questo scopo useremo le due formule seguenti, dove sono elementi diversi di :
Fissiamo una decomposizione in scambi di ed osserviamo che ogni che compare in uno di tali scambi deve comparire almeno in un altro. In caso contrario mediante tale composizione di scambi non sarebbe immagine di se stesso, ma sarebbe immagine dell’altro elemento che fa coppia con lui nell’unico scambio che lo coinvolge. Supponiamo per semplicità che sia e procediamo nel modo seguente. Applicando ripetutamente la prima delle due formule precedenti possiamo “spostare” uno alla volta i cicli che coinvolgono fino a farli diventare consecutivi. Ora consideriamo due di tali cicli consecutivi : se la seconda formula ci permette di cancellare i due cicli ottenendo una decomposizione di con 2 cicli in meno di prima. Se , la prima formula ci permette di scrivere una decomposizione nello stesso numero di cicli, ma in cui compare una volta in meno. Ripetendo la procedura riusciremo a ottenere una decomposizione in cicli, in cui non compare più. Ora possiamo prendere in esame un altro numero che compare ed applicare a lui la stessa procedura, fino a farlo sparire. Al termine della procedura nessun numero comparirà negli scambi e quindi avremo scambi. Durante ciascun passo della procedura il numero di scambi rimane invariato o diminuisce di 2: pertanto il numero iniziale di scambi era pari. □
Abbiamo visto che la decomposizione di una permutazione in scambi non è univocamente determinata, ma lo è la decomposizione in cicli disgiunti, a meno dell’ordine in cui scriviamo i cicli stessi (Proposizione 5.10). Possiamo “catalogare” le permutazionidi a seconda di quali sono le lunghezze delle permutazioni che costituiscono la sua decomposizione in cicli disgiunti. più precisamente, sia e sia la sua decomposizione in cicli disgiunti. Sia il numero di cicli di lunghezza presenti nella decomposizione di , con la convenzione di considerare gli elementi fissati da come -cicli. L’ -pla è detta il tipo della permutazione . Un altro modo di indicare il tipo di una permutazione è .
Esempio 5.16. Usando la convenzione di non scrivere quando e di scrivere solo quando , i possibili tipi di una permutazione di sono
Esempio 5.17. Calcoliamo il numero di permutazioni di di tipo . Si tratta di sistemare i numeri nella scrittura seguente al posto dei puntini:
Ci sono modi di fare cioè . Bisogna però tenere conto che la stessa permutazione può essere ottenuta con questa procedura in più modi differenti. Infatti si devono fare le due considerazioni seguenti:
In totale il numero delle permutazioni del tipo assegnato è quindi:
Lo stesso risultato può essere ottenuto ragionando nel seguente modo.
Infine, poichè l’ordine di scrittura dei cicli di uguale lunghezza nella decomposizione è arbitrario, il numero ottenuto va diviso per . Quindi, in totale il numero delle permutazioni del tipo assegnato si può anche scrivere nella forma:
Per calcolare la parità di una permutazione possiamo decomporla in scambi e poi contare il loro numero per stabilire se si tratta di un numero pari oppure dispari. Un metodo alternativo e più veloce è dato dalla seguente
Proposizione 5.18. La parità di un -ciclo è . La parità di una permutazione di tipo coincide con la parità di
ossia dalla parità del numero di cicli di lunghezza pari.
Proof. La prima affermazione è conseguenza della Proposizione 5.10. Per quel che riguarda la seconda, basta ricordare che si può ottenere una decomposizione in scambi di una permutazione decomponendo prima nel prodotto di cicli disgiunti e poi sostituendo ad ogni ciclo una sua decomposizione in scambi. Decomponendo ogni -ciclo in scambi, il numero complessivo di scambi in cui abbiamo decomposto è dato proprio dal numero presente nell’enunciato. poichè a noi non interessa sapere quanti sono, ma solo se il numero è pari o dispari, ci basterà contare quanti sono i cicli disgiunti con lunghezza pari, poichè quelli di lunghezza dispari sono permutazioni pari e quindi non modificano la parità. □
5.1 Considerate le seguenti permutazioni:
calcolare i prodotti , , , , , .
5.2 Siano , , , le permutazioni dell’esercizio precedente. Scrivere le loro inverse rispetto alla composizione.
5.3 Siano , , , le permutazioni dell’esercizio 6.1. Scriverle come prodotto di cicli disgiunti. Scrivere inoltre come prodotto di cicli disgiunti anche , , , , , .
5.4 Scrivere tutti i possibili tipi di una permutazione di .
5.5 Calcolare il numero di permutazioni di di tipo e il numero di quelle di tipo .
5.6 Calcolare il numero di permutazioni di di tipo e il numero di quelle di tipo .
5.7 Calcolare il numero di permutazioni di di tipo .
5.8 Calcolare il numero di permutazioni di di tipo . 5.9 Trovare l’inversa di ognuna delle seguenti permutazioni di :
5.10 Dimostrare che una permutazione e la sua inversa hanno la stessa parit‘a.
5.11 Dimostrare che, per ogni coppia di permutazioni e , le permutazioni e hanno la stessa parità.
5.12 Scrivere tutti i tipi di permutazioni in e in .
5.13 Decomporre le permutazioni dell’esercizio 6.1 e dell’esercizio 6.9 in prodotto di trasposizioni.
5.14 Consideriamo le permutazioni , . Trovare la parit‘a di e , e scriverle come prodotto di trasposizioni.
5.15 Calcolare il numero di permutazioni di di tipo e il numero di quelle di tipo .
5.16 Sia permutazione di . Determinare il numero di permutazioni di di tipo tali che .
5.17 Siano e le seguenti permutazioni in
e sia .
5.18 Siano le permutazioni di così definite:
Ancora sui gruppi: sottogruppi e omomorfismi
Da ora in poi, nella trattazione generale useremo sempre (salvo diverso avviso esplicito) la notazione moltiplicativa per i gruppi.
Definizione 6.1. Siano un gruppo e un sottoinsieme di . Si dice che è un sottogruppo di e si scrive se è un gruppo con l’operazione indotta da quella di . Più esplicitamente, è un sottogruppo di se
Spesso per verificare se un sottoinsieme di un gruppo è un suo sottogruppo è comodo utilizzare il seguente
Proposizione 6.2 (Criterio dei sottogruppi). Un sottoinsieme di un gruppo è un suo sottogruppo se e solo se soddisfa la seguente condizione:
Proof. Supponiamo che sia un sottogruppo di . poichè , allora . Se inoltre , allora per definizione di sottogruppo anche e quindi . Quindi il sottogruppo soddisfa il criterio. Supponiamo viceversa che sia un sottoinsieme di che soddisfa il criterio. Proviamo che soddisfa anche le tre condizioni per essere un sottogruppo. Prendiamo un qualsiasi elemento (che esiste perchè ), allora per il criterio . Applicando poi la condizione data dal criterio ai due elementi e otteniamo . Se infine , per quanto abbiamo già provato sappiamo che . Applicando il criterio alla coppia , otteniamo . □
Esempio 6.3. Il sottoinsieme di è un sottogruppo del gruppo . Infatti e per ogni la somma tra e l’opposto di sta in . Invece non è un sottogruppo di . Infatti, , ma .
Esempio 6.4. Il sottoinsieme dei numeri razionali positivi è un sottogruppo di . Infatti l’identità del gruppo appartiene a , l’inverso di un numero razionale positivo è un numero razionale positivo e il prodotto di due numeri razionali positivi è ancora un numero razionale positivo. Invece dei razionali negativi non è un sottogruppo.
Esempio 6.5. Il sottoinsieme delle permutazioni pari di è un sottogruppo di . Infatti la permutazione identità è pari, componendo due permutazioni pari si ottiene una permutazione pari e l’inversa di una permutazione pari è pari. Questo sottogruppo si chiama gruppo alterno su elementi e si denota . Invece le permutazioni dispari di non formano un suo sottogruppo, poichè ad esempio non contiene la funzione identità .
Esempio 6.6. Il sottoinsieme dei multipli interi di è un sottogruppo del gruppo . Infatti e la differenza tra due multipli interi di è un multiplo intero di .
Fissiamo ora un gruppo , un suo sottgruppo e un suo elemento . L’insieme si denota con e si dice laterale sinistro di rappresentato da ; in modo analogo potremmo definire il laterale destro.
Proposizione 6.7. Con le notazioni precedenti:
Proof. i) La funzione data da è biunivoca poichè ha come inversa la funzione che moltiplica ogni elemento a sinistra per . ii) “” poichè , allora esiste tale che e quindi . “” Sia e sia , un qualsiasi elemento di . Allora . Di conseguenza . Per motivi di simmetria vale anche l’altra inclusione e quindi . iii) Nessun laterale è vuoto, poichè e quindi . Per lo stesso motivo l’unione dei laterali è tutto . Due laterali sinistri e hanno un elemento in comune se e solo se esistono tali che . Allora e quindi, grazie a ii), concludiamo che . □
Corollario 6.8 (Teorema di Lagrange). Se è un gruppo finito ed è un suo sottogruppo, allora il numero di elementi di divide esattamente il numero di elementi di .
Proof. Abbiamo dimostrato che i laterali sinistri di formano una partizione di e che inoltre ciascuno di essi ha lo stesso numero di elementi di . Dunque possiamo ottenere il numero di elementi di moltiplicando il numero di elementi di per il numero di laterali sinistri diversi. □
Esempio 6.9 (Il gruppo alterno). è facile verificare che il sottoinsieme delle permutazioni pari di è un suo sottogruppo (detto gruppo alterno). Ogni laterale sinistro costituito da permutazioni con la stessa parità del rappresentante . poichè la composizione di due permutazioni pari è pari e la composizione di due permutazioni dispari è pari, vi saranno due soli laterali stesso e l’insieme formato dalle permutazioni dispari. Quindi il numero di elementi di è .
Esempio 6.10. Il sottogruppo ha elementi. poichè non divide possiamo affermare che non ha sottogruppi di ordine . Infatti l’ordine di ogni suo sottogruppo deve appartenere all’insieme dei divisori di : . Il teorema di Lagrange non afferma tuttavia che per ognuno di tali divisori esitono effettivamente sottogruppi con quell’ordine. Lasciamo come esercizio al lettore stabilire se in vi è un sottogruppo con elementi.
Ora che consideriamo non solo insiemi, ma strutture algebriche (quindi un insieme dotato di un’operazione), ci interessa capire quando una funzione definita tra due strutture algebriche “rispetta” le operazioni.
Definizione 6.11. Siano due insiemi e siano e due operazioni definite su e rispettivamente. Una funzione è un omomorfismo (detto anche morfismo) rispetto alle operazioni e se
Esempio 6.12. Si consideri la funzione data da . Possiamo verificare che è un omomorfismo rispetto alle operazioni indicate. Infatti
Esempio 6.13. Si consideri la funzione data da . Possiamo verificare che non è un omomorfismo rispetto alle operazioni indicate mostrando che in almeno un caso non rispetta le operazioni. Ad esempio
Se una struttura algebrica deve soddisfare anche altre condizioni, oltre a possedere una operazione, una funzione sarà un omomorfismo di quella struttura se oltre alle operazioni rispetterà anche le altre proprietà .
Definizione 6.14. Siano e due semigruppi. Diremo che una funzione è un omomorfismo di semigruppi se è un omomorfismo rispetto alle operazioni. Se inoltre e sono monoidi e , indicano rispettivamente l’elemento neutro di rispetto all’operazione e l’elemento neutro di rispetto all’operazione , diremo che è un omomorfismo di monoidi se è un omomorfismo di semigruppi e inoltre .
Esempio 6.15. Consideriamo con l’operazione di moltiplicazione componente per componente . Siverifica facilmente che si tratta di un monoide con identità , ma non di un gruppo: ad esempio è un elemento privo di inverso. Consideriamo la funzione data da . Questa funzione rispetta l’operazione del monoide, ma non è un omomorfismo di monoidi, in quanto che non è l’identità del codominio.
Definizione 6.16. Siano , due gruppi. Una funzione si dice omomorfimo di gruppi se rispetta le operazioni, ossia:
L’idea di omomorfismo di struttura algebrica è quella di una funzione che rispetta tutte le proprietà della struttura algebrica. Nel caso dei gruppi ci si aspetterebbe che la definizione contenga anche la richiesta di mandare l’identità del dominio in quella del codominio e di mandare l’inverso di un elemento nell’inverso della sua immagine. Vediamo ora che queste condizioni sono solo apparentemente assenti dalla definizione; in realtà nel caso dei gruppi la condizione di essere compatibile con le operazioni ha come conseguenza anche quelle relative alle identità e agli inversi.
Proof. Preso un qualsiasi elemento , avremo per definizione di omomorfismo e di identità :
Applicando la cancellazione a otteniamo . □
Si faccia attenzione al fatto che la dimostrazione del lemma precedente funziona perchè dominio e codominio sono gruppi, ma non vale ad esempio nel caso dei monomidi, come si vede nell’esempio seguente. Non tutte le funzioni tra due gruppi sono omomorfismi. La funzione considerata nel lemma seguente in genere non lo è , tuttavia si tratta di una funzione importante, con conseguenze interessanti.
Definizione 6.18. Un omomorfismo di gruppi si dice:
Se esiste un isomorfismo tra i gruppi e , allora si dice che e sono isomorfi e si scrive .
Esempio 6.19. Il gruppo delle simmetrie del triangolo equilatero è isomorfo al gruppo delle permutazioni di 3 elementi. Si ottiene un isomorfismo numerando da 1 a 3 i vertici del triangolo ed associado ad ogni simmetria del triangolo la corrispondente permutazione dei vertici. Il gruppo delle simmetrie del quadrato non è invece isomorfo al gruppo . Possiamo costruire un monomorfismo in modo analogo a quanto fatto per il triangolo equilatero. Tuttavia nessuna simmetria del quadrato corrisponde alla permutazione che fissa due vertici adiacenti e scambia gli altri due.
Abbiamo visto che una funzione è suriettiva se la sua immagine insiemistica coincide col codominio. Ovviamente questo vale anche per i morfismi di gruppi. Tuttavia l’insieme immagine in questo caso ha proprietà più interessanti.
Proof. Eseguiamo la verifica utilizzando il Criterio dei sottogruppi. Due qualsiasi elementi di sono del tipo , con . Abbiamo allora, grazie alla Proposizione 6.17 e alla definizione di omomorfismo:
poichè è un gruppo e , allora anche e quindi . □
Per verificare l’iniettività di una funzione dobbiamo controllare che ogni coppia di elementi diversi del dominio abbiano immagini diverse. Nel caso dei morfismi il controllo può essere fattopiù velocemente usando la nozione seguente.
Definizione 6.21. Dato un omomorfismo di gruppi , si dice nucleo di e si denota l’insieme controimmagine di . In simboli:
Lemma 6.22. Sia un omomorfismo di gruppi. Allora:
Proof. i) Usiamo il criterio. Siano due elementi di , ossia due elementi di tali che . Allora:
Dunque ossia . ii) “” Se è iniettivo, la controimmagine di un elemento, in particolare la controimmagine di , contiene al massimo un elemento. D’altra parte è un sottogruppo di e quindi contiene almeno . Dunque . “” Supponiamo che non sia iniettivo: esistono allora due elementi diversi , di tali che . Allora . Dunque e . □
Proof. Proviamo solo la prima uguaglianza; la seconda è del tutto analoga. Per “”basta osservare che . “”Sia tale che . Allora . Dunque . Ponendo , otteniamo . □
Proof. Usiamo il criterio dei sottogruppi. Se e sono due qualsiasi elementi di , allora il prodotto del primo per l’inverso del secondo è (Corollario 4.30) e quindi appartiene ad . □
Definizione 6.25. Sia un gruppo e un suo elemento. Si dice sottogruppo ciclico generato da e si denota con il sottogruppo costituito dalle potenze di con esponenti interi. Diremo che è un gruppo ciclico se vi è un suo elemento tale che .
Attenzione: In notazione additiva, ossia se il gruppo è , scriveremo
Esempio 6.26. Il sottoinsieme dei multipli interi di è un sottogruppo ciclico di . Infatti in notazione additiva elevare a potenza -esima un elemento significa sommarlo con se stesso volte se e significa sommare con se stesso -volte il suo opposto se ; infine se la potenza con esponente è per definizione l’identità del gruppo, ossia nel nostro caso è . Quindi in notazione additiva la potenza -esima di si scrive e in questo caso è proprio il prodotto di per . Dunque i multipli di costituiscono il sottogruppo ciclico generato da nel gruppo con l’operazione di addizione. Notiamo che stesso è un gruppo ciclico perchè coincide col suo sottogruppo ciclico generato da .
Esempio 6.27. Nel gruppo delle permutazioni il sottogruppo ciclico generato dal ciclo contiene 3 elementi, ed esattamente . Infatti si può verificare che e quindi tutte le potenze con esponenti interi positivi coincidono con uno dei 3 elementi scritti. Inoltre da si deduce anche che e quindi anche le potenze di con esponenti negativi coincidono con una delle 3 potenze elencate.
Proposizione 6.28. Sia un -ciclo del gruppo simmetrico . Il sottogruppo ciclico generato da ha esattamente elementi:
Proof. Sia . Possiamo intanto osservare che e quindi, generalizzando il ragionamento fatto nell’esempio precedente, ogni potenza di coincide con una di quelle elencate. Inoltre tutte le potenze elencate sono diverse; infatti se abbiamo . Quindi . □
Esempio 6.29. Il gruppo contiene oltre ai sogruppi banali, ossia al sottogruppo nullo che contiene solo e il sottogruppo che coincide con tutto , anche tanti altri sottogruppi ciclici. Per ogni , il sottoinsieme di dei multipli interi di :
è un sottogruppo di . Nei prossimi capitoli vedremo che questi sono tutti i possibili sottogruppi di . Cosideriamo per ora un caso particolare. Il sottoinsieme è un sottogruppo di . Presi infatti due qualsiasi elementi e di , avremo . Mostriamo ora che coincide col sottogruppo ciclico . L’inclusione è evidente: tutti gli elementi di sono multipli di : . L’altra inclusione si ottiene osservando che e quindi per ogni si ha .
Consideriamo ora un elemento di un gruppo e le sue potenze. Se vi sono due esponenti diversi tali che , allora per la potenza con esponente la loro differenza si ha . In particolare supponendo , avremo una potenza di con esponente positivo che vale .
Definizione 6.30. Diremo che ha periodo infinito se tutte le potenze di sono tutte diverse. In caso contrario si dice periodo di il minimo intero positivo tale che .
In notazione additiva, ossia se , il periodo di è il minimo intero positivo tale che (oppure è infinito).
Esempio 6.31. Consideriamo il gruppo delle permutazioni di con l’usuale composizione. Componendo con sè stessa la permutazione otteniamo e Dunque il peiodo di è .
Lemma 6.32. L’identità di un gruppo è l’unico elemento con periodo . Il periodo di un elemento , , coincide con l’ordine del sottogruppo ciclico generato da , ossia:
Proof. Consideriamo l’omomorfismo definito da associando ad ogni la potenza . Se ha ordine finito allora è costituito dalle potenze di con esponenti da a . □
Corollario 6.33. Il periodo di un qualsiasi elemento di un gruppo finito di ordine è un divisore di .
Si dicono gruppi diedrali i gruppi di simmetrie di un dato poligono i Possiamo considerare ad esempio le simmetrie del triangolo isoscele, oppure quelle dell’esagono regolare o quelle di un rettangolo non quadrato e così via. Un modo semplice per individuare le simmetrie di un poligono è quello di etichettare i suoi vertici (ad esempio ordinatamente con i numeri da a ) e di considerare quindi la permutazione dei vertici corrispondente a ciascuna simmetria. È facile verificare che in questo modo le simmetrie di un triangolo rettangolo corrispondono all’intero gruppo . Invece per , e simmetrie di un poligono regolare con lati corrispondono ad un sottogruppo proprio di di cardinalità : ci sono vertici in cui ”spostare” il vertice etichettato con e per ciascuno ci sono due vertici, quelli a lui adiacenti, in cui spostare il vertice .
Sia un intero fissato, . Indichiamo con l’insieme dei multipli interi di , ossia . Possiamo associare a (o a ) la relazione di congruenza modulo in :
Se si dice che è congruo a modulo e si scrive . Un modo equivalente di esprimere la relazione di congruenza modulo è la seguente:
Infatti, se e , allora ; viceversa se e , anche la divisione di per , ossia , ha lo stesso resto . Tratteremo più a fondo la divisione con resto in uno dei prossimi capitoli. La relazione di congruenza modulo è una relazione di equivalenza in . Il quoziente si dice insieme delle classi di resto modulo (o delle classi di congruenza modulo ) e si indica abitualmente con .
Proof. La prima parte dell’asserto segue immediatamente dalla definizione di congruenza data inizialmente: se e solo se ossia se e solo se con . La seconda parte dell’asserto si ottiene ricordando che ogni classe di equivalenza è caratterizzata dal resto della divisione di per e che i resti possibili sono gli interi tali che . □
Possiamo definire in delle operazioni di somma e prodotto ponendo:
Lasciamo come esercizio al lettore la verifica che queste operazioni sono ben definite, ossia che il risultato non dipende dai rappresentanti. Le classi di resto con l’operazione di somma prima definita è un gruppo abeliano. L’identità à e l’opposto di una classe è la classe che ha come rappresentante l’opposto, ossia .
Esempio 6.35. Scriviamo esplicitamente le tabelline della somma nei casi e . Per semplicità nelle tabelline scriviamo solo i numeri che sono rappresentanti speciali delle classi, sottointendendo il simbolo che indica la classe.
Otteniamo due tabelline simmetriche rispetto alla diagonale principale poichè l’operazione è commutativa. Osserviamo anche che in ogni riga ed in ogni colonna compaiono tutti gli elementi, ma scritti ogni volta in un diverso ordine.
Il risultato delle operazioni e in non sempre è “intuitivo”.
Possiamo anche considerare con l’operazione di prodotto sui rappresentanti: . però non è un gruppo. Infatti è l’identità rispetto al prodotto, ma non ha l’inverso.
6.1 Consideriamo la funzione
definita come
.
Consideriamo
con l’operazione
.
La funzione
è un
omomorfismo di
in sè stesso? È anche un omomorfismo di monoidi?
Consideriamo
con l’operazione
.
La funzione
è un
omomorfismo di
in sè stesso? È anche un omomorfismo di monoidi?
6.2 Consideriamo l’insieme e l’usuale operazione prodotto . è un semigruppo? È anche un monoide?
6.3 Consideriamo i monoidi e e la funzione ,
è un omomorfismo di monoidi?
6.4 Consideriamo la funzione definita come . Consideriamo con l’operazione e con l’operazione . La funzione è un omomorfismo?
6.5 Sia un insieme e sia il monoide libero delle parole su . Definiamo la funzione lunghezza di una parola:
Se consideriamo con l’operazione , è un omomorfismo di monoidi?
6.6 Si consideri la struttura algebrica , dove l’operazione è definita come segue:
6.7 Sia il gruppo delle permutazioni di con l’usuale composizione. Scrivere tutti gli elementi del gruppo ciclico generato da .
6.8 Nel gruppo delle permutazioni di con l’usuale composizione, determinare il peiodo di e di .
6.9 Sia un gruppo abeliano e siano .
6.10 Sia un gruppo e siano .
6.11 Si consideri in l’operazione definita da .
6.12 Si consideri in l’operazione definita da . È vero che è un gruppo?
6.13 Si consideri in l’operazione definita da .
6.14 Sia dotato dell’usuale operazione di prodotto. Verificare che è un gruppo.
6.15 Sia . Dimostrare che è un sottogruppo di . È vero che è un sottogruppo del gruppo moltiplicativo ?
6.16 Il gruppo prodotto Siano e due gruppi. Provare che l’operazione nell’insieme prodotto cartesiano definita da rende un gruppo. Se non diversamente specificato, il prodotto cartesiano di due gruppi viene sempre considerato dotato di questa struttura di gruppo e viene chiamato gruppo prodotto. Verificare che le funzioni di proiezione , dal prodotto cartesiano su uno dei fattori, nel caso di un gruppo prodotto sono degli epimorfismo di gruppi.
6.17 Consideriamo i gruppi additivi , e e sia definita da .
6.18 Si consideri in l’operazione definita da .
6.19 Consideriiamo i gruppi additivi e . Indichiamo con la classe di un numero intero in e con la sua classe in .
6.20 Consideriiamo i gruppi additivi e . Indichiamo con la classe di un numero intero in e con la sua classe in .
6.21 Sia il gruppo delle permutazioni di 3 elementi e sia definito da .
Definizione 7.1. Si dice anello un insieme dotato di due operazioni, usualmente denotate con e e dette somma e prodotto, che soddisfano le seguenti proprietà :
Inoltre l’anello si dice commutativo con identità se soddisfa anche le due ulteriori condizioni:
Esempio 7.2. L’insieme dei numeri interi dotato delle operazioni e è un anello commutativo con identitè , con e .
Esempio 7.3. L’insieme delle classi di resto modulo (Capitolo 9) dotato delle operazioni e è un anello commutativo con identità . In particolare:
Molte proprietà dei numeri interi che usiamo abitualmente non sono caratteristiche dei numeri interi, ma dipendono soltanto dalla struttura di anello, ossia valgono per tutti gli anelli (oppure per tutti gli anelli commutativi con identità ), incluso ad esempio . L’enunciato seguente presenta alcune proprietà di questo tipo; alcune altre sono inserite tra gli esercizi.
Lemma 7.4. Sia un anello. Allora:
Se inoltre è un anello commutativo con identità , allora:
Proof. Le proprietà i), ii), iii) derivano dal fatto che è un gruppo. iv) Sia un qualsiasi elemento di . Si hanno le uguaglianze: . Sommando ai due membri estremi dell’uguaglianza l’opposto di troviamo da un lato e dall’altro . Allora , come volevasi. v) L’unicità dell’identità moltiplicativa si prova in modo del tutto analogo a quello seguito per l’identità additiva. vi) Basta provare che soddisfa la definizione di l’opposto di , ossia che sommato con lui dà :
□
Definizione 7.5. Siano e due anelli. Nel prodotto cartesiano si possono introdurre due operazioni di somma e prodotto ponendo
Si verifica che con tali operazioni componente per componente, il prodotto cartesiano è un anello, detto anello prodotto di e . Se inoltre e sono anelli commutativi con identità , anche lo ‘e . Se infine esistono le identità e , allora anche l’anello prodotto ha identità .
In questa sezione consideriamo sempre un anello commutativo con identità . Spesso sottointenderemo il simbolo del prodotto, ossia scriveremo invece di , e useremo la notazione abbreviata al posto di .
Definizione 7.6. Si dice che è un dominio di integrità o semplicemente un dominio se in vale la legge di annullamento del prodotto ossia se
Lemma 7.7. Se è un dominio di integrità, allora in vale la legge di cancellazione per il prodotto ossia , se allora .
Proof. Sommando ai due membri di l’opposto di si ottiene ossia . poichè vale la legge di annullamento del prodotto e , allora ossia (sommando ai due membri) . □
Concretamente gli zero-divisori sono quegli elementi per cui non vale la legge di cancellazione del prodotto. Un anello commutativo con identità è un dominio se e solo se l’unico zero-divisore è .
Esempio 7.9. In l’unico elemento per cui non vale la legge di cancellazione è e quindi è un dominio di integrità.
Esempio 7.10. In , l’anello delle classi di resto modulo 6 si ha , anche se e . Quindi non è un dominio di integrit‘a.
Esempio 7.11. L’anello prodotto non è un dominio di integrit‘a. Infatti e , ma il loro prodotto è nullo:
Definizione 7.12. Un elemento si dice unità o anche elemento invertibile di se esiste in un suo inverso rispetto al prodotto, ossia un elemento tale che . Di solito l’inverso di un elemento (che, se esiste, è sempre unico) si indica con . Due elementi di si dicono associati l’uno all’altro se esiste una unità tale che (e quindi ).
Esempio 7.13. In gli unici elementi invertibili sono e . Due elementi sono allora associati se sono uguali oppure sono opposti.
Esempio 7.14. In gli unici elementi invertibili sono e . Quindi in , e sono associati se oppure se .
Esempio 7.15. Nell’anello prodotto sono invertibili tutti gli elementi tali che e , mentre non lo sono tutti gli altri, ossia quelli in cui compare al primo e/o al secondo posto.
Esempio 7.16. Le seguenti sono le tabelline del prodotto in e in :
Escludendo da otteniamo un gruppo col prodotto. Infatti i due elementi diversi da sono inversi di se stessi. Invece, nel caso non otteniamo un gruppo neanche escludendo , ossia neppure gà un gruppo. Infatti anche non ha l’inverso.
Definizione 7.17. Si dice che un anello commutativo con identità è un campo se ogni elemento non nullo di è una unità.
Esempio 7.18. L’anello è un campo. Anche nell’anello , tutti gli elementi tranne sono invertibili, quindi anche è un campo. Invece non è un campo.
Definizione 7.19. Siano e due anelli. Una funzione si dice omomorfismo di anelli se
Se inoltre e hanno identità , si richiede che valga anche: .
Definizione 7.20. Un omomorfismo di anelli si dice:
Possiamo caratterizzare la suriettività e l’iniettività di un omomorfismo di anelli mediante l’immagine e il nucleo, esattamente come abbiamo visto nel caso degli omomorfismi di gruppi.
Le definizioni date di nucleo e di immagine si riferiscono semlicemente alla struttura additiva degli anelli e . Ricordando che ogni omomorfismo di anelli è anche, per definizione, un omomorfismo di gruppi additivi, otteniamo il risultato seguente:
Proposizione 7.22. Sia un omomorfismo di anelli. Allora
Consideriamo il prodotto cartesiano dell’insieme dei numeri naturali per sè ed in esso la relazione:
Si può facilmente verificare che è una relazione di equivalenza. Osserviamo che sono in relazione con la coppia tutte e sole le coppie del tipo . Inoltre, in ogni altra classe di equivalenza vi è una (e soltanto una) coppia in cui uno dei due elementi è lo . Se infatti , ossia se , allora e, analogamente, se , ossia se , allora .
Definizione 7.23. Si dice insieme dei numeri interi relativi l’insieme quoziente . Ogni classe di equivalenza si dice numero intero relativo. La classe di si dice zero di e si indica con ; la classe di (dove ) si indica con o semplicemente con e si dice numero intero positivo, la classe di (dove ) si indica con e si dice numero intero negativo.
Possiamo definire le operazioni somma e prodotto in a partire dalle operazioni di , nel modo seguente:
e
Possiamo inoltre definire in un ordine totale nel modo seguente:
Lasciamo per esercizio al lettore la verifica che queste operazioni sono ben poste (ossia che il risultato non dipende dai rappresentanti) e la dimostrazione del seguente risultato.
Proposizione 7.24. L’applicazione data da è iniettiva e rispetta le operazioni e l’ordinamento ossia:
Mediante ossiamo identificare i numeri naturali con i numeri interi positivi e considerare come un sottoinsieme di .
7.1 Siano e due anelli (oppure anelli commutativi con identità ). Verificare che le operazioni definite componente per componente nel prodotto soddisfano le proprietà di anello (rispettivamente: di anello commutativo con identità ). 7.2 Si consideri l’anello con la somma e il prodotto usuali
Stabilire quali sono gli elementi invertibili di .
Determinare gli eventuali zero-divisori di .
è vero che è un dominio? È vero che è un campo?
7.3 Si consideri l’anello con la somma e il prodotto usuali
Stabilire quali sono gli elementi invertibili di .
Determinare gli eventuali zero-divisori.
È vero che è un dominio? È vero che è un campo?
7.4 Si consideri l’anello con le operazioni usuali e l’anello prodotto .
Stabilire se la funzione data da è un omomorfismo di anelli.
La funzione è iniettiva? È suriettiva?
7.5 Si considerino gli anelli e con le operazioni usuali e l’anello prodotto .
Provare che la funzione data da è un omomorfismo di anelli.
Determinare nucleo e immagine di .
è un monomorfismo di anelli? È un epimorfismo di anelli?
7.6 Stablire se la funzione data da è un omomorfismo di anelli. È anche un omorfismo di anelli commutativi con identità ?
7.7 Stablire se la funzione data da è un omomorfismo di anelli.
7.8 Determinare il nucleo e l’immagine dell’omomorfismo data da .
7.9 Determinare il nucleo e l’immagine dell’applicazione data da .
7.10 Sia un anello commutativo con identità . Provare che l’inverso di un elemento , se esiste, è unico.
7.11 Sia un anello commutativo con identità e siano e elementi invertibiie di .
Provare che è cancellabile ossia che : .
Provare che è invertibile.
Provare per induzione che è invertibile , per ogni .
7.12 Sia un anello commutativo con identità . Provare l’equivalenza:
è uno zero-divisore non è cancellabile.
7.13 Sia un anello commutativo con identità . Provare per ogni le seguenti relazioni (tra le quali la regoletta del “ ”):
, , , ,
, ,
se è un intero pari e se è un intero dispari.
L’anello degli interi
In questo capitolo approfondiamo lo studio dell’anello . In particolare ci concentreremo sull’algoritmo di divisione in e le sue applicazioni. Le proprietà di cui ci occuperemo riguardano la possibilità di dividere un elemento per un altro. Iniziamo introducendo alcune definizioni generali sugli anelli che riguardano appunto i fattori di un elemento.
Definizione 8.1. Siano elementi di . Si dice che divide se esiste tale che . In simboli “ divide ” si scrive e “ non divide ” si scrive .
Definizione 8.2. Sia un anello commutativo con identità . Un elemento , che non è invertibile e che non è , si dice
riducibile in se può essere scritto come un prodotto , , in cui nè nè sono invertibili;
irriducibile se e non è riducibile, ossia se non si può decomporre in un prodotto tranne che nel prodotto di una unità per un elemento associato ad ;
primo in se ogni volta che divide un prodotto allora divide uno dei due fattori. In simboli: oppure .
NOTA BENE Si faccia attenzione al fatto che e gli elementi invertibili di non sono mai, per definizione, nè riducibili, nè irriducibili, nè primi.
Esempio 8.3. In il numero è un elemento irriducibile poichè non può essere scritto come prodotto, a meno di non usare i fattori , , e che sono rispettivamente unità di oppure associati a in . Il numero è anche primo in perchè un prodotto è pari soltanto quando almeno uno dei due fattori è pari (ossia è primo perchè oppure ). Invece e e non sono nè riducibili, nè irriducibili, nè primi.
Esempio 8.4. Si consideri in l’elemento . è primo in : infatti, se divide , allora è pari o altrimenti è pari. Tuttavia, non è irriducibile in : è sufficiente osservare che , è nè nè sono invertibili in (si veda la tabella della moltiplicazione di nel Capitolo 9).
Osservazione 8.5. Nelle scuole elementari e medie spesso si dice che un numero è primo se non è decomponibile in un prodotto, confondendo quindi primo con irriducibile. Questa confusione non porta ad errori poichè l’insieme degli elementi irriducibili di coincide con l’insieme degli elementi primi di ossia, relativamente a , queste due nozioni risultano essere equivalenti. Questa proprietà è parte del Teorema fondamentale dell’aritmetica ed è un fatto tutt’altro che ovvio o banale. Inoltre le due nozioni non sono per nulla equivalenti in generale.
Definizione 8.6. Un dominio si dice dominio fattoriale o dominio a fattorizzazione unica (in breve U.F.D., dall’inglese Unique Factorization Domain) se ogni elemento non nullo e non invertibile si decompone in modo unico (a meno dell’ordine e di fattori moltiplicativi invertibili) nel prodotto di elementi irriducibili.
La divisione con resto oggetto di questo paragrafo è semplicemente il primo tipo di divisione che si impara alle elementari (prima dell’introduzione delle frazioni), ma è anche un importantissimo strumento di calcolo e di dimostrazione per le proprietà dell’anello .
Teorema 8.7. Per ogni coppia di numeri interi, con , esistono e sono univocamente determinati i numeri interi (quoziente) ed (resto), tali che con .
Proof. Per prima cosa dimostriamo che degli interi ed siffatti esistono e poi proveremo che sono univocamente determinati. Osserviamo intanto che è sufficiente provare l’asserto nel caso e . Se infatti e si ha allora ; analogamente se , e si ha allora con (oppure se ). Siano, allora, e . Procediamo per induzione su . Se , basta prendere . Supponiamo l’asserto vero per tutti gli interi e proviamolo per . Se , è sufficiente prendere ed . Se , l’asserto è vero per i numeri e , ossia esistono e tali che e . Allora e soddisfano le condizioni volute. Proviamo ora l’unicità di ed . Supponiamo che valgano le relazioni e con . Sottraendo membro a membro si ottiene ossia . Essendo , allora e quindi anche deve essere nullo. □
Definizione 8.8. Siano un numero intero detto base e un insieme di simboli detti cifre associati ai numeri compresi tra e . Si dice scrittura posizionale di numero intero positivo una sequenza ordinata tale che ed .
La scrittura posizionale di un numero negativo si ottiene premettendo il segno alla scrittura posizionale di .
Corollario 8.9. Fissata una base e un insieme di cifre , ogni numero intero positivo possiede una e una sola scrittura posizionale e ogni seuquenza del tipo con è la scrittura posizionale di un numero intero.
Proof. Per provare che una tale scrittura esiste (ed anche per calcolarla) procediamo per induzione su . Se , allora , con . Sia allora e supponiamo l’asserto vero per tutti in numeri minori di . Eseguiamo la divisione di per : , con . Per l’ipotesi induttiva, l’asserto è vero per il quoziente . Se , la scrittura di si ottiene ponendo , e . Per i numeri negativi si usa la scrittura posizionale dell’opposto preceduta dal segno . □
Esempio 8.10. Introduciamo le nuove cifre per il numero e per oltre alle cifre abituali. La notazione in base del numero (che in base si scrive) è poichè . Per calcolarla a partire da si eseguono le divisioni: con resto
con resto
con resto .
Nel seguito di questo paragrafo e nel prossimo ci occuperemo dei divisori di un numero intero e supporremo sempre di lavorare con numeri positivi e con fattori positivi. Tutte le proprietà dimostrate, però, valgono per tutti i numeri interi, anche per i negativi, poichè ogni numero intero è associato ad un numero positivo, cioè differisce da un positivo per un fattore moltiplicativo invertibile o .
Definizione 8.11. Si dice massimo comun divisore di due interi e non entrambi nulli il numero intero positivo tale che , e t.c. e si ha .
Il quindi è il più grande divisore comune ad e , non solo rispetto alla relazione d’ordine totale , ma anche rispetto alla divisibilità.
Esempio 8.12. Non ha senso definire il poichè l’insieme dei divisori di coincide con e quindi non ha massimo. Invece, se , , allora .
L’aver richiesto che il sia un numero positivo fa sì che, se esiste (cosa non ovvia ma che proveremo essere vera), allora è unico. Per provare che il massimo comun divisore esiste useremo il seguente lemma.
Proof. Sia . Ogni divisore comune a e divide anche ; d’altra parte si ha anche e quindi ogni divisore comune ad e divide anche . □
Teorema 8.14. (Identità di Bé zout) Siano due interi non entrambi nulli. Allora esistono dei numeri interi opportuni (ma non unici!) tali che
Grazie al Lemma 8.13 possiamo calcolare il massimo comun divisore e i numeri interi che compaiono nell’identità di Bé zout, col metodo noto come algoritmo euclideo o algoritmo delle divisioni successive. Per calcolare il massimo comun divisore di due numeri , con si procede nel modo seguente:
dove è il resto della divisione di per , è il resto della divisione di per e è il resto della divisione di per . Questo procedimento ha al più passi (poichè ) e si ferma non appena si trova un resto nullo. Il è l’ultimo resto non nullo trovato. Procedendo a ritroso da ed utilizzando le relazione trovate ad ogni divisione , si ricava l’identitàdi Bé zout.
Esempio 8.16. Procedimento per calcolare :
Allora . Procedimento per calcolare l’identitàdi Bé zout:
Proof. Siano e l’identitàdi Bé zout. Se , ogni divisore comune ad e divide anche ; in particolare . Viceversa, se , allora , dove si ponga , . □
Le equazioni del tipo con nelle incognite di cui si cercano suluzioni in si dicono equazioni Diofanteee lineari in due incognite. Osseriviamo infine che il minimo comune multiplo di due numeri si ottiene facilmente a partire dal loro massimo comun divisore come: e quindi può essere, anch’esso, calcolato mediante l’algoritmo euclideo.
John McLane è un poliziotto statunitense. Sta inseguendo un pazzo che lascia bombe in giro per New York. Di fianco ad una fontana trova una valigetta e due taniche da 3 e 5 galloni rispettivamente. Nella valigetta c’é una bomba controllata da una bilancia. Per disinnescare la bomba John deve appoggiare sopra la bilancia una tanica con esattamente 4 galloni d’acqua. Ha un minuto di tempo prima che la bomba esploda quindi per misurare i 4 galloni può usare solo le due taniche che ha a portata di mano. Come fa? (Indovinello tratto dal film “Die hard- Duri a morire”) SOLUZIONE: dobbiamo cercare le soluzioni all’equazione diofantea
| (1) |
Infatti, abbiamo a disposizione due contenitori della capacità di 3 e 5 galloni rispettivamente, con i quali dobbiamo ottenere (versando acqua in un contenitore o svuotandola da uno all’altro) esattamente 4 galloni. Cerchiamo soluzioni intere per e perchè i contenitori non sono graduati: cercare di riempire uno dei due contenitori “a metà “, rischieremmo di far esplodere la bomba a causa di un’imprecisione! Le uniche mosse che ci garantiscono precisione, sono quelle di riempire completamente un contenitore (+1) o svuotarlo completamente (-1). Posso travasare acqua da un recipiente all’altro, ma per essere “precisi”, posso travasare completamente un contenitore pieno nell’altro. Questo non “influisce”sulle variabili dell’equazione. L’equazione (1) ha soluzione se e solo se (Corollario 8.17). In effetti , quindi l’equazione (1) ha soluzione! Per trovarla (con certezza!), calcoliamo con l’algoritmo euclideo per poi esplicitare l’identit‘a di Bézout:
Da queste equazioni troviamo tali che :
Quindi , . Una soluzione (non è l’unica!!!!) dell’equazione (1) è . In pratica: John McLane deve riempire alla fontana la tanica da 3 galloni per 8 volte. Ogni volta che lo riempie, la svuota in quello da 5. Di volta in volta, il recipiente da 5 galloni si riempirà fino all’orlo, e John dovrà svuotarlo per 4 volte. Alla fine di questo procedimento, nella tanica da 5 galloni ci saranno esattamente 4 galloni di acqua! Non è l’unica soluzione!!!!! John può anche riempire 3 volte il recipiente da 3, travasare man mano in quello da 5 e poi svuotare quello da 5 solo 1 volta: .
In questo paragrafo proveremo che ogni numero intero, non nullo e non invertibile, si fattorizza in modo essenzialmente unico (ossia a meno di permutazioni dei fattori e di cambiamenti di segno) nel prodotto di numeri primi. Ci sarà utile la seguente
Definizione 8.18. Sia un elemento di un anello commutativo con identità. Due fattorizzazioni e sono essenzialmente la stessa fattorizzazione di se e per ogni si ha , dove le sono unità di e è una opportuna permutazione degli indici. In altre parole due fattorizzazioni sono essenzialmente la stessa se differiscono solo per l’ordine dei fattori e per eventuali fattori moltiplicativi invertibili.
Lemma 8.19. Sia un numero intero . Allora può essere scritto come prodotto di numeri interi irriducibili .
Proof. Senza perdere in generalità, possiamo supporre e considerare solo fattori . Procediamo per induzione su . Se , allora è irriducibile, , e non c’è nulla da provare. Supponiamo l’asserto vero per tutti gli interi , e proviamo che vale anche per . Se è irriducibile, come prima , . Se invece si può scrivere come prodotto , con non invertibili, allora i fattori sono tali che e quindi grazie all’ipotesi induttiva possiamo scrivere , e quindi , . □
Proof. “” Supponiamo che sia primo. Se con , allora e quindi, essendo primo, deve dividere almeno uno dei fattori. Se , allora , da cui, per la cancellazione, . Questa uguaglianza dice che è una unità di e quindi che non ha decomposizioni effettive in un prodotto, cioè è irriducibile. “” Sia un numero irriducibile e siano interi tali che e . Proviamo che allora . Dalle ipotesi fatte segue che ; possiamo allora scrivere l’identitàdi Bézout (Teorema 8.14). Moltiplicando i due membri per e ricordando che ossia che esiste tale che , troviamo: e quindi . □
Teorema 8.21. (Teorema fondamentale dell’aritmetica) è un dominio a fattorizzazione unica ossia ogni numero intero si fattorizza in modo essenzialmente unico nel prodotto di numeri primi.
Proof. I risultati precedenti mostrano che ogni numero intero ( ) si fattorizza nel prodotto di irriducibili e che gli irriducibili in sono anche primi. Allora si fattorizza nel prodotto di numeri primi. Rimane da provare che la fattorizzazione è essenzialmente unica. Supponiamo che tutti i fattori siano positivi (sostituendo eventualmente i negativi con i loro opposti). Sia , con fattori e tutti primi. Procediamo per induzione su . Se , allora è irriducibile e quindi anche e . Supponiamo che la scrittura sia unica per i prodotti di fattori irriducibili e proviamolo per i prodotti di fattori irriducibili. poichè è primo e divide , allora divide uno dei : possiamo supporre di riordinare i in modo che . Ma anche è irriducibile e quindi . Allora si ha . Mediante la cancellazione otteniamo , che è un prodotto di fattori irriducibili. Dall’ipotesi induttiva segue che (ossia ) e che, a meno dell’ordine, le due fattorizzazioni coincidono, ossia , , . Avendo già provato che , abbiamo dimostrato per intero l’unicità della fattorizzazione di . □
Un modo conveniente per scrivere la fattorizzazione di un intero nel prodotto di fattori primi è quello di raccogliere mediante esponenti i fattori uguali, ottenendo scritture del tipo , dove i sono primi distinti. L’esponente si dice molteplicità di in .
Proof. Supponiamo per assurdo che esistano solo un numero finito di primi . L’intero non è divisibile esattamente per alcun e quindi non è divisibile per alcun primo. Troviamo cosè un numero privo di fattori primi, in contrasto con quanto provato. □
Si noti che la precedente è una vera dimostrazione per assurdo e non, come si potrebbe pensare, un metodo per costruire un ulteriore numero primo a partire da primi assegnati. Ad esempio il numero non è primo, ma si decompone nel prodotto di e .
8.1 Calcolare MCD di 18779 e 4183 usando l’algoritmo euclideo.
8.2 Scrivere l’identità di Bézout per i numeri 45 e 51.
8.3 Calcolare il MCD e l’identità di Bézout dei numeri e .
8.4 Determinare la scrittura posizionale in base , e del numero (che nella abituale base si scrive) .
8.5 Scrivere nella abituale base i numeri , , , dove l’indice indica la base usata.
8.6 Si consideri il numero , scritto in base 16, e si riscriva lo stesso numero in base .
8.7 Consideriamo , e adottiamo la notazione . Si consideri il numero , scritto in base 16, e si riscriva lo stesso numero in base .
8.8 Consideriamo , e adottiamo la notazione . Si consideri il numero , scritto in base 16, e si riscriva lo stesso numero in base .
8.9 Si scriva il numero intero in base .
8.10 Trovare il MCD di e di ed esplicitare l’identità di Bézout.
8.11 Trovare il MCD di e di ed esplicitare l’identità di Bézout. Calcolare inoltre .
8.12
8.13 Determinare un numero tale che , dove .
8.14 Trovare il MCD e il mcm di e , e quindi determinare un numero tale che , dove .
8.15 I produttori della serie di film Die Hard vogliono girare un ultimo film della serie, in cui l’eroe John
McLane muore a causa dell’indovinello delle taniche: gli vengono fornite una tanica di capacità
galloni e una di
capacità
galloni, e deve
ottenere esattamente
galloni, solo riempiendo completamente e svuotando completamente le taniche, altrimenti scoppierà una
bomba.
Quali tra le seguenti coppie di interi
porta di sicuro alla morte John McLane?
8.16 Determinare il MCD di , e .
8.17 Sia un numero primo. Provare che per ogni si ha oppure .
8.18 Dire se le seguenti equazioni hanno soluzioni intere:
Gli anelli delle classi di resto
Il risultato seguente caratterizza le unità e gli zero-divisori degli anelli .
Proof. 1)
è una unità in
tale che
in
tale che
tali che
(cfr. Lemma 8.17)
.
2)
è zero-divisore in
,
,
tale che
in
,
,
tale che
.
□
Ricordiamo ora la definizione di campo e una proprietà valida per ogni anello commutativo con identità : Si dice che un anello commutativo con identità è un campo se ogni elemento non nullo di è una unità .
Lemma 9.2. Sia un anello commutativo con identità .
Proof. Proviamo che se è invertibile e si ha , allora necessariamente . Moltiplichiamo i due membri di per ; si ottiene ossia , come volevasi. La seconda affermazione si ottiene subito dalla prima ricordando le definizioni di campo e di dominio. □
Proof. “ è un campo è un dominio” è un caso particolare del lemma precedente. Per provare “ è un dominio è un numero primo” basta ricordare che se non è primo, allora è riducibile e osservare che i fattori di una sua fattorizzazione corrispondono a classi e non nulle in ma tali che ossia a zero-divisori propri. Infine “ è un numero primo è un campo” si ottiene ricordando che ogni classe in è del tipo con ; se è primo, allora per ogni classe non nulla, ossia tale che , si ha e quindi è invertibile in (Proposizione 9.1). □
Esempio 9.4. In è invertibile poichè . Per determinarne l’inverso, calcoliamo (mediante l’algoritmo euclideo) l’identità di Bézout . In si ha allora e quindi . Notiamo che i coefficienti dell’identità di Bézout non sono unicamente determinati; ad esempio si ha anche ; questo non contrasta con l’unicitè dell’inverso poichè in si ha . In è uno zero-divisore, poichè . Si ha infatti , con , avendo ottenuto dalla divisione .
Definizione 9.5. Una congruenza lineare è una equazione in del tipo , con . Sono soluzioni della congruenza tutti i numeri interi tali che è multiplo di .
Risulta evidente dalla definizione che se è soluzione della congruenza , anche lo è, per ogni . Risolvere la congruenza equivale a risolvere in l’equazione lineare in una variabile , oppure a risolvere in l’equazione lineare in due variabili . Quest’ultimo modo di interpretare una congruenza lineare ci fornisce immediatamente il criterio per sapere se ammette soluzioni e, in caso affermativo, il metodo per calcolare le soluzioni stesse.
Proof. L’asserto segue immediatamente dal Corollario 8.17. □
Metodo risolutivo per le congruenze lineari. Se una congruenza lineare soddisfa la condizione , possiamo dividere i coefficienti per il ottenendo una congruenza equivalente alla precedente (ossia con le stesse soluzioni) e tale che . Possiamo allora supporre . Risolviamo in l’equazione lineare moltiplicando i due membri per l’inverso di ( esiste poichè e può essere calcolato mediante l’algoritmo euclideo). In vi è l’unica soluzione . L’insieme delle soluzioni della congruenza è costituito da tutti i numeri tali che ed è quindi .
Osservazione 9.7. Se , l’insieme delle soluzioni di è l’insieme , dove è una qualsiasi soluzione della congruenza. Per determinare tutte le soluzioni è quindi sufficiente conoscerne una qualsiasi.
Osservazione 9.8. Se , la congruenza è risolubile e il suo insieme delle soluzioni si può esprimere mediante una nuova congruenza con coefficiente direttivo ossia del tipo , dove è una qualsiasi soluzione della congruenza e .
Definizione 9.9. Si chiama funzione di Eulero l’applicazione data da , ossia è il numero di interi tra e coprimi con .
La funzione di Eulero di un numero coincide col numero di classi invertibili in . Ad esempio, se è un numero primo, , poichè tutte le classi non nulle in sono invertibili. più in generale, se è la potenza di un numero primo , poichè in sono invertibili tutte le classi tranne le classi i cui rappresentanti compresi tra e sono i multipli di , ossia , , , , . Vediamo ora un metodo per calcolare il valore di per ogni intero a partire dalla fattorizzazione di in fattori primi , con primi tutti distinti.
Proof. La dimostrazione si articola in alcuni punti della cui prova diamo solo una breve traccia. Sia un numero primo.
Esempio 9.12. Consideriamo i due numeri e che sono coprimi. poichè è primo, si ha . Verifichiamo il Teorema di Eulero in questo caso particolare mediante calcoli diretti:
Esempio 9.13. Vogliamo calcolare la cifra
che indica le unità del numero
scritta in forma posizionale. Anche un computer incontra grosse difficoltà ad eseguire
questo calcolo e in ogni caso fornisce soltanto una approssimazione del risultato data
dalle prime cifre a sinistra del numero accompagnate da una opportuna potenza di
,
non certo l’ultima cifra a destra. Eseguiamo in altro modo questo calcolo facendo
ricorso al Teorema di Eulero. Osserviamo che calcolare la cifra delle unità equivale a
calcolare il resto della divisione per
ossia il numero
compreso tra
e
tale che
in
.
Intanto
quindi in
si ha
.
Ora, per il teorema di Eulero con
,
e
vale la relazione
.
Quindi
.
La cifra finale di
è quindi
.
Esempio 9.14. Vogliamo trovare le ultime due cifre decimali (ossia decine e unità) di . Le ultime due cifre decimali corrispondono al resto della divisione per . Come nell’esempio precedente usiamo il Teorema di Eulero:
Ora dunque . Inoltre e quindi
Il Teorema di Eulero è alla base di un metodo crittografico particolarmente ingegnoso che risolve il problema della segretezza nello scambio delle “chiavi” tra il mittente e il destinatario.
(da 10 lezioni di matematica di G. Ferrarese, M. Roggero, G. Tamone, Aracne ed.)
La crittografia, dal greco
= nascosto e
= scrivere, è lo studio dei metodi per garantire la segretezza del contenuto di un
messaggio anche nel caso sia intercettato. Un metodo crittografico ideale dovrebbe
permettere al mittente di crittografare con molta facilità i messaggi e dovrebbe inoltre
assicurare che solo il destinatario designato possa decifrarli con facilit‘a. Nata come
raccolta di tecniche e di sistemi per assicurare la riservatezza di messaggi tra regnanti,
imperatori, amanti, etc, la crittografia è maturata definitivamente a rango di scienza solo
nei primi del 1900 con l’avvento di nuove teorie e tecniche matematiche. Attualmente è
entrata a far parte della nostra vita quotidiana, poichè ne fanno uso tessere Bancomat,
telefoni cellulari, trasmissioni televisive, internet e in genere ogni strumento di
comunicazione elettronica.
Le sue origini sono antichissime; basti pensare che più di 6000 anni fa si
scrivevano
geroglifici egizi in modo non standard e ancora oggi si lavora per la loro interpretazione e
che nella Bibbia si trova un esempio di crittografia mediante sostituzione di ogni lettera
dell’alfabeto con la lettera che occupa la stessa posizione nell’ alfabeto scritto al contrario.
I metodi crittografici a chiave pubblica non richiedono lo scambio di comunicazioni
riservate in alcun momento tra mittente e destinatario. Nel seguito tutte le comunicazioni
tra i due soggetti si intenderanno come disponibili a chiunque; ad esempio possono
avvenire mediante pubblicazione su un giornale oppure su un sito internet completamente
accessibile. La prima metodologia crittografica di questo genere fu sviluppata nel
1978 da tre ricercatori: Ronald Rivest, Adi Shamir e Leonard Adleman; essi
realizzarono una procedura che, dalle loro iniziali, prende il nome di “RSA”.
L’idea di base del codice RSA è la constatazione , di quanto sia facile moltiplicare
tra
loro due numeri dati e di quanto sia invece difficile (o meglio calcolativamente lungo)
risalire ai fattori dato il prodotto. In teoria chiunque può decifrare un messaggio
crittografato mediante il codice RSA, ma il tempo richiesto per la decifrazione è tanto da
rendere il messaggio ormai privo di interesse. Il diretto destinatario possiede invece un
metodo di decifratura molto veloce. Vediamo come questa “doppia velocità ” possa
essere praticamente realizzata.
Ci si accorda (pubblicamente!) su come trasformare i messaggi in sequenze di numeri
ciascuno di lunghezza
prefissata: sia
uno di questi numeri. Il destinatario del messaggio prepara la chiave di decifrazione nel
modo seguente:
Qualunque sia il numero che ottiene come rappresentante della classe , egli può infine ricavare come resto della divisione di per ; infatti (essendo positivo e minore di ) è proprio il resto della divisione per di ogni numero congruo a modulo .
Come si può vedere nell’ultimo passaggio la validità del Teorema di Eulero sta alla base di questa procedura. Infatti è grazie a tale risultato che possiamo affermare che . A titolo di curiosità diciamo che i primi attualmente adoperati per l’RSA hanno un numero di cifre dell’ordine delle centinaia e che il metodo viene considerato del tutto sicuro. In un esperimento del 1994 per rompere una chiave RSA di 129 cifre, (ossia per fattorizzare un numero di 129 cifre), sono stati necessari 8 mesi di lavoro coordinato effettuato da 600 gruppi di ricerca sparsi in 25 paesi, che hanno messo a disposizione 1600 computers, facendoli lavorare in parallelo collegati tra loro attraverso Internet!
Esempio 9.15. Eseguiamo una simulazione di codifica e decodifica di un messaggio mediante RSA. Il destinatario del messaggio, chiamiamola Francesca, ha scelto i due primi e e li ha moltiplicati ottenendo . Perchè questa simulazione con numeri così piccoli abbia senso dobbiamo fingere che nessuno (a parte Francesca) sia in grado di calcolare in tempi brevi la fattorizzazione di . Francesca ha calcolato , ha scelto coprimo con e ha determinato (mediante l’algoritmo euclideo) un numero tale che , ottenendo (poichè ). Francesca comunica poi pubblicamente, a tutti coloro che vogliono scriverle in modo riservato, i due numeri e . Paolo vuole mandarle il messaggio : calcola: , lo divide per e ottiene il resto che spedisce a Francesca. Nessuno è in grado di decodificare il messaggio tranne Francesca che possiede la chiave di decifrazione . Francesca calcola allora e quindi divide per ottenendo il resto che è il messaggio “in chiaro”. Si noti che Francesca non deve necessariamente calcolare per intero la potenza prima di eseguire la divisione per , ma può lavorare nelle classi di resto nel modo seguente:
.
9.1 Determinare l’unico numero compreso tra e che stia nella classe di resto modulo di e poi di .
9.2 Come si fa ad ottenere esattamente 3 litri di acqua usando un recipiente da litri e un altro da litri?
9.3 Eseguire in i calcoli: .
9.4 Scrivere la tabellina del in ossia: , , …. Quanto fa ?
9.5 Scrivere la lista delle potenze di in ossia: , , …. Quanto fa ?
9.6 Provare che in in tutte le classi tranne sono invertibili determinando esplicitamente gli inversi.
9.7 Risolvere le seguenti equazioni in
mediante sostituzione diretta di ciascun elemento di
:
9.8 Se in , cosa possiamo dire di ?
9.9 Risolvere mediante sostituzione diretta l’equazione in :
9.10 Calcolare
9.11 Trovare la cifra finale di e .
9.12 Calcolare le ultime due cifre di e .
9.13 Fino dalle elementari si imparano alcuni espedienti pratici per riconoscere velocemente se un numero è divisibile per , , , e . Ottenere in modo rigoroso questi criteri operando sulle classi di resto in modo analogo a quanto fatto per la prova del . Perchè non si imparano anche criteri per la divisibilità per o per ?
9.14 Verificare se la relazione tra i punti del piano per cui due punti sono in relazione se e solo se hanno la stessa distanza dall’origine è una relazione di equivalenza.
9.15 Verificare se la relazione tra le rette del piano per cui due rette sono in relazione se e solo se sono parallele è una relazione di equivalenza.
9.16 Verificare se la relazione tra triangoli del piano per cui due triangoli sono in relazione se e solo se sono simili è una relazione di equivalenza.
9.17 Verificare se la relazione tra le rette del piano per cui due rette sono in relazione se e solo se sono perpendicolari è una relazione di equivalenza.
9.18 Verificare se la relazione tra numeri reali per cui due numeri sono in relazione se e solo se uno dei due divide l’altro è una relazione di equivalenza. 9.19 Sia l’insieme delle classi di equivalenza di polinomi ottenuto mediante la relazione di equivalenza per cui due polinomi sono equivalenti se e solo se divisi per hanno lo stesso resto. Provare che è in corrispondenza biunivoca con .
9.20 Consideriamo , l’anello delle classi di resto modulo .
Trovare un intero , , tale che . Ne esiste più d’uno?
Esiste un intero pari nella classe di ?
Esiste un intero multiplo di nella classe di ?
Sia un intero fissato. Provare che esiste almeno un intero , con , tale che .
9.21 Nell’anello :
determinare tutti gli elementi invertibili e le loro classi;
determinare tutti gli zero-divisori;
trovare tutti gli elementi tali che .
Provare che è invertibile in per ogni . Possiamo allora dire che gli elementi invertibili di sono infiniti?
9.22 Si determini (se esiste) l’inverso di in .
9.23 L’equazione ha soluzioni in ?
9.24 Risolvere le congruenze:
9.25 Calcolare , e , dove è la funzione di Eulero.
9.26 Determinare la cifra delle unitè del numero .
9.27 Determinare la cifra delle unitè e quella delle centinaia del numero .
9.28 Risolvere la congruenza .
9.29 Determinare il generatore del sottogruppo di .
9.30 Nel gruppo delle classi di resto modulo 55:
9.31 Determinare tutti gli elementi del gruppo e il periodo di ciascuno. Dedurre da quanto ottenuto se è un gruppo ciclico?
9.32 Determinare tutti gli elementi del gruppo e il periodo di ciascuno. Dedurre da quanto ottenuto se è un gruppo ciclico?