24/9

La prima parte delle lezione è stata dedicata ad informazioni generali sul corso, sul corso di laurea e sui servizi a disposizione degli studenti. Sono stati presentati contenuto e finalità del corso, modalità di svolgimento e materiali didattici.

Introduzione molto informale alle nozioni di linguaggio, formula, proposizione (o formula chiusa, sintassi e semantica. Comparazione tra linguaggio (semi)formalizzato e linguaggio non formalizzato.

Alcuni connettivi proposizionali (introdotti e descritti solo semanticamente): negazione, congiunzione, disgiunzione inclusiva, disgiunzione esclusiva (XOR), congiunzione negata (NAND).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.

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

Esercizi proposti:

1. Scrivere tavole di verità per le forme proposizionali $p\land p$, $p\land(p\lor q)$, $p\lor(p\land q)$, $\lnot (p\lor q)$, $(\lnot p)\lor q $.

26/9

Discussione degli esercizi dalla lezione precedente.

Forme proposizionali; forme logicamente equivalenti tra loro. Connettivo di equivalenza (o bicondizionale). Tautologie e contraddizioni. Diverse tautologie, tra le quali quelle di commutatività dei connettivi $\land$, $\lor$, $\xor$, $\iff$; di associatività di $\land$, $\lor$, $\iff$; di idempotenza per $\land$, $\lor$; distributività tra $\land$ e $\lor$; tautologia della doppia negazione, principio di non contraddizione e principio del terzo escluso.

Connettivo di implicazione (o condizionale). Discussione sul suo utilizzo (e sugli errori più comuni nei quali sia cade) e sulle espressioni verbali che da cui è reso nel linguaggio corrente e nel linguaggio matematico. Due tautologie: implicazione come disgiunzione e tautologia delle doppia implicazione.

Questi materiali sono contenuti in Logica rudimentale.

Esercizi proposti:

1. Svolgere l'esercizio C.1, l'esercizio B.4 ed almeno alcuni dei rimanenti esercizi B e C da Logica rudimentale.
2. La forma proposizionale $(p\iff p)\iff p$ è una tautologia, una contraddizione oppure una forma contingente (cioè né una tautologia né una contraddizione)? 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. La forma proposizionale $\bigl(q\iff r\bigr)\iff \bigl((p\land q)\iff(p\land r)\bigr)$ è una tautologia?

28/9

Discussione di vari esercizi dalla lezione precedente. Esempi di traduzione dal linguaggio ordinario a quello (semi)formalizzato e viceversa.

Altre tautologie sull'implicazione: transitività e legge di contrapposizione. Comparazione tra diversi modi di provare ch una data forma proposizionale sia una tautologia.

Tautologie sulla negazione: leggi di De Morgan, negazione di una implicazione, disgiunzione esclusiva come negazione del bicondizionale. Esempi, anche nel linguaggio ordinario, ed esercizi.

Alcune tautologia sulla disgiunzione esclusiva ($\xor$): associatività, distributività della congiunzione rispetto a $\xor$.

Interdipendenza tra i connettivi proposizionali: basta uno tra NAND e NOR per descriverli tutti.

Introduzione alla logica dei predicati. Variabili, quantificatori universale ed esistenziale: sintassi essenziale ed interpretazione. Occorrenze libere o vincolate di variabili; sostituzioni di termini a variabili. Formule chiuse.

Anche i materiali discussi in questa lezione sono contenuti in Logica rudimentale e, in parte, nelle altre note già segnalate.

Avviso: dall'area materiale didattico del mio sito web docenti si accede alle registrazioni delle prime due lezioni del corso; le successive seguiranno. Si ricorda che l'accesso a questo nuovo servizio sperimentale è limitato agli studenti iscritti al corso ed è inteso solo per uso strettamente personale.

Esercizi proposti:

1. Abbiamo provato la distributività di $\land$ rispetto a $\xor$. Decidere se anche $\lor$ è distibutivo rispetto a $\xor$. In altri termini: confrontare tra loro le forme proposizionali $p\lor (q\xor r)$ e $(p\lor q)\xor (p\lor r)$ e decidere se sono logicamente equivalenti.
2. Svolgere quanti più è possibile tra gli esercizi D, E, F da Logica rudimentale (suggerisco in particolare gli esercizi in D) e leggere l'osservazione G.3, sostanzialmente già fatta a lezione.
3. Verificare (alcune tra) le tautologie in esempi di tautologie.
4. 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$”?
5. Vero o falso? $10=10^2 \implica \log_3 5\lt 0$.
6. Negare: “Se domani nevica e l'aereo è puntuale, o andremo a mare oppure 33 è un numero primo”.
7. Negare la forma proposizionale $(p\land q)\implica (r\lor s)$.

1/10

Discussione di esercizi dalla lezione precedente.

Predicati. Formule valide. Quantificatori ristretti e loro interpretazione. Esempi, tra cui: formule universali o esistenziali ristrette ad una condizione sempre falsa.

Alcune altre regole della logica dei predicati. Frasi contenenti più quantificatori; comparazione tra formule del tipo $\forall x(\exists y(\dots))$ e del tipo $\exists y(\forall x(\dots))$. Negazione di formule universali e di formule esistenziali (anche nel caso dei quantificatori ristretti).

Il quantificatore $\exists!$, descritto dall'equivalenza $(\exists!x(\psi(x)))\iff(\exists x(\forall y(\psi(y)\iff x=y)))$ per ogni formula $\psi$ (si veda quanto in Logica rudimentale, in particolare l'osservazione G.3).

Nozione informale di insieme. Il simbolo '$\in$' di appartenenza. Assioma di estensionalità e qualche sua conseguenza (irrilevanza dell'ordine in cui sono elencati gli elementi di un insieme e delle ripetizioni in questi elenchi). Insieme vuoto e sua unicità.

Sarà utile per la prossima lezione, oltre a quanto già segnalato, Tautologie e identità insiemistiche.

Esercizi proposti:

1. Svolgere quanti più è possibile tra gli esercizi H di Logica rudimentale.
2. Vero o falso?: $(\forall x\in\vuoto)(x\ne x)$.
3. Negare: Ogni cavallo bianco mangia carote.
4. Negare: Ogni mese mi arriva la bolletta del gas e la pago.
5. Negare la formula: $\exists x (\forall y (\phi(x,y)))\implica \forall x (\exists y (\psi(x,y)))$.
6. Assegnati in qualche modo gli oggetti $a,b,c$, si può dire quanti elementi ha l'insieme $\set{a,b,c}$ i cui elementi sono (tutti e soli) $a$, $b$ e $c$?

3/10

Discussione approfondita di esercizi dalla lezione precedente.

Definizione di inclusione e di inclusione stretta. Comparazione tra inclusione e appartenenza; è importante distinguere bene tra queste due nozioni, così come tra un insieme $x$ ed il suo singleton $\set x$; ad esempio tra $\vuoto$ e $\set\vuoto$.

Discussione su diversi esempi: per ogni $x$ si ha $\vuoto\subseteq x$ e $x\subseteq x$, ma $x\notin x$.

L'insieme $\P(x)$ delle parti di un insieme $x$, Tra i suoi elementi ci sono sicuramente $\vuoto$ e $x$. Esempi: $\P(\vuoto)$, $\P(\set 1)$ e $\P(\set{1,2})$.

Estensione di un predicato unario e cenni a problemi fondazionali. L'antinomia di Russell. Presentazione informale degli assiomi di separazione.

Vari esempi ed esercizi sulla descrizione di insiemi.

Sarà utile per la prossima lezione, oltre a quanto già segnalato, Tautologie e identità insiemistiche. Questa volta è vero.

Esercizi proposti:

1. Esercizio I.4 da Logica rudimentale.
2. Decidere se e esistono e, nel caso, descrivere esplicitamente gli insiemi $\set{x\mid \forall y (x= y)}$, $\set{x\mid \forall y (x\ne y)}$, $\set{x\mid \exists y (x= y)}$, $\set{x\mid \exists y (x\ne y)}$, $\set{x\mid \forall y (y\subseteq x)}$, $\set{x\mid x=\set{0,1,2}}$, $\set{y\mid y=\set{0,1,2}}$, $\set{x\mid x=\set{0,1,2,x}}$.
3. Sia $x=\set{\set{\set{\set\vuoto}}}$. Quanti elementi ha $x$? Quante parti ha $x$?
4. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto\subset\vuoto$; $\vuoto\in\P(\vuoto)$; $\vuoto\subseteq\P(\vuoto)$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{2,1,3}$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{4,2,1,3}$.
5. Elencare gli elementi di $\P(\set{0,1,2})$.

5/10

Discussione molto approfondita degli esercizi dalla lezione precedente sul linguaggio insiemistico.

Comparazione tra i connettivi di equivalenza e implicazione, da una parte, e le relazioni di uguaglianza e inclusione tra insiemi dall'altra. Alcune operazioni insiemistiche (unione ed intersezione binarie, complemento in un fissato insieme, differenza insiemistica (detta anche complemento relativo) e loro proprietà, ricavate a partire da tautologie. (come nella sezione finale di Logica rudimentale, e in Tautologie e identità insiemistiche). Abbiamo, tra l'altro discusso le formule di idempotenza, commutatività e associatività per le operazioni di unione e intersezione binarie, ed inoltre formule che coinvolgono la differenza insiemistica, tra cui le formule insiemistiche di De Morgan.

Diagrammi di Euler-Venn; alcuni esempi; diagrammi generici. Utilizzando diagrammi di Euler-Venn generici è possibile dimostrare formule insiemistiche.

Esercizi proposti:

1. $\N\in\P(\Z)$?
2. Descrivere esplicitamente gli insiemi $\set{x\mid \forall y (x\cap y=\vuoto)}$, $\set{x\mid \exists y (x\cup y=\vuoto)}$, $\set{x\mid \forall y (x\cup y=\vuoto)}$.
3. Svolgere gli esercizi J3, J5 e J6 di Logica rudimentale.
4. Verificare tutte le tautologie e le formule in Tautologie e identità insiemistiche che non abbiamo già verificato a lezione.
5. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
6. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\setminus(b\setminus c)$ e $(a\setminus b)\setminus c$. Decidere se è vera o falsa la proposizione: $(\forall a,b,c) (a\setminus(b\setminus c)=(a\setminus b)\setminus c)$.
   Ripetere l'esercizio per $a\cap(b\setminus c)$ e $(a\cap b)\setminus c$.
7. Per ogni $a,b$ si ponga $a\ds b=\set{x\mid (x\in a)\xor(x\in b)}$. Rappresentare in diagrammi di Euler-Venn (generici) $a\ds b$ e $(a\ds b)\ds c$.
8. Dimostrare che per ogni $a,b$ sono equivalenti tra loro: (1): $a\subseteq b$; (2): $a\cap b=a$; (3): $a\cup b=b$.

8/10

Discussione approfondita degli esercizi dalla lezione precedente. L'operazione insiemistica $\ds$ di differenza simmetrica e alcune sue proprietà principali: commutatività, associatività, distributività dell'intersezione rispetto alla differenza simmetrica; per ogni insieme $a$ si ha $a\ds a=\vuoto$ e $a\ds\vuoto=a$.

Operazione di unione unaria. Definizione e numerosi esempi. Riduzione dell'unione binaria ad una unione unaria: $\forall a,b(a\cup b=\bigcup\set{a,b})$.

Esercizi proposti:

1. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\cap(b\ds c)$ e $a\cup(b\ds c)$, confrontandoli tra loro e con $(a\cap b)\ds(a\cap c)$ e $(a\cup b)\ds(a\cup c)$.
2. Siano $a$ e $b$ due insiemi. Supposto $a\subseteq b$, descrivere $a\ds b$.
3. Siano $A=\set{n\in\N\mid 3\le n\le 10}$, $B$ l'insieme dei numeri naturali pari, $C=\set{1,2,8,13,1234}$. Descrivere, elencandone gli elementi, $A\setminus B$, $A\ds C$, $B\cap C$, $B\ds (B\setminus C)$,
4. Calcolare $\bigcup A$ in ciascuno dei seguenti casi: (1) $A=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $A$ è l'insieme delle parti finite di $\N$; (3) $A$ è l'insieme delle parti infinite di $\N$; (4) $A=\set{x\subseteq\N\mid 13\notin x}$; (5) $A=\set{x\subseteq\N\mid 13\in x}$; (6) $A=\big\{\set{124,n}\mid n\in\N\big\}$; (7) $A=\set{[n-1,n+1]\mid n\in\N}$, dove, si ricorda, per ogni coppia $a,b$ di numeri reali, $[a,b]=\set{x\in\R\mid a\le x\le b}$ è l'insieme dei numeri reali compresi tra $a$ e $b$.

10/10

Discussione di alcuni degli esercizi dalla lezione precedente.

L'operazione di intersezione unaria (per insiemi non vuoti). Definizione ed esempi. Riduzione dell'intersezione binaria ad una intersezione unaria. Formule di De Morgan per unione ed intersezioni unarie; formule di distributività generalizzata: per ogni $S$ ed $A$, $S\cap \bigcup A=\bigcup_{a\in A}(S\cap a)$ e, se $A\ne \vuoto$, $S\cup \bigcap A=\bigcap_{a\in A}(S\cup a)$.

Coppie ordinate. Prodotto cartesiano tra due insiemi. Alcuni esempi. $\forall a,b (a\times b=\vuoto\iff (a=\vuoto \lor b=\vuoto))$. Terne ordinate.

Corrispondenze tra due insiemi; diversi modi per rappresentarle (diagrammi, tabelle). Grafico di una corrispondenza. Relazioni binarie in un insieme. Applicazioni (o funzioni) tra due insiemi. Notazioni: per insiemi $A$ e $B$, $\Corr(A,B)$, $\Map(A,B)$, $\Rel(A)=\Corr(A,A)$ indicano, nell'ordine, gli insiemi delle corrispondenze e quello delle delle applicazioni da $A$ a $B$, e l'insieme delle relazioni binarie in $A$.

Qualche esempio di applicazione e di corrispondenza che non è un'applicazione. Applicazioni costanti. Per un'applicazione $\alpha$: dominio e codominio di $\alpha$; immagine $\alpha(a)$ di un elemento $a$ del dominio di $\alpha$, immagine $\im\alpha=\set{\alpha(a)\mid a\in A}$ dell'applicazione $\alpha$. Applicazioni suriettive.

Esercizi proposti:

1. Scrivere in dettaglio le dimostrazioni della formula di De Morgan non verificata a lezione in modo completo: per ogni $S$ e per ogni $A\ne\vuoto$, $S\setminus \bigcup A=\bigcap_{a\in A} (S\setminus a)$. Fare lo stesso per le formule di distributività generalizzata.
2. (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ò dunque 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).
3. Vero o falso? (1): $(\set{0}\times\N)\cup (\set{1}\times\N)=\set{0,1}\times\N$; (2): $(\N\times\N)\cup ((\Z\setminus \N)\times(\Z\setminus \N))=\Z\times\Z$.
4. Siano $a$ e $b$ due insiemi. Si ha $a\times b=b\times a$ se e solo se …?
5. 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}$;
6. Sappiamo che esiste un'applicazione suriettiva e costante da $\N$ ad un certo insieme $A$. Cosa possiamo dire su $A$?

15/10

Discussione di alcuni degli esercizi dalla lezione precedente.

Operazioni binarie (ovunque definite) in un insieme. Definizione ed esempi. Tavola di Cayley di un'operazione binaria.

Operazioni commutative ed associative; cenni ai teoremi di associatività e di commutatività. Nozione di struttura algebrica; semigruppi. Diversi esempi ed esercizi.

Operazione opposta di una operazione binaria e dualità destra/sinistra.

Elementi neutri a sinistra e a destra; elementi neutri. 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$ è neutro, inoltre $s$ è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura.

Esempi e controesempi ad illustrazione di quest'ultimo teorema.

Esercizi proposti:

1. Vero o falso? Per ogni insieme non vuoto $S$ ed ogni operazione binaria $*$ in $S$, …
   1. … in $S$ esiste sempre un elemento neutro a destra o un elemento neutro a sinistra;
   2. … se $*$ è commutativa tutti gli elementi neutri a destra in $(S,*)$ sono anche neutri a sinistra;
   3. … se $*$ è commutativa in $S$ esiste al massimo un elemento neutro a sinistra;
   4. … se $a$ e $b$ sono due elementi neutri a sinistra distinti in $(S,*)$, in $(S,*)$ non esistono elementi neutri a destra.
2. Dato l'insieme $A=\set{0,1}$, scrivere le tavole di Cayley di $(\P(A),\cup)$ e di $(\P(A),\ds)$.
3. Verificare che, come detto a lezione, per ogni insieme $S$ le operazioni $*$ e $\bullet$ definite in $S$ ponendo $a*b=a$ e $a\bullet b=b$ per ogni $a,b\in S$ sono associative.
4. Studiare le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, e determinando gli elementi neutri a sinistra, a destra, neutri delle strutture da esse definite:
   • $\alpha\colon (a,b)\in \N\times\N\mapsto a10^b\in\N$;
   • $\beta\colon (a,b)\in \Z\times\Z\mapsto -ab\in\Z$;
   • $\gamma\colon (a,b)\in \Q\times\Q\mapsto (a+b)/2\in\Q$;
   • $\delta\colon (a,b)\in \Z\times\Z\mapsto 2ab\in\Z$;
   • $\varepsilon\colon (a,b)\in \Q\times\Q\mapsto 2ab\in\Q$;
   • $\zeta\colon (a,b)\in \Z\times\Z\mapsto a+b+2\in\Z$;
   • $\eta\colon (a,b)\in \N\times\N\mapsto a(b^{a+b}+3ab^2)+1\in\N$;
   • $\theta\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto (a\cap\N)\cup b\in\P(\Z)$;
   • $\iota\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto a\cup b\cup \set 1\in\P(\Z)$;
5. Ripetere l'esercizio precedente per l'operazione $*$ definita in $\set{0,1,2,3}$ da questa tavola di Cayley:

   	0	1	2	3
   0	1	1	0	1
   1	1	1	1	1
   2	1	1	2	1
   3	1	1	3	1

   Suggerimento: per ogni scelta di $a,b,c\in S$ si calcolino $a*(b*c)$ e $(a*b)*c$ considerando separatamente i casi $c=2$ e $c\ne 2$.

17/10

Discussione di molti degli esercizi dalla lezione precedente, con illustrazione di alcune tecniche per lo studio delle applicazioni binarie.

Monoidi. Diversi esempi, tra i quali il monoide delle parole su un alfabeto come esempio di monoide non commutativo.

Simmetrici destri e sinistri; simmetrici. Unicità dei simmetrici nei monoidi: se, per un elemento $a$ 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 $a$, l'unico simmetrico sinistro di $a$ e l'unico simmetrico destro di $a$ in $S$. Osservazione banale: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di sé stesso. Elementi simmetrizzabili. Esempio: determinazione degli elementi simmetrizzabili del monoide $(\Z,\cdot)$ e del monoide delle parole. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico".

Gruppi e gruppi abeliani. Vari esempi, tra questi il gruppo $(\P(A),\ds)$ per un arbitrario insieme $A$.

Esercizi proposti:

1. Determinare gli elementi simmetrizzabili nel monoide $(\R,\cdot,1)$ e, per un arbitrario insieme $A$, nei monoidi $(\P(A),\cup,\vuoto)$ e $(\P(A),\cap,A)$. Farlo anche per le strutture dotate di elemento neutro definite dalle operazioni presentate nell'esercizio 4 della lezione scorsa. Alcune di queste strutture sono gruppi?
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 $*$ è associativa, se è commutativa, 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. Che tipo di struttura (semigruppo, monoide, gruppo, commutativo o no?) è $(X,*)$?
3. Stesse domande come all'esercizio precedente, per le operazioni
   • $\varphi\colon(a,b)\in\Z\times\Z\mapsto a+b-1\in\Z$
   • $\psi\colon(a,b)\in\Z\times\Z\mapsto ab+1\in\Z$
   • $\mu\colon((a,b),(c,d))\in(\Z\times\Z)\times(\Z\times\Z) \mapsto (a+bc,bd)\in\Z\times\Z$
   • $\tau\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\cup Y)\cap\N\in\P(\Z)$
   • $\omega\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto(X\setminus Y)\cup\set 1\in\P(\Z)$
   al posto di $*$ (suggerimento per l'ultima operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).
4. Sia $S=\set{a,x,y}$ un insieme di tre elementi e si consideri in $S$ l'operazione $*$ definita in $S$ da questa tavola di Cayley:

   	$a$	$x$	$y$
   $a$	$a$	$x$	$y$
   $x$	$x$	$a$	$a$
   $y$	$y$	$y$	$a$

   Dopo aver verificato che $a$ è neutro in $(S,*)$ e aver determinato i simmetrici destri e sinistri degli elementi di $S$, senza fare ulteriori calcoli si decida se $(S,*,a)$ è un monoide.
5. Verificare che se $*$ è un'operazione associativa, anche la sua operazione opposta è associativa.

19/10

Discussione di diversi esercizi dalla lezione precedente (studio di proprietà di operazioni binarie).

Parti chiuse (o stabili) in una struttura (rispetto ad una operazione binaria); operazioni indotte e strutture indotte. Molti esempi. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà, mentre è possibile che non conservino elementi neutri o simmetrici.

Esercizi proposti:

1. Delle seguenti tredici 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}$, l'insieme degli interi pari, l'insieme degli interi dispari dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
2. Nel monoide delle parole su un alfabeto che contenga la lettera y, dire se sono o non sono parti chiuse: l'insieme delle parole di lunghezza (nel senso ovvio) maggiore di 55; l'insieme delle parole di lunghezza pari; l'insieme delle parole che iniziano per y; l'insieme delle parole che finiscono per yyy; l'insieme delle parole in cui y appare al massimo tre volte; l'insieme delle parole che se hanno lunghezza maggiore di 10 allora non hanno y tra le lettere che vi appaiono.
3. In $D:=\Z\times\Z$ si definiscano le operazioni binarie $*$ e $\bullet$ ponendo, per ogni $a,b,c,d\in\Z$, $(a,b)*(c,d)=(ac,b+d)$ e $(a,b)\bullet(c,d)=(ac,b-d)$. Studiare $(D,*)$ e $(D,\bullet)$, decidendo che genere di strutture algebriche siano, (semigruppi, monoidi, gruppi, commutative o meno) e, nel caso la domanda abbia senso, quali siano i loro elementi simmetrizzabili. Stabilire poi se $\Z\times \set 0$ e $\Z\times\set{1}$ sono o non sono parti chiuse rispetto a $*$ o rispetto a $\bullet$ e studiare, ove esistano, le corrispondenti strutture indotte.
4. Altri esercizi su argomenti trattati finora nel corso e su argomenti che incontreremo presto sono in una raccolta preparata lo scorso anno per le vacanze di pasqua.

22/10

Discussione di diversi esercizi dalla lezione precedente.

Nozione di sottomonoide e relativi esempi. Il gruppo degli invertibili $\U(M)$ (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}$).

Diversi esempi: i gruppi degli invertibili dei monoidi $(\Z,\cdot)$ e $(\R,\cdot)$ (sono, rispettivamente, dati da $\set{1,-1}$ e $\R\setminus\set 0$); quelli di $(\P(A),\cap)$ e $(\P(A),\cup)$ e del monoide delle parole su un alfabeto sono gruppi identici (cioè coincidono con il singleton del loro elemento neutro). $\U(M)=M$ se $M$ è un gruppo.

Il problema della 'buona definizione' di un'applicazione, con diversi esempi ed esercizi.

Prodotto relazionale tra corrispondenze: definizione ed esempi.

Esercizi proposti:

1. Quali tra queste sono applicazioni ben definite? Qui $P$ è l'insieme delle parti non vuote di $\Z$
   • $n\in\Z\mapsto n^2/2\in\Z$;
   • $X\in P\mapsto \min X\in\Z$;
   • $X\in P\mapsto \Z\setminus X\in P$;
   • $X\in \P(\Z)\mapsto X\cap\N\in\P(\N)$;
   • $X\in \P(\Z)\mapsto X\ds\N\in\P(\N)$;
   Tra le corrispondenze elencate nell'esercizo 7 di quelli per le vacanze di pasqua, quali sono applicazioni?
2. 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$.

24/10

Discussione di diversi esercizi dalla lezione precedente, con richiami sui contenuti della stessa lezione.

Proprietà di associatività per il prodotto relazionale. L'applicazione identica in un insieme e sua proprietà di neutralità rispetto al prodotto relazionale. Il monoide delle relazioni binarie in un insieme.

Il prodotto relazionale tra due applicazioni componibili è sempre un'applicazione. Composizione (prodotto operativo) tra applicazioni; sua descrizione esplicita. Notazione: $\beta\circ\alpha:=\alpha\beta$ se $\alpha$ e $\beta$ sono applicazioni. Cenno alle varie notazioni per l'immagine di un elemento mediante un'applicazione. Esempi di calcolo di applicazioni composte. Tra questi: composizione (a destra o a sinistra) con applicazioni costanti. Il monoide delle trasformazioni di un insieme $S$ (lo indichiamo con $T(S)$; è un sottomonoide del monoide delle relazioni binarie in $S$). Se $|S|=2$, $T(S)$ non è commutativo.

Esercizi proposti:

1. Per un arbitrario insieme $A$, sia $k$ l'applicazione $x\in\P(A)\mapsto A\setminus x\in\P(A)$. Calcolare $k\circ k$.
2. Svolgere l'esercizio 8 da quelli per le vacanze di pasqua
3. Sia $S=\set{0,1}$. Elencare gli elementi di $T(S)$ (sono in tutto 4) e scrivere la tavola di Cayley di $T(S)$.
4. Sia $S$ un insieme. Dimostrare che $T(S)$ è commutativo se e solo se $|S|\lt 2$.
5. Nel monoide $T(\Z)$ delle trasformazioni di $\Z$, dire quali tra queste parti sono chiuse: $\set{f\in T(\Z)\mid f(1)=1}$, $\set{f\in T(\Z)\mid f(1)=0}$, $\set{f\in T(\Z)\mid \im f\subseteq\N}$, $\set{f\in T(\Z)\mid \im f\not\subseteq\N}$.

26/10

Discussione molto approfondita degli esercizi dalla lezione precedente. Sia $(S,*)$ una struttura algebrica con un'operazione binaria in cui esista elemento neutro, allora da una tavola di Cayley per $*$ si legge facilmente quali elementi sono simmetrizzabili a destra o a sinistra e quali sono i loro simmetrici destri o sinistri.

Restrizioni di applicazioni; prolungamenti. Immersione $x\in T\mapsto x\in A$ di una parte $T$ di un insieme $A$ in $A$, essa è la restrizione a $T$ dell'applicazione identica di $A$. Componendola con un'applicazione $f\colon A\to B$ si ottiene la restrizione $f_{|T}$ di $f$ a $T$.

Applicazione immagine $\vecf\colon\P(A)\to\P(B)$ ed applicazione antiimmagine $\avecf\colon\P(B)\to\P(A)$ definite da un'applicazione $f\colon A\to B$. Esempi. Si ha: $\vecf (\vuoto)=\avecf(\vuoto)=\vuoto$, $\vecf(A)=\im f$, $\,\avecf (B)=A$ e, per ogni $X\sseq A$, $\vecf(X)=\im f_{|X}$ e $X\sseq\avecf(\vecf (X))$ (questa inclusione può essere stretta).

Esercizi proposti:

1. Siano $A=\set{1,2}$ e $B=\set{1,2,3}$. Scrivere due diversi prolungamenti a $B$ dell'immersione di $A$ in $B$ (si richiedono, in altri termini, due applicazioni $B\to B$ che abbiano l'immersione di $A$ in $B$ come restrizione).
2. Sia $f\colon x\in\P(\Z)\mapsto x\cup\N\in\P(\Z)$. Descrivere $\vecf(\P(\N))$.
3. Sia $+\colon (a,b)\in\N\times\N\mapsto a+b\in\N$ la consueta operazione di addizione in $\N$. Calcolare l'antiimmagine di $\set{1,2}$ mediante $+$.
4. Siano $f\colon n\in\Z\mapsto n^2\in\Z$ e $X=\set{n\in\N\mid n\le 10}$. Calcolare $\vecf(X)$, $\avecf (X)$, $\avecf(\vecf(X))$ e $\vecf(\avecf(X))$.
5. Dimostrare che se $f\colon A\to B$ è un'applicazione si ha $\avecf(\vecf(A))=A$ e
   1. per ogni $Y\sseq B$, $\;\vecf(\avecf(Y))=Y\cap \im f\sseq Y$;
   2. per ogni $X,Y\sseq A$ si ha $\;X\sseq Y\implica \vecf(X)\sseq\vecf(Y)$;
   3. per ogni $X,Y\sseq B$ si ha $\;X\sseq Y\implica \avecf(X)\sseq\avecf(Y)$;

29/10

Discussione molto approfondita di vari esercizi dalla lezione precedente. Dalla discussione è emerso il fatto che se $f$ è un'applicazione suriettiva, per ogni parte $X$ del codominio di $f$ si ha $\vecf(\avecf(X))=X$.

Caratterizzazioni della suriettività. Tra queste, un'applicazione $f\colon A\to B$ è suriettiva (cioè: $\im f=B$) se e solo se (1): per ogni $y\in B$ esiste $x\in A$ tale che $f(x)=y$, o anche se e solo se (2): per ogni $y\in B$ si ha $\avecf(\set y)\ne\vuoto$.

Diversi esempi ed esercizi, con discussione sui possibili errori e accorata preghiera di non duplicarli. Ridotte di un'applicazione.

Se $f\colon A\to B$ e $g\colon B\to C$ sono applicazioni componibili, si ha:

• se $f$ e $g$ sono entrambe suriettive $g\circ f$ è suriettiva;
• se $g\circ f$ è suriettiva, allora $g$ è suriettiva.

(a proposito della seconda affermazione abbiamo visto con un esempio che è possibile che $g\circ f$ sia suriettiva ma $f$ non lo sia). Dunque, nel monoide $T(A)$ delle trasformazioni di un insieme $A$ le applicazioni suriettive costituscono un sottomonoide.

Sezioni di un'applicazione $f\colon A\to B$ (cioè applicazioni $h\colon B\to A$ tali che $f\circ h=\id_B$). Teorema: un'applicazione è suriettiva se e solo se ammette sezioni. Esempi. Dunque: nel monoide $T(A)$ delle trasformazioni di un insieme $A$ le applicazioni suriettive sono precisamente quelle invertibili a destra.

Esercizi proposti:

1. Tra queste applicazioni, decidere quali sono suriettive e descrivere, per esse, almeno una sezione e, se possibile, due:
   • la consueta operazione di addizione $+\colon\Z\times\Z\to\Z$ in $\Z$.
   • $\alpha\colon n\in\Z\mapsto |n|+1\in\N^*$
   • $\beta\colon n\in\N\mapsto \begin{cases} 44&\text{se }n=0\\ n-1&\text{se }n\ne0\end{cases}\in\N$;
   • $\gamma\colon n\in\N\mapsto \begin{cases} n/2&\text{se $n$ è pari}\\ n&\text{se $n$ è dispari}\end{cases}\in\N$;
   • $\delta\colon x\in\P(\Z)\mapsto \N\setminus x\in\P(\Z)$;
   • $\varepsilon\colon x\in A\mapsto 4-x\in A$, qui $A=\set{1,2,3}$;
   • $\zeta\colon\N^*\to\N^*$ che ad ogni numero intero positivo associa il numero delle sue cifre nella consueta rappresentazione del numero in base 10 (ad esempio $\zeta(7)=1$, $\zeta(35)=2$, $\zeta(7777)=4$);
2. Ispirandosi all'esercizio precedente, trovare in $T(\N^*)$ un elemento con infiniti simmetrici a destra. Questo elemento ha simmetrici a sinistra?
3. Siano $f\colon A\to B$ e $g\colon B\to C$ applicazioni componibili. Verificare che $\im (g\circ f)\sseq \im g$ e che vale $\im(g\circ f)= \im g$ se $f$ è suriettiva.
4. Provare, utilizzando quanto osservato a lezione, che se $f$ è un'applicazione, allora $f$ è suriettiva se e solo se $\vecf$ è suriettiva.

31/10

Discussione di alcuni esercizi dalla lezione precedente. Come trovare tutte le sezioni di una data applicazione suriettiva.

Applicazioni iniettive. Definizione in due forme equivalenti; negazione dell'iniettività. Applicazioni biettive. Esempi ed esercizi. Le restrizioni di un'applicazione iniettiva sono tutte iniettive.

Se $f\colon A\to B$ e $g\colon B\to C$ sono applicazioni componibili, si ha:

• se $f$ e $g$ sono entrambe iniettive $g\circ f$ è iniettiva;
• se $f$ e $g$ sono entrambe biettive $g\circ f$ è biettiva;
• se $g\circ f$ è iniettiva, allora $f$ è iniettiva;
• se $g\circ f$ è biettiva, allora $f$ è iniettiva e $g$ è suriettiva.

Retrazioni di un'applicazione $f\colon A\to B$ (cioè applicazioni $h\colon B\to A$ tali che $h\circ f=\id_A$). Teorema: un'applicazione $f\colon A\to B$ è iniettiva se e solo se $A=\vuoto$ o $f$ ammette retrazioni. Dire che una applicazione $f$ è una sezione di una applicazione $g$ equivale a dire che $g$ è una retrazione di $f$. Tutte le sezioni sono iniettive e tutte le retrazioni sono suriettive.

Applicazione inversa di un'applicazione (cioè: applicazione che sia sia una sezione che una retrazione). Teorema (unicità dell'inversa): se un'applicazione $f$ ha una sezione $s$ ed una retrazione $r$, allora $s=r$, quindi $s$ è inversa di $f$; inoltre $s$ è l'unica sezione, l'unica retrazione e l'unica inversa di $f$.

Per un'arbitraria applicazione $f$ sono equivalenti: (1) $f$ è biettiva; (2) $f$ ha una inversa; (3) $f$ ha una ed una sola sezione.

Esistono in questo sito delle note su sezioni e retrazioni (e argomenti collegati) che consiglio di leggere (almeno in parte), tenendo però in conto che le notazioni lì usate non sono quelle seguite nel corso e che molto del materiale lì contenuto non ci riguarda necessariamente. In particolare, rispetto al corso:

1. le note usano una diversa notazione per la composizione di applicazioni: se $f\colon A\to B$ e $g\colon B\to C$ sono applicazioni componibili, nelle note la loro composta $g\circ f$ è scritta sempre come $fg$;
2. le note usano la notazione esponenziale per l'immagine di un elemento mediante un'applicazione: $a^f$ piuttosto che $f(a)$ come nel corso;
3. non fa parte del programma l'enunciato 5 né ciò che segue l'eunciato 8.

Esercizi proposti:

1. Tornare agli esercizi 7 e 8 da quelli per le vacanze di pasqua, stabilendo quali tra quelle elencate sono applicazioni iniettive, suriettive, biettive e determinando, ove possibile, retrazioni, sezioni ed applicazioni inverse.
2. Fare lo stesso per le applicazioni che appaiono nell'esercizio 4 di Tautologie, insiemi, aritmetica (NB: $fg$ va letto come $g\circ f$).
3. … ed anche per e applicazioni:
   • $n\in\Z\mapsto n+5\in\Z$;
   • $n\in\N\mapsto n+5\in\N$;
   • per un arbitrario insieme $A$: $\quad x\in\P(A)\mapsto A\setminus x\in\P(A)$;
   • $n\in\N\mapsto \begin{cases}n/2&\text{se }n\text{ è pari}\\-(n+1)/2&\text{se }n\text{ è dispari}\end{cases}\in\Z$.
4. Trovare, nel monoide delle trasformazioni di $\N$, un elemento con infiniti inversi a sinistra.
5. Trovare tutte le sezioni e tutte le retrazioni dell'applicazione immersione $\set{0}\to\set{0,1}$.

2/11

Discussione dettagliata di alcuni esercizi dalla lezione precedente. Ulteriori caratterizzazioni della biettività: un'applicazione $f\colon A\to B$ è biettiva se e solo se $\forall y\in B$$(\exists! x\in A$$(y=f(x)))$. Metodi effettivi per la dimostrazione della biettività di un'applicazione e per descrizione esplicita della sua inversa. Esempio di applicazione biettiva da $\N$ a $\Z$.

Riepilogo sulla simmetrizzabilità (anche a destra o a sinistra) nel monoide delle trasformazioni di un insieme. Permutazioni (cioè applicazioni biettive da un insieme a sé stesso); il gruppo simmetrico $\Sym(A)=\U(T(A))$ su un insieme $A$. $\Sym(A)$ è abeliano se e solo $A$ ha meno di tre elementi. Trasposizioni.

Esercizi proposti:

1. Trovare, ove possibile, una sezione ed una retrazione di ciascuna delle applicazioni qui indicate, dove $A=\set{0,1,2}$, $B=\set{1,2}$, $C=\set{1,2,3,4}$:
   • $f\colon A\to B$ definita da $0\mapsto 1$, $1\mapsto 2$, $2\mapsto 1$;
   • $g\colon C\to A$ definita, da $1\mapsto 1$, $2\mapsto 2$, $3\mapsto 0$, $4\mapsto 0$;
   • $f\circ g$;
   • $h\colon x\in B\mapsto 2+x\in C\setminus B$.
2. Sia $S=\set{1,2,3}$. Sapendo che $\Sym(S)$ ha esattamente 6 elementi, trovarli (basta pensare alle trasposizioni ed ai loro prodotti) e scrivere la tavola di Cayley di $\Sym(S)$.
3. Facendo uso dell'esempio visto a lezione, decidere se esiste un'applicazione biettiva da $\N^*$ a $\Z$.

5/11

Discussione di alcuni esercizi dalla lezione precedente. Esercizio supplementare: se $f$ e $g$ sono applicazioni suriettive (risp. iniettive) componibili, $s$ è una sezione (risp. retrazione) di $f$ e $t$ è una sezione (risp. retrazione) di $g$, allora $t\circ s$ è una sezione (risp. retrazione) di $f\circ g$.

Prime osservazioni di calcolo combinatorio. Fattoriali e fattoriali discendenti. Scelti comunque due insiemi finiti $A$ e $B$ si ha: $|A\times B|=|A|\,|B|$ e l'insieme $B^A=\Map(A,B)$ ha cardinalità $|B|^{|A|}$. Inoltre:

1. esistono applicazioni iniettive da $A$ a $B$ se e solo se $|A|\le |B|$. Nel caso, il loro numero è $|B|!/(|A|-|B|)!$;
2. esistono applicazioni suriettive da $A$ a $B$ se e solo se $|A|=|B|=0$ oppure $|A|\ge |B|>0$;
3. esistono applicazioni biettive da $A$ a $B$ se e solo se $|A|=|B|$. Nel caso, il loro numero è $|A|!$;
4. in particolare, $|\Sym(A)|=|A|!$.
5. se $|A|=|B|$ e $f\colon A\to B$ è un'applicazione, sono equivalenti: (1) $f$ è iniettiva, (2) $f$ è biettiva, (3) $f$ è suriettiva.

L'ultima affermazione diventa falsa per insiemi $A$ e $B$ infiniti: esempi.

Cenni alla nozione generale di equipotenza tra insiemi: se $A$ e $B$ sono insiemi arbitrari, $A$ è equipotente a $B$ (in simboli: $|A|=|B|$) se e solo se esiste un'applicazione biettiva da $A$ a $B$. Osservazioni: se $A$ è equipotente a $B$, allora $B$ è equipotente ad $A$; $A$ è eqipotente ad $A$; se $A$ è equipotente a $B$ e $B$ è equipotente a $C$ allora $A$ è equipotente a $C$. Si scrive invece $|A|\le |B|$ per dire che esiste un'applicazione iniettiva da $A$ a $B$. Questa simbologia è in accordo con quanto visto per gli insiemi finiti.

Sono tra loro equipotenti $\N$, $\N^*$, $\Z$; solo a titolo di notizia lo sono anche $\Z$ e $\Q$ ma non lo sono $\Q$ ed $\R$. Sempre a titolo di notizia: per ogni insieme $S$ si ha $|S|\le |\P(S)|$ ma non $|S|=|\P(S)|$ (non esistono applicazioni suriettive da $S$ a $\P(S)$).

Esercizi proposti:

1. Provare che in ogni monoide sia l'insieme degli elementi simmetrizzabili a sinistra che quello degli insiemi simmetrizzabili a destra sono parti chiuse.
2. Siano $A=\set{n\in\N\mid n\lt 8}$ e $B=\set{n\in\N\mid n\lt 10}$. Esprimere (non fare calcoli!):
   • $|A|$, $|B|$ e $|A\times B|$;
   • il numero delle applicazioni da $A$ a $B$ e, tra queste, il numero di quelli iniettive, il numero di quelle suriettive, il numero di quelle biettive;
   • il numero delle applicazioni da $A\times B$ a $B\times A$ e, tra queste, il numero di quelli iniettive, il numero di quelle suriettive, il numero di quelle biettive;
   • il numero delle applicazioni costanti da $B$ ad $A$;
   • il numero delle applicazioni $f$ da $B$ ad $A$ tali che $f(0)=2$;
   • il numero delle applicazioni $f$ da $B$ ad $A$ tali che $\im f\sseq \set{0,1,7}$;
   • il numero delle applicazioni iniettive $f$ da $A$ a $B$ tali che $f(0)\ne 5$.
   Sia $X$ una parte di $A$. Supponiamo che esista un'applicazione suriettiva da $X$ ad $A$. Cosa sappiamo dire su $X$?
3. Utilizzando un alfabeto $A$ di 7 caratteri, quante stringhe di lunghezza $n$ possiamo formare se $n=5$ e quante se $n=12$? E, in ciascuno dei due casi, quante senza ripetizioni di caratteri?
4. 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?

7/11

Discussione di alcuni esercizi dalla lezione precedente.

Traslazioni in una struttura algebrica con un'operazione binaria; elementi cancellabili, a sinistra o a destra; elementi cancellabili. Rapporto tra simmetrizzabilità e cancellabilità in un monoide. Esempi. Questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità, che contiene più di quanto richiesto ai fini di questo corso. A noi servono, oltre alle definizioni, la proposizione 1 ed il Teorema 4.

Visualizzazione delle cancellabilità nelle tavole di Cayley, con diversi esempi. In particolare: ciascuna delle righe e delle colonne della tavola di Cayley di un gruppo è sempre priva di ripetizioni. Costruzione della tavola di Cayley dei gruppi di cardinalità due o tre.

Potenze (o, in notazione additiva, multipli) di un elemento di un semigruppo secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari nel caso dei gruppi). 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.

Esercizi proposti:

1. Svolgere l'esercizio 9 degli esercizi per le vacanze di pasqua determinando, per ciascuna delle stutture associative lì presentate, quali elementi sono cancellabili a destra e/o a sinistra.
2. Per un arbitrario insieme $A$ determinare gli elementi cancellabili a destra e/o a sinistra rispetto a ciascuna delle operazioni $\cup$, $\cap$, $\ds$, $\setminus$ in $\P(A)$.
3. Definita in $\Z\times\Z$ l'operazione $*$ ponendo, per ogni $a,b,c,d\in\Z$, $(a,b)*(c,d)=(a+c,bd)$, si determinino gli elementi cancellabili in $(\Z\times\Z,*)$.
4. Per ogni elemento $a$ di un semigruppo $S$, siano $\sigma_a$ e $\delta_a$ le traslazioni sinistra e destra $S\to S$ determinate da $a$. Provare che, per ogni $a,b\in S$, si ha $\sigma_{ab}=\sigma_a\circ\sigma_b$ e $\delta_{ab}=\delta_b\circ\delta_a$.
5. Verificare che, in ogni monoide $S$, l'insieme degli elementi cancellabili a sinistra e quello degli elementi cancellabili a destra sono parti chiuse.

9/11

Discussione dettagliata di alcuni esercizi dalla lezione precedente. Le traslazioni definite in un monoide da elementi invertibili sono biettive, e viceversa.

Omomorfismi tra strutture algebriche ad una operazione binaria. Alcuni esempi; tra essi: l'omomorfismo dal monoide delle parole su un alfabeto al monoide additivo dei naturali che ad ogni parola associa la sua lunghezza.

Gli omomorfismi suriettivi conservano l'associatività, la commutatività, gli elementi neutri (anche a destra o a sinistra), i simmetrici (anche a destra o a sinistra). Isomorfismi. L'inversa di ogni isomorfismo è un isomorfismo. Discussione generale ed alcuni esempi. Invarianza delle proprietà algebriche per isomorfismi. Isomorfismi e tavole di Cayley.

Alcuni esempi di isomorfismi: l'applicazione $X\mapsto S\setminus X$, per un fissato insieme $S$, da $(\P(S),\cup)$ a $(\P(S),\cap)$ o viceversa; la funzione esponenziale da $(\R,+)$ a $(\R^+,\cdot)$ (il gruppo moltiplicativo dei reali positivi).

Esercizi proposti:

1. L'applicazione $X\in \P(\Z)\mapsto X\cap \N\in\P(\N)$ è un omomorfismo da $(\P(\Z),\cap)$ a $(\P(\N),\cap)$? e da $(\P(\Z),\cup)$ a $(\P(\N),\cup)$?
2. Scrivere un isomorfismo da $(\set{1,-1},\cdot)$ a $(\P(\set 1),\ds)$.
3. Tenuto conto di ciò che abbiamo verificato nella lezione precedente, possiamo concludere che i gruppi di cardinalità 3 sono isomorfi tra loro?
4. Si consideri l'operazione binaria $\varphi$ in $\Z$ definita nell'esercizio 3 della lezione del 17 ottobre e si stabilisca se l'applicazione $n\in\Z\mapsto n+1\in\Z$ è un isomorfismo da $(\Z,+)$ a $(\Z,\varphi)$. Quest'ultimo è un gruppo?
5. Siano $g\colon (A,*)\to (B,\bullet)$ e $f\colon (B,\bullet)\to (C,\lozenge)$ omomorfismi. Provare che $f\circ g$ è un omomorfismo da $(A,*)$ a $(C,\lozenge)$.
6. Verificare che, come detto a lezione, se $f$ è un isomorfismo da una struttura algebrica $(S,*)$ ad una struttura algebrica $(T,\bullet)$ e $x$ è un elemento di $S$, allora $x$ è cancellabile a destra in $(S,*)$ se e solo se $x$ è cancellabile a destra in $(T,\bullet)$.
7. Sia $*$ un'operazione binaria nell'insieme $S$ e sia $T$ una parte chiusa (non vuota) in $(S,*)$. Verificare che l'immersione di $T$ in $S$ è un omomorfismo da $(T,*)$ a $(S,*)$.
8. Sia $G$ un gruppo abeliano. Verificare che l'applicazione $g\in G\mapsto g^{-1} \in G$, che ad ogni elemento $G$ associa l'inverso, è un isomorfismo da $G$ a $G$. Cambia qualcosa se $G$ non è abeliano?

12/11

Discussione dettagliata di alcuni esercizi dalla lezione precedente. Ulteriori osservazioni sulla nozione di isomorfismo.

Sottogruppi di un gruppo e loro caratterizzazione. Esempio: per ogni numero intero $n$, l'insieme $n\Z=\set{na\mid a\in\Z}$ costituisce un sottogruppo di $(\Z,+)$ (è stato anche detto, ma non dimostrato, che tutti i sottogruppi di $(\Z,+)$ sono di questa forma).

Arbitrarie intersezioni tra parti chiuse (in una struttura algebrica), tra sottomonoidi in un monoide, tra sottogruppi in un gruppo sono ancora parti chiuse, sottomonoidi, sottogruppi. Parti chiuse, sottomonoidi e sottogruppi generati da una parte $X$ di un semigruppo, o di un monoide, o di un gruppo. Descrizione di questi nel caso in cui $A$ sia un singleton. Gruppi ciclici; i gruppi ciclici sono abeliani. Esempio: il sottogruppo di $\Sym(\{1,2,3,4\})$ generato dal (singleton del)la permutazione definita da $1\mapsto 2\mapsto 3\mapsto 4\mapsto 1$; sua tavola di Cayley. Questo gruppo (ciclico di cardinalità 4) non è isomorfo a $(\P(\set{0,1}),\ds)$ che pure è un gruppo di cardinalità 4.

Omomorfismi di monoidi. Omomorfismi di gruppi.

Anelli. Definizione. Anelli commutativi; anelli unitari. Lo zero $0_R$ e (se esiste) l'unità $1_R$ di un anello. Terminologia per gli anelli: opposti (cioè simmetrici rispetto all'operazione additiva) e inversi (cioè eventuali simmetrici rispetto all'operazione moltiplicativa). Esempi: l'anello $(\Z,+,\cdot)$ degli interi; l'anello $(\P(A),\ds,\cap)$ delle parti di un insieme $A$.

Esercizi proposti:

1. Quali tra questi sono e quali non sono anelli: rispetto alle usuali operazioni di addizione e di moltiplicazione, $(\R,+,\cdot)$, $(\Q,+,\cdot)$, $(2\Z,+,\cdot)$, $(\Z\setminus 2\Z,+,\cdot)$; per un insieme $A$, $(\P(A),\cup,\cap)$, $(\P(A),\ds,\cup)$; $(\Z,+,*)$ dove $+$ è l'usuale addizione tra interi e $*$ è definita da: $\forall a,b\in\Z(a*b=0)$.
2. Stabilire, sia facendo uso di tautologie che facendo uso di diagrammi di Venn, se, per un arbitario insieme $A$ l'operazione $\setminus$ è distributiva a destra e/o a sinistra rispetto all'unione e/o rispetto all'intersezione.
3. Per ogni insieme $S$, ricordando che $\P_1(S)$ è $\set{\set x\mid x\in S}$, trovare il sottomonoide di $(\P(S),\cup)$ generato da $\P_1(S)$ nel caso in cui $S=\set{1,2,3}$ e nel caso in cui $S=\N$. Attenzione alla trappola!
4. Siano $(R,+,\cdot)$ e $(S,\oplus,\odot)$ due anelli. Nel prodotto cartesiano $C=R\times S$ definiamo due operazioni binarie (che continuiamo a indicare con $+$ e $\cdot$) ponendo, per ogni $a,b\in R$ e $u,v\in S$, $(a,u)+(b,v)=(a+b,u\oplus v)$ e $(a,u)\cdot(b,v)=(a\cdot b,u\odot v)$. Provare che $C$, munito di queste due operazioni, è un anello, che questo anello è commutativo se e solo se lo sono sia $R$ che $S$ ed è unitario se e solo se lo sono sia $R$ che $S$.
5. 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}$.
6. Nel gruppo $\Sym\set{1,2,3,4,5}$ si descriva il sottogruppo generato dal (singleton del)la permutazione $\alpha$ definita da $1\mapsto 2\mapsto 3\mapsto 4\mapsto 5\mapsto 1$ e la sua tavola di Cayley.
7. Questo esercizio ha lo scopo di mostrare che ogni gruppo di cardinalità 4 è isomorfo ad uno dei due gruppi di cardinalità 4 esibiti a lezione. Sia $(G,\cdot)$ un gruppo di cardinalità 4, con elemento neutro $t$. Provare a scriverne le possibili tavole di Cayley, utilizzando la proprietà di cancellabilità, ovvero l'assenza di ripetizioni nelle righe e nelle colonne, ragionando come segue:
   1. mostrare che se un elemento $a$ di $G$ è tale che $a^2\ne t$, allora $a\ne t$ e, chiamando $b$ l'elemento $a^2$ e $c$ il restante elemento di $G$, è possibile completare la tavola di Cayley di $G$ in un solo modo;
   2. mostrare che anche nell'altro caso, cioè se ogni elemento di $G$ ha per quadrato $t$, è possibile completare la tavola di Cayley di $G$ in un solo modo;
   3. trarre la conclusione.

14/11

Discussione di alcuni esercizi dalla lezione precedente. Un esempio di anello non unitario; un esempio di anello unitario non commutativo, presentato solo per cenni: l'anello delle matrici $2\times 2$ sugli interi.

Sottoanelli di un anello; sottoanelli unitari. Esempi. Omomorfismi di anelli e di anelli unitari. Isomorfismi tra anelli. Nozione di sottoanello generato.

Alcune regole elementari di calcolo in un anello $R$: per ogni $a$, $b$ in $R$, $a0_R=0_R=0_Ra$, e $a(-b)=-(ab)=(-a)b$. Notazione $a-b=a+(-b)$; per ogni $a,b,c\in R$ si ha $a(b-c)=ab-ac$. Osservazione: se $a,b\in R$, in generale si ha $(a+b)^2=a^2+ba+ab+b^2$, non sempre vale $(a+b)^2=a^2+2ab+b^2$.

In un anello che abbia più di un elemento lo zero non può essere invertibile. Corpi e campi (esempi: i campi dei razionali, dei reali, dei complessi; anche $\P(S)$ è un campo, di cardinalità 2, se $|S|=1$.)

Divisori dello zero sinistri, destri, divisori dello zero negli anelli. I divisori sinistri (risp. destri) dello zero sono precisamente gli elementi non cancellabili a sinistra (risp. a destra), i divisori dello zero sono precisamente gli elementi non cancellabili.

Legge di annullamento del prodotto, anelli integri, domini di integrità. Esempi. I campi sono domini di integrità unitari, ma non vale il viceversa (un esempio è fornito dall'anello degli interi). I domini di integrità finiti (ma in verità tutti gli anelli integri finiti) sono campi. Per questi argomenti si consultino le note sulla cancellabilità.

La prossima prova in itinere verterà sugli argomenti trattati nel corso sino a questo punto, ad eccezione dei risultati di tipo combinatorio sul conteggio delle applicazioni tra insiemi finiti.

Esercizi proposti:

1. Dimostrare che, per ogni numero intero $n$, $n\Z=\set{nk\mid k\in\Z}$ costituisce un sottoanello dell'anello degli interi.
2. Esercizio 5 da Polinomi e strutture algebriche, solo relativamente alle nozioni introdotte a lezione.
3. Nell'anello $\Z\times\Z$, definito, come in uno degli esercizi della scorsa lezione, ponendo $(a,b)+(c,d)=(a+c,b+d)$ e $(a,b)\cdot(c,d)=(ac,bd)$, si decida quali tra questi elementi sono divisori dello zero e quali cancellabili: $(1,1)$, $(1,2)$, $(0,4)$. Fatto questo, provare a descrivere l'insieme dei divisori dello zero in $\Z\times\Z$.
4. Con riferimento all'anello $\Z\times\Z$ dell'esercizio precedente, verificare che $\set{0}\times \Z$ è un sottoanello di $\Z\times\Z$. Ne è un sottoanello unitario? Che tipo di anello è $\set{0}\times \Z$ (munito delle operazioni indotte da quele di $\Z\times\Z$)? Per caso è isomorfo ad un anello che ben conosciamo?
   Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
5. Provare che, se $S$ è un insieme non vuoto, l'anello delle parti di $S$ ha esattamente un elemento che non è divisore dello zero.
6. Sia $R$ un anello unitario. È possibile che $1_R$ sia un divisore dello zero in $R$?
7. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?
8. Provare che se $a$ e $b$ sono elementi di un anello $(R,+,\cdot)$ si ha $(a+b)^2=a^2+2ab+b^2$ se e solo se $ab=ba$.

16/11

Discussione molto approfondita di esercizi dalla lezione precedente.

Un'ulteriore regola di calcolo per un anello unitario $R$: il multiplo $na$ di un elemento $a$ secondo un intero $n$ è il prodotto (in $R$) tra $n1_R$ e $a$.

Nozione generale di $n$-pla. Rappresentazione di parti di un insieme finito di cardinalità $n$ mediante $n$-ple di 0 e 1. Per una parte $T$ di un insieme $S$, funzione caratteristica $\chi_{T,S}$ di $T$ in $S$. Teorema: l'applicazione da $\P(S)$ a $\set{0,1}^S$ che a ciascuna parte $T$ di $S$ associa $\chi_{T,S}$ è biettiva (la dimostrazione va ancora completata, lo faremo nella prossima lezione). Conseguenza: per ogni insieme finito $S$ si ha $|\P(S)|=2^{|S|}$.

Esercizi proposti:

1. In $S=\Z\times\Z$ si considerino le operazioni binarie $\oplus$ e $*$ definite ponendo, per ogni $a,b,c,d\in\Z$ $(a,b)\oplus(c,d)=(a+c,b+d)$ e $(a,b)*(c,d)=(ac,ad)$. Si decida se $(S,\oplus, *)$ è un anello e, nel caso, se è commutativo, se è unitario, se è integro, se è un corpo; determinarne i divisori sinistri ed i divisori destri dello zero.
2. Sia $S=\set{1,2,3}$. Nell'anello prodotto diretto $R=\P(S)\times \Z$, cioè quello definito a partire dagli anelli $\P(S)$ e $\Z$ come indicato in uno degli esercizi della lezione del 12/11, si dica quali e quanti sono gli elementi invertibili e i divisori dello zero. Si trovino poi un sottoanello di $R$ che abbia cardinalità 8, uno di cardinalità 4 ed uno che sia un dominio di integrità.
3. Dati due insiemi equipotenti $S$ e $T$ ed un'applicazione biettiva $f\colon S\to T$, provare che:
   1. l'applicazione $X\in \P(S)\mapsto \vecf(X)\in\P(T)$ è un isomorfismo dall'anello delle parti di $S$ all'anello delle parti di $T$;
   2. l'applicazione $\sigma\in T(S)\mapsto f\circ \sigma\circ f^{-1}\in T(T)$ è un isomorfismo dal monoide delle trasformazioni di $S$ al monoide delle trasformazioni di $T$;
   3. l'applicazione $\sigma\in \Sym(S)\mapsto f\circ \sigma\circ f^{-1}\in \Sym(T)$ è un isomorfismo dal gruppo simmetrico su $S$ al gruppo simmetrico su $T$.

19/11

Discussione approfondita di esercizi sugli anelli dalla lezione precedente.

Completamento della dimostrazione lasciata in sospeso nella lezione precedente (sulla biezione $T\in \P(S) \mapsto\chi_{T,S}\in\set{0,1}^S$, per un insieme $S$), con ulteriore illustrazione dell'importanza delle biezioni (e degli isomorfismi), che permettono di tradurre problemi e soluzioni, e codificare dati, da un ambito ad un altro in modo reversibile e senza perdita di informazione.

Anelli booleani; esempio: per ogni insieme $S$ l'anello delle parti di $S$ è booleano. Proprietà degli anelli booleani: sono commutativi e, in essi, ogni elemento coincide col suo opposto. I sottoanelli unitari degli anelli booleani sono anelli booleani. Enunciato del teorema di Stone (per ogni anello booleano $R$ esiste un insieme $S$ tale che $R$ sia isomorfo ad un sottoanello unitario di $\P(S)$; se inoltre $R$ è finito esiste un insieme $S$ tale che $R\iso\P(S)$). Conseguenze: la cardinalità di un anello booleano finito è necessariamente una potenza di 2; due anelli booleani finiti della stessa cardinalità sono certamente isomorfi (per questo va usato anche l'ultimo degli esercizi della lezione scorsa).

Richiami sulle relazioni binarie. Proprietà riflessiva e proprietà antiriflessiva: negazioni; esempi; confronto tra queste proprietà.

Esercizi proposti:

1. Sia $R$ un anello booleano di cardinalità compresa tra 500 e 1000. Cosa sappiamo dire su $R$? Se $S$ è un anello booleano di cardinalità compresa tra 300 e 800, si ha necessariamente $R\iso S$?
2. Siano $S$ e $T$ due insiemi. Provare che l'anello prodotto diretto $\P(S)\times\P(T)$ è booleano.
3. Sia $a$ un elemento idempotente di un anello unitario $R$. Provare che o $a=1_R$ oppure $a$ è un divisore dello zero in $R$.
4. Sia $B$ l'insieme costituito da tutte le parti $X$ di $\N$ tali che o $X$ o $\N\setminus X$ è finito. Verificare che $B$ costituisce un sottoanello unitario di $\P(\N)$ e quindi è un anello booleano. A titolo di notizia: $B$ non è isomorfo all'anello $\P(S)$ per alcun insieme $S$; addirittura non esistono insiemi $S$ tale che $B$ e $\P(S)$ siano equipotenti.
5. Provare se se $\rho$ è una relazione binaria in un insieme $A$, allora $\rho$ è riflessiva e antiriflessiva se e solo se $A=\vuoto$.

21/11

Discussione di esercizi dalla lezione precedente.

Ulteriori proprietà di relazioni binarie: proprietà simmetrica, antisimmetrica e transitiva; loro formulazioni equivalenti in termini di proprietà della relazione duale e del grafico; loro negazione. Diversi esempi. Una relazione binaria in un insieme $A$ è simmetrica e antisimmetrica se e solo se il suo grafico è contenuto nella diagonale di $A$.

Relazioni di ordine (largo), relazioni di ordine stretto, relazioni di equivalenza. 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.

Esercizi proposti:

1. Esercizi 1 (esclusi i punti f e g) e 2 (esclusi i punti a e b) 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$ un insieme non vuoto e sia $\Re$ la relazione universale in $A$, cioè quella che ha per grafico $A\times A$. Delle proprietà di relazioni binarie introdotte nelle ultime due lezioni, quali sono soddisfate da $\Re$?
3. Dimostrare che se $A$ è un insieme finito di cardinalità $n$ esistono esattamente $2^{n^2}$ relazioni binarie in $A$ (suggerimento: quante sono le parti di $A\times A$?).
4. Sia $A=\set{0,1}$. Delle 16 relazioni binarie in $A$ (vedi esercizio precedente), dire quali e quante sono riflessive, quali e quante antiriflessive, quali e quante sono simmetriche, quali e quante sono antisimmetriche. Usando l'osservazione conclusiva delle lezione di oggi, provare che se una relazione binaria $\alpha$ in $A$ non è transitiva, allora $0\mathrel\alpha 1$ e $1\mathrel\alpha 0$. A questo punto, quante sono le relazioni binarie non transitive e quante quelle transitive in $A$?

23/11

Discussione di esercizi dalla lezione precedente.

Ulteriori esempi di relazioni di equivalenza. Le relazioni di equivalenza banali in un insieme (relazione di uguaglianza e relazione universale).

Nucleo di equivalenza di un'applicazione (anche detto, nel libro di testo, equivalenza associata all'applicazione). Esempi. Il nucleo di equivalenza di un'applicazione $f$ è la relazione di uguaglianza (risp. quella universale) nel dominio di $f$ se e solo se $f$ è iniettiva (risp. costante).

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$;
• sono tra loro equivalenti: $a\sim b$, $b\sim a$, $ a\in[b]_\sim$, $b \in [a]_\sim$, $[a]_\sim\cap [b]_\sim\ne \vuoto$, $ [a]_\sim=[b]_\sim$;
• ogni elemento di $A$ appartiene ad esattamente una classe di equivalenza.

Con le stesse notazioni, proiezione canonica di $A$ su $A/{\sim}$: è l'applicazione (suriettiva) $A\to A/{\sim}$ che manda ogni $x\in A$ in $[x]_\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: $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$. Esempi. Gli insiemi quoziente (definiti da relazioni di equivalenza) sono partizioni.

Per un arbitrario insieme $A$, biezione canonica da $\Eq(A)$ a $\Part(A)$ (insiemi delle relazioni di equivalenza e delle partizioni di $A$): è l'applicazione che ad ogni $\alpha\in\Eq(A)$ associa $A/\alpha$. Il fatto che questa applicazione è biettiva non è stato ancora dimostrato.

Esercizi proposti:

1. Fissata una relazione di equivalenza $\sim$ in un insieme $A$, provare che per ogni $a,b\in A$ si ha $a\sim b$ se e solo se $ [a]_\sim\subseteq [b]_\sim$
2. Descrivere il nucleo di equivalenza dell'applicazione $n\in\Z\mapsto n^2-7\in\Z$ e, per un arbitrario $X\subset \Z$, quello della funzione caratteristica di $X$ in $\Z$. Descrivere l'insieme quoziente di $\Z$ rispetto a questo secondo nucleo.
3. Siano $S=\set{n\in\N\mid n\lt 8}$ e $\sim$ la relazione binaria definita in $\P(S)$ ponendo, per ogni $x,y\in \P(S)$, $x\sim y\iff |x|=|y|$. Dopo aver verificato che $\sim$ è una relazione di equivalenza, descrivere l'insieme quoziente $\P(S)/\sim$. Quanti e quali sono i suoi elementi?
4. Quali tra queste sono partizioni di $\set{n\in\N\mid n\lt 8}$?: $\set{\set{1,3,5}, \set{n\in\N\mid n \text{ è pari}},\set{7}}$, $\set{\set{n\in\N\mid n\lt 7},\set{7}}$, $\set{\set{0,1,3,5}, \set{n\in\N\mid n^2=16},\set{2,7},\set{6,8}}$.
5. Trovare, se possibile, un insieme $X$ tale che $\set{\N^*,\Z\setminus\N^*, X}$ sia una partizione di $\Z$.
6. Per quali insiemi $X\subseteq\N$ l'insieme $\set{X,\N\setminus X}$ è una partizione di $\N$?

26/11

Discussione di esercizi dalla lezione precedente.

Dimostrazione del teorema fondamentale sulle partizioni e le relazioni di equivalenza (biettività, per ogni insieme $A$, dell'applicazione ${\sim}\in\Eq(A)\mapsto A/{\sim}\in\Part(A)$). Applicazioni di questo risultato, esempi, esercizi.

Il numero degli elementi di una unione finita di insiemi finiti. Il principio della partizione (se $F$ è una partizione di un insieme finito $A$, allora $|A|$ e la somma $\sum_{b\in F}|b|$). Il principio di inclusione-esclusione, con verifica nel caso dell'unione di due o tre insiemi.

Descrizione delle 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)})$.

L'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in A/{\sim}$ è biettiva, quindi si ha $|A/{\sim}|=|\im f|$. Teorema fondamentale di omomorfismo per insiemi. 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.

Ogni relazione d'ordine largo $\rho$ in un insieme $A$ definisce una relazione di ordine stretto $\rho_{\ne}$ in $A$ descritta da: $(\forall x,y\in A)$$(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$.

Esercizi proposti (sono tanti; hanno priorità i numeri 3, 5, 12):

1. 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$?
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$? Descriverli esplicitamente.
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. 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. Identificare $\alpha$ nel caso in cui $\beta$ sia una delle relazioni di equivalenza banali in $B$.
5. Sia $A=\set{1,2,3,4,5,6}$. Stabilire quante sono, e descrivere esplicitamente, le relazioni di equivalenza $\sim$ in $A$ tali che $1\sim 3\not\sim 2\sim 4$ e $4\in[5]_\sim$.
6. 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$?
7. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cap \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}$.
8. Esercizio 2, punti (i) e (ii), dal compito del 22 giugno 2015.
9. Esercizio 2 dal compito del 5 marzo 2015.
10. Esercizio 1 dal compito del 16 luglio 2013.
11. Sia $A=\set{0,1,2}$. Posto $M=A^\N$ (l'insieme delle applicazioni da $\N$ ad $A$), definire in $M$ la relazione binaria $\gamma$ ponendo, per ogni $f,g\in M$, $f\mathrel\gamma g\iff f(43)=g(43)$. Decidere se $\gamma$ è una relazione di equivalenza e, nel caso lo sia, calcolare $|M/\gamma|$ e decidere se esistono classi di equivalenza rispetto a $\gamma$ che siano finite.
12. 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|$?
13. Utilizzando diagrammi di Venn, come fatto a lezione nel caso della formula analoga per due insiemi, verificare la formula di inclusione-esclusione per tre insiemi finiti (per ogni $A,B,C$ che siano insiemi finiti, $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$).

28/11

Discussione di alcuni esercizi dalla lezione precedente.

Relazione d'ordine largo $\underline\sigma$ in un insieme $A$ definita da una relazione di ordine stretto $\sigma$. L'applicazione $\sigma\in \OS(A)\mapsto \underline\sigma\in \OL(A)$ è biettiva; l'inversa è, con le notazioni dele lezione scorsa, l'applicazione $\rho\in\OL(A)\mapsto\rho_{\ne}\in \OS(A)$. Descrizione di queste applicazioni in termini dei grafici delle relazioni coinvolte.

Insiemi ordinati. Se la relazione binaria $\rho$ ha una delle proprietà finora definite (riflessiva, antiriflessiva, simmetrica, antisimmetrica, transitiva, essere di equivalenza, d'ordine largo, d'ordine stretto), anche la sua duale ha la stessa proprietà (e, ovviamente, viceversa). Cenno al principo di dualità per insiemi ordinati.

Elementi tra loro confrontabili rispetto ad una relazione d'ordine. Relazioni d'ordine totale ed insiemi totalmente ordinati. Esempi. L'insieme delle parti di un insieme $A$, ordinato per inclusione, è totalmente ordinato se e solo se $|A|\le 1$.

Elementi minimi ed elementi minimali (degli elementi minimali sono state date due definizioni equivalenti); dualmente: elementi massimi ed elementi massimali. Prima osservazione: il minimi sono minimali; per dualità: i massimi sono massimali. Il discorso va continuato.

Esercizi proposti:

1. Si considerino in $\P(\N)$ i seguenti sottoinsiemi: l'insieme delle parti finite; l'insieme delle parti infinite; l'insieme delle parti di cardinalità compresa tra 5 e 14 (incluse); l'insieme $\set{\set{1,2,3}, \set{4},\set{n\in\N\mid n>3}}$. Di ciascuno di essi, se ordinato per inclusione, si dica quali sono gli eventuali elementi che sono minimi, massimi, minimali, massimali.
2. Sia $A=\set{1,2,3,4}$ e, in $\P(A)$, si definisca la relazione binaria $\tau$ definita ponendo, per ogni $x, y\in\P(A)$, $x\mathrel\tau y$ se e solo se $x\cap\set{2,3}\subseteq y\cap\set{2,3}$. Decidere se $\tau$ è una relazione d'ordine. Se lo è decidere se $\tau$ è totale e trovare gli elementi di $\P(A)$ che, rispetto a $\tau$ siano minimi, massimi, minimali, massimali. Ripetere l'esercizio dopo aver sostituito $\tau$ con $\sigma$, definita ponendo, per ogni $x, y\in\P(A)$, $x\mathrel\sigma y$ se e solo se $x=y$ oppure $x\cap\set{2,3}\subset y\cap\set{2,3}$.
3. Verificare che se un elemento $x$ è minimale in un insieme totalmente ordinato $(A,\rho)$ allora $x$ è minimo in $(A,\rho)$.

30/11

Discussione di alcuni esercizi dalla lezione precedente.

Se $a$ è minimo (risp. massimo) in un insieme ordinato $(S,\rho)$, $a$ è l'unico elemento minimale (risp. massimale) in $(S,\rho)$, quindi anche l'unico minimo (risp. massimo). 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: se in un insieme ordinato finito esiste un unico elemento minimale (risp. massimale), questo è il minimo (risp. massimo).

Ordinamento indotto su un (arbitrario) sottoinsieme di un insieme ordinato. Isomorfismi tra insiemi ordinati e proprietà che essi conservano. Applicazioni crescenti tra insiemi ordinati; esempio di un'applicazione biettiva crescente che non è un isomorfismo.

Relazione di copertura definita da una relazione d'ordine. Nel caso finito, essa determina l'ordinamento. Diagrammi di Hasse di insiemi ordinati finiti, con esempi.

Esercizi proposti:

1. Rispetto alla relazione d'ordine usuale tra numeri razionali, dati due numeri razionali $a$ e $b$, in quali casi $b$ copre $a$?
2. Sia $(S,\rho)$ un insieme ordinato e siano $a, b\in S$. Dimostrare che le seguenti proprietà sono equivalenti:
   • $b$ copre $a$;
   • $a$ è un elemento massimale di $\set{x\in S\mid x\mathrel{\rho_\ne} b}$ (ordinato con l'ordinamento indotto da $\rho$);
   • $a\ne b$ e $\set{x\in S\mid a\mathrel\rho x \land x\mathrel\rho b}=\set{a,b}$.
3. Rappresentare con un diagramma di Hasse ciascuno dei seguenti insiemi, ordinati per inclusione: $\set{\set{1,2,3}, \set{4},\set{n\in\N\mid n>3}}$, $\set{x\sseq \set{1,2,3}\mid 1\in x\lor 2\in x}$, $\set{x\sseq \set{1,2,3}\mid |x|\in \set{1,2}}$, $\P(\set{1,2,3})$. Di questi stessi insiemi ordinati determinare gli elementi minimali, massimali, minimo, massimo.
4. Siano $(B,\beta)$ un insieme ordinato e $f\colon A\to B$ un'applicazione. Sia $\alpha$ la relazione binaria definita in $A$ ponendo, per ogni $x,y\in A$, $x\mathrel\alpha y$ se e solo se $x=y$ oppure $f(x) \mathrel{\beta_{\ne}} f(y)$. Verificare che:
   • $\alpha$ è una relazione d'ordine;
   • se $M$ è l'insieme degli elementi minimali in $(\im f,\beta)$, $\avecf$ è l'insieme degli elementi minimali in $(A,\alpha)$;
   • se $M$ è l'insieme degli elementi massimali in $(\im f,\beta)$, $\avecf$ è l'insieme degli elementi massimali in $(A,\alpha)$.

3/12

Discussione degli esercizi dalla lezione precedente ed ulteriori esempi di diagrammi di Hasse.

Relazione di divisibilità in semigruppi ed in monoidi commutativi. Essa è transitiva e, nel caso dei monoidi, anche riflessiva. Nel caso del monoide $(\N,\cdot)$ (ma non nel caso del monoide $(\Z,\cdot)$) è una relazione d'ordine. Elementi associati in un monoide commutativo (due elementi $a$ e $b$ sono associati ($a\sim b$) se e solo se $a$ divide $b$ e $b$ divide $a$). Se $a,a', b,b'$ sono elementi di un monoide commutativo tali che $a\sim a'$ e $b\sim b'$, allora $a$ divide $b$ se e solo se $a'$ divide $b'$. Due elementi di un monoide commutativo $M$ sono associati se e solo se hanno lo stesso insieme di divisori ed anche se e solo se hanno lo stesso insieme di multipli. Di conseguenza: la relazione "essere elementi associati" è una relazione di equivalenza in $M$. Inoltre, se $a$ è un elemento di $M$ e $u\in \U(M)$, allora $au$ è associato ad $a$; se $a$ è cancellabile vale anche il viceversa: gli associati ad $a$ sono tutti e soli gli elementi della forma $au$ al variare di $u\in \U(M)$. Esempi.

Divisibilità in un anello commutativo unitario $R$: se $a\in R$ e due elementi sono multipli di $a$, anche le loro combinazioni lineari sono multiple di $a$.

Divisori banali di un elemento in un monoide commutativo. Elementi irriducibili; numeri primi.

Proprietà di buon ordinamento di $(\N,\le)$. Principio di induzione (prima forma).

Esercizi proposti:

1. Dimostrare per via diretta (cioè provando le proprietà riflessiva, simmetrica, transitiva) che, in un monoide comutativo, la relazione "essere elementi associati" è di equivalenza.
2. Disegnare il diagramma di Hasse, trovando anche gli elementi minimali, gli elementi massimali, eventuali minimo e massimo nell'insieme $\set{2,4,7,8,14,21}$ ordinato per divisibilità (cioè: tramite l'ordinamento indotto dalla divisibilità in $(\N,\cdot)$).
3. Fare lo stesso per l'insieme dei numeri naturali divisori di $n$, per ciascun $n$ appartenente a $\set{9,10,11,12,100}$.
4. Per un arbitrario insieme $A$, descrivere la relazione di divisibilità nel monoide $(A,\cup)$ (già la conosciamo). Nello stesso monoide, dire quando è che due elementi sono associati e quali elementi sono irriducibili.
5. Usando il principio di induzione, dimostrare che per ogni $n\in\N^*$ si ha $\sum_{i=1}^ni=n(n+1)/2$.

5/12

Dimostrazione per induzione dell'uguaglianza $|\P(S)|=2^{|S|}$ per ogni insieme finito $S$.

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 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}$. Il triangolo di Tartaglia-Pascal; formula ricorsiva: per ogni $k,n\in \N$ tali che $k\le n$, $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$; di conseguenza, formula chiusa: $\binom nk=n!/(k!(n-k)!)$.

Formula di Newton per l'espansione delle potenze di un binomio in un anello commutativo.

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.

Seconda forma del principio di induzione (o principio di induzione completa) e dimostrazioni di proprietà dei numeri naturali 'per controesempio minimo'.

Teorema fondamentale dell'aritmetica (in $\N^\#$ ed in $\Z\setminus\set 0$); ne è stata dimostrata solo una parte (ogni intero di valore assoluto maggiore di 1 è prodotto di numeri primi), ma non quella relativa all'essenziale unicità della fattorizzazione. Nozione di monoide fattoriale. Descrizione dei divisori di un assegnato elemento in un monoide fattoriale, con particolare riferimento ai casi di $\N^*$ e $\Z\setminus\set 0$.

Esercizi proposti:

1. Completare la verifica, solo accennata a lezione, della buona definizione dei coefficienti binomiali. Si tratta di provare che se $f\colon S\to T$ è un'applicazione biettiva e $k\in \N$, allora l'applicazione $X\in \P_k(S)\to \vecf(X)\in\P_k(T)$ è biettiva; l'inversa è $X\in \P_k(T)\to \avecf(X)\in\P_k(S)$.
2. Calcolare $\binom 74$ utilizzando il triangolo di Tartaglia-Pascal.
3. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_7(S)$.
4. Sia $S$ un insieme di cardinalità 11. Quante sono le parti di $S$ di cardinalità 5? E quante quelle di cardinalità 6? Quante sono le 8-parti di $\P(S)$?
5. Sia $S$ un insieme di cardinalità 5. Le funzioni caratteristiche delle 2-parti di $S$ sono tutte e sole le applicazioni da $S$ a $\set{0,1}$ tali che …? Quante sono?
6. 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)}$.
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. Che probabilità ha Anacleto di vincere?
8. Quanti sono, in $\N$, i divisori di $n=2\cdot 3^{7}\cdot 11^3$? E quanti tra essi sono multipli di $9$? E quanti sono i divisori di $n$ in $\Z$?

7/12

Equivalenze compatibili con un'operazione binaria ed operazioni quoziente (cioè quelle indotte sull'insieme quoziente). Esempi. Congruenza in una struttura algebrica e struttura quoziente. Se $\sim$ è una congruenza in una struttura di sostegno $S$, la proiezione canonica $a\in S\mapsto [a]_\sim \in S/{\sim}$ è un omomorfismo suriettivo (dalla struttura assegnata alla struttura quoziente), quindi conserva: commutatività, associatività, esistenza di neutri e simmetrici (anche solo a destra o sinistra), distributività. I quozienti di semigruppi, monoidi, gruppi (eventualmente abeliani), anelli (eventualmente commutativi o unitari) sono strutture dello stesso tipo. Avvertenza: non viene conservata la distributività

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$); sono effettivamente congruenze nell'anello $(\Z,+,\cdot)$ (a titolo di notizia: sono le sole congruenze in $(\Z,+)$). Notazioni: per interi $a$ ed $m$, $[a]_m=[a]_{\equiv m}$ e $\Z_m=\Z/{\equiv_m}$. Descrizione esplicita di $\equiv_m$ nei casi in cui $m$ è uno tra 0, 1 e 2. Per ogni intero $m$, ${\equiv_m}={\equiv_{-m}}$.

Descrizione esplicita delle classi resto: per ogni $m,a\in \Z$ si ha $[a]_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|$ e viene anche indicato con $\rest(a,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\Z)$$(a=bq+r \land 0\le 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$).

Massimi comuni divisori (MCD) 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 $d$.

Esistenza ed espressione di un MCD tra due elementi $a$ e $b$ di un monoide fattoriale.

Algoritmo euclideo (delle divisioni successive) per la ricerca di un MCD tra due numeri interi. Un'osservazione per la sua velocizzazione.

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.

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

Esercizi proposti:

1. Verificare che la relazione "avere la stessa lunghezza" è una congruenza nel monoide delle parole su un alfabeto. Fare lo stesso per la relazione definita dichiarando due parole $v$ e $w$ equivalenti se e solo se o sono entrambe di lunghezza zero o hanno lo stesso primo carattere.
2. 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 $*$. Spiegare perché questo esercizo generalizza parte del precedente.
3. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
4. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
5. La relazione indotta in $\N^*$ da $\equiv_2$ (cioè quella definita dichiarando due numeri interi positivi equivalenti se e solo se sono congrui modulo 2) è compatibile con l'operazione di elevazione a potenza ($(a,b)\mapsto a^b$) in $\N^*$? E se sostituiamo $\N$ ad $\N^*$ cambia qualcosa?
6. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_4$.
7. Come accennato a lezione, il passaggio ad un'operazione quoziente non conserva sempre la cancellabilità. Verificarlo su questo esempio: il numero $2$ è cancellabile nell'anello $\Z$, ma $[2]_4$ non è cancellabile nell'anello $\Z_4$. In effetti, vediamo così che benché $\Z$ sia un dominio di integrità, il suo anello quoziente $\Z_4$ non è un dominio di integrità.
8. Descrivere un massimo comun divisore negativo (in $\Z$) tra i numeri $2^6 3^4 7^5 11^8$ e $2^5 3^9 5^7 11^2$.
9. Calcolare $\rest(786761!,1111)$.
10. Svolgere gli esercizi 5 e 6 da Tautologie, insiemi, aritmetica, usando l'algoritmo euclideo per il nr.5. Trovare poi due interi $u$ e $v$ tali che il massimo comun divisore positivo tra $155$ e $688$ sia $155u+688v$.

10/12

Minimi comuni multipli.

Altre formulazioni del teorema di Bézout ed equazioni diofantee: 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$;
• per ogni $c\in\Z$, l'equazione diofantea $ax+by=c$ ha soluzioni (intere) se e solo $d$ divide $c$.
• $a$ e $b$ sono coprimi se e solo se esistono interi $u$ e $v$ tali che $1=au+bv$;

Se un'equazione diofantea (del tipo appena descritto) ha soluzioni, ne ha infinite. Lemma di Euclide (come conseguenza del teorema di Bézout): siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$.

Equazioni di primo grado in un anello commutativo unitario. Equazioni congruenziali (di primo grado, ad una incognita). L'equazione congruenziale $ax\equiv_m c$ (in $\Z$) è un modo per esprimere l'equazione $[a]_m X= [c]_m$ in $\Z_m$. Equivalenza tra il problema di risolvere l'equazione congruenziale $ax\equiv_m c$ e quello di risolvere l'equazione diofantea $ax+my=c$ (dove $a$, $c$ ed $m$ sono interi). Criterio di esistenza di soluzioni per le equazioni congruenziali (del tipo considerato). Come conseguenza: determinazione degli elementi invertibili nei quozienti di $\Z$. Per un intero $m>1$ sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità; (3) $m$ è primo. Si ritrova inoltre, con verifica diretta, una proprietà già nota: gli elementi non invertibili nei quozienti propri di $\Z$ sono tutti divisori dello zero.

Metodi effettivi per la semplificazione e la risoluzione delle equazioni congruenziali. Se $a,b\in\Z$ e $m\in\N^*$, indicando con $(*)$ l'equazione congruenziale $ax\equiv_m c$, si ha:

• se $a'\in[a]_m$ e $c'\in[c]_m$, l'equazione congruenziale $a'x\equiv_m c'$ è equivalente a $(*)$ (nel senso che le due equazioni hanno lo stesso insieme di soluzioni);
• per ogni $s,t,k\in\Z$, se $k\ne 0$, si ha $s|t$ se e solo se $sk|tk$. Di conseguenza, $akx\equiv_{mk} ck$ è equivalente a $(*)$;
• se $\ell$ è un intero coprimo con $m$, $a\ell x\equiv_{m} c\ell$ è equivalente a $(*)$; (questo perché $[\ell]_m$ è invertibile in $\Z_m$).

Algoritmo per la determinazione dell'insieme di tutte le soluzioni di un'equazione congruenziale come $(*)$ (se non vuoto, è una classe di resto modulo $m/d$, dove $d$ è un massimo comun divisore tra $a$ e $m$).

Rapido cenno a metodi di calcolo in artimetica modulare.

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

Segnalo inoltre due articoli di carattere divulgativo (rivolti a studenti delle scuole superiori) a proposito di aritmetica modulare e sue applicazioni che, anche se i loro contenuti sono in gran parte estranei al programma di questo corso, possono essere di interesse per qualcuno dei partecipanti: Una introduzione all'aritmetica modulare e Matematica e crittografia.

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario. Sua proprietà universale (come dalle note). Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata); l'omomorfismo di sostituzione.

Esercizi proposti:

1. Di ciascuno degli elementi di $\Z_4$, $\Z_7$, $\Z_{12}$ dire se è o non è un elemento invertibile, un elemento cancellabile, un divisore dello zero. Degli elementi invertibili di $\Z_{12}$ trovare anche gli inversi.
2. Indicando, per ogni $n\in\Z$, con $\bar n$ la classe $[n]_{66}$, in $\Z_{66}$ dire quali tra $\bar 7$, $\bar 8$, $\overline {667}$, $\overline{1000}$ sono invertibili, e di questi determinare gli inversi.
3. Svolgere gli esercizi da 7 a 11 in Tautologie, insiemi, aritmetica.
4. Usando l'algoritmo euclideo esteso, trovare l'insieme delle (cioè: di tutte le) soluzioni delle equazioni congruenziali: $2000000055x\equiv_{100} 11$; $2000000055x\equiv_{100} 15$; $100x\equiv_{55} 15$; $300x\equiv_{55} 45$; $80x+2 \equiv_{120} 6x+27$; $80x+1 \equiv_{120} 6x+27$.
5. Autoassegnarsi e risolvere un gran numero di equazioni congruenziali a caso.
6. Usando l'algoritmo euclideo esteso, trovare, ove possibile, soluzioni delle equazioni diofantee $14x+6y=1$, $14x+6y=4$, $140x+60y=20$. Di una di esse, trovare tre diverse soluzioni.
7. Bertrando deve dare a Filiberto un certo numero $n$ di chiodi (non uno di più, non uno di meno) di un certo tipo, ma questi chiodi sono disponibili solo in confezioni da 36 e da 120 chiodi, che non vanno assolutamente aperte. Sapendo che Bertrando e Filiberto hanno a disposizione quantità illimitate di entrambi i tipi di queste confezioni, per quali valori di $n$ è possibile che Bertrando dia a Filiberto i chiodi richiesti (senza aprire nessuna confezione)? È, ad esempio, possibile farlo per $n=100$? E, nel caso, in che modo? E per $n=300$?
8. Siano $a,b,m\in\Z$. Verificare che $a\equiv_m b$ implica $a\equiv_t b$ per qualsiasi divisore $t$ di $m$.
9. Sia $n$ un numero intero positivo. Come è noto, $n$ si può scrivere in base 10 rappresentandolo con la stringa “$a_t a_{t-1} a_{t-2}\dots a_2 a_1 a_0$”, dove $t\in\N^*$ e ciascuno degli $a_i$ (le 'cifre' di $n$) è un numero naturale minore di 10, intendendo con questo $n=\sum_{i=0}^t a_i 10^i$. Provare, approfondendo quanto visto a lezione:
   • $n\equiv_9 \sum_{i=0}^t a_i$;
   • $n$ è divisibile per 9 se e solo se la somma delle sue cifre è divisibile per 9;
   • $n$ è divisibile per 3 se e solo se la somma delle sue cifre è divisibile per 3;
   • giustificare il 'criterio di divisibilità per 3' e la 'prova del 9' che vengono insegnati nella scuola elementare;
   • $n\equiv_{11} \sum_{i=0}^t (-1)^i a_i$.
   Usare quanto visto sopra per calcolare (a mente) $\rest(72543618991175,9)$ e $\rest(72543618991175,3)$, e poi $\rest(626\cdot 3125,3)$.
10. Svolgendo i calcoli a mente, verificare che $\rest(2^{3665},7)$ è uguale a $4$ (suggerimento: $\rest(2^3,7)=\dots$).

12/12

Questa lezione segue, salvo poche omissioni, il contenuto delle mie note sui polinomi. Dettaglio su una notazione: nelle note l'insieme degli interi positivi è indicato con $\N^+$.

Nel resoconto di questa lezione $R$ indica sempre un anello commutativo unitario.

Successione dei coefficienti di un polinomio, polinomi costanti, grado e coefficiente direttore di un polinomio, polinomi monici. Grado di somma, differenza e prodotto tra due polinomi. Se il polinomio $f\in R[x]$ ha coefficiente direttore cancellabile (in $R$), allora $f$ stesso è cancellabile in $R[x]$ ed inoltre vale per $f$ ed un qualsiasi polinomio $g\in R[x]$ la regola di addizione dei gradi: $\nu(fg)=\nu(f)+\nu(g)$ e $\cd(fg)=\cd(f)\cd(g)$. Di conseguenza: $R[x]$ è un dominio di integrità se e solo se lo è $R$; se questo accade vale sempre, in $R[x]$, la regola di addizione dei gradi e $\U(R[x])=\U(R)$. Esempi che mostrano come queste due proprietà possano non valere se $R$ non è integro.

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. Se $R$ è un campo è sicuramente possibile effettuare la divisione per un qualsiasi polinomio non nullo. Di conseguenza, nell'anello dei polinomi su un campo si può eseguire l'algoritmo euclideo per la ricerca di un MCD e vale il Teorema di Bézout (informazione: questo teorema non vale in $\Z[x]$).

Applicazione polinomiale definita da un polinomio. Radici di un polinomio. Ogni radice di un polinomio è radice anche di ogni suo multiplo.

Teorema del resto: se $R$ è un anello commutativo unitario, $f\in R[x]$ e $c\in R$, allora il resto nella divisione di $f$ per $x-c$ è $f(c)$. Come conseguenza, Teorema di Ruffini: $c$ è radice di $f$ se e solo se $x-c$ divide $f$. Teorema di Ruffini generalizzato e sue conseguenze: se $R$ è dominio di integrità unitario si ha: (1) se $0_R\ne f\in R[x]$, allora $f$ ha al più $\nu(f)$ radici in $R$; (2) principio di identità dei polinomi: se, inoltre, $R$ è infinito due polinomi in $R[x]$ coincidono se e solo se definiscono la stessa applicazione polinomiale. Controesempi mostrano che questi risultati non valgono per anelli commutativi booleani né per anelli finiti.

Anelli fattoriali. Teorema (non dimostrato): se $R$ è un anello fattoriale, anche $R[x]$ è un anello fattoriale. Associati in $R[x]$, con particolare riferimento al caso in cui $R$ 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 R[x]\setminus R$ si fattorizza come prodotto di un invertibile (il suo coefficiente direttore) e polinomi irriducibili monici, in modo unico a meno dell'ordine dei fattori.

Caratterizzazione dei polinomi irriducibili nel'anello dei polinomi su un campo; esistenza di radici ed irriducibilità.

Descrizione dei polinomi irriducibili sul campo reale e sul campo complesso (segue da questa descrizione che i polinomi di grado dispari in $\R[x]$ hanno sempre radici in $\R$).

Polinomi in $\Q[x]$. Ciascuno di essi è associato (in $\Q[x]$) ad un polinomio a coefficienti interi, che ha quindi le stesse radici e fattorizzazioni in irriducibii essenzialmente uguali a quelle del polinomio originale. 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. I risultati in questo paragrafo non sono stati dimostrati.

Esercizi proposti:

1. Per ogni numero primo positivo $p$, sia $f_p$ il polinomio $\overline{22}x^5+\bar 8 x^4 - \bar7x^2+\bar 3$ a coefficienti nel campo $\Z_p$. Stabilire, per ogni primo $p$, qual è il grado di $f_p$. Per quali primi $p$ il polinomio $f_p$ è monico?
2. Se possibile, trovare un polinomio di coefficiente direttore 340 che sia associato in $\Q[x]$ a $3x^2-1$.
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 di $f_n$ nei casi rimanenti.
4. Vero o falso: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.
5. Siano $f$ e $g$ polinomi su un anello commutativo unitario $R$. Verificare che se $f$ e $g$ sono associati in $R[x]$, allora $f$ e $g$ hanno le stesse radici in $R$.
6. Sia $R$ un anello commutativo unitario. Verificare che l'anello dei polinomi $R[x]$ è infinito (Suggerimento: se $n$ e $m$ sono numeri naturali distinti, si può avere $x^n=x^m$?).
7. Provare che, qualunque sia l'anello commutativo $A$, se $f$ è un polinomio monico in $A[x]$, $f$ è cancellabile ma non invertibile in $\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.
8. 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]$).
9. Sia $f=x^4-4\in \Z[x]$. Scrivere $f$ come prodotto di polinomi monici irriducibili in $\Q[x]$ e come prodotto di polinomi irriducibili monici in $\R[x]$.
10. Utilizzando il teorema di Ruffini come punto di partenza, scrivere il polinomio $x^5-x\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$.
11. Utilizzando il teorema di Ruffini come punto di partenza, scrivere il polinomio $f=\bar 2 x^4+x+\bar 1\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Trovare poi l'associato monico di $f$ in $\Z_5[x]$.
12. Svolgere, almeno in parte, gli esercizi nr. 1, 2, 3 e 8 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo.
13. Il polinomio $35x^{11}-6x^7+3x+15$ è irriducibile in $\Q[x]$? E $x^3+4$?
14. 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$.
15. 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$.
16. 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]$.
17. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
18. 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, 6 dal compito di maggio 2018.

14/12

Minoranti e maggioranti di parti in un insieme ordinato $(S,\rho)$. Esempi ed osservazioni; per $A,B\subseteq S$ e $a\in S$ si ha $\minor_{(S,\rho)}(A\cup B)=\minor_{(S,\rho)}(A)\cap\minor_{(S,\rho)}(B)$; inoltre $a$ è minimale in $S$ se e solo se $\minor_{(S,\rho)}(\set a)=\set a$, valgono ovviamente gli enunciati duali. Tra gli esempi: in $(\N,|)$ i minoranti (risp. maggioranti) di una parte $X$ sono gli insiemi dei divisori (risp. multipli) comuni degli elementi di $X$; se $A$ è un insieme e $X\subseteq\P(A)$, i minoranti ed i maggioranti di $X$ in $(\P(A),\subseteq)$ sono, rispettivamente i sottoinsiemi di $\bigcap X$ (o di $A$ se $X=\vuoto$) ed i sottoinsiemi di $A$ contenenti $\bigcup X$.

Estremo inferiore $\inf_{(S,\rho)}(X)=\max(\minor_{(S,\rho)}(X))$ ed estremo superiore $\sup_{(S,\rho)}(X)=\min(\maggior_{(S,\rho)}(X))$ di una parte $X$ di un insieme ordinato $(S,\rho)$. Diversi esempi. In particolare: gli estremi inferiori e superiori in $(\N,\mid)$ ed in $(\P(A),\subseteq)$ per un insieme $A$ sono descritti da MCD e mcm nel primo caso, da intersezione ed unione nel secondo. Osservazioni (valgono ovviamente anche gli enunciati duali): per ogni $a\in S$ e $X\sseq S$ sono equivalenti: $a=\min X$; $a\in X \cap \minor_{(S,\rho)}(X)$; $a=\inf_{(S,\rho)}(X)\in X$.

Reticoli. Definizione ed esempi. Il duale di un reticolo è necessariamente un reticolo; principio di dualità per reticoli. Sono reticoli tutti gli insiemi totalmente ordinati; $(\N,\mid)$ e, per ogni insieme $A$, $(\P(A),\subseteq)$. 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. Se due parti $A$ e $B$ di un reticolo hanno estremi inferiori $a=\inf A$ e $b=\inf B$, allora anche $A\cup B$ ha estremo inferiore, precisamente $\inf(\set{a,b})$ (e vale l'enunciato duale). Di conseguenza, ogni parte finita e non vuota di un reticolo ha estremo inferiore ed estremo superiore.

Le due operazioni (binarie) reticolari (meet/inf/$\land$ e join/sup/$\lor$). Loro proprietà algebriche (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. Sottoreticoli. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo. Intervalli chiusi.

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

Reticoli booleani. Algebre di Boole. Equivalenza tra queste due nozioni. Leggi di De Morgan in algebre di Boole. Sottoalgebre di Boole.

Costruzione di un'anello booleano a partire da un'algebra di Boole (ovvero, da un reticolo booleano) e construzione, inversa, di un'algebra di Boole a partire da un anello booleano (non sono state effettuate, se non per cenni, le verifiche). Senza verifica: i sottoanelli unitari di un anello booleano sono le sottoalgebre della corrispondente algebra di Boole. Equivalenza tra lo studio dei reticoli booleani, delle algebre di Boole, degli anelli booleani; coincidenza delle corrispondenti nozioni di isomorfismo. Di conseguenza: 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 (ed enunciati analoghi per le algebre di Boole).

Richiamo sulle funzioni caratteristiche. Per ogni $n\in\N^*$, l'anello (booleano) $\Z_2^n$ delle $n$-ple di elementi di $\Z_2$, ovvero delle applicazioni da $S=\set{1,2,\dots,n}$ a $\Z_2$. Identificazione delle "stringhe di zeri e uno" di fissata lunghezza $n$ con gli elementi di $\Z_2^n$. 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.

Oltre che al libro di testo, per il contenuto di questa lezione è possibile fare riferimento alle note sulle strutture booleane.

Esercizi proposti:

1. Verificare in dettaglio che se $a$ e $b$ sono elementi di un reticolo $(S,\rho)$ e $a\mathrel\rho b$, allora l'intervallo chiuso $\{x\in S\mid a\mathrel\rho x$ e $x\mathrel\rho b\}$ è un sottoreticolo di $(S,\rho)$.
2. Si disegni il diagramma di Hasse dell'insieme dei divisori di $30$, stabilendo se si tratta di un reticolo, di un reticolo distributivo, di un reticolo complementato, di un reticolo booleano. Se possibile, trovarne un sottoreticolo di cardinalità 7 e/o un sottoreticolo di cardinalità 5.
3. Esercizi 5, 6 e 7 da relazioni binarie, intendendo 'algebra di Boole' come sinonimo di 'reticolo booleano'.
4. Per ciascuno dei seguenti insiemi, ordinati per divisibilità (in $\N$), disegnare il diagramma di Hasse e decidere se si tratta o meno di un reticolo ed eventualmente di un sottoreticolo di $(\N,|)$: $\set{n\in\N\mid n\le 10}$, $\set{2^n\mid n\in\N}$, $\set{n\in\Div_\N(60)\mid n \text{ è pari}}$, $\set{1,2,3,5,45,60,900}$.
5. Verificare che una parte non vuota di un'algebra di Boole ne è una sottoalgebra se e solo se è chiusa per le due operazioni reticolari (cioè forma un sottoreticolo) e contiene come elemento il complemento di ogni suo elemento.
6. Verificare le leggi di De Morgan nelle algebre di Boole (scelti comunque elementi $a$, $b$ nell'algebra, $(a\land b)'=a'\lor b'$ e $(a\lor b)'=a'\land b'$).
7. Verificare completamente la correttezza della costruzione di un'algebra di Boole a partire da un anello booleano.
8. Costruire un esempio di reticolo complementato con un sottoreticolo non complementato. Suggerimento: cercare una catena nel reticolo delle parti di un insieme.
9. Costruire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi e tutti gli altri elementi hanno esattamente un complemento.
10. Di un reticolo $L$ sappiamo che è complementato e che ha esattamente 675 elementi. Possiamo stabilire se è distributivo?
11. Degli insiemi ordinati discussi nei primi due esercizi della lezione del 28/11, dire quali sono reticoli e, per quelli che lo sono, se sono distributivi e e se sono complementati.
12. Stabilire per quali $n\in\set{0,15,16,20,15\cdot 77}$ il reticolo dei naturali divisori di $n$ (ordinato per divisibilità in $\N$) è booleano.
13. Svolgere gli esercizi nr. 3 dai compiti di marzo 2014 e di novembre 2018. Esercizi su insiemi ordinati e reticoli si trovano, del resto, in ogni prova d'esame.

17/12

Cenni informali a 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.

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.

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.

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.

Numero di vertici e di lati in un albero finito. Sia $G$ un multigrafo finito, con insiemi $V$ di vertici e $L$ di lati e con esattamente $k$ componenti connesse. Allora $|L|\ge |V|-k$ (dunque, $|L|\ge |V|-1$ se $G$ è connesso), e vale $|L|=|V|-k$ se e solo se $G$ è una foresta. Sono equivalenti: (1) $G$ è un albero; (2)) $G$ è connesso e $|V|=|L|+1$; (3) $G$ è una foresta e $|V|=|L|+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. Identificare 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$.