Introduzione al corso: presentazione e informazioni generali.
Rudimenti di logica proposizionale. I principali connettivi
proposizionali (descritti semanticamente): negazione,
congiunzione, disgiunzione (inclusiva), condizionale (implicazione) e
bicondizionale (equivalenza). Disgiunzione esclusiva. Tabelle di
verità. Tautologie, contraddizioni e forme contingenti. Alcune
tautologie classiche: principî del terzo escluso e di non
contraddizione, leggi di De Morgan. Interpretazione di una implicazione
come disgiunzione, negazione di una implicazione.
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 con sé.
Esercizi assegnati:
Esercizi sugli argomenti della lezione precedente.
Cenni alla logica dei predicati. Quantificatori: universale (∀) ed esistenziale (∃) e loro uso; frasi contenenti più quantificatori (esempi di frasi delle forme ∀x∃y o ∃y∀x). Cenni alle nozioni di occorrenza libera e legata di una variabile; le formule contenenti variabili libere non sono proposizioni.
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à). Vari modi per descrivere insiemi; cenni a problemi fondazionali, come il paradosso di Russell.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Negazioni di frasi introdotte da quantificatori. Proposizioni della forma (∀x∈S)p(x) e della forma (∃x∈S)p(x); se S è l'insieme vuoto le prime sono sempre vere, le seconde sempre false. Inclusione tra insiemi. La regola della "doppia inclusione": (∀ A,B)(A=B ⇔ (A⊆B ∧ B⊆A)). Rapporti tra connettivi proposizionali e nozioni insiemistiche. Inclusione e implicazione; operazioni insiemistiche (binarie) di unione, intersezione e complemento e loro corrispettivi nel calcolo proposizionale. Diagrammi di Euler-Venn. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare identità insiemistiche. Lettura di una parte tautologie e identità insiemistiche (proprietà associativa, commutativa, iterativa, distributive per ∧ e ∨).
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Differenza simmetrica e disgiunzione esclusiva. Associatività dei connettivi ⇔ e XOR (disgiunzione esclusiva), osservando la tautologia (a XOR b)⇔((¬a)⇔b) e l'equivalenza tra (a⇔b)⇔c e (a XOR b) XOR c. Verifica dell'associatività delle differenza simmetrica anche tramite diagrammi di Euler-Venn. Completamento di tautologie e identità insiemistiche.
Il quantificatore ∃!, descritto ponendo (∃!x)p(x)" equivalente a ((∃!x)p(x))∧(∀x,y)((p(x)∧p(y))⇒x=y), ovvero a (∃x)(∀y)(p(y)⇔x=y).
Richiamo sulla distinzione tra appartenenza e inclusione. Singleton di un elemento.
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 ℘(S) delle parti di un insieme finito.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente. Ancora su appartenenza e inclusione: per ogni insieme X si ha ∅⊆X e X⊆X, mentre X∉X.
Schema generale degli argomenti da affrontare successivamente nel corso; centralità della nozione di corrispondenza.
Coppie ordinate. Prodotto cartesiano tra due insiemi. Il numero dei suoi elementi (nel caso di insiemi finiti).
Corrispondenze tra insiemi, relazioni binarie in un insieme, applicazioni tra insiemi. Introdotte le notazioni: Corr(A,B) (insieme delle corrispondenze da A a B), Rel(A) (=Corr(A,A); insieme delle relazioni binarie in A), con riferimento ad insiemi A e B. Notazione infissa per corrispondenze e relazioni.
Dominio e codominio di una corrispondenza e, in particolare, di una relazione Il problema della "buona definizione" (o buona posizione) per un'applicazione; esempi.
Esercizi assegnati:
Portare con sé dalla prossima lezione: tautologie, insiemi, aritmetica e relazioni binarie.
Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche estensione.
Diverse notazioni per indicare un'applicazione; notazioni per l'immagine di un elemento del dominio mediante un'applicazione.
Successioni e famiglie. Unione e intersezione unarie; l'unione di un insieme o di una famiglia; l'intersezione di un insieme non vuoto o di una famiglia non vuota.
Applicazioni iniettive e applicazioni suriettive. Negazione di iniettività e suriettività; esempi. L'immagine im f di un'applicazione f. Applicazioni biettive. Equipotenza tra insiemi, con particolare attenzione al caso degli insiemi finiti. Principio di induzione (nella prima forma; senza giustificazione). Se S è un insieme finito di cardinalità n, |℘(S)|=sn.
Esercizio: (∀A,B)(A×B=∅⇔(A=∅∨B=∅).
Restrizioni di corrispondenze. Restrizioni di applicazioni. Esempi.
Prodotto relazionale tra corrispondenze. Prodotto operativo (o composizione) tra applicazioni (il prodotto relazionale tra applicazioni è un'applicazione). Corrispondenze (e applicazioni) componibili. Associatività del prodotto relazionale e, come caso particolare, del prodotto operativo.
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.
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). Esempi e controesempi
Neutralità dell'applicazione identica. L'uso di diagrammi commutativi per applicazioni.
Introdotte le notazioni InjMap(A,B) e SurMap(A,B) per gli insiemi delle applicazioni iniettive o suriettive da A a B e ΔA={(a,a)|a∈A} (diagonale di A).
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Relazioni binarie riflessive, antiriflessive, simmetriche, antisimmetriche, transitive. Confronto tra queste proprietà. Descrizione delle stesse proprietà in termini di condizioni sul grafico di una relazione. Introdotta a questo scopo la nozione di inversa di una corrispondenza. Diversi esempi.
Relazioni di equivalenza in un insieme. Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione. Classi di equivalenza e loro proprietà fondamentali (rispetto ad una fissata relazione di equivalenza, due elementi sono equivalenti se e solo se uno dei due appartiene alla classe di equivalenza dell'altro, ovvero se e solo se le classi di equivalenza da essi determinate coincidono; se due classi di equivalenza sono distinte esse sono disgiunte). L'insieme quoziente definito da un'equivalenza.
Partizioni di un insieme. Gli insiemi quoziente sono partizioni.
Esercizi assegnati:
Solita avvertenza: portare con sé, alla prossima lezione, i cinque fogli (tra note e esercizi) già segnalati tra quelli da scaricare da questo sito.
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Restrizioni e immersioni di un sottoinsieme in un insieme. Prolungamenti
e ridotte di applicazioni. Legami tra queste nozioni.
Il numero delle applicazioni e il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti, fattoriali.
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. Descrizione delle retrazioni (da completare). L'inversa di un'applicazione. Un'applicazione è biettiva se e solo se ha inversa (cioè se e solo se è invertibile). 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.
Su questi argomenti verranno presto messe a disposizione delle note.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Determinazione esplicita dei prolungamenti di un'assegnata applicazione ad un assegnato insieme contenente il dominio e delle retrazioni di un'assegnata applicazione iniettiva. Si vedano le note su sezioni e retrazioni.
Condizioni di esistenza di applicazioni inettive o suriettive tra assegnati insiemi finiti: se A e B sono insiemi finiti, allora InjMap(A,B) non è vuoto se e solo se |A|≤|B|; SurMap(A,B) non è vuoto se e solo se |A|≥|B| e, se B=∅, allora A=∅.
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).
Applicazione immagine e applicazione controimmagine (o immagine inversa, o antiimmagine) definita da un'applicazione.
Biezione canonica tra Eq(A) e Part(A) (insiemi delle relazioni di equivalenza e delle partizioni di un insieme A). 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). Anche su questo argomento appariranno presto delle note su questo sito.
Esercizi assegnati: In mancanza di simboli più idonei, per questi esercizi si useranno le notazioni I(f) e A(f) per indicare l'applicazione immagine e l'applicazione controimmagine definite dall'applicazione f.
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Coefficienti binomiali: definizione e proprietà elementari (in mancanza di simboli appositi in HTML, scriviamo qui (n:k) per il coefficiente binomiale n su k): 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); (n+1:k+1)=(n:k)+(n:k+1). Triangolo di Tartaglia-Pascal. Formula esplicita: (n:k)=n!/(n-k)!k!. (con due dimostrazioni, una diretta, un'altra per induzione su n).
Operazioni (binarie, interne) in un insieme. Operazioni associative e operazioni commutative; esempi. Cenni ai teoremi di associatività e di commutatività. Nozione di struttura algebrica. Esempi di strutture associative e non, commutative e non. Parti stabili in una struttura (rispetto ad una operazione).
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Operazioni indotte su parti stabili, sottostrutture; queste ereditano le (eventuali) proprietà associativa e commutativa. Diversi esempi.
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, l'unico simmetrico sinistro di x e l'unico simmetrico destro di x). Interpretazione di queste nozioni nel monoide T(S) delle trasformazioni di un insieme S. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico".
Gruppi, gruppi abeliani. Il gruppo degli invertibili (o simmetrizzabili) U(M) di un monoide M. Formula per l'inversione di un prodotto in un monoide). Il gruppo simmetrico Sym(S):=U(T(S)) su un insieme S. Nozione di permutazione.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Nozione di sottogruppo; caratterizzazione (una parte non vuota H di un gruppo ne è un sottogruppo se e solo se x-1y∈H per ogni x,y∈H. Esempi.
Sym(X) non è abeliano se X è un insieme tale che |X|>2.
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).
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. Isomorfismi. L'importanza della nozione di isomorfismo. Le proprietà algebriche sono invarianti per isomorfismi. Cenno alle tavole di moltiplicazione (di Cayley). Esempi di isomorfismi.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Relazioni d'ordine (o ordinamenti). Ordinamenti stretti ed ordinamenti larghi in un insieme, sostanziale equivalenza tra le due nozioni (biezione tra l'insieme degli ordinamenti stretti e quello degli ordinamenti larghi in un dato 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 minimi, massimi, minimali e massimali, con particolare riferimento agli insiemi sopre citati. Esempi di insiemi con più elementi minimali ed esempio di un insieme con un unico elemento minimale che però non è minimo.
Ogni insieme ordinato finito e non vuoto ha elementi minimali ed elementi massimali.
Relazione di copertura associata ad un ordinamento. Diagrammi di Hasse di un insieme ordinato finito.
Nozione di isomorfismo tra insiemi ordinati. Esempio di un'applicazione crescente e biettiva che non è un isomorfismo tra insiemi ordinati.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Buon ordinamento di (N,≤); giustificazione del principio di induzione, nella prima e nella seconda forma.
Minoranti e maggioranti di parti di un insieme ordinato. Estremo inferiore ed estremo superiore. Diversi esempi, tra cui:
Per una parte T di un insieme ordinato S e per un elemento t∈T sono equivalenti: t=min T; t=inf T; x è un minorante di T. (Vale ovviamente anche l'enunciato duale).
Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli. Il duale di ogni reticolo è un reticolo, si ha quindi un principio di dualità anche per reticoli.
Se A e B sono parti di un insieme ordinato S, entrambe dotate di estremo inferiore in S, allora i minoranti di A∪B sono precisamente quelli di{inf A,inf B}, dunque A∪B ha estremo inferiore se e solo se lo ha {inf A,inf B} e, nel caso questi estremi inferiori esistano, essi coincidono. (Ovviamente vale l'enunciato duale per gli estremi superiori). In ogni reticolo tutte le parti finite non vuote hanno 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).
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).
Sottoreticoli; esempi: intervalli chiusi in un reticolo, Div(n) in (N,|), dove n∈N, ℘(T) in (℘(S),⊆), se T⊆S. Esempio di una parte di un reticolo che non è un sottoreticolo, ma che, munito dell'ordinamento indotto, è un reticolo.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
Complementi di un elemento in un reticolo limitato (cioè con minimo e massimo); diversi esempi; il complemento non è necessariamente unico. Reticoli complementati. Il duale di un reticolo complementato è complementato, un sottoreticolo di un reticolo complementato può non essere complementato.
Isomorfismi tra reticoli (come insiemi ordinati e come strutture algebriche; le due nozioni coincidono).
Reticoli distributivi. Esempi: (&weierp(S),⊆) per un insieme S, (N,|) (senza dimostrazione), catene (cioè: insiemi totalmente ordinati). Ciascuna delle due leggi distributive in un reticolo implica l'altra (senza dimostrazione). I sottoreticoli ed il duale di un reticolo distributivo sono distributivi. In un reticolo distributivo (limitato) ciascun elemento ha al massimo un complemento. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff, con esempi di applicazioni.
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. 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).
Anelli, definizione ed esempi. Anelli commutativi, anelli unitari. Corpi e campi (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).
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente, con particolare attenzione all'anello delle parti di un insieme (ultimo degli esercizi assegnati).
Esempi di anelli: l'anello (non commutativo) M2(R) delle matrici 2×2 su un anello R. Sottoanelli unitari di anelli unitari; un esempio di sottoanello di un anello unitaro che non è un sottoanello unitario pur essendo, per proprio conto, un anello unitario. Operazione opposta e dualità destra-sinistra per semigruppi, monoidi, gruppi, anelli.
Potenze (o, in notazione additiva, multipli) di un elemento secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari per elementi simmetrizzabili di un monoide). Regole di calcolo, tra le quali: per ogni n,m∈Z e per ogni x per cui queste potenze siano definite, xn+m=xnxm e xnm=(xn)m; similmente, in notazione additiva, per i multipli. Inoltre: se due elementi a e b di un monoide commutano (cioè, in notazione moltiplicativa, ab=ba) e a ha simmetrico a' allora a' e b commutano.
Nozione di parte stabile generata e di sottostruttura generata da una parte di una assegnata struttura. Descrizione della parte stabile (cioè sottosemigruppo), del sottomonoide e del sottogruppo generate da un elemento (ovvero da un singleton) nelle opportune strutture. Gruppi ciclici (sono tutti abeliani; esempio: il gruppo additivo degli interi è ciclico, generato da 1).
Regole di calcolo per anelli: per ogni x, y, z in un anello R si ha 0Rx=x0R=0R; (−x)y=x(−y)=−(xy); (x−y)z=xz−yz e dualmente z(x−y)=zx−zy. Se R è unitario (n1R)x=nx per ogni n∈Z.
Esercizi assegnati:
Discussione di uno degli esercizi proposti nella lezione precedente.
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 (costruzione di un reticolo booleano a partire da un anello booleano e costruzione inversa; per quest'ultima la dimostrazione non è stata completata, ciò che manca è tra gli esercizi). Sottoanelli unitari degli anelli boleani ed enunciato del teorema di Stone per anelli booleani.
Formula del binomio di Newton per elementi permutabili in un anello (vedi coefficienti binomiali).
Elementi cancellabili e divisori dello zero negli anelli (vedi cancellabilità). Anelli integri e domini di integrità; legge di annullamento del prodotto. Esempi. I campi sono domini di integrità; i domini di integrità finiti sono campi. Menzione del teorema di Wedderburn (i corpi finiti sono campi).
Equivalenze compatibili con un'operazione binaria ed operazione indotta sul quoziente. Questa è ben definita solo nel caso in cui l'equivalenza sia compatibile con l'operazione.
Esercizi assegnati:
Richiami ed appofondimenti sulle equivalenze compatibili con un'operazione binaria. Discussione approfondita del secondo degli esercizi della lezione precedente.
Congruenze in una struttura algebrica e struttura quoziente. Proprietà che si conservano passando alla struttura quoziente (come associatività, commutatività, esistenza di neutri e simmetrici, idempotenza, distributività); quozienti di semigruppi, monoidi, gruppi, anelli etc. Epimorfismi e monomorfismi. Epimorfismo canonico (cioè proiezione canonica) da una struttura ad un suo quoziente.
Esempio: il monoide delle parole su un alfabeto e la congruenza definita dichiando equivalenti due parole se e solo se hanno la stessa lunghezza (vedi gli esercizi proposti).
Equivalenze compatibili a destra o a sinistra con una operazione binaria. Caratterizzazione delle equivalenze compatibili come equivalenze compatibili sia destra che a sinistra.
Le congruenze in Z (cioè le equivalenze ≡m al variare di m∈Z. Osservazioni: ≡0 è la relazione universale; ≡1 è l'uguaglianza; per ogni m∈Z, ≡m e ≡-m coincidono. Verifica diretta del fatto che tutte queste sono congruenze nell'anello (Z,+,⋅). È stato solo enunciato che queste sono le sole congruenze di (Z,+). Per queste dimostrazioni è stato anche osservato che in ogni anello commutativo R un elemento che divida due elementi ne divide tutte le combinazioni lineari a coefficienti in R.
Gli anelli quoziente Zm. Descrizione dei loro elementi (per ogni m∈N#, Zm ha esattamente m elementi: le classi di resto [0]m, [1]m, …, [m−1]m). Divisione (aritmetica) con resto in Z: (∀a∈Z)(∀b∈Z−{0}) (∃!(q,r)∈Z×Z)(a=bq+r ∧ 0≤r<|b|). La ‘operazione’ mod in Z.
Esempi di calcoli in aritmetica modulare (calcolo di potenze).
Esercizi assegnati:
Discussione approfondita di alcuni degli esercizi della lezione precedente.
Le congruenze in Z come nuclei di equivalenza delle applicazioni resto: due interi sono congrui modulo un intero positivo m se e solo se hanno lo stesso resto nella divisione per m. Per ogni a ed m in Z, la classe di resto di a modulo m è a+mZ.
Rappresentazione degli interi positivi in base 10 e criteri di divisibilità per 2, 5, 4, 25, 8, etc., 3, 9, 11, in N; ‘prova del nove’. Osservazione: se due interi sono congrui modulo un intero m, essi sono congrui modulo ogni divisore di m. Ulteriori esempi di calcoli in aritmetica modulare.
Periodo di un elemento in un gruppo. Elementi periodici ed aperiodici. Esempi. L'elemento neutro di un gruppo è l'unico elemento di periodo 1. 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. Utilizzo di queste osservazioni per i calcoli di potenze in aritmetica modulare. Caratteristica di un anello unitario; esempio: caratteristica dei quozienti di Z.
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|). "Stringhe di zeri ed uno" (viste come funzioni caratteristiche) ed anelli booleani; un esempio di isomorfismo.
Esercizi assegnati:
Discussione di alcuni degli esercizi della lezione precedente.
Fattorizzazione in monoidi commutativi. Caratterizzazioni della nozione di elemento associato: fissato un monoide commutativo (M,⋅), se a,b∈M, allora a e b sono associati se e solo se hanno gli stessi divisori, ovvero se e solo se hanno gli stessi multipli. Inoltre, se a è cancellabile, a e b sono associati se e solo se b=au per un opportuno u∈U(M). Monodi regolari. Se M è regolare la relazione di divisibilità in M è un ordinamento se e solo se l'unità è l'unico invertibile in M.
Per monoidi commutativi regolari: divisori banali e fattorizzazioni non banali. Elementi irriducibili, Fattorizzazioni "essenzialmente uguali" (cioè uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati). Monoidi fattoriali. Diversi esempi: Teorema fondamentale dell'aritmetica (fattorialità dei monoidi moltiplicativi degli interi positivi e degli interi non nulli). (Si è dimostrata l'esistenza di fattorizzazioni in irriducibili per gli elementi non invertibili, non l'essenziale unicità delle stesse); sono anche fattoriali i gruppi e il monoide (N,+,0). mentre non lo è il monoide additivo dei razionali non negativi (in cui non esistono irriducibili). Un esempio di monoide commutativo regolare non fattoriale in cui ogni elemento non invertibile è prodotto di irriducibili è tra gli esercizi assegnati. Nozione di anello fattoriale (esempi: Z, i campi). Elementi primi (essi sono sempre irriducibili) e 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).
Fattorizzazione primaria di un elemento a in un monoide fattoriale e utilizzo di questa per la determinazione dei divisori di a. In maggior dettaglio è stato considerato il caso dei monoidi (N#,⋅) e (Z#,⋅). In questi due casi: calcolo del numero dei divisori.
Esercizi assegnati:
Discussione di alcuni degli esercizi della lezione precedente.
Richiami sui massimi comuni divisori e sui minimi comuni multipli. In ogni semigruppo commutativo i massimi comuni divisori di una parte assegnata costituiscono una classe di elementi associati; simile enunciato vale per i minimi comuni multipli. Espressione (dunque anche esistenza) di un massimo comun divisore d e di un minimo comune multiplo m tra due elementi a e b di un monoide fattoriale. Si ha che dm è associato ad ab.
Algoritmo euclideo delle divisioni successive per la determinazione di un massimo comun divisore tra due interi. Esempi, giustificazione dell'algoritmo, qualche idea per la sua velocizzazione. Divisione euclidea tra due interi a e b (se a,b∈Z e b≠0, esistono interi q ed r tali che a=bq+r e |r|≤|b/2|).
Estensione dell'algoritmo euclideo e Teorema di Bézout (la dimostrazione fornita è quella, costruttiva, 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 diofantee (di primo grado, a due indeterminate). Criterio di esistenza di soluzioni. Determinazione dell'insieme di tutte le soluzioni.
Equazioni congruenziali (di primo grado). Equivalenza tra il problema di risolvere una equazione diofantea e quello di risolvere un'equazione congruenziale (dei tipi considerati). Criterio di esistenza di soluzioni per le equazioni congruenziali.
Elementi invertibili nei quozienti di Z: caratterizzazione. Se m∈N#, l'anello Zm è un campo se e solo se m è primo (ciò equivale anche all'essere Zm integro).
Esercizi assegnati:
Equazioni congruenziali (di primo grado): metodi di semplificazione e di soluzione, illustrati anche su alcuni degli esercizi della lezione precedente; determinazione dell'insieme di tutte le soluzioni. Diversi esempi e discussione dei possibili errori. Osservazioni sugli inversi in aritmetica modulare (con applicazioni alle equazioni congruenziali) e sui possibili metodi di calcolo. Notazione "a-1 mod m".
La funzione di Eulero. Numero degli invertibili in un quoziente di Z. Metodi di calcolo; esempi.
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 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; esempi.
Esercizi assegnati:
L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario. Definizione e prime proprietà. Proprietà universale per gli 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".
Terminologia essenziale: successione dei coefficienti di un polinomio, grado e coefficiente direttore di un polinomio non nullo, termine noto, polinomi costanti, polinomi monici.
Per ogni anello commutativo A, A[x] è infinito e non è un campo (x non è invertibile).
Grado della somma, della differenza e 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.
Per polinomi su un campo: Algoritmo euclideo per la ricerca del massimo comun divisore e Teorema di Bézout. Esistenza e unicità del MCD monico tra due polinomi non nulli nell'anello dei polinomi su un campo (come conseguenza del fatto che, se K è un campo, 0≠k∈K e 0≠f∈K[x], allora tra gli associati di f in K[x] esiste uno ed un solo polinomio di coefficiente direttore k; in particolare f ha esattamente un associato 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:
Osservazioni elementari: se un polinomio g divide un polinomio f allora le radici di g sono anche radici di f; se f e g sono associati allora essi hanno le stesse radici. Applicazione del teorema di Ruffini: le radici comuni a un insieme di polinomi sono le radici di un loro massimo comun divisore (qualora questo esista).
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 né su anelli booleani.
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.
Informazioni: hanno radici nel campo complesso C tutti i polinomi non costanti in C[x], dunque i polinomi irriducibili in C[x] sono tutti e soli quelli di grado 1. Inoltre, ogni polinomio di grado dispari in R[x] ha radici nel campo reale R; i polinomi irriducibili in R[x] hanno grado al più 2.
Alcuni metodi di fattorizzazione per polinomi. 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.
Cenni ai polinomi su quozienti di Z.
Esercizi assegnati:
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 (ovvero: piano). Terminologia: vertici, lati, adiacenza, incidenza, grado, vertici isolati. Grafi completi, grafo complementare di un grafo.
Isomorfismi tra grafi e proprietà che questi conservano. Esempi di grafi isomorfi e non, tecniche di costruzione di isomorfismi.
Teorema: il doppio del numero dei lati di un multigrafo finito è la somma dei gradi dei suoi vertici. Vertici pari e vertici dispari; questi ultimi sono in numero pari.
Cammini e circuiti. Relazione di connessione; (multi)grafi connessi. Sottografi. Componenti connesse.
Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari (solo enunciato). Esempi, tra cui il problema dei sette ponti di Königsberg.
Enunciato del teorema di Kuratowski sui (multi)grafi planari.
Definizione di foresta e di albero. Teorema: un grafo 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.
Metodi di costruzione di grafi finiti con assegnati invarianti; alcuni esempi (tra cui: tutti i grafi semplici su al più quattro vertici, elencati a meno di isomorfismi).
Esercizi assegnati:
Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso finito.
Nozione di distanza in multigrafi ed alberi. Rappresentazione radicale di un albero; foglie. Come conseguenza: gli alberi finiti sono grafi planari (e di conseguenza sono planari le foreste finite). Inoltre, in ogni albero finito con almeno due vertici esistono almeno due vertici di grado uno.
Lemma: 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).
Richiami sulle permutazioni; e sul gruppo simmetrico su un insieme; i gruppi Sn.
Cicli, trasposizioni. Periodo di un ciclo. Decomposizione di un ciclo di lunghezza k nel prodotto di k−1 trasposizioni. Supporto di una permutazione, permutazioni disgiunte. Permutazioni disgiunte commutano (ma non vale il viceversa). Decomposizione di una permutazione (su un insieme finito) in prodotto di cicli a due a due disgiunti. Uso di tale decomposizione per effettuare calcoli di potenze di una permutazione e per calcolarne il periodo. Diversi esempi.
Fattorizzazione (non unica!) di una permutazione su un insieme finito in prodotto di trasposizioni. Parità di una permutazione. Molte di queste nozioni sulle permutazioni 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 di classe pari e di classe dispari.
Esercizi assegnati: