6/3

Introduzione al corso: presentazione, informazioni generali, modalità di svolgimento, materiali didattici.

Cenni sulla logica proposizionale: nozioni informali di linguaggio, formula, proposizione (formula chiusa). Alcuni connettivi proposizionali (introdotti e descritti solo semanticamente): negazione, congiunzione, disgiunzione inclusiva, disgiunzione esclusiva (XOR), congiunzione negata (NAND), equivalenza (o bicondizionale). 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, legge delle doppia negazione, commutatività di congiunzione, disgiunzione, disgiunzione esclusiva, bicondizionale, leggi di De Morgan. alcune tautologie sull'implicazione (doppia implicazione, implicazione come disgiunzione, negazione dell'implicazione, legge di contrapposizione); Per il connettivo di implicazione non vale la commutatività.

Per il contenuto di questa lezione e delle prossime, si vedano Logica rudimentale, tavola dei connettivi binari, esempi di tautologie. Potrebbe esere utile avere queste note con sé in aula.

Esercizi proposti:

1. Verificare che per ciascuna scelta di $*$ tra $\land$ e $\lor$, la forma proposizionale $(p * p)\iff p$ è una tautologia (tautologie dell'idempotenza).
2. La forma proposizionale $(p\iff p)\iff p$ è una tautologia, una contraddizione oppure contingente? La forma proposizionale $(p\xor p)\iff p$ è una tautologia, una contraddizione oppure contingente? La forma proposizionale $p\xor p$ è una tautologia, una contraddizione oppure contingente?
3. Negare la frase "Aldo e Bruno giocano a golf".
4. Verificare la tautologia $((p\land q)\land r)\iff (p\land (q\land r))$ (associatività del connettivo di congiunzione.
5. Svolgere quanti più è possibile tra gli esercizi A, B, e, soprattutto, D da Logica rudimentale.
6. Se indichiamo con $p$ la formula “$3x\lt 4$” e con $q$ la formula “$y+1=z$”, quale connettivo proposizionale va inserito al posto di “$*$” in modo che la formula $p\mathop * q$ traduca (dal punto di vista della logica proposizionale) la frase “$3x\lt 4$, nonostante $y+1=z$”?
7. La forma proposizionale $\bigl(q\iff r\bigr)\iff \bigl((p\land q)\iff(p\land r)\bigr)$ è una tautologia?

9/3

Rapida discussione su alcuni esercizi dalla lezione precedente.

Il connettivo di implicazione (o condizionale), con ampia discussione e diverse tautologie che lo riguardano. Altre tautologie, tra cui associatività di bicondizionale e XOR e distributività della congiunzione rispetto alla XOR.

Osservazioni sulla interdipendenza tra i connettivi binari: per esprimerli tutti bastano $\lnot$ e $\land$ (ovvero $\lnot$ e $\lor$) o, addirittura, il solo NOR (o il solo NAND).

Per tutti questi materiali si vedano Logica rudimentale, Tavola dei connettivi binari, Esempi di tautologie e la prima colonna di Tautologie e identià insiemistiche.

Introduzione alla logica dei predicati. Variabili, quantificatori universale ed esistenziale: sintassi essenziale ed interpretazione. Il quantificatore $\exists!$, descritto, per ogni formula $\phi$ dall'equivalenza $(\exists!x(\phi(x)))\iff(\exists x\forall y(\phi(y)\iff x=y))$.

Esercizi proposti:

1. Verificare le tautologie che esprimono la distributività della congiunzione rispetto alla disgiunzione e, viceversa, della disgiunzione rispetto alla congiunzione: $\bigl(p\land (q\lor r)\bigr)\iff \bigl((p\land q)\lor (p\land r)\bigr)$ e $\bigl(p\lor (q\land r)\bigr)\iff \bigl((p\lor q)\land (p\lor r)\bigr)$.
2. $\bigl(p\lor (q\xor r)\bigr)\iff \bigl((p\lor q)\xor (p\lor r)\bigr)$ è una tautologia?
3. Esercizi C ed E da Logica rudimentale.
4. Negare: “Se domani il tempo è bello e Carlo si sveglia presto, o andremo a mare oppure 4567 è un numero primo”.
5. Negare la forma proposizionale $(p\land q)\implica (r\lor s)$.

13/3

Rapida discussione su alcuni esercizi dalla lezione precedente.

Occorrenze libere o vincolate di variabili; sostituzioni di termini a variabili. Formule chiuse.

Quantificatori ristretti. Formule con quantificatori ristretti ad una condizione impossibile, come $(\forall x\in\varnothing)(\dots)$ o $(\exists x\in\vuoto)(\dots)$.

Alcune altre 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 (anche con quantificatori ristretti).

Nozione di insieme. Il simbolo '$\in$' di appartenenza. Assioma di estensionalità. Unicità del'insieme vuoto. Cenni a problemi fondazionali: estensione di un predicato unario, antinomia di Russell. Schema di assiomi di separazione.

Inclusione tra insiemi: definizione di $\subseteq$. È importante distinguere bene tra appartenenza e inclusione. Ad esempio, per ogni $a$ si ha $\vuoto\subseteq a$, (in particolare, $\vuoto\subseteq\vuoto$), ma $\vuoto\notin\vuoto$. Si ha, più in generale (è una conseguenza di un assioma noto come assioma di fondazione): $\forall a(a\notin a)$. Singleton di un insieme.

Comparazione tra i connettivi di equivalenza e implicazione, da una parte, e le relazioni di uguaglianza o inclusione tra insiemi dall'altra.

Esercizi proposti:

1. Esercizi G ed H da Logica rudimentale.
2. Negare: “Almeno uno dei miei amici, se dorme russa”.
3. Negare la formula: $\exists x (\forall y (\phi(x,y)))\implica \forall x (\exists y (\psi(x,y)))$.
4. 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)}$.
5. Supponendo asegnato il numero $n$, quanti elementi ha l'insieme $\set{1,n-3}$?

16/3

Operazioni insiemistiche (unione ed intersezione binarie, complemento relativo, differenza simmetrica) e loro proprietà. Formule insiemistiche ricavate da tautologie (come nella sezione finale di Logica rudimentale, ma si veda anche Tautologie e identità insiemistiche).

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

Operazione insemistica di unione unaria.

Esercizi proposti:

1. Esercizi J da Logica rudimentale.
2. Provare le formule insiemistiche di De Morgan seguendo le indicazioni in Logica rudimentale, pag. 22.
3. Usando diagrammi di Venn, confrontare, per arbitrari insiemi $a$, $b$, $c$, gli insiemi $a\cup(b\setminus c)$ e $(a\cup b)\setminus c$.
4. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
5. Calcolare, per un arbitario insieme $a$, $a\ds a$.

20/3

L'operazione insemistica di intersezione unaria per insiemi non vuoti.

Coppie ordinate. Prodotto cartesiano tra due insiemi. $\forall a,b(a\times b=\vuoto\iff (a=\vuoto\lor b=\vuoto))$. Se $a$ e $b$ sono finiti, $|a\times b|=|a|\cdot|b|$. Terne ordinate.

Corrispondenze tra due insiemi; diversi modi per rappresentarle (diagrammi, tabelle). Relazioni binarie in un insieme. Notazioni: $\Corr(A,B)$ e $\Rel(A)=\Corr(A,A)$, per insiemi $A$ e $B$.

Prodotto relazionale tra corrispondenze e sua associatività.

Applicazioni tra insiemi. Dominio e codominio. Il problema della "buona" (corretta) definizione di un'applicazione; alcuni esempi.

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.

Solo terminolgia: trasformazioni di un insieme, cioè applicazioni da un insieme a se stesso.

Composizione (prodotto operativo) tra applicazioni: il prodotto relazionale tra due applicazioni componibili è sempre un'applicazione. Sua descrizione esplicita. Notazione: $\beta\circ\alpha:=\alpha\beta$. Applicazione identica in un insieme e sue proprietà di neutralità.

Esercizi proposti:

1. Verificare le formule infinitarie di De Morgan: se $S$ ed $A$ sono insiemi e $A\ne\vuoto$, $S\setminus\bigcap A=\bigcup\set{S\setminus a\mid a\in A}$ e $S\setminus\bigcup A=\bigcap\set{S\setminus a\mid a\in A}$.
2. Verificare le formule infinitarie di distributività tra unione e intersezione: se $S$ ed $A$ sono insiemi e $A\ne\vuoto$, $S\cup\big(\bigcap A\big)=\bigcap\set{S\cup a\mid a\in A}$ e $S\cap\big(\bigcup A\big)=\bigcup\set{S\cap a\mid a\in A}$.
3. (non facilissimo) 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).
4. Siano $a$ e $b$ due insiemi. Si ha $a\times b=b\times a$ se e solo se …?
5. Siano $\N$ l'insieme dei numeri naturali e $S=\set{1,2,3}$. Siano poi $\alpha$ la relazione binaria in $S$ definita da: $(\forall x,y\in S)(x\mathrel\alpha y\iff x\lt y)$ e $\beta$ la corrispondenza da $S$ ad $\N$ di grafico $\set{2}\times\set{x\in\N\mid x\lt 10}$. Descrivere la corrispondenza prodotto $\alpha\beta$ e la relazione binaria $\alpha^2=\alpha\alpha$.
6. La corrispondenza: $n\in\Z\mapsto n^2/2\in\Z$ è un'applicazione ben definita?
7. 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}$;
8. (neutralità delle applicazioni identiche rispetto alle corrispondenze) Sia $\alpha$ una corrispondenza da un insieme $A$ ad un insieme $B$. Allora $\alpha\id_B=\id_A\alpha=\alpha$.

23/3

Discussione di esercizi dalla lezione precedente (formule infinitarie di De Morgan).

Altri esempi relativi al problema della buona definizione di un'applicazione. Introdotti, per ogni insieme $S$, l'insieme $\P(S)$ delle parti di $S$ e, per ogni $k\in\N$, l'insieme $\P_k(S)$ delle $k$-parti (cioè parti di cardinalità $k$) di $S$.

Restrizioni e prolungamenti, di un'applicazione. L'immersione in un insieme di una sua parte (se $X$ è una parte di un insieme $Y$, l'immersione di $X$ in $Y$, spesso indicata con $X\hookrightarrow Y$, è l'applicazione $x\in X\mapsto x\in Y$, cioè la restrizione ad $X$ di $\id_Y$).

Applicazioni costanti. L'immagine $\im f$ di un'applicazione $f$; applicazioni suriettive. Caratterizzazione della suriettività; sua negazione. Discussione sullo studio della suriettività o meno di un'applicazione; errori frequenti. Ridotta di un'applicazione alla sua immagine.

Applicazioni iniettive; negazione della iniettività. Diversi esempi. Applicazioni biettive. Ogni applicazione il cui dominio ha meno due elementi è iniettiva; ogni applicazione ha un restrizioni iniettive.

La composta di due applicazioni suriettive (risp. iniettive, biettive) è necessariamente suriettiva (risp. iniettiva, biettiva).

Esercizi proposti:

1. Svolgere gli esercizi 3 (escluso il punto f) e 4 da Tautologie, insiemi, aritmetica. (Notazione: $\N^\#=\N^+=\N\setminus\set0$; $2\N$ è l'insieme dei numeri naturali pari).
2. Un'applicazione costante può essere suriettiva?
3. Provare che se $f$ è un'applicazione iniettiva, ogni restrizione di $f$ è iniettiva.
4. Sia $S=\set{a,b,c}$, dove $|S|=3$, e $T=\set{0,1}$. Descrivere tutte le applicazioni da $S$ a $T$ che non siano suriettive.
5. Di ciascuna delle seguenti applicazioni si stabilisca se è suriettiva e se è iniettiva:
   • $n\in\Z\longmapsto |n|+1\in\N$;
   • $\set{a,b,c}\in\P_3(\Z)\longmapsto a+b+c\in\Z$;
   • $\set{a,b,c}\in\P_3(\N)\longmapsto a+b+c\in\N$;
6. Siano $S=\set{1,2}$ e $T=\set{1,2,3}$. Data l'applicazione $f\colon S\to T$ definita da $f(1)=2$ e $f(2)=1$, scrivere tutti prolungamenti di $f$ ad $S$ (suggerimento: sono tre) e decidere quali sono iniettivi e quali sono suriettivi.
7. Data un'applicazione $f\colon A\to B$, se $X$ è un sottoinsieme di $A$ e $\iota$ è l'immersione di $X$ in $A$, verificare che $f\circ\iota$ è la restrizione di $f$ a $X$.

27/3

Teorema: 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 di applicazione identica (quindi biettiva) che si possa scrivere come applicazione composta $g\circ f$, dove $g$ non è iniettiva ed $f$ non è suriettiva.

Sezioni e retrazioni di un'applicazione. Nozione di applicazione inversa. Teorema: un'applicazione è suriettiva se e solo se ha una sezione; è iniettiva se e solo se ha una retrazione oppure ha dominio vuoto; biettiva se e solo se ha un'inversa. Alcuni esempi.

Osservazione: dire che un'applicazione $f$ è una retrazione di un'applicazione $g$ equivale a dire che $g$ è una sezione di $f$; dunque tutte le sezioni sono iniettive e tutte le retrazioni sono suriettive.

Unicità dell'inversa: se un'applicazione $f$ ha sia una retrazione $r$ che una sezione $s$, allora $r=s$, dunque $r$ è inversa di $f$; inoltre, $r$ è l'unica retrazione, l'unica sezione e dunque l'unica inversa di $f$. Teorema: le applicazioni invertibili (cioè dotate di inversa) sono precisamente quelle biettive. Osservazione ulteriore: un'applicazione è biettiva se e solo se ammette una ed una sola sezione.

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$. Diversi esempi; alcune proprietà. Con queste notazioni si ha $\vec f(\vuoto)=\antivecf(\vuoto)=\vuoto$, $\,\vec f(A)=\im f$, $\,\antivecf (B)=\antivecf (\im f)=A$. Una funzione $f\colon A\to B$ è suriettiva se e solo se $\antivecf (\set{b})\ne\vuoto$ per ogni $b\in B$; iniettiva se e solo se $|\antivecf (\set{b})|\le 1$ per ogni $b\in B$.

Discussione generale sulla nozione di invertibilità.

Cenni sulla nozione di equipotenza tra insiemi.

Esercizi proposti:

1. 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.
2. Siano $f\colon n\in\Z\mapsto n^2\in\Z$ e $X=\set{n\in\N\mid n\le 10}$ Calcolare $\vec f(X)$, $\antivecf (X)$, $\antivecf(\vec f(X))$ e $\vec f(\antivecf(X))$.
3. Descrivere tutte le sezioni ed almeno tre retrazioni distinte dell'immersione di $\N$ in $\Z$.
4. Provare che l'applicazione $f\colon n\in\N\longmapsto \begin{cases} n/2,&\text{se $n$ è pari}\\ -(n+1)/2,&\text{se $n$ è dispari}\end{cases}\in\Z$ è biettiva. Qual è l'inversa?
5. Sia $f\colon A\to B$ un'applicazione. Allora:
   1. Per ogni $X\subseteq A$ e $Y\subseteq B$ si ha $X\subseteq\antivecf(\vec f( X))$ e $\vec f(\antivecf(Y))\subseteq Y$, ma, in generale, possono non valere le corrispondenti uguaglianze.
   2. Per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y\cap \im f$.
   3. $f$ è iniettiva se e solo se per ogni $X\subseteq A$ si ha $X=\antivecf (\vec f(X))$ (cioè se e solo se $\antivecf\circ\vec f$ è l'identità di $\P(A)$); $f$ è suriettiva se e solo se per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y$ (cioè se e solo se $\vec f\circ\antivecf$ è l'identità di $\P(A)$).
   4. Per ogni $U,V\subseteq A$, $\vec f(U\cup V)=\vec f(U)\cup\vec f(V)$ e $\vec f(U\cap V)\subseteq \vec f(U)\cap\vec f(V)$, in questo caso l'uguaglianza può non valere.
   5. Per ogni $U, V\subseteq B$, $\antivecf(U\cup V)=\antivecf(U)\cup \antivecf(V)$ e $\antivecf(U\cap V)=\antivecf(U)\cap \antivecf(V)$.
   6. $f$ è iniettiva se e solo se per ogni $U,V\subseteq A$ si ha $\vec f(U\cap V)= \vec f(U)\cap\vec f(V)$.
6. Verificare che le applicazioni immagine e antiimmagine definite da applicazioni identiche sono applicazioni identiche e 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$.
7. Usando l'esercizio precedente e le nozioni di sezione e retrazione provare che, per un'applicazione $f$
   1. sono equivalenti: $f$ è iniettiva; $\vec f$ è iniettiva; $\antivecf$ è suriettiva;
   2. sono equivalenti: $f$ è suriettiva; $\vec f$ è suriettiva; $\antivecf$ è iniettiva;
   3. sono equivalenti: $f$ è biettiva; $\vec f$ è biettiva; $\antivecf$ è biettiva. Inoltre, se queste si verificano, $\vec f$ e $\antivecf$ sono una l'inversa dell'altra.

30/3

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti; fattoriali.

Notazione: $B^A$ e ${}^AB$ come sinonimi di $\Map(A,B)$.

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|>0$ oppure $A=B=\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. L'insieme delle trasformazioni $T(A)=A^A$ e quello $\Sym(A)$ delle permutazioni (cioè: trasformazioni biettive) di un insieme $A$; se $A$ è finito, $|\Sym(A)|=|A|!$.

Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti, con verifica nel caso dell'unione di due o tre insiemi.

Funzione caratteristica $\chi_{A,X}$ di una parte $X$ di un insieme $A$; biezione canonica $X\in\P(S)\mapsto \chi_{A,X}\in\set{0,1}^S$ e sua inversa. Dimostrazione della formula $|\P(A)|=2^{|A|}$ per ogni insieme finito $A$. Rappresentazione (in contesto informatico) di parti di un insieme finito come "stringhe di 0 e 1".

Richiamo: il principio di induzione.

Esercizi proposti:

1. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=7$ e $|B|=10$.
   1. Se $|A\cap B|=2$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=12$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 5$, cosa possiamo dire su $|A\cup B|$?
   4. Indicare il numero delle applicazioni, delle applicazioni iniettive e delle applicazioni suriettive da $A$ a $B$.
   5. Sia $X$ una parte di $A$. Supponiamo che esista un'applicazione suriettiva da $X$ ad $A$. Cosa sappiamo dire su $X$?
   6. Indicare il numero delle applicazioni e quello delle applicazioni iniettive da $\P(A)$ a $\P(A\times B)$
2. Siano $S=\set{0,1,5}$ e $T=\set{1,2}$. Descrivere esplicitamente tutte le applicazioni iniettive da $T$ ad $S$ e le applicazioni suriettive da $S$ a $T$ (suggerimento per la seconda parte: si fa prima a dire quali non sono suriettive). Quante sono?
3. Sia $A=\set{1,2,3,4,5,6}$ e siano $f$ e $g$ applicazioni da $A$ ad $\set{0,1}$ definite da $f(1)=f(2)=f(5)=f(6)=1=g(2)=g(4)=g(5)$ e $f(3)=f(4)=0=g(1)=g(3)=g(6)$. Se $F$ e $G$ sono le parti di $A$ che hanno come funzioni caratteristiche, rispettivamente, $f$ e $g$, scrivere le funzioni caratteristiche di $F\cap G$, $F\cup G$ e $F\ds G$. Viene qualcosa in mente?

30/3

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti; fattoriali.

Notazione: $B^A$ e ${}^AB$ come sinonimi di $\Map(A,B)$.

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|>0$ opure $A=B=\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. L'insieme delle trasformazioni $T(A)=A^A$ e quello $\Sym(A)$ delle permutazioni (cioè: trasformazioni biettive) di un insieme $A$; se $A$ è finito, $|\Sym(A)|=|A|!$.

Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti, con verifica nel caso dell'unione di due o tre insiemi.

Funzione caratteristica $\chi_{A,X}$ di una parte $X$ di un insieme $A$; biezione canonica $X\in\P(S)\mapsto \chi_{A,X}\in\set{0,1}^S$ e sua inversa. Dimostrazione della formula $|\P(A)|=2^{|A|}$ per ogni insieme finito $A$. Rappresentazione (in contesto informatico) di parti di un insieme finito come "stringhe di 0 e 1".

Richiamo: il principio di induzione.

Esercizi proposti:

1. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=7$ e $|B|=10$.
   1. Se $|A\cap B|=2$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=12$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 5$, cosa possiamo dire su $|A\cup B|$?
   4. Indicare il numero delle applicazioni, delle applicazioni iniettive e delle applicazioni suriettive da $A$ a $B$.
   5. Sia $X$ una parte di $A$. Supponiamo che esista un'applicazione suriettiva da $X$ ad $A$. Cosa sappiamo dire su $X$?
   6. Indicare il numero delle applicazioni e quello delle applicazioni iniettive da $\P(A)$ a $\P(A\times B)$
2. Siano $S=\set{0,1,5}$ e $T=\set{1,2}$. Descrivere esplicitamente tutte le applicazioni iniettive da $T$ ad $S$ e le applicazioni suriettive da $S$ a $T$ (suggerimento per la seconda parte: si fa prima a dire quali non sono suriettive). Quante sono?
3. Sia $A=\set{1,2,3,4,5,6}$ e siano $f$ e $g$ applicazioni da $A$ ad $\set{0,1}$ definite da $f(1)=f(2)=f(5)=f(6)=1=g(2)=g(4)=g(5)$ e $f(3)=f(4)=0=g(1)=g(3)=g(6)$. Se $F$ e $G$ sono le parti di $A$ che hanno come funzioni caratteristiche, rispettivamente, $f$ e $g$, scrivere le funzioni caratteristiche di $F\cap G$, $F\cup G$ e $F\ds G$. Viene qualcosa in mente?

3/4

Dimostrazione alternativa (per induzione) di: $(\forall A)(|\P(A)|=2^{|A|})$.

Coefficienti binomiali: buona definizione del coefficiente binomiale $\binom nk$, per ogni $k,n\in\N$, come cardinalità di $\P_k(S)$, per un qualsiasi insieme $S$ di cardinalità $n$. Osservazioni sui casi, banali, in cui $k$ vale 0, 1 o $n$, o è maggiore di $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$ tali che $k\le n$, formula ricorsiva: $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$ e formula chiusa: $\binom nk=n!/(k!(n-k)!)$. Il triangolo di Tartaglia-Pascal.

Questi argomenti sono anche esposti in una nota, Coefficienti Binomiali, il cui stile espositivo, però, non coincide con quello usato a lezione. In particolare, la formula chiusa per i coefficienti binomiali è stata dimostrata in aula per induzione e non come nelle note.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche. Negazione di ciascuna di queste proprietà; loro espressione in termini di proprietà (insiemistiche) del grafico.

Esercizi proposti:

1. Posto $S=\set{0,1,2,3,4}$, elencare gli elementi di $\P_4(S)$ e quelli di $\P_6(S)$.
2. Sia $S$ un insieme di cardinalità 12. Quante sono le parti di $S$ di cardinalità 5? E quante quelle di cardinalità 7? Quante sono le 10-parti di $\P(S)$?
3. Sia $S$ un insieme di cardinalità 5. Le funzioni caratteristiche delle 3-parti di $S$ sono tutte e sole le applicazioni da $S$ a $\set{0,1}$ tali che …? Quante sono?
4. Posto $A=\set{1,2,3,\ldots,7}$ e $B=\set{2,5}$, indicare le cardinalità degli insiemi $L_1:=\set{X\in\P(A)\mid (4\in X)\land(|X|=5)}$ e $L_2:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X)\land(|X|=5)}$.
5. Siano $S$ l'insieme dei primi 90 numeri interi positivi e $T$ una sua parte costituita da 10 elementi. Calcolare la cardinalità dell'insieme delle 5-parti di $S$ e quella dell'insieme delle 5-parti di $T$. Anacleto partecipa ad un gioco: deve scegliere dieci numeri interi compresi tra 1 e 90; tra i novanta numeri ne verranno poi estratti 5 ed Anacleto vince se (e solo se) tutti e cinque i numeri estratti sono tra quelli che lui aveva scelto. Che probabilità ha Anacleto di vincere?

6/4

Relazioni binarie antisimmetriche e transitive. Confronto tra queste proprietà e quelle già definite; negazione di esse, loro espressione in termini di proprietà (insiemistiche) del grafico. Esempi. Un'osservazione su come semplificare la verifica della transitività di una relazione binaria $\rho$ su un insieme $A$: se $x,z\in A$ e $y\in \set{x,z}$, allora l'implicazione $((x\mathrel\rho y)\land(y\mathrel\rho z))\implica x\mathrel\rho z$ è banalmente verificata.

Relazioni di equivalenza, relazioni di ordine largo, relazioni di ordine stretto. Diversi esempi. Notazioni introdotte: $\Eq(S)$, $\OL(S)$, $\OS(S)$, per gli insiemi delle relazioni di equivalenza, di ordine largo, di ordine stretto in un insieme $S$.

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 $A$ per ogni $a,b\in A$ 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\iff [a]_\sim\cap [b]_\sim\ne \vuoto$.

Nucleo di equivalenza di un'applicazione (anche detto equivalenza associata all'applicazione).

Proiezione canonica $a\in A\mapsto [a]_\sim\in A/{\sim}$ definita da una relazione di equivalenza $\sim$ su un insieme $A$. Ogni equivalenza è il nucleo di equivalenza di un'applicazione: ad esempio, della proiezione canonica che essa definisce.

Classi di equivalenza rispetto al nucleo di equivalenza di un'applicazione: se $\sim$ è il nucleo di equivalenza di un'applicazione $f$ di dominio $A$, per ogni $x\in A$ si ha $[x]_\sim=\antivecf(\set{f(x)})$.

Esercizi proposti:

1. Esercizi 1 (esclusi i punti f e g), 2, 3, 4 da relazioni binarie. Terminologia e notazioni: per ‘ordinamento’ si intende una relazione d'ordine stretto o largo; $\N^\#=\N^*=\N^+=\N\setminus\set 0$.
2. Sia $A=\set{1,2,3,4,5,6,7,8}$ e sia $B$ l'insieme degli interi pari appartenenti ad $A$. Detta $f$ l'applicazione $A\to\Z$ definita ponendo $f(a)=16$ se $a\in B$ e $f(a)=(a-3)^2$ se $a\in A\setminus B$, sia $\rho$ il nucleo di equivalenza di $f$. Si descrivano in modo esplicito (elencandone cioè gli elementi) tutte le classi di equivalenza modulo $\rho$ e $A/\rho$. Quanti elementi ha $A/\rho$?
3. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cup \set{1,2,3}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim_f}$, dove $\sim_f$ è il nucleo di equivalenza di $f$? Descriverli esplicitamente.
4. 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|$.
5. Siano $f$ un'applicazione da un insieme $A$ ad un insieme $B$ e $\beta$ una relazione di equivalenza in $B$. Verificare che la relazione binaria $\alpha$ definita in $A$ ponendo, per ogni $x,y\in A$, $x\mathrel\alpha y \iff f(x)\mathrel\beta f(y)$ è di equivalenza.

10/4

L'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in A/{\sim}$ è biettiva (teorema fondamentale di omomorfismo per insiemi), quindi si ha $|A/{\sim}|=|\im f|$. Si consiglia di consultare le note, scritte a questo riguardo, anche se con stile e notazioni non identiche a quelle della lezione. Si legga, in particolare, l'esempio conclusivo.

Partizioni di un insieme. Definizione e prima caratterizzazione: $F$ è una partizione di un insieme $A$ se e solo se $\vuoto\notin F\subseteq \P(A)$ e $(\forall x\in A)(\exists! b\in F)(x\in b)$. Vari esempi; tra questi le partizioni banali di un insieme $A$, cioè $\P_1(A)$ e, se $A\ne\vuoto$, $\set A$. Proiezione di $A$ in una sua partizione $F$: è l'applicazione (suriettiva) $\pi_F\colon A\to F$ che manda ogni $x\in A$ nell'unico $b\in F$ a cui $x$ appartiene.

Per un arbitrario insieme $A$, 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)$; la sua inversa è l'applicazione che ad ogni partizione $F$ di $A$ associa il nucleo di equivalenza della proiezione di $A$ su $F$ (due elementi di $A$ risultano equivalenti se e solo se appartengono allo stesso blocco della partizione $F$). Diversi esempi. Tra questi: corrispondenza tra partizioni ed equivalenze banali; elenco delle relazioni di equivalenza in $\set{1,2,3}$.

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.

Elementi neutri a sinistra e a destra; elementi neutri.

Esercizi proposti:

1. Scrivere cinque partizioni (distinte) di $\Z$.
2. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cup \set{1,2,3}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim_f}$, dove $\sim_f$ è il nucleo di equivalenza di $f$? Dopo aver risposto a questa domanda, descrivere esplicitamente gli elementi di $\P(S)/{\sim_f}$.
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. Contare ed elencare le relazioni di equivalenza nell'insieme $\set{1,2}$.
5. Sia $S$ un insieme e sia $|S|=4$. Calcolare il numero delle partizioni di $S$ ed il numero delle relazioni di equivalenza in $S$.
6. Esercizio 2, punti (i) e (ii), dal compito del 22 giugno 2015.
7. Esercizio 2 dal compito del 5 marzo 2015.
8. 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,5,6}\subseteq [3]_\rho$ e $6\in[7]_\rho$?
9. Esercizio 1 dal compito del 16 luglio 2013.
10. Si considerino le operazioni binarie $*$, $\diamond$, $\circ$ definite in $\Z$ ponendo, per ogni $a,b\in\Z$, $a*b=ab+a+b$, $a\diamond b=a$, $a\circ b=ab+1$. Per ciascuna di esse si stabilisca se è un'operazione associativa, commutativa, se ammette elementi neutri a destra, o a sinistra.

20/4

Unicità degli elementi neutri (se, in una assegnata struttura, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura). Semigruppi e monoidi. Diversi esempi, tra i quali semigruppi con più di un elemento neutro a destra. 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$, quindi $s$ è l'unico simmetrico di $x$, l'unico simmetrico sinistro di $x$ e l'unico simmetrico destro di $x$ in $S$. Interpretazione di queste nozioni nel monoide delle trasformazioni di un insieme: i simmetrici destri e sinistri sono in questo caso le sezioni e le retrazioni. Osservazione banale: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di se stesso.

Osservazione: il monoide delle trasformazioni di un insieme $A$ è commutativo se e solo se $|A|\lt 2$

Elementi simmetrizzabili. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico".

Diversi esercizi sullo studio di un'operazione.

Cenno ai teoremi di associatività e di commutatività.

Parti chiuse (o stabili) in una struttura (rispetto ad una operazione); operazioni indotte. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà.

Esercizi proposti:

1. Dato un insieme $A$, determinare gli elementi simmetrizzabili nei monoidi $(\P(A),\cup,\vuoto)$, $(\P(A),\cap,A)$, $(\P(A),\ds,\vuoto)$.
2. Sia $*$ l'operazione binaria definita in $X:=\Z\times\Z$ da: $(\forall\; a,b,c,d\in\Z) \big((a,b)*(c,d)=(ac,ad)\big)$. Decidere se $(X,*)$ è un semigruppo, se è commutativo, se ammette elementi neutri a sinistra, se ne ammette a destra. Nel caso la richiesta abbia senso, determinare gli elementi simmetrizzabili in $(X,*)$, descrivendone i simmetrici.
3. Stesse domande come all'esercizio precedente, per le operazioni $(a,b)\in\Z\times\Z\mapsto a+b+1\in\Z$ e $(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\setminus Y)\cup\set 1\in\P(\Z)$ al posto di $*$ (suggerimento per la seconda operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).
4. Delle seguenti undici 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 {0,1}$, $\set {-1}$, $\set {0,1,2}$, $\set {1,-1}$, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.

27/4

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

Gruppi; gruppi abeliani. Esempi: i gruppi additivi degli interi, dei razionali, dei reali, corrispondenti gruppi moltiplicativi; il gruppo $(\P(A),\ds)$ per un arbitrario insieme $A$. Sotogruppi e loro caratterizzazione.

Il gruppo degli invertibili (cioè degli elementi simmetrizzabili) di un monoide $M$: è l'insieme $\U(M)$ degli elementi simmetrizzabili in $M$ ed è un sottomonoide di $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}$).

Esempi, i gruppi (moltiplicativi) degli invertibili dei monoidi $(\Z,\cdot)$ e $(\R,\cdot)$ (sono, rispettivamente, dati da $\set{1,-1}$ e $\R\setminus\set 0$), il gruppi simmetrico $\Sym(A)$ su un insieme $A$ (è il gruppo degli invertibili del monoide delle trasformazioni di $A$; i suoi elementi sono le permutazioni di $A$). $\Sym(A)$ è abeliano se e solo se $|A|\le 2$. Alcuni esempi in cui il gruppo degli invertibili è identico (consiste, cioè del solo elemento neutro).

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 nella prima parte di una nota sulla cancellabilità (che contiene più di quanto richiesto ai fini di questo corso). Semigruppi e monoidi (commutativi) cancellativi.

Omomorfismi tra strutture algebriche (per ora, solo nel caso di strutture ad una operazione binaria); 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.

Isomorfismi. L'inversa di ogni isomorfismo è un isomorfismo. 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 o simmetrizzabile, o cancellabile ha la stessa proprietà (e gli isomorfismi conservano gli eventuali neutri e simmetrici).

Altri esempi di isomorfismo: la funzione esponenziale è un isomorfismo da $(\R,+)$ a $(\R^+,\cdot)$ (il gruppo moltiplicativo dei reali positivi); per un arbitrario insieme $A$, l'applicazione $X\mapsto A\setminus X$ è un isomorfismo da $(\P(A),\cap)$ a $(\P(A),\cup)$.

Esercizi proposti:

1. Generalizzando un esempio visto a lezione, provare che, per ogni insieme $A$, l'unico elemento cancellabile in $(\P(A),\cup)$ è $\vuoto$. Quali sono gli elementi cancellabili in $(\P(A),\cap)$?
2. Sia $(S,*)$ un semigruppo. Provare che, per ogni $x,y\in S$ si ha $\lambda_{x*y}=\lambda_x\circ \lambda_y$ (usando le notazioni introdotte a lezione, per ogni $a\in S$ chiamiamo $\lambda_a$ la traslazione sinistra determinata da $a$ in $S$; $\circ$ è l'usuale operazione di composizione tra applicazioni). Dunque: l'applicazione $x\in S\mapsto \lambda_x\in T(S)$ è un omomorfismo da $(S,*)$ al monoide delle trasformazioni di $S$.
3. Determinare il gruppo degli invertibili e l'insieme degli elementi cancellabili del monoide delle parole su un alfabeto.
4. Provare che l'insieme dei numeri razionali positivi è un sottogruppo del gruppo moltiplicativo razionale $(\Q\setminus\set 0,\cdot)$.
5. Sia $A=\set{1,2,3,4,5}$ e sia $H=\set{f\in \Sym (A)\mid f(1)=1}$. Provare che $H$ è un sottogruppo di $\Sym(A)$.
6. Sia $(S,*)$ un semigruppo. Provare che l'insieme degli elementi cancellabili a sinistra in $(S,*)$ è chiuso rispetto a $*$.
7. Sia $*$ l'applicazione $(a,b)\in\Z\times\Z\mapsto ab+a+b\in\Z$ già considerata in precedenti esempi ed esercizi. Verificare che $f\colon n\in(\Z,*)\mapsto n+1\in(\Z,\cdot)$ è un isomorfismo. Dedurne direttamente (senza eseguire nessun altro calcolo) che $(\Z,*)$ è un monoide, con elemento neutro $0$ e due soli elementi invertibili: $0$ e $-2$. Dedurre inoltre che ogni intero diverso da $-1$ è cancellabile in $(\Z,*)$.
8. Esiste un isomorfismo da $(\Z,+)$ a $(\Z,\cdot)$?
9. Sia $f\colon X\to Y$ un'applicazione biettiva. Verificare che l'applicazione $\alpha\in T(X)\mapsto f\circ \alpha \circ f^{-1} \in T(Y)$ è un isomorfismo tra i monoidi delle trasformazioni di $X$ e di $Y$ e che $\alpha\in \Sym(X)\mapsto f\circ \alpha \circ f^{-1} \in \Sym(Y)$ è un isomorfismo tra i due gruppi simmetrici indicati.
10. Siano $A$ e $B$ due insiemi, con $|A|=1$ e $|B|=2$. Provare che i gruppi $(\P(A),\ds)$ e $\Sym(B)$ sono isomorfi. Suggerimento: $\Sym(B)$ ha due elementi: $\id_B$ ed un'altra permutazione, chiamiamola $\sigma$. Verificare che l'applicazione $\P(A)\to \Sym(B)$ definita da $\vuoto\mapsto \id_B$ e $A\mapsto \sigma$ è un isomorfismo.
11. 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 simmetrizzabile in $(S,*)$ allora $f(x)$ è un elemento simmetrizzabile in $(T,\diamond)$, individuando il simmetrico di $f(x)$.
12. Siano $(S,*)$ e $(T,\diamond)$ strutture algebriche ad un'operazione binaria. Supponiamo che $f\colon S\to T$ sia un omomorfismo suriettivo (cioè un epimorfismo) tra di esse. Verificare che se $(S,*)$ ha elemento neutro $u$, allora $f(u)$ è neutro in $(T,\diamond)$; se $*$ è commutativa (oppure associativa), $\diamond$ ha la stessa proprietà.

4/5

Tavole di Cayley (ovvero di moltiplicazione) per operazioni binarie. Visualizzazione di proprietà tramite tavole di Cayley: commutatività, esistenza di neutri e di simmetrici, cancellabilità. Alcuni esempi. Tavole di Cayley e isomorfismi. Tavole di Cayley per gruppi di cardinalità 2, 3 o 4.

Anelli, anelli commutativi, anelli unitari. Esempi, tra cui: $(\Z,+,\cdot)$, $(2\Z,+,\cdot)$ (non unitario), anelli di matrici (come esempi di anelli non commutativi), l'anello delle parti di un insieme.

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$. Alcune regole elementari di calcolo: per ogni $a$, $b$, $c$ in $R$ si scrive $a-b$ per $a+(-b)$ e si ha $a0_R=0_R=0_Ra$, dove $0_R$ è lo zero di $R$, $a(-b)=-(ab)=(-a)b$ e $a(b-c)=ab-ac$ e $(a-b)c=ac-bc$. Corpi e campi. Esempi. Formula del binomio di Newton. Ne è stata data dimostrazione solo per cenni; chi desidera approfondirla può consultare la parte finale (enunciato numero 5) delle note sui coefficienti binomiali.

Legge di annullamento del prodotto e domini di integrità.

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 (senza dimostrazione): 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$. In notazione additiva queste formule diventano, con le stesse quantificazioni, $(n+m)x=nx+mx$ e $(nm)x=m(nx)$. Potenze (o multipli) secondo interi di uno stesso elemento di un semigruppo commutano sempre tra loro. In ogni anello unitario $R$ si ha, per ogni $n\in\Z$ e $a\in R$, $na=(n 1_R)a$. Nozione di periodo di un elemento in un gruppo e di caratteristica di un anello. Alcuni esempi: $\car(\Z)=0$, $\car(\P(A))=2$ per ogni insieme $A$. Se $R$ è un anello unitario di carateristica $c$, si ha $ca=0_R$ per ogni $a\in R$.

Esercizi proposti:

1. Scrivere le tavole di Cayley di $\P(\set{0,1},\cup)$ e $\P(\set{0,1},\ds)$.
2. Provare che se $R$ è un anello unitario e $|R|>1$, $0_R$ non può essere invertibile in $R$. [Suggerimento: se $a$ fosse l'inverso di $0_R$, sia avrebbe $1_R=0_R a =0_R$.]
3. Esercizio 5 da Polinomi e strutture algebriche.
4. Svolgere l'esercizio 9 da Polinomi e strutture algebriche, tralasciando le domande relative alla nozione di ideale e, in generale, tutto ciò che sia riferito a nozioni e notazioni che non abbiamo (ancora) definito.
5. Dimostrare (per induzione) le regole di calcolo per le potenze in semigruppi enunciate a lezione.
6. Trovare un sottoanello di $\Z$ a cui appartenga 3 ma non 2.
7. Siano $S$ un insieme e $T$ un suo sottoinsieme proprio. Verificare che (rispetto, come al solito, alle operazioni $\ds$ e $\cap$), $\P(T)$ è un sottoanello di $\P(S)$ ed è, come $\P(S)$, unitario, ma l'unità di $\P(T)$ non coincide con quella di $\P(S)$.

8/5

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

Se $R$ è un anello unitario e $|R|>1$, lo zero di $R$ non è invertibile (con richiamo alla definizione di corpi e campi; il loro gruppo moltiplicativo).

Partizioni ed equivalenze compatibili con un'operazione binaria. Esempio: in $\Z$ l'equivalenza "avere la stessa parità" è compatibile sia con l'addizione che con la moltiplicazione; l'equivalenza "avere lo stesso segno", definita dichiarando equivalenti due interi se e solo se essi sono o entrambi positivi, o entrambi negativi o entrambi zero, è compatibile con la moltiplicazione ma non con l'addizione. Altro esempio: l'equivalenza "avere la stessa lunghezza" è compatibile con l'operazione binaria (concatenazione) nel monoide delle parole su un alfabeto.

Operazione quoziente (cioè quella indotta sul quoziente determinato da un'equivalenza compatibile con un'operazione binaria). Questa è ben definita se e solo se l'equivalenza è compatibile con l'operazione.

Congruenze in una struttura algebrica. Struttura quoziente ed epimorfismo canonico. 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 (abeliani e non), anelli, anelli unitari sono strutture dello stesso tipo.

Relazione di divisibilità in semigruppi e monoidi commutativi: transitività e (nel caso dei monoidi) riflessività. L'insieme ordinato $(\N,\mid)$.

La relazione $\sim$ ("essere elementi associati") in un monoide commutativo $(M,\cdot)$, definita da: $(\forall a,b\in M)(a\sim b\iff (a|b \land b|a))$. Dunque, $|$ è una relazione d'ordine in $M$ se e solo se $\sim$ è la relazione di uguaglianza. 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 $a\sim b$ se e solo se $\Div(a)=\Div(b)$, ovvero se e solo se $aM=bM$. Da ciò segue che $\sim$ è una relazione di equivalenza. Per ogni $a\in M$ e $u\in \U(M)$, si ha $a\sim au$; se $a$ è cancellabile vale anche il viceversa e dunque $[a]_\sim=a\U(M)$. Esempio: elementi associati in $(\Z,\cdot)$.

Ogni elemento invertibile in un monoide commutativo divide tutti gli elementi del monoide.

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

Equivalenze compatibili a destra o a sinistra con una operazione binaria. Caratterizzazione delle equivalenze compatibili come equivalenze compatibili sia destra che a sinistra.

Le congruenze modulo un intero in $\Z$ (cioè le equivalenze $\equiv_m$ al variare di $m\in\Z$). Verifica diretta del fatto che tutte queste sono congruenze nell'anello $(\Z,+,\cdot)$. Solo a titolo di notizia, è stato detto che queste sono le sole relazioni di equivalenza compatibili con l'addizione in $\Z$.

Esercizi proposti:

1. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
2. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
3. Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è compatibile con $*$.
4. La relazione di equivalenza "avere la stessa parità" è compatibile con l'operazione di elevazione a potenza ($(a,b)\mapsto a^b$) in $\N^\#$? E in $\N$?
5. Per quali interi $m$ la conguenza modulo $m$ è una delle relazioni di equivalenze banali in $\Z$?
6. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z/\equiv_2$ (i cui elementi sono l'insieme degli interi pari e quello degli interi dispari).
7. Verificare che la relazione d'ordine usuale in $\N$ è la relazione di divisibilità nel monoide $(\N,+)$ e che, per un arbitrario insieme $A$, la relazione di inclusione in $\P(A)$ è la relazione di divisibilità nel monoide $(\P(A),\cup)$.

11/5

Osservazioni sulle congruenze in $\Z$: $\equiv_0$ e $\equiv_1$ sono, rispettivamente, la relazione di uguaglianza e quella universale in $\Z$; per ogni $m\in\Z$ si ha ${\equiv_m}={\equiv_{-m}}$.

I quozienti $\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 $i$ e $j$ sono numeri naturali minori di $m$ e $i\equiv_m j$, allora $i=j$), quindi $|\Z_m|=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\lt |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à). Esempio: divisori dello zero in $\Z$, in $\P(S)$ per un insieme $S$, in $\Z_6$.

In ogni struttura algebrica, le intersezioni di parti chiuse sono parti chiuse; parte chiusa generata da una parte.

Esercizi proposti:

1. Calcolare $8\modbin 6$, $-8\modbin 6$, $8\modbin -6$, $-8\modbin -6$.
2. Similmente a quanto fatto in aula per $\Z_6$, si dica di ciascun elemento di $\Z_8$ se è o meno un divisore dello zero, se è o meno invertibile. (Suggerimento: calcolare i quadrati delle classi di 3 e di 5.)
3. Eseguendo solo facilissimi calcoli a mente, si calcoli $\rest(2^{15},7)$ e $\rest(2^{16},7)$. (Suggerimento: partire da $\rest(2^3,7)$.)
4. Senza eseguire calcoli, si trovi $\rest(93\cdot 901,9)$.

12/5

Ancora sulla parte chiusa generata da una parte in una struttura; alcuni esempi. Sottomonoidi e sottogruppi generati. Sottosemigruppi, sottomonoidi e sottogruppi generati da singleton; gruppi ciclici. Esempio: $(\Z,+)$ e, per ogni $m\in\N^+$, $(\Z_m,+)$ sono gruppi ciclici. A titolo di notizia: ogni gruppo ciclico è isomorfo ad uno di questi. Osservazione: per ogni intero positivo $m$, si ha $m=\car (\Z_m)$.

Approfondimenti sulla periodicità: se $x$ è un elemento di un gruppo (moltiplicativo) $G$, $x$ è periodico se e solo se l'applicazione $n\in\Z\mapsto x^n\in G$ non è iniettiva. Di conseguenza: in un gruppo finito tutti gli elementi sono periodici. Se $x$ è periodico di periodo $m$ allora, per ogni $a,b\in\Z$, si ha $x^a=x^b\iff a\equiv_m b$. In particolare, $x^a=x^{a\,\modbin\,n}$, e $x^a=1_G$ se e solo se $m$ divide $a$.

Calcoli in aritmetica modulare; diversi esempi. Come applicazione: criteri di divisibilità di numeri naturali per 2, 4, 5, 3, 9, 11. Osservazione: due interi congrui modulo un intero $m$ sono congrui anche modulo ciascun divisore di $m$.

Principio di induzione: prima e seconda forma (o induzione completa), con dimostrazione (a partire dal buon ordinamento dei naturali).

Divisori banali di un elemento ed elementi irriducibili in un monoide commutativo. Interpretazione di queste nozioni in $(\N,\cdot)$ e $(\Z,\cdot)$. Numeri interi primi.

Teorema fondamentale dell'aritmetica (prima parte): ogni intero maggiore di $1$ è prodotto di primi.

Esercizi proposti:

1. Sia $x$ un elemento periodico, di periodo $m$, in un gruppo moltiplicativo $G$. Identificare il nucleo di equivalenza dell'applicazione $n\in\Z\mapsto x^n\in G$.
2. Nella stessa situazione dell'esercizio precedente, verificare che l'inverso di $x$ è $x^{m-1}$.
3. Sempre nella stessa situazione, il sottogruppo generato da $x$ ha esattamente $m$ elementi. (Suggerimento: questo sottogruppo è l'insieme delle potenze di $x$; dal momento che, per ogni $a,b\in\Z$, $x^a=x^b$ se e solo se $a\equiv_m b$, il numero di queste potenze è uguale a quello delle classi di resto modulo $m$. A ben guardare, questo ragionamento si può sintetizzare come un'applicazione del primo degli esercizi di questa lezione unitamente al teorema di omomorfismo per insiemi.)
4. Nel gruppo $(\P(\N),\ds)$, trovare il sottogruppo generato da $A$ e quello generato da $B$, dove $A=\set{\set 1}$ e $B=\set{\set 0,\set 1}$.
5. Trovare il sottomonoide di $(\P(\N),\cup)$ generato da $\P_1(\N)$, facendo attenzione a non cadere nella trappola.
6. Dando per noto che $[7]_{25}$ sia invertibile nell'anello $\Z_{25}$, calcolarne il periodo nel gruppo degli invertibili di $\Z_{25}$. Calcolare poi $\rest(7^{987897979676856478},25)$ e l'inverso di $[7]_{25}$.
7. Esercizio 12 da Tautologie, insiemi, aritmetica.
8. Che giorno (delle settimana) è $3^{500}$ giorni dopo una domenica (se nel frattempo non viene riformato il calendario)?
9. Calcolare $\rest(786761!,1111)$.

15/5

Invito tutti gli studenti alla compilazione dei questionari sulla valutazione della didattica

Fattorizzazioni "essenzialmente uguali" (cioè uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati) in monoidi. Monoidi cancellativi e monoidi fattoriali. Interpretazione di queste nozioni nei casi di $(\N^*,\cdot)$ e $(\Z^*,\cdot)$, dove $\Z^*=\Z\setminus\vuoto$.

Descrizione dell'insieme dei divisori di un elemento in un monoide fattoriale $M$ a partire da una sua fattorizzazione in irriducibili: se $a\in M$ e $a=up_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una sua decomposizione primaria (dunque, $u$ è invertibile e 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 $v p_1^{b_1} p_2^{b_2}\cdots p_n^{b_n}$, dove $v$ è un invertibile e ciascuno degli esponenti $b_i$ è un numero intero positivo minore o uguale ad $a_i$.

Massimi comuni divisori (MCD) e minimi comuni multipli (mcm) in semigruppi commutativi. Se $d$ è un MCD di una parte $X$ di un monoide commutativo $M$, i MDC di $X$ in $M$ sono tutti e soli gli elementi di $M$ associati ad $X$. Analogo enunciato per i mcm.

Esistenza ed espressione di un MCD $d$ e di un mcm $m$ tra due elementi $a$ e $b$ di un monoide fattoriale. Osservazione: $ab$ e $md$ risultano associati.

L'algoritmo euclideo delle divisioni successive per la determinazione di un massimo comun divisore tra due interi.

Qualche idea per la velocizzazione dell'algoritmo euclideo.

Estensione dell'algoritmo euclideo e Teorema di Bézout, nella forma: se $a,b\in\Z$ e $d$ è un massimo comun divisore tra $a$ e $b$, allora $d$ è una combinazione lineare di $a$ e $b$ a coefficienti in $\Z$. La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo.

Lemma di Euclide: siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$.

Per questi argomenti si possono consultare le note sull'Algoritmo euclideo ed altre note disponibili nel sito docenti della Professoressa Leone.

Esercizi proposti:

1. Provare che $(\N,+)$ è un monoide fattoriale, con $1$ come unico elemento irriducibile.
2. Alcuni esempi di monoidi commutativi e cancellativi non fattoriali:
   • Sia $\Q_{\ge0}$ l'insieme dei numeri razionali positivi. Allora $(\Q_{\ge0},+)$ è un monoide commutativo cancellativo il cui unico elemento simmetrizzabile è quello neutro (cioè $0$) e che non ha elementi irriducibili. Quindi, in questo monoide quasi tutti gli elementi sono non simmetrizzabili, ma nessuno di essi è prodotto di irriducibili. Dunque, $(\Q_{\ge0},+)$ non è fattoriale.
   • Sia $M=\set 1\cup 2\N^*$, il sottomonoide di $(\N^*, \cdot)$ costituito da $1$ e dagli interi positivi pari. Verificare che, in $(M,\cdot)$, $2$, $6$ e $18$ sono irriducibili e non associati tra loro, quindi $36$ ha due fattorizzazioni essenzialmente distinte come prodotto di irriducibili: $2\cdot 18=6\cdot 6$. Anche questo monoide (che è commutativo e cancellativo) non è fattoriale.
3. Determinare quali e quanti sono i divisori in $(\N,\cdot)$ ed in $(\Z,\cdot)$ di $120$ e di $7^{12}13^{8}19^{15}$.
4. Esercizi da 5 a 8 da Tautologie, insiemi, aritmetica (notazione: $\N^\#=\N^*$.)
5. Se possibile, trovare una coppia $(u,v)$ di interi tali che $1=49 u+ 120 v$
6. Se possibile, trovare una coppia $(u,v)$ di interi tali che $1=48 u+ 120 v$

18/5

Rinnovo l'invito alla compilazione dei questionari sulla valutazione della didattica

Conseguenze del Lemma di Euclide: se un numero intero primo $p$ divide un prodotto $q_1 q_2\cdots q_s$ di interi primi, allora è associato ad uno dei fattori $q_i$. Completamento della dimostrazione del Teorema Fondamentale dell'Aritmetica (essenziale unicità delle fattorizzazioni degli interi in prodotti numeri primi). Anelli fattoriali. $\Z$ è un anello fattoriale.

Equazioni diofantee (di primo grado a due incognite) ed altre formulazioni del teorema di Bézout: se $a,b\in\Z$ e $d$ è un MCD tra $a$ e $b$,

• l'insieme delle combinazioni lineari di $a$ e $b$ in $\Z$ coincide con $d\Z$;
• $a$ e $b$ sono coprimi se e solo se esistono interi $u$ e $v$ tali che $1=au+bv$;
• per ogni $c\in\Z$, l'equazione diofantea $ax+by=c$ ha soluzioni (intere) se e solo $d$ divide $c$.

Metodo di risoluzione di equazioni diofantee (del tipo appena descritto).

Equazioni congruenziali (di primo grado, ad una incognita). L'equazione congruenziale $ax\equiv_m b$ (in $\Z$) è un modo per esprimere l'equazione $[a]_m X= [b]_m$ in $\Z_m$. 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 (del tipo considerato). Di conseguenza: determinazione degli elementi invertibili nei quozienti di $\Z$.

Algoritmo per la risoluzione delle equazioni congruenziali. Equazioni congruenziali ridotte. L'insieme di tutte le soluzioni di un'equazione congruenziale. Metodi per la semplificazione delle equazioni congruenziali: se $a,b\in\Z$ e $m\in\N^*$,

• se $a'\in[a]_m$ e $b'\in[b]_m$, le equazioni congruenziali $ax\equiv_m b$ e $a'x\equiv_m b'$ hanno le stesse soluzioni;
• per ogni $k\in\Z\setminus \set 0$, $a|b$ se e solo se $ak|bk$. Di conseguenza, le equazioni congruenziali $ax\equiv_m b$ e $akx\equiv_{mk} bk$ hanno le stesse soluzioni;
• se $\ell$ è un intero coprimo con $m$, le equazioni congruenziali $ax\equiv_m b$ e $a\ell x\equiv_{m} b\ell$ hanno le stesse soluzioni.

Qualche esempio.

Gli elementi non invertibili nei quozienti propri di $\Z$ sono tutti divisori dello zero. Per un intero $m>1$ sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità; (3) $m$ è primo.

Per questi argomenti si possono consultare le note sull'Algoritmo euclideo ed altre note disponibili nel sito docenti della Professoressa Leone.

Esercizi proposti:

1. Esercizi da 9 a 11 da Tautologie, insiemi, aritmetica.
2. Di ciascuno degli elementi di $\Z_{20}$ si stabilisca se è invertibile e, nel caso, si trovi l'inverso.
3. Siano $m=2^5 3^8 19$ e $a:=3^4 7^2 19^3$. Sapendo che $1897a\equiv_ m 1539$, si descriva l'insieme di tutte le soluzioni dell'equazione congruenziale $ax \equiv_m 1539$.
4. Si determini l'insieme di tutte le soluzioni dell'equazione congruenziale $12x\equiv_{34} 6$ e, quindi l'insieme di tutte le soluzioni dell'equazione diofantea $12x+34y=6$.
5. Si determinino tutti gli interi $u$ tali che $20(u-1)\equiv_{28}4(u-2)$ e tutti gli interi $v$ tali che $20(v-1)\equiv_{28}4v-2$
6. In $\Z_{48}$ si determini, ove possibile, l'inverso di $[7]_{48}$, $[9]_{48}$, $[11]_{48}$, $[-13]_{48}$, $[47]_{48}$. Capire perché c'è davvero bisogno di far calcoli in una sola occasione.

22/5

Rinnovo l'invito alla compilazione dei questionari sulla valutazione della didattica

Considerazioni sui numeri primi. Per verificare che un intero $n\gt 1$ sia primo basta verificare che non sia divisibile per alcun primo minore o uguale alla sua radice quadrata.

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario.

Terminologia essenziale: successione dei coefficienti di un polinomio, polinomi costanti, grado e coefficiente direttore di un polinomio, polinomi monici.

Proprietà universale per gli anelli dei polinomi (come dalle note). Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata); l'omomorfismo di sostituzione; per ogni intero $m\ne 0$, l'epimorfismo da $\Z[x]$ a $\Z_m[x]$, indotto dall'epimorfismo canonico $\Z\epi \Z_m$, che ad ogni polinomio $f$ associa "$f$ stesso riguardato modulo $m$".

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

Grado di somma, differenza e 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)$ e $\cd(fg)=\cd(f)\cd(g)$.

$A[x]$ è un dominio di integrità se e solo se lo è $A$; se questo accade vale sempre, in $A[x]$, la regola di addizione dei gradi e $\U(A[x])=\U(A)$. Esempi che mostrano come queste due proprietà possano non valere se $A$ non è integro.

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. È sicuramente possibile effettuare la divisione se $A$ è un campo e $g\ne 0$.

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

Esercizi proposti:

1. Sia $A$ un anello commutativo unitario. Verificare che l'anello dei polinomi $A[x]$ è infinito (Suggerimento: se $n$ e $m$ sono numeri naturali distinti, si può avere $x^n=x^m$?), Fornire un esempio di anello infinito di caratteristica 3.
2. Vero o falso: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.
3. Per ogni intero $n>1$ si consideri il polinomio $f_n=\overline{30}x^5+\overline{10}x^3+\overline{3}x^2+ \overline{6}\in\Z_n[x]$. Stabilire per quali $n$ il grado di $f_n$ è $5$ e trovare il grado $f_n$ nei casi rimanenti.
4. Dividere, in ciascuno degli anelli $\Q[x]$ e $\Z_5[x]$ il polinomio $2x^4+1$ per $3x+2$ (nel secondo caso, ovviamente, i polinomi vanno riguardati come polinomi a coefficienti in $\Z_5[x]$).
5. Svogere, almeno in parte, gli esercizi nr. 1 e nr. 2 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo.
6. Provare che, qualunque sia l'anello commutativo $A$ ed $f$ un polinomio monico in $A[x]$, $f$ è cancellabile ma non invertibile in $\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.

25/5

Ancora una volta: invito alla compilazione dei questionari sulla valutazione della didattica

Applicazione polinomiale definita da un polinomio. Radici di un polinomio.

Teorema del resto: e Teorema di Ruffini: se $A$ è un anello commutativo unitario, $f\in A[x]$ e $c\in A$, allora il resto nella divisione di $f$ per $x-c$ è $f(c)$. Come conseguenza, $c$ è radice di $f$ se e solo se $x-c$ divide $f$.

Teorema di Ruffini generalizzato e sue e conseguenze. Se $A$ è dominio di integrità unitario si ha: (1) se $0_A\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 tutti risultati non valgono per anelli commutativi unitari arbitrari (mai per anelli finiti).

Teorema (non dimostrato): se $A$ è un anello fattoriale, anche $A[x]$ è un anello fattoriale. Associati in $A[x]$, con particolare riferimento al caso in cui $A$ sia un campo: in questo caso, ogni classe di polinomi associati non nulli ha uno ed un solo rappresentante monico; di conseguenza ogni $f\in A[x]\setminus A$ si fattorizza come prodotto di un invertibile (il suo coefficiente direttore) e polinomi irriducibili monici, in modo unico a meno dell'ordine dei fattori.

Cenni a metodi di fattorizzazione. Caratterizzazione dei polinomi irriducibili su un campo $K[x]$; esistenza di radici ed irriducibilità. Descrizione dei polinomi irriducibili sul campo reale e sul campo complesso; Polinomi in $\Q[x]$. Ciascuno di essi ha un associato in $\Z[x]$.Criterio di irriducibilità di Eisenstein. Per ogni $n\in\N^*$ ed ogni primo $p$, $x^n+p$ è irriducibile in $\Q[x]$. Radici razionali di un polinomio $f\in\Z[x]$; se $f$ è monico tali radici sono intere.

Determinazione dei polinomi irriducibili di grado al più 4 in $\Z_2[x]$.

Esercizi proposti:

1. Dal fatto che i polinomi irriducibili in $\R[x]$ hanno grado uno o due, dedurre che ogni polinomio di grado dispari in $\R[x]$ ha sempre radici in $\R$.
2. 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 \lt 100$.
3. Per ogni $n\in\N^*$, sia $f_n=(100+4n)x^4+(n+8)x^3+nx^2+1$ e sia $\bar {f_n}\in \Z_{11}[x]$ il polinomio $f_n$ riguardato come polinomio a coefficienti in $\Z_{11}[x]$. Sia $L=\{n\in\N^* \mid \nu \bar {f_n}=2\}$. Decidere se $L=\vuoto$ o $L\ne\vuoto$; nel secondo caso, posto $m=\min L$, scrivere l'associato monico di $\bar {f_m}$ in $\Z_{11}[x]$. Ripetere l'esercizio dopo aver ridefinito $f_n$ come $(100+4n)x^4+(n-8)x^3+nx^2+1$.
4. Svogere l'esercizio nr. 3 da Polinomi e strutture algebriche.
5. Tra i seguenti polinomi, dire quali sono e quali non sono irriducibili in $\Q[x]$ e quali sono e quali non sono irriducibili in $\R[x]$: $x^3+1$, $x^2+1$, $(10x^2+11)(x^2+2)$, $27x^8+100x^7+15$, $x^{896}-4^{896}$. Riguardati i polinomi precedenti a coefficienti in $\Z_5[x]$, dire quali sono irriducibili in $\Z_5[x]$.
6. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
7. I testi delle prove scritte contengono un gran numero di esercizi sui polinomi. Si guardino, ad esempio, gli esercizi 4 dal compito di gennaio 2015, 5 dal compito di ottobre 2016, 4 dal compito di maggio 2016, 4 dal compito di giugno 2016, 5 dal compito di ottobre 2016, 5 dal compito di gennaio 2017.
8. Si trovino, in $\Z_5[x]$, tutti i polinomi monici irriducibili di secondo grado e tutti i polinomi di quarto grado che siano riducibili ma privi di radici. Quanti sono?

29/5

Ogni polinomio di grado dispari in $\R[x]$ ha radici in $\R$.

Anelli booleani. Proprietà: sono commutativi e, escluso l'anello con un solo elemento, hanno caratteristica 2. Enunciato del teorema di Stone e sua conseguenza: la cardinalità di un anello booleano è necessariamente una potenza di 2.

Insiemi ordinati. Biezione canonica tra gli insiemi delle relazioni di ordine stretto e quello delle relazioni di ordine largo in un fissato insieme (senza dimostrazione; si vedano gli esercizi). Elementi tra loro confrontabili in insiemi ordinati; ordinamenti totali (relazioni di ordine totale), insiemi totalmente ordinati.

Ordinamenti duali e principio di dualità per insiemi ordinati.

Ordinamento indotto su un sottoinsieme di un insieme ordinato. Applicazioni crescenti ed isomorfismi tra insiemi ordinati.

Minimi e massimi in insiemi ordinati; elementi minimali e massimali. Esempi. Se $a$ è minimo (risp. massimo) in un insieme ordinato $(S,\le)$, $a$ è l'unico elemento minimale (risp. massimale) in $(S,\le)$. Esempio di un insieme ordinato privo di minimo e di massimo in cui, però, esiste un elemento che è, allo stesso tempo, l'unico elemento minimale e l'unico elemento massimale. In ogni insieme ordinato finito non vuoto, esistono elementi minimali ed elementi massimali. Solo a titolo di notizia (ma tra gli esercizi): se un insieme ordinato finito ha un unico elemento minimale, questo è in minimo dell'insieme.

Intervalli (aperti e chiusi) in un insieme ordinato; relazione di copertura definita da una relazione d'ordine. Nel caso finito, essa determina l'ordinamento (ma questo non è vero nel caso degli insiemi infiniti). Diagrammi di Hasse. Esempi; visualizzazione di proprietà di insiemi ordinati sui loro diagrammi di Hasse. Vari esempi. Due insiemi ordinati finiti sono isomorfi se e solo se si possono rappresentare con lo stesso diagramma di Hasse.

Minoranti e maggioranti di un sottoinsieme in un insieme ordinato. Esempi.

Esercizi proposti:

1. Provare, come conseguenza del teorema di Stone, che due anelli booleani finiti con lo stesso numero di elementi sono necessariamente isomorfi.
2. Verificare quanto segue, solo enunuciato a lezione: dato un insieme $A$
   • se $\rho$ è una relazione d'ordine largo in $A$, la relazione $\rho_{\ne}$, definita da: ($\forall x,y\in A)(x\mathrel {\rho_{\ne}}y\iff (x\mathrel\rho y\, \land\, x\ne y))$) è una relazione d'ordine stretto in $A$;
   • se $\sigma$ è una relazione d'ordine stretto in $A$, la relazione $\underline\sigma$, definita da: ($\forall x,y\in A)(x\mathrel {\underline\sigma}y\iff (x\mathrel \sigma y \,\lor\, x=y))$) è una relazione d'ordine largo in $A$.
   • Indicati con $\OL(A)$ e $\OS(A)$, nell'ordine, gli insiemi delle relazioni di ordine largo e di ordine stretto in $A$, le applicazioni $\rho\in\OL(A)\mapsto \rho_{\ne}\in\OS(A)$ e $\sigma\in\OS(A)\mapsto \underline\sigma\in\OL(A)$ sono l'una inversa dell'altra, quindi biettive.
3. Sia $S$ un insieme ordinato e sia $x$ un suo elemento minimale. Allora $x$ è minimo in $S$ se e solo se è $x$ è minimale in $S$ ed è confrontabile con ogni elemento di $S$.
4. Sia $(S,\le)$ un insieme ordinato finito e supponiamo che $x$ sia il suo unico elemento minimale. Provare che $x=\min(S,\le)$ ragionando in modo che segue. Sia $X$ l'insieme degli elementi di $S$ non confrontabili con $x$. Se $X\ne \vuoto$, allora $X$ ha un elemento minimale $y$. Allora $y$ non è minimale in $S$ (perché $y\ne x$), dunque esiste $z\in S$ tale che $z\lt y$.Ora, $z\notin X$, altrimenti sarebbe contraddetta la minimalità di $y$ in $X$). Dunque $z$ è confrontabile con $x$. Dedurne $x\le z$ e, da ciò, $x \lt y$. Ma questo contraddice $y\in X$. Questa contraddizione mostra che $X=\vuoto$. Usando l'esercizio precedente, si ricava $x=\min(S,\le)$.
5. Sia $\Pf(\N)$ l'insieme delle parti finite di $\Z$. In $(\Pf(\N),\subseteq)$, determinare gli eventuali elementi minimali, massimali, minimo, massimo. Determinare i minoranti ed i maggioranti di $\Pf(\N)$ in $(\P(\N),\subseteq)$.
6. Per ciascuno dei seguenti insiemi, ordinati per divisibilità, disegnare il diagramma di Hasse e descrivere gli eventuali minimi, massimi, elementi minimali, elementi massimali: $\Div (18)$ (l'insieme dei naturali divisori di $18$), $\Div(64)$, $\Div(30)$, $\set{n\in\N\mid n\lt 10}$, $\set{2,3,4,8,18,100}$.
7. Siano $A$ e $B$ due parti dell'insieme ordinato $S$. Provare che se $M_A$ e $M_B$ sono gli insiemi dei minoranti di $A$ e di $B$,d allora l'insieme dei minoranti di $A\cup B$ è $M_A\cap M_B$. Provare anche che
   • se $A$ ha minimo $a$, allora $M_A$ è l'insieme dei minoranti di $\set a$;
   • se $a\in M_A\cap A$, allora $a=\min A$.
8. Sia $X=\set{\set{1,2}, \set{1,4,5}}$. Descrivere l'insieme dei minoranti e quello dei maggioranti di $X$ in $(\P(\N),\subseteq)$.
9. Generalizzando l'esercizio precedente, per ogni insieme $S$ ed ogni parte $X$ di $\P(S)$, descrivere l'insieme dei minoranti e quello dei maggioranti di $X$ in $(\P(S),\subseteq)$.

1/6

Se $X$ è una parte di un insieme ordinato $S$, dire che un elemento $a$ di $S$ è il minimo di $X$ equivale a dire che $a$ è un minorante di $X$ appartenente a $X$.

Data un'applicazione $f\colon A\to B$, e una relazione di ordine largo $\le$ in $B$, la relazione binaria $\alpha$ in $A$ definita da $(\forall x,y\in A)(x\mathrel\alpha y\iff (f(x)\lt f(y)\lor x=y))$ è di ordine largo. Alcuni esempi; descrizione degli elementi minimali e massimali in $(A,\alpha)$ (costituiscono, rispettivamente, l'antiimagine mediante $f$ dell'insieme degli elementi minimali e di quello degli elementi massimali in $(\im f,\le)$). Se $f$ non è iniettiva, la relazione binaria $\tau$ definita in $A$ da $(\forall x,y\in A)(x\mathrel\tau y\iff f(x)\le f(y))$ non è d'ordine.

Estremo inferiore ed estremo superiore di una parte $X$ di un insieme ordinato $S$ in $S$. Diversi esempi. In particolare: gli 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. Osservazioni (valgono ovviamente anche gli enunciati duali): l'estremo inferiore di $S$ in $S$ è (l'eventuale) minimo di $S$; se $a=\inf_S X$ allora i minoranti di $X$ in $S$ sono precisamente gli elementi minori o uguali ad $a$; se $X$ ha minimo allora questo è anche l'estremo inferiore di $X$ in $S$.

