Corso di Algebra - Corso di recupero, a.a. 2007/08
Le lezioni

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

Rudimenti di logica proposizionale. I principali connettivi proposizionali (descritti semanticamente): negazione, congiunzione, disgiunzione (inclusiva), condizionale (implicazione) e bicondizionale (equivalenza). Disgiunzione esclusiva. Tabelle di verità. Tautologie, contraddizioni e forme contingenti. Alcune tautologie classiche: principî del terzo escluso e di non contraddizione, leggi di De Morgan, alcune tautologie sulle implicazioni: interpretazione di una implicazione come disgiunzione, negazione di una implicazione, bicondizionale come doppia implicazione.
Delle note disponibili in questo sito sono molto rilevanti per il contenuto di questa lezione: tavola dei connettivi binari e esempi di tautologie. Nella prossima lezione sarà utilizzata anche la lista di tautologie e identità insiemistiche; per seguire utilmente la lezione sarà bene avere queste tre note con sé.

Esercizi assegnati:

1. Utilizzando le tabelle di verità verificare le tautologie 2.5, 3.5 e 5.3 da esempi di tautologie.
2. Verificare che il bicondizionale viene negato dalla disgiunzione esclusiva, cioè che la forma (p ⇔ q)⇔(¬(p XOR q)) è una tautologia (XOR indica il connettivo di disgiunzione esclusiva).

Esercizi sugli argomenti della lezione precedente.

Altre tautologie sull'implicazione: legge di contrapposizione, transitività.

Cenni alla logica dei predicati. Quantificatori: universale (∀) ed esistenziale (∃) e loro uso; frasi contenenti più quantificatori (esempi di frasi delle forme ∀x∃y… o ∃y∀x…). Cenni alle nozioni di occorrenza libera e legata di una variabile; le formule contenenti variabili libere non sono proposizioni. 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à). Vari modi per descrivere insiemi; cenni a problemi fondazionali.

Esercizi assegnati:

1. Verificare le tautologie 2.1, e 3.4 da esempi di tautologie.
2. Negare: (∀x)(∃y)((p∧q)⇒(r⇒(s∨t)))
3. Negare la frase: 'La prossima settimana, ogni giorno, se pioverà prenderò l'ombrello oppure metterò l'impermeabile'.
4. Riflettere su {x|x∉x}.

Discussione degli esercizi proposti nella lezione precedente, con osservazioni sul paradosso di Russell.

Cenno all'assioma di separazione. Scritture 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. Inclusione tra insiemi. La regola della "doppia inclusione": (∀ A,B)(A=B ⇔ (A⊆B ∧ B⊆A)). Discussione sulla distinzione tra appartenenza e inclusione. Il singleton di un insieme. Per ogni insieme x si ha x∉x, quindi x≠{x}.

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 (da completare), transitività dell'implicazione). Complemento relativo (differenza) tra insiemi. Diagrammi di Euler-Venn. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare identità insiemistiche.

Esercizi assegnati:

1. Elencare gli elementi degli insiemi:
   • {n∈Z|(n>5)∧(n<14)}
   • {n∈Z|(∃m∈Z)(n+m=8)}
   • {n∈Z|(∃m∈N)(n+m=8)}
   • {n∈Z|(∀m∈N)(n+m=8)}
2. Verificare in dettaglio la tautologia (a∧(b∨c))⇔((a∧b)∨(a∧c)).
3. Rappresentare su diagrammi di Venn (per insiemi A, B, C) gli insiemi A−(B−(A∩C)) e (A−B)∪(B∩C); confrontare il risultato e trarne conclusioni. Vale: (∀A,BC) (A−(B−(A∩C)=(A−B)∪(B∩C))?

Discussione degli esercizi proposti nella lezione precedente.

Altre discussioni ed esempi sui diagrammi di Euler-Venn, diagrammi di Euler-Venn generici. Dimostrare la verità o la falsità di identità insiemistiche.

Completamento di tautologie e identità insiemistiche. Tra le varie formule insiemistiche viste, particolarmente importanti sono quelle di De Morgan.

Differenza simmetrica tra due insiemi e disgiunzione esclusiva (XOR). Associatività dei connettivi ⇔ e XOR; la seconda ottenuta dalla prima osservando la tautologia (a XOR b)⇔((¬a)⇔b) e l'equivalenza tra (a⇔b)⇔c e (a XOR b) XOR c. Associatività della differenza simmetrica.

Cardinalià di un insieme finito. Cardinalità della differenza tra due insiemi finiti, discussione di qualche errore frequente. 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.

Esercizi assegnati:

1. Esercizi nr. 1 e 2 da tautologie, insiemi, aritmetica.
2. Verificare: (∀A,B)(A−B=A−(A∩B)).
3. Verificare: (∀A,B)(A⊆B ⇔  A Δ B=B−A).
4. Verificare l'associatività della differenza simmetrica anche tramite diagrammi di Euler-Venn.
5. Verificare in dettaglio il principio di inclusione-esclusione nel caso dell'unione di tre (arbitrari) insiemi finiti.
6. Dati due insiemi A e B tali che |A|=100, |B|=70 e |A∪B|=150, calcolare |A∩B|.

Discussione degli esercizi proposti nella lezione precedente.

Unione e intersezione unarie, cioè unione di un insieme e intersezione di un insieme non vuoto.

L'insieme delle parti ℘(S) di un insieme S; inoltre, per ogni numero naturale k, l'insieme ℘_k(S) delle k-parti (cioè parti di cardinalità k) di S. Esempi: descrizione di ℘(∅) e di ℘({a}) per un insieme a; descrizione di ℘₀(S) e ℘₁(S) per un insieme S.

Descrizioni di un insieme con scritture della forma {t(x,y,z,…) | p(x,y,z,…)} (abbreviazione di {a | (∃x,y,z,…)(a=t(x,y,z,…) ∧ p(x,y,z,…)}).

Coppie ordinate. Il prodotto cartesiano A × B tra due insiemi A e B. La diagonale Δ_A={(x,x)|x∈A} di un insieme A.

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.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche, antisimmetriche, transitive. Confronto tra queste proprietà. Esempi. Relazioni di equivalenza in un insieme.

Esercizi assegnati:

1. Descrivere, elencandone gli elementi, ℘({1,2}), ℘₃({0,1,2,3}) e ℘₆({0,1,2,3}).
2. 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.
3. Descrivere, elencandone gli elementi, {1,2,5} × {1,3}.
4. Assegnati insiemi A e B, trovare condizioni necessarie e sufficienti affinché:
   • A × B = ∅;
   • A × B = B × A.
5. Descrivere, elencandone gli elementi, il grafico della relazione binaria α in S:={1,2,3} definita ponendo a αb⇔a≤b per ogni a,b∈S. Studiare le proprietà di α (è riflessiva?, antiflessiva?, simmetrica? etc.).
6. Sempre per S:={1,2,3}, rappresentare graficamente la corrispondenza ((S,S),{(1,1),(1,3),(2,3),(3,3)}) e studiarne le proprietà.
7. Esercizio nr. 1 da relazioni binarie, escluso il punto (f) e le domande su ordinamenti.
8. Esercizio nr. 7 dal compito di marzo 08, solo per le relazioni α e β ed escluse le domande sulle relazioni d'ordine. Ripetere l'esercizio per la relazione φ∈Rel(Z) definita ponendo, per ogni a,b∈Z, a φ b &hArr (a<2⇒b>2).

Discussione di alcuni degli esercizi proposti nella lezione precedente. Per arbitrari insiemi finiti A e B si ha |A × B|=|A| · |B|.

Applicazioni tra insiemi. Il problema della "buona" (corretta) definizione di un'applicazione; esempi. Introdotte le notazioni Map(A,B), B^A 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, a^f, f_a) 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. L'immagine im f di un'applicazione f. Applicazioni biettive.

Il nucleo di equivalenza di (o equivalenza associata a) un'applicazione. Classi di equivalenza e loro proprietà fondamentali: rispetto ad una fissata relazione di equivalenza ρ in un insieme A: per ogni a, b∈A si ha

• a ρ b ⇔ b ρ a ⇔ a∈[b]_ρ ⇔ b∈[a]_ρ ⇔ [a]_ρ=[b]_ρ;
• a∈[a]_ρ, quindi [a]_ρ≠∅;
• [a]_ρ≠[b]_ρ ⇒ [a]_ρ∩[b]_ρ=∅.

L'insieme quoziente definito da un'equivalenza.

Esercizi assegnati:

1. Posto 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²}
2. Esercizio nr. 3 da tautologie, insiemi, aritmetica, esclusa l'applicazione al punto f.
3. Sia f un'applicazione. Allora f è iniettiva se e solo se il suo nucleo di equivalenza è…?. Inoltre, f è costante se e solo se il suo nucleo di equivalenza è…?.
4. Sia X={1,2,3,4,5}. Verificare che la relazione binaria ρ definita in ℘(X) ponendo (∀a,b ∈ ℘(X)) (a ρ b ⇔ |a|=|b|), è di equivalenza. Descrivere esplicitamente l'insieme quoziente ℘(X)/ρ e la classe [{1,3,5}]_ρ.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Partizioni di un insieme. Gli insiemi quoziente sono partizioni. In modo più esplicito: biezione canonica tra Eq(A) e Part(A) (insiemi delle relazioni di equivalenza e delle partizioni di un insieme A); di questa applicazione è stata dimostrata la suriettività ma non ancora l'iniettività.

Proiezione canonica di un insieme su un suo quoziente; ogni equivalenza è il nucleo di equivalenza di un'applicazione.

Esercizio: descrizione delle relazioni binarie che siano contemporaneamente simmetriche e antisimmetriche; l'uguaglianza è l'unica relazione di equivalenza antisimmetrica.

Prodotto relazionale tra corrispondenze; corrispondenze componibili.

Esercizi assegnati:

1. Si scrivano tutte le partizioni dell'insieme S={1,2,3} ed i grafici di tutte le relazioni di equivalenza su S. Si descriva in dettaglio la biezione canonica Eq(S) →Part(S).
2. Siano α e β le corrispondenze così definite: α : A→B, e β : B→C, dove A={1,2}, B={1,2,3,4,5} e C={1,2,3}, il grafico di α è {(1,1),(1,3),(1,4),(2,4),(2,5)}, quello di β è {(1,3),(3,2),(4,2),(5,3)} ∪ ({2}×C). Scrivere il grafico della corrispondenza prodotto αβ : A→C.
3. … ci sono ancora diversi esercizi in sospeso dalle lezioni precedenti; non dimenticarsene …

Discussione degli esercizi proposti nella lezione precedente.

Partizioni banali e corrispondenti equivalenze (banali: uguaglianza e relazione universale).

Richiamo ed esempi sul prodotto relazionale. Associatività del prodotto relazionale. Il prodotto relazionale tra due applicazioni (componibili) è un'applicazione. 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 in un insieme; sua neutralità (moltiplicando a destra o a sinistra una corrispondenza α per un'applicazione identica si ottiene α).

Una relazione binaria di grafico ρ è transitiva se e solo se ρ²⊆ρ. Inoltre ρ è simmetrica se e solo se ρ^-1⊆ρ (è stata così introdotta la nozione di relazione inversa), ovvero se e solo se ρ^-1=ρ.

Iniettività e suriettività per applicazioni composte: se f e g sono applicazioni componibili, allora fg è iniettiva (risp. suriettiva) se f e g sono entrambe iniettive (risp. suriettive); se fg è iniettiva (risp. suriettiva) allora f è iniettiva (risp. g è suriettiva). Esempi e controesempi.

Introdotte le notazioni InjMap(A,B) e SurMap(A,B) per gli insiemi delle applicazioni iniettive o suriettive da A a B

Applicazione immagine (da ℘(A) a ℘(B) ) e applicazione antiimmagine (da ℘(B) a ℘(A) ) definita da un'applicazione da A a B.

Sezioni e retrazioni di un'applicazione. Un'applicazione è suriettiva se e solo se ha sezioni. Descrizione delle sezioni di un'assegnata applicazione; esempi.

Esercizi assegnati:

1. Una relazione binaria di grafico ρ è antisimmetrica se e solo se ρ∩ρ^-1⊆ …?
2. Esercizio nr. 4 da tautologie, insiemi, aritmetica.
3. Sia S={1,2,3,4} e sia α : S→S l'applicazione definita dalla matrice di prima riga (1,2,3,4) e seconda riga (1,1,3,2). Si descrivano tutte le potenze α², α³, α⁴ … (potenze calcolate rispetto al prodotto operativo). Si studi iniettività e suriettività di α e di ciascuna di queste sue potenze.
4. Siano A={1,2,3,4,5,6} e B={1,2,3}. Siano f e g le applicazioni da A a B definite ponendo 1^f=1^g=3, 2^f=2^g=3, 3^f=3^g=1, 4^f=4^g=3, 5^f=5^g=1, 6^f=2, 6^g=1. Scrivere tutte le sezioni di f e tutte le sezioni di g.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Un'applicazione è iniettiva se e solo se o ha dominio vuoto oppure ha una retrazione; ogni applicazione il cui dominio ha meno di due elementi è iniettiva.

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. Inoltre, un'applicazione f è biettiva se e solo se ha una ed una sola sezione. 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. Un caso è quello dalla biezione canonica tra gli insiemi delle equivalenze e delle partizioni di un assegnato insieme; è stata completata la dimostrazione della biettività di quest'applicazione.

Restrizioni e prolungamenti di applicazioni. L'immersione in un insieme di una sua parte. Legami tra queste nozioni: 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.

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 esplicita dell'insieme delle retrazioni di un'assegnata applicazione.

Esercizi assegnati:

1. Provare che ogni applicazione ha una restrizione iniettiva.
2. Siano A={1,2,3,4}, S={1,2,3,4,5,6} e, per tre elementi a due a due distinti u, v e z, B={u,v,z}. Si elenchino tutti i prolungamenti a S dell'applicazione f : A→B definita ponendo 1^f=v, 2^f=u, 3^f=4^f=z.
3. Esercizi da nr. 1 a nr. 4 da Sezioni e Retrazioni.

Oltre alle note già utilizzate, dalla prossima lezione portare con sé Il Teorema di Omomorfismo per Insiemi.

Discussione di alcuni degli esercizi proposti nella lezione precedente. Gli esercizi da Sezioni e Retrazioni saranno ridiscussi.

Un'applicazione il cui dominio abbia più di un elemento è biettiva se e solo se ha una ed una sola retrazione.

Il numero delle applicazioni e il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti.

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

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

Coimmagine di un'applicazione (come quoziente rispetto al nucleo di equivalenza). Teorema di omomorfismo per insiemi (fattorizzazione canonica di un'applicazione).

Esercizi assegnati:

1. Avendo posto, per ogni n∈N, I_n={1,2,3,…,n}, si calcoli |Map(A,B)| e |InjMap(A,B)| in ciascuno dei seguenti casi: A=I₄ e B=I₇, A=I₇ e B=I₄, A=I₇−I₄ e B=I₃, A=℘(I₄) e B=℘(I₇), A=I₄×℘(I₄) e B=I₇×℘(I₄).
2. Scrivere tutte le applicazioni iniettive e tutte le applicazioni suriettive tra gli insiemi S={a,b} e T={u,v,z}, dove |S|=2 e |T|=3.

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Il fattoriale n!=1·2·3·…·n di un numero naturale. Se S è un insieme finito di cardinalità n, l'insieme delle permutazioni di S ha cardinalità n!

Principio di induzione e seconda dimostrazione (ricorsiva) dell'uguaglianza |℘(S)|=2^|S| per un insieme finito S.

Coefficienti binomiali: definizione e proprietà elementari (in mancanza di simboli appositi in HTML, scriviamo qui (n:k) per il coefficiente binomiale n su k): per ogni intero positivo n e per ogni naturale k minore di n, si ha (n:0)=(n:n)=1 e (n:1)=n;  (n:0)+(n:1)+…+(n:n)=2ⁿ; (n:k)=(n:n-k); (n+1:k+1)=(n:k)+(n:k+1). Triangolo di Tartaglia-Pascal. Formula esplicita: (n:k)=n!/(n-k)!k!.

Esercizi assegnati:

1. Usare il principio di induzione per provare che, per ogni n∈N, si ha 1+2+…+n = n(n+1)/2.
2. Sia S un insieme di cardinaltà 12. Quante sono le parti di S di cardinalità 5? E quante quelle di cardinalità 7? Quante sono le 10-parti di ℘(S)?
3. Posto A={1,2,3,…,8}, indicare la cardinalità di {X∈℘(A) | (5∈X) ∧ (|X|=4)} e quella di {X∈℘(A) | (6∉X) ∧ (|X|=5)}.

