Corso di Algebra - Corso di recupero, a.a. 2005/06
Le lezioni

lezioni

6/3
Introduzione al corso: presentazione, finalità, informazioni generali.
Rudimenti di logica proposizionale. I principali connettivi proposizionali (descritti semanticamente): negazione, congiunzione, disgiunzione, condizionale (implicazione) e bicondizionale (equivalenza). Negazione di una implicazione, leggi di De Morgan ed altre tautologie classiche. Delle note disponibili in questo sito sono molto rilevanti per il contenuto di questa lezione: tavola dei connettivi binari e esempi di tautologie. Nella prossima lezione sarà utilizzata anche la lista di tautologie e identità insiemistiche; per seguire utilmente la lezione sarà bene avere queste tre note a portata di mano.
9/3
Esercizi sugli argomenti della lezione precedente.
Disgiunzione esclusiva (AUT/XOR) e sua negazione. Interdipendenza semantica tra i connettivi (vedi tavola dei connettivi binari.
Cenni alla logica dei predicati. Quantificatori: universale (∀) ed esistenziale (∃) e loro uso; frasi contenenti più quantificatori (esempi di frasi delle forme ∀∃ o ∃∀); negazioni di frasi con quantificatori. Vago cenno alle nozioni di occorrenza libera e legata di una variabile.
Nozione informale di insieme. Uso di '∈'. Principio di estensionalità: ((∀ A,B)(A=B ⇔ (∀ x(x∈A⇔ x∈ B))) e sue applicazioni. L'insieme vuoto ∅ (e sua unicità).
Esercizi assegnati: tavola di verità e negazione di ((p⇒q)∧r)⇒((p⇒r)∧(q⇒p)); negazione di ((∀x)P(x))⇒(∃y∀x Q(x,y)).
Si rinnova l'invito a presentarsi a lezione con le tre note su connettivi, tautologie, tautologie e identità insiemistiche.
13/3
Discussione degli esercizi dalla lezione precedente.
Inclusione tra insiemi. La regola della "doppia inclusione": (∀ A,B)(A=B ⇔ (A⊆B ∧ B⊆A)).
Parti (o sottoinsiemi) di un insieme, parti proprie, l'insieme ℘(S) delle parti di un insieme S.
Modi di descrizione degli insiemi (per elencazione degli elementi, tramite 'proprietà' caratteristiche, …). L'"insieme di tutti gli insiemi" non esiste.
Rapporti tra connettivi proposizionali e nozioni insiemistiche. Inclusione e implicazione; operazioni insiemistiche (binarie) di unione, intersezione e complemento e loro corrispettivi nel calcolo proposizionale. Lettura di tautologie e identità insiemistiche (in aggiunta: transititività dell'implicazione, vedi esempi di tautologie e dell'inclusione).
Diagrammi di Euler-Venn. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare identità insiemistiche. Esempi, tra i quali: distributività dell'intersezione rispetto al complemento. Esercizio: confrontare, per insiemi A, B, C, gli insiemi A∪(B-C) e (A∪B) - (B∪C).
Differenza simmetrica e disgiunzione esclusiva. Esercizio: provare l'associatività delle differenza simmetrica (utilizzando diagrammi di Euler-Venn).
16/3
Discussione degli esercizi dalla lezione precedente. Ulteriore verifica dell'associatività delle differenza simmetrica, utilizzando l'associatività del bicondizionale e la tautologia (¬(a⇔b))⇔((¬a)⇔b) per ottenere l'associatività del connettivo XOR.
Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti (con verifiche dettagliate nel caso delle unioni di due o tre insiemi).
L'insieme delle parti di un insieme: esempi; il numero degli elementi di ℘(S) se S è un insieme finito–con la relativa dimostrazione è stato introdotto il principio di induzione.
Esercizio: elencare gli elementi di ℘({1,2,3,4}).
Descrizione generale degli argomenti da affrontare successivamente nel corso; centralità della nozione di corrispondenza.
Coppie ordinate. Esercizio (non facilissimo): la definizione di Kuratowski di coppia ordinata (data come (a,b):={{a},{a,b}} per ogni a e b) è una 'buona' definizione di coppia ordinata).
Prodotto cartesiano tra due insiemi. Il numero dei suoi elementi (nel caso di insiemi finiti). Esercizio: Per insiemi A e B descrivere A×∅ e ∅×A; stabilire esattamente quando si ha A×B=B×A
Corrispondenze tra insiemi, Relazioni binarie, applicazioni tra insiemi. Introdotte le notazioni: Corr(A,B) (corrispondenze da A a B), Rel(A) (=Corr(A,A); relazioni binarie in A), con riferimento ad insiemi A e B.
Procurarsi per la prossima lezione: tautologie, insiemi, aritmetica e relazioni binarie.
20/3
Discussione degli esercizi dalla lezione precedente, escluso quello sulla definizione di Kuratowski di coppia ordinata.
Alcuni dettagli sul connettivo ∃!, descritto in questi termini: "(∃!x)P(x)" equivale a "((∃x)P(x))∧((∀x,y)((P(x)∧P(y))⇒x=y))", ovvero a "(∃x)(∀y)(P(y)⇔x=y)".
Le applicazioni. Dominio e codominio. Notazioni per le applicazioni e per l'immagine di un elemento del dominio mediante un'applicazione. Il problema della "buona definizione" (o buona posizione) per un'applicazione; esempi.
Immagine di un'applicazione; applicazoni suriettive; ridotta di un'applicazone. Applicazioni iniettive. Negazione di iniettività e suriettività. Esercizi: stabilire se x2∈R+→x4∈R e x2∈R+→x5∈R definiscono correttamente applicazioni, e nel caso discuterne l'eventuale iniettività e suriettività (R è l'insieme dei numeri reali, R+ è l'insieme dei numeri reali positivi ; → sostituisce il simbolo di assegnazione, che non esiste in HTML). Si veda anche tautologie, insiemi, aritmetica.
Relazioni binarie riflessive, antiriflessive, simmetriche, transitive. Negazione di ciascuna delle quattro proprietà considerate. Esempi, relazione di uguaglianza in un insieme e suo grafico (diagonale).
Esercizio: si studi, rispetto alle quattro proprietà appena elencate la relazione binaria ρ in ℘(N) definita ponendo, per ogni coppia di parti X e Y di N, XρY⇔X∩Y=∅ (relazione di disgiunzione tra gli insiemi di numeri naturali).
Solita avvertenza: avere con se, alla prossima lezione, i cinque fogli (tra note e esercizi) già segnalati tra quelli da scaricare da questo sito.
23/3
Discussione degli esercizi dalle lezioni precedenti.
Prodotto (relazionale) tra corrispondenze. Corrispondenza inversa. Una relazione binaria di grafico ρ è riflessiva (risp. antiriflessiva) se e solo se ρ è contenuto nella (risp. disgiunto dalla) diagonale, simmetrica se e solo se ρ-1=ρ, transitiva se e solo se ρ2⊆ρ.
Associatività del prodotto relazionale e, come caso particolare, del prodotto operativo (o composizione) tra applicazioni. L'uso di diagrammi commutativi per applicazioni. Fare attenzione alla notazione ‘da sinistra verso destra’ usata per la composizione di applicazioni, differente da quella (ο) utilizzata nel libro di testo: fg=gοf.
Esercizi: Si considerino le applicazioni f:x∈N→x2∈N, g:x∈N→{x}-2N∈℘(N) e, posto X={1,2,3,4,5,6,7}, h:x∈X→8-x∈X (verificare che sia ben posta) e k:X→X definita (in notazione matriciale) dalla matrice di prima riga 1 2 3 4 5 6 7 e seconda riga 3 7 5 3 2 4 6. Si eseguano tutte le composizioni possibili (anche, ad esempio, k2); di tutte le applicazioni date o ottenute si discutano iniettività e suriettività.
Iniettività e suriettività per applicazioni composte: se f e g sono applicazioni componibili, allora fg è iniettiva (risp. suriettiva) se f e g sono entrambe iniettive (risp. suriettive); se fg è iniettiva (risp. suriettiva) allora f è iniettiva (risp. g è suriettiva).
27/3
Discussione di alcuni esercizi dalle lezioni precedenti (affinché se ne discuta bisogna che qualcuno provi almeno a farli!).
Relazioni di equivalenza. Vari esempi. Il nucleo di equivalenza di un'applicazione (da Facchini è chiamato equivalenza associata). Unioni e intersezioni arbitrarie di insiemi e famiglie (non vuote nel caso dell'intersezione).
Partizioni di un insieme, equivalenza determinata da una partizione. Classi di equivalenza ed insieme quoziente. Biezione canonica tra Eq(S) e Part(S) (insiemi delle relazioni di equivalenza e delle partizioni di un insieme S). Partizioni banali e corrispondenti equivalenze (uguaglianza e relazione universale).
Proiezione canonica di un insieme su un suo quoziente; ogni equivalenza è il nucleo di equivalenza di un'applicazione. Coimmagine di un'applicazione (come quoziente rispetto al nucleo di equivalenza). Teorema di omomorfismo per insiemi (fattorizzazione canonica di un'applicazione).
Esercizio: si calcoli il numero delle relazioni di equivalenza nell'insieme {1,2,3}.
30/3
Discussione dell'esercizio dalla lezione precedente.
Equipotenza e confronto di cardinalità tra insiemi (in un qualsiasi insieme la relazione di equipotenza è una equivalenza, la relazione "avere cardinalità minore o uguale" è riflessiva e transitiva). Esercizio (come applicazione del teorema di omomorfismo per insiemi): sia ~ la relazione di equipotenza in ℘(S), dove S={n∈N|n≤10}; si calcoli |℘(S)/~|.
Applicazione immagine e applicazione controimmagine (o immagine inversa) definita da un'applicazione.
Restrizioni e prolungamenti di applicazioni, immersioni. Legami tra queste nozioni.
Sezioni di un'applicazione. Un'applicazione è suriettiva se e solo se ha sezioni. Descrizione delle sezioni; esempi.
Retrazioni di un'applicazione. Un'applicazione è iniettiva se e solo se ha retrazioni oppure ha per dominio l'insieme vuoto. Esempi.
Neutralità dell'applicazione identica. Applicazione inversa. Un'applicazione è biettiva se e solo se ha inversa. Unicità dell'inversa: se s e r sono, rispettivamente, una sezione ed una retrazione dell'applicazione f allora s=r, dunque s è l'unica inversa, l'unica sezione e l'unica retrazione di f. Inversa della composta di due applicazioni biettive.
Calcolo combinatorio. Per insiemi finiti A e B, calcolo di |Map(A,B)| e di |InjMap(A,B)| (gli insiemi qui indicati sono, rispettivamente, quello delle applicazioni e quello delle applicazioni iniettive da A a B). Fattoriali discendenti e fattoriale di un numero naturale.
Esercizi. Scrivere tre prolungamenti a Z dell'immersione di N in Z.
Posto A={a,b,c} (dove |A|=3) e B={1,2,3,4,5}, scrivere tutte le sezioni dell'applicazione f:B→A che manda 1 in a, 2 in b, 3 in a, 4 in c e 5 in b. Scrivere tutte le retrazioni dell'applicazione g:A→B che manda a in 1, b in 2 e c in 4.
3/4
Discussione degli esercizi dalla lezione precedente. Descrizione esplicita delle retrazioni di un'assegnata applicazione iniettiva.
Teorema: se f è un'applicazione tra due insiemi finiti ed equipotenti, allora f è iniettiva se e solo se è suriettiva (dunque, se e solo se è biettiva).
Cardinalità dei prodotti cartesiani di insiemi finiti.
L'insieme ℘k(S) delle k-parti di un insieme S (qui k è un numero naturale). Cardinalità di questo insieme: coefficienti binomiali e loro prime proprietà (utilizzando, in mancanza di simboli appositi in HTML, la notazione (n:k) per il coefficiente binomiale n su k, abbiamo osservato che, per ogni intero positivo n e per ogni naturale k minore di n, si ha: (n:0)=(n:n)=1 e (n:1)=n;  (n:0)+(n:1)+…+(n:n)=2n; (n:k)=(n:n-k) (tramite una biezione tra ℘k(S) e ℘n-k(S), dove |S|=n); (n+1:k+1)=(n:k)+(n:k+1) (si descrive quindi il triangolo di Tartaglia-Pascal); formula esplicita: (n:k)=n!/(n-k)!k!.
Operazioni (binarie, interne) in un insieme. Operazioni associative e operazioni commutative; esempi. Cenni ai teoremi di associatività e di commutatività. Nozione di struttura algebrica. Parti stabili in una struttura (rispetto ad una operazione).
Esercizi: 1). Siano A e B due insiemi tali che |A|=10 e |B|=15. Indicare: |A×B|, |Map(A,B)|, |Map(B,A)|, |InjMap(A,B)|, |InjMap(B,A)|, |SurMap(A,B)| (l'insieme qui considerato è quello delle applicazioni suriettive da A a B), |Corr(A,B)|, |Corr(B,A)|, |℘(A)|, la cardinalità dell'insieme delle parti di A equipotenti a B, quella dell'insieme delle parti di B equipotenti a A.
2). Delle seguenti sette parti di Z: N, Z-N, {x∈Z|x>-100}, {0}, {1}, {2}, {0,1,2}, dire quali sono stabili rispetto alla (usuale) operazione di moltiplicazione.
Dalla prossima lezione servirà avere con sé la pagina di esercizi polinomi e strutture algebriche.
6/4
Discussione degli esercizi dalle lezioni precedente. Altri esercizi sulle parti stabili. Esempi di strutture associative e commutative (insiemi numerici muniti dell'addizione o della moltiplicazione; insieme delle parti di un insieme munito dell'operazione di unione, intersezione o differenza simmetrica) o solo associative (trasformazioni di un insieme).
Operazioni indotte su parti stabili; queste ereditano le (eventuali) proprietà associativa e commutativa.
Elementi neutri a sinistra e a destra; elementi neutri e loro unicità (se, in una assegnata struttura, s è un elemento neutro a sinistra e d è un elemento neutro a destra, allora s=d e quindi s è (l'unico) elemento neutro). Esempi, tra cui quello di una struttura associativa (semigruppo) con più di un elemento neutro a sinistra.
Semigruppi e monoidi. Notazioni per le strutture algebriche che coinvolgano anche operazioni unarie o nullarie (come nel caso dei monoidi). Tra gli esempi: il monoide T(S) delle trasformazioni di un insieme S (non commutativo se |S|>1). Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che sono monoidi ma non sottomonoidi.
Simmetrici destri e sinistri in una struttura con elemento neutro; simmetrici, elementi simmetrizabili. Unicità, nel caso dei monoidi (se, per un elemento x di un assegnato monoide, s è un simmetrico sinistro e d è un simmetrico destro di x, allora s=d e quindi s è (l'unico) simmetrico di x). Interpretazione di queste nozioni nel monoide T(S). Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione moltiplicativa) per "simmetrico".
Gruppi. Definizione ed esempi. Il gruppo degli invertibili U(M) di un monoide M (e formula per l'inversione di un prodotto in un monoide). Diversi esempi; il gruppo simmetrico Sym(S) su un insieme S. Permutazioni. Gruppi abeliani; Sym(S) non è abeliano se |S|>2.
Esercizi assegnati: 1). Siano A e B insiemi tali che ∅≠A⊆B. Rispetto a quali tra le operazioni ∪, ∩ e Δ (differenza simmetrica) in ℘(B) la parte {X⊆B|A⊆X} è stabile?
2). Esercizio nr. 4 da polinomi e strutture algebriche.
3). Esercizio nr. 5 da un compito del 20 febbraio 2004.
10/4
Discussione degli esercizi dalla lezione precedente.
Elementi cancellabili, a sinistra o a destra rispetto ad un'operazione binaria; elementi cancellabili. Rapporto tra simmetrizzabilità e cancellabilità in un monoide; il caso dei semigruppi finiti (si vedano le relative note).
Sottogruppi di un gruppo e loro caratterizzazione (una parte H di un gruppo G ne costituisce un sottogruppo se e solo se non è vuota e x-1y∈H per ogni x,y∈H). Esempi.
Omomorfismi tra strutture algebriche. Omomorfismi di semigruppi, di monoidi, di gruppi. Un esempio di omomorfismo di semigruppi tra monoidi che non è, però, un omomorfismo tra monoidi. Monomorfismi, epimorfismi, isomorfismi. L'importanza della nozione di isomorfismo; le proprietà algebriche sono invarianti per isomorfismi. Cenno alle tavole di moltiplicazione (di Cayley).
Definizione di relazione binaria antisimmetrica, di ordinamento stretto, di ordinamento largo.
Esercizi assegnati: 1). Esercizio nr. 3 da un compito del 17 febbraio 2006.
2). L'applicazione X∈℘(Z)→ X∩N∈℘(N) è un omomorfismo da (℘(Z),∩) a (℘(N),∩)? E da (℘(Z),∪) a (℘(N),∪)?
3). Verificare che, per ogni insieme S, l'applicazione X∈(℘(S),∩)→S-X∈(℘(S),∪) è un isomorfismo.
4). Riprendere l'esercizio nr. 5 da un compito del 20 febbraio 2004 per dimostrare che U(X) è un sottogruppo di Sym({1,2,3,4}) isomorfo a Sym({1,3,4}).
5). Riguardare i primi due esercizi da relazioni binarie, rispondendo alle domande sugli ordinamenti.
20/4
Discussione di uno solo degli esercizi dalla lezione precedente.
Corrispondenza (biezione) tra gli ordinamenti stretti e gli ordinamenti larghi in un insieme; esempi. Alcuni insiemi ordinati: i reali, razionali, gli interi, i naturali, ordinati secondo l'ordinamento usuale. L'insieme delle parti di un insieme, ordinato per inclusione. Elementi confrontabili e non confrontabili. Ordinamenti totali.
La relazione di divisibilità in un semigruppo o in un monoide commutativi. Questa relazione può non essere antisimmetrica: elementi associati. Casi notevoli in cui la relazione di divisibilità è un ordinamento (largo): numeri naturali, interi positivi.
Ordinamento indotto su una parte di un insieme ordinato.
Ordinamento duale (cioè relazione inversa di una relazione d'ordine; anch'essa è una relazione d'ordine). Principio di dualità. Nozioni di minimo ed elemento minimale in un insieme ordinato e corrispondenti nozioni duali: massimo ed elemento massimale. Unicità di minimo (e massimo): se x e y sono elementi di un insieme ordinato in cui x sia minimo (risp. massimo) e y sia minimale (risp. massimale) allora x=y. Esempi di insiemi con più elementi minimali ed esempio di un insieme con un unico elemento minimale che però non è minimo.
Relazione di copertura associata ad un ordinamento. Diagrammi di Hasse di un insieme ordinato finito.
Esercizi assegnati: 1). Per quali insiemi S l'insieme ℘(S) è totalmente ordinato per inclusione?
2). Esercizio numero 6 da relazioni binarie, (solo per le parti che riguardano nozioni già affrontate).
24/4
Discussione di alcuni esercizi dalle lezioni precedenti (tanto per cambiare).
Ogni insieme ordinato finito e non vuoto ha elementi minimali ed elementi massimali; ciò garantisce la possibilità di disegnare diagrammi di Hasse. Lo stesso non vale nel caso di insiemi infiniti; esempi. Minimi, massimi, elementi minimali o massimali in (N,|), (N#,|) e (N#-{1},|).
Minimo, massimo, elementi minimali e massimali di una parte di un insieme ordinato. Buon ordinamento di N e giustificazione del principio di induzione.
Minoranti e maggioranti di una parte di un insieme ordinato. Estremo inferiore ed estremo superiore. Esempi; tra questi è stata enunciata un'importante proprietà dell'ordinamento usuale dei numeri reali: ogni parte di R che abbia minoranti (risp. maggioranti) ha estremo inferiore (risp. superiore).
Per una parte T di un insieme ordinato S e per un elemento x∈T sono equivalenti: x=min T; x=inf T; x è un minorante di T
Se A e B sono parti di un insieme ordinato S, entrambe dotate di estremo inferiore in S, allora A∪B ha estremo inferiore se e solo se lo ha {inf A,inf B}; nel caso esistano, questi due estremi inferiori coincidono. (Ovviamente vale l'enunciato duale per gli estremi superiori).
Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli. Il duale di ogni reticolo è un reticolo. In ogni reticolo, ogni parte finita non vuota ha estremo inferiore ed estremo superiore. Nozione di reticolo completo (esempio: l'insieme delle parti di un insieme, ordinato per inclusione). In ogni reticolo, un eventuale elemento minimale (risp. massimale) è minimo (risp. massimo).
Esercizi assegnati: 1). Descrivere l'insieme dei minoranti e l'insieme dei maggioranti in (N,|) di {15,20,30}.
2). Disegnare i diagrammi di Hasse di Div(18), Div(8) e Div(30) (insiemi dei naturali divisori di 18, 8 e 30), ordinati per divisibilità.
3). Esercizio nr. 5 da relazioni binarie, (solo per quanto riguarda nozioni già definite).
27/4
Discussione di esercizi dalla lezione precedente.
Ogni reticolo finito ha minimo e massimo.
Estensione della nozione di estremo inferiore e di estremo superiore: definizione di massimo comun divisore e minimo comune multiplo (in un semigruppo commutativo).
Reticoli come strutture algebriche: operazioni reticolari. Equivalenza tra lo studio dei reticoli come strutture ordinate e come strutture algebriche. Esempio: per un insieme S, il reticolo (℘(S),⊆) e (℘(S),∩&cup). Principio di dualità per reticoli.
Sottoreticoli; esempi: intervalli chiusi in un reticolo, Div(n) in (N,|), dove n∈N. Esempio di una parte di un reticolo che non è un sottoreticolo, ma che, munito dell'ordinamento indotto, è un reticolo.
Isomorfismi tra insiemi ordinati ed isomorfismi tra reticoli. Un esempio di applicazione crescente e biettiva tra insiemi ordinati che non è un isomorfismo.
Complementi di un elemento in un reticolo limitato (cioè con minimo e massimo); diversi esempi; il complemento non è necessariamente unico. Reticoli complementati.
Esercizio assegnato: elencare, a meno di isomorfismi, tutti gli insiemi ordinati di cardinalità 1, 2 o 3, disegnandone diagrammi di Hasse.
4/5
Discussione dell'esercizio dalla lezione precedente.
Ulteriori esempi di complementi in reticoli. Reticoli distributivi. Esempi: (&weierp(S),⊆) per un insieme S, (N,|) (senza dimostrazione), catene. Ciascuna delle due leggi distributive in un reticolo implica l'altra (senza dimostrazione). I sottoreticoli dei reticoli distributivi sono distributivi, l'analogo non vale per i reticoli complementati. In un reticolo distributivo (limitato) ciascun elemento ha al massimo un complemento. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff. Le proprietà di essere un reticolo complementato e di essere un reticolo distributivo sono invarianti per dualità.
Reticoli booleani: definizione ed esempi. Operazione unaria di complemento (') e algebre di Boole. Equivalenza tra le nozioni di reticolo booleano e di algebra di Boole. Proprietà delle algebre di Boole: l'operazione di complemento è involutoria (il complemento del complemento di ogni elemento x è x stesso), leggi di De Morgan. Sottoalgebre di Boole, con esempi e controesempi (esempi di sottoreticoli di un reticolo booleano che non sono sottoalgebre di Boole. Enunciato del teorema di Stone. Come conseguenza: le algebre di Boole finite hanno per cardinalità una potenza di 2; due algebre di Boole finite equipotenti sono necessariamente isomorfe. Il booleano di un insieme.
Cenni alle applicazioni delle algebre di Boole: in logica (algebra di Boole associata ad un linguaggio: cenni vaghissimi), corrispondenza (informale) tra proprietà in un insieme e booleano dell'insieme stesso. Ad un livello più formalmente preciso: `stringhe di zeri e uno' e algebre di Boole: nozione di funzione caratteristica di una parte di un insieme S; biezione tra &weierp(S) e Map(S,{0,1}) (ne segue una seconda dimostrazione della formula |&weierp(S)|=2|S|). Come si rappresenta l'insieme delle parti di {1,2,3,…,n} (dove n è un intero positivo) mediante l'insieme delle stringhe di lunghezza n formate da 0 e 1.
Esercizi assegnati: 1). Esercizio nr. 5 da un compito del 21 ottobre 2005.
2). Esercizio nr. 7 da un compito del 18 novembre 2005.
8/5
Discussione degli esercizi dalla lezione precedente.
Anelli. Anelli commutativi, anelli unitari. Sottoanelli e sottoanelli unitari. Omomorfismi di anelli e di anelli unitari. Esempi di sottoanelli di anelli unitari che non sono sottoanelli unitari pur essendo, per proprio conto, anelli unitari. Esempi di omomorfismi tra anelli unitari che non conservano l'unità. Anello opposto di un anello e dualità sinistra-destra per anelli. Prime regole di calcolo negli anelli: 0a=a0=0; -(ab)=(-a)b=a(-b) e (-a)(-b)=ab per ogni a e b, in ogni anello.
Definizioni di corpo e campo (attenzione alla non corrispondenza con la terminologia che usa Facchini. Un corpo è un anello unitario in cui ogni elemento diverso da zero è invertibile; un campo è un corpo commutativo). Esempi: l'anello Z degli interi ed il suo sottoanello (non unitario) degli interi pari, i campi Q ed R dei razionali e dei reali, l'anello (non commutativo) delle matrici 2×2 sugli interi (sui razionali, sui reali etc.).
Multipli e potenze di un elemento secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari per elementi simmetrizzabili). Regole di calcolo (in semigruppi o monoidi): per ogni n,m∈Z e per ogni a per cui queste potenze siano definite, an+m=anam e anm=(an)m; similmente, in notazione additiva, per i multipli. Multipli dell'unità in un anello unitario. Regola di calcolo per anelli unitari R: per ogni n∈Z e a∈R, (n1R)a=na.
Esercizi assegnati: anche se mi sono dimenticato di dirlo in aula, se qualcuno a casa prova farlo inizieremo la prossima lezione discutendo l'esercizio nr. 5 da polinomi e strutture algebriche.
11/5
Verifica (tramite diagrammi di Euler-Venn) della distributività dell'intersezione rispetto alla differenza simmetrica.
Formula del binomio di Newton (per elementi permutabili in anelli arbitrari, vedi pag. 4 in Coefficienti binomiali).
Elementi idempotenti in semigruppi, monoidi ed anelli. Idempotenti banali in un anello.
Anelli booleani. Esempi. Proprietà: sono commutativi ed hanno caratteristica 2 (la nozione di caratteristica è stata appena accennata). Equivalenza tra le nozioni di anello booleano e di reticolo booleano (sono state effettuate in dettaglio le verifiche della correttezza della costruzione di un reticolo booleano a partire da un anello booleano, la costruzione inversa è stata solo indicata, ma non sono state svolte le relative dimostrazioni). Enunciato del teorema di Stone per anelli booleani.
Elementi cancellabili e divisori dello zero negli anelli (vedi cancellabilità). Anelli integri e domini di integrità. Esempi. I campi sono domini di integrità; i domini di integrità finiti sono campi.
Approfondimenti sulla divisibilità nei monoidi commutativi: la relazione "essere elementi associati" è di equivalenza. Nei monoidi (commutativi) regolari, due elementi sono associati se e solo se uno è multiplo dell'altro con cofattore invertibile.
Esercizi assegnati: 1). Esercizio nr. 5 da polinomi e strutture algebriche.
2). Sia, in un anello unitario, a un elemento idempotente. Provare che anche 1-a è idempotente.
15/5
Discussione degli esercizi dalla lezione precedente, con qualche estensione del nr. 5 da polinomi e strutture algebriche (l'anello lì descritto è isomorfo a quello degli interi).
Se a e b sono elementi di un monoide commutativo M, allora a e b sono associati se e solo se hanno gli stessi divisori, ovvero se e solo se hanno gli stessi multipli. Se M è regolare, la divisibilità in M è un ordinamento se e solo se l'unità è l'unico invertibile in M.
Per monoidi commutativi regolari: divisori banali, elementi irriducibili; fattorizzazioni banali e non banali. Esempio di un monoide infinito con un solo invertibile e privo di irriducibili. Fattorizzazioni in irriducibili; fattorizzazioni "essenzialmente uguali" (uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati). Monoidi fattoriali. Teorema fondamentale dell'aritmetica (fattorialità dei monoidi moltiplicativi degli interi positivi e degli interi non nulli). (Si è dimostrata l'esistenza di fattorizzazioni in irriducibili, non l'essenziale unicità delle stesse). Elementi primi; essi sono irriducibili. Caratterizzazioni della fattorialità: un monoide commutativo regolare è fattoriale se e solo se in esso ogni elemento non invertibile è prodotto di irriducibili e ogni irriducibile è primo; ovvero: se e solo se in esso ogni elemento non invertibile è prodotto di primi (non sono state fornite dimostrazioni di questo teorema). Un esempio di monoide commutativo regolare non fattoriale in cui ogni elemento non invertibile è prodotto di primi (vedi l'esercizio assegnato). Anelli fattoriali (esempi: Z, campi). Cenni molto rapidi al monoide delle parole su un alfabeto.
Esercizio assegnato: Sia M il sottomonoide (commutativo, regolare) di (N,·,1) costituito da 1 e dagli interi positivi pari (in M l'unico invertibile è 1). Mostrare che, in M,
1) gli elementi irriducibili sono tutti e soli gli interi positivi della forma 2d, dove d è un intero dispari;
2) ogni elemento diverso da 1 è prodotto di irriducibili;
3) non esistono primi. (Suggerimento: se d e t sono interi positivi dispari distinti e t>1, allora 2d divide (2dt)(2t) in M, ma …)
19/5
Discussione dell'esercizio dalla lezione precedente.
Fattorizzazione primaria (cioè in potenze di primi) di un intero positivo n. Determinazione dei divisori di n (in N e in Z) dalla sua fattorizzazione primaria. Cenno al caso (più generale) dei monoidi fattoriali e applicazione al calcolo di massimi comuni divisori e minimi comuni multipli.
Divisione con resto (aritmetica) in Z. Esistenza e unicità di quoziente e resto. Operazione binaria mod in Z. Divisione euclidea in Z.
Congruenze in Z. ≡0 è la relazione universale, ≡1 è l'uguaglianza, per ogni m∈Z, ≡m e ≡-m coincidono. Le congruenze in Z sono equivalenze (oltre la verifica diretta, è stato osservato che, per ogni intero m diverso da 0, ≡m è il nucleo di equivalenza di a∈Z→a mod m∈Z). Classi di resto, loro descrizione, loro numero, insiemi completi di rappresentanti. L'insieme quoziente Zm:= Z/≡m.
Compatibilità delle congruenze con l'addizione e la moltiplicazione di Z. Applicazioni: criteri di divisibilità per 2, 5, 4, 25, 8, etc., 3, 9, 11, ‘prova del nove’. Osservazione: se due interi sono congrui modulo un intero m, essi sono congrui modulo ogni divisore di m. Altri esempi di calcoli in aritmetica modulare.
Esercizi assegnati: 1). Elencare gli interi compresi tra -30 e 30 (inclusi) e congrui a 16 modulo 7.
2). Calcolare 11111111111 mod 3.
3). Esercizio nr. 12 da Tautologie, insiemi, aritmetica.
4). Esercizi nr. 1 e 2 da un compito del 23 settembre 2005.
22/5
Discussione degli esercizi dalla lezione precedente.
Strutture quoziente: equivalenze compatibili con un'operazione binaria; congruenze in una struttura algebrica; loro caratterizzazione come equivalenze compatibili a sinistra e a destra; operazioni quoziente. Un esempio di relazione di equivalenza in Z compatibile con la moltiplicazione ma non con l'addizione. Proprietà che si conservano passando alla struttura quoziente (associatività, commutatività, esistenza di neutri e simmetrici, idempotenza, distributività etc.). Proiezione canonica su una struttura quoziente: è un epimorfismo. Quozienti di semigruppi, monoidi, gruppi, anelli etc.
Particolare enfasi è stata posta sui quozienti dell'anello Z. Gli unici quozienti di Z sono gli anelli Zm, ciò è conseguenza del fatto che le sole congruenze in (Z,+) sono le congruenze ≡m al variare di m in N (questo fatto non è stato dimostrato). Se m è un intero maggiore di 1, Zm è un dominio di integrità (dunque un campo) se e solo se m è primo. Vari esempi.
Periodo di un elemento in un gruppo. Nozione di sottogruppo generato da una parte e di gruppo ciclico. Se un elemento x di un gruppo ha periodo finito n, allora, per ogni intero t, si ha xt=1 se e solo se n divide t; più in generale, se a,b∈Z, xa=xb se e solo se a e b sono congrui modulo n. Un esempio di questa osservazione in un calcolo in aritmetica modulare. L'elemento neutro di un gruppo è l'unico elemento di periodo 1. Caratteristica di un anello unitario; esempio: caratteristica dei quozienti di Z.
Esercizi assegnati: 1). In ogni monoide commutativo la relazione "essere elementi associati" è una congruenza.
2). Per quali interi m>1 l'anello Zm è booleano?
3). Calcolare i periodi degli elementi del gruppo moltiplicativo del campo Z7.
25/5
Discussione degli esercizi dalla lezione precedente.
I massimi comuni divisori di due assegnati elementi in un monoide commutativo costituiscono una classe di elementi associati.
Osservazione: se R è un anello commutativo unitario, ogni elemento di R che divida due elementi a e b di R divide ogni combinazione lineare (in R) di a e b. Algoritmo euclideo delle divisioni successive per la determinazione di un massimo comun divisore tra due interi. Esempi, giustificazione dell'algoritmo.
Se m è un mcm(a,b) e d è un MCD(a,b), allora dm è associato ad ab.
Equazioni diofantee (di primo grado, a due indeterminate), estensione dell'algoritmo euclideo per la ricerca di una loro soluzione. Teorema di Bézout (la dimostrazione fornita è quella data dalla validità dell'algoritmo euclideo, diversa da quella nel libro di testo). Conseguenze: caratterizzazione delle coppie di interi coprimi; lemma di Euclide: se a,b,c sono interi, a divide bc ed è coprimo con b, allora a divide c. Esempi.
Equazioni congruenziali (di primo grado). Criterio di esistenza di soluzioni.
Esercizi assegnati: Esercizi nr. 5, 6, 7, 8 e 9 da Tautologie, insiemi, aritmetica. L'esercizio 9 è da svolgere senza usare l'algoritmo euclideo.
29/5
Discussione degli esercizi dalla lezione precedente.
Metodi di semplificazione e di ricerca di una soluzione per le equazioni congruenziale (di primo grado).
Elementi invertibili nei quozienti di Z. Determinazione dell'insieme di tutte le soluzioni di un'equazione congruenziale di primo grado. Diversi esempi e discussione dei possibili errori.
La funzione di Eulero. Numero degli invertibili in un quoziente di Z.
Esercizi assegnati:
1). Esercizio nr. 10 (a e b) da Tautologie, insiemi, aritmetica, da svolgere senza usare l'algoritmo euclideo.
2). Esercizio nr. 8 da un compito del 16 dicembre 2005.
3). Esercizio nr. 8 da un compito del 17 febbraio 2006.
1/6
Discussione degli esercizi dalla lezione precedente.
Osservazioni sugli inversi in aritmetica modulare e sui possibili metodi di calcolo. Notazione "a-1 mod m".
Determinazione dell'insieme di tutte le soluzioni (intere) di equazioni diofantee lineari a due indeterminate.
Laterali di un sottogruppo; i laterali destri di un fissato sottogruppo in un gruppo ne costituiscono una partizione (esempio: le classi di resto in Z). Teorema di Lagrange per gruppi finiti; conseguenze: in un gruppo finito le sia le cardinalità dei sottogruppi che i periodi degli elementi dividono la cardinalità del gruppo. Applicazioni all'artimetica modulare; teorema di Fermat-Eulero e Piccolo teorema di Fermat; vari esempi.
Esercizi assegnati:
1). Sia ~ la relazione di equivalenza associata all'insieme dei laterali destri di un sottogruppo H del gruppo G. Verificare che, per ogni a,b∈G, si ha a~b⇔ab-1∈H e che ~ è compatibile a destra con l'operazione binaria interna di G.
2). Calcolare (2153425771012)80 mod 41.
3). Tenendo presente che né 24 né 23 sono congrui a 1 modulo 21, senza fare calcoli dire qual è il periodo di [2]21 nel gruppo degli invertibili di Z21.
5/6
Discussione degli esercizi dalla lezione precedente.
L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario. Definizione e prime proprietà. Polinomi (cioè: elementi di un tale anello). Successione dei coefficienti di un polinomio. Terminologia essenziale: grado e coefficiente direttore di un polinomio non nullo; termine noto di un polinomio, polinomi costanti. Proprietà fondamentale (proprietà universale) degli anelli dei polinomi: se φ:A→B è un omomorfismo di anelli unitari commutativi e ι è l'immersione di A in A[x], per ogni b∈B esiste un unico omomorfismo di anelli unitari ψ:A[x]→B tale che ι&psi=φ e xψ=b. Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza non è stata invece dimostrata). Altre applicazioni della proprietà fondamentale: omomorfismo di sostituzione; per ogni intero positivo m, epimorfismo da Z[x] a Zm[x] che ad ogni polinomio f associa f stesso "riguardato modulo m".
Per ogni anello commutativo A, A[x] è infinito e non è un campo (x non è invertibile).
Il grado del prodotto tra due polinomi. Se il polinomio non nullo f ha coefficiente direttore cancellabile (in A), allora f stesso è cancellabile (in A[x]). Teorema: A[x] è un dominio di integrità se e solo se lo è A, in questo caso vale in A[x] la regola di addizione dei gradi e U(A[x])=U(A). Esempi che mostrano come queste due proprietà non valgano necessariamente se A non è integro.
Divisione lunga (con resto) tra polinomi (nel caso in cui il divisore sia non nullo ed abbia coefficiente direttore invertibile). Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. Il caso particolare dei polinomi su un campo.
Algoritmo euclideo per la ricerca del massimo comun divisore tra polinomi su un campo. Teorema di Bézout (sempre per polinomi su un campo).
Associati in A[x]: se A è un dominio di integrità polinomi non nulli associati in A[x] hanno necessariamente lo stesso grado; se A è un campo, in ogni classe di polinomi associati (non nulli) esiste uno ed un solo rappresentante monico.
Applicazione polinomiale associata ad un polinomio. Radici di un polinomio. Teorema del resto e Teorema di Ruffini (per anelli commutativi unitari arbitrari).
Esercizi assegnati:
1). Sia A un anello commutativo unitario. L'applicazione che ad ogni polinomio in A[x] associa il suo termine noto è un epimorfismo di anelli unitari da A[x] ad A.
2). Provare che non è possibile effettuare (nel senso usuale) la divisione lunga di x+1 per 2x+3 in Z[x].
3). Esercizi nr. 1 e 2 da polinomi e strutture algebriche.
4). Esercizio nr. 8 da un compito del 23 settembre 2005.
8/6
Discussione di alcuni degli esercizi dalla lezione precedente.
Applicazione del teorema di Ruffini: le radici comuni a due polinomi sono le radici di un loro massimo comun divisore.
L'anello dei polinomi su un anello fattoriale è esso stesso fattoriale (solo enunciato), come caso particolare: fattorialità di Z[x] e dell'anello dei polinomi su un campo. Per un campo K: caratterizzazione dei polinomi irriducibili in K[x] in termini di non decomponibilità in prodotto di polinomi di grado minore; relazione tra le proprietà di esser privo di radici e di essere irriducibile (le due proprietà sono equivalenti per polinomi di grado 2 e 3). Esempi di polinomi di grado maggiore di 3 riducibili in Q[x] ma privi di radici in Q.
Metodi di fattorizzazione per polinomi.
Informazioni: hanno radici nel campo complesso (risp. reale) tutti i polinomi in C[x] (risp. in R[x]) di grado positivo (risp. dispari). Sono irriducibili in C[x] tutti e soli i polinomi di grado uno, i polinomi irriducibili in R[x] hanno grado al più 2.
Ogni polinomio in Q[x] è associato ad un polinomio a coefficienti interi. Radici razionali di polinomi a coefficienti in Z: limitazioni e metodi di ricerca. Come caso particolare: le radici razionali dei polinomi monici a coefficienti interi sono intere. Criterio di irriducibilità di Eisenstein. Applicazione: esistono in Q[x] polinomi irriducibili di grado arbitrario.
Teorema di Ruffini generalizzato (per polinomi a coefficienti in un dominio di integrità unitario). Il grado limita il numero delle radici dei polinomi su domini di integrità; esempi di polinomi non nulli per i quali il numero delle radici supera il grado (in anelli non integri). Principio di identità dei polinomi (per polinomi su domini di integrità infiniti). Il principio non vale nel caso dei polinomi su campi finiti o su anelli booleani.
Esercizi assegnati:
1). Siano f=x4-2x3+2x2-3x-2 e g=x4-2x3+2x2-6x-2. Fattorizzare in prodotto di irriducibili (nei corrispondenti anelli di polinomi) f riguardato prima come polinomio a coefficienti in Z5 e poi in Z11, g riguardato prima come polinomio a coefficienti in Z2 e poi in Z3. (Le fattorizzazioni in irriducibili di f e g in Z[x] sono state calcolate in aula).
2). Esercizio nr. 8 da un compito del 18 novembre 2005.
3). Esercizio nr. 9 da un compito del 17 marzo 2006.
12/6
Discussione di uno degli esercizi dalla lezione precedente.
Grafi: diverse nozioni (informali) di grafo. Definizioni di grafo semplice (in termini di lati e in termini di relazione di adiacenza; equivalenza tra le definizioni) e di multigrafo. Rappresentazione grafica. Nozione di (multi)grafo planare. Grafi completi, grafo complementare di un grafo. Terminologia: vertici, lati, adiacenza, incidenza, grado, vertici isolati.
Isomorfismi tra grafi e proprietà che questi conservano. Esempi. Sottografi.
Per multigrafi finiti: Teorema: il doppio del numero dei lati è la somma dei gradi dei vertici. Vertici pari e vertici dispari; questi ultimi sono in numero pari.
Cammini e circuiti. Relazione di connessione; (multi)grafi connessi; componenti connesse.
Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari (solo enunciato). Esempio: il problema dei sette ponti di Königsberg.
Metodi di costruzione di un grafo con assegnati invarianti. Esempi.
Definizione di foresta e di albero. Teorema: un multigrafo finito G è una foresta se e solo se per ogni coppia (a,b) di vertici di G esiste al più un cammino in G da a a b. Corrispondente caratterizzazione degli alberi.
Esercizi assegnati:
1). Ridimostrare il primo dei teoremi visti nella lezione (il doppio del numero dei lati …) facendo induzione sul numero dei lati.
2). Esercizi 1, 2, 3 e 5 da Grafi
3). Esercizio nr. 3 da un compito del 17 marzo 2006.
4). Elencare, a meno di isomorfismi, tutti i grafi (semplici) connessi con al più 4 vertici.
15/6
Discussione di alcuni degli esercizi dalla lezione precedente.
Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso finito.
Nozione di distanza in multigrafi ed alberi. Rappresentazione radicale di un albero; foglie. In ogni albero finito con almeno due vertici esistono almeno due vertici di grado uno. Inoltre, il sottografo ottenuto da un albero cancellandone un vertice di grado uno ed il lato ad esso incidente è ancora un albero. Caratterizzazione degli alberi: un multigrafo finito G=(V,L,f) è un albero se e solo se: (1) è connesso e |V|=|L|+1, ovvero se e solo se: (2) è una foresta e |V|=|L|+1. Con le stesse notazioni, G è una foresta se e solo se ha esattamente |V|-|L| componenti connesse (in generale, il numero delle componenti connesse in un multigrafo finito non può essere inferiore a questa differenza; in particolare, se il multigrafo è connesso, allora |L|≥|V|-1).
Grafi planari (o piani). Gli alberi sono planari. Enunciato del terorema di Kuratowski.
Richiami su trasformazioni e permutazioni; il gruppo simmetrico Sn. Supporto di una permutazione, permutazioni disgiunte. Permutazioni disgiunte commutano (ma non vale il viceversa). Cicli. Periodo di un ciclo. Decomposizione di una permutazione (su un insieme finito) in prodotto di cicli a due a due disgiunti. Come ottenere da tale decomposizione il periodo di una permutazione. Decomposizione (non unica!) di un ciclo, e quindi di una permutazione arbitraria, in prodotto di trasposizioni. Parità di una permutazione. Tutte queste nozioni (sulle permutazioni e sui gruppi simmetrici) sono state esposte in modo informale e i relativi enunciati non sono stati pienamente dimostrati. Nessuna giustificazione, in particolare, è stata data del fatto che nessuna permutazione può essere contemporaneamente pari e dispari.
Esercizi assegnati:
1). Determinare, a meno di isomorfismi, tutti gli alberi con cinque vertici.
2). Sia φ:S→S' un'applicazione biettiva. Provare che l'applicazione f∈T(S)→φ-1fφ∈T(S') è un isomorfismo di monoidi ed induce un isomorfismo (di gruppi) da Sym(S) a Sym(S').
3). Calcolare, come prodotto di cicli disgiunti, l'inverso della permutazione (12)(134)(2574)∈S8.