Reticoli. Definizione ed esempi. Il duale di un reticolo è necessariamente un reticolo; principio di dualità per reticoli. Sono reticoli tutti gli insiemi totalmente ordinati; per ogni insieme $S$, $(\P(S),\subseteq)$ ed $(\N,\mid)$. Questi ultimi due sono reticoli completi (cioè reticoli in cui ogni sottoinsieme ha estremo inferiore ed estremo superiore). Un elemento minimale (risp. massimale) in un reticolo è necessariamente minimo (risp. massimo). Di conseguenza i reticoli finiti sono limitati, ciè hanno minimo e massimo, ma questo non è sempre vero per reticoli infiniti.

Siano $(S,\sigma)$ un insieme ordinato e $A, B\subseteq S$. Supponiamo che esistano $a=\inf_{(S,\sigma)} A$ e $b=\inf_{(S,\sigma)}B$. Allora i minoranti di $A\cup B$ sono precisamente i minoranti di $\set{a,b}$; esiste $\inf_{(S,\sigma)}(A\cup B)$ se e solo se esiste $\inf_{(S,\sigma)}(\set{a,b})$ e, nel caso esistano, questi estremi inferiori coincidono. Enunciato duale per gli estremi superiori. Conseguenza: in un reticolo, ogni sottoinsieme finito non vuoto ha estremo inferiore ed estremo superiore (abbiamo così una seconda dimostrazione del fatto che i reticoli finiti sono limitati).

Le due operazioni (binarie) reticolari (meet/inf/$\land$ e join/sup/$\lor$).

Proprietà algebriche delle operazioni reticolari (commutatività, associatività, leggi di assorbimento, iteratività). 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 tramite biezioni canoniche. Esempio particolarmente significativo: per un insieme $S$, le strutture $(S,\subseteq)$ e $(S,\cap,\cup)$.

Sottoreticoli. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

Esercizi proposti:

1. Date un'applicazione $f\colon A\to B$ ed una relazione di ordine stretto $\rho$ in $B$, provare che la relazione binaria $\tau$ in $A$ definita da $(\forall x,y\in A)(x\mathrel\tau y\iff f(x)\mathrel\rho f(y))$ è di ordine stretto. Qual è la relazione di ordine largo ad essa corrispondente?
2. Sia $S=\set{2^{3n-1}\mid n\in\N}$. Determinare, in $(\N,\mid)$, l'insieme dei minoranti e l'insieme dei maggioranti di $S$ e, se esistono, $\inf S$ e $\sup S$.
3. Si consideri la relazione d'ordine $\preceq$ definita su $\P(\Z)$ dalla relazione di inclusione in $\P(\Z)$ e dall'applicazione $g\colon X\in\P(Z)\mapsto X\cap\N\in\P(\Z)$, vale a dire, quella definita da: $(\forall X,Y\in\P(Z))(X\preceq Y\iff X=Y \lor g(X)\subset g(Y))$. Trovare gli (eventuali) elementi minimali e massimali in $(\P(\Z),\preceq)$ e i minoranti in $(\P(\Z),\preceq)$ di $T:=\set{A,B,C}$, dove $A=\set{n\in\Z\mid n^2\lt 10}$, $B=\set{3^n\mid n\in\N}$, $C=[11]_{10}$. Se esistono, trovare $\inf_{(\P(\Z),\preceq)}(T)$ e $\sup_{(\P(\Z),\preceq)}(T)$. $(\P(\Z),\preceq)$ è un reticolo? Trovare due sottoinsiemi si $\P(\Z)$ di cardinalità 4 che, rispetto all'ordinamento indotto da $\preceq$, siano reticoli, ma non siano isomorfi tra loro. $(\P(\Z),\preceq)$ ha un sottoinsieme infinito totalmente ordinato?
4. Dei seguenti insiemi, ordinati per divisibilità in $\N$, dire quali sono sottoreticoli di $(\N,\mid)$ e quali sono reticoli. Disegnare i diagrammi di Hasse di quelli finiti: $\set{1,2,3,6}$, $\set{0,1,2,3}$, $\N^*$, $\N^*\setminus\set{1}$, $\set{0,1,2,3,12,18}$.
5. Provare che se $a$ e $b$ sono due elementi di un reticolo $(L,\le)$ e $a\le b$, allora l'intervallo chiuso di estremi $a$ e $b$ è un sottoreticolo di $L$. Provare anche che $\set{x\in L \mid x\le a}$ e $\set{x\in L \mid a\le x}$ sono sottoreticoli.

5/6

Minimi e massimi in reticoli come elementi neutri rispetto alle operazioni reticolari.

Complementi di elementi in reticoli limitati. Esempi di elementi privi di complemento, con un solo complemento, con più complementi. In ogni reticolo limitato, il minimo ha il massimo come unico complemento e viceversa. Reticoli complementati. Sia in $(\N,\mid)$ che in un arbitrario reticolo totalmente ordinato e limitato, nessun elemento diverso da minimo e massimo ha complemento.

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 reticoli distributivi sono distributivi.

Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff. Esempi di uso (corretto e non) del criterio di Birkhoff.

Reticoli booleani. Algebre di Boole. Equivalenza tra queste due nozioni. Leggi di De Morgan in algebre di Boole; l'operazione unaria di complemento è involutoria. Sottoalgebre di Boole. Enunciato del teorema di Stone per reticoli booleani e per algebre di Boole, e sue conseguenze: i reticoli booleani finiti hanno per cardinalità una potenza di 2; due reticoli booleani finiti equipotenti sono necessariamente isomorfi.

Costruzione di un reticolo booleano a partire da un anello booleano. Construzione, inversa, di un'anello booleano a partire da un reticolo booleano (questa seconda costruzione è stata mostrata, ma non ne è stata verificata la correttezza).

Richiamo sulle funzioni caratteristiche. Cenni alla costruzione dell'anello $R^n$ delle $n$-ple di elementi di $R$ a partire da un anello $R$ e da un intero positivo $n$; quest'anello è booleano se $R$ è booleano e si può anche descrivere come anello costituito dalle applicazioni da $S=\set{1,2,\dots,n}$ a $R$. Identificazione delle "stringhe di zeri e uno" di fissata lunghezza $n$ con gli elementi dell'anello $\Z_2^n$ delle applicazioni da $S$ a $\Z_2$. L'applicazione che ad ogni parte di $S$ associa la sua funzione caratteristica è un isomorfismo di anelli (booleani) da $\P(S)$ a $\Z_2^n$. Interpretazione delle operazioni 'bit a bit' alla luce di questo isomorfismo.

Sono in rete delle nuove note sulle strutture booleane, in cui sono discussi (anche) i contenuti di questa lezione.

Esercizi proposti:

1. Costruire un esempio di reticolo complementato con un sottoreticolo non complementato. Suggerimento: cercare una catena nel reticolo delle parti di un insieme.
2. Costruire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi e tutti gli altri elementi hanno esattamente un complemento.
3. Svolgere l'esercizio 3 dal compito del 18 marzo 2014.
4. Svolgere gli esercizi da 5 a 8 da relazioni binarie.
5. Scrivere esplicitamente un isomorfismo tra il reticolo dei divisori di 30 (ordinato per divisibilità) e quello delle parti di un insieme di cardinalità 3.
6. Di due reticoli booleani $L$ e $M$ sappiamo che hanno entrambi cardinalità compresa tra 400 e 900. Che conclusioni possiamo trarre? Possiamo, in particolare, stabilire se $L$ e $M$ sono isomorfi?
7. Di un reticolo $L$ sappiamo che è complementato e che ha esattamente 675 elementi. possiamo stabilire se è distributivo?
8. Verificare in dettaglio che, come detto ma non dimostrato a lezione, se $(R,+,\cdot)$ è un anello booleano e $(R,\land,\lor,1,0,{}')$ è la struttura di algebra di Boole definita su di esso, nel modo canonico, una parte di $R$ è un sottoanello unitario di $(R,+,\cdot)$ se e solo se è una sottoalgebra booleana di $(R,\land,\lor,1,0,{}')$.
9. Sia $R$ l'insieme delle parti $X$ di $\N$ tali che o $X$ o $\N\setminus X$ sia finito. Dimostrare che $R$ è un sottoanello unitario dell'anello delle parti di $\N$, e quindi un anello booleano. Questo esempio è di particolare interesse perché si può dimostrare (ma non si chiede qui di farlo) che $R$ non è isomorfo all'insieme delle parti di $S$ per alcun insieme $S$.

8/6

Ulteriore (e ultimo) invito alla compilazione dei questionari sulla valutazione della didattica

Principio di dualità per reticoli distributivi, complementati, booleani.

Cenni informali alle diverse nozioni di grafo. Definizione di grafo semplice (sia in termini di lati, o archi, che in termini di relazione di adiacenza; equivalenza tra le due definizioni). Rappresentazione grafica. Definizione di multigrafo. Terminologia: estremi di un lato, incidenza, grado, vertici (o nodi) isolati. Grafi completi, grafo complementare di un grafo.

Isomorfismi tra grafi (o tra multigrafi); proprietà che questi conservano. Esempi di grafi isomorfi e non, tecniche di costruzione di isomorfismi. Elenco, a meno di isomorfismi, dei grafi su al più quattro vertici. Sottografi.

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

Teorema: il doppio del numero dei lati di un multigrafo finito (senza cappi) è 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. 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 grafo finito $G=(V,L)$ è 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 $G$ ha esattamente $|V|-|L|$ componenti connesse. In generale, il numero delle componenti connesse in un grafo finito è sempre maggiore o uguale a $|V|-|L|$; in particolare, se il grafo è 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) connessi su cinque vertici. Indentificare tra questi gli alberi.
3. Utilizzando la rappresentazione radicale di un albero, provare che le foreste finite sono grafi planari.
4. Si considerino i grafi $G=(V,L)$ che verificano la proprietà $\Phi$: “$|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 $\Phi$, quali sono i gradi dei suoi vertici?
   2. Disegnare, se possibile, un grafo che verifichi $\Phi$.
   3. Disegnare, se possibile, due grafi tra loro non isomorfi che verifichino $\Phi$.
   4. Disegnare, se possibile, un grafo non connesso che verifichi $\Phi$.
   5. Disegnare, a meno di isomorfismi, tutti i grafi che verificano $\Phi$.