Corso di Algebra - Corso di recupero, a.a. 2013/14
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, disgiunzione esclusiva (XOR), 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. Diversi esempi di tautologie: principî del terzo escluso e di non contraddizione, commutatività di congiunzione, disgiunzioni, bicondizionale, associatività della congiunzione, implicazione come disgiunzione ed altri.

Per il contenuto di questa lezione e delle prossime, si vedano Logica rudimentale, tavola dei connettivi binari, esempi di tautologie

Esercizi proposti:

1. Verificare l'associatività del connettivo di disgiunzione (inclusiva).
2. Partendo dall'ultimo esempio visto a lezione, (la tavola di verità per la forma proposizionale $(p\Rightarrow q)\land(q\Rightarrow r)$), si provi che la forma $\bigl((p\Rightarrow q)\land(q\Rightarrow r)\bigr)\Rightarrow(p\Rightarrow r)$ è una tautologia.
3. La forma proposizionale $(p\land \lnot p)\Longrightarrow \bigl((p\lor q)\land (r\Rightarrow (s\lor p))\bigr)$ è una tautologia?

Discussione degli esercizi proposti nella lezione precedente, con approfondimenti. Metodi alternativi di calcolo di valori di verità.

Altre tautologie, tra cui: distributività tra congiunzione e disgiunzione, tautologie sulla negazione (leggi di De Morgan, negazione dell'implicazione), legge di contrapposizione, XOR come negazione del bicondizionale, associatività del bicondizionale e della disgiunzione esclusiva (XOR), XOR come negazione del bicondizionale, distributività della congiunzione rispetto a XOR; esplicitazioni di XOR.

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

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

Esercizi proposti: Sono consigliati tutti gli esercizi da Logica rudimentale, in particolare: B.3, B.4, B.5; C.1, C.2; tutti i D; E da 1 a 6; F.1, F.3.

Discussione di alcuni degli esercizi proposti nella lezione precedente, con approfondimenti.

Ulteriori osservazioni sulle sostituzioni e sulle occorrenze libere o vincolate di variabili (queste ultime ‘non vengono sostituite’. Formule valide. Predicati.

Descrizione del quantificatore $\exists!$ tramite equivalenze come $(\exists!x(\varphi(x)))\iff(\exists x\forall y(\varphi(x)\iff x=y))$.

Alcune regole della logica dei predicati. Frasi contenenti più quantificatori; esempi di frasi delle forme $\forall x\exists y(\dots)$ o $\forall x\exists y(\dots)$. Negazione di formule universali e di formule esistenziali. Quantificatori ristretti. Negazione di formule con quantificatori ristretti. Formule con quantificatori ristretti ad una condizione impossibile (come $(\forall x\in\varnothing)(\dots)$ o $(\exists x\in\vuoto)(\dots)$.

Discussione di alcuni (frequenti) errori di ragionamento.

Esercizi proposti:

1. Scrivere, in analogia a quanto fatto per $\exists!$, una formula che che permetta di definire il quantificatore $\exists_2$ (“esistono esattamente due”): per ogni formula $\varphi$ in cui non appare la variabile $x$, $(\exists_2 x(\varphi))\iff \dots$.
2. Esercizi e osservazioni G e H da Logica rudimentale.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Nozione (solo informale) di insieme. Il simbolo '$\in$' di appartenenza. Cenni a problemi fondazionali. Assioma di estensionalità e sue applicazioni. L'insieme vuoto $\vuoto$ (sua unicità).

Inclusione tra insiemi. È importante distinguere bene tra appartenenza e inclusione. Per ogni $x$ si ha $x\subseteq x$ ma $x\notin x$. Il singleton di un insieme; $\forall x(x\ne\set{x})$.

Sottoinsiemi (o parti) di un insieme. L'insieme $\P(S)$ delle parti di un insieme $S$. Qualunque sia $S$, si ha $\vuoto,\, S\in\P(S)$.

Estensione di un predicato unario. Antinomia di Russell. Assioma di separazione. “L'insieme di tutti gli insiemi” non esiste.

Comparazione tra l'equivalenza logica tra predicati (da una parte) ed uguaglianza tra insiemi (dall'altra). Corrispondenza informale tra connettivi proposizionali e relazioni o operazioni insiemistiche. Implicazione ed inclusione, congiunzione e intersezione, disgiunzione ed unione, disgiunzione esclusiva e differenza simmetrica. Alcune formule insiemistiche ottenute da tautologie: regola della doppia inclusione, leggi di idempotenza per unione e intersezione (binarie), commutatività, associatività e distributività per queste e per la differenza simmetrica.

Esercizi proposti:

1. Elencare gli elementi di $\P(\set{\vuoto, \set{\vuoto}, a})$, assumendo $a\notin\set{\vuoto, \set{\vuoto}}$.
2. Descrivere esplicitamente gli insiemi $\set{x\mid x=\vuoto}$, $\set{x\mid \forall y (x\subseteq y)}$, $\set{x\mid \forall y (x\in y)}$, $\set{x\mid \forall y (x=y)}$.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Complemento (o differenza) tra insiemi. Completamento di quanto in tautologie e identità insiemistiche ed in Formule insiemistiche da Logica rudimentale: interpretazione del connettivo di negazione nell'ambiente di un prefissato insieme S come complemento in S.

Diagrammi di Euler-Venn; qualche esempio. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare formule insiemistiche. Uso dei diagrammi di Euler-Venn per costruire controesempi.

Diagrammi di Venn e cardinalità (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.

Descrizione di insiemi con scritture del tipo $\set{t(x_1,x_2,\ldots,x_n)\mid \varphi(x_1,x_2,\ldots,x_n)}$ (abbreviazione di $\set{a\mid \exists x_1,x_2,\ldots,x_n (a=t(x_1,x_2,\ldots,x_n)\land \varphi(x_1,x_2,\ldots,x_n))}$.

Coppie ordinate (solo un cenno alla definizione di Kuratowski, vedi esercizi). Prodotto cartesiano tra due insiemi. Corrispondenze tra due insiemi.

Esercizi proposti:

1. Rappresentare su diagrammi di Venn (per insiemi $A,B,C$) gli insiemi:
   1. $(A\cap B)\cap C$;
   2. $(A\cup B)\cap C$, ovvero $(A\cap C)\cup(B\cap C)$;
   3. $(A\ds B)\cap C$, ovvero $(A\cap C)\ds (B\cap C)$;
   4. $(A\cap B)\setminus C$ e $(A\setminus C)\cap(B\setminus C)$;
   5. $(A\cup B)\setminus C$ e $(A\setminus C)\cup(B\setminus C)$;
   Trarre qualche conclusione dal confronto delle ultime due coppie di diagrammi.
2. È vero che: $\forall a,b (a\subseteq b \iff \P(a)\subseteq P(b))$?
3. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=8$ e $|B|=10$. Sapendo che $3\le |A\cap B|<6$, cosa possiamo dire su $|A\cup B|$?
4. Provare che, per ogni $a,b,c,d$, si ha: $\set{\set{a},\set{a,b}}=\set{\set{c},\set{c,d}}$ se e solo se $a=c$ e $b=d$. (Si può usare questa osservazione per dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. Questa è la cosiddetta definizione di Kuratowski della nozione di coppia ordinata).
5. Elencare gli elementi di $S\times T$, dove $S=\set{1,2,3}$, $T=\set{a, b}$ e $|T|=2$.
6. Siano $A$ e $B$ due insiemi. Si ha $A\times B=B\times A$ se e solo se …?

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Ancora sulle corrispondenze. Relazioni binarie. Rappresentazioni di corrispondenze mediante diagrammi o tabelle. Prodotto relazionale tra corrispondenze; sua associatività. Corrispondenza inversa di una corrispondenza.

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\in\N$, l'insieme $\P_n(S)$ delle $n$-parti di $S$.

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.

Composizione (prodotto operativo) di applicazioni. Applicazione identica di un insieme e sua proprietà di neutralità (vedi esercizi).

Immagine di un'applicazione. Applicazioni suriettive.

Esercizi proposti:

1. Siano $\N$ l'insieme dei numeri naturali e $S=\set{1,2,3}$. Siano poi $\alpha$ la relazione binaria in $S$ di grafico $\set{(1,3), (3,1),(3,3)}$ e $\beta$ la corrispondenza da $S$ ad $\N$ di grafico $\set{2}\times\set{x\in\N\mid x<10}$. Descrivere la corrispondenza prodotto $\alpha\beta$ e la relazione binaria $\alpha^2=\alpha\alpha$.
2. (Neutralità delle applicazioni identiche) Sia $\alpha$ una corrispondenza da un insieme $A$ ad un insieme $B$. Provare che $\alpha=\id_A\alpha=\alpha\id_B$, dove $\id_A$ e $\id_B$ rappresentano, come usuale, le applicazioni identiche di $A$ e di $B$.
3. La corrispondenza: $n\in\Z\mapsto n^2/2\in\Z$ è un'applicazione ben definita?
4. Indicato con $\R^+_0$ l'insieme dei numeri reali non negativi (cioè $\R^+_0=\set{a\in\R\mid a\ge 0}$, si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • $\alpha\colon \R\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\beta\colon \R^+_0\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\gamma\colon \R^+_0\to \R^+_0$, di grafico $\set{(a,b)\in\R\times\R^+_0\mid a=b^2}$;
5. Date la applicazioni $f\colon X\in\P(\N)\mapsto X\cup \set 1 \in\P(\N)$ e $g\colon X\in\P(\N)\mapsto X\setminus \set 1 \in\P(\N)$, descrivere le applicazioni composte $f\circ g$ e $g\circ f$. Di ciascuna delle due, si stabilisca se è suriettiva.

Discussione di alcuni degli esercizi proposti nella lezione precedente, con un'osservazione aggiuntiva sulla non commuttività del prodotto operativo tra applicazioni.

Famiglie; successioni.

Unione ed intersezioni unarie; unioni ed intersezioni per famiglie, estensioni delle leggi distributive e di De Morgan.

Restrizioni, prolungamenti, ridotte di un'applicazione. L'immersione in un insieme di una sua parte (se $Y$ è una parte di un insieme $X$, l'immersione di $Y$ in $X$, spesso indicata con $Y\hookrightarrow X$, è l'applicazione $y\in Y\mapsto y\in X$, cioè la restrizione ad $Y$ di $\id_X$). Restrizioni di un'applicazione $f$ come composte tra un'immersione ed $f$.

Applicazioni iniettive; negazione della iniettività. Esempi. Applicazioni biettive. Ogni applicazione ha una ridotta suriettiva; restrizioni e ridotte di applicazioni iniettive sono iniettive.

La composta di due applicazioni suriettive (risp. iniettive, biettive) è necessariamente suriettiva (risp. iniettiva, biettiva). Parziale inversione di questo risultato: se la composta $g\circ f$ di due applicazioni è suriettiva allora quella che agisce per seconda (cioè $g$) è suriettiva; se invece $g\circ f$ è iniettiva allora $f$ è iniettiva. Un esempio si applicazione biettiva che si possa scrivere come applicazione composta $g\circ f$, dove $g$ non è iniettiva ed $f$ non è suriettiva.

Esercizi proposti:

1. Sia $F$ l'insieme delle parti finite di $\N$. Calcolare $\bigcup F$ e $\bigcap F$.
2. Vero o falso?
   1. Ogni applicazione il cui dominio abbia meno di due elementi è iniettiva.
   2. Ogni applicazione ha una restrizione iniettiva.
   3. I prolungamenti delle applicazioni suriettive sono suriettivi.
   4. Ogni applicazione ha un prolungamento suriettivo.
3. Esercizio nr. 3 da Tautologie, Insiemi, Aritmetica, escluso il punto f. Al punto d, con $2\N$ si intende 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\circ f$.

Discussione di alcuni degli esercizi proposti nella lezione precedente, con osservazioni aggiuntive.

Un altro modo per rappresentare le applicazioni: tramite matrici a due righe; esempi.

Sezioni di un'applicazione suriettiva e retrazioni di un'applicazione iniettiva (data un'applicazione $f\colon A\to B$, si ha che $f$ è suriettiva se e solo se esiste un'applicazione $g\colon B\to A$ (una sezione di $f$) tale che $f\circ g=\id_B$; invece $f$ è iniettiva se e solo se $A=\vuoto$ oppure esiste un'applicazione $g\colon B\to A$ (una retrazione di $f$) tale che $g\circ f=\id_A$). Tutte le sezioni sono iniettive, tutte le retrazioni sono suriettive.

Applicazione inversa di un'applicazione. Le applicazioni invertibili (cioè quelle per le quali esista un'inversa) sono precisamente quelle biettive. Questo fatto è stato verificato sia utilizzando i risultati su sezioni e retrazioni si direttamente. Unicità dell'inversa di un'applicazione biettiva (un'applicazione biettiva ha una unica inversa, che è anche la sua unica sezione e la sua unica retrazione).

Importanza della nozione di invertibilità.

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti (notazione: $n^{\underline m}=n(n-1)(n-2)\cdots(n-m+1)$).

Criterio di esistenza di applicazioni iniettive/suriettive/biettive tra assegnati insiemi finiti: se $A$ e $B$ sono insiemi finiti, allora esistono applicazioni iniettive da $A$ a $B$ se e solo se $|A|\le |B|$; esistono applicazioni suriettive da $A$ ad $B$ se e solo se $|A|\ge |B|$ e $B=\vuoto\implica A=\vuoto$; esistono applicazioni biettive da $A$ ad $B$ se e solo se $|A|=|B|$. Per un'applicazione $f$ tra due insiemi finiti con lo stesso numero di elementi sono equivalenti: $f$ è iniettiva, $f$ è suriettiva, $f$ è biettiva.

Quest'ultimo risultato non si estende al caso degli insiemi infiniti. Cenni al confronto tra cardinalità tra insiemi infiniti (cardinalità di $\N$, $\Z$, $\Q$, $\R$), menzione del teorema di Cantor: $\forall x (|\P(x)|>|x|)$.

Esercizi proposti:

1. Provare che, se $f$ e $g$ sono applicazioni biettive componibili, l'inversa di $f\circ g$ è $g^{-1}\circ f^{-1}$, dove $g^{-1}$ e $f^{-1}$ sono rispettivamente le inverse di $g$ e $f$.
2. Elencare tutte le sezioni dell'applicazione $f\colon X\to Y$, dove $X=\set{1,2,3,4}$, $Y=\set{a,b}$, con $a\ne b$ e, per ogni $n\in X$, $f(n)$ è $a$ se $n$ è pari, $b$ se $n$ è dispari.
3. Siano $A=\set{1,2,3}$ e $B=\set{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.
5. Siano $A=\set{1,2,3}$ e $B=\set{u,v,w}$, dove $|B|=3$. Quante sono le applicazioni biettive da $A$ a $B$? Elencarle tutte.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Il fattoriale $n!$ di un numero naturale $n$. L'insieme $\Sym(S)$ delle permutazioni di un insieme $S$; se $S$ è finito, $|\Sym(S)|=|S|!$.

Applicazione immagine $\vec f\colon\P(A)\to\P(B)$ ed applicazione antiimmagine $\antivecf\colon\P(B)\to\P(A)$ definite da un'applicazione $f\colon A\to B$. Con queste notazioni si ha $\vec f(\vuoto)=\antivecf(\vuoto)=\vuoto$, $\,\vec f(A)=\im f$, $\,\antivecf (B)=A$, $\,\antivecf (\im f)=A$. Non è generalmente, vero che $\vec f$ e $\antivecf$ siano l'una applicazione inversa dell'altra. È possibile aversi $\vec f (U)\cap \vec f(V)\subset \vec f(U\cap V)$ per parti $U$ e $V$ del dominio di $f$. Esempi e controesempi.

Richiamo del principio di induzione. Cardinalità dell'insieme delle parti di un insieme finito: per ogni insieme finito $S$ si ha $|\P(S)|=2^{|S|}$. Di questo risultato abbiamo fornito due dimostrazioni, una per induzione su $|S|$, una utilizzando l'importante nozione di funzione caratteristica di una parte di $S$ e la biezione da $\P(S)$ all'insieme delle applicazioni da $\set{0,1}$ a $S$ che a ogni parte di $S$ associa la sua funzione caratteristica.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, 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. Un'osservazione su come semplificare la verifica della transitività di una relazione binaria.

Esercizi proposti:

1. Sia $v$ l'applicazione valore assoluto in $\Z$, cioè $v\colon n\in\Z\mapsto |n|\in\Z$. Posto $A=\set{n\in\Z\mid -10 < n < 20}$, si calcolino $\vec v(A)$, $\antivecv(A)$, $\vec v(\antivecv(A))$, $\antivecv(\vec v (A))$.
2. Provare che, se $f$ è l'applicazione identica in un insieme $A$, $\vec f$ e $\antivecf$ coincidono con l'applicazione identica di $\P(A)$.
3. Provare che, se $f$ e $g$ sono applicazioni componibili, $(f\circ g)\vecvuoto=\vec f\circ \vec g$  e  $(f\circ g)\antivecvuoto=\antivecg\circ \antivecf$. Se $f$ è biettiva, allora anche $\vec f$ è biettiva e la sue inversa è $\antivecf$, che coincide con $(f^{-1})\vecvuoto$.
4. Sia $f\colon A\to B$ un'applicazione. Provare che,
   • $\vec f$ è iniettiva se e solo se $f$ è iniettiva; $\vec f$ è suriettiva se e solo se $f$ è suriettiva (suggerimento: si possono usare gli esercizi precedenti e le caratterizzazioni di iniettività e suriettività in termini di esistenza di retrazioni e sezioni).
   • Se $U\subseteq V\subseteq A$ allora $\vec f(U)\subseteq \vec f(V)$; se $U\subseteq V\subseteq B$ allora $\antivecf(U)\subseteq \antivecf(V)$.
   • Per ogni $X\subseteq A$ si ha $X\subseteq \antivecf (\vec f(X))$; per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y\cap \im f$.
   • $f$ è iniettiva se e solo se per ogni $X\subseteq A$ si ha $X=\antivecf (\vec f(X))$; $f$ è suriettiva se e solo se per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y$.
5. Da relazioni binarie: esercizi nr. 1 (ad esclusione di 1.f e 1.g e tralasciando la domande su equivalenze e ordinamenti); nr. 2, punti c, d, e; nr. 3 limitatamente alle domande su $\tau$, $\sigma$ e $\psi$. (La parte restante di questi esercizi, come, in generale, di tutti quelli disponibili, potrà essere più utilmente affrontata in seguito e, comunque, in fase di preparazione dell'esame).

Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche ulteriore commento.

Relazioni di equivalenza in un insieme. Esempi, tra i quali le equivalenze banali (l'uguaglianza e la relazione universale) in un insieme. Nucleo di equivalenza di un' applicazione (anche detta equivalenza associata ad un'applicazione).

Classi di equivalenza ed insieme quoziente definito da una relazione di equivalenza. Proprietà fondamentali delle classi di equivalenza: fissata una relazione di equivalenza $\sim$ in un insieme $S$ per ogni $a,b\in S$ si ha:

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$;
• $a\sim b \iff b\sim a \iff a\in[b]_\sim\iff b \in [a]_\sim\iff [a]_\sim=[b]_\sim$;
• $(\forall C\in S\,/{\sim})(\forall x\in C)(C=[x]_\sim)$.

Proiezione canonica $a\in S\mapsto [a]_\sim\in S/{\sim}$. Ogni equivalenza è il nucleo di equivalenza di un'applicazione, ad esempio, della proiezione canonica che essa definisce.

Partizioni di un insieme. Definizione e prima caratterizzazione: $P$ è una partizione di un insieme $S$ se e solo se $P\subseteq \P(S)\setminus\set\vuoto$ e $(\forall x\in S)(\exists! b\in P)(x\in b)$.

Gli insiemi quoziente sono partizioni. Esempi: le partizioni banali, cioè i quozienti definiti dalle equivalenze banali in un insieme $S$; queste partizioni sono dunque $\set S$ e $\P_1(S)$. Altri esempi: tutte le partizioni degli insiemi $\set{1,2}$ e $\set{1,2,3}$.

Esercizi proposti:

1. Ripetere (eufemismo) l'esercizo 5 dalla lezione scorsa, comprese le domande sulle relazioni di equivalenza.
2. Sia $f\colon A\to B$ un'applicazione. Provare che $f$ è iniettiva se e solo se il nucleo di equivalenza di $f$ è la relazione di uguaglianza in $A$; provare che $f$ è costante se e solo se il nucleo di equivalenza di $f$ è la relazione di universale in $A$.
3. Siano $S=\set{1,2,3,4}$ e $A=\set{1,2}$; si consideri l'applicazione $f\colon x\in\P(S)\mapsto x\setminus A\in \P(S)$. $f$ è iniettiva? $f$ è suriettiva? Detto $\rho$ il nucleo di equivalenza di $f$, si descriva, innanzitutto, $[\vuoto]_\rho$ in modo esplicito (elencandone cioè gli elementi) e se ne calcoli la cardinalità. Si descrivano poi, sempre in modo esplicito, tutti gli elementi di $\P(S)/\rho$ e si calcoli $|\P(S)/\rho|$.
4. Esercizio 4 da relazioni binarie.
5. Sia $S$ un insieme infinito. È vero che $\set{\P_k(S)\mid k\in\N}$ è una partizione di $\P(S)$? O magari una partizione dell'insieme $\Pf(S)$ delle parti finite di $S$? E se $S$ è finito?
6. Si trovino sei partizioni (distinte) dell'insieme $\set{1,2,3,4}$.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Descrizione esplicita dell'insieme quoziente definito da un nucleo di equivalenza: se $\sim$ è il nucleo di equivalenza di un'applicazione $f$ di dominio $S$, per ogni $x\in S$ si ha $[x]_\sim=\antivecf(\set{f(x)})$. Di conseguenza, $S/{\sim}=\set{\antivecf(\set{y})\mid y\in \im f}$. L'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in S/{\sim}$ è biettiva, quindi si ha $|S/{\sim}|=|\im f|$ (questo risultato è noto come teorema di omomorfismo per insiemi— si può consultare Il Teorema di Omomorfismo per Insiemi, che è però scritto con notazioni e stile leggermente diversi da quelli usati negli ultimi anni a lezione: notazione esponenziale per le immagini degli elementio mediante un'applicazione; ordine naturale dei fattori per la composizione di applicazioni).

Avevamo visto che ogni insieme quoziente è una partizione; vale anche il viceversa: per ogni insieme $A$ si ha la biezione canonica da $\Eq(A)$ a $\Part(A)$ (insiemi delle relazioni di equivalenza e delle partizioni di $A$): questa è l'applicazione $\rho\in\Eq(A)\mapsto A/\rho\in\Part(A)$ ed è, appunto, biettiva. La sua inversa è l'applicazione che ad ogni partizione $P$ di $A$ associa il nucleo di equivalenza dell'applicazione da $A$ a $P$ che ad ogni $x\in A$ associa l'elemento di $P$ a cui $x$ appartiene (dunque: due elementi di $A$ risultano equivalenti se e solo se appartengono allo stesso blocco della partizione).

Alcuni esempi: elenco delle relazioni di equivalenza di $\set{1,2}$ o di $\set{1,2,3}$. Applicazione $X\in\P(S)\mapsto |X|\in\N$ per un insieme finito $S$. Il suo nucleo di equivalenza ed il corrispondente insieme quoziente: la partizione $\set{\P_k(S)\mid |S|\ge k\in\N}$ di $\P(S)$.

Coefficienti binomiali: buona definizione del coefficiente binomiale $\binom nk$, per ogni $k,n\in\N$, come cardinalità di $\P_k(S)$ ed ogni insieme $S$ di cardinalità $n$. Osservazioni sui casi, banali, in cui $k$ vale 0, 1 o $n$, o $k>n$. Per ogni $n\in\N$ si ha $\sum_{k=0}^n\binom nk=2^n$.

Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$. Per ogni $k,n\in \N$, formula ricorsiva: $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$ e, se $k\le n$, formula chiusa: $\binom nk=n!/(k!(n-k)!)=n^{\underline k}/k!$. Anche questi argomenti sono esposti in una nota, Coefficienti Binomiali, in cui però lo stile espositivo non coincide con quello usato a lezione. In particolare, la formula chiusa per i coefficienti binomiale è stata dimostrata in aula per induzione e non come nelle note.

Esercizi proposti:

1. Esercizio 1 dal compito del 16 luglio 2013.
2. Sia $S=\set{a,b,c}$ un insieme. Descrivere tutte le relazioni di equivalenza in $S$ e calcolarne il numero. (Attenzione: quanti elementi ha $S$?)
3. Sia $A=\set{1,2,3,4,5,6,7}$. Quante (e quali) sono le relazioni di equivalenza $\rho$ in $A$ tali che $1\mathrel\rho 3$, $\set{2,4,6}\subseteq [3]_\rho$ e $3\in[7]_\rho$?
4. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_6(S)$.
5. 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 $\P(S)$?
6. Posto $A=\set{1,2,3,\ldots,7}$, indicare la cardinalità di $\set{X\in\P(A)\mid (3\in X)\land(|X|=5)}$ e quella di $\set{X\in\P(A)\mid (4\notin X)\land(|X|=3)}$.
7. 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. Quale probabilità ha Anacleto di vincere?

Rapida discussione di alcuni degli esercizi proposti nella lezione precedente.

Il Triangolo di Tartaglia-Pascal.

Operazioni (binarie, interne, ovunque definite) in un insieme. Operazioni associative e operazioni commutative; esempi. Nozione di struttura algebrica. Diversi 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); operazioni indotte e sottostrutture. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà. Le intersezioni tra parti chiuse sono a loro volta chiuse. La parte chiusa generata da una parte in una struttura. Alcuni 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 nonché l'unico elemento neutro a sinistra). Esempi, tra cui quello di un semigruppo con più di un elemento neutro a destra.

Monoidi. Tra gli esempi: vari insiemi numerici con l'operazione di addizione o di moltiplicazione; per un arbitrario insieme $S$, sono monoidi $(\P(S),\cup,\vuoto)$ e $(\P(S),\cap,S)$, e poi il monoide $T(S)$ delle trasformazioni di $S$ (che è commutativo se e solo se $|S|\le 1$).

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

Esercizi proposti:

1. Esercizio nr. 4 da polinomi e strutture algebriche.
2. Verificare che l'operazione $(a,b)\in\R\times\R\mapsto |a-b|\in\R$ (distanza tra due punti della retta reale) è commutativa ma non associativa.
3. Sia $M$ l'insieme delle matrici $2\times 2$ di numeri reali, munito del prodotto $\cdot$ righe per colonne. $(M,\cdot)$ è un semigruppo? È un monoide? Questo prodotto è commutativo?
4. Delle seguenti dieci parti di $\Z$: $\N$, $\Z\setminus \N$, $\vuoto$, $\set{x\in\Z \mid x > 8}$, $\set{x\in\Z \mid x> -8}$, $\set 0$, $\set 1$, $\set {-1}$, $\set {0,1,2}$, $\set {1,-1}$, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
5. Si determini, in $(\P(\N),\cap)$, la parte chiusa generata da $\set{\set{1},\set{3,4}}$.

Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche ulteriore commento.

Nozione di operazione opposta e dualità destra/sinistra per operazioni binarie.

Simmetrici destri e sinistri; simmetrici. Unicità dei simmetrici nei monoidi: se, per un elemento $x$ di un assegnato monoide $S$, $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 $S$. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico". Ancora un richiamo al monoide $T(S)$ delle trasformazioni di un insieme $S$: i suoi elementi invertibili a destra o a sinistra sono le trasformazioni suriettive ed iniettive, rispettivamente.

Gruppi. Esempi, come $(\Z,+,0,-)$, $(\Q\setminus\set\vuoto,\cdot,1,{}^{-1})$, $(\P(S),\ds,\vuoto,\id_S)$ per un insieme $S$. Gruppi abeliani.

Il gruppo $\U(M)$ degli invertibili (cioè degli elementi simmetrizzabili) di un monoide $M$. Formula per il calcolo del simmetrico di un prodotto in un monoide (in notazione moltiplicativa, per ogni $a,b\in \U(M)$ si ha $(ab)^{-1}=b^{-1}a^{-1}$.

Alcuni esempi importanti: il gruppo moltiplicativo $\set{1,-1}$ degli invertibili del monoide $(\Z,\cdot)$; il gruppi simmetrico $\Sym(S)$ su un insieme $S$ (è il gruppo degli invertibili del monoide delle trasformazioni di $S$; i suoi elementi sono le permutazioni di $S$). Notazione: $\S_n:=\Sym(\set{1,2,3,\ldots,n})$, per ogni intero positivo $n$.

Cenni ad alcune proprietà delle permutazioni e dei gruppi simmetrici: cicli (permutazioni cicliche); trasposizioni (cicli di lunghezza 2). Permutazioni tra loro disgiunte; esse commutano tra loro. Ogni permutazione su un insieme finito $S$ è prodotto di cicli a due a due disgiunti, in modo unico, a meno dell'ordine dei fattori. Ogni ciclo è prodotto di trasposizioni, infatti ogni ciclo $(a_1\,a_2\,\dots\,a_k)$ si fattorizza come $(a_1\,a_k)\circ(a_1\,a_{k-1})\circ\cdots\circ(a_1\,a_3)\circ(a_1\,a_2)$. Di conseguenza, ogni permutazione di un insieme finito è prodotto di trasposizioni. Non è stata fornita dimostrazione di questi fatti.

Dato un insieme $S$, il gruppo $\Sym(S)$ è abeliano se e solo se $|S|\le 2$.

Esercizi proposti:

1. Si studino le strutture $(\Z,\oplus)$ e $(\Z,\odot)$ dove $\oplus$ e $\odot$ 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), quali elementi sono dotati di simmetrici. Di che tipo di strutture algebriche si tratta?
2. Sia determini il gruppo degli invertibili in ciascuno dei monoidi: $(\N,\cdot)$, $(\Q,+)$, $(\R,\cdot)$ e, per un assegnato insieme $S$, $(\P(S),\cap)$.
3. Si $S$ un insieme tale che $|S|>2$, e si fissi $a\in S$. Definiamo un'operazione binaria $*$ in $S$, ponendo, per ogni $x,y\in S$, $x*y=a$, se $a\notin \set{x,y}$, e $a*x=x=x*a$. L'operazione $*$ è commutativa? Verificare che $a$ è neutro in $(S,*)$ e che, per ogni $x\in S$, ogni elemento di $S\setminus\set a$ è simmetrico di $x$ rispetto a $*$.
   A questo punto, senza fare alcun calcolo rispondere alla domanda: $*$ è associativa?
4. Cosa cambierebbe nell'esercizio precedente se si assumesse $|S|=2$?
5. Provare che se $\alpha$ è una trasposizione di un insieme $X$, allora $\alpha\circ\alpha=\id_X$ e $\alpha$ coincide con la sua inversa. Provare anche che se $\beta$ è un ciclo di lunghezza 3 in $X$, allora $\beta\circ\beta\circ\beta=\id_X$. È vero che, in questo caso, l'inversa di $\beta$ è $\beta\circ\beta$?
6. [Vediamo se ci riuscite …] Sia $\sigma\in \S_9$ la permutazione descritta da $ \begin{pmatrix} 1&2&3&4&5&6&7&8&9\\ 4&9&8&6&3&1&7&5&2 \end{pmatrix}. $ Scrivere $\sigma$ come composta di cicli a due a due disgiunti e, fatto ciò, come composta di trasposizioni.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

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

Elementi cancellabili, a sinistra o a destra rispetto ad un'operazione binaria; elementi cancellabili. Traslazioni in una struttura algebrica. Rapporto tra simmetrizzabilità e cancellabilità in un monoide. Esempi. Equivalenza tra cancellabilità e simmetrizzabilità per semigruppi finiti (senza dimostrazione). Questi contenuti sono disponibili in una nota sulla cancellabilità. Visualizzazione della cancellabilità in una tavola di Cayley.

Isomorfismi tra strutture algebriche. Discussione generale ed alcuni esempi. Invarianza delle proprietà algebriche per isomorfismi: questi conservano la commutatività e associatività; inoltre l'immagine mediante un isomorfismo di un elemento che sia (a destra o a sinistra) neutro, simmetrizzabile, cancellabile ha la stessa proprietà. Tavole di Cayley e isomorfismi; esempio: i gruppi di cardinalità due sono tutti isomorfi tra loro, come si è visto dalle loro tavole di Cayley. Altri esempi di isomorfismi, tra cui la funzione esponenziale come isomorfismo dal gruppo additivo dei reali al gruppo moltiplicativo dei reali positivi. Un esempio importante: se $X$ e $Y$ sono insiemi equipotenti (cioè tali che $|X|=|Y|$) allora i corrispondenti gruppi simmetrici ed i corrisponenti monoidi delle trasformazioni sono isomorfi: $\Sym(X)\iso\Sym(Y)$ e $T(X)\iso T(Y)$.

Omomorfismi tra strutture algebriche; monomorfismi ed epimorfismi. 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.

Esercizi proposti:

1. Sia $S=\set{1,2}$. Scrivere le tavole di Cayley di $(\P(S),\cap)$ e di $(\P(S),\ds)$.
2. Sia $G$ un gruppo di cardinalità 3; siano $t$ (neutro), $a$ e $b$ i suoi elementi. Scrivere la tavola di Cayley di $G$ partendo dalla riga e dalla colonna intestate da $t$ (che sono note). Procedere utlizzando il fatto che sia le righe che le colonne sono prive di ripetizioni (è un po' come risolvere un sudoku).
   Concludere che i gruppi di cardinalità 3 sono tutti isomorfi tra loro e sono abeliani.
3. Determinare gli elementi cancellabili nel monoide $(\P(\Z),\cap)$.
4. Tra i monoidi $(\Z,\cdot)$, $(\Z, +)$, $(\N,+)$, $(\P(\N),\cap)$, $(\P(\N),\ds)$ ce ne sono due isomorfi tra loro?
5. Verificare in dettaglio che, se $f\colon S\to T$ è un isomorfismo da una struttura $(S,*)$ dotata di elemento neutro ad una struttura $(T,\diamond)$, se $x$ è un elemento simmetrizabile in $(S,*)$ allora $f(x)$ è un elemento simmetrizabile in $(T,\diamond)$, individuando il simmetrico di $f(x)$.
6. Per ogni insieme $S$, verificare che l'applicazione $X\in\P(S)\mapsto S\setminus X\in\P(S)$ è un isomorfismo da $(\P(S),\cap)$ a $(\P(S),\cup)$. (Questo spiega il fatto che le due strutture hanno le stesse proprietà algebriche.)
7. Verificare che se $f\colon (S,*)\to (T,\diamond)$ è un epimorfismo e $*$ è associativa (risp. commutativa), allora anche $\diamond$ ha la stessa proprietà.
8. Tornando al primo degli esercizi proposti la lezione scorsa, verificare che l'applicazione $n\in\Z\mapsto n-1\in\Z$ è un isomorfismo da $(\Z,+)$ a $(\Z,\oplus)$ e da $(\Z,\cdot)$ a $(\Z,\odot)$.
9. Sia $(G,\cdot)$ un gruppo con un solo elemento, $t$. Sia $S=\set{a,b}$ un insieme con due elementi e definiamo in $S$ l'operazione $*$ ponendo $b*a=b$ e $a*a=a*b=b*b=a$. Provare che l'applicazione definita da $t\mapsto a$, da $G$ a $S$ è un monomorfismo da $(G,\cdot)$ a $(S,*)$, benché $(G,\cdot)$ sia un gruppo abeliano mentre $*$ non è né associativa né commutativa e $(S,*)$ non abbia elemento neutro.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Sottogruppi e loro caratterizzazione. Qualche esempio.

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\in\Z$ per cui $x^n$ e $x^m$ siano definiti, $x^{n+m}=x^n x^m$ e $x^{nm}=(x^n)^m$ (è stata data solo dimostrazione parziale della prima di queste formule ). In notazione additiva queste formule diventano, con le stesse quantificazioni, $(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: siano $a$ e $b$ sono elementi di un monoide che commutano tra loro; se $a$ è invertibile, allora anche l'inverso di $a$ commuta con $b$.

Sottosemigruppi, sottomonoidi e sottogruppi generati da singleton. Gruppi ciclici. Esempio: i gruppi $\U(\Z,\cdot)$ e $(\Z,+)$ sono ciclici. I gruppi ciclici sono necessariamente abeliani; $\P(\set{1,2},\ds)$ è abeliano ma non ciclico. Periodo di un elemeno in un gruppo.

Relazioni d'ordine largo e relazioni d'ordine stretto. Esempi (ordinamento usuale tra numeri reali, relazione di inclusione tra insiemi). Ordinamento duale.

Ordine stretto $\rho_{\ne}$ definito da un ordine largo $\rho$ in un insieme $A$ (definito da: ($\forall x,y\in A)(x\mathrel {\rho_{\ne}}y\iff x\mathrel\rho y\, \land\, x\ne y$) e ordine largo $\underline\sigma$ definito da un ordine stretto $\sigma$ in $A$ (definito da: ($\forall x,y\in A)(x\mathrel {\underline\sigma}y\iff x\mathrel \sigma y \,\lor\, x=y$). Si veda l'esercizio nr. 7 per un importante approfondimento su questo punto.

Esercizi proposti:

1. $\U(\Z,\cdot)$ è un sottogruppo di $(\R^\#,\cdot)$ (il gruppo moltiplicativo dei reali non nulli)? $(\N,+)$ è un sottogruppo di $(\Z,+)$?
2. Siano $S$ un insieme non vuoto e $x\in S$. Provare che $\set{\alpha\in \Sym(S)\mid \alpha(x)=x}$ è un sottogruppo di $\Sym(S)$.
3. Provare che, per ogni $k\in\N^+$ e per ogni insieme $S$, ogni $k$-ciclo in $\Sym(S)$ ha periodo $k$.
4. Completare la dimostrazione delle formule sulle potenze nei gruppi date a lezione.
5. Si consideri il ciclo $\gamma=(1\,2\,3\,4)\in\S_4$. Si scriva la tavola di Cayley del sottogruppo $G=\gen\gamma$ di $\S_4$ generato da $\gamma$ (dunque, $G$ ha quattro elementi: $\gamma^0=\id_{\set{1,2,3,4}}$, $\gamma$, $\gamma^2$ e $\gamma^3$).
   Si verifichi che $G$ non è isomorfo a $\P(\set{1,2},\ds)$, quindi esistono due gruppi di cardinalità 4 non isomorfi tra loro.
6. Sia $x$ un elemento del semigruppo $(S,\cdot)$. Si verifichi che $C:=\set{a\in S\mid ax=xa}$ è una parte non vuota di $S$, chiusa rispetto a $\cdot$. Verificare, inoltre, che se $(S,\cdot)$ è un monoide (risp. un gruppo), allora $C$ ne costituisce un sottomonoide (risp., un sottogruppo).
7. Sia $A$ un insieme e siano, nell'ordine, $\OS(A)$ e $\OL(A)$ gli insiemi delle relazioni di ordine stretto e di quelle di ordine largo in $A$. Verificare che le applicazioni $\rho\in \OL(A)\mapsto \rho_{\ne}\in\OS(A)$ e $\sigma \in\OS(A)\mapsto \underline\sigma\in \OL(A)$ (le definizioni di $\rho_{\ne}$ e $\underline\sigma$ sono indicate nel resoconto della lezione) sono due biezioni, una inversa dell'altra. (Sono le cosiddette biezioni canoniche tra $\OS(A)$ e $\OL(A)$).

Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche ulteriore commento. In particolare, discussione delle biezioni canoniche tra $\OS(A)$ e $\OL(A)$ per un insieme $A$ (esercizio 7 dalla lezione scorsa)

Insiemi ordinati. Ordinamento indotto su parti di un insieme ordinato. Ordinamento duale; principio di dualità per insiemi ordinati. Minimo e massimo; loro unicità. Proprietà di buon ordinamento di N (rispetto all'ordinamento usuale). Cosidetta ‘seconda forma’ del principio di induzione, argomentazione per controesempio minimo. Giustificazione del principio di induzione (‘prima forma’).

Relazione di divisibilità in semigruppi e monoidi commutativi. Elementi associati. La relazione "essere elementi associati" in un monoide commutativo $(M,\cdot)$: si tratta di una relazione di equivalenza e si può caratterizzare in questo modo: indicando, per ogni $x\in M$ con $\Div(x)$ e $xM$, nell'ordine, gli insiemi dei divisori e dei multipli di $x$ in $M$, per ogni $a, b \in M$ si ha che $a$ e $b$ sono associati in $M$ se e solo se $\Div(a)=\Div(b)$, ovvero se e solo se $aM=bM$. Inoltre, se $a$ è cancellabile, $a$ e $b$ sono associati in $M$ se e solo se $b=au$ per un opportuno $u\in\U(M)$. Elementi tra loro associati in $(\Z,\cdot)$. L'insieme ordinato $(\N,\mid)$.

Anelli, anelli commutativi, anelli unitari. Esempi: $(\Z,+,\cdot)$, $(2\Z,+,\cdot)$ (non unitario), anelli di matrici (come esempi di anelli non commutativi).

Esercizi proposti:

1. In $\P(\Z)$ si definiscano le relazioni binarie $\prec$ e $\preceq$ ponendo, per ogni $a,b\in\P(\Z)$, $a\prec b\iff a\cap\N\subset b\cap\N$ e $a\preceq b\iff a\cap\N\subseteq b\cap\N$. Stabilire: $\prec$ è d'ordine (stretto o largo)? $\preceq$ è d'ordine (stretto o largo)?
2. $(\N^+,\mid)$ ha massimo? Se possibile, trovare in $(\N,\mid)$ 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.
3. Dato un insieme $S$, si descriva in modo esplicito la relazione di divisibilità nel monoide $(\P(S),\cup)$. È una relazione d'ordine? È una relazione che già conosciamo?
   Ripetere l'esercizio sostituendo a $(\P(S),\cup)$ i monoidi $(\N,+)$ e $(\Q,\cdot)$.
4. Verificare in modo diretto (cioè provandone riflessività, simmetria e transitività) che, in un monoide commutativo, la relazione di essere elementi associati è di equivalenza.
5. Dato un monoide commutativo $M$, per ogni $a\in M$ sono equivalenti: (1): $a$ è invertibile; (2): $a$ è associato all'unità di $M$; (3) $aM=M$. Dimostrarlo.
6. Ritornare sull'esercizio nr. 5 da polinomi e strutture algebriche, già affrontato in parte (lezione del 12/11, esercizio 1), decidendo se $(\Z,\oplus,\odot)$ è un anello, un anello commutativo, un anello unitario.
7. (Esempio importante) Dato un insieme $S$, si provi che $(\P(S),\ds,\cap)$ è un anello. Questo anello è commutativo? È unitario?

Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche ulteriore commento. In particolare, discussione dell'anello delle parti $(\P(S),\ds,\cap)$ di un insieme $S$.

Sottoanelli, sottoanelli unitari di un anello unitario. Esempi di sottoanelli di un anello unitario che non sono unitari oppure lo sono ma non come sottoanelli.

Notazioni ed alcune regole di calcolo negli anelli: se $(R,+,\cdot)$ è un anello, per ogni $x\in R$ si indica con $-x$ l'opposto (simmetrico in $(R,+)$) di $x$ in $R$; per ogni coppia di elementi $a$ e $b$ dell'anello $R$ si scrive $a-b$ per $a+(-b)$; si ha $a0_R=0_R=0_Ra$, dove $0_R$ è lo zero di $R$, e $a(-b)=-(ab)=(-a)b$. Conseguenza: se $|R|>1$, lo zero di $R$ non può essere invertibile (cioè simmetrizzabile rispetto alla moltiplicazione in $R$, qualora $R$ sia unitario). Corpi e campi. Esempi. In ogni anello unitario $R$ si ha $(n 1_R)x=nx$ per ogni $n\in\Z$ e $x\in R$. Caratteristica di un anello unitario. Qualche esempio. Formula del binomio di Newton. Non ne è stata data dimostrazione se non per cenni, 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)^2=a^2+b^2+2ab$ se e solo se $ab=ba$.

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

Partizioni ed equivalenze compatibili con un'operazione binaria. Congruenze in una struttura algebrica. Esempio: l'equivalenza "avere lo stesso segno" 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$. Invece la relazione "avere la stessa parità" è una congruenza in $(\Z, +, \cdot)$. Altro esempio: nel monoide delle parole su un alfabeto, l'equivalenza definita definita dichiarando equivalenti due parole se e solo se esse hanno la stessa lunghezza è un congruenza. (Si veda l'esercizio esercizio 4 come generalizzazione di questo esempio; fare riferimento all'omomorfismo dal monoide delle parole ad $(\N,+)$ che ad ogni parola associa la sua lunghezza.)

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. Struttura quoziente. Proprietà che si conservano passando alla struttura quoziente (come associatività, commutatività, esistenza di neutri e simmetrici, distributività — verifiche lasciate per esercizio); 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.

Esercizi proposti:

1. Verificare che l'applicazione di cui all'esercizio nr. 8 della lezione del 14/11 è un isomorfismo di anelli unitari da $(\Z,+,\cdot)$ a $(\Z,\oplus,\odot)$.
2. Sia $T=\bigl\{\bigl(\begin{smallmatrix} a&b\\0&c\end{smallmatrix}\bigr)\mid a,b,c\in\R\bigr\}$ (insieme delle matrici triangolari alte di tipo $2\times 2$ sui reali). Verificare che $T$ è un sottoanello unitario dell'anello $M_2(\R)$ delle matrici $2\times 2$ sui reali. Provare che il suo monoide moltiplicativo è isomorfo al monoide $(S,*)$ descritto nell'esercizio 3 del compito del 14 novembre scorso.
3. Siano $S$ un insieme e $T$ un suo sottoinsieme non vuoto. L'insieme $\set{X\mid T\subseteq X\subseteq S}$ è un sottoanello di $(\P(S),\ds,\cap)$?
4. Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è una congruenza in $(A,*)$.
5. Sia $v\colon n\in\Z\mapsto |n|\in\Z$, l'applicazione valore assoluto. Questa è un omomorfismo da $(\Z,+)$ a $(\Z,+)$? E da $(\Z,\cdot)$ a $(\Z,\cdot)$? Studiare la struttura ottenuta quozientando $\Z$ rispetto al nucleo di equivalenza di $v$. Questa è per caso isomorfa ad una struttura che ben conosciamo?
6. Sia $M$ un monoide commutativo. Provare che la relazione "essere elementi associati" è una congruenza in $M$.
7. La relazione di equipotenza in $\P(\N)$ è compatibile con una delle operazioni $\cap$, $\cup$, $\ds$?
8. Dimostrare che l'anello quoziente $\set{P,D}$ di $(\Z, + ,\cdot)$ presentato a lezione, dove $P$ e $D$ sono rispettivamente l'insieme dei numeri pari e quello dei numeri dispari, è un campo, isomorfo a $(\P(S),\ds,\cap)$ se $S$ è un singleton.

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Omomorfismi di monoidi e di anelli unitari. Esempi.

Le congruenze modulo un intero in $\Z$ (cioè le equivalenze $\equiv_m$ al variare di $m\in\Z$). Osservazioni: $\equiv_0$ è la relazione uguaglianza, $\equiv_1$ è la relazione universale, $\equiv_2$ è la relazione "avere la stessa parità" discussa tra gli esempi nella scorsa lezione; per ogni $m\in \Z$, $\equiv_{-m}$ coincide con $\equiv_m$. Verifica diretta del fatto che tutte queste sono congruenze nell'anello $(\Z,+,\cdot)$. Solo a titolo di notizia, è stato menzionato il fatto che queste sono le sole congruenze dell'anello $(\Z,+,\cdot)$, anzi le sole relazioni di equivalenza in $\Z$ compatibili con l'addizione. Gli anelli quoziente $\Z_m:=\Z_{\equiv_m}$. Descrizione esplicita delle classi resto: per ogni $m,a\in \Z$, la classe di resto $[a]_m:=[a]_{\equiv_m}$ di $a$ modulo $m$ è $a+m\Z:=\set{a+mk\mid k\in \Z}$. L'operazione parziale mod (per ogni $a,m\in\Z$, se $m\ne0$, $a\modbin m$ è, per definizione, il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$). Descrizione esplicita dei quozienti di $\Z$: per ogni $m\in\N^+$, $\Z_m=\set{[0]_m, [1]_m, [2]_m, \dots, [m-1]_m}$. Gli elementi di $\Z_m$ appena elencati sono a due a due distinti (vale a dire: se $a$ e $b$ sono interi compresi tra $0$ e $m-1$ e $a\equiv_m b$, allora $a=b$), quindi $|\Z_m|=m$. Per ogni $n\in\Z$ si ha poi $n[1]_m=[n]_m$, di conseguenza $\Z_m$ ha caratteristica $m$.

Divisione con resto (o divisione aritmetica) in $\Z$: $(\forall a, b\in\Z)(b\ne 0\implica (\exists!(q,r)\in\Z\times\N)(a=bq+r \land r<|b|) )$. Con queste notazioni, $a$, $b$, $q$ ed $r$ prendono rispettivamente i nomi di dividendo, divisore, quoziente e resto (nella divisione di $a$ per $b$) e si ha $r=a\modbin b$; si scrive anche $r=\rest(a,b)$. Congruenze in $\Z$ come nuclei di equivalenza di funzioni resto (due interi sono congrui modulo un intero non nullo $m$ se e solo se hanno lo stesso resto nella divisione per $m$).

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

Esercizi proposti:

1. Calcolare $23\modbin 9$ (ovvero: $\rest(23,9)$), $23\modbin (-9)$, $(-23)\modbin 9$ , $(-23)\modbin (-9)$.
2. Si elenchino gli elementi di $S\cap [7]_4$, dove $S=\set{n\in\Z\mid -10 \le n \le 10}$.
3. Fissato $m\in\N$, si descriva in modo esplicito (e semplice) la classe $[0]_m$. Questa classe è un sottogruppo di $(\Z,+)$? Esistono altri elementi in $\Z_m$ che sono sottogruppi di $(\Z,+)$?
4. Calcolare $876984737830287! \modbin 123456789$.
5. Si trovino i divisori dello zero in $(\P(\Z),\ds,\cap)$.
6. Si descriva in dettaglio l'anello $\Z_6$, stabilendo per ogni suo elemento $c$ se $c$ è o meno: invertibile, divisore dello zero, cancellabile, idempotente. Ripetere l'esercizio per l'anello $\Z_5$.

Discussione di alcuni degli esercizi proposti nella lezione precedente, con qualche ulteriore commento. In particolare, discussione delle proprietà dei singoli elementi dell'anello $\Z_6$. Solo a titolo di notizia: tutti gli anelli integri finiti sono campi.

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

Ancora sul periodo di un elemento in un gruppo. Sia $x$ un elemento di un gruppo $(G,\cdot,1_G,{}^{-1})$. Allora $x$ è periodico se e solo l'applicazione $n\in\Z\mapsto x^n\in G$ non è iniettiva. (Dunque, in un gruppo finito ogni elemento ha periodo finito. Senza dimostrazione si è menzionato il fatto che, sempre nell'ipotesi che $G$ sia finito, $x^{|G|}=1_G$, dunque il periodo di $x$ divide $|G|$). Se $x$ ha periodo finito $\lambda$, allora, per ogni $n$, $m\in \Z$, si ha $x^n=x^m\iff n\equiv_\lambda m$ (vale a dire: $\equiv_m$ è il nucleo di equivalenza dell'applicazione appena definita. Dunque: $x^n=x^{n\,\modbin\,\lambda}$). In particolare, $x^n=1$ se e solo se $\lambda$ divide $n$; l'inverso di $x$ è $x^{\lambda-1}$. Inoltre, in queste ipotesi, il sottogruppo (ciclico) generato da $x$ ha ordine $\lambda$. In ogni gruppo, l'elemento neutro è l'unico elemento di periodo 1. Utilizzo della nozione di periodo per i calcoli di potenze in aritmetica modulare.

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.

Divisori banali e fattorizzazioni banali; elementi irriducibili ed elementi primi in un monode commutativo cancellativo. Sia la proprietà di essere primo che quella di essere irriducibile si conserva nel passaggio da un elemento ad un suo associato.

Esercizi proposti:

1. Posto $n=23456789987654321$, calcolare $n \modbin 9$, $n^n \modbin 9$, $n \modbin 11$ e $n^n \modbin 11$.
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 è giovedì, che giorno della settimana sarà tra $1000+497(823^{32}+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 riformato il nostro calendario).
4. Calcolare i periodi delle permutazioni $\sigma:=(1\,2)\circ(3\,4)$ e $\tau:=(1\,2\,3)\circ(4\,5)$ in $\S_5$. Calcolare $\sigma^{289027426587}$ e $\tau^{180035}$.
5. Verificare che $[2]_{31}$ è invertibile in $(\Z_{31},\cdot)$ e calcolarne il periodo. Dopo aver fatto ciò, calcolare $2^{65772846764193659377}\modbin 31$.
6. Se $G$ è un gruppo, in notazione moltiplicativa, e $x\in G$, provare che l'applicazione $n\in\Z\mapsto x^n\in G$ menzionata nel corso della lezione è un omomorfismo da $(\Z,+)$ a $G$. (È a partire da questa osservazione che si può dimostrare che tutti i gruppi ciclici sono isomorfi a $(\Z,+)$ o a $(\Z_m,+)$ per un opportuno $m\in\N^+$.)

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Fattorizzazioni "essenzialmente uguali" (cioè uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati) in monoidi cancellativi. 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 (banalmente) fattoriali i gruppi. Anelli fattoriali (esempi: $\Z$, tutti i campi).

Senza fornire dimostrazioni, si è accennato a questi fatti: se $M$ è un monoide commutativo cancellativo, 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\in M$ e $a=p_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una sua decomposizione primaria (dunque, i $p_i$ sono irriducibili a due a due non associati tra loro, e gli esponenti $a_i$ sono interi positivi), i divisori di $a$ in $M$ sono tutti e soli gli elementi della forma $u p_1^{b_1} p_2^{b_2}\cdots p_n^{b_n}$, dove $u$ è un invertibile e ciascuno degli esponenti $b_i$ è un numero naturale minore o uguale ad $a_i$.

Cenno al crivello di Eratostene. Per verificare che un intero $n\ge 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 parti in semigruppi commutativi. 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$.

Esercizi proposti:

1. 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?
2. Perché, senza effettuare alcun calcolo, possiamo immediatamente stabilire che 9000000000000000000000000000 non è multiplo di 13?
3. Esercizi 7 e 8 da Tautologie, insiemi, aritmetica.
4. Elencare i divisori in $\N$ di 270 ed i divisori in  $\Z$ di 60.
5. Quanti sono i divisori in $\N$ di $2^4 7^2 41^{44}$?
6. Esiste $n\in \N$ tale che 85 divida $2^{11n}3^{2n+3}7^{n(3n+1)}13^{6n}$?
7. $2^5 3^5 5^6$ divide $2^6 3^{15}7^2 11$ in $\Z$?
8. Qual è il minimo intero positivo $n$ tale che $10^6$ (cioè un milione) divida $n!$ ?
9. Sia $P=\set 1 \cup 2\N$. Dopo aver verificato che $(P,\cdot)$ è un sottomonoide cancellativo di $(\N,\cdot)$, provare che in $P$ gli elementi $2$, $6$ e $18$ sono irriducibili e $36$ ha due fattorizzazioni essenzialmente diverse come prodotto di irriducibili ($36=6\cdot 6=2\cdot 18$).

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\in \Z$ e $b\ne 0$, esistono interi $q$ ed $r$ tali che $a=bq+r$ e $|r|\le |b/2|$).

Equazioni diofantee (di primo grado, a due indeterminate). Estensione dell'algoritmo euclideo e Teorema di Bézout (come determinazione dell'insieme delle combinazioni lineari tra due interi o, equivalentemente, come criterio di esistenza di soluzioni di equazioni diofantee del tipo considerato). La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo.

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\in\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 l'equazione congruenziale $ax\equiv_m b$ e quello di risolvere l'equazione diofantea $ax+my=b$ (dove $a, b$ ed $m$ sono interi). Criterio di esistenza di soluzioni per le equazioni congruenziali.

Elementi invertibili nei quozienti di $\Z$. Se $m\in \N^+$, l'anello $\Z_m$ è un campo se e solo se $m$ è primo.

Altri appunti sugli argomenti trattati in questa lezione (e, presumibilmente, nella prossima) sono disponibili nel sito docenti della Professoressa Leone.

Esercizi proposti:

1. Esercizi 5, 9 (utilizzare l'agoritmo euclideo) e 6 da Tautologie, insiemi, aritmetica. (NB: l'espressione $ax\equiv b\pmod m$ è equivalente a $ax\equiv_m b$.)
2. Trovare, se possibile, soluzioni delle equazioni congruenziali $302x\equiv_{144} 6$, $144x\equiv_{302} 6$ e $151x\equiv_{72} 3$.
3. Trovare, se possibile, soluzioni dell'equazione congruenziale $200x+10\equiv_{72} 49x+13$.
4. Aldo deve a Bice 147 talleri boemi. Sapendo che il tallero boemo viene emesso solo in monete da 357 e da 700 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?
5. Si individuino gli elementi invertibili, quelli cancellabili, quelli idempotenti e i divisori dello zero dell'anello $\Z_{20}$.

Equazioni congruenziali (di primo grado, ad una incognita): metodi di soluzione e di semplificazione; diversi esempi. Equazioni congruenziali ridotte. Determinazione dell'insieme di tutte le soluzioni intere di un'equazione congruenziale (del tipo considerato). Dati gli interi $a$, $m$ e $k$, con $mk\ne 0$, confronto tra le classi resto $[a]_m$ e $[a]_{km}$. Descrizione dell'insieme di tutte le soluzioni di un'equazione diofantea di primo grado in due incognite.

Introduzione alla funzione di Eulero; il numero degli invertibili in un quoziente di $\Z$. Cenni al Teorema di Fermat-Eulero e alle sue applicazioni in crittografia.

Elementi minimali e massimali in insiemi ordinati. Esempi. In ogni insieme ordinato, il minimo (se esiste) è l'unico elemento minimale; il massimo (se esiste) è l'unico elemento massimale. Ogni insieme ordinato finito e non vuoto ha elementi minimali ed elementi massimali.

Esercizi proposti:

1. Esercizi 10 e 11 da Tautologie, insiemi, aritmetica.
2. Usando il teorema di Fermat-Eulero, calcolare $13^{181} \modbin 19$.
3. Si determinino gli eventuali elementi minimali e massimali in ciascuno dei seguenti insiemi, tutti ordinati per inclusione: $\P(\Z)$, $\Pf(\Z)$ (l'insieme delle parti finite di $\Z$), $\P(\Z)\setminus \set\Z$ (l'insieme delle parti proprie di $\Z$).
4. Si determinino gli eventuali elementi minimali e massimali in $(\N,\le)$ e $(\Z,\le)$ (ordinamento usuale).
5. Si determinino gli eventuali elementi minimali, massimali, minimo, massimo in $\set{n\in\N^+\mid n<10}$, ordinato per divisibilità.
6. Sia $(S,\le)$ un insieme totalmente ordinato, e sia $x\in S$. È vero che se $x$ è minimale (risp. massimale) in $(S,\le)$ allora $x$ è minimo (risp. massimo) in $(S,\le)$?
7. Sia $a$ un insieme non appartenente a $\Z$. Si definisca la relazione binaria $\sigma$ in $S:=\set{a}\cup\Z$, ponendo, per ogni $x,y\in S$, $x\mathrel{\sigma} y\iff \left((x,y\in \Z)\land(x \lt y)\right)$, dove $<$ denota l'ordinamento usuale tra interi. Dimostrare che:
   1. $\sigma$ è una relazione di ordine stretto in $S$;
   2. nell'insieme ordinato $(S,\sigma)$, $a$ è l'unico elemento minimale ed anche l'unico elemento massimale, ma non è né minimo né massimo.

Discussione di diversi esercizi proposti nelle lezioni precedenti, con qualche ulteriore commento. Tra questi, hanno rilevanza anche per la teoria gli esercizi 6 e 7 della lezione scorsa.

Diagrammi di Hasse di insiemi ordinati finiti; relazione di copertura associata ad un ordinamento. Alcuni esempi.

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

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

Esempi: estremi inferiori e superiori in $(\P(S),\subseteq)$ per un insieme $S$ ed in $(\N,\mid)$: sono descritti da intersezione ed unione nel primo caso, da MCD e mcm nel secondo.

Reticoli. Definizione ed esempi. Il duale di un reticolo è necessariamente un reticolo; principio di dualità per reticoli. Gli insiemi totalmente ordinati non vuoti sono reticoli.

Osservazione: se $A$ e $B$ sono parti di un insieme ordinato $(S,\le)$, nel quale esistono $a=\inf A$ e $b=\inf B$, allora, sempre in $(S,\le)$, l'insieme dei minoranti di $A\cup B$ coincide con l'insieme dei minoranti in $(S,\le)$ di $\set{a,b}$; dunque esiste $\inf(A\cup B)$ se e solo se esiste $\inf\set{a,b}$, nel qual caso questi due estremi inferiori coincidono. Vale l'enunciato duale per gli estremi superiori. Conseguenza: in ogni reticolo ogni parte finita non vuota ha estremo superiore ed estremo inferiore, dunque: i reticoli finiti sono limitati (cioè hanno minimo e massimo).

Esercizi proposti:

1. Esibire un esempio di reticolo infinito limitato.
2. 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\le a$.
3. (Generalizzazione dell'esercizio 1 dalla lezione dell'11 novembre). Sia $T$ un insieme ordinato dalla relazione d'ordine largo $\le$ (o, equivalentemente dalla corrispondente relazione d'ordine stretto $<$). Sia $f\colon S\to T$ un'applicazione di codominio $T$. Definiamo in $S$ due relazioni binarie $\preceq$ e $\prec$, ponendo, per ogni $a,b\in S$, $\quad a\preceq b \iff f(a)\le f(b)\quad$e$\quad a\prec b \iff f(a)< f(b)$. Provare che:
   1. $\prec$ è una relazione di ordine stretto in $S$.
   2. In $(S,\prec)$, gli elementi minimali sono tutti e soli quelli di $\antivecf(M)$, dove $M$ è l'insieme degli elementi minimali di $\im f$ (rispetto all'ordinamento indotto da $\le$ su $\im f$).
   3. Descrivere gli elementi massimali in $(S,\prec)$.
   4. $\preceq$ è una relazione di ordine (largo) in $S$ se e solo se $f$ è iniettiva.
4. Per ogni $n\in\set{4,6,9,12,19,20,30}$ disegnare il diagramma di Hasse dell'insieme $\Div_\N(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.
5. Si disegni il diagramma di Hasse dell'insieme $\set{1,2,5,20,50,100}$, ordinato per divisibilità. Questo è un reticolo?
6. Esercizio nr. 6 da relazioni binarie, tralasciando tutto ciò che segue la domanda che chiede se l'insieme ordinato studiato sia o meno un reticolo.

Reticoli completi. Esempi: $(\P(S),\subseteq)$ per un insieme $S$ e $(\N,\mid)$ sono completi; $\Z$ e $\R$, con l'ordinamento usuale, non sono completi; l'insieme $\Q\cap [0,1]$ dei numeri razionali compresi tra 0 e 1, munito dell'ordinamento usuale, è un reticolo limitato non completo.

In ogni reticolo, ogni elemento minimale (risp. massimale) è minimo (risp. massimo).

Operazioni reticolari e loro proprietà (commutatività, associatività, iteratività, leggi di assorbimento). Reticoli come strutture algebriche. Equivalenza tra le nozioni di reticolo come insieme ordinato e di reticolo come struttura algebrica (in particolare: coincidenza tra le due possibili nozioni di isomorfismo); passaggio da un tipo di struttura all'altro. Esempio particolarmente significativo: per un insieme $S$, le strutture $(S,\subseteq)$ e $(S,\cap,\cup)$.

Sottoreticoli; esempi, tra cui gli intervalli chiusi in un reticolo; in particolare: $\Div(n)$ in $(\N,\mid)$, per un $n\in \N$. 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. Il complemento non è necessariamente unico. Ove presenti, minimo e massimo sono l'uno complemento dell'altro. Reticoli complementati. Un sottoreticolo di un reticolo complementato può non essere complementato. Le catene (cioè: gli insiemi totalmente ordinati) sono complementati se e solo se hanno al più due elementi. Diversi esempi.

Reticoli distributivi. Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), le catene. 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 reticoli booleani. Sottoalgebre di Boole. Enunciato del teorema di Stone (nel caso finito e, poi, nel caso generale). Conseguenze: 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.

Esercizi proposti:

1. Tutti i reticoli finiti sono completi.
2. Se $X$ è un sottoinsieme non vuoto di $\R$, allora $X$ è completo (rispetto all'ordinamento usuale di $\R$) se e solo se è dotato in $\R$ di minoranti e maggioranti.
3. Completare l'esercizio nr. 6 e svolgere gli esercizi 5, 7 e 8 da relazioni binarie. Al fine di questi esercizi, trattare l'espressione "algebra di Boole" come sinonimo di "reticolo booleano".
4. Utilizzando solo, in modo diretto, la definizione di distributività, verificare che i reticoli trirettangolo e pentagonale non sono distributivi. L'esercizio consiste nel trovare, in ciascuno dei due reticoli, elementi $a$, $b$, $c$ per i quali si abbia $a\land(b\lor c)\ne (a\land b)\lor (a\land c)$ oppure $a\lor(b\land c)\ne (a\lor b)\land (a\lor c)$.
5. Sia $T$ un sottoinsieme proprio dell'insieme $S$. Verificare che, nel reticolo booleano $(\P(S),\subseteq)$, $\P(T)$ è un intervallo chiuso, quindi un sottoreticolo; ma $\P(T)$ non costituisce una sottoalgebra dell'algebra di Boole $\P(S)$.
6. Provare che, in ogni algebra di Boole, l'operazione unaria di complemento è involutoria (cioè: il complemento del complemento di ogni elemento $x$ è $x$ stesso).
7. Verificare, in una arbitraria algebra di Boole $B$, le leggi di De Morgan: per ogni $a$, $b\in B$, $(a\land b)'=a'\lor b'$ e $(a\lor b)'=a'\land b'$.
8. Passare buone feste.

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. Teorema di Stone per anelli booleani. (Le sottoalgebre di Boole di un'algebra di Boole sono precisamente i sottoanelli unitari dell'anello booleano costruito su di essa).

Cenno al prodotto diretto di anelli; per ogni intero positivo $n$, l'anello booleano $\Z_2^n$ e sua rappresentazione come insieme di "stringhe di zeri ed uno" di lunghezza $n$. Anelli booleani e funzioni caratteristiche: discussione dettagliata dell'isomorfismo canonico di anelli da $\P(\set{1,2,\dots,n})$ a $\Z_2^n$ (si faccia anche riferimento a quanto visto nel corso della lezione del 29/10); interpretazione insiemistica delle algebre di Boole costituite da stringhe di zeri ed uno di assegnata lunghezza.

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

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario: definizione. Note (diverse) sui polinomi sono qui e nel sito docenti della Professoressa Leone.

Esercizi proposti:

1. Quali anelli booleani sono domini di integrità?
2. Completare in tutti i dettagli la dimostrazione della correttezza della costruzione, accennata a lezione, del prodotto diretto di anelli.
3. Sia $S=\set{a,b,c}$ un insieme tale che $|S|=3$. Si scriva esplicitamente un isomorfismo dall'anello (booleano) $\Z_2^3$ a $(\P(S),\ds,\cap)$.

Proprietà universale per gli anelli dei polinomi. Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata). La proprietà universale è stata anche utilizzata per definire l'omomorfismo di sostituzione e, 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, termine noto, polinomi costanti, polinomi monici. Abbiamo assunto $-\infty$ e $0$ come grado e coefficiente direttore del polinomio nullo; per il resto la terminologia è conforme quella delle mie note.

Applicazione polinomiale definita da un polinomio. Osservazione: polinomi distinti possono definire la stessa applicazione polinomiale: esempi costruiti su anelli finiti e su anelli booleani. Per ogni anello commutativo unitario $A$, $A[x]$ è infinito.

D'ora in avanti, nel resoconto di questa lezione $A$ indica sempre un anello commutativo unitario.

Grado del prodotto tra due polinomi. Se il polinomio $f\in A[x]$ ha coefficiente direttore cancellabile (in $A$), allora $f$ stesso è cancellabile in $A[x]$ ed inoltre vale per $f$ ed un qualsiasi polinomio $g\in A[x]$ la regola di addizione dei gradi: $\nu(fg)=\nu(f)+\nu(g)$. Esempi nei quali questa regola fallisce.

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 (per ogni coppia di polinomi) e si ha $\U(A[x])=\U(A)$. Esempi che mostrano come queste due proprietà non valgano necessariamente se $A$ non è integro.

Qualunque sia $A$, $x\notin\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.

Grado della somma e della differenza tra due polinomi. Divisione tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto.

Esercizi proposti:

1. Per ogni $n\in\N^+$ sia $f_n=3nx^5+1\in\Z_{10}[x]$. Per quali valori di $n$ si ha che $f_n$ è monico? Trovare, se possibile, $n,m\in\N^+$ tali che $\nu(f_n\, f_m)<25$.
2. Dividere, in ciascuno degli anelli $\Q[x]$ e $\Z_5[x]$ il polinomio $2x^4+1$ per $3x+2$.

Ancora sulla divisione tra due polinomi $f$ (dividendo) e $g$ (divisore) in $A[x]$, dove $A$ è un anello commutativo unitario. È sicuramente possibile effettuare la divisione se (1): $g\ne 0$ e $A$ è un campo; oppure (2): $g$ è monico.

Per l'anello dei polinomi su un campo: algoritmo euclideo per la ricerca di un MCD e Teorema di Bézout. (Informazione: questo teorema non vale in $\Z[x]$.)

Teorema del resto: con le notazioni di sopra, se $g=x-c$ per un $c\in A$, allora il resto nella divisione di $f$ per $g$ è $f(c)$. Come conseguenza, Teorema di Ruffini. Nel caso in cui $A$ sia un dominio di integrità: Teorema di Ruffini generalizzato e sue e conseguenze: (1) se $A$ è dominio di integrità unitario e $0\ne f\in A[x]$, allora $f$ ha al più $\nu(f)$ radici in $A$; (2) principio di identità dei polinomi: se, inoltre, $A$ è infinito due polinomi in $A[x]$ coincidono se e solo se definiscono la stessa applicazione polinomiale. Controesempi mostrano che questi risultati non valgono per anelli commutativi unitari arbitrari.

Teorema (non dimostrato): se $A$ è un anello fattoriale, $A[x]$ è un anello fattoriale. Fattorizzazioni nell'anello dei polinomi su un campo $K$: associato monico di un polinomio non nullo; 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 in $\Q[x]$. Ciascuno di essi ha un associato in $\Z[x]$. Radici razionali di un polinomio $f\in\Z[x]$; se $f$ è monico tali radici sono intere. Criterio di irriducibilità di Eisenstein. Per ogni $n\in\N^+$ ed ogni primo positivo $p$, $x^n-p$ è irriducibile in $\Q[x]$. Per il contenuto di questa lezione si possono consultare le mie note sui polinomi, che possono essere di aiuto anche per gli esercizi qui sotto indicati.

Esercizi proposti:

1. Si costruisca, se possibile, un polinomio di grado 500 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-20\le n <100$.
2. Determinare il massimo comun divisore monico in $\Q[x]$ tra $x^8-1$ e $x^5-1$.
3. Elencare i polinomi irriducibili di grado 2 o 3 in $\Z_2[x]$.
4. In $\Z_3[x]$ si consideri il polinomio $f=x^4+x^3+x^2+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_3[x]$) per $2x^4+x^3+x^2+x+2$ al posto di $f$.
5. Esercizio nr. 3 da Polinomi e strutture algebriche.

Introduzione ai grafi. Diverse nozioni di grafo. Definizione di grafo semplice (sia in termini di lati che in termini di relazione di adiacenza; equivalenza tra le due definizioni). Definizione 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. Sottografi.

Nozione di (multi)grafo planare (ovvero: piano) ed enunciato del teorema di Kuratowski. Grafi bipartiti.

Teorema: il doppio del numero dei lati di un multigrafo finito è la somma dei gradi dei suoi vertici. Vertici pari e vertici dispari; questi ultimi sono in numero pari.

Cammini e circuiti. Relazione di connessione; (multi)grafi connessi. Componenti connesse di un grafo. Distanza in un grafo connesso

Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari (solo enunciato). Esempi, tra cui il problema dei sette ponti di Königsberg.

Foreste e alberi. Teorema: un grafo finito $G$ è una foresta se e solo se per ogni coppia $(a,b)$ di vertici distinti 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.

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, se $G$ è una foresta allora $G$ 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|\ge|V|-1$.

Esercizi proposti:

1. Esercizi da Grafi, ad esclusione del nr. 4.
2. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) su quattro vertici.
3. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) connessi su cinque vertici. Indentificare tra questi gli alberi.
4. 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$.