Discussione degli esercizi proposti nella lezione precedente.

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à. Diversi esempi.

Elementi neutri a sinistra e a destra; elementi neutri e loro unicità (se, in una assegnata struttura, s è un elemento neutro a sinistra e d è un elemento neutro a destra, allora s=d e quindi s è (l'unico) elemento neutro, 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. Notazioni per le strutture algebriche che coinvolgano anche operazioni unarie o nullarie (come nel caso dei monoidi). Tra gli esempi: il monoide T(S) delle trasformazioni di un insieme S (non è commutativo se |S|>1). Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che non sono monoidi oppure sono monoidi ma non sottomonoidi.

Simmetrici destri e sinistri in una struttura con elemento neutro; simmetrici, elementi simmetrizabili. Unicità, nel caso dei monoidi (se, per un elemento a 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".

L'insieme U(M) degli elementi simmetrizzabili di un monoide M. Questa è una parte stabile di M; formula per il calcolo del simmetrico di un prodotto in un monoide.

Esercizi assegnati:

1. Esercizio nr. 4 da polinomi e strutture algebriche.
2. 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 stabili rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
3. Calcolare l'insieme degli elementi simmetrizzabili di ciascuno dei seguenti monoidi: (℘(S),∩,S), (℘(S),∪,∅), (Z,+,0), (Z,·,1).

Discussione degli esercizi proposti nella lezione precedente.

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.

Gruppi. Il gruppo degli invertibili (elementi simmetrizzabili) U(M) di un monoide M. Esempi, tra i quali il gruppo simmetrico Sym(X):=U(T(X)) su un insieme X. Cicli (permutazioni cicliche), traposizioni. Gruppi abeliani; per ogni n∈N^#, il gruppo S_n := Sym({1,2,…n}) è abeliano se e solo se n≤2.

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

Tavole di moltiplicazione (di Cayley) per operazioni binarie. Nozione di isomorfismo.

Esercizi assegnati:

1. 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 ·.
2. Determinare l'insieme degli elementi cancellabili in ciascuno dei seguenti monoidi: (Z,+), (Z,·), (℘(N),∪), (℘(N),∩).
3. Scrivere la tavola di moltiplicazione di T({1,2}) (il monoide delle trasformazioni d {1,2}).
4. Dimostrare che l'insieme {f ∈ S₅ | 5^f = 5} costituisce un sottogruppo di S₅.

Discussione degli esercizi proposti nella lezione precedente.

Omomorfismi tra strutture algebriche. Monomorfismi, epimorfismi. Isomorfismi, come omomorfismi invertibili. Le proprietà algebriche sono invarianti per isomorfismi. Esempi notevoli di isomorfismi. Omomorfismi di semigruppi, di monoidi, di gruppi. Diversi esempi, tra i quali qualche esempio di omomorfismo di semigruppi tra monoidi che non è, però, un omomorfismo di monoidi. Gli omomorfismi di semigruppi tra gruppi sono sempre omomorfismi di gruppi.

Relazioni d'ordine (o ordinamenti). Ordinamenti stretti ed ordinamenti larghi in un insieme, sostanziale equivalenza tra le due nozioni (biezione tra l'insieme degli ordinamenti stretti e quello degli ordinamenti larghi in un dato insieme); esempi. Alcuni insiemi ordinati: i reali, razionali, gli interi, i naturali, ordinati secondo l'ordinamento usuale. L'insieme delle parti di un insieme, ordinato per inclusione. Elementi confrontabili e non confrontabili. Ordinamenti totali. La relazione di divisibilità in un semigruppo o in un monoide commutativi. Questa relazione può non essere antisimmetrica: elementi associati. Casi notevoli in cui la relazione di divisibilità è un ordinamento (largo): numeri naturali, interi positivi.

Ordinamento indotto su una parte di un insieme ordinato. Ordinamento duale (cioè relazione inversa di una relazione d'ordine; anch'essa è una relazione d'ordine). Principio di dualità. Nozioni di minimo ed elemento minimale in un insieme ordinato e corrispondenti nozioni duali: massimo ed elemento massimale.

Esercizi assegnati:

1. Sia f  l'applicazione X ∈ ℘(Z) → X∩N ∈ ℘(N). Stabilire se f è un omomorfismo (di semigruppi?, di monoidi?) tra (℘(Z),∪) e (℘(N),∪), tra (℘(Z),∪) e (℘(N),∩), tra (℘(Z),∩) e (℘(N),∪), tra (℘(Z),∩) e (℘(N),∩).
2. Dimostrare che il sottogruppo H={f ∈ S₅ | 5^f = 5} è isomorfo a S₄. [Suggerimento: si consideri l'applicazione da S₄ ad H che ad ogni α ∈H associa la permutazione di {1,2,3,4,5} che manda 5 in 5 e ciascun altro n appartenente al dominio in n^α.]
3. Sia f:X→Y un'applicazione biettiva. Verificare che t∈T(X)→f^-1tf∈T(Y) è un isomorfismo di monoidi; dedurre che t∈Sym(X)→f^-1tf∈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.
4. Esercizi nr. 1 e nr. 2 da relazioni binarie, per quanto riguarda gli ordinamenti.
5. Siano definite in ℘(Z) le relazioni binarie α e β, ponendo, per ogni X,Y ∈ ℘(Z), X α Y ⇔ X∩N⊆Y ∩ N e X β Y ⇔ X∩N⊂Y ∩ N. Per ciascuna di queste due relazioni stabilire se si tratta o meno di un ordinamento (stretto o largo) e, nel caso, trovare gli eventuali elementi minimo, massimo, minimali, massimali.

Discussione degli esercizi proposti nella lezione precedente.

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.

Buon ordinamento di (N,≤); giustificazione del principio di induzione, nella prima forma. Seconda del principio di induzione; argomentazione per "controesempio minimo".

Ogni insieme ordinato finito e non vuoto ha elementi minimali ed elementi massimali.

Relazione di copertura associata ad un ordinamento. Diagrammi di Hasse di un insieme ordinato finito.

Nozione di isomorfismo tra insiemi ordinati. Esempio di un'applicazione crescente e biettiva che non è un isomorfismo tra insiemi ordinati.

Minoranti e maggioranti di parti di un insieme ordinato. Estremo inferiore ed estremo superiore. 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 (℘(S),⊆), per un insieme S;
• estremi inferiori e superiori in (N,|).

Partendo da quest'ulitimo esempio sono state date le definizioni di massimo comun divisore e di minimo comune multiplo tra elementi di un arbitario semigruppo commutativo.

Reticoli. Definizione ed esempi. Gli insiemi totalmente ordinati non vuoti sono reticoli. Il duale di ogni reticolo è un reticolo, si ha quindi un principio di dualità anche per reticoli. In ogni reticolo, ogni elemento minimale (risp. massimale) è minimo (risp. massimo).

Se A e B sono parti di un insieme ordinato S, entrambe dotate di estremo inferiore in S, allora i minoranti di A∪B (cioè di A e B) sono precisamente quelli di {inf A,inf B}, dunque A∪B ha estremo inferiore se e solo se lo ha {inf A,inf B} e, nel caso questi estremi inferiori esistano, essi coincidono. (Ovviamente vale l'enunciato duale per gli estremi superiori). Di conseguenza: in ogni reticolo tutte le parti finite non vuote hanno estremo inferiore ed estremo superiore. Nozione di reticolo completo (esempio: l'insieme delle parti di un insieme, ordinato per inclusione).

Reticoli come strutture algebriche: operazioni reticolari.

Esercizi assegnati:

1. Per quali insiemi S l'insieme ℘(S) è totalmente ordinato per inclusione?
2. Disegnare i diagrammi di Hasse per gli insiemi Div(n) dei numeri naturali divisori di n, ordinati per divisibilità (in N), per n nell'insieme {9,18,19,20,30,49}. Quali tra questi sono reticoli? Quali isomorfi tra loro?
3. Esercizi nr. 5 e 6 da relazioni binarie, escluse le domande su reticoli distributivi, complementati, booleani, algebre di Boole.
4. Si disegni il diagramma di Hasse dell'insieme {-15,1,2,60,80,120,1000} ordinato per divisibilità (in Z); si tratta di un reticolo? In esso, se esistono, si trovino inf{60,120,1000} e sup{-15,1000}.
5. Per un insieme S ed una sua parte propria T si decida quali tra questi insiemi, ordinati per inclusione, sono reticoli: ℘(T), ℘(S)-℘(T) e, se S è infinito, ℘_f(S) (insieme delle parti finite di S), ℘_inf(S) (=℘(S)-℘_f(S)), ℘_cof(S) (={X∈℘(S) |  S-X è finita}, insieme delle parti cofinite di S), ℘_f(S)∪℘_cof(S).

Discussione degli esercizi proposti nella lezione precedente (ma l'esercizio nr. 5 va ancora discusso).

Richiamo: operazioni reticolari; equivalenza tra lo studio dei reticoli come strutture ordinate e come strutture algebriche. Esempio: per un insieme S, il reticolo (℘(S),⊆) e (℘(S),∩,&cup).

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.

Reticoli limitati (cioè con minimo e massimo); i reticoli finiti sono limitati (ma non vale il viceversa). 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. Proprietà delle algebre di Boole: l'operazione di complemento è involutoria (il complemento del complemento di ogni elemento x è x stesso), leggi di De Morgan. Il booleano di un insieme. Sottoalgebre di Boole. Enunciato del teorema di Stone (nel caso finito e, poi, nel caso generale). Come conseguenza: le algebre di Boole finite hanno per cardinalità una potenza di 2; due algebre di Boole finite equipotenti sono necessariamente isomorfe. Esempio di un'algebra di Boole (infinita) che non è isomorfa al booleano di alcun insieme.

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

Anelli, definizione ed esempi. Anelli commutativi, anelli unitari, l'anello degli interi. Esempi di anelli non unitari e non commutativi; l'anello (non commutativo) M₂(R) delle matrici 2×2 su un anello R.

Esercizi assegnati:

1. Completare la dimostrazione del fatto che, rispetto all'ordinamento definito da una coppia di operazioni reticolari, una delle due operazioni definisce l'estremo superiore tra due elementi (l'affermazione duale è stata verificata a lezione).
2. Verificare per via diretta che ogni catena è un reticolo distributivo.
3. Completare gli esercizi nr. 5 e 6 da relazioni binarie, rispondendo alle domande su reticoli distributivi, complementati, booleani, algebre di Boole.
4. Esercizio nr. 8 da relazioni binarie.
5. Estendere l'esercizio nr. 5 dalla lezione precedente, decidendo quali delle parti indicate sono sottoreticoli e quali sottoalgebre di Boole di ℘(S)
6. Provare che, per ogni insieme S, (℘(S),Δ,∩) è un anello (commutativo?, unitario?).
7. Esercizio nr. 5 da polinomi e strutture algebriche.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Anelli unitari e loro sottoanelli unitari. Un esempio di sottoanello di un anello unitaro che non è un sottoanello unitario pur essendo, per proprio conto, un anello unitario. Operazione opposta e dualità destra-sinistra per semigruppi, monoidi, gruppi, anelli.

Alcune regole di calcolo per anelli: per ogni x, y, z in un anello R si ha 0_Rx=x0_R=0_R;  (−x)y=x(−y)=−(xy);  (x−y)z=xz−yz e dualmente z(x−y)=zx−zy (si ricordi che x−y è definito come x+(−y)).

In ogni monoide (S,·), per ogni elemento x l'insieme {y∈S | xy=yx} degli elementi che commutano con x è una parte stabile. Inoltre, se S è un monoide, per ogni y∈U(S) si ha che y commuta con x se e solo se il simmetrico di y commuta con x.

Potenze (o, in notazione additiva, multipli) di un elemento secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari per elementi simmetrizzabili di un monoide). Regole di calcolo, tra le quali: per ogni n,m∈Z e per ogni x per cui queste potenze siano definite, x^n+m=xⁿx^m e x^nm=(xⁿ)^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 (n1_R)x=nx per ogni n∈Z.

Parte stabile generata e di sottostruttura generata da una parte di una assegnata struttura. Descrizione della parte stabile (cioè sottosemigruppo), del sottomonoide e del sottogruppo generate da un elemento (ovvero da un singleton) nelle opportune strutture.

Esercizi assegnati:

1. Determinare, in S₃, il sottogruppo generato da {(1 2), (1 2 3)}.
2. Determinare i sottosemigruppi, sottomonoidi e sottogruppi generati in (Q^#,·) da {1}, da {−1}, da {2}.
3. Determinare le quattro sottoalgebre di Boole generate: da ℘_f(N) in ℘(N); da {{1}}, da {{1},{2}} e da {{1},{1,3}} in ℘({1,2,3}).

Discussione degli esercizi proposti nella lezione precedente.

Gruppi ciclici: sono abeliani. Esempi: il gruppo additivo degli interi è ciclico, generato da 1; sono ciclici i gruppi identici e S₂; non è ciclico S₃.

Lo zero di un anello (unitario) non può essere invertibile; definizione di corpo e di campi (attenzione alla non corrispondenza con la terminologia che usa Facchini. Un corpo è un anello unitario in cui ogni elemento diverso da zero è invertibile; un campo è un corpo commutativo). Esempi.

Altre regole di calcolo in anelli: formula del binomio di Newton (per elementi permutabili in un anello; vedi coefficienti binomiali).

Anelli booleani. Esempi. Proprietà: sono commutativi ed hanno caratteristica 2 (per il momento la definizione di caratteristica è stata appena accennata). Equivalenza tra le nozioni di anello booleano e di reticolo booleano (costruzione di un reticolo booleano a partire da un anello booleano e costruzione inversa; quest'ultima è stata accennata senza procedere alla dimostrazione, che si lascia come esercizio). Sottoanelli unitari degli anelli boleani ed enunciato del teorema di Stone per anelli booleani. Isomorfismi di anelli (booleani) e di reticoli (booleani).

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, idempotenza, distributività); quozienti di semigruppi, monoidi, gruppi, anelli etc.

Esempi, tra cui il monoide delle parole su un alfabeto e la congruenza definita in esso dichiando equivalenti due parole se e solo se hanno la stessa lunghezza (vedi gli esercizi assegnati).

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,+,⋅). È stato solo enunciato che queste sono le sole congruenze di (Z,+). Nel corso di queste dimostrazioni è stato anche osservato che in ogni anello commutativo R un elemento che divida due elementi ne divide tutte le combinazioni lineari a coefficienti in R. Gli anelli quoziente Z_m.

Esercizi assegnati:

1. Provare che se a e b sono elementi di un anello si ha (a+b)²=a²+2ab+b² se e solo se ab=ba.
2. Verificare la correttezza della costruzione indicata a lezione di un anello booleano a partire da un reticolo booleano.
3. Verificare che l'equivalenza τ definita in Z ponendo, per ogni a,b∈Z, aτb⇔(a=b=0∨ab>0) è compatibile con la moltiplicazione in Z. Descrivere esplicitamente la relativa operazione quoziente.
4. Provare che se f è un omomorfismo di dominio una struttura S, allora il nucleo di equivalenza di f è una congruenza in S.
5. Provare che se M è il monoide delle parole su un alfabeto e λ è la congruenza definita a lezione (due parole sono in relazione modulo λ se e solo se hanno la stessa lunghezza) allora M/λ è isomorfo al monoide (N,+,0). Usare l'applicazione M→N che ad ogni parola associa la sua lunghezza; mostrare che è un omomorfismo.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

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

Per ogni a,m ∈ Z, se m≠0 esiste uno ed un solo r ∈ N tale che a ≡_m r e r < |m|. Si pone: a mod m := r.

Divisione (aritmetica) con resto in Z: (∀a ∈ Z)(∀b∈Z−{0}) (∃!(q,r)∈Z×N)(a=bq+r ∧ r<|b|).

Le congruenze ≡_m riguardate come nuclei di equivalenza di funzioni resto: due interi sono congrui modulo un intero positivo m se e solo se hanno lo stesso resto nella divisione per m. Per ogni a ed m in Z, la classe di resto di a modulo m è a+mZ. Descrizione dettagliata degli elementi dei quozienti Z_m (per ogni m∈N^#, Z_m ha esattamente m elementi: le classi di resto [0]_m, [1]_m, …, [m−1]_m).

Un esempio importante: l'anello Z₂ (è un campo ed è booleano). Anelli booleani definiti su "stringhe di zeri ed uno" di assegnata lunghezza n (ovvero n-ple di elementi di Z₂). 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}.

Esempi di calcoli in aritmetica modulare (calcolo di potenze, somme, prodotti).

Rappresentazione degli interi positivi in base 10 e criteri di divisibilità per 2, 5, 4, 25, 8, etc., 3, 9, 11, in N; ‘prova del nove’. Osservazione: se due interi sono congrui modulo un intero m, essi sono congrui modulo ogni divisore di m.

Periodo di un elemento in un gruppo. Elementi periodici ed aperiodici. Esempi. L'elemento neutro di un gruppo è l'unico elemento di periodo 1. Se un elemento x di un gruppo ha periodo finito t, allora, per ogni intero n, si ha xⁿ=1 se e solo se t divide n; più in generale, se a,b∈Z, x^a=x^b se e solo se a e b sono congrui modulo t.

Utilizzo di queste osservazioni per i calcoli di potenze in aritmetica modulare

Esercizi assegnati:

1. Elencare tutti gli interi compresi tra −20 e 25 che siano congrui a 5 modulo 8.
2. Si calcoli: 30 mod 7,  (-30) mod 7;  30 mod (-7).
3. Si calcolino i periodi di [3]₇ e [24]₇ in U(Z₇) e di [13]₁₅ in U(Z₁₅) (osservare che 13 ≡₁₃ −2). Posto k=123456789, si calcolino 13^k mod 15, 3^k mod 7, 24^k mod 7, 3^k + 24^k mod 7, k^k mod 9, k^k mod 5 e k^k mod 3.
4. Esercizi nr. 1 e 2 da un compito del 23 settembre 2005.
5. Esercizio nr. 12 da Tautologie, insiemi, aritmetica.

Discussione degli esercizi proposti nella lezione precedente.

Caratteristica di un anello unitario; il caso dei quozienti di Z.

Completamento di quanto nelle note sulla cancellabilità: elementi cancellabili e divisori dello zero negli anelli; anelli integri e domini di integrità; legge di annullamento del prodotto. Esempi. I campi sono domini di integrità; i domini di integrità finiti sono campi. Menzione del teorema di Wedderburn (i corpi finiti sono campi).

Fattorizzazione in monoidi commutativi. Richiami sulla relazione "essere elementi associati" in un monoide commutativo (osservazione importante: si tratta di una relazione di equivalenza) e caratterizzazioni: fissato un monoide commutativo (M,⋅), se a,b ∈ M, allora a e b sono associati se e solo se hanno gli stessi divisori, ovvero se e solo se hanno gli stessi multipli. Inoltre, se a è cancellabile, a e b sono associati se e solo se b = au per un opportuno u∈U(M). Monodi regolari. Se M è (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. 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; da completare (la dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo, diversa da quella nel libro di testo).

Esercizi assegnati:

1. Trovare gli elementi cancellabili dell'anello booleano ℘(N).
2. Provare che in ogni monoide commutativo la relazione “essere elementi associati” è una congruenza.
3. Sia S il sottomonoide (commutativo, regolare) di (N,⋅,1) costituito da 1 e dagli interi positivi pari. Verificare che, in S,
   • l'unico invertibile è 1;
   • gli elementi irriducibili sono tutti e soli gli interi positivi della forma 2d, dove d è un intero dispari (o, in altri termini: tutti e soli gli interi positivi congrui a 2 modulo 4);
   • ogni elemento diverso da 1 è prodotto di irriducibili;
   • 36 ha due fattorizzazioni in irriducibili: 36=2·18=6·6 e queste sono "essenzialmente diverse";
   • non esistono primi. (Suggerimento: se d e t sono interi positivi dispari distinti e t>1, allora 2d divide (2dt)(2t) in S, ma …)
   Dunque, S non è fattoriale.
4. Esiste un intero positivo n tale che 25⁶⁷⁶⁶ⁿ17²ⁿ⁺³ sia multiplo di 13?
5. Esercizi nr. 5–8 da Tautologie, insiemi, aritmetica.

In ogni semigruppo commutativo i massimi comuni divisori di una parte assegnata costituiscono una classe di elementi associati; simile enunciato vale per i minimi comuni multipli.

Completamento del Teorema di Bézout ed equazioni diofantee (di primo grado, a due indeterminate). Criterio di esistenza di soluzioni.

Equazioni congruenziali (di primo grado). Equivalenza tra il problema di risolvere una equazione diofantea e quello di risolvere un'equazione congruenziale (dei tipi considerati). Criterio di esistenza di soluzioni per le equazioni congruenziali.

Elementi invertibili nei quozienti di Z. Se m∈N^#, l'anello Z_m è un campo se e solo se m è primo (ciò equivale anche all'essere Z_m integro).

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 è gⁿ⁻¹).

Determinazione dell'insieme di tutte le soluzioni di un'equazione diofantea (del tipo considerato).

Altre due conseguenze det Teorema di Bézout: caratterizzazione delle coppie di interi coprimi; Lemma di Euclide: se a,b,c sono interi, a divide bc ed è coprimo con b, allora a divide c. Esempi.

La funzione di Eulero. Numero degli invertibili in un quoziente di Z. Metodi di calcolo; esempi.

Laterali di un sottogruppo; i laterali destri di un fissato sottogruppo in un gruppo ne costituiscono una partizione (esempio: le classi di resto 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.

Esercizi assegnati:

1. Esercizi nr. 9–11 da Tautologie, insiemi, aritmetica. L'esercizio 9 e le parti (a) e (b) del numero 10 sono da svolgere senza usare l'algoritmo euclideo.
2. Esercizio nr. 8 da un compito del 17 febbraio 2006. Consultare i relativi commenti.
3. Esercizio nr. 5 da un compito del 17 marzo 2006.
4. Indicare gli elementi invertibili, quelli cancellabili, i divisori dello zero, e gli elementi idempotenti nell'anello Z_n, per n ∈ {10,11,12}. Degli elementi invertibili si determinino periodo ed inverso.
5. Calcolare φ(1000) e φ(13⁵·800·4). Calcolare poi 573⁴⁰¹ mod 1000 e 20⁴⁰¹ mod 1000. Fare attenzione!
6. Sia H un sottogruppo di un gruppo (G, · ) e sia ρ la relazione di equivalenza in G corrispondente alla partizione di G in laterali destri di H (cioè tale che G/ρ = {Hx | x ∈ G). Provare che ρ è compatibile a destra con l'operazione · di G.

Rapidamente discusso l'esercizio nr. 5 dall'ultima lezione. Nozione di elemento nilpotente in un anello.

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 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, termine noto, polinomi costanti, polinomi monici.

Grado della somma, della differenza e del prodotto tra due polinomi. Se il polinomio non nullo f ha coefficiente direttore cancellabile (in A), allora f stesso è cancellabile (in A[x]). Teorema: A[x] è un dominio di integrità se e solo se lo è A, in questo caso vale in A[x] la regola di addizione dei gradi e U(A[x])=U(A). Esempi che mostrano come queste due proprietà non valgano necessariamente se A non è integro.

Per ogni anello commutativo A, A[x] è infinito e non è un campo (x non è invertibile).

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

Il contenuto della lezione di oggi corrisponde all'incirca alla prima parte delle note sui polinomi presenti in questo sito. È importante avere con sé una copia delle stesse note in occasione della prossima lezione (che si terrà il 5 giugno).

Esercizi assegnati:

1. Esercizi nr. 1 e 2 da polinomi e strutture algebriche.
2. Trovare tutte le radici in Z₁₂ del polinomio 3x ∈ Z₁₂[x] e, in Z₈ del polinomio x² + 1 ∈ Z₈[x]. Osservare come da questi esempi segua che il né il Teorema di Ruffini generalizzato né la sua conseguenza sulla limitazione al numero di radici di un polinomio non nullo valgano per anelli non integri.

Completamento di quanto nelle note sui polinomi presenti in questo sito. In dettaglio:

Principio di identità dei polinomi (per polinomi su domini di integrità infiniti). Il principio non vale nel caso dei polinomi su campi finiti né su anelli booleani.

Per un campo K: caratterizzazione dei polinomi irriducibili in K[x] in termini di non decomponibilità in prodotto di polinomi di grado minore; relazione tra le proprietà di esser privo di radici e di essere irriducibile (le due proprietà sono equivalenti per polinomi di grado 2 e 3). Esempi di polinomi di grado maggiore di 3 riducibili in Q[x] ma privi di radici in Q.

Informazioni: hanno radici nel campo complesso C tutti i polinomi non costanti in C[x], dunque i polinomi irriducibili in C[x] sono tutti e soli quelli di grado 1. Inoltre, ogni polinomio di grado dispari in R[x] ha radici nel campo reale R; i polinomi irriducibili in R[x] hanno grado al più 2.

Alcuni metodi di fattorizzazione per polinomi. Ogni polinomio in Q[x] è associato ad un polinomio a coefficienti interi. 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.

Richiami sulle permutazioni e sul gruppo simmetrico su un insieme; i gruppi S_n.

Cicli, trasposizioni. Periodo di un ciclo. Decomposizione di un ciclo di lunghezza k nel prodotto di k−1 trasposizioni. Supporto di una permutazione, permutazioni disgiunte. Permutazioni disgiunte commutano (ma non vale il viceversa).

Esercizi assegnati:

1. Determinare tutti i polinomi monici irriducibili in Z₃[x] di grado minore di 5.
2. In Q[x], quali tra x⁴−3x³+3x−6,   x⁴−3x³+3x−1  e  x⁸+12x⁵+8x²−2x+30 sono irriducibili?
3. Esercizi nr. 8 nr. 9 da un compito del 17 marzo 2006.
4. Esercizio nr. 10 da un compito del 13 febbraio 2008.
5. Esercizio nr. 8 da un compito del 27 gennaio 2006.
6. Esercizio nr. 11 da un compito del 5 settembre 2007.
7. Esercizio nr. 9 da un compito del 12 marzo 2008.
8. Esercizio nr. 10 da un compito del 17 dicembre 2007.

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 (per quanto riguarda gli esercizi sui grafi tralasciare, per il momento, le domande relative a nozioni non ancora introdotte, cioè alberi, foreste, circuiti e cammini euleriani):

1. Calcolare il periodo,il quadrato, il cubo, l'inverso e la parità di α := (4 9)(1 3 2)(2 6 3 4)(1 5)(1 2 4 5)(1 5 6 7)(4 8). Calcolare α¹⁰⁰.
2. Elencare, a meno di isomorfismi, tutti i grafi connessi con (esattamente) cinque vertici.
3. Esercizi 1, 2 e 5 da Grafi
4. Esercizio nr. 3 da un compito del 17 marzo 2006.
5. Esercizio nr. 5 da un compito del 16 marzo 2007.
6. Esercizio nr. 5 da un compito del 12 marzo 2008.

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:

1. Esercizio nr. 3 da Grafi.
2. Elencare, a meno di isomorfismi, tutti gli alberi con non più di cinque vertici.
3. Esercizio nr. 4 da un compito del 13 ottobre 2006.
4. Esercizio nr. 5 da un compito del 18 maggio 2007.