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 semanticamente): negazione, congiunzione, disgiunzione (inclusiva), disgiunzione esclusiva, bicondizionale (equivalenza) e condizionale (implicazione). Tabelle (o tavole) di verità, con esempi del loro uso. Tautologie, contraddizioni e forme contingenti. Alcune tautologie classiche: principî del terzo escluso e di non contraddizione, alcune tautologie sulle implicazioni: bicondizionale come doppia implicazione, negazione del bicondizionale con la disgiunzione esclusiva, interpretazione di una implicazione come disgiunzione, negazione di una implicazione, leggi di De Morgan.
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é.
Esercizi assegnati:
Esercizi sugli argomenti della lezione precedente. Altre tautologie; completamento della lettura di esempi di tautologie e rapida discussione su tavola dei connettivi binari.
Cenni alla logica dei predicati. Variabili; quantificatori: universale (∀) ed esistenziale (∃) e loro uso. Cenni alle nozioni di occorrenza libera e legata di una variabile; le formule contenenti variabili 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 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à). Alcuni modi per descrivere insiemi; cenni a problemi fondazionali ed al paradosso di Russell.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
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.
Sottoinsiemi (o parti) di un insieme. L'insieme ℘(S) delle parti di un insieme S. Qualunque sia S, si ha ∅∈℘(S) e S∈℘(S).
Un ulteriore cenno al paradosso di Russell. Un'altra ‘regola’ insiemistica: (∀x)(x∉x), (dunque x≠{x}); non esiste “l'insieme di tutti gli insiemi”.
Assioma di separazione. Descrizione di insiemi tramite espressioni del tipo {x∈S|p(x)} per un predicato p(x).
Proposizioni della forma (∀x∈S)(p(x)) e della forma (∃x∈S)(p(x)); 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.
A partire dalla prossima lezione portare con sé tautologie, insiemi, aritmetica.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Altre discussioni ed esempi sui diagrammi di Euler-Venn (esercizio nr. 2(a) da tautologie, insiemi, aritmetica). Dimostrare la verità o la falsità di identità insiemistiche.
Completamento di tautologie e identità insiemistiche.
Differenza simmetrica tra due insiemi e disgiunzione esclusiva (XOR). Associatività dei connettivi ⇔ e XOR; la seconda è stata ottenuta dalla prima tramite l'equivalenza tra (a⇔b)⇔c e (a XOR b) XOR c, che segue dalla tautologia (a XOR b)⇔((¬a)⇔b). Associatività della differenza simmetrica.
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.
Cardinalità dell'insieme delle parti di un insieme finito: |℘(S)|=2|S|. Per verificare questa uguaglianza è stato introdotto il principio di induzione.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
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|.
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.
È stato anche introdotto l'uso di descrivere 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,…)}).
Diversi modi per descrivere corrispondenze; rappresentazioni grafiche di corrispondenze e relazioni, via diagrammi o tabelle.
Applicazioni tra insiemi. Il problema della "buona" (corretta) definizione di un'applicazione; esempi. Introdotte le notazioni Map(A,B), BA e AB per l'insieme delle applicazioni dall'insieme A all'insieme B. 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.
Applicazioni iniettive e applicazioni suriettive. Negazione di iniettività e suriettività; esempi. Applicazioni biettive. Equipotenza tra insiemi.
Definito, per ogni insieme S e per ogni k ∈ N, l'insieme ℘k(S) delle k-parti (cioè parti di cardinalità k) di S.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente, ad eccezione dell'ultimo e dell'esercizio 3.e da tautologie, insiemi, aritmetica, la discussione dei quali è rimandata.
Prodotto relazionale tra corrispondenze; corrispondenze componibili. Esempi. Corrispondenza inversa di una corrispondenza. Associatività del prodotto relazionale. 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 α).
La composta di due applicazioni iniettive (risp. suriettive) è necessariamente iniettiva (risp. suriettiva).
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente. L'immagine im f di un'applicazione f. 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). Esempi e controesempi. 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).
Un'osservazione fatta: ogni applicazione il cui dominio abbia meno di due elementi è iniettiva.
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à del grafico della relazione. La diagonale ΔA={(x,x) | x∈A} di A. Relazioni di equivalenza e relazioni d'ordine in un insieme.
Classi di equivalenza ed insieme quoziente definito da un'equivalenza. Qualche esempio. Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione. Proprietà fondamentali delle classi di equivalenza: fissata una relazione di equivalenza ρ in un insieme A, per ogni a, b ∈ A si ha
Esercizi assegnati:
Discussione di alcuni (pochi) degli esercizi proposti nella lezione precedente.
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. Esempi, tra cui: descrizione di Eq(A) e Part(A) per A = {1,2}.
Partizioni banali e corrispondenti equivalenze (banali: uguaglianza e relazione universale).
Proiezione canonica di un insieme su un suo quoziente; ogni equivalenza è il nucleo di equivalenza di un'applicazione.
Dalla prossima lezione portare con sé, oltre alle altre già menzionate, le note su Sezioni e Retrazioni.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
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.
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. Descrizione esplicita dell'inversa di un'applicazione biettiva.
Una discussione di carattere generale: come vengono descritti insiemi tramite applicazioni biettive tra essi ed insiemi già ben descritti. L'esempio della biezione canonica tra gli insiemi delle equivalenze e delle partizioni di un assegnato insieme.
Descrizione delle sezioni di un'assegnata applicazione (e loro numero); esempi. Un'applicazione è biettiva se e solo se ha una ed una sola sezione.
Oltre alle note già utilizzate, dalla prossima lezione portare con sé Il Teorema di Omomorfismo per Insiemi.
Esercizi assegnati:
Si ricorda che, affinché si prosegua con l'abitudine di assegnare e, soprattutto, discutere esercizi in aula è necessario che un numero ragionevole di studenti si presenti a lezione con esercizi svolti, o almeno tentati, anziché aspettare di farsi imboccare col cucchiaino.
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Il numero delle applicazioni e il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti. 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, 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).
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!
Descrizione esplicita dell'insieme dei prolungamenti di un'assegnata applicazione f : X→Y ad un insieme S contenente X: biezione tra questo insieme e Map(S-X,Y). Descrizione dell'insieme delle retrazioni di un'assegnata applicazione in termini di prolungamenti dell'inversa di una ridotta..
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Descrizione esplicita dell'insieme delle retrazioni di un'assegnata applicazione. Il numero delle retrazioni di un'applicazione (iniettiva) tra insiemi finiti. Un'applicazione il cui dominio abbia più di un elemento è biettiva se e solo se ha una ed una sola retrazione.
Coimmagine di un'applicazione (come quoziente rispetto al 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 note su questo argomento sino al triangolo di Tartaglia-Pascal incluso; non è si è ancora parlato, invece, dell'enunciato numero 4 né di ciò che segue.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Formula esplicita per il calcolo dei coefficienti binomiali.
Operazioni (binarie, interne) in un insieme. Operazioni associative e operazioni commutative; esempi. Cenno 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); nozione di operazione indotta e di sottostruttura. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà. 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 sinistra.
Semigruppi e monoidi. Tra gli esempi: il monoide T(S) delle trasformazioni di un insieme S (non è commutativo se |S|>1).
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".
Dalla prossima lezione sarà utile avere con sé le note sulla cancellabilità
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Notazioni per le strutture algebriche che coinvolgano anche operazioni unarie o nullarie, come nel caso dei monoidi. Esempi, come (N,+,0), (T(S),·,idS), (℘(S),&cap,S), per un insieme S.
Gruppi. Esempi, come (Z,+,0,−), (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 simmetrico Sym(S):=U(T(S)) su un insieme S; se |S| ≥ 3 questo è un gruppo non abeliano. Cicli (permutazioni cicliche), trasposizioni. Notazione: Sn = Sym({1,2,3,…,n}).
Parti stabili generate da una parte in una struttura (rispetto ad una operazione). Più in generale, sottostrutture. Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che non sono monoidi oppure sono monoidi ma non sottomonoidi. 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).
Omomorfismi tra strutture algebriche. Omomorfismi di semigruppi e di monoidi.
Esercizi assegnati:
Discussione degli esercizi proposti nelle lezioni precedenti.
Omomorfismi tra strutture algebriche; monomorfismi, epimorfismi, isomorfismi. Esempi. Discussione sulla nozione generale di isomorfismo. Tavole di Cayley (ovvero di moltiplicazione) per operazioni binarie. Esempi: isomorfismo tra i gruppi S2, ({1,−1},⋅), (℘({1}),Δ); tutti i gruppi di cardinalità 2 sono tra loro isomorfi (come è stato dimostrato più avanti, usando la proprietà di cancellabiltà e una tavola di Cayley). Invarianza delle proprietà algebriche per isomorfismi. L'esistenza di neutri e di simmetrici è preservata dagli isomorfismi, non da tutti gli omomorfismi.
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.
Anelli, anelli commutativi, anelli unitari. Esempi: (Z,+,⋅), (Q,+,⋅), (℘(S,Δ,∩). Cenno agli anelli di matrici, come esempi di anelli non commutativi.
Notazioni e regole di calcolo in un anello: 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).
Esercizi assegnati:
Discussione di uno degli esercizi proposti nella lezione precedenti.
Cancellabilità negli anelli; divisori dello zero; anelli integri e domini di integrità. Corpi e campi. Esempi.
Sottoanelli e sottoanelli unitari di anelli unitari. Omomorfismi di monoidi, di gruppi, di anelli, di anelli unitari.
Relazione di divisibilità in semigruppi e monoidi commutativi, ed in anelli commutativi. Elementi associati. Esempi: divisibilità in (N,+), in (℘(S),∪), in (Z,⋅), in (N,⋅). Se R è un anello commutativo, un elemento che divida due elementi ne divide tutte le combinazioni lineari a coefficienti in R.
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. Esempi. 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. Proprietà che si conservano passando alla struttura quoziente (come associatività, commutatività, esistenza di neutri e simmetrici, distributività); quozienti di semigruppi, monoidi, gruppi etc.
Esempi, tra cui 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.
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.
Divisione (aritmetica) con resto in Z: (∀a ∈ Z)(∀b∈Z−{0}) (∃!(q,r)∈Z×N)(a=bq+r ∧ r<|b|). Questo enunciato non è stato ancora dimostrato.
Per ogni a,m ∈ Z, se m≠0 esiste uno ed un solo r ∈ N tale che a ≡m r e r < |m|. Conseguenza: per ogni intero positivo m, Zm ha esattamente m elementi: le classi di 0, 1, 2, …, m−1.
Esercizi assegnati:
Buon ordinamento di N (rispetto all'ordinamento usuale), giustificazione del principio di induzione; cosidetta `seconda forma' del principio di induzione, argomentazione per "controesempio minimo". Dimostrazione di quanto enunciato nella lezione precedente a proposito della divisione aritmetica (esistenza e unicità di quoziente e resto). Per ogni a,m ∈ Z, se m≠0 si indica come a mod m il resto della divisione (aritmetica) di a per m.
Ancora sulle congruenze ≡m in Z. È stato solo enunciato il fatto che queste sono le sole congruenze di (Z,+). Le congruenze ≡m riguardate come nuclei di equivalenza di funzioni resto: due interi sono congrui modulo un intero non nullo 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. In questo modo abbiamo completato la descrizione dettagliata degli elementi dei quozienti Zm.
Epimorfismo canonico (cioè proiezione canonica) da una struttura ad un suo quoziente. Esempio: per ogni intero positivo m, l'epimorfismo canonico (di anelli unitari) da Z a Zm.
Esempio: elementi invertibili, cancellabili, divisori dello zero, idempotenti nell'anello Z6.
Calcoli in aritmetica modulare (calcolo di somme, prodotti, potenze). Divesi 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.
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). Prima regola di calcolo: per ogni n,m∈N e per ogni x per cui queste potenze siano definite, xn+m=xnxm.
Esercizi assegnati:
Discussione degli esercizi proposti nella lezione precedente.
Ulteriori regole di calcolo per potenze (o multipli) in semigruppi, monoidi, gruppi: 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. Potenze (o multipli) secondo interi di uno stesso elemento di un semigruppo commutano sempre tra loro. In ogni anello unitario R si ha (n1R)x=nx per ogni n∈Z.
Nel corso delle dimostrazioni svolte è stato anche osservato che, se a e b sono elementi di un semigruppo che commutino tra loro (cioè tali che ab = ba) e b è invertibile, allora anche a e l'inverso di b commutano tra loro.
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#,⋅).
L'elemento neutro di un gruppo è l'unico elemento di periodo 1. Se un elemento x di un gruppo ha periodo finito λ, allora, per ogni intero n, si ha xn=1 se e solo se λ divide n; più in generale, se n, m ∈ Z, xn=xm se e solo se n e m sono congrui modulo λ. Osservazione: se x ha periodo finito λ, 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.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Parte stabile generata e 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.
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 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 e di 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.
Ulteriori 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.
Relazione di copertura associata ad un ordinamento.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Diagrammi di Hasse di un insieme ordinato finito. Esempi.
Isomorfismi tra insiemi ordinati. Esempio di un'applicazione crescente e biettiva che non è un isomorfismo tra insiemi ordinati.
Minoranti e maggioranti di parti in un insieme ordinato. Estremo inferiore ed estremo superiore. Diversi esempi, tra cui:
Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli. In ogni reticolo, ogni elemento minimale (risp. massimale) è minimo (risp. massimo).
Nozione di reticolo completo (esempio: l'insieme delle parti di un insieme, ordinato per inclusione).
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 limitati (cioè con minimo e massimo). I reticoli finiti sono limitati (ma non vale il viceversa).
Reticoli come strutture algebriche; operazioni reticolari. Esempio: per un insieme S, (℘(S),⊆) e (℘(S),∧,∨). Le dimostrazioni sono ancora da completare.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Completamento della discussione sull'equivalenza tra lo studio dei reticoli come strutture ordinate e dei reticoli come strutture algebriche.
Il duale di ogni reticolo è un reticolo, si ha quindi un principio di dualità anche per reticoli.
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. Esempi di parti di reticoli che non sono sottoreticoli, ma che, muniti dell'ordinamento indotto, sono reticoli.
Complementi di un elemento in un reticolo limitato; 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.
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.
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. 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.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
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 accennata senza procedere alla dimostrazione, che si lascia come esercizio). Sottoanelli unitari degli anelli booleani ed enunciato del teorema di Stone per anelli booleani. Isomorfismi di anelli unitari (booleani) e di reticoli (booleani).
Cenni alle applicazioni delle algebre di Boole in logica (algebra di Boole associata ad un linguaggio).
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 (ovvero n-ple di elementi di Z2). 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}.
Formula del binomio di Newton per il calcolo delle potenze di una somma tra due elementi permutabili in un anello (vedi coefficienti binomiali).
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Richiami sulla 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).
Massimo comun divisore e minimo comune multiplo di una parte di un arbitario semigruppo commutativo. Esempi. Se non vuoto, l'insieme dei MCD di un'assegnata parte di un monoide commutativo è una classe di equivalenza rispetto alla relazione "essere elementi associati", analoga affermazione vale per i minimi comuni multipli.
Monodi regolari. Se M è (commutativo e) regolare 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. 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). Anelli fattoriali (esempi: Z, i campi).
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 di alcuni degli esercizi proposti nelle lezioni precedenti.
Altre conseguenze 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.
Se d e m sono, rispettivamente un massimo comun divisore ed un minimo comune multiplo tra due elementi a e b di un monoide fattoriale, allora dm è associato ad ab.
Ancora sull'algoritmo euclideo. 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). Equazioni diofantee (di primo grado, a due indeterminate). Criterio di esistenza di soluzioni (altra forma del Teorema di Bézout).
Altre 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.
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.
Metodi di semplificazione e di soluzione di equazioni congruenziali, 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 (se un elemento g di un gruppo ha periodo n, allora l'inverso di g è gn−1).
Esercizi assegnati:
Rapida discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Determinazione dell'insieme di tutte le soluzioni di un'equazione diofantea (di primo grado, con due indeterminate).
Ancora sugli invertibili nei quozienti di Z. Se m∈N#, l'anello Zm è un campo se e solo se m è primo (ciò equivale anche all'essere Zm integro). 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.
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.
Esercizi assegnati:
Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.
Il contenuto della lezione di oggi corrisponde alle sezioni 4, 5 e 6 delle note sui polinomi. La parte ancora rimanente sarà oggetto della prossima lezione, durante la quale sarà importante avere con sé una copia delle stesse note.
Argomenti trattati oggi:
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. 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). 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 o su anelli booleani.
Esercizi assegnati:
Completamento di quanto nelle note sui polinomi.
Se A è un anello fattoriale, anche A[x] è fattoriale (senza dimostrazione). 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. Criterio di irriducibilità di Eisenstein. Applicazione: esistono in Q[x] polinomi irriducibili di grado arbitrario. 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.
Osservazioni sui polinomi su campi che siano quozienti di Z; diversi esempi.
Esercizi assegnati (si leggano bene gli esempi nelle note sui polinomi):
Richiami sulle permutazioni e sul gruppo simmetrico su un insieme. 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. Esempi.
Fattorizzazione (non unica!) di una permutazione su un insieme finito in prodotto di trasposizioni. Parità di una permutazione; il gruppo alterno. 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.
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. Relazione di connessione; (multi)grafi connessi. Sottografi. Componenti connesse di un multigrafo.
Nozione di (multi)grafo planare (ovvero: piano) ed enunciato del teorema di Kuratowski.
Esercizi assegnati:
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. 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.
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.
Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso finito.
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: