Corso di Algebra - Corso di recupero, a.a. 2012/13
Le lezioni

Introduzione al corso: presentazione; informazioni generali; modalità di svolgimento.

Cenni sulla logica proposizionale. Nozione informale di proposizione (in termini solo semantici). I principali connettivi proposizionali (anch'essi descritti solo semanticamente): negazione, congiunzione, disgiunzione (inclusiva), equivalenza (o bicondizionale), implicazione (o condizionale). Comparazione tra il loro uso e quello di espressioni analoghe del linguaggio naturale. Tabelle (o tavole) di verità, con esempi del loro uso in calcolo proposizionale. Tautologie, contraddizioni e forme contingenti con esempi: principî del terzo escluso e di non contraddizione.

Il contenuto di questa lezione è riportato (con qualche espansione) in alcune note sulla logica elementare che metterò a disposizione quanto prima su questo sito. Un link a queste note apparirà su questa stessa pagina. Può essere utile consultare anche: una tavola dei connettivi binari e esempi di tautologie.

Aggiornamento: i nuovi appunti sono in rete: Logica rudimentale. Il contenuto di questa lezione è coperto, approssimativamente, dalle prime sei pagine. Sono benvenute le segnalazioni di errori di battuta.

Esercizi proposti:

1. Scrivere la tavola di verità della forma proposizionale p ∧ (q ∧ r).
2. Verificare che la forma proposizionale (p ∧ q) ⇔ (q ∧ p) è una tautologia.

Discussione degli esercizi proposti nella lezione precedente.

Forme proposizionali logicamente equivalenti. Tautologie: idempotenza di ∧ e ∨; commutatività e associatività di ∧,∨ e ⇔; distributività di ∧ rispetto a ∨ e di ∨ rispetto a ∧.

Tautologie sulla negazione: doppia negazione, leggi di De Morgan, negazione dell'equivalenza (introdotto così il connettivo XOR), negazione dell'inclusione.

Altre tautologie sull'implicazione: equivalenza come doppia implicazione, implicazione come disgiunzione, legge di contrapposizione.

Alcune tautologie su XOR, tra cui la legge associativa e la distributività di ∧ rispetto a XOR.

Cenni ai connettivi NAND e NOR ed al fatto che ciascuno di essi basta per esprimere tutti gli altri connettivi binari.

Introduzione minimale alla logica dei predicati; tutto l'argomento è (e sarà) svolto solo per cenni ed in modo informale. Quantificatori: universale (∀) ed esistenziale (∃); loro interpretazione nell'uso matematico. Occorrenze libere e vincolate di una variabile; formule chiuse (o proposizioni).

Quantificatori ristretti: interpretazione di formule come (∀x ∈ S)(p(x)) .

Per il contenuto di questa lezione e della precedente, si vedano, approssimativamente, le prime cinque sezioni di Logica rudimentale.

Esercizi proposti:

1. Provare ad indovinare: come si interpretano formule della forma (∃x ∈ S)(p(x))?
2. Da Logica rudimentale: esercizi B da 2 a 6, C2, D da 1 a 3, E3 (leggere anche l'osservazione E4), E5, H1.

Discussione di alcuni degli esercizi proposti nella lezione precedente. Ulteriori osservazioni sulle sostituzioni e sulle occorrenze libere o vincolate di variabili (queste ultime ‘non vengono sostituite’.

Frasi contenenti più quantificatori (esempi di frasi delle forme ∀x∃y… o ∃y∀x…). Predicati. Descrizione del quantificatore ∃! tramite l'equivalenza tra (∃!x)(p(x)) e (∃x)(∀y)(p(y)⇔x=y). Negazione di frasi introdotte da quantificatori (o da quantificatori ristretti).

Nozione (solo informale) di insieme. Il simbolo '∈' di appartenenza. Cenni a problemi fondazionali; l'antinomia (o paradosso) di Russell. Assioma di estensionalità: (∀A,B)(A=B ⇔ (∀x(x∈A⇔ x∈ B))) e sue applicazioni. L'insieme vuoto ∅ (e sua unicità). Assioma di separazione.

Comparazione tra l'equivalenza logica tra predicati (da una parte) ed uguaglianza tra insiemi (dall'altra).

Esercizi proposti:

1. Da Logica rudimentale, sono ancora da discutere E5 e buona parte di H1. Aggiungiamo a questi H4, H5, H6 e le osservazioni G.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti. Non esiste l'insieme di tutti gli insiemi.

Inclusione tra insiemi. È importante distinguere bene tra appartenenza e inclusione. Per ogni x si ha x⊆x, ma x∉x. Il singleton di un insieme; ∀x(x≠{x}).

Sottoinsiemi (o parti) di un insieme. L'insieme ℘(S) delle parti di un insieme S. Qualunque sia S, si ha ∅ ⊆ S (cioè ∅ ∈ ℘(S)) e S; ⊆ S (cioè S ∈ ℘(S)).

Corrispondenza informale tra connettivi proposizionali e relazioni o operazioni insiemistiche. Implicazione ed inclusione, congiunzione e intersezione, disgiunzione ed unione. Interpretazione della negazione (non esiste l'insieme degli oggetti non appartenenti ad un insieme dato) e differenza (o complemento relativo) tra insiemi. Alcune formule insiemistiche: regola della doppia inclusione, transitività dell'inclusione, leggi di idempotenza, commutatività, associatività e distributività per l'unione e l'intersezione binarie; formule (insiemistiche) di De Morgan. Per questo e per altro, si veda la sezione Formule insiemistiche in Logica rudimentale, esclusa l'ultima sottosezione (Parti di un fissato insieme).

Diagrammi di Euler-Venn; qualche esempio. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare formule insiemistiche.

Differenza simmetrica tra due insiemi e disgiunzione esclusiva (XOR). Alcune formule per la differenza simmetrica e sue proprietà essenziali, tra le quali: commutatività, associatività, distributività di ∩ rispetto a Δ. ∀x(xΔx=∅).

Esercizi proposti:

1. Negare la frase (in linguaggio naturale): 'Tutte le volte che vado dal salumiere, se c'è del salame lo compro'.
2. Descrivere esplicitamente gli insiemi {x | x = ∅}, {x | ∀a(x ⊆ a)}, {y | ∀x(x = y)}.
3. Elencare gli elementi di ℘(∅), ℘({1}) e ℘({1,2}).
4. Si ha ∅ = {∅}?
5. Rappresentare su diagrammi di Venn (per insiemi A, B, C) gli insiemi:
   1. (A∩B)∩C;
   2. (AΔB)ΔC;
   3. (A∪B)∩C, ovvero (A∩C)∪(B∩C);
   4. (AΔB)∩C, ovvero (A∩C)Δ(B∩C);
   5. (AΔB)∪C e (A∪C)Δ(B∪C);
   6. (A∩B)−C e (A−C)∩(B−C);
   7. (A∪B)−C e (A−C)∪(B−C);
   Trarre qualche conclusione dal confronto delle ultime tre coppie di diagrammi.
6. È vero che (∀ A, B) (℘(A) ⊆ ℘(B) ⇔ A ⊆ B)?
7. Elencare gli elementi degli insiemi:
   • {n∈N|(n<13)∧(n≥4)}
   • {n∈N|(n<13)∨(n≥4)}
   • {n∈N|(n>5)⇒(n<14)}
   • {n∈Z|(∃m∈Z)(n+m=5)}
   • {n∈Z|(∃m∈Z)(n+m≠5)}
   • {n∈Z|(∃m∈N)(n+m=5)}
   • {n∈Z|(∀m∈N)(n+m=5)}
   (Z indica l'insieme dei numeri interi, N indica l'insieme dei numeri naturali: N = {n∈Z | n≥0}).
8. Esercizio I3 da Logica rudimentale (il grosso lo abbiamo già discusso in aula).

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti. Uso dei diagrammi di Euler-Venn per costruire controesempi a formule insiemistiche.

Diagrammi di Venn e cardinalià (numero degli elementi) 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.

Completamento di Formule insiemistiche da Logica rudimentale: interpretazione del connettivo di negazione nell'ambiente di un prefissato insieme S come complemento in S. Qualche ulteriore formula.

Descrizione di insiemi 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.

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.

Diversi modi per descrivere corrispondenze; rappresentazioni grafiche di corrispondenze e relazioni, via diagrammi o tabelle.

Prodotto relazionale tra corrispondenze.

Esercizi proposti:

1. Esercizi J4 e J5 da Logica rudimentale.
2. Rappresentare su diagrammi di Venn (per insiemi A, B, C) e quindi confrontare gli insiemi A−(B−C) e (A−B)−C.
3. Per ogni numero reale r sia X_r l'insieme dei numeri reali minori di r². Posto Y = {X_r | r ∈ R}, descrivere gli insiemi ∪Y e ∩Y. Nota: i simboli R, ∪ e ∩ indicano, nell'ordine, l'insieme dei numeri reali, l'unione (unaria) e l'intersezione (unaria).
4. Verificare in dettaglio il principio di inclusione-esclusione nel caso dell'unione di tre (arbitrari) insiemi finiti.
5. Dati due insiemi A e B tali che |A|=35, |B|=31 e |A∩B|=15, calcolare |A∪B|, |A−B| e |B−A|.
6. Un incaricato di indagini di mercato ci fa sapere di avere interrogato un campione di 70 persone. Il suo risultato è che, di queste, 41 sono uomini e 29 donne, 37 hanno più di 35 anni e 33 hanno al più questa età, a 52 piace la cioccolata, a 18 no. Inoltre, in questo campione, gli uomini con oltre 35 anni sono 15, gli uomini a cui piace la cioccolata sono 24, le persone di oltre 35 anni a cui piace la cioccolata sono 18. Possiamo fidarci di questi dati?
7. Dimostrare che per ogni a, b, c e d si ha:
   • {a,b}={c,d} ⇔ ((a=c ∧ b=d) ∨ (a=d ∧ b=c));   (questo è facile)
   • {{a},{a,b}}={{c},{c,d}} ⇔ (a=c ∧ b=d).   (meno facile)
   Dedurne che la definizione di Kuratowski di coppia ordinata (data come (a,b):={{a},{a,b}} per ogni a e b) è una 'buona' definizione di coppia ordinata.
8. Descrivere, elencandone gli elementi, {1,3,4} × {3,5,7}.
9. Dati gli insiemi A e B, trovare condizioni necessarie e sufficienti affinché:
   • A × B = ∅;
   • A × B = B × A.
10. Siano N l'insieme dei numeri naturali e S={1,2,3}. Siano poi α la relazione binaria in S di grafico {(1,3), (3,1),(3,3)} e β la corrispondenza da S ad N di grafico {2} × {x∈N | x<10}. Descrivere la corrispondenza prodotto αβ.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Associatività del prodotto relazionale tra corrispondenze. Corrispondenza inversa di una corrispondenza; esempi (relazioni “essere minore di” ed “essere maggiore di”).

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 n ∈ N, l'insieme ℘_n(S) delle n-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, a^f, f_a) per indicare l'immagine mediante un'applicazione f di un elemento a del suo dominio. Successioni e famiglie.

Composizione (prodotto operativo) di applicazioni.

L'immagine im f di un'applicazione f. Applicazioni suriettive. Negazione della suriettività. Esempi.

Applicazioni iniettive. Negazione della iniettività. Esempi. 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). Ogni applicazione il cui dominio abbia meno di due elementi è iniettiva.

Applicazioni biettive. L'applicazione identica id_A 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 α).

Restrizioni, prolungamenti e ridotte di applicazioni.

Esercizi proposti:

1. La corrispondenza: n ∈ Z → n²/2 ∈ Z è un'applicazione ben definita?
2. Indicato con R⁺₀ l'insieme dei numeri reali non negativi (cioè R⁺₀={a ∈ R | a ≥ 0}), si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • α: R → R, di grafico {(a,b) ∈ R×R | a=b²}
   • β: R⁺₀ → R, di grafico {(a,b) ∈ R×R | a=b²}
   • γ: R⁺₀ → R⁺₀, di grafico {(a,b) ∈ R×R⁺₀ | a=b²}
3. Esercizio nr. 3 da Tautologie, Insiemi, Aritmetica, escluso il punto f. Al punto d, la notazione 2N indica l'insieme dei numeri naturali pari.
4. Esercizio nr. 4 da Tautologie, Insiemi, Aritmetica. Attenzione: il prodotto che appare nel testo come fg va letto g o f.

Discussione degli esercizi proposti nella lezione precedenti.

La composta di due applicazioni iniettive (risp. suriettive, biettive) è necessariamente iniettiva (risp. suriettiva, biettiva). Parziale inversione di questo risultato: se la composta g o f di due applicazioni è iniettiva allora quella che agisce per prima (cioè f) è iniettiva; se invece g o f è suriettiva allora g è suriettiva. Esempi e controesempi.

L'inversa di un'applicazione. Un'applicazione è biettiva se e solo se ha inversa (cioè se e solo se è invertibile). Unicità dell'inversa.

Importanza della nozione di invertibilità.

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti (notazione: n^m = n(n−1)(n−1)…(n−m+1)).

Criterio di esistenza di applicazioni iniettive tra assegnati insiemi finiti: se A e B sono insiemi finiti, allora esistono applicazioni iniettive da A a B se e solo se |A|≤|B|.

Esercizi proposti:

1. Dati un'applicazione f: A→B ed un sottoinsieme X di A, descrivere la composta di f con l'immersione di X in A.
2. Provare che, se f e g sono applicazioni biettive componibili, l'inversa di fog è g^-1of^-1, dove g^-1 e f^-1 sono rispettivamente le inverse di g e f.
3. Siano A={1,2,3} e B={x,y}, dove |B|=2. Dire quante sono le applicazioni da A a B, quante quelle da B ad A, quante quelle iniettive da A a B e quante quelle iniettive da B ad A.
4. Elencare tutte le applicazioni di cui all'esercizio precedente.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Condizioni di esistenza di applicazioni suriettive o biettive tra assegnati insiemi finiti: se A e B sono insiemi finiti, allora esistono applicazioni suriettive da A a B se e solo se |A|≥|B| e B=∅ ⇒ A=∅; esistono applicazioni biettive da A a B se e solo se |A|=|B|. Di passaggio, si è notato che per ogni applicazione suriettiva f esiste un'applicazione (necessariamente inietttiva) g tale che fog sia l'applicazione identica del codominio di f.

Teorema: se f è un'applicazione tra due insiemi finiti con lo stesso numero di elementi, allora f è iniettiva se e solo se è suriettiva (dunque, se e solo se è biettiva). Questa proprietà vale solo nel caso delle applicazioni tra insiemi finiti.

Cenni su: equipotenza e confronto di cardinalità tra insiemi; cardinalità di alcuni insiemi infiniti (N, Z, Q, R, N×N, R×R, ℘(N)); teorema di Cantor: ∀S (|S|<|℘(S)|

Applicazione immagine f^→: ℘(A) → ℘(B) ed applicazione antiimmagine f^←:℘(B) → ℘(A) definite da un'applicazione f : A → B. Con queste notazioni si ha f^→(∅)=f^←(∅)=∅; f^→(A)=im f e f^←(B)=A. Esempi e controesempi.

Richiamo del principio di induzione. Cardinalità dell'insieme delle parti di un insieme finito: per ogni tale insieme S si ha |℘(S)|=2^|S|.

Proprietà di relazioni binarie: relazioni riflessive e relazioni antiriflessive. Espressione di queste proprietà in termini di proprietà (insiemistiche) del grafico della relazione. La diagonale Δ_S={(x,x) | x∈S} di S.Esempi.

Esercizi proposti:

1. [ripetuto] Siano A={1,2,3} e B={x,y}, dove |B|=2. Dire quante sono le applicazioni da A a B, quante quelle da B ad A, quante quelle iniettive da A a B e quante quelle iniettive da B ad A. Elencare tutte queste applicazioni.
2. Siano A={1,2,3} e B={x,y,z}, dove |B|=3. Quante sono le applicazioni biettive da A a B? Elencarle tutte.
3. Sia v l'applicazione valore assoluto in Z, cioè v: x∈Z→|x|∈Z. Posto A={n∈Z | −10<n<20}, si calcolino v^→(A), v^←(A), v^←(v^→(A)), v^→(v^←(A)), v^→(v^→(A)) e v^←(v^←(A)).
4. Provare che, se f è l'applicazione identica in un insieme A, f^→ e f^← coincidono con l'applicazione identica in ℘(A).
5. Provare che, se f e g sono applicazioni componibili, (fg)^→=f^→g^→  e  (fg)^←=g^←f^←. Se f è biettiva, allora anche f^→ è biettiva e la sue inversa è f^←, che coincide con (f^-1)^→.
6. Provare che, come detto a lezione, se f : A → B è un'applicazione, per ogni X ⊆ A si ha X ⊆ f^←(f^→(X)) e, per ogni Y ⊆ B si ha f^→(f^←(Y)) = Y ∩ im f.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti. Fattoriali; espressione dei fattoriali discendenti come rapporti tra fattoriali.

Richiamo: relazioni riflessive e antiriflessive. Altre proprietà di relazioni binarie: relazioni simmetriche, antisimmetriche, transitive. Confronto tra queste proprietà; negazione di ciascuna di esse, loro espressione in termini di proprietà (insiemistiche) del grafico. Esempi, tra gli altri con relazioni in insiemi finiti descritte da tabelle quadrate.

Relazioni di equivalenza e relazioni d'ordine (stretto o largo) in un insieme.

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

• a ∈ [a]_ρ, quindi [a]_ρ ≠ ∅;
• a ρ b ⇔ b ρ a ⇔ a ∈ [b]_ρ ⇔ b ∈ [a]_ρ ⇔ [a]_ρ= [b]_ρ ⇔ [a]_ρ⊆ [b]_ρ ⇔ [a]_ρ⊇ [b]_ρ ⇔ [a]_ρ∩ [b]_ρ≠ ∅.
• (∀C ∈ S/ρ)(∀x ∈ C)(C = [x]_ρ).

Diversi esempi, tra cui le equivalenze banali (l'uguaglianza e la relazione universale) in un insieme. Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione. Sia f un'applicazione. Allora f è iniettiva (risp. costante) se e solo se il suo nucleo di equivalenza è l'uguaglianza (risp. la relazione universale) sul dominio di f.

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).

Esercizi proposti:

1. In relazioni binarie, esercizi nr. 1 (ad esclusione di 1.f e 1.g), nr. 3 limitatamente alle domande su τ, σ e ψ,  2.c, 2.d e 2.e. (La parte restante di questi esercizi, come, in generale, di tutti quelli disponibili, potrà essere più utilmente affrontata in fase di preparazione dell'esame).
2. Esercizio 4 da relazioni binarie.
3. Siano S={1,2,3,4} e A={1,2}; si consideri l'applicazione f:x∈℘(S)→x∩A∈℘(A). f è iniettiva? f è suriettiva? Detto ρ il nucleo di equivalenza di f, si descriva, innanzitutto, [∅]_ρ in modo esplicito (elencandone cioè gli elementi) e se ne calcoli la cardinalità. Si descrivano poi, sempre in modo esplicito, tutti gli elementi di ℘(S)/ρ e si calcoli |℘(S)/ρ|.
4. Sia f:A→B un'arbitraria applicazione e sia τ il suo nucleo di equivalenza. Fissato un x∈A, si verifichi che [x]_τ=f^←({f(x)}). Si usi questo fatto per dare una descrizione di A/τ da cui si possa dedurre che |A/τ| = |im f|.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Partizioni di un insieme. Definizione e prima caratterizzazione: P è una partizione di un insieme S se e solo se P⊆℘(S)−∅ e (∀ x∈S)(∃!b∈P)(x∈b). 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 (dunque: due elementi di S risultano equivaleneti se e solo se appartengono allo stesso blocco della partizione).

Numerosi esempi, tra i quali 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 ℘₁(S)); tutte le partizioni dell'insieme {1,2,3}.

Applicazione X∈℘(S)→|X|∈N per un insieme finito S. Coefficienti binomiali: buona definizione del coefficiente binomiale (ⁿ_k) [la resa del simbolo in HTML è piuttosto approssimativa] come cardinalità di ℘_k(S), per ogni k, n in N ed ogni insieme S di cardinalità n. I casi, banali, in cui k vale 0, 1 o n, o è maggiore di n.

Esercizi proposti:

1. Sia S={a,b,c} un insieme. Descrivere tutte le relazioni di equivalenza in S e calcolarne il numero. (Attenzione: quanti elementi ha S?)
2. Sia A={1,2,3,4,5,6,7}. Quante (e quali) sono le relazioni di equivalenza ρ in A tali che 1 ρ 3, {2,4,6}⊆[3]_ρ e 3∈[7]_ρ?
3. Esercizi nr. 3, 4, 6 da un compito del 13 febbraio 2009 (attenzione: la tipologia di questo compito è molto diversa da quelli in uso negli ultimi anni).
4. Elencare gli elementi di ℘₃({0,1,2,3}) e ℘₆({0,1,2,3})).

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Proprietà di simmetria dei coefficienti binomiali: se k, n∈N e k≤n allora (ⁿ_k)=(ⁿ_n−k). Per gli stessi k ed n, formula ricorsiva: (ⁿ⁺¹_k+1)=(ⁿ_k) + (ⁿ_k+1) e formula chiusa: (ⁿ_k)=n!/(k!(n-k)!) (In verità, la formula ricorsiva vale per arbitrari k e n in N). Triangolo di Tartaglia-Pascal. Per questi argomenti si possono consultare le note Coefficienti Binomiali, che sono però scritte con notazioni e stile leggermente diversi da quelli usati quest'anno in aula. In particolare, la formula chiusa per i coefficienti binomiale è stata dimostrata in aula per induzione e non come nelle note.

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 chiuse (o 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.

Esercizi proposti:

1. Sia S un insieme di cardinaltà 13. Quante sono le parti di S di cardinalità 5? E quante quelle di cardinalità 8? Quante sono le 10-parti di ℘(S)?
2. Posto A={1,2,3,…,7}, indicare la cardinalità di {X ∈ ℘(A) | (5 ∈ X) ∧ (|X| = 4)} e quella di {X ∈ ℘(A) | (6 ∉ X) ∧ (|X| = 5)}.
3. Siano S l'insieme dei primi 90 numeri interi positivi e T una sua parte costituita da 10 elementi. Calcolare la cardinalità dell'insieme delle 5-parti di S e quella dell'insieme delle 5-parti di T. Anacleto partecipa ad un gioco: deve scegliere dieci numeri interi compresi tra 1 e 90; tra i novanta numeri ne verranno poi estratti 5 ed Anacleto vince se (e solo se) tutti e cinque i numeri estratti sono tra quelli che lui aveva scelto. Che probabilità ha Anacleto di vincere?
4. Esercizio nr. 4 da polinomi e strutture algebriche, tralasciando la richiesta sull'elemento neutro.
5. Delle seguenti dieci parti di Z: N, Z-N, ∅, {x ∈ Z | x≥10}, {x ∈ Z | x > −10}, {0}, {1}, {-1}, {0,1,2}, {1,−1}, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.

Discussione degli esercizi proposti nella lezione precedente.

Le intersezioni tra parti chiuse sono a loro volta chiuse. La parte chiusa 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 un semigruppo con più di un elemento neutro a destra.

Nozione di operazione opposta e cenno alla dualità destra-sinistra.

Monoidi. Tra gli esempi: vari insiemi numerici con l'operazione di addizione o di moltiplicazione; per un arbitrario insieme S, (℘(S),∪,∅) e (℘(S),∩,S), e poi il monoide T(S) delle trasformazioni di S (che è commutativo se e solo se |S|≤1).

Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che non sono monoidi oppure sono monoidi ma non sottomonoidi.

Simmetrici destri e sinistri; simmetrici. 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,−), (Q-{∅}, ⋅ ,1,⁻¹), (℘(S),Δ,∅,id_S) per un insieme S. Sottogruppi. 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)⁻¹ = b⁻¹a⁻¹). Il gruppo simmetrico Sym(S):=U(T(S)) su un insieme S. Permutazioni.

Esercizi proposti:

1. Completare l'esercizio nr. 4 da polinomi e strutture algebriche.
2. In (℘(N),∪), si determini la parte stabile generata da {{1},{3,4}}.
3. Tra le seguenti strutture algebriche dire quali sono semigruppi, quali monoidi, quali gruppi: (S,∗), dove S è uno tra N, N^#=N-{0}, Z, Q, Q⁺ (quest'ultimo è l'insieme dei numeri razionali positivi) e ∗ è una tra + e ·.
4. Si studino le strutture (Z,⊕) e (Z, ⊙) dove ⊕ e ⊙ sono le operazioni definite nell'esercizio nr. 5 di polinomi e strutture algebriche. Per ciascuna delle due operazioni si dica se è commutativa, se è associativa, se ammette elementi neutri (a destra, a sinistra). Di che tipo di strutture algebriche si tratta?
5. Sia determini il gruppo degli invertibili in ciascuno dei monoidi: (N,+), (Z,+), (Z,·) e, per un assegnato insieme S, (℘(S),∪) e (℘(S),∩).
6. (N,+) è un sottogruppo di (Z,+)? (Z,+) è un sottogruppo di (Q,+)?

Discussione degli esercizi proposti nella lezione precedente.

Ancora sui gruppi simmetrici: cicli (permutazioni cicliche); trasposizioni (cicli di lunghezza 2). Ogni ciclo è prodotto di trasposizioni, infatti ogni ciclo (a₁ a₂ … a_k) si può fattorizzare come (a₁ a_k)o(a₁ a_k−1)o(a₁ a_k−2) … (a₁ a₃)o(a₁ a₂)); ogni permutazione su un insieme finito X è prodotto di cicli, dunque prodotto di trasposizioni (non è stata fornita dimostrazione di questi fatti). Dato un insieme X, il gruppo Sym(X) è abeliano se e solo se |X| ≤ 2. Notazione: S_n = Sym({1,2,3,…,n}), per ogni intero positivo n.

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 (senza dimostrazione).

Tavole di Cayley (ovvero di moltiplicazione) per operazioni binarie. Visualizzazione di proprietà tramite tavole di Cayley: commutatività, esistenza di neutri e di simmetrici, cancellabilità.

Omomorfismi tra strutture algebriche. Monomorfismi, epimorfismi, isomorfismi. Alcuni esempi; tra essi: l'epimorfismo dal monoide delle parole su un alfabeto al monoide additivo dei naturali che ad ogni parola associa la sua lunghezza; la funzione esponenziale come isomorfismo dal gruppo additivo dei reali al gruppo moltiplicativo dei reali positivi. Discussione sulla nozione generale di isomorfismo. Invarianza delle proprietà algebriche per isomorfismi.

Esercizi proposti:

1. Sia W il monoide delle parole su un fissato alfabeto (non vuoto). Determinarne il gruppo degli invertibili U(W). Quali sono gli elementi cancellabili in W?
2. Sia S un semigruppo e sia T l'insieme degli elementi di S che sono cancellabili a sinistra. T è una parte chiusa in S?
3. Si verifichi che l'applicazione x∈Z →x−1∈Z è un isomorfismo da (Z,+,·) a (Z,⊕, ⊙) (cioè sia da (Z,+) a (Z,⊕) che da (Z,·) a (Z, ⊙)), dove ⊕ e ⊙ sono le operazioni definite nell'esercizio nr. 5 di polinomi e strutture algebriche. Si riguardi l'intero esercizio alla luce di questo fatto.
4. Sia f : X→Y un'applicazione biettiva. Verificare che α ∈ Sym(X) → f o α o f^-1 ∈Sym(Y) è un isomorfismo di gruppi. Concludere che se X e Y sono due insiemi equipotenti allora i gruppi Sym(X) e Sym(Y) sono isomorfi, e che se X è un insieme finito di cardinalità n, Sym(X) è isomorfo ad S_n.
5. Scrivere la tavola di Cayley di T({1,2}) (il monoide delle trasformazioni di {1,2}).
6. Sia G un gruppo con esattamente due elementi: quello neutro, t, e x. Scrivere la tavola di moltiplicazione di G. È possibile concludere che tutti i gruppi con esattamente due elementi sono isomorfi tra loro?
7. Scrivere un isomorfismo tra i gruppi S₂ e (℘({1}),Δ), ed uno tra S₂ e ({1,-1},·), il gruppo degli invertibili di (Z,·).
8. Per un arbitrario insieme S, utilizzando l'applicazione X ∈ ℘(S) → S - X ∈ ℘(S), si verifichi che le strutture (℘(S),∪) e (℘(S),∩) sono isomorfe.

Discussione di alcuni degli esercizi proposti nella lezione precedente. Estendendo uno degli esercizi: tavola di Cayley di un (arbitrario) gruppo di cardinalità 3; i gruppi di cardinalità 3 sono tutti isomorfi tra loro.

Altre osservazioni sulla invarianza di proprietà algebriche per isomorfismi.

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: per ogni elemento x di un semigruppo e per ogni n, m ∈ Z per cui xⁿ e x^m siano definite, x^n+m= xⁿx^m e x^nm= (xⁿ)^m. (Solo della prima di queste due formule è stata data una parziale dimostrazione. Le analoghe formule, in notazione additiva, sono (n+m)x=nx+mx e (nm)x= n(mx)). 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 a è invertibile, allora anche l'inverso di a commuta con b.

Sottosemigruppi, sottomonoidi e sottogruppi generati da singleton. Gruppi ciclici. Esempio: il gruppo (Z,+) è ciclico. Esempio di due gruppi non isomorfi di cardinalità 4 (i soli, a meno di isomorfismi): uno è ciclico, l'altro, cioè (℘({1,2}),Δ) no (vedi esercizi).

Anelli, anelli commutativi, anelli unitari. Esempi: (Z,+,⋅), (Q,+,⋅), (℘(S),Δ,∩). Sottoanelli. Anelli di matrici (come esempi di anelli non commutativi).

Sottoanelli unitari di un anello unitario. Esempi sottoanelli di un anello unitario che non sono unitari oppure lo sono ma non come sottoanelli. Omomorfismi di Omomorfismi di semigruppi e di monoidi; 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 (n1_R)x = nx per ogni n ∈ Z (dimostrazione lasciata per esercizio). Formula del binomio di Newton. Non ne è stata date dimostrazione, chi desidera vederne una la può trovare nella parte finale (enunciato numero 5) delle note sui coefficienti binomiali. Osservazione: se a e b sono elementi di un anello, si ha (a+b)²=a²+b²+2ab se e solo se a e b commutano (cioè ab=ba).

Esercizi proposti:

1. Siano α la permutazione ciclica (1 2 3 4) di S₄ e S={1,2}. Scrivere le tavole di moltiplicazione del gruppo {α⁰,α¹,α²,α³} costituito dalle quattro potenze di α (che è un sottogruppo di S₄, quello generato da α) e del gruppo (℘(S),Δ).
2. Sia (S,·) un semigruppo e sia x∈S. Posto C={a∈S | ax=xa}, provare che C è una parte chiusa (non vuota) di S; e inoltre che se S è un monoide allora C ne è un sottomonoide e se S è un gruppo C ne è un sottogruppo.
3. L'applicazione n∈Z→3n∈Z è un omomorfismo di anelli (o di anelli unitari) da (Z,+,·) a se stesso?
4. L'applicazione X∈℘(Z)→X∩N∈℘(Z) è un omomorfismo di anelli (o di anelli unitari) da (℘(Z),∩,Δ) a se stesso? La ridotta di questa applicazione a ℘(N), cioè X∈℘(Z)→X∩N∈℘(N) è un omomorfismo di anelli (o di anelli unitari) da (℘(Z),∩,Δ) a (℘(N),∩,Δ)?

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Biezione canonica tra l'insieme delle relazioni di ordine stretto e quelle di ordine largo in un assegnato insieme. Insiemi ordinati. Minimo e massimo; loro unicità. Principio di dualità per insiemi ordinati. Proprietà di buon ordinamento di N (rispetto all'ordinamento usuale) e giustificazione del principio di induzione. Cosidetta cosidetta ‘seconda forma’ del principio di induzione, argomentazione per "controesempio minimo".

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 Div(a) dei divisori in M di a coincide con l'insieme Div(b) 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). L'insieme ordinato (N, | ).

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. Divisibilità ed elementi associati nell'anello degli interi e nel monoide (N,·).

Esercizi proposti:

1. (N^#, | ) ha massimo? Se possibile, trovare in (N, | ) un sottoinsieme non vuoto che sia privo sia di massimo che di minimo, uno che abbia minimo ma non massimo ed uno che abbia massimo ma non minimo.
2. Dato un insieme S, si studi la relazione di divisibilità nel monoide (℘(S),∪). È una relazione d'ordine? È una relazione che già conosciamo?
3. Verificare in modo diretto (cioè usando solo la definizione) che, in un monoide commutativo, la relazione di essere elementi associati è di equivalenza.
4. Dato un monoide commutativo M, verificare che per ogni a, b∈M, a e b sono associati se e solo se aM=bM.
5. Dato un monoide commutativo M, per ogni a∈M sono equivalenti: (1): a è invertibile; (2): a è associato all'unità di M; (3) aM=M.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

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.

Altro esempio: nel monoide delle parole su un alfabeto, la congruenza definita dichiarando equivalenti due parole se e solo se esse hanno la stessa lunghezza. Più in generale, se f è un omomorfismo definito in una struttura algebrica, il nucleo di equivalenza di f è una congruenza sul dominio di f (esercizio!).

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.

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à); i quozienti di semigruppi, monoidi, gruppi, anelli, anelli unitari sono strutture dello stesso tipo.

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: ≡₁ è la relazione universale; ≡₀ è 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 Z_m (cioè Z/≡_m). 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; questo numero è minore di |m|). Descrizione esplicita dei quozienti di Z e dei loro elementi: per ogni intero positivo m, Z_m consiste delle classi di 0, 1, 2, …, m−1. (il fatto che queste classi siano a due a due distinte e quindi |Z_m|=m non è stato ancora verificato).

Esercizi proposti:

1. Verificare che, come detto a lezione, se f è un omomorfismo che ha per dominio una struttura algebrica (S,∗), il nucleo di equivalenza di f è compatibile con ∗.
2. Siano W il monoide delle parole su un alfabeto e λ la congruenza in W "avere la stessa lunghezza" vista a lezione. Provare che il monoide quoziente W/λ è isomorfo a (N,+). (Suggerimento: si prenda in esame l'applicazione da W/λ a N che, per ogni parola w in W, associa la lunghezza di w alla classe [w]_λ.)
3. Sia v l'applicazione ‘valore assoluto’ in Z: n∈Z→|n|∈Z. Il nucleo di equivalenza σ di v è compatibile con l'addizione o con la moltiplicazione in Z? In caso di risposta positiva, si descrivano le proprietà algebriche del quoziente Z/σ (munito, ovviamente, dell'operazione quoziente indotta da + o da ·). Questo quoziente è isomorfo ad una struttura già nota?
4. Calcolare 10 mod 7; −10 mod 7; 10 mod −7; −10 mod −7.
5. Si elenchino gli elementi di A ∩ [3]₄, dove A={n∈Z | -10<n<10}.
6. Descrivere, per un arbitrario m∈N, la classe di resto [0]_m. Questa è un sottogruppo di (Z,+)? Esistono altri elementi in Z_m che sono sottogruppi di (Z,+)?

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Epimorfismo canonico (cioè proiezione canonica) da una struttura ad un suo quoziente.

Se i, j, m sono interi tali che 0≤i<j<m allora certamente i e j non sono congrui modulo m. Dunque, le classi [0]_m, [1]_m, [2]_m, … [m−1]_m sono a due a due distinte, quindi, per ogni intero positivo m si ha |Z_m|=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; scriviamo anche a mod b=rest(a,b). Descrizione (alternativa) delle congruenze in Z come nuclei di equivalenza delle funzioni resto.

Cancellabilità negli anelli; divisori dello zero; anelli integri e domini di integrità (si veda la seconda parte delle note sulla cancellabilità). Se m è un intero positivo composto, Z_m non è un dominio di integrità.

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. Vari esempi. Nei gruppi finiti, tutti gli elementi sono periodici. In qualsiasi gruppo, l'elemento neutro è l'unico elemento di periodo 1.

Esercizi proposti:

1. Determinare i divisori dello zero nell'anello (℘({1,2,3},Δ,∩).
2. Se il capodanno di un anno non bisestile capita di domenica, in che giorno della settimana capiterà il capodanno successivo? Perché?
3. Se oggi è martedì, che giorno della settimana sarà tra 1000+49(23³²+1)+700700070701 giorni? (nell'ipotesi, poco realistica, che dopo tanto tempo ci sia ancora qualcuno a contare i giorni della settimana; per giunta senza aver cambiato il nostro calendario).
4. Calcolare 7659776787729! mod 123456789.
5. Posto n=17827456390, calcolare n mod 3, n mod 9 e n mod 11.
6. Calcolare il periodo di: {1} e di {1,2} in (℘({1,2,3},Δ); di [2]₁₀ e di [5]₁₀ in (Z₁₀,+); della permutazione f definita da f(1)=2, f(2)=1, f(3)=4, f(4)=3 in S₄.
7. Verificare che in ogni gruppo simmetrico, per ogni intero positivo k i cicli di lunghezza k hanno periodo k.

Discussione degli esercizi proposti nella lezione precedente.

Se un elemento x di un gruppo ha periodo finito λ, allora, per ogni n, m ∈ Z, si ha xⁿ=x^m se e solo se n e m sono congrui modulo λ. In particolare, xⁿ=1 se e solo se λ divide n; l'inverso di x è x^λ−1. Inoltre, in queste ipotesi, il sottogruppo (ciclico) generato da x ha ordine λ.

Caratteristica di un anello unitario. Esempi. Z ha caratteristica 0, per ogni intero positivo m, Z_m ha caratteristica m, per ogni insieme non vuoto S, (℘(S,Δ,∩) ha caratteristica 2. In un anello unitario di caratteristica λ si ha λx=0 per ogni elemento x.

Per ogni m ∈ N^#, il gruppo additivo di Z_m è ciclico di cardinalità m. A meno di isomorfismi, questi gruppi e (Z,+) sono i soli gruppi ciclici; quest'ultimo fatto non è stato dimostrato.

Utilizzo della nozione di periodo per i calcoli di potenze in aritmetica modulare.

Fattorizzazione in monodi commutativi regolari. Divisori banali. Elementi irriducibili ed elementi primi. Entrambe le proprietà si conservano nel passaggio da un elemento ad un suo associato. Fattorizzazioni "essenzialmente uguali" (cioè uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati). Monoidi fattoriali Alcuni 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. Anelli fattoriali (esempi: Z, tutti i campi).

Senza fornire dimostrazioni, si è accennato a questi fatti: se M è un monoide commutativo regolare, allora ogni elemento primo di M è irriducibile; inoltre, M è fattoriale se e solo se (1) ogni suo elemento non invertibile è prodotto di irriducibili e (2) ogni suo elemento irriducibile è primo. Ancora: M è fattoriale se e solo se ogni suo elemento non invertibile è prodotto di primi. Dunque, nei monodi fattoriali (in particolare, nel monoide moltiplicativo degli interi positivi) le nozioni di elemento primo e di elemento irriducibile sono equivalenti.

Descrizione dell'insieme dei divisori di un elemento in un monoide fattoriale M a partire da una sua fattorizzazione in irriducibili (o, meglio, da una fattorizzazione primaria): se a∈M e a=p₁^a₁p₂^a₂…p_n^a_n è una sua decomposizione primaria (dunque, i p_i sono irriducibili a due a due non associati, e gli esponenti a_i sono interi positivi, i divisori di a in M sono tutti e soli gli elementi della forma up₁^b₁p₂^b₂…p_n^b_n, dove u è un invertibile e ciascuno degli esponenti b_i è un numero naturale minore o uguale ad a_i.

Esercizi proposti:

1. Verificare che [2]₆₃ è invertibile in (Z₆₃,· ) e calcolarne il periodo. Dopo aver fatto ciò, calcolare 2^{65772846764193659370} mod 63.
2. Il monoide (N,+,0) è fattoriale? Quali sono i suoi elementi irriducibili? Il monoide additivo dei razionali non negativi è fattoriale? Quali sono i suoi elementi irriducibili?
3. Perché, senza effettuare alcun calcolo, possiamo immediatamente stabilire che 9000000000000000000000000000 non è multiplo di 17?
4. Esercizi 7 e 8 da Tautologie, insiemi, aritmetica.
5. Elencare i divisori in N di 270 ed i divisori in  Z di 60.
6. Quanti sono i divisori in N di 2⁴·7²·41⁴⁴?
7. Esiste n ∈ N^# tale che 85 divida 2¹¹⁺ⁿ·3⁷ⁿ·7^n(3n+1)·13⁶ⁿ?
8. 2⁵·3⁵·5⁶ divide 2⁶·3¹⁵·7²·11 in Z?
9. Qual è il minimo intero positivo n tale che 10⁶ (cioè un milione) divida n! ?

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Fattorizzazioni banali e non banali di elementi in monodi commutativi regolari.

Cenno al crivello di Eratostene. 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.

Massimi comuni divisori e minimi comuni multipli di una parte di un monoide commutativo. I massimi comuni divisori costituiscono una classe di elementi associati; analogo enunciato vale per i minimi comuni multipli. 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. Osservazione: 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 interi (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, 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).

Esercizi proposti:

1. Esercizi 5 e 11 in Tautologie, insiemi, aritmetica.
2. Aldo deve a Bice 133 talleri boemi. Sapendo che il tallero boemo viene emesso solo in monete da 35 e da 224 talleri (e non esiste in forma di banconota, e nessuna banca o servizio finanziario permette operazioni in talleri boemi), potrà Aldo pagare a Bice la somma che le deve? Se sì, in che modo?

Discussione di alcuni degli esercizi proposti nella lezione precedente, con ulteriorii commenti sull'algoritmo euclideo e sul teorema di Bézout.

Conseguenze del Teorema di Bézout: caratterizzazione delle coppie di interi coprimi (cioè con 1 come massimo comun divisore); Lemma di Euclide: siano a,b,c ∈ Z con a e b coprimi; se a divide bc allora a divide c. Si è accennato al fatto che da questo lemma si può dedurre l'essenziale unicità delle fattorizzazioni in irriducibili in N^#, completando così la dimostrazione del Teorema Fondamentale dell'Aritmetica.

Equazioni congruenziali (di primo grado). Equivalenza tra il problema di risolvere un'equazione congruenziale e quello di risolvere un'equazione diofantea (dei tipi considerati). Criterio di esistenza di soluzioni per le equazioni congruenziali. Descrizione dell'insieme delle soluzioni. Algoritmo risolutivo, e metodi di semplificazione. Appunti su questi argomenti sono disponibili nel sito docenti della Professoressa Leone.

Elementi invertibili nei quozienti di Z. Se m∈N^#, l'anello Z_m è un campo se e solo se m è primo.

Introduzione alla funzione di Eulero; il numero degli invertibili in un quoziente di Z.

Esercizi proposti:

1. Esercizi 6, 9, e 10 in Tautologie, insiemi, aritmetica.
2. Nell'anello Z₁₅ si individuino gli elementi invertibili, i divisori dello zero, quelli cancellabili, quelli idempotenti.
3. Calcolare φ(1000), dove φ è la funzione di Eulero. Confrontare φ(1000) con il prodotto φ(100)φ(10).

Discussione di uno degli esercizi proposti nella lezione precedente, con qualche ulteriore commento ed esempio sulla funzione di Eulero.

Caso speciale del teorema di Lagrange per gruppi: se G è un gruppo finito e |G|=n, si ha xⁿ=1_G per ogni x∈G. Applicazioni all'artimetica modulare: Teorema di Fermat-Eulero e Piccolo Teorema di Fermat. Cenni alle applicazioni di questi risultati alla crittografia.

Elementi (tra loro) confrontabili e non confrontabili in insiemi ordinati. Ordinamenti totali. Elementi minimali e massimali. Esempi. 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 insiemi con più elementi minimali ed esempio di un insieme con un unico elemento minimale che però non è minimo. Osservazione: 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.

Minoranti e maggioranti di parti in un insieme ordinato. Estremo inferiore ed estremo superiore di una parte di un insieme ordinato. Confronto tra le proprietà di essere minimo (massimo) e di essere estremo inferiore (superiore) per una parte di un insieme ordinato.

Diversi esempi, tra cui:

• cosiddetta completezza dei reali: ogni parte di R che, rispetto all'ordinamento usuale, abbia minoranti (risp. maggioranti) ha estremo inferiore (risp. superiore);
• estremi inferiori e superiori in (N,| ).
• estremi inferiori e superiori in (℘(S),⊆), per un insieme S;

Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli.

In ogni reticolo, ogni elemento minimale (risp. massimale) è minimo (risp. massimo), dunque: reticoli finiti sono limitati (cioè hanno minimo e massimo; non vale il viceversa).

Esercizi proposti:

1. Sapendo che 4567 è un numero primo, si calcolino: 2976⁴⁵⁶⁷ mod 4567,  φ(45670), 2976¹⁸²⁶⁴ mod (5·4567) e 2976¹⁸²⁶⁴ mod 45670.
2. Si determinino (eventuali) elementi minimi, massimi, minimali e massimali in ciascuno dei seguenti insiemi, ordinati per divisibilità: {18,6,12,4}, {n ∈ N |  n ≤ 10}, N − {1,2,3}.
3. Si determinino (eventuali) elementi minimi, massimi, minimali e massimali in ciascuno dei seguenti insiemi, ordinati per inclusione: ℘(N)−{∅}, ℘_f(N) (questo è l'insieme delle parti finite di N), S={X∈℘_f(N) | X ha cardinalità dispari}.
4. Nell'insieme S dell'esercizio precedente, ordinato per inclusione, si determinino, se esistono, inf{A, B} e inf{A,C}, dove A={n∈N | n<9}, B={n∈N | 6<n<20}, C={n∈N | 5<n<9}. (S,⊆) è un reticolo?
5. Per ogni n nell'insieme {4,6,9,12,19,20,30} disegnare il diagramma di Hasse dell'insieme Div(n) dei numeri naturali divisori di n, ordinato per divisibilità (in N). Tra gli insiemi ordinati così ottenuti si cerchino tutte le coppie di insiemi ordinati tra loro isomorfi.
6. Si disegni il diagramma di Hasse dell'insieme {1,2,5,20,50,100}, ordinato per divisibilità. Questo è un reticolo?
7. Fornire un esempio di reticolo infinito limitato.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Il duale di ogni reticolo è un reticolo; principio di dualità per reticoli.

In un insieme ordinato S, siano A e B due parti dotate di estremo inferiore: a=inf A e b=inf B. Allora l'insieme dei minoranti in S di A∪B coincide con l'insieme dei minoranti in S di {a,b}. Di conseguenza, A∪B ha estremo inferiore se e solo se {a,b} ha estremo inferiore, e, nel caso esistano, questi estremi inferiori coincidono. (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 (altra giustificazione del fatto che ogni reticolo finito è limitato, cioè dotato di minimo e massimo). Reticoli completi (esempi: l'insieme delle parti di un insieme, ordinato per inclusione; N, ordinato per divisibilità) e non completi (esempi: N e l'intervallo dei razionali compresi tra 0 e 1, con l'ordinamento usuale; il secondo è un reticolo limitato non completo).

Reticoli come strutture algebriche; operazioni reticolari. Esempio: per un insieme S, comparazione tra (℘(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. Gli insiemi totalmente ordinati sono complementati se e solo se hanno al più due elementi.

Reticoli distributivi. Esempi: (℘(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. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff.

Reticoli booleani ed algebre di Boole. Il duale di un reticolo complementato (risp. distributivo, booleano) è necessariamente complementato (risp. distributivo, booleano). 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: i reticoli booleani finiti hanno per cardinalità una potenza di 2; due reticoli booleani finiti equipotenti sono necessariamente isomorfi. 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. 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.

Cenni alle applicazioni delle algebre di Boole in logica (algebra di Boole associata ad un linguaggio).

Esercizi assegnati:

1. Siano x un elemento ed A una parte di un insieme ordinato (S,≤). Se A ha in S estremo inferiore a, allora x è un minorante di A se e solo se x ≤ a.
2. Tra i reticoli Div(n) considerati nell'esercizio 5 della scorsa lezione, quali sono booleani?
3. Verificare in modo diretto che i reticoli trirettangolo e modulare non sono distributivi.
4. Esercizi nr. 5, 6 e 7 da relazioni binarie. Ai fini di questi esercizi, considerare l'espressione ‘algebra di Boole’ come sinonimo di ‘reticolo booleano’.
5. Il campo Z₂ è un anello booleano? Quali anelli booleani sono domini di integrità?
6. Completare in tutti i dettagli la dimostrazione della correttezza della costruzione, mostrata a lezione, di un reticolo booleano a partire da un anello booleano.
7. Dato un anello (R,+,⋅), ed un intero positivo n, si consideri l'insieme Rⁿ delle n-ple di elementi di R. In questo insieme, si definiscano due operazioni + e ⋅ come segue: per ogni a₁, a₂, …, a_n, b₁, b₂, …, b_n in R si ponga (a₁,a₂,…,a_n)+(b₁,b₂,…,b_n)=(a₁+b₁,a₂+b₂,…,a_n+b_n) e (a₁,a₂,…,a_n)⋅(b₁,b₂,…,b_n)=(a₁b₁,a₂b₂,…,a_nb_n). Si verifichi che (Rⁿ,+,⋅) è un anello, e che esso è booleano se e solo se (R,+,⋅) è booleano.
8. Sia S={a,b,c} un insieme tale che |S|=3. Si scriva esplicitamente un isomorfismo dall'anello booleano (℘(S),Δ,∩) all'anello Z₂³ costruito, come nell'esercizio precedente, a partire dall'anello Z₂.
9. Sia A un anello booleano e sia B una sua parte. Considerata anche la struttura di algebra di Boole su A (definita come a lezione), si verifichi che B è una sottoalgebra di Boole di A se e solo se B è un sottoanello unitario di A. Come si può enunciare il teorema di Stone per anelli boooleani?

Discussione di alcuni degli esercizi proposti nella lezione precedente, con le seguenti, ulteriori, osservazioni sulle algebre di Boole.

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} (confrontare con gli esercizi 7 e 8 della lezione scorsa).

Cenni alle applicazioni delle algebre di Boole in logica (algebra di Boole associata ad un linguaggio).

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. Primo cenno alle componenti connesse di un grafo.

Sottografi. 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). Esempi, tra cui il problema dei sette ponti di Königsberg.

Esercizi assegnati:

1. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) su quattro vertici.
2. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) connessi su cinque vertici.
3. Si considerino i grafi G=(V,L) che verificano la proprietà p: “|V|=6=|L| ed esistono in G (almeno) due vertici di grado 3 ed (almeno) tre vertici di grado 2”.
   1. Se un grafo G verifica p, quali sono i gradi dei suoi vertici?
   2. Disegnare, se possibile, un grafo che verifichi p.
   3. Disegnare, se possibile, due grafi tra loro non isomorfi che verifichino p.
   4. Disegnare, se possibile, un grafo non connesso che verifichi p.
   5. Disegnare, a meno di isomorfismi, tutti i grafi che verificano p.
4. Tutti gli esercizi da Grafi, ad eccezione dell'esercizio nr. 4. Ignorare le domande su alberi e foreste.

Discussione di uno degli esercizi proposti nella lezione precedente; metodi di costruzione di grafi finiti con assegnati invarianti.

Distanza in un multigrafo. Componenti connesse di un multigrafo.

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).

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario. Definizione e prime proprietà. Proprietà universale per gli anelli dei polinomi; un cenno è stato fatto a come verificare l'unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata). Altre applicazioni della proprietà fondamentale: omomorfismo di sostituzione; per ogni intero positivo m, epimorfismo da Z[x] a Z_m[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. Applicazione polinomiale definita da un polinomio. Osservazione: polinomi distinti possono definire la stessa applicazione polinomiale: esempi costruiti su anelli finiti e su anelli booleani.

Note (diverse) sui polinomi sono qui e nel sito docenti della Professoressa Leone.

Esercizi assegnati:

1. Completare gli esercizi da Grafi, ad eccezione dell'esercizio nr. 4.
2. Calcolare il grado del polinomio fg dove f e g sono, rispettivamente, i polinomi 1+3x e 1−3x dell'anello Z₉[x].

Per il contenuto della lezione di oggi si vedano le sezioni 4–9 degli appunti sui polinomi in questo sito (esercizi ed esempi sono consigliati, ma facoltativi) o le corrispondenti sezioni degli appunti sui polinomi nel sito docenti della Professoressa Leone.

Discussione di uno degli esercizi proposti nella lezione precedente.

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. Senza dimostrazione: A[x] è un anello fattoriale se e solo se lo è A. Ad esempio, sono fattoriali Z[x] e, per ogni campo K, K[x].

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 di un massimo comun divisore e Teorema di Bézout.

Radici di un polinomio. Teorema del resto e Teorema di Ruffini. Per domini di integrià: Teorema di Ruffini generalizzato e conseguenze: un polinomio non nullo a coefficienti in un dominio di integrità ha al più tante radici quanto è il suo grado; principio di identità dei polinomi (a coefficienti in un dominio di integrità infinito).

Fattorizzazioni nell'anello dei polinomi su un campo K. Caratterizzazione dei polinomi irriducibili in K[x]. Esistenza di radici ed irriducibilità. Descrizione dei polinomi irriducibili sul campo reale e sul campo complesso; i polinomi di grado dispari in R[x] hanno sempre radici in R. Polinomi sui razionali e sugli interi: radici razionali di un polinomio in Z[x], criterio di irriducibilità di Eisenstein.

Esercizi assegnati:

1. Determinare il massimo comun divisore monico in Q[x] tra x⁹−1 e x⁵−1.
2. Elencare i polinomi irriducibili di grado 2 o 3 in Z₂[x].
3. In Z₃[x] si consideri il polinomio f=x⁴+x³+x²+2x+1. Dopo averne determinato le radici, lo si fattorizzi nel prodotto di un invertibile e di polinomi irriducibili monici. Si ripeta l'esercizio (sempre in Z₃[x]) per 2x⁴+x³+x²+x+2 al posto di f.