Introduzione al corso: presentazione; informazioni generali; modalità di svolgimento.
Rudimenti di logica proposizionale. Nozione informale di proposizione (in termini solo semantici). I principali connettivi proposizionali (anch'essi descritti solo semanticamente): negazione, congiunzione, disgiunzione (inclusiva), disgiunzione esclusiva, condizionale (o implicazione), bicondizionale (o equivalenza). Tabelle (o tavole) di verità, con esempi del loro uso. Tautologie, contraddizioni e forme contingenti. Forme logicamente equivalenti. Alcune tautologie classiche: principî del terzo escluso e di non contraddizione, leggi di De Morgan, bicondizionale come doppia implicazione, 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 le prossime lezioni sarà bene avere queste tre note con sé.
Si ricorda che la prossima lezione si terrà lunedì 5 ottobre.
Esercizi assegnati:
Verificare poi che anche le due forme proposizionali (¬p) ⇔ q e p ⇔ (¬q) sono logicamente equivalenti a p XOR q (e quindi a ¬(p ⇔ q)).
Discussione di alcuni esercizi proposti nella lezione precedente. In particolare: legge di contapposizione e negazione del bicondizionale con la disgiunzione esclusiva.
Altre tautologie; lettura di esempi di tautologie e discussione su tavola dei connettivi binari.
Cenni alla logica dei predicati. Costanti e variabili; quantificatori: universale (∀) ed esistenziale (∃) e loro uso. Cenni alle nozioni di occorrenza libera e legata di una variabile; le formule contenenti variabili in occorrenze libere non sono proposizioni. Frasi contenenti più quantificatori (esempi di frasi delle forme ∀x∃y… o ∃y∀x…). Predicati. Negazioni di frasi introdotte da quantificatori. Il quantificatore ∃!, definito ponendo (∃!x)(p(x)) equivalente a (∃x)(∀y)(p(x)⇔x=y).
Nozione (solo 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à).
Inclusione tra insiemi: per definizione, (∀A,B)(A⊆B ⇔ (∀x)(x∈A⇒x∈B)). La regola della "doppia inclusione": (∀ A,B)(A=B ⇔ (A⊆B ∧ B⊆A)). Distinzione tra appartenenza e inclusione. Il singleton di un insieme.
Alcuni modi per descrivere insiemi; cenni a problemi fondazionali ed al paradosso di Russell.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente. Come conseguenza di assiomi della teoria degli insiemi (della teoria a cui, implicitamente facciamo riferimento noi), si ha: (∀x)(x ∉ x), dunque x ≠ {x}.
Sottoinsiemi (o parti) di un insieme. L'insieme ℘(S) delle parti di un insieme S. Qualunque sia S, si ha ∅ ∈ ℘(S) e S ∈ ℘(S).
Assioma di separazione. Descrizione di insiemi tramite espressioni del tipo { x ∈ S | p(x) } per un predicato p(x). Non esiste “l'insieme di tutti gli insiemi”.
Proposizioni della forma (∀x ∈ S)(p(x)) e della forma (∃x ∈ S)(p(x)); loro negazioni; se S è l'insieme vuoto le prime proposizioni sono sempre vere, le seconde sempre false.
Predicati definiti in un insieme S e parti di S. Rapporti tra connettivi proposizionali e nozioni insiemistiche: bicondizionale ed uguaglianza, inclusione e implicazione; operazioni insiemistiche (binarie) di unione e intersezione e loro corrispettivi nel calcolo proposizionale. Lettura di una parte tautologie e identità insiemistiche (proprietà associativa, commutativa, iterativa, distributiva). Complemento relativo (differenza) tra insiemi. Diagrammi di Euler-Venn. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare identità insiemistiche.
Differenza simmetrica tra due insiemi e disgiunzione esclusiva (XOR). Associatività del connettivo bicondizionale (⇔).
Esercizi assegnati:
Discussione di molti degli esercizi proposti nella lezione precedente. Ulteriori esempi di dimostrazioni della verità o falsità di identità insiemistiche tramite diagrammi di Venn.
Equivalenza logica tra le forme proposizionali (a⇔b)⇔c e (a XOR b) XOR c; associatività del connettivo XOR e associatività della differenza simmetrica.
Completamento di tautologie e identità insiemistiche.
Descrizione di un insieme con scritture del tipo {t(x,y,z,…) | p(x,y,z,…)} (abbreviazione di {a | (∃x,y,z,…)(a=t(x,y,z,…) ∧ p(x,y,z,…)}).
Unione e intersezione unarie, cioè unione di un insieme e intersezione di un insieme non vuoto; estensioni a queste operazioni delle leggi di De Morgan.
Cardinalià di un insieme finito. Cardinalità della differenza tra due insiemi finiti. Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti, con verifica dettagliata nel caso dell'unione di due insiemi.
Un cenno introduttivo al principio di induzione. Come applicazione, cardinalità dell'insieme delle parti di un insieme finito: per ogni tale insieme S si ha |℘(S)|=2|S|.
Coppie ordinate. Il prodotto cartesiano A × B tra due insiemi A e B. Se A e B sono insiemi finiti si ha |A × B|=|A| · |B|.
Esercizi assegnati:
Discussione sugli esercizi proposti nella lezione precedente.
Corrispondenze tra insiemi. Relazioni binarie in un insieme. Introdotte le notazioni: Corr(A,B) (insieme delle corrispondenze da A a B) e Rel(A) (=Corr(A,A); insieme delle relazioni binarie in A) con riferimento ad insiemi A e B. Notazione infissa per corrispondenze e relazioni. Esempi.
Diversi modi per descrivere corrispondenze; rappresentazioni grafiche di corrispondenze e relazioni, via diagrammi o tabelle.
Prodotto relazionale tra corrispondenze; corrispondenze componibili. Corrispondenza inversa di una corrispondenza. Esempi. Associatività del prodotto relazionale.
Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche, antisimmetriche, transitive. Confronto tra queste proprietà; negazione di ciascuna di esse. Esempi. Espressione di queste proprietà in termini di proprietà (insiemistiche) del grafico della relazione. La diagonale ΔA={(x,x) | x∈A} di A. Relazioni di equivalenza e relazioni d'ordine (stretto o largo) in un insieme.
Esercizi assegnati:
Discussione di esercizi proposti nella lezione precedente.
Applicazioni tra insiemi. Dominio e codominio. Il problema della "buona" (corretta) definizione di un'applicazione; vari esempi. Nel corso della presentazione di alcuni esempi è stato definito, per ogni insieme S e per ogni k ∈ N, l'insieme ℘k(S) delle k-parti di S.
Diversi modi per rappresentare le applicazioni (oltre alle notazioni più usuali, rappresentazioni tramite diagrammi e come matrici a due righe). Diverse notazioni (sinistra, destra, esponenziale, a pedice: f(a), fa, (a)f, af, af, fa) per indicare l'immagine mediante un'applicazione f di un elemento a del suo dominio.
L'immagine im f di un'applicazione f.
Introdotte le notazioni Map(A,B), BA e AB per l'insieme delle applicazioni dall'insieme A all'insieme B. Nel caso in cui A e B siano finiti, la cardinalità di questo insieme è |B||A|.
Il prodotto relazionale tra due applicazioni (componibili) è un'applicazione, ciò permette di definire il prodotto operativo (o composizione) tra 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.
L'applicazione identica idA in un insieme A; è quella con dominio e codominio A che manda ogni elemento in sé. Neutralità dell'applicazione identica (componendo a destra o a sinistra una corrispondenza α per un'applicazione identica si ottiene α).
Applicazioni iniettive e applicazioni suriettive. Negazione di iniettività e suriettività; esempi. Applicazioni biettive. Un'osservazione fatta: ogni applicazione il cui dominio abbia meno di due elementi è iniettiva.
L'immersione in un insieme di una sua parte (se Y è una parte di X, l'immersione di Y in X è l'applicazione y ∈ Y → y ∈ X).
La composta di due applicazioni iniettive (risp. suriettive, biettive) è necessariamente iniettiva (risp. suriettiva, biettiva).
Se il prodotto fg di due applicazioni è iniettivo allora il primo fattore, f, è iniettivo; se invece fg è suriettivo allora g è suriettivo (questo è il primo enunciato in Sezioni e Retrazioni, d'ora in avanti portare con sé queste note a lezione). Esempi e controesempi.
Esercizi assegnati:
Discussione di alcuni esercizi sulla lezione precedente.
Restrizioni, prolungamenti e ridotte di un'applicazione. Alcune osservazioni: se X ⊆ A l'immersione ι : X→A è la restrizione ad X dell'applicazione identica di A; se f : A→B è un'applicazione allora la restrizione f|X è il prodotto ιf, mentre se h : A→C è una ridotta di f (quindi im f ⊆ C ⊆ B) allora f = hj, dove j è l'immersione di C in B.
Applicazione immagine f→: ℘(A) → ℘(B) ed applicazione antiimmagine f←:℘(B) → ℘(A) definite da un'applicazione f : A → B.
Sezioni e retrazioni di un'applicazione. Un'applicazione è suriettiva se e solo se ha sezioni; un'applicazione è iniettiva se e solo se o ha dominio vuoto oppure ha retrazioni. Prima introduzione alla coimmagine di un'applicazione; descrizione dell'insieme di tutte le sezioni di una data applicazione suriettiva (e, nel caso finito, cardinalità di questo insieme) e descrizione, ancora da rifinire, dell'insieme di tutte le retrazioni di una data applicazione iniettiva. Un'applicazione che abbia esattamente una sezione è necessariamente biettiva (e viceversa); un'applicazione il cui dominio abbia più di un elemento è biettiva se e solo se ha una ed una sola retrazione.
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.
Importanza della nozione di invertibilità. Una discussione di carattere generale: come vengono descritti insiemi tramite applicazioni biettive tra essi ed insiemi già ben descritti. La nozione di equipotenza. Un esempio: descrizione esplicita dell'insieme dei prolungamenti di un'assegnata applicazione f : S→T ad un insieme X contenente S: biezione tra questo insieme e Map(X - S,T).
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Completamento della descrizione dell'insieme di tutte le retrazioni di una data applicazione iniettiva; nel caso finito è stata calcolata la cardinalità di questo insieme (enunciati 11 e 12 in Sezioni e retrazioni). Un esempio tratto dagli esercizi proposti.
Il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti nm = n(n−1)(n−1)…(n−m+1). Il fattoriale n!=1·2·3·…·n di un numero naturale. 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 B=∅ ⇒ 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). Si noti che questa proprietà vale solo nel caso delle applicazioni tra insiemi finiti.
Trasformazioni di un insieme S (cioè applicazioni da S in S) e permutazioni (cioè trasformazioni biettive). Se S è un insieme finito di cardinalità n, l'insieme delle permutazioni di S ha cardinalità n!
Classi di equivalenza ed insieme quoziente definito da una relazione di equivalenza. Proprietà fondamentali delle classi di equivalenza: fissata una relazione di equivalenza ρ in un insieme A, per ogni a, b ∈ A si ha
Qualche esempio. Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione. Ogni equivalenza è il nucleo di equivalenza di un'applicazione (specificamente, della proiezione canonica che essa definisce, dall'insieme su cui la relazione è definita al suo insieme quoziente.
Partizioni di un insieme. Gli insiemi quoziente sono partizioni, e viceversa. In modo più esplicito: biezione canonica tra Eq(A) e Part(A) (insiemi delle relazioni di equivalenza e delle partizioni di un insieme A): questa applicazione associa ad ogni ρ ∈ Eq(A) l'insieme quoziente A/ρ ed è, appunto, biettiva. La sua inversa è l'applicazione che ad ogni partizione P di S associa il nucleo di equivalenza dell'applicazione da S a P che ad ogni x ∈ S associa l'elemento di P a cui x appartiene.
Tra gli esempi sono stati menzionate le partizioni banali, cioè quelle corrispondenti alle equivalenze banali in un insieme S (uguaglianza e relazione universale; i corrispondenti quozienti, cioè le partizioni banali sono, nell'ordine {S} e ℘1(S)). Altro esempio importante: la relazione di equivalenza definita nell'esercizio 1.a in relazioni binarie e la partizione di Z costituita dall'insieme dei numeri interi pari e dall'insieme dei numeri interi dispari.
Oltre alle note già utilizzate, dalla prossima lezione portare con sé le note sul Teorema di Omomorfismo per Insiemi e sui Coefficienti Binomiali.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente. Richiami su: relazioni di equivalenza, nuclei di equivalenza, partizioni. Esempi.
La coimmagine di un'applicazione, vista come insieme quoziente determinato dal suo nucleo di equivalenza.
Teorema di omomorfismo per insiemi (fattorizzazione canonica di un'applicazione). Esempi di applicazioni di questo teorema per il calcolo della cardinalità dell'insieme quoziente rispetto ad una relazione di equivalenza.
Coefficienti binomiali. Si è discusso il contenuto delle prime tre pagine delle note su questo argomento cioè sino all'enunciato numero 4 incluso. La pagina che segue sarà discussa in una lezione nelle prossime settimane.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Operazioni (binarie, interne, ovunque definite) in un insieme. Operazioni associative e operazioni commutative; esempi. Nozione di struttura algebrica. Esempi di strutture associative e non, commutative e non. Cenno ai teoremi di associatività e di commutatività.
Parti stabili in una struttura (rispetto ad una operazione); nozione di operazione indotta e di sottostruttura. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà. Esempi. La parte stabile generata da una parte in una struttura; 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, anzi, è l'unico elemento neutro a destra o sinistra). Esempi, tra cui quello di una struttura associativa (semigruppo) con più di un elemento neutro a destra.
Nozione di operazione opposta e cenno alla dualità destra-sinistra.
Semigruppi e monoidi. Tra gli esempi: il monoide T(X) delle trasformazioni di un insieme X (non è commutativo se |X|>1).
Notazioni per le strutture algebriche che coinvolgano anche operazioni unarie o nullarie, come nel caso dei monoidi. Esempi, come (N,+,0), (T(X),·,idX), (℘(X),&cup,∅), per un insieme X.
Simmetrici destri e sinistri in una struttura con elemento neutro; simmetrici, elementi simmetrizabili. Interpretazione di queste nozioni nel monoide T(X) delle trasformazioni di un insieme X.
Dalla prossima lezione sarà utile avere con sé le note sulla cancellabilità
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Sottostrutture. Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che non sono monoidi oppure sono monoidi ma non sottomonoidi.
Unicità dei simmetrici nei monoidi: se, per un elemento x di un assegnato monoide M, 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 in M. Ancora un richiamo al monoide T(X) delle trasformazioni di un insieme X. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico".
Gruppi. Esempi, come (Z,+,0,−), (℘(X),Δ,∅,id), (Q-{∅}, ⋅ ,1,−1). Gruppi abeliani.
Il gruppo degli invertibili (elementi simmetrizzabili) U(M) di un monoide M. Formula per il calcolo del simmetrico di un prodotto in un monoide (in notazione moltiplicativa, per ogni a, b ∈ U(M) si ha (ab)−1 = b−1a−1). Esempi, tra i quali il gruppo {1,−-1} degli invertibili in (Z,⋅ ) e il gruppo simmetrico Sym(X):=U(T(X)) su un insieme X; se |X| ≥ 3 questo è un gruppo non abeliano. Cicli (permutazioni cicliche); trasposizioni (cicli d lunghezza 2). Ogni ciclo è prodotto di trasposizioni, infatti ogni ciclo (a1 a2 … ak) si può fattorizzare come (a1 a2)(a1 a3)(a1 a4) … (a1 ak). Notazione: Sn = Sym({1,2,3,…,n}).
Sottogruppi; loro caratterizzazione: una parte non vuota H di un gruppo (G,∗) ne costituisce un sottogruppo se e solo se x' ∗ y ∈ H per ogni x, y ∈ H (qui x' indica il simmetrico di x) o, equivalentemente, se e solo se x ∗ y' ∈ H per ogni x, y ∈ H.
Omomorfismi tra strutture algebriche. Omomorfismi di semigruppi e di monoidi. Monomorfismi, epimorfismi, isomorfismi. Esempi. Discussione sulla nozione generale di isomorfismo. Invarianza delle proprietà algebriche per isomorfismi. Tavole di Cayley (ovvero di moltiplicazione) per operazioni binarie. Esempi: isomorfismo tra i gruppi S2 e ({1,−1},⋅); tutti i gruppi di cardinalità 2 sono tra loro isomorfi (come è stato dimostrato descrivendone le tavole di Cayley). Visualizzazione di proprietà tramite tavole di Cayley: commutatività, esistenza di neutri e di simmetrici.
Esercizi assegnati:
Discussione di esercizi proposti nella lezione precedente.
Isomorfismo tra Sym X e Sym Y laddove X e Y siano insiemi equipotenti (vedi esercizi).
Omomorfismi di semigruppi, di monoidi e di gruppi. Esempi. (L'esistenza di neutri e di simmetrici è preservata dagli isomorfismi, non da tutti gli omomorfismi.) Gli omomorfismi di semigruppi tra due gruppi sono isomorfismi tra gruppi, come è stato dimostrato più avanti nel corso della lezione.
Elementi cancellabili, a sinistra o a destra rispetto ad un'operazione binaria; elementi cancellabili. Rapporto tra simmetrizzabilità e cancellabilità in un monoide. Esempi. Equivalenza tra cancellabilità e simmetrizzabilità per semigruppi finiti. I semigruppi finiti ad elementi tutti cancellabili sono gruppi. Visualizzazione della cancellabilità sulle tavole di Cayley. Esempio: tavola di Cayley di un gruppo di cardinaltà 3 (i gruppi di cardinalità 3 sono a due a due isomorfi; in effetti si può dimostrare lo stesso per i gruppi di cardinalità p per ogni primo p). Esempio di due gruppi non isomorfi di cardinalità 4 (i soli, a meno di isomorfismi).
Potenze 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: per ogni elemento x di un semigruppo e per ogni n, m ∈ Z per cui xn e xm siano definite, xn+m= xnxm e xnm= (xn)m. (Solo della prima di queste due formule è stata data una parziale dimostrazione). Potenze (o multipli) secondo interi di uno stesso elemento di un semigruppo commutano sempre tra loro.
Ulteriore osservazione: se a e b sono elementi di un monoide che commutino tra loro e b è invertibile, allora anche a e l'inverso di b commutano tra loro.
Anelli, anelli commutativi, anelli unitari. Esempi: (Z,+,⋅), (Q,+,⋅), (℘(S),Δ,∩). Sottoanelli.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Richiamo sulle potenze e sulle loro proprietà; loro espressione in notazione additiva (cioè come multipli secondo interi). Sottosemigruppi, sottomonoidi e sottogruppi generati da singleton. Gruppi ciclici. Esempio: il gruppo (Z,+) è ciclico.
Nozione di sottoanello unitario di un anello unitario. Esempi sottoanelli di un anello unitario che non sono unitari oppure lo sono ma non come sottoanelli. Omomorfismi di anelli e di anelli unitari. Esempi.
Notazioni e regole di calcolo negli anelli: per ogni coppia di elementi a e b dell'anello R si scrive a − b per a + (−b); si ha a0 = 0a = 0 e a(−b) = −(ab) = (−a)b; dove 0 è lo zero di R e, per ogni x ∈ R, con −x si indica l'opposto (cioè il simmetrico nel gruppo additivo) di x. Conseguenza: se |R| > 1, lo zero di R non è invertibile (cioè simmetrizzabile rispetto alla moltiplicazione in R). Corpi e campi. Esempi. In ogni anello unitario R si ha (n1R)x = nx per ogni n ∈ Z. Formula del binomio di Newton.
Definizione di anello booleano. Cenno agli anelli di matrici, come esempi di anelli non commutativi. Cancellabilità negli anelli; divisori dello zero; anelli integri e domini di integrità (si veda la seconda parte delle note sulla cancellabilità).
Relazione di divisibilità in semigruppi e monoidi commutativi. Elementi associati. La relazione "essere elementi associati" in un monoide commutativo M: si tratta di una relazione di equivalenza e si può caratterizzare in questo modo: due elementi a e b di M sono associati se e solo se l'insieme dei divisori in M di a coincide con l'insieme dei divisori in M di b o, equivalentemente, se e solo l'insieme aM dei multipli in M di a coincide con bM (l'insieme dei multipli di b). Inoltre, se a è cancellabile, a e b sono associati se e solo se b = au per un opportuno u∈U(M).
Equivalenze compatibili con un'operazione binaria. Esempio: l'equivalenza in Z definita dichiarando equivalenti due interi se e solo se essi sono o entrambi positivi, o entrambi negativi o entrambi zero è compatibile con l'usuale moltiplicazione ma non con l'usuale addizione in Z.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Relazione di divisibilità in anelli commutativi. Se R è un anello commutativo, un elemento che divida due elementi ne divide tutte le combinazioni lineari a coefficienti in R.
Una parentesi: insiemi ordinati; relazione d'ordine (largo) indotta su una parte di un insieme ordinato. Nozione di minimo e unicità di questo. Buon ordinamento di N (rispetto all'ordinamento usuale), giustificazione del principio di induzione; cosidetta `seconda forma' del principio di induzione, argomentazione per "controesempio minimo".
Operazione indotta sul quoziente determinato da un'equivalenza compatibile con un'operazione binaria. Questa è ben definita solo nel caso in cui l'equivalenza sia compatibile con l'operazione. Esempi.
Esempio: il monoide delle parole su un alfabeto e la congruenza definita in esso dichiarando equivalenti due parole se e solo se hanno la stessa lunghezza. Più in generale, se f è un omomorfismo definito in una struttura algebrica (S,&lowast), il nucleo di equivalenza di f è una congruenza.
Equivalenze compatibili a destra o a sinistra con una operazione binaria. Caratterizzazione delle equivalenze compatibili come equivalenze compatibili sia destra che a sinistra. Congruenze in una struttura algebrica e struttura quoziente. Epimorfismo canonico (cioè proiezione canonica) da una struttura ad un suo quoziente. Proprietà che si conservano passando alla struttura quoziente (come associatività, commutatività, esistenza di neutri e simmetrici, distributività); i quozienti di semigruppi, monoidi, gruppi, anelli, anelli unitari sono strutture dello stesso tipo.
Le congruenze in Z (cioè le equivalenze ≡m al variare di m ∈ Z). Osservazioni: ≡1 è la relazione universale; ≡0 è l'uguaglianza; per ogni m∈Z, ≡m e ≡-m coincidono. Verifica diretta del fatto che tutte queste sono congruenze nell'anello (Z,+,⋅). Gli anelli quoziente Zm. Descrizione esplicita delle classi resto: per ogni m, a∈Z, la classe di resto [a]m di a modulo m è a+mZ={a+mk | k∈Z}. L'operazione parziale mod (per ogni a,m ∈ Z, se m≠0, a mod m è, per definizione, il minimo numero naturale in [a]m). Divisione (aritmetica) con resto in Z: (∀a ∈ Z)(∀b∈Z−{0}) (∃!(q,r)∈Z×N)(a=bq+r ∧ r<|b|). Con queste notazioni, il resto r coincide con a mod b. Descrizione esplicita dei quozienti di Z: per ogni intero positivo m, Zm ha esattamente m elementi: le classi di 0, 1, 2, …, m−1.
Esercizi assegnati:
Discussione sugli esercizi proposti nella lezione precedente.
Le congruenze ≡m sono le sole congruenze di (Z,+); questo fatto non è stato dimostrato. Per ogni m ∈ N#, il gruppo additivo di Zm è ciclico di cardinalità m. A meno di isomorfismi, questi gruppi e (Z,+) sono i soli gruppi ciclici; anche queso fatto non è stato dimostrato.
Calcoli in aritmetica modulare (calcolo di somme, prodotti, potenze). Diversi esempi. 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.
Periodo di un elemento in un gruppo. Elementi periodici ed aperiodici. Esempi: il periodo (in un gruppo simmetrico) di un ciclo di lunghezza k è precisamente k; elementi periodici e aperiodici in (Q#,⋅). In qualsiasi gruppo, l'elemento neutro è l'unico elemento di periodo 1.
Se un elemento x di un gruppo ha periodo finito λ, allora, per ogni n, m ∈ Z, si ha xn=xm se e solo se n e m sono congrui modulo λ. In particolare, xn=1 se e solo se λ divide n; e l'inverso di x è xλ−1.
Utilizzo di queste osservazioni per i calcoli di potenze in aritmetica modulare. Notazione: a−1 mod m.
Caratteristica di un anello unitario. Esempi. In un anello unitario di caratteristica positiva λ si ha λx=0 per ogni elemento x.
Richiami sugli insiemi ordinati. Ogni ordinamento largo su un insieme X definisce in modo canonico un ordinamento stretto su X. Il viceversa sarà discusso nella prossima lezione.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Insiemi ordinati. Biezione canonica tra l'insieme degli ordinamenti stretti e quello degli ordinamenti larghi in un dato insieme (e, quindi, sostanziale equivalenza tra le due nozioni); esempi. Alcuni insiemi ordinati: i reali, razionali, gli interi, i naturali, ordinati secondo l'ordinamento usuale, i naturali ordinati per divisibilità; l'insieme delle parti di un insieme, ordinato per inclusione. Elementi confrontabili e non confrontabili. Ordinamenti totali. Ordinamento duale (cioè relazione inversa di una relazione d'ordine; anch'essa è una relazione d'ordine). Principio di dualità. Nozione di massimo (duale di minimo) in un insieme ordinato. Elementi minimali e massimali. Ancora sull'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. 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. Diagrammi di Hasse di insiemi ordinati finiti; relazione di copertura associata ad un ordinamento.
Isomorfismi tra insiemi ordinati. Esempio di un'applicazione crescente e biettiva che non è un isomorfismo tra insiemi ordinati.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Minoranti e maggioranti di parti in un insieme ordinato. Estremo inferiore ed estremo superiore. Diversi esempi, tra cui:
Massimo comun divisore e minimo comune multiplo di una parte X in un semigruppo commutativo S. L'insieme dei mcd di X in S o è vuoto o è una classe completa di elementi associati (cioè una classe di equivalenza rispetto alla relazione 'essere elementi associati') in S. Analogo enunciato vale per l'insieme dei mcm di X in S.
Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli. Il duale di ogni reticolo è un reticolo; principio di dualità per reticoli.
In ogni reticolo, ogni elemento minimale (risp. massimale) è minimo (risp. massimo). Reticoli limitati (cioè con minimo e massimo). I reticoli finiti sono limitati (ma non vale il viceversa).
Se A e B sono parti di un insieme ordinato S, entrambe dotate di estremo inferiore in S, e anche {inf A,inf B} ha estremo inferiore t in S, allora t è anche inf(A∪B). (Ovviamente vale l'enunciato duale per gli estremi superiori). Di conseguenza: in ogni reticolo tutte le parti finite non vuote hanno estremo inferiore ed estremo superiore. Reticoli completi (esempio: l'insieme delle parti di un insieme, ordinato per inclusione).
Reticoli come strutture algebriche; operazioni reticolari. Esempio: per un insieme S, (℘(S),⊆) e (℘(S),∧,∨). Equivalenza tra lo studio dei reticoli come strutture ordinate e dei reticoli come strutture algebriche.
Isomorfismi tra reticoli (come insiemi ordinati e come strutture algebriche; le due nozioni di isomorfismo coincidono).
Sottoreticoli; esempi, tra cui gli 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, munita dell'ordinamento indotto, è un reticolo.
Complementi di un elemento in un reticolo limitato; esempi; il complemento non è necessariamente unico. Reticoli complementati. Un sottoreticolo di un reticolo complementato può non essere complementato.
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 dei un reticoli distributivi sono distributivi. In un reticolo distributivo (limitato) ciascun elemento ha al massimo un complemento (questo fatto non è stato dimostrato ma lo sarà nella prossima lezione). Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff.
Reticoli booleani: definizione; un esempio.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Il duale di un reticolo complementato (risp. distributivo, booleano) è necessariamente complementato (risp. distributivo, booleano). Dimostrazione dell'unicità del complemento in un reticolo distributivo.
Esempi di uso del criterio di distributività di Birkhoff. Distributività delle catene.
Esempi di reticoli booleani. Operazione unaria di complemento (') e algebre di Boole. Equivalenza tra le nozioni di reticolo booleano e di algebra di Boole. Dualità per algebre 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. Il booleano di un insieme. Sottoalgebre di Boole. Enunciato del teorema di Stone (nel caso finito e, poi, nel caso generale). Come conseguenza: le algebre di Boole finite hanno per cardinalità una potenza di 2; due algebre di Boole finite equipotenti sono necessariamente isomorfe. Esempio di un algebra di Boole (infinita) che non è isomorfa all'algebra delle parti di alcun insieme.
Anelli booleani. Proprietà: sono commutativi ed hanno caratteristica 2. Esempi; l'anello delle parti di un insieme; il campo Z2. 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; quest'ultima è stata indicata senza procedere alla dimostrazione. Sottoanelli unitari degli anelli booleani e sottoalgebre di Boole. Teorema di Stone per anelli booleani.
Un esempio importante: funzione caratteristica di una parte di un insieme. Equipotenza tra ℘(S) e Map(S,{0,1}) per un qualsiasi insieme S. Se S è finito |℘(S)|=2|S| (seconda dimostrazione di questo fatto). Anelli booleani definiti su "stringhe di zeri ed uno" di assegnata lunghezza n. Tali stringhe si possono riguardare come funzioni caratteristiche; in questo modo si definisce in modo naturale un isomorfismo tra l'anello booleano considerato e l'anello booleano delle parti di {1,2,3,…n}.
Cenni alle applicazioni delle algebre di Boole in logica (algebra di Boole associata ad un linguaggio).
Esercizi assegnati:
Rapida discussione sugli esercizi proposti nella lezione precedente.
Fattorizzazione in monodi commutativi regolari. Se M è un tale monoide la relazione di divisibilità in M è un ordinamento se e solo se l'unità è l'unico invertibile in M. Divisori banali e fattorizzazioni non banali di elementi in un monoide commutativo regolare. 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. Anelli fattoriali (esempi: Z, i campi).
Una conseguenza del teorema Fondamentale dell'Aritmetica: per verificare che un intero n > 1 sia primo basta verificare che non sia divisibile per alcun primo minore o uguale alla sua radice quadrata. Cenno al crivello di Eratostene.
Descrizione dell'insieme dei divisori di un elemento in un monoide fattoriale a partire da una fattorizzazione in irriducibili (o, meglio, da una fattorizzazione primaria; in maggior dettaglio è stato considerato il caso dei monoidi (N#,⋅) e (Z#,⋅); in questi due casi: calcolo del numero dei divisori). Come conseguenza: esistenza (ed espressione) 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.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Elementi primi in un monoide commutativo regolare. Ogni primo è irriducibile ma non necessariamente vale il viceversa. 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).
Divisione euclidea tra interi (se a,b∈Z e b≠0, esistono interi q ed r tali che a=bq+r e |r|≤|b/2|). Uso di questa divisione per la velocizzazione dell'algoritmo euclideo.
Estensione dell'algoritmo euclideo e Teorema di Bézout (la dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo, diversa da quella nel libro di testo).
Conseguenze del Teorema di Bézout: caratterizzazione delle coppie di interi coprimi; Lemma di Euclide: se a,b,c ∈ Z, con a e b coprimi, e a divide bc allora a divide c. Verifica del fatto che gli irriducibili in (N#,⋅) sono primi e completamento della giustificazione del Teorema Fondamentale dell'Aritmetica.
Equazioni diofantee (di primo grado, a due indeterminate). Criterio di esistenza di soluzioni (altra forma del Teorema di Bézout).
Introduzione alle equazioni congrenziali (di primo grado). Siano a,b ∈ Z e m ∈ N#; se [a]m è invertibile in Zm, allora l'insieme delle soluzioni (in Z) dell'equazione congruenziale ax ≡mb è una classe di resto modulo m.
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. Se m∈N#, l'anello Zm è un campo se e solo se m è primo.
Determinazione dell'insieme di tutte le soluzioni di un'equazione congruenziale (con dimostrazioni lasciate in sospeso).
Per la prossima lezione sarà utile avere con sé le note sulla funzione di Eulero.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Metodi di semplificazione e di soluzione di equazioni congruenziali e dimostrazioni relative. Diversi esempi e discussione dei possibili errori.
Determinazione dell'insieme di tutte le soluzioni di un'equazione diofantea (di primo grado, con due indeterminate).
La funzione di Eulero ed il 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 modulo un fissato intero positivo m sono i laterali destri in Z del sottogruppo mZ). 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. Cenni alle applicazioni di questi risultati alla crittografia.
Per la prossima lezione sarà molto importante avere con sé le note sui polinomi.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Il contenuto della lezione di oggi corrisponde all'incirca alle prime 5 sezioni delle note sui polinomi. La parte rimanente sarà oggetto delle prossima lezione, durante le quali sarà importante avere con sé una copia delle stesse note.
L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario. Definizione e prime proprietà. Proprietà universale per gli anelli dei polinomi; 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, polinomi costanti, polinomi monici.
Per ogni anello commutativo A, A[x] è infinito.
Grado della somma, della differenza e del prodotto tra due polinomi. Se il polinomio non nullo f ∈ A[x] 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.
Se A è un anello commutativo e f è un polinomio monico in A[x] con grado positivo, allora f non è invertibile (ad esempio, x non è invertibile). Di conseguenza A[x] non è un campo.
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.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nella lezione precedente.
La lezione è consistita in una discussione generale sul contenuto delle note sui polinomi, con diversi esempi.
Esercizi assegnati (si leggano bene gli esempi nelle note sui polinomi):
Richiami sulle permutazioni e sul gruppo simmetrico su un insieme. 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. Esempi. Fattorizzazione (non unica!) di una permutazione su un insieme finito in prodotto di trasposizioni. Parità di una permutazione; il gruppo alterno. Queste ultime nozioni sulle permutazioni sono state esposte in modo informale e i relativi enunciati non sono stati pienamente dimostrati. In particolare, non è stato giustificato il fatto che nessuna permutazione può essere contemporaneamente di classe pari e di classe dispari.
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. 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. Distanza in un multigrafo. Relazione di connessione; (multi)grafi connessi. Sottografi. Componenti connesse di un multigrafo.
Esercizi assegnati:
Discussione di alcuni esercizi proposti nella lezione precedente.
Nozione di (multi)grafo planare (ovvero: piano) ed enunciato del teorema di Kuratowski. Grafi bipartiti.
Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari (enunciato e cenni alla dimostrazione). Esempi, tra cui il problema dei sette ponti di Königsberg.
Foreste e alberi. Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso finito.
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.
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 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 è sempre maggiore o uguale a |V|-|L|; in particolare, se il multigrafo è connesso, allora |L|≥|V|-1).
Metodi di costruzione di grafi finiti con assegnati invarianti; diversi esempi ed esercizi.
Esercizi assegnati: