21/9

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

Introduzione molto informale alle nozioni di linguaggio, formula, termine, proposizione, sintassi, semantica. Introduzione ai connettivi proposizionali, descritti solo semanticamente, cioè in termini di valori di verità. Tavole (o tabelle) di verità. Il connettivo unario di di negazione (NOT, $\lnot$).

Per il (molto ridotto) contenuto di questa lezione e delle prossime (certamente più consistenti), si veda Logica rudimentale.

Avvertenza: come indicato nell'avviso nella pagina principale del corso, non faremo lezione lunedì 26. La lezione di venerdì 23 si terrà invece regolarmente.

Esercizi proposti (ha senso svolgerli solo se non si consultano preventivamente le note o il libro di testo):

1. Scrivere una tavola di verità che descriva il connettivo AND.
2. Riflettere su cosa esprima il connettivo descritto dalla tavola di verità che segue:

   $p$	$q$	$p\mathbin{\text{?}}q$
   $V$	$V$	$V$
   $V$	$F$	$F$
   $F$	$V$	$F$
   $F$	$F$	$V$

23/9

Nella prima parte delle lezione sono stati rapidamente discussi gli esercizi dalla lezione precedente e sono state date ulteriori informazioni su corso ed esami.

I connettivi di negazione, congiunzione (AND, $\land$), disgiunzione inclusiva (OR, $\lor$) e disgiunzione esclusiva ($\xor$). Il connettivo di congiunzione negata ($\nand$). Uso di questi connettivi ed ambiguità nel linguaggio quotidiano. Il connettivo bicondizionale ('doppia implicazione', 'se e solo se', $\shiff$). Forme proposizionali e loro tavole di verità; esempi. Forme proposizionali logicamente equivalenti tra loro.

Tautologie, contraddizioni, forme contingenti Alcuni esempi di tautologie tra cui i principi del terzo escluso e di non contraddizione; doppia negazione; tautologie di iteratività (o idempotenza), commutatività, associatività; distributività per i connettivi $\land$ e $\lor$.

Connettivo condizionale (implicazione, $\implica$). Alcune tautologie: negazione di una implicazione, implicazione come disgiunzione, legge di contrapposizione, legge della doppia implicazione. Espressioni verbali usate per esprimere implicazioni o equivalenze. Primo cenno alle tautologie di De Morgan.

Avvertenza (meglio abbondare): come indicato in un avviso nella pagina principale del corso, non faremo lezione lunedì 26.

Esercizi proposti:

1. Verificare che sono tautologie le forme che a lezione sono state indicate come tautologie senza dimostrarlo.
2. Decidere se la forma proposizionale $(p\nand (q\nand r))\iff ((p\nand q)\nand r)$ è una tautologia.
3. Gli esercizi nella prima parte di Logica rudimentale sono tutti utili; consiglio di provare, in particolare, gli esercizi da B2 a B5, tutti i C, E1, E2, E4, E6.
4. Negare le frasi "se piove mi bagno", "se piove non mi bagno", "se piove, mi bagno e mi ammalo".

28/9

Discussione di diversi esercizi dalla lezione precedente.

Ancora sulle tautologie di De Morgan. Altre tautologie: transitività dell'implicazione, varie negazioni del bicondizionale, tautologie di associatività per $\shiff$ e $\xor$, distributività di $\land$ rispetto a $\xor$.

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

Introduzione alla logica dei predicati. Variabili e loro sostituzioni. I quantificatori universale ed esistenziale. Occorrenze libere ed occorrenze vincolate di variabili. Proposizioni (o formule chiuse). Predicati. Nelle sostituzioni di termini a variabili vengono sostituite solo le occorrenze libere delle variabili.

Quantificatori ristretti: il caso del quantificatore universale. Una proposizione introdotta da un quantificatore universale ristretto ad una condizione falsa è certamente vera.

Oltre a Logica rudimentale, può essere utile consultare tavola dei connettivi binari ed esempi di tautologie.

Esercizi proposti:

1. Esercizi D, E3, E5, F1, G2, G3 da Logica rudimentale.
2. Verificare le tautologie in esempi di tautologie.
3. Abbiamo provato la distributività di $\land$ rispetto a $\xor$. Verificare che $\lor$ non è distributivo rispetto a $\xor$, vale a dire: $\big(p\lor (q\xor r)\big)\iff \big((p\lor q)\xor (p\lor r)\big)$ non è una tautologia. Analogamente, $\lor$ è distributivo rispetto a $\shiff$? Ovvero: $\big(p\lor (q\shiff r)\big)\iff \big((p\lor q)\shiff (p\lor r)\big)$ è una tautologia?
4. Negare: “Se esco di casa o mi affaccio al balcone, vedo Maria e Franco”.
5. Negare la forma proposizionale $(p\lor q)\implica (r\land s)$.

30/9

Discussione di esercizi dalla lezione precedente.

Quantificatori ristretti: il caso del quantificatore universale.

Alcune regole della logica dei predicati (come in Logica rudimentale), tra esse: negazione di formule con quantificatori (anche ristretti). Formule con più quantificatori; comparazione tra formule del tipo $\forall x(\exists y(\dots))$ e del tipo $\exists y(\forall x(\dots))$.

Il quantificatore $\exists!$.

Introduzione informale alla nozione di insieme. Il simbolo binario '$\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à. Inclusione tra insiemi. Comparazione tra inclusione ($\sseq$) e appartenenza: è fondamentale distinguere bene tra queste due nozioni. Ad esempio: per ogni $x$ si ha $\vuoto\subseteq x$, quindi in particolare $\vuoto\sseq\vuoto$, ma $\vuoto\notin\vuoto$.

Esercizi proposti:

1. Esercizi H da Logica rudimentale.
2. Verificare che $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)\land x\ne y))$ esprime la negazione di $\exists!x(\phi(x))$. Andrebbe bene anche $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)))$?
3. Negare: Ogni mucca verde mangia cioccolata.
4. Negare: Ogni mese, se non mi arriva la bolletta del gas non la pago.
5. Per assegnati $a,b,c$, sia $x=\set{a,b,c}$. Quanti elementi ha $x$?
6. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\vuoto\sseq\set{1,2,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{2,1,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{4,2,1,3}$.

3/10

Discussione degli esercizi della lezione precedente.

Il singleton $\set x$ di un insieme $x$ (èsempre diverso da $x$). Per ogni insieme $x$ si ha $x\subseteq x$, ma $x\notin x$.

Estensione di un predicato unario; notazione $\set{x\mid \phi(x)}$ per un predicato unario nella variabile $x$. Cenni a problemi fondazionali; l'antinomia di Russell. Presentazione informale degli assiomi di separazione. Non esiste "l'insieme di tutti gli insiemi".

Nozioni insiemistiche e connettivi proposizionali. Comparazione tra i connettivi di equivalenza e implicazione da una parte, le relazioni di uguaglianza e inclusione tra insiemi dall'altra; operazioni insiemistiche binarie di unione, intersezione e differenza simmetrica, ed identità insiemistiche che coinvolgono queste operazioni dedotte da tautologie (di commutatività, associatività, iteratività, distributività) che coinvolgano $\lor$, $\land$, $\xor$. L'operazione binaria di differenza tra insiemi; complemento di un insieme in un insieme che lo contenga e connettivo di negazione. Diverse formule tra quelle in Tautologie ed identità insiemistiche; formule insiemistiche di De Morgan (per terne arbitrarie di insiemi).

Esercizi proposti:

1. Esercizi I4, J1, J3, J4, J5, J6 da Logica rudimentale.
2. Verificare le formule in Tautologie ed identità insiemistiche (ne abbiamo già viste molte a lezione).
3. Siano $a=\set{1,2,3,4,5,6,7}$, $b=\set{5,6,7,8,9}$, $c=\set{0,5,9}$. Elencare gli elementi di: $a\cap b$, $a\ds b$, $b\setminus c$, $(c \setminus b)\ds a$.
4. Quanti elementi ha $\set{\vuoto,\set\vuoto}$. Quanti elementi ha $\set{\N}$? E quanti $\set{\set\N}$? E quanti $\set{\set{\set{\set\vuoto}}}$?
5. Elencare gli elementi di $\P(\vuoto)$, quelli di $\P(\set{\vuoto})$, quelli di $\P(\set{1,2})$ quelli di $\P(\set{1,2,3})$.
6. Dimostrare che per ogni $a,b$ sono equivalenti: (1) $a\sseq b$; (2) $a\cap b=a$; (3) $a\cup b=b$; (4) $a\setminus b=\vuoto$; (5) $a\ds b=b\setminus a$.

5/10

Discussione di diversi esercizi della lezione precedente.

Diagrammi di (Euler-)Venn. Diagrammi di Venn generici e loro uso per dimostrare formule insiemistiche (di uguaglianza o di inclusione) universali o per la costruzione di controesempi (un diagramma di Venn per un certo insieme $V$, in cui quindi ogni elemento di $V$ sia rappresentato da un'area, è generico quando, per ogni parte non vuota $P$ di $V$ nel diagramma appare, non vuota, un'area che descriva gli oggetti appartenenti a ciascuno degli elementi di $P$ ed a nessuno degli elementi di $V\setminus P$). Esempi di diagrammi generici per coppie e per terne di insiemi. Diversi esempi di uso di questi diagrammi; tra questi: distributività da destra della differenza insiemistica rispetto ad unione e intersezione (binarie); per ogni $a$ e $b$, si ha che $a\ds b$ coincide con $(a\cup b)\setminus (a\cap b)$ e con $(a\setminus b)\cup(b\setminus a)$.

L'unione unaria $\bigcup a=\set{x\mid \exists b\in a(x\in b)}$ di un insieme $a$. Ad esempio: $\bigcup\vuoto=\vuoto$. Riduzione dell'unione binaria all'unione unaria: per ogni $a,b$ si ha $a\cup b=\bigcup \set{a,b}$. L'intersezione (unaria) $\bigcap a=\set{x\mid \forall b\in a(x\in b)}$ di un insieme non vuoto $a$. Discussione sul motivo per cui $\bigcap \vuoto$ non è definito.

Esercizi proposti:

1. Calcolare, per un arbitario insieme $a$, $a\ds a$ e $a\ds\vuoto$.
2. Rappresentare, in un diagramma di Venn generico, il termine insiemistico $a\cap(b\ds c)$.
3. Svolgere l'esercizio 2 dal compito del 13 novembre 2013.
4. Spiegare perché questo non è un diagramma di Venn generico mentre quest'altro lo è.
5. Rappresentare, in un diagramma di Venn generico, i termini insiemistici $a\cup(b\cap c)$ e $a\cap(b\cup c)$. Decidere se vale una delle formule $\forall a,b,c \big(a\cup(b\cap c)\sseq a\cap(b\cup c)\big)$ e $\forall a,b,c \big(a\cup(b\cap c)\supseteq a\cap(b\cup c)\big)$. Ripetere l'esercizio per i termini insiemistici $a\setminus(b\setminus c)$ e $(a\setminus b)\setminus c$.
6. Verificare che, per ogni $a,b$, si ha $a\cap b=\bigcap\set{a,b}$.
7. Calcolare, oltre a $\bigcup \vuoto$, $\bigcup\set{\vuoto}$, e poi $\bigcup\set{a}$ e $\bigcap\set{a}$ per un arbitrario insieme $a$.
8. Calcolare $\bigcup A$ e $\bigcap 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 infinite di $\N$; (3) $A=\set{x\subseteq\N\mid 13\notin x}$; (4) $A=\set{x\subseteq\N\mid 13\in x}$; (5) $A=\big\{\set{124,n}\mid n\in\N\big\}$; (6) $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$.

7/10

Lunga discussione di esercizi dalla lezione precedente; approfondimenti sui diagrammi (generici) di Venn.

Scritture alternative per rappresentare insemi e per rappresentare unioni o intersezioni unarie: $\set{t(x,y,z,\dots)\mid \phi(x,y,z,\dots)}$, dove $t$ è un termine e $\phi$ un predicato nelle variabili $x,y,z$ è un'abbreviazione per $\set{a\mid \exists x,y,z,\dots(\phi(x,y,z,\dots)\land a=t(x,y,z,\dots)}$; $\bigcup_{\phi(x,y,z,\dots)}t(x,y,z,\dots)$ e $\bigcap_{\phi(x,y,z,\dots)}t(x,y,z,\dots)$ sono l'unione e l'intersezione di $\set{t(x,y,z,\dots)\mid \phi(x,y,z,\dots)}$ (ad esempio, $\bigcup_{x\in a}x=\bigcup a$).

Formule generalizzate di associatività, distributività e De Morgan per unione e intersezione unarie: per ogni $a$ e $b$, se $a\ne\vuoto\ne b$, $\big(\bigcap a\big)\cap \big(\bigcap b\big)=\bigcap\set{x\cap y\mid (x\in a) \land (y\in b)}$, $\big(\bigcup a\big)\cup \big(\bigcup b\big)=\bigcup\set{x\cup y\mid (x\in a) \land (y\in b)}$, $a\cap \bigcup b=\bigcup_{x\in b}(a\cap x)$, $a\cup \bigcap b=\bigcap_{x\in b}(a\cup x)$, $a\setminus \bigcup b=\bigcap_{x\in b}(a\setminus x)$ e $a\setminus \bigcap b=\bigcup_{x\in b}(a\setminus x)$.

Coppie ordinate e loro proprietà caratteristica. Terne ordinate ed analoga proprietà caratteristica. Prodotto cartesiano tra due insiemi.

Esercizi proposti:

1. Dimostrare che, per ogni $x$ e $y$:
   1. $x\times y=\vuoto$ se e solo se uno tra $x$ e $y$ è vuoto;
   2. $x\times y=y\times x$ se e solo se o $x=y$ oppure uno tra $x$ e $y$ è vuoto.
2. (per i più curiosi). Provare che per ogni $a$, $b$, $c$ e $d$, si ha $\set{\set a,\set{a,b}}=\set{\set c,\set{c,d}}$ se e solo se $a=c$ e $b=d$. Tenendo conto di questa proprietà, si può dunque dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. In effetti, questa è la definizione di coppia ordinata proposta da Kuratowski (ma ce ne sono altre!).
3. Elencare gli elementi di $\set{1,2}\times \set{1,3}$, quelli di $\set{1,3}\times \set{1,2}$ e quelli di $(\set{1,2}\times \set{1,3})\cap (\set{1,3}\times \set{1,2})$.
4. 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$.

10/10

Discussione di esercizi della lezione precedente.

Corrispondenze tra due insiemi. Grafico di una corrispondenza. Relazioni binarie in un insieme. Notazioni: per insiemi $a$ e $b$, $\Corr(a,b)$ indica l'insieme delle corrispondenze da $a$ a $b$, $\Rel(a)$ quello delle relazioni binarie in $a$ (dunque: $\Corr(a,b)=\set{(a,b,g)\mid g\sseq a\times b}$ e $\Rel(a)=\Corr(a,a)$).

Alcuni modi di descrivere corrispondenze (attraverso il grafico, diagrammi, tabelle, condizioni di appartenenza al grafico). Esempi.

Prodotto relazionale tra corrispondenze; sua associatività.

Applicazioni (o funzioni) tra due insiemi; dominio e codominio (notazione: $\Map(a,b)$ è l'insieme delle applicazioni di dominio $a$ e codominio $b$). L'immagine $f(x)$ di un elemento $x$ del dominio di $f$ (è un elemento del codominio).

Il prodotto relazionale tra due applicazioni $f\colon a\to b$ e $g\colon b\to c$ è ancora un'applicazione (da $a$ a $c$): l'applicazione composta $g\circ f$.

Esercizi proposti:

1. Siano $a=\set{1,2,3}$ e $b=\set{0,5,10}$. Sia poi $\rho$ la corrispondenza da $a$ a $b$ definita da: per ogni $x\in a$ e $y\in b$ si ha $x\mathrel\rho y\iff x^2\le y$. Elencare gli elementi del grafico di $\rho$. Rappresentare poi $\rho$ con un diagramma con frecce e con una tabella. $\rho$ è un'applicazione?
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$.
3. Siano $\alpha$ e $\beta$ le corrispondenze da $\Z$ a $\P(\Z)$ definite ponendo, per ogni $n\in\Z$ e $x\in \P(\Z)$, $\quad n\mathrel{\alpha}x\iff n\in x\quad$ e $\quad n\mathrel{\beta}x\iff n\notin x$. Sia poi $\gamma$ la relazione di inclusione in $\P(\Z)$, cioè la relazione binaria in $\P(\Z)$ definita ponendo, per ogni $x,y\in\P(\Z)$, $x\mathrel{\gamma}y\iff x\sseq y$. Descrivere $\alpha\gamma$ e $\beta\gamma$.
4. Elencare gli elementi del grafico della corrispondenza $\rho$ da $\N$ a $\Z$ così definita: $\forall a\in \N\big(\forall b\in\Z\big(a\mathrel\rho b\iff (b^2\lt 6 \land a\le b)\big)\big)$. Questa corrispondenza è un'applicazione?
5. Sia $a$ un insieme, e sia $\Delta_a=\set{(x,x)\mid x\in a}$. Stabilire se la relazione binaria in $a$ di grafico $\Delta_a$ è un'applicazione.
6. Siano $a$ e $b$ insiemi e sia $x$ un elemento di $b$. Stabilire se la corrispondenza da $a$ a $b$ di grafico $a\times\set x$ è un'applicazione.
7. Indicato con $\R^+_0$ l'insieme dei numeri reali non negativi (cioè: $\R^+_0=\set{a\in\R\mid a\ge 0}$), si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • $\alpha$ da $\R$ a $\R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\beta$ da $\R^+_0$ a $\R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\gamma$ da $\R^+_0$ a $\R^+_0$, di grafico $\set{(a,b)\in\R\times\R^+_0\mid a=b^2}$;

12/10

Discussione degli esercizi della lezione precedente.

Descrizioni di applicazioni (o, più in generale, di corrispondenze) nella forma $\dots\in a\mapsto\dots\in b$. Il problema della "buona definizione" di un'applicazione. Alcuni esempi di corrispondenze che non sono applicazioni (per parlarne abbiamo introdotto, per ogni $a$ e per ogni numero naturale $k$, l'insieme $\P_k(a)$ delle $k$-parti di $a$, cioè delle parti di $a$ con esattamente $k$ elementi).

Alcuni tipi di applicazioni: applicazioni costanti; l'applicazione identica $\id_a\colon x\in a\mapsto x\in a$ in un insieme $a$; più in generale: l'immersione $x\in b\mapsto x\in a$ in un insieme $a$ di una sua parte $b$. Restrizioni (e, viceversa, prolungamenti) di applicazioni (ad esempio, le immersioni sono restrizioni di applicazioni identiche).

Descrizione esplicita di applicazioni composte. Restrizioni come composte con immersioni ed altri esempi.

L'immagine $\im f=\set{f(x)\mid x\in a}$ dell'applicazione $f\colon a\to b$ (è una parte del codominio $b$ di $f$); applicazioni suriettive; diverse forme della definizione di suriettività; esempi.

La composta tra due applicazioni (componibili) suriettive è certamente suriettiva.

Esercizi proposti:

1. Date le applicazioni $f\colon n\in\N\mapsto 2n+3\in\N$ e $g\colon n\in\N\mapsto 6n\in\N$, descrivere esplicitamente $g\circ f$ e $f\circ g$. Quali tra queste applicazioni sono suriettive?
2. Vero o falso?
   1. Ogni applicazione ha una restrizione costante.
   2. Se $f$ e $g$ sono applicazioni componibili e $f$ è costante, allora $f\circ g$ è costante.
   3. Se $f$ e $g$ sono applicazioni componibili e $g$ è costante, allora $f\circ g$ è costante.
   4. Per ogni scelta degli insiemi $a$ e $b$ ed ogni applicazione $f\colon a\to b$, $f\circ\id_a=f$.
   5. Per ogni scelta degli insiemi $a$ e $b$ ed ogni applicazione $f\colon a\to b$, $\id_b\circ f=f$.
3. Elencare gli elementi del grafico della corrispondenza $\rho$ da $\N$ a $\Z$ così definita: $\forall a\in \N\big(\forall b\in\Z\big(a\mathrel\rho b\iff (b^2\lt 6 \land a\le b)\big)\big)$. Questa corrispondenza è un'applicazione?
4. Quali tra queste sono applicazioni ben definite? (Detto diversamente: quali delle corrispondenze qui indicate sono applicazioni?) Qui $P=\P(\Z)\setminus\set\vuoto$ è l'insieme delle parti non vuote di $\Z$, come sempre $\P_2(\Z)$ è l'insieme delle parti di $\Z$ che hanno esattamente due elementi.
   1. $n\in\Z\mapsto n^2/2\in\Z$;
   2. $n\in\Z\mapsto \set {n,2n}\in\P(\Z)$;
   3. $n\in\Z\mapsto n^2/2\in\Q$;
   4. $\set{a,b}\in\P_2(\Z)\mapsto a+b\in\N$;
   5. $\set{a,b}\in\P_2(\Z)\mapsto a+b\in\Z$;
   6. $\set{a,b}\in\P_2(\N)\mapsto a^b\in\N$;
   7. $(a,b)\in\Z\times\Z\mapsto a-b\in\N$;
   8. $(a,b)\in\Z\times\Z\mapsto a-b\in\Z$;
   9. $(a,b)\in\N\times\N\mapsto a^b\in\N$;
   10. $X\in P\mapsto \min X\in\Z$; (qui $\min X$ è, se esiste, il più piccolo numero appartenente ad $X$).
   11. $X\in P\mapsto \Z\setminus X\in P$;
   12. $X\in \P(\Z)\mapsto X\cap\N\in\P(\N)$;
   13. $X\in \P(\Z)\mapsto X\ds\N\in\P(\N)$.
5. Svolgere gli esercizi nr. 7 e 8 dalla raccolta "per le vacanze di pasqua".

14/10

Discussione di alcuni degli esercizi della lezione precedente. Negazione della suriettività.

Se un'applicazione composta $f\circ g$ è suriettiva, allora $f$ è suriettiva (ma $g$ può non esserlo).

Ridotte di un'applicazione; la ridotta suriettiva di un'applicazione: è quella alla sua immagine.

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$, ponendo $\vecf(c)=\im f_{|c}=\set{f(x)\mid x\in c}$ per ogni $c\in\P(a)$ e $\avecf(c)=\set{x\in a\mid f(x)\in c}$ per ogni $c\in\P(b)$. Diversi esempi. Si ha: $\vecf (\vuoto)=\avecf(\vuoto)=\vuoto$, $\vecf(a)=\im f$, $\,\avecf (b)=\avecf (\im f)=a$. Per ogni $x\in a$, $\vecf(\set x)=\set{f(x)}$, per ogni $y\in b$, $\avecf(\set y)=\set{x\in a\mid f(x)=y}$. Dunque, $f$ è suriettiva se e solo se $\avecf(\set y)\ne\vuoto$ per ogni $y\in b$. Inoltre, per ogni $c\in\P(a)$ si ha $c\sseq\avecf(\vecf (c))$ (e l'inclusione può essere stretta).

Applicazioni iniettive. Negazione dell'iniettività: un'applicazione $f\colon a\to b$ non è iniettiva se e solo se: $\exists x,y\in a$$(x\ne y\land f(x)=f(y))$. Un'applicazione $f\colon a\to b$ è iniettiva se e solo se $|\avecf(\set y)|\le 1$ per ogni $y\in b$; inoltre: se $|a|\lt 2$, $f$ è certamente iniettiva.

Esercizi proposti:

1. Vero o falso?
   1. Ogni applicazione ha una ridotta suriettiva.
   2. Ogni applicazione ha una restrizione iniettiva.
2. Sia $f\colon a\to b$ un'applicazione costante. Esattamente in quali casi $f$ è suriettiva? Ed esattamente in quali casi $f$ è iniettiva?
3. Sia $f\colon x\in\P(\Z)\mapsto x\cup\N\in\P(\Z)$. Descrivere $\vecf(\P(\N))$, $\avecf(\set\vuoto)$ e $\avecf(\P(\set{n\in\Z\mid n\gt-2}))$.
4. Provare che se $f\colon a\to b$ è un'applicazione si ha $\vecf(\avecf (y))=y\cap\im f$ per ogni $y\in\P(b)$. Dedurne: $f$ è suriettiva se e solo se per ogni $y\in\P(b)$ vale $\vecf(\avecf (y))=y$.
5. Siano $f\colon a\to b$ e $g\colon b\to a$ applicazioni. Provare che l'applicazione immagine $(g\circ f)\vec{\phantom 1}3$ definita da $g\circ f$ è $\vecg\circ \vecf$ e che, analogamente, $(g\circ f)\avec{\phantom 1}3=\avecf\circ\avecg$.
6. Provare che per ogni insieme $a$ sia l'applicazione immagine che l'applicazione antiimmagine definite da $\id_a$ coincidono con $\id_{\P(a)}$.
7. Provare che, come accade per le applicazioni, per ogni $a$ e $b$ ed ogni $f\in\Corr(a,b)$, si ha $\id_a f=f\id_b=f$ (stiamo qui facendo uso del prodotto relazionale).
8. Delle applicazioni proposte negli esercizi della lezione scorsa (inclusi quelli dalla raccolta "per le vacanze di pasqua"), stabilire se sono iniettive.
9. L'applicazione $h\colon a\in\Z\mapsto \begin{cases}a+1&\text{se $a$ è pari}\\a+2&\text{se $a$ è dispari}\end{cases}\in\Z$ è iniettiva? Determinare $\im h$.
10. Di ciascuna delle seguenti applicazioni, decidere se sono iniettive e se sono suriettive:
    • $a\colon n\in\N\mapsto n+1 \in\N$
    • $b\colon n\in\Z\mapsto n+1 \in\Z$
    • $c\colon n\in\N\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\N$
    • $d\colon n\in\Z\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\Z$

17/10

Discussione di alcuni degli esercizi della lezione precedente. Le restrizioni delle applicazioni iniettive sono iniettive. Cenno ad un frequente (brutto) errore in cui si cade pretendendo di provare che un'applicazione $f$ è suriettiva come conseguenza del fatto che $\im f$ è contenuto in $\im f$ (!!!!!).

Applicazioni biettive. Ad esempio, lo sono le applicazioni identiche.

Le restrizioni delle applicazioni iniettive sono iniettive. Le composte tra due applicazioni (componibili) iniettive sono certamente iniettive; viceversa, se una composta $g\circ f$ è iniettiva, allora $f$ è iniettiva (ma $g$ può non esserlo). Analogo enunciato per le applicazioni biettive ottenuto da quest'ultimo e dall'analogo enunciato per le applicazioni suriettive. Esempio di un'applicazione biettiva della forma $g\circ f$ tale che $f$ non sia suriettiva e $g$ non sia iniettiva (ecco una versione dell'esempio: $a=\set 1$ e $b=\set{1,2}$; $f$ è l'immersione di $a$ in $b$, $g$ è l'unica applicazione da $b$ ad $a$, cioè la costante $1$. Allora $g\circ f=\id_a$).

Due proprietà formali: associatività della composizione tra applicazioni; neutralità delle applicazioni identiche rispetto al prodotto relazionale (come da esercizi proposti nelle ultime due lezioni: se $f\colon a\to b$ è una corrispondenza, allora $\id_a f=f \id_b=f$).

Sezioni e retrazioni di un'applicazione $f\colon a\to b$: un'applicazione $g\colon b\to a$ è una sezione di $f$ se e solo se $f\circ g=\id_b$, è una retrazione di $f$ se e solo se $g\circ f=\id_a$ (cioè se e solo se $f$ è una sezione di $g$); tutte le sezioni sono inettive, tuttte le retrazioni sono suriettive. Un'applicazione $f\colon a\to b$ è suriettiva se e solo se ammette sezioni, è iniettiva se e solo se ammette retrazioni oppure $a=\vuoto$.

Esempi di sezioni e retrazioni.

Nota: esistono in questo sito delle note su sezioni e retrazioni. Chi volesse leggerne almeno una parte tenga presente che molto del materiale lì contenuto non fa parte del nostro programma e le notazioni lì usate non sono quelle seguite nel corso. 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: $x^f$ piuttosto che $f(x)$ come nel corso.

Esercizi proposti:

1. Siano $a=\set{0,1,2,3,4,5,6}$ e $b=\set{2,3,4}$. Determinare tre retrazioni o tre sezioni dell'applicazione $\alpha\colon x\in b\mapsto x+1\in a$ e tre retrazioni o tre sezioni dell'applicazione $\beta\colon a\to b$ definita da $\beta(0)=\beta(1)=2$, $\beta(2)=3$ e $\forall x\in a\setminus\set{0,1,2}$$(\beta(x)=4)$.
2. Fornire quattro diverse retrazioni dell'immersione di $\N$ in $\Z$.
3. Di ciascuna delle applicazioni nell'ultimo degli esercizi della lezione scorsa, fornire, ove ne esistano, sezioni e retrazioni, se possibile più di una.

19/10

Discussione degli esercizi della lezione precedente.

Inverse di un'applicazione (cioè: applicazioni che ne siano sia sezioni che retrazioni). 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$.

(Notazione: si indica con $f^{-1}$ l'inversa dell'applicazione biettiva $f$. In alcuni contesti, ma non nel nostro corso, si usa indicare con lo stesso simbolo l'applicazione antiimmagine $\avecf$ di $f$; non confondere MAI queste due applicazioni tra loro.)

Teorema: per un'applicazione $f\colon a\to b$ le affermazioni che seguono sono equivalenti: (1) $f$ è biettiva; (2) $f$ ha una sezione ed una retrazione; (3) $f$ ha un'inversa; (4) $f$ ha una ed una sola sezione; (5) $\forall y\in b(\exists! x\in a(f(x)=y))$; (6) $\forall y\in b(|\avecf(\set y)|=1)$.

Esempi di inverse; vari metodi che permettono di riconoscere che un'applicazione sia biettiva. Osservazione: per un'applicazione $f\colon a\to a$ (di dominio e codominio uguali), poniamo $f^2=f \circ f$, $f^3=f \circ f\circ f$ e, più in generale, per ogni intero $n>1$, $f^n=f\circ f\circ \cdots\circ f$, composizione con $n$ fattori (tutti uguali a $f$). Se $f^n=\id_a$, allora $f$ è biettiva, con inversa $f^{n-1}$ (ad esempio, $f=f^{-1}$ se e solo se $f^2=\id_a$).

Osservazioni sull'importanza della nozione di invertibilità

Operazioni binarie (ovunque definite) in un insieme. Definizione ed esempi. Operazioni binarie commutative ed associative. Cenno ai teoremi di associatività e di commutatività. Nozione di struttura algebrica. Diversi esempi di operazioni associative e non, commutative e non. Tra queste: l'operazione di composizione nell'insieme $T(a)=\Map(a,a)$ delle trasformazioni di $a$.

Elementi neutri a sinistra e a destra; elementi neutri. Alcuni esempi.

Esercizi proposti:

1. Tra le applicazioni $f\colon n\in\Z\mapsto 2n-1\in\Z$, $g\colon n\in\Z\mapsto 2n-1\in\Q$, $h\colon n\in\Q\mapsto 2n-1\in\Q$, $k\colon n\in\Z\mapsto 8-n\in\Z$ si dica quali sono biettive e di queste si determinino le inverse. Fare lo stesso per l'applicazione $\alpha$ da $a=\set{1,2,3,4}$ ad $a$ che manda 1 in 3, 2 in 4, 3 in 2 e 4 in 1.
2. Si trovi l'inversa dell'applicazione al punto (ii) dell'esercizio 7 di quelli per le vacanze di pasqua.
3. Si verifichi che l'applicazione $n\in\Z\mapsto\begin{cases}2n-1,&\text{se }n\gt0\\-2n,&\text{se }n\le0\end{cases}\in\N$ è biettiva.
4. Si verifichi che l'applicazione $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$ è biettiva.
5. Per caso le due applicazioni agli esercizi precedenti sono l'una inversa dell'altra?
6. Sia $*$ un'operazione binaria associativa e commutativa sull'insieme $S$. Senza fare uso dei teoremi di associatività e commutatività, dimostrare in modo diretto che, per ogni $a,b,c,d\in S$, si ha: $(a*b)*(c*d)=(a*c)*(b*d)$.
7. Sia $a$ un insieme. Determinare (ove ce ne siano) gli elementi neutri a sinistra, a destra, neutri in $\P(a)$ rispetto alle operazioni $\cup$, $\cap$, $\ds$, $\setminus$. Fare lo stesso in $(a,*)$ dove $*$ è l'operazione $(x,y)\in a\times a\mapsto x\in a$. Questa operazione è associativa?

21/10

Discussione di alcuni degli esercizi della lezione precedente.

Teorema (unicità dei neutri): se, in una assegnata struttura con un'operazione binaria, $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 di strutture con più di un neutro a destra o a sinistra.

Operazione opposta definita da una operazione binaria. La seconda coincide con la prima se e solo se l'operazione è commutativa; è associativa se e solo se lo è la prima; un elemento della struttura è neutro a sinistra (risp. a destra) se e solo se è neutro a destra (risp. a sinistra) rispetto all'operazione opposta. Cenno al principio di dualità destra/sinistra per operazioni binarie. Esempio: il caso del prodotto relazionale e della composizione tra applicazioni.

Monoidi; vari esempi, tra questi: il monoide delle parole su un alfabeto.

In una struttura con un'operazione binaria ed elemento neutro: simmetrici destri o sinistri; simmetrici. L'eventuale elemento neutro è simmetrico di sé stesso. Elementi simmetrizzabili (anche: simmetrizzabili a sinistra o a destra). Vari esempi. Identificazione degli elementi simmetrizzabili a destra, a sinistra, simmetrizzabili nel monoide delle trasformazioni di un insieme.

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

Teorema di 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 $a$, 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$.

Gruppi; alcuni esempi.

Parti chiuse (si dice anche stabili) in una struttura (rispetto ad una operazione binaria); operazioni indotte e strutture indotte. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà. Neutri e passaggio ad una struttura indotta; alcuni esempi.

Esercizi proposti:

1. Delle seguenti dodici 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. Questo esercizio contiene un errore, quale?
2. L'insieme delle parti finite di $\N$ è chiuso in $(\P(\N),\cap)$, in $(\P(\N),\cup)$, in $(\P(\N),\ds)$? E quello delle parti infinite?
3. Nel monoide delle parole su un alfabeto che contenga la lettera y, dire se sono o non sono parti chiuse rispetto alla concatenazione: 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 non appare; 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.
4. Fissato un insieme $a$, dire quali dei seguenti insiemi costituiscono parti chiuse in $(T(a),\circ,\id_a)$: l'insieme delle applicazioni (da $a$ in $a$) iniettive, l'insieme di quelle suriettive, l'insieme di quelle biettive, l'insieme di quelle non iniettive, l'insieme di quelle non suriettive, l'insieme di quelle costanti, l'insieme di quelle non costanti. In alcuni casi la risposta potrebbe dipendere dalla scelta di $a$.
5. Provare che, se $a$ è un insieme, il monoide delle trasformazioni di $a$ è commutativo se e solo se $a$ ha al massimo un elemento. (Suggerimento: si compongano tra loro applicazioni costanti.)
6. Provare che, per ogni insieme $a$, l'unico elemento simmetrizzabile del monoide $(\P(a),\cap,a)$ è $a$.
7. Studiare le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, determinandone gli elementi neutri a sinistra, a destra, neutri delle strutture da esse definite e, nel caso la domanda abbia senso, gli elementi simmetrizzabili a sinistra, a destra, simmetrizzabili nelle stesse strutture:
   • $\alpha\colon (a,b)\in \Z\times\Z\mapsto a+b+1\in\Z$;
   • $\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 \N\times\N\mapsto a10^b\in\N$;
   • $\eta\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto a\cup b\cup \set 1\in\P(\Z)$;

   Se si ha tempo, studiare anche queste altre; altrimenti le si può riservare alla prossima occasione:

   • $\theta\colon (a,b)\in \N\times\N\mapsto a(b^{a+b}+3ab^2)+1\in\N\quad$ (suggerimento: calcolare $1\mathbin\theta2$, $2\mathbin\theta1$, $0\mathbin\theta(1\mathbin\theta 1)$, $(0\mathbin\theta1)\mathbin\theta 1$);
   • $\iota\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto (a\cap\N)\cup b\in\P(\Z)$;
   • $\kappa\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+\alpha b,\alpha\beta)\in S$, dove $S=\Z\times\set{-1,1}$.
8. 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;
   5. … se $a$ è un elemento neutro a sinistra in $(S,*)$, nessun elemento di $S\setminus\set a$ è neutro a destra in $(S,*)$.
9. Vero o falso? Per ogni insieme non vuoto $S$ ed ogni operazione binaria $*$ in $S$, tale che $(S,*)$ abbia elemento neutro $t$ …
   1. … $t$ ammette simmetrico in $(S,*)$;
   2. … se $t$ ammette simmetrico in $(S,*)$, questo è $t$ stesso;
   3. … se $*$ è commutativa, in $(S,*)$ ogni elemento dotato di un simmetrico sinistro ha un simmetrico.
10. Studiare la struttura algebrica $(S,*)$ dove $S=\Z\times\Z$ e $*\colon S\times S\to S$ è definita da $(a,\alpha)*(b,\beta)=(a+\alpha b,\alpha\beta)$, stabilendo di che tipo di struttura si tratta, tra quelle già introdotte (un semigruppo?, un monoide?, un gruppo?; commutativo o no?), se (e quali) elementi neutri a destra, a sinistra, neutro ha, e, nel caso la domanda abbia senso, quali sono i suoi elementi simmetrizzabili, identificandone i simmetrici.

24/10

Discussione di alcuni degli esercizi della lezione precedente. Osservazioni su un possibile errore in cui si cade quando si omettono (o si usano male) i quantificatori mentre si cercano, ad esempio, elementi neutri rispetto ad una operazione binaria e si finisce per dare risposte prive di alcun senso.

Gli elementi simmetrizzabili di un monoide $M$ ne costituiscono una parte chiusa $\U(M)$. Espressione del simmetrico di un prodotto in un monoide $M$ (in notazione moltiplicativa, per ogni $a,b\in\U(M)$ si ha $(ab)'=b'a'$ se gli apici indicano simmetrici).

Nozione di sottostruttura; sottosemigruppi (parti chiuse non vuote in un semigruppo), sottomonoidi (in un monoide: parti chiuse a cui appartiene l'elemento neutro), sottogruppi (in un gruppo: sottomonoidi a cui appartiene il simmetrico di ciascun loro elemento). Esempio importante: in ogni monoide $M$ il gruppo degli invertibili $\U(M)$ costituisce un sottomonoide. Esso è, inoltre, un gruppo, chiamato 'il gruppo degli invertibili' di $M$.

Esempi: i gruppi degli invertibili dei monoidi già incontrati nel corso. Tra questi, per ogni insieme $a$, il gruppo simmetrico $\Sym(a)$ di $a$; questo è il gruppo degli invertibili del monoide delle trasformazioni di $a$; i suoi elementi sono le permutazioni (cioè le trasformazioni biettive) di $a$.

Una caratterizzazione dei sottogruppi (una parte non vuota $H$ di un gruppo ne è un sottogruppo se e solo se per ogni $x,y\in H$ il prodotto (in notazione moltiplicativa) $xy'$ appartiene ad $H$, qui $y'$ indica il simmetrico di $x$ nel gruppo).

Tavola di Cayley di un'operazione binaria. Visualizzazione di proprietà in una tavola di Cayley: commutatività, esistenza di neutri sinistri o destri, simmetrizzabilità.

Esercizi proposti: (dare priorità a 3, 4 e 5):

1. Dato un insieme $a$, verificare che $\Rel(a)$, munito dell'operazione di prodotto relazionale forma un monoide e che l'insieme delle trasformazioni di $a$ ne costituisce un sottomonoide. Trovare ulteriori sottomonoidi di quest'ultimo.
2. Sia $*$ l'operazione binaria in $S:=\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+b,\alpha\beta)$ per ogni $a,b,\alpha,\beta\in\Z$. Decidere che tipo di struttura algebrica è $(S,*)$; se per caso si tratta di un monoide determinarne il gruppo degli invertibili.
3. Siano $a$ un insieme, $b$ una sua parte e $x$ un suo elemento. Provare che $\P(b)$ costituisce un sottogruppo di $(\P(a),\ds)$ e $\set{\alpha\in\Sym(a)\mid \alpha(x)=x}$ costituisce un sottogruppo di $(\Sym(a),\circ)$.
4. Sia $a=\set{1,2}$. Scrivere le tavole di Cayley di $(\P(a),\cup)$, $(\P(a),\cap)$, $(\P(a),\ds)$, $(\P(a),\setminus)$.
5. Sia ancora $a=\set{1,2}$. Dopo aver stabilito che $T(a)$ ha esattamente quattro elementi (suggerimento: uno è $\id_a$, uno l'applicazione che scambia tra loro $0$ e $1$, gli altri due sono costanti), determinare $\Sym(a)$ e scrivere le tavole di Cayley di $T(a)$ e di $\Sym(a)$.
6. Ragionando sull'esercizio precedente dimostrare che il monoide delle trasformazioni di un insieme $x$ è commutativo se e solo se $|x|\lt 2$.
7. Siano $a=\set{1,2,3,4}$ e $\sigma$ l'applicazione di $a$ in $a$ che manda 1 in 2, 2 in 3, 3 in 4 e 4 in 1. Dopo aver verificato che $\sigma^4(=\sigma\circ\sigma\circ\sigma\circ\sigma)$ coincide con $\id_a$ e di conseguenza che $\sigma$ è biettiva e $\Sigma:=\set{\id_a,\sigma,\sigma^2,\sigma^3}$ costituisce un sottogruppo di $\Sym(a)$, scrivere la tavola di Cayley di $(\Sigma,\circ)$.
8. 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.

26/10

Discussione di alcuni degli esercizi della lezione precedente. Il monoide delle trasformazioni di un insieme è commutativo se e solo se questo insieme ha al massimo un elemento.

Cancellabilità. Traslazioni in una struttura algebrica con un'operazione binaria; elementi cancellabili, a sinistra o a destra; elementi cancellabili. Esplicitazione e negazione della cancellabilità. In ogni monoide, gli elementi simmetrizzabili a sinistra (rispettivamente a destra) sono tutti cancellabili a sinistra (rispettivamente a destra). Il viceversa non vale in generale (ad esempio, non vale in $(\Z,\cdot)$) ma vale nel caso dei monoidi finiti (quest'ultima cosa non è stata per ora dimostrata). Molti esempi. Nei gruppi tutti gli elementi sono cancellabili (questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità, che contiene più di quanto richiesto ai fini di questo corso; per il momento, a noi serve solo il contenuto della prima pagina). Cancellabilità e tavole di Cayley.

Omomorfismi; definizione e vari esempi. Isomorfismi.

Gli omomorfismi suriettivi conservano: commutatività, associatività, elementi neutri (anche a destra o a sinistra), simmetrici (anche a destra o a sinistra), ma in generale non la cancellabilità (un esempio a proposito: se $a$ è un insieme finito non vuoto e $W$ è il monoide delle parole su $a$, allora l'applicazione $\gamma$ che ad ogni parola $w\in W$ associa l'insieme delle lettere che appaiono in $w$ è un omomorfismo suriettivo da $W$ a $(\P(a),\cup)$. Se $w$ è una qualsiasi parola non vuota in $W$, si ha che $w$ è cancellabile (in $W$) ma $\gamma(w)$ non lo è in $(\P(a),\cup)$. Altri esempi saranno forniti in seguito).

Esercizi proposti:

1. Determinare gli elementi cancellabili in $(\P(a),\cup)$ se $a$ è un insieme non vuoto.
2. Determinare gli elementi cancellabili in $(\Z\times\Z,*)$, dove $*$ è l'operazione binaria in $\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+b,\alpha\beta)$ per ogni $a,b,\alpha,\beta\in\Z$.
3. Sia $*$ un'operazione binaria in un insieme $S$. Indicando, per ogni $a\in S$, con $\sigma_a\colon x\in S\mapsto a*x\in S$ e con $\delta_a\colon x\in S\mapsto x*a\in S$ le traslazioni sinistra e destra determinate da $a$ in $(S,*)$, verificare che:
   • se $t\in S$, $t$ è neutro a sinistra (rispettivamente, a destra) in $(S,*)$ se e solo $\sigma_t=\id_S$ (rispettivamente, $\delta_t=\id_S$);
   • nell'ipotesi che $*$ sia associativa, per ogni $a,b\in S$, si ha $\sigma_{a*b}=\sigma_a\circ\sigma_b$ e $\delta_{a*b}=\delta_{b}\circ\delta_{a}$.
   Concludere che:
   • se $*$ è associativa, sia l'insieme degli elementi cancellabili a sinistra che quello degli elementi cancellabili a destra che quello degli elementi cancellabili sono chiusi in $(S,*)$;
   • se $(S,*,t)$ è un monoide e $a\in S$, allora $a$ è simmetrizzabile in $(S,*,t)$ se e solo se $\sigma_a$ e $\delta_a$ sono suriettive, e in questo caso esse sono anche biettive.
4. Sia $*$ un'operazione binaria nell'insieme $G=\set{t,x}$. Assumendo che $(G,*)$ sia un gruppo con $t$ come elemento neutro, e $t\ne x$, si scriva la tavola di Cayley di $(G,*)$.
5. Verificare che, per ogni insieme $s$, l'applicazione $x\in\P(s)\mapsto s\setminus x\in\P(s)$ è un isomorfismo da $(\P(s),\cap)$ a $(\P(s),\cup)$ ed anche da $(\P(s),\cup)$ a $(\P(s),\cap)$.
6. Sia $\alpha\colon (a,b)\in \Z\times\Z\mapsto a+b+1\in\Z$ l'operazione binaria in $\Z$ già discussa in uno degli esercizi della lezione del 21 ottobre. Provare che $n\in (\Z,+)\mapsto n-1\in (\Z,\alpha)$ è un isomorfismo.
7. Sia $*$ è l'operazione binaria in $S:=\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+\alpha b,\alpha\beta)$ per ogni $a,b,\alpha,\beta\in\Z$, già discussa un recente esercizio. Per ciascuna delle applicazioni $n\in\Z\mapsto (n,1)\in S$ e $n\in\Z\mapsto (0,n)\in S$ decidere se di tratta di un omomorfismo da $(\Z,+)$, o da $(\Z,\cdot)$, a $(S,*)$. L'applicazione $(a,\alpha)\in S\mapsto \alpha\in\Z$ è un omomorfismo da $(S,*)$ a $(\Z,+)$? Ed a $(\Z,\cdot)$?
8. A lezione non abbiamo verificato che gli omomorfismi suriettivi conservano l'associatività ed i simmetrici. Farlo.
9. Vero o falso? Supponendo che esista un omomorfismo suriettivo da una struttura $(S,*)$ ad una struttura $(T,\bullet)$, dove $*$ e $\bullet$ sono operazioni binarie, …
   • se $(S,*)$ è un semigruppo, $(T,\bullet)$ è un semigruppo;
   • se $(S,*)$ è un monoide, $(T,\bullet)$ è un monoide;
   • se $(S,*)$ è un gruppo, $(T,\bullet)$ è un gruppo.

28/10

Discussione di alcuni degli esercizi della lezione precedente.

L'inversa di un isomorfismo è necessariamente un isomorfismo. Invarianza delle proprietà algebriche (inclusa la cancellabilità) per isomorfismi.

Discussione generale sull'importanza e utilità della nozione di isomorfismo ed, in generale, delle codifiche reversibili. Alcuni esempi, tra questi: la funzione esponenziale da $(\R,+)$ a $(\R^+,\cdot)$ (il gruppo moltiplicativo dei reali positivi); per un fissato insieme $S$, l'isomorfismo $x\mapsto S\setminus x$, da $(\P(S),\cup)$ a $(\P(S),\cap)$ (o viceversa).

Isomorfismi e tavole di Cayley. Esempi (espandendo esercizi recenti): le tavole di Cayley dei gruppi di cardinalità due o tre (unici a meno di isomorfismi; lo stesso non vale per quelli di cardinalità quattro).

Permutazioni cicliche. Il gruppo simmetrico su un insieme $a$ è abeliano (cioè commutativo) se e solo se $|a|\le 2$.

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 (non dimostrate): 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 qualsiasi semigruppo commutano sempre tra loro.

In una struttura algebrica: parte chiusa generata da una parte. Sottomonoidi (in monoidi) e sottogruppi (in gruppi) generati da parti. Descrizione delle parti chiuse, dei sottomonoidi e dei sottogruppi generati da un singleton; gruppi ciclici (esempio: $(\Z,+)$).

Importante: si prenda nota dell'avviso nella pagina principale del corso a proposito del recupero della lezione di lunedì 31 ottobre.

Esercizi proposti:

1. Trovare un isomorfismo tra $(\Z,\cdot)$ e la struttura $(\Z,\beta)$ discussa in uno degli esercizi della lezione del 21 ottobre.
2. Provare che se $f$ è un omomorfismo da una struttura $(S,*)$ ad una struttura $(T,\bullet)$, dove $*$ e $\bullet$ sono operazioni binarie, per ogni parte chiusa $x$ di $(S,*)$, $\vecf(x)$ è chiusa in $(T,\bullet)$; per ogni parte chiusa $y$ di $(T,\bullet)$, $\avecf(y)$ è chiusa in $(S,*)$.
3. Sia $a=\set{1,2,3}$. In $\Sym(a)$ si considerino la trasposizione $\alpha$ definita dalle assegnazioni $1\mapsto2\mapsto 1$ e $3\mapsto 3$ e $\beta$, definita da $2\mapsto3\mapsto 2$ e $1\mapsto 1$. Calcolare $\alpha\circ\beta$ e $\beta\circ\alpha$; verificare che questi sono due cicli di lunghezza tre, uno inverso dell'altro.
4. Sia $f\colon a\to b$ un'applicazione biettiva. Dimostrare che l'applicazione $\sigma\in T(a)\mapsto f\circ\sigma\circ f^{-1}\in T(b)$ è un isomorfismo di monoidi. Dedurre da questo un isomorfismo $\Sym(a)\to\Sym(b)$.
5. Nel gruppo $(\Z,+)$, determinare le parti chiuse generate da $\set{-1}$ e da $\set{1,-1}$, il sottomonoide generato da $\set{-1,2}$ ed il sottogruppo generato da $\set{2,3}$.
6. In $(\P(\N),\cup,\vuoto)$, determinare il sottomonoide generato da $\P_1(\N)$ (l'insieme dei singleton dei numeri naturali).

31/10

Introduzione alla combinatoria. Assegnati insiemi finiti $a, b, c,\dots$, cardinalità di $a\times b$, di $a\cup b$, di $a\cup b \cup c$. Il principio di principio di inclusione-esclusione, con verifica nel caso dell'unione tra due o tre insiemi finiti. Il numero delle applicazioni e quello delle applicazioni iniettive o costanti $a\to b$ (nel corso della lezione sono poi state viste varianti equivalenti dello stesso problema: numero delle stringhe in un dato insieme di caratteri e di data lunghezza che soddisfino varie condizioni). Notazione: $b^a=\Map(a,b)$. Fattoriali e fattoriali discendenti. Scelti comunque due insiemi finiti $a$ e $b$:

• esistono esattamente $|b|^{|a|}$ applicazioni da $a$ a $b$. In particolare, non ne esistono se e solo se $b=\vuoto\ne a$;
• esistono applicazioni iniettive da $a$ a $b$ se e solo se $|a|\le |b|$. Nel caso, il loro numero è $|b|!/(|b|-|a|)!$;
• esistono applicazioni suriettive da $a$ a $b$ se e solo se $|a|\ge |b|$ e $b=\vuoto\implica a=\vuoto$;
• esistono applicazioni biettive da $a$ a $b$ se e solo se $|a|=|b|$. Nel caso, il loro numero è $|a|!$. In particolare, $|\Sym(a)|=|a|!$;
• se $|a|=|b|$ e $f\colon a\to b$ è un'applicazione, sono equivalenti: (1) $f$ è iniettiva, (2) $f$ è biettiva, (3) $f$ è suriettiva.

L'ultimo risultato non vale per insiemi infiniti: esempi.

Questa lezione si è tenuta in remoto. È disponibile una trascrizione (ovviamente parziale) del suo contenuto. Una registrazione della lezione dovrebbe, al proprietario piacendo, essere reperibile nella piattaforma Teams.

Esercizi proposti:

1. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=15$ e $|B|=10$.
   1. Se $|A\cap B|=8$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=20$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 8$, cosa possiamo dire su $|A\cup B|$?
2. Siano dati due insiemi $a$ e $b$ tali che $|a|=6$ e $|b|=12$. Quante sono le applicazioni da $a$ a $b$? Quante tra queste sono iniettive? Quante suriettive? Quante costanti?
3. Siano $a=\set{n\in\N\mid n \lt 9}$, e $b=\set{5,11,33,76}$, Quante sono le applicazioni $f$ da $a$ a $b$ tali che $\forall x\in a$$(f(x)\le 30)$? Quante sono le applicazioni $g$ da $b$ ad $a$ tali che $g(5)=g(33)\ne g(11)$?
4. Quante sono le parole di lunghezza 6 che si possono ottenere utilizzando un alfabeto di 10 caratteri? Tra queste, quante sono quelle che hanno tutte le lettere in posizione dispari (la prima, la terza etc.) uguali? E quelle palindrome? E quelle in cui nessuna lettera è ripetuta? E quelle in cui non ci sono lettere consecutive ripetute?
5. Sia $S$ un insieme di cardinalità $3$. Quante sono le operazioni binarie in $S$? E, in generale, se $S$ ha un'arbitraria cardinalità finita $n$?
6. Posto $a=\set{1,2,3}$, elencare le sei permutazioni di $a$ e scrivere la tavola di Cayley del gruppo simmetrico $\Sym(a)$.

2/11

Discussione di esercizi dalle due lezioni precedenti.

Cenni all'equipotenza ed alla comparazione tra cardinalità per insiemi infiniti, come da questa pagina. (se $a$ e $b$ sono insiemi arbitrari, $|a|=|b|$, $|a|\le|b|$ e $|a|\lt |b|$ significano, nell'ordine, che esiste un'applicazione biettiva da $a$ a $b$, che ne esiste una iniettiva, che ne esiste una iniettiva ma non ne esistono di biettive). A titolo di notizia (salvo che per i casi già verificati): $|\N^*|=|\N|=|\Z|=|\Q|\lt|\R|=|\R\times\R|=|\P(\N)|$; per ogni $a$ si ha $|a|\lt|\P(a)|$.

Come applicazione di uno dei risultati dalla lezione precedente: sia $S$ un semigruppo finito; se $S$ ha un elemento cancellabile, allora $S$ è un monoide ed ogni suo elemento cancellabile è simmetrizzabile.

Se $a$ e $b$ sono insiemi equipotenti, allora $\P(a)$ e $\P(b)$ (ma anche, per ogni $k\in\N$, $\P_k(a)$ e $\P_k(b)$) sono equipotenti.

Funzioni caratteristiche (per ogni parte $T$ di un insieme $S$, la funzione caratteristica $\chi_{T,S}\colon S\to \set{0,1}$ di $T$ in $S$ associa, ad ogni $x\in S$, $1$ se $x\in T$ e $0$ se $x\notin T$). Teorema: l'applicazione da $\P(S)$ a $\Map(S,\set{0,1})$ che a ciascuna parte $T$ di $S$ associa $\chi_{T,S}$ è biettiva; l'inversa manda ogni $f\in \Map(S,\set{0,1})$ in $\avecf(\set 1)\in\P(S)$. Di conseguenza: $\P(S)$ e $\Map(S,\set{0,1})$ sono equipotenti; se $S$ è finito $|\P(S)|=2^{|S|}$.

Discussione sulla codifica delle parti di un insieme finito in termini delle corrispondenti funzioni caratteristiche e, quindi, di "stringhe di 0 e 1" (cioè parole sull'alfabeto ${0,1}$) di lunghezza la cardinalità dell'insieme

Coefficienti binomiali: per ogni $n,k\in\N$, $\binom nk$ è per definizione la cardinalità di $\P_k(a)$, per un qualsiasi insieme $a$ di cardinalità $n$ (questo numero è ben definito, cioè non varia se $a$ è sostituito da un qualsiasi altro insieme di cardinalità $n$). Osservazioni sui casi, banali, in cui $k$ vale 0, 1 o $n$, oppure $k>n$. Per ogni $n\in\N$, $\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}$. Questo argomento è anche esposto in una nota, Coefficienti Binomiali, il cui stile espositivo, però, non coincide (soprattutto per quanto seguirà) con quello usato a lezione.

Esercizi proposti:

1. Siano dati due insiemi $a$ e $b$ tali che $|a|=7$ e $|b|=11$. Quante sono le corrispondenze da $a$ a $b$? (Si tratta di stabilire quanti sono i possibili grafici…)
2. Siano $S$ un insieme e $T$ una sua parte. Quale parte di $S$ ha per funzione caratteristica l'applicazione $x\in S\mapsto 1-\chi_{T,S}(x)\in \set{0,1}$?
3. Posto $a=\set{n\in\N^*\mid n\le 9}$, rappresentare, nel senso spiegato a lezione, le parti $\vuoto$, $\set 1$ e $\set{2,3,5}$ di $a$ come "stringhe di 0 e 1".
4. Posto $a=\set{1,2,3,4}$, scrivere esplicitamente i 16 elementi di $\P(a)$ (come facciamo a sapere che sono $16$?), raggruppandoli per cardinalità. Quanto vale $\binom 42$?
5. Dando per noto che $\binom{44}{20}=1761039350070$, calcolare $\binom{44}{24}$.
6. Ricordando quanto valgono $\binom 60$ e $\binom 61$ (e quindi $\binom 66$ e $\binom 65$) e dando per noto che $\binom 62=15$, calcolare prima $\binom 64$ e, come conseguenza, $\binom 63$. Utilizzare solo quanto visto nella lezione di oggi.
7. Sviluppando il ragionamento svolto (?) per l'esercizio precedente, calcolare $\binom 52$.

4/11

Discussione di esercizi dalla lezione precedente.

Principio d'induzione: se $p$ è un predicato unario, $b\in\N$ e $N_b=\set{n\in\N\mid b\le n}$, se valgono $p(b)$ e, per ogni $n\in N_b$, l'implicazione $p(n)\implica p(n+1)$, allora vale $p(n)$ per ogni $n\in N_b$ (la giustificazione del principio è stata rimandata). Come esempio di applicazione: per ogni $n\in\N^*$, $1+2+\cdots+n=n(n+1)/2$.

Lemma: per ogni insieme finito $S$ ed ogni $a\in S$, $|\P(S)|=2|\P(S\setminus\set a)|$; inoltre, per ogni $k\in\N$, $|\P_{k+1}(S)|=|\P_{k+1}(S\setminus\set a)|+|\P_k(S\setminus\set a)|$. Dalla prima parte: nuova dimostrazione (per induzione) della formula $|\P(S)|=2^{|S|}$ per insiemi finiti $S$; dalla seconda: formula ricorsiva per i coefficienti binomiali: per ogni $k,n\in \N$, $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$. Il triangolo di Tartaglia-Pascal e sue proprietà. Formula esplicita per i coefficienti binomiali (con dimostrazione svolta per induzione, non come nelle note): per ogni $k,n\in \N$, se $k\le n$ si ha $\binom nk=n!/(k!(n-k)!)$.

Esercizi proposti:

1. Usando il principo di induzione, provare che per ogni $n\in\N^*$ si ha che $1+3+\cdots+(2n-1)$ (la somma dei primi $n$ interi positivi dispari) è uguale a $n^2$.
2. Per ogni semigruppo $(S,\cdot)$, a partire dall'assunzione che, per ogni $x\in S$ si ha $x^1=x$ e $x^{n+1}=x^n\cdot x$ per ogni $n\in\N^*$, provare, usando il principo di induzione, che per ogni elemento $x\in S$ ed ogni $n,m\in\N^*$ si ha $x^{m+n}=x^mx^n$ e $x^{mn}=(x^m)^n$.
3. Sia $a=\set{n\in\N\mid n\lt 10}$. Quante sono le parti di $a$ a cui appartiene $3$? Quante sono le parti di $a$ contenenti $\set{3,4,8}$? Quante sono le parti di $a$ a cui appartiene $3$ ma non appartiene $7$?
4. Utilizzando la porzione del triangolo di Tartaglia-Pascal disponibile in questo sito, calcolare $\binom {13}5$ e poi $\binom {14}5$.
5. Sia $S$ un insieme di cardinalità 11. Quante sono le parti di $S$ di cardinalità 4? E quante quelle di cardinalità 7? Quante sono le 5-parti di $\P(S)$?
6. Posto $S=\set{1,2,3,4,5,6}$, calcolare in numero delle parti di $S$ contenenti $\set{2,6}$. Quante di queste hanno cardinalità 5?
7. Posto $A=\set{n\in\N\mid n\lt 9}$ e $B=\set{2,5}$, esprimere (utilizzando coefficienti binomiali; non calcolare!) le cardinalità degli insiemi $U:=\set{X\in\P(A)\mid 0\notin X\land|X|=6}$, $V:=\set{X\in\P(A)\mid 0\in X\land |X|=6}$, $W=\set{X\in\P(A)\mid B\sseq X\land |X|=6}$ e $Z:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X) \land |X|=6}$.

7/11

Discussione di esercizi dalla lezione precedente.

Partizioni di un insieme (si veda la prima parte delle note, appena aggiornate, su partizioni ed equivalenze). Definizione, caratterizzazione, esempi. Proiezione di un insieme su una sua partizione. Se $F$ è una partizione di un insieme finito $a$, allora $|a|=\sum_{b\in F}|b|$.

Proprietà di relazioni binarie: proprietà riflessiva, simmetrica, transitiva; loro formulazioni equivalenti in termini di proprietà della relazione duale e del grafico; loro negazione. Diversi esempi. Un'osservazione che semplifica la verifica della transitività di una relazione binaria $\rho$ su un insieme $A$: se $x,z\in A$ e $y\in \set{x,z}$, allora l'implicazione $((x\mathrel\rho y)\land(y\mathrel\rho z))\implica x\mathrel\rho z$ è banalmente verificata. Relazioni di equivalenza. Esempi di relazioni di equivalenza; tra queste le relazioni di equivalenza banali in un insieme (la relazione di uguaglianza e la relazione universale).

Classi di equivalenza; loro proprietà fondamentali: 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=[b]_\sim$;
• $[a]_\sim$ è l'unica classe di equivalenza rispetto a $\sim$ a cui $a$ appartenga.

Con le stesse notazioni: l'insieme quoziente $A/{\sim}$. Questo insieme è una partizione di $A$.

Nucleo di equivalenza di un'applicazione (anche detto, nel libro di testo, equivalenza associata all'applicazione).

Esercizi proposti:

1. Sia $a=\set{n\in\N\mid n\lt 10}$. Stabilire quali tra questi sono e quali non sono partizioni di $a$: $a$, $b=\set a$, $c=\set{\vuoto,\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $d=\set{\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $e=\set{\set{1,2,3,4,5,7,9},\set{0,2},\set{6,8}}$.
2. Trovare quattro partizioni distinte dell'insieme $\set{1,2,3,4}$.
3. Trovare tre partizioni non banali dell'insieme $\Z$.
4. Svolgere gli esercizi 1 (esclusi i punti f e g) e 2 (solo i punti d ed e) da relazioni binarie, limitatamente alle proprietà di essere, riflessiva, simmetrica, transitiva, di equivalenza.
5. Sia $\sim$ una relazione di equivalenza in un insieme $A$. Verificare: $\forall x,y\in A$, $(x\sim y\iff [x]_{\sim}\sseq [y]_{\sim})$.
6. Utilizzando quanto detto a lezione (e riportato in questo registro) sulla semplificazione nella verifica della transitività di una relazione binaria, trovare tutte le relazioni binarie non transitive sull'insieme $\set{0,1}$.
7. Verificare in dettaglio quanto rapidamente detto nella parte finale della lezione: il nucleo di equivalenza di un'applicazione $f$ di dominio $A$ è la relazione di uguaglianza in $A$ se e solo se $f$ è iniettiva; le relazione universale in $A$ se e solo se $f$ è costante.
8. Sia $f$ l'applicazione da $A=\set{0,1,2,3,4,5,6,7}$ a $\Z$ definita da $f(0)=10$, $f(1)=f(2)=50$ e $f(a)=a^2+1$ per ogni altro elemento $a$ di $A$. Detto $\rho$ il nucleo di equivalenza di $f$, descrivere $A/\rho$, elencando i suoi elementi e gli elementi di ciascuna delle classi modulo $\rho$. Quanti elementi ha $A/\rho$?
9. Siano $v\colon n\in\Z\mapsto |n|\in\N$ e $w\colon n\in\Z\mapsto n^2\in\Z$. Descriverne i nuclei di equivalenza e, rispetto a ciascuno di essi, la classe di $-5$.
10. Provare che la relazione binaria $\sigma$ definita in $\R$ ponendo, per ogni $x,y\in\R$, $x\mathrel\sigma y$ se e solo $x^4+(\log |x|+1)^3+1=y^4+(\log |y|+1)^3+1$ è di equivalenza.
11. Detto $\rho$ il nucleo di equivalenza dell'applicazione $X\in\P(\Z)\mapsto X\cap\N\in\P(\N)$, descrivere $[\set{-1}]_\rho$ e $[\vuoto]_\rho$.
12. Siano $a$ un insieme finito e $k\colon \P(a)\to\N$ l'applicazione che ad ogni parte $x$ di $a$ associa la sua cardinalità. Descrivere il nucleo di equivalenza $\tau$ di $k$ e l'insieme quoziente $Q:=\P(a)/\tau$. Quanti elementi ha $Q$?

9/11

Discussione di vari esercizi dalla lezione precedente. Ulteriori osservazioni sulle classi di equivalenza; due diverse classi rispetto alla stessa relazione di equivalenza sono necessariamente disgiunte.

Proiezione canonica di un insieme $a$ su un suo quoziente $a/{\sim}$; questa ha proprio $\sim$ come nucleo di equivalenza, quindi ogni relazione di equivalenza è un nucleo di equivalenza (in effetti, di molte applicazioni).

Teorema fondamentale su partizioni e relazioni di equivalenza: per ogni insieme $a$, l'applicazione ${\sim}\in\Eq(a)\mapsto a/{\sim}\in\partz(a)$ è biettiva (dominio e codominio sono gli insiemi delle relazioni di equivalenza e delle partizioni di $a$); descrizione dell'inversa. Utilizzo di questa biezione per lo studio delle relazioni di equivalenza su un insieme. Tra gli esempi: descrizione delle relazioni di equivalenza su un insieme di cardinalità 3. Le partizioni banali di un insieme $a$, (cioè $\P_1(a)$ e, se $a\ne\vuoto$, $\set a$) corrispondono alle relazioni di equivalenza banali di $a$.

Descrizione delle classi di equivalenza rispetto ad un nucleo di equivalenza. Teorema di omomorfismo per insiemi (se ne continuerà a discutere nella prossima lezione).

Anche il contenuto di questa lezione è in partizioni ed equivalenze.

Esercizi proposti:

1. Riguardare, alla luce del contenuto della lezione di oggi (in particolare: risultati sui nuclei di equivalenza e teorema di omomorfismo per insiemi), gli esercizi della lezione precedente (in particolare i numeri 8, 11 e 12)
2. Svolgere l'esercizio 1 dal compito del 16 luglio 2013.
3. Svolgere le parti (i) e (ii) dell'esercizio 3 dal compito del 18 giugno 2019.
4. Siano $S=\set{n\in\N\mid n\lt 15}$, $T=\set{n\in\N\mid n\lt 6}$ e $\theta$ l'applicazione $X\in\P(S)\mapsto |X|\in\N$. Detto $\rho$ il nucleo di equivalenza di $\theta$, descrivere $[T]_\rho$ e $|[T]_\rho|$. Trovare, se possibile, una parte $V$ di $S$ tale che $[V]_\rho\ne[T]_\rho$ ma $|[V]_\rho|=|[T]_\rho|$.
5. Sia $a=\set{0,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[0]_\sim=[6]_\sim$
   • … le relazioni di equivalenza $\rho$ in $a$ tali che $0\mathrel\rho 3$, $\set{2,5,6}\subseteq [3]_\rho$ e $6\in[4]_\rho$.
6. Sia $a$ un insieme tale che $|a|=21$. Quante sono le relazioni di equivalenza $\rho$ in $a$ tali che $a/\rho$ abbia esattamente due elementi?
7. Sia $f\colon a\to b$ un'applicazione e sia $\sim$ il suo nucleo di equivalenza. Supponiamo di non conoscere $f$, ma di conoscere $|a|$ e $|b|$. Possiamo stabilire quanto vale $|a/{\sim}|$? Se sappiamo che $f$ è iniettiva, possiamo stabilire quanto vale $|a/{\sim}|$? Se sappiamo che $f$ è suriettiva, possiamo stabilire quanto vale $|a/{\sim}|$?

11/11

Discussione di esercizi dalla lezione precedente. Ulteriori esempi sul teorema di omomorfismo per insiemi.

Fattorizzazione di un'applicazione attraverso la proiezione sul quoziente rispetto al nucleo di equivalenza; ogni applicazione è la composta di un'applicazione iniettiva per una suriettiva. Altri esempi. Può essere anche utile una vecchia nota sul teorema di omomorfismo per insiemi. Come vale per altri materiali in questo sito, questa è scritta con notazioni diverse da quelle attualmente usate nel corso, (riguardo alla composizione tra applicazioni ed alle immagini di elementi mediante applicazioni: $fg$ in luogo di $g\circ f$ e $x^f$ in luogo di $f(x)$), ma si consiglia di leggere l'esempio 2. Terminologia usata: la coimmagine $\text{coim}\;f$ di un'applicazione $f$ è il quoziente del dominio di $f$ rispetto al nucleo di equivalenza di $f$.

Anelli. Definizione ed esempi; anelli commutativi, anelli unitari. Sottoanelli, sottoanelli unitari; omomorfismi di anelli. 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).

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 per la differenza: $a-b=a+(-b)$; distributività della moltiplicazione rispetto all'operazione di differenza così definita; se $R$ è unitario, per ogni $n\in\Z$ si ha $(n1_R)a=na$.

Osservazione: non sempre, negli anelli, è verificata la consueta legge di annullamento del prodotto.

Esercizi proposti:

1. Posto $a=\set{1,2,3}$, e detta $F$ la partizione $\set{\set 1,\set{2,3}}$ di $a$, stabilire quante sono le applicazioni $f\colon a\to a$ tali che $F=a/\rho$, dove $\rho$ è il nucleo di equivalenza di $f$.
2. 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$. Questo anello si chiama anello prodotto diretto di $R$ per $S$.
3. Nell'anello prodotto diretto $\Z\times\Z$, definito come all'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 quelle di $\Z\times\Z$)? Per caso è isomorfo ad un anello che già conosciamo?
   Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
4. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?

14/11

Discussione di esercizi dalla lezione precedente.

Omomorfismi di anelli unitari.

Legge di annullamento del prodotto con esempi di anelli in cui essa non vale. Divisori dello zero sinistri, destri, divisori dello zero negli anelli. Teorema: 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. Anelli integri, domini di integrità.

In un anello che abbia più di un elemento lo zero non può essere cancellabile, quindi non può essere invertibile. Corpi e campi (esempi: i campi dei razionali e dei reali, l'anello delle parti di un singleton). I campi sono domini di integrità; il viceversa non vale: un controesempio è fornito dall'anello degli interi. Gli anelli unitari finiti integri sono corpi; a titolo di notizia: essi sono addirittura campi. Per questi argomenti si vedano le note sulla cancellabilità.

Formula del binomio di Newton: se $a$ e $b$ sono due elementi di un anello unitario e $ab=ba$, allora, per ogni intero positivo $n$, si ha $(a+b)^n=\sum_{k=0}^n\binom nk a^k b^{n-k}$ (si veda l'ultima pagina delle note sui coefficienti binomiali).

Relazioni (binarie) antiriflessive e antisimmetriche. Relazioni d'ordine (largo) e relazioni d'ordine stretto. Esempi. La relazione duale ad una relazione binaria $\rho$ è d'ordine se $\rho$ è d'ordine, d'ordine stretto se $\rho$ è d'ordine stretto.

Notazione: fissato un insieme $a$, $\OL(a)$ e $\OS(a)$ denotano gli insiemi delle relazioni di ordine largo e di ordine stretto nell'insieme $a$. Ogni relazione d'ordine largo $\rho$ in un insieme ne definisce una, $\rho_{{\ne}}$, di ordine stretto nello stesso insieme. Questa è descritta da: $(\forall x,y\in a)$$(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$.

ATTENZIONE: come indicato nell'avviso nella pagina principale del corso, le due prossime lezioni si terrano in remoto.

Esercizi proposti:

1. Verificare che, per ogni insieme $a$, nell'anello delle parti di $a$ ogni elemento diverso dall'unità $a$ è un divisore dello zero.
2. Nell'anello prodotto diretto $\Z\times\Z$, definito come nell'esercizio 2 della lezione precedente, si decida quali tra questi elementi sono divisori dello zero, quali cancellabili e quali invertibili: $(1,1)$, $(3,2)$, $(0,4)$ $(1,-1)$. Fatto questo, provare a descrivere l'insieme dei divisori dello zero in $\Z\times\Z$.
3. Sia $a$ un elemento invertibile in un anello unitario $R$. È possibile che $a$ sia un divisore dello zero in $R$?
4. Provare (ammesso che sia vero) quanto segue: se $a$ e $b$ sono elementi di un anello $R$, in $R$ si ha $(a+b)^2=a^2+2ab+b^2$ se e solo se $ab=ba$.
5. Completare gli esercizi 1 (esclusi i punti f e g) e 2 (solo i punti d ed e) da relazioni binarie (per "ordinamento" si intende "relazione d'ordine stretto o largo").
6. Sia $\rho$ una relazione d'ordine largo nell'insieme $a$. Definita $\rho_{{\ne}}$ come fatto a lezione, come si ottiene il grafico di $\rho_{{\ne}}$ da quello di $\rho$?
7. Siano $\rho$ e $\sigma$ le relazioni binarie in $\Z$ definite ponendo, per ogni $a,b\in\Z$: $a\mathrel\rho b$ se e solo se $a^2+2\le b^2+2$ e $a\mathrel\sigma b$ se e solo se $a=b$ oppure $a^2+a+1\lt b^2+b+1$. Di ciascuna delle due decidere se è una relazione d'ordine.
8. La relazione binaria $\tau$ definita in $\N$ ponendo, per ogni $a,b\in\N$, $a\mathrel\tau b$ se e solo se $b-a\in\N\setminus\set 1$ è d'ordine?

16/11

Discussione di esercizi dalla lezione precedente.

Notazione: fissato un insieme $a$, biezioni (una è l'inversa dell'altra) $\rho\in\OL(a)\mapsto\rho_{\ne}\in\OS(a)$ e $\sigma\in \OS(a)\mapsto\sigma_{=}\in\OL(a)$. Qui $\sigma_{=}$ è descritta da: $(\forall x,y\in a)$$(x\mathrel{\sigma_{=}}y \iff (x\mathrel\sigma y \lor x=y))$. Osservazione: le relazioni di ordine stretto sono antisimmetriche.

La relazione $|_S$ di divisibilità in un semigruppo commutativo $S$: è sempre transitiva, è riflessiva se $S$ è un monoide. Elementi associati. La relazione di divisibilità in $(\Z,\cdot)$ non è d'ordine, quella in $(\N,\cdot)$ lo è.

Insiemi ordinati. Esempi essenziali. Confrontabilità ed insiemi totalmente ordinati. Relazione d'ordine (stretto o largo) indotta su una parte; sottoinsiemi ordinati.

Funzioni crescenti ed isomorfismi tra insiemi ordinati. Esempio di applicazione biettiva crescente tra insiemi ordinati che non è un isomorfismo (l'applicazione identica da $\N^*$, ordinato per divisibilità ad $\N^*$ ordinato dall'ordinamento usuale).

Questa lezione si è tenuta in remoto. È disponibile una trascrizione (ovviamente parziale, ma editata nella parte iniziale) del suo contenuto. Una registrazione della lezione dovrebbe, se abbiamo fortuna, essere reperibile nella piattaforma Teams.

ATTENZIONE: come indicato nell'avviso nella pagina principale del corso, anche la prossima lezione si terrà in remoto.

Esercizi proposti:

1. Provare che se $S$ è un insieme, $T$ è una sua parte e $\sigma\in\OS(S)$, la relazione $\sigma_T$ indotta da $\sigma$ su $T$ è di ordine stretto. Verificare anche che la relazione indotta su $T$ da $\sigma_=$ coincide con $(\sigma_T)_=$.
2. Verificare che se $S$ è un monoide commutativo la relazione "essere elementi associati" in $S$ è di equivalenza.
3. Descrivere (e se possibile, identificare con qualcosa di già noto) la relazione di divisibilità in ciascuno dei monoidi $(\N,+)$ e, per un arbitrario insieme $a$, $(\P(a),\cup)$ e $(\P(a),\cap)$.
4. Riflettere sull'esempio emerso a lezione del sottomonoide $T=\set 1\cup\set{n\in\N\mid n>5}$ del monoide $(\N,\cdot)$, in cui la relazione di divisibilità differisce da quella indotta dalla relazione di divisibilità in $(\N,\cdot)$. Costruire un esempio analogo nel monoide $(\N,+)$.
5. Trovare un isomorfismo dall'insieme delle parti di $\set{0,1}$ all'insieme delle parti di $\set{3,4}$, ordinati per inclusione.
6. Provare che se due insiemi $a$ e $b$ sono equipotenti, gli insiemi ordinati $(\P(a),\sseq)$ e $(\P(b),\sseq)$ sono isomorfi.

18/11

Discussione di esercizi dalla lezione precedente.

Elementi minimi e minimali (e, dualmente, massimi e massimali) in insiemi ordinati. Esempi e comparazione tra le proprietà. Se, in un arbitrario insieme ordinato, un elemento $x$ è minimo, allora $x$ è l'unico elemento minimale (e quindi l'unico minimo). Enunciato duale per massimi e massimali. L'enunciato non si inverte: esempio di un insieme ordinato privo di minimo e massimo e dotato di un elemento che è, allo stesso tempo, l'unico elemento minimale e l'unico elemento massimale (si veda l'esercizio 1). (Solo a titolo di notizia: se un insieme ordinato finito ha un unico elemento minimale, questo ne è il minimo).

In ogni insieme ordinato finito non vuoto esistono sempre elementi minimali ed elementi massimali.

Intervalli (chiusi, aperti o semiaperti) in insiemi ordinati. Relazione di copertura definita da una relazione d'ordine. Nel caso degli insiemi ordinati finiti, ma non in generale, essa determina l'ordinamento. Diagrammi di Hasse di insiemi ordinati finiti. Esempi.

Anche questa lezione si è tenuta in remoto. È disponibile una trascrizione parziale del suo contenuto. Esiste la possibilità che una registrazione della lezione sia in qualche forma reperibile sulla piattaforma Teams.

Esercizi proposti:

1. Completare la verifica del fatto che la relazione binaria $\rho$ in $\Z$ discussa a lezione e definita da $\forall a,b\in\Z$$(a\mathrel\rho b\iff{}$$ a\le b\land (a=0\iff b=0))$ è effettivamente d'ordine.
2. Siano $A=\set{0,1,2,3}$ e $B=\set{1,2,3,4}$. Dopo averne disegnato i diagrammi di Hasse, descrivere gli eventuali elementi minimo, massimo, minimali e massimali in $A$ ed in $B$, ordinati dall'ordinamento indotto dalla divisibilità in $\N$. Trovare in $A$ una parte che sia totalmente ordinata (sempre dall'ordinamento indotto dalla divisibilità in $\N$) della cardinalità massima possibile.
3. Siano $A=\set{0,1,2,3}$ e $\rho$ la relazione binaria definita in $\P(A)$ ponendo, per ogni $x,y\in\P(A)$, $x\mathrel\rho y$ se e solo se $x=y \lor |x|\lt|y|$. Provare che $\rho$ è una relazione d'ordine, decidere se è totale e determinare in $(\P(A),\rho)$ gli eventuali elementi minimo, massimo, minimali e massimali. Disegnare un diagramma di Hasse di $(\P(A\setminus\set 0),\rho)$.
4. Costruire un esempio di insieme ordinato con esattamente due elementi minimali.
5. Esiste in $\P(\N)$ una parte infinita che sia totalmente ordinata per inclusione (cioè dall'ordinamento indotto dall'inclusione in $\P(\N)$)?
6. In ciascuno dei seguenti insiemi, ordinati dalla relazione di inclusione, determinare gli eventuali elementi minimali, massimali, minimo, massimo: $\P(\Z)$, $\Pf(\Z)$ (l'insieme delle parti finite di $\Z$), $\P(\Z)\setminus\Pf(\Z)$ (l'insieme delle parti infinite di $\Z$), $\P(\Z)\setminus\P(\N)$, $\P_7(\Z)$, $\P_4(\Z)\cup\P_9(\Z)$, $\set{\set{1,2,3}, \set{4},\set{n\in\Z\mid n>1}}$. Fare lo stesso per gli insiemi $\set{x\in\Q\mid 0\lt x \le 3}$ e $\set{x\in\Q\mid 0\lt x \le\sqrt 2}$ ordinati dall'ordinamento indotto da quello usuale di $\R$.
7. Svolgere i punti da (i) a (v) dell'esercizio 6 dal compito del 16 gennaio 2019.

21/11

Discussione di esercizi dalla lezione precedente.

Completamento della discussione sui diagrammi di Hasse. Diagrammi simili a quelli di Hasse, ma anche di tipo più generale, descrivono sempre una relazione d'ordine. Esempi.

Date un'applicazione $f\colon S\to T$ ed una relazione d'ordine $\le$ in $T$, relazione d'ordine stretto e relazione d'ordine largo definite in $S$ da $f$ e $\le$: quella stretta (risp. larga) è definita da: scelti comunque $x$ e $y$ in $S$, $x$ è in relazione con $y$ se e solo se $f(x)\lt f(y)$, (risp. se e solo se $x=y$ oppure $f(x)\lt f(y)$), descrizione degli elementi minimali o massimali ed altre osservazioni.

Minoranti e (dualmente) maggioranti di una parte $T$ di un insieme ordinato $(S,\rho)$. Notazione: indichiamo gli insiemi da essi formati come $T^{\downarrow_{(S,\rho)}}$ e $T^{\uparrow_{(S,\rho)}}$ rispettivamente. Alcuni esempi; tra questi: se $T=\vuoto$, $T^{\downarrow_{(S,\rho)}}=T^{\uparrow_{(S,\rho)}}= S$; se $S$ è un insieme e $T\subseteq\P(S)$, i minoranti ed i maggioranti di $T$ in $(\P(S),\subseteq)$ sono, rispettivamente, i sottoinsiemi di $\bigcap T$ (o di $S$ se $T=\vuoto$) ed i sottoinsiemi di $S$ contenenti $\bigcup T$.

Estremi inferiori ed estremi superiori. Definizione di reticolo.

Esercizi proposti:

1. Completare l'esercizio 6 da relazioni binarie, sino alla prima occorrenza della parola 'reticolo'.
2. Per un arbitrario $X\sseq \N$, descrivere gli insiemi dei maggioranti e dei minoranti di $X$ in $(\N,|)$.
3. Decidere se sono reticoli: per ogni insieme $a$, $(\P(a),\sseq)$, $(\N,\le)$, $(\N,|)$, gli insiemi ordinati degli esercizi 2 e 3 delle lezione scorsa, l'insieme $\Pf(\Z)$ delle parti finite di $\Z$, ordinato per inclusione.
4. Verificare: se $a$ è un elemento di un insieme ordinato $(S,\rho)$, $a$ è minimale in $(S,\rho)$ se e solo se $\set a^{\downarrow_{(S,\rho)}}=\set a$. Formulare poi l'enunciato duale (ovviamente, anch'esso vale).
5. Verificare: se $T$ è una parte di un insieme ordinato $(S,\rho)$, per ogni $a\in T$, sono equivalenti: (1) $a=\min (T,\rho)$, (2) $a\in T\cap T^{\downarrow_{(S,\rho)}}$, (3) $a\in T$ e $a=\inf_{(S,\rho)}(T)$. Formulare poi l'enunciato duale.
6. Verificare: se $a$ e $b$ sono parti di un insieme ordinato $(S,\rho)$, allora $(a\cup b)^{\downarrow_{(S,\rho)}}=a^{\downarrow_{(S,\rho)}}\cap b^{\downarrow_{(S,\rho)}}$ e $(a\cup b)^{\uparrow_{(S,\rho)}}=a^{\uparrow_{(S,\rho)}}\cap b^{\uparrow_{(S,\rho)}}$, mentre $(a\cap b)^{\downarrow_{(S,\rho)}}\supseteq a^{\downarrow_{(S,\rho)}}\cup b^{\downarrow_{(S,\rho)}}$ e $(a\cap b)^{\uparrow_{(S,\rho)}}\supseteq a^{\uparrow_{(S,\rho)}}\cup b^{\uparrow_{(S,\rho)}}$, dove le inclusioni possono essere strette.

23/11

Discussione di esercizi dalla lezione precedente. Esempi: sono reticoli $(\P(S),\sseq)$ (per qualsiasi insieme $S$), $(\N,\le)$ e tutti gli insiemi totalmente ordinati, $(\N,\mid)$. Reticoli completi (lo sono $(\P(S),\sseq)$ (per ogni $S$) e $(\N,\mid)$, non lo è $(\R,\le)$). Massimi comuni divisori (MCD) e minimi comuni multipli (mcm) di parti di un semigruppo commutativo. Se $(S,\rho)$ è un insieme ordinato, per ogni $a,b\in S$ sono equivalenti: (1) $a\rho b$; (2) $a=\inf_{(S,\rho)}\set{a,b}$; (3) $a=\min_{(S,\rho)}\set{a,b}$; (4) $b=\sup_{(S,\rho)}\set{a,b}$; (5) $b=\max_{(S,\rho)}\set{a,b}$; dunque, per verificare che un insieme ordinato sia un reticolo basta prendere in esame le coppie di elementi non confrontabili tra loro.

Qualsiasi reticolo ha al più un elemento minimale ed al più un elemento massimale; questo per più ragioni. Una è: un elemento minimale (risp. massimale) in un reticolo è necessariamente il minimo (risp. massimo) del reticolo.

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

Reticoli limitati; lo sono tutti i reticoli finiti non vuoti, ma anche $(\N,\mid)$ e $(\P(S),\subseteq)$ per ogni insieme $S$ (ma non, ad esempio, $(\N,\le)$).

Siano $(S,\rho)$ un insieme ordinato e $X,Y\sseq S$. Allora, in $(S,\rho)$, si ha (con anche gli enunciati duali): $(X\cup Y)^{\downarrow}=X^{\downarrow}\cap Y^{\downarrow}$, supposti poi esistenti $x=\inf_{(S,\rho)}X$ e $y=\inf_{(S,\rho)}Y$, si ha poi $X^{\downarrow}=\set{x}^{\downarrow}=\set{a\in S\mid a\mathrel\rho x}$, dunque $(X\cup Y)^{\downarrow}=\set{x,y}^{\downarrow}=\set{a\in S\mid a\mathrel\rho x\land a\mathrel\rho y}$. Pertanto, se $(S,\rho)$ è un reticolo e $X$ e $Y$ sono sue parti dotate di estremo inferiore (risp. superiore), anche $X\cup Y$ ha estremo inferiore (risp. superiore). Di conseguenza: tutte le parti finite e non vuote di un (arbitrario) reticolo hanno estremo inferiore ed estremo superiore.

Le due operazioni (binarie) reticolari (join/sup/unione reticolare/$\lor$ e meet/inf/intersezione reticolare/$\land$) definite in un reticolo. Loro proprietà algebriche (commutatività, associatività, leggi di assorbimento, iteratività). In generale, come proprietà algebrica, l'iteratività è conseguenza delle leggi di assorbimento. Reticoli come strutture algebriche: se $(L,\lor,\land)$ è una struttura algebrica in cui $\lor$ e $\land$ sono operazioni binarie associative e commutative per le quali valgono le leggi di assorbimento, allora esiste una relazione d'ordine $\rho$ in $L$ tale che $(L,\rho)$ sia un reticolo che ha $\lor$ e $\land$ come operazioni reticolari ($\rho$ è definita ponendo, per ogni $a$, $b\in L$, $a\mathrel\rho b$ se e solo se $a=a\land b$ o, equivalentemente, $b=b\lor a$). Fissato un qualsiasi insieme $L$, questa costruzione definisce un'applicazione biettiva tra l'insieme delle coppie ordinate $(\lor,\land)$ di operazioni binarie in $L$ che verificano le proprietà indicate e quello delle relazioni d'ordine in $L$ che rendono $L$ un reticolo; dunque si possono, in modo equivalente a quanto fatto sinora, definire i reticoli anche come strutture algebriche, e le due trattazioni sono equivalenti. Esempio particolarmente significativo: per ogni insieme $S$, le operazioni reticolari corrispondenti alla relazione di inclusione in $\P(S)$ sono quelle di unione e intersezione.

Interpretazione della dualità in un reticolo come scambio tra le due operazioni reticolari. Se $(L,\rho)$ è un reticolo, con operazioni reticolari $\lor$ (estremo superiore) e $\land$ (estremo inferiore), e $a\in L$, allora $a$ è neutro rispetto a $\lor$ se e solo se $a=\min(L,\rho)$, è neutro rispetto a $\land$ se e solo se $a=\max(L,\rho)$.

Isomorfismi tra reticoli: per un applicazione tra reticoli sono equivalenti le proprietà di essere un isomorfismo di insiemi ordinati e quella di essere un isomorfismo tra le strutture algebriche definite dalle operazioni reticolari.

Sottoreticoli (cioè parti non vuote di un reticolo chiuse rispetto alle operazioni reticolari). Esempi di sottoreticoli; lo sono tutti gli intervalli chiusi. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

Complementi in un reticolo limitato; reticoli complementati (esempio: il reticolo delle parti di un insieme lo è; un insieme totalmente ordinato con più di due elementi non lo è). Esempi. In un reticolo (limitato) un elemento $a$ ha per complemento un elemento $b$ con cui è confrontabile se e solo se $a$ e $b$ sono il minimo ed il massimo dl reticolo.

Esercizi proposti:

1. Svolgere l'esercizio 3 dal compito del 12 novembre 2018.
2. Siano $P=\set{1,3,4,6,12}$ (cioè $\Div_{(\N,\cdot)}(12)\setminus\set 2$) e $T=\set{0,1,2,3,5}$. Si verifichi che entrambi, muniti della relazione indotta dalla divisibilità in $(\N,\cdot)$, sono reticoli ma non sottoreticoli di $(\N,\mid)$, e si determinino in ciascuno di essi tutte le coppie di elementi che sono tra loro complementi. Si consiglia di disegnarne i diagrammi di Hasse.
3. Stabilire per quali interi $n$ nell'insieme $\set{2,14,18,27,30}$ il reticolo dei numeri naturali divisori di $n$ (sottoreticolo di $(\N,\mid\,))$ è complementato.
4. $2$ ha un complemento in $(\N,\mid)$?

25/11

Discussione degli esercizi dalla lezione precedente.

Per gli argomenti di questa lezione, si vedano le note sulle strutture booleane, esclusa l'ultima sezione che verrà discussa in seguito.

Reticoli distributivi (senza dimostrazione: la distributività anche di una sola delle due operazioni reticolari rispetto all'altra implica la distributività del reticolo). Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), gli insiemi totalmente ordinati. I sottoreticoli dei reticoli distributivi sono distributivi. Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; criterio di distributività di Birkhoff (dimostrata solo l'implicazione banale).

Reticoli booleani ed algebre di Boole; equivalenza tra le nozioni; dualità per algebre di Boole; ogni algebra di Boole è isomorfa alla sua duale. Sottoalgebre di Boole (non lo sono tutti i sottoreticoli, ma solo quelli chiusi per complementi). Alcune identità nelle algebre di Boole: per ogni $a$ e $b$ si ha: $(a')'=a$, $a=0\lor a=1\land a$, $(a\land b)'=a'\lor b'$ e $(a\lor b)'=a'\land b'$ (identità di De Morgan).

Anelli booleani; l'anello delle parti di un qualsiasi insieme è booleano. Proprietà degli anelli booleani: sono commutativi e, in essi, ogni elemento coincide col suo opposto (cioè: $2a=0_R$ per ogni elemento $a$ di un anello booleano $R$). Enunciato del teorema di Stone per anelli booleani (ogni anello booleano è isomorfo ad un sottoanello unitario dell'anello delle parti di un insieme; ogni anello booleano finito è isomorfo all'anello delle parti di un insieme). Conseguenze: gli anelli booleani finiti hanno per cardinalità una potenza di $2$; scelti comunque due anelli booleani finiti, essi sono isomorfi se e solo se sono equipotenti.

Costruzione di un'algebra di Boole (ovvero, di un reticolo booleano) a partire da un anello booleano e costruzione (inversa) di un'anello booleano a partire da un'algebra di Boole (per la seconda costruzione non sono state effettuate verifiche). I sottoanelli unitari di un anello booleano sono tutte e sole le sottoalgebre della corrispondente algebra di Boole. Equivalenza tra lo studio dei reticoli booleani, delle algebre di Boole, degli anelli booleani. Teorema di Stone per reticoli booleani e per algebre di Boole, con corollari come per gli anelli booleani.

Esercizi proposti:

1. Disegnare il diagramma di Hasse di un reticolo in cui esista un elemento con sei complementi.
2. Trovare, tra i sottoinsiemi di $\P(\N)$, ordinati per inclusione:
   1. un sottoinsieme di cardinalità 5 che non sia un reticolo;
   2. un sottoinsieme di cardinalità 5 che sia un reticolo trirettangolo.
   3. un sottoinsieme di cardinalità 5 che sia un reticolo pentagonale.
3. Esercizio 5 dal compito dell'8 marzo 2019.
4. Provare che, come detto a lezione, l'insieme delle parti $x$ di $\N$ tali che uno tra $x$ e $\N\setminus x$ sia finito costituisce un sottoanello unitario di $(\P(\N),\ds,\cap)$.
5. Svolgere l'esercizio 4 dalle note sulle strutture booleane.
6. Verificare che un'applicazione tra i sostegni di due algebre di Boole è un isomorfismo di algebre di Boole se e solo se è un isomorfismo tra i corrispondenti reticoli (visti come insiemi ordinati).
7. Spiegare perché un reticolo complementato di cardinalità 1000 non può essere distributivo.

28/11

Discussione di esercizi dalla lezione precedente.

Proprietà di buon ordinamento di $(\N,\le)$; dimostrazioni "per controesempio minimo". Giustificazione del principio di induzione (prima forma). Seconda forma del principio di induzione (o principio di induzione completa); offre una versione alternativa (e non consigliata) del metodo di dimostrazione per controesempio minimo.

Ancora sulla divisibilità. Elementi tra loro associati (cioè che si dividono a vicenda) in un arbitrario monoide commutativo $M$; la relazione "essere elementi associati" è di equivalenza in $M$, per verifica diretta, ma anche perché per due qualsiasi elementi $a$ e $b$ sono equivalenti le proprietà di essere associati, di avere gli stessi divisori, di avere gli stessi multipli. Osservazione generale: se, in monoide commutativo, $a$ e $a'$ sono elementi tra loro associati ed anche $b$ e $b'$ sono elementi tra loro associati, allora $a$ divide $b$ se e solo se $a'$ divide $b'$. Dunque: le proprietà relative alla divisibilità tra elementi restano invariate al passaggio da elementi ad elementi associati. Sia $a\in M$; per ogni $u\in\U(M)$, $a$ e $au$ sono associati; se $a$ è cancellabile vale anche il viceversa: gli elementi associati ad $a$ in $M$ sono tutti e soli quelli della forma $au$ per un opportuno $u\in\U(M)$. Esempio: associati in $\N$ e in $\Z$ rispetto alla moltiplicazione.

Divisori banali di un elemento $a$: sono gli invertibili e gli associati ad $a$. Divisori propri (sono i divisori non associati). Elementi irriducibili (cioè non invertibili e privi di divisori non banali). In $(\N,\cdot)$ ed in $(\Z,\cdot)$ gli elementi irriducibili sono i numeri primi.

Fattorizzazioni (in prodotto di irriducibili) "essenzialmente uguali" in monoidi commutativi. Monoidi fattoriali (cioè: monoidi cancellativi (ovvero: ad elementi tutti cancellabili) in cui ogni elemento non invertibile è prodotto di irriducibili e lo è in modo essenzialmente unico). Anelli fattoriali. Enunciato del Teorema Fondamentale dell'Aritmetica nelle forme: (1) $(\N^\#,\cdot)$ è un monoide fattoriale; (2) $(\Z^\setminus\set 0,\cdot)$ è un monoide fattoriale; (3) $(\Z,+,\cdot)$ è un anello fattoriale. Forme esplicite dell'enunciato.

Esercizi proposti:

1. Assegnato un arbitrario insieme $a$, nel monoide $(\P(a),\cap,a)$ descrivere gli elementi associati ad un arbitrario elemento $x$.
2. Quali sono gli elementi irriducibili nel monoide $(\N,+,0)$? $(\N,+,0)$ è un monoide fattoriale?
3. Assegnato un insieme finito $S$, quali sono gli elementi irriducibili in $(\P(S),\cup,\vuoto)$? $(\P(S),\cup)$ è un monoide fattoriale?
4. Ridimostrare il fatto che ogni insieme ordinato finito e non vuoto ha elementi minimali usando il metodo del controesempio minimo. Suggerimento: se l'asserto è falso, esiste il minimo intero positivo $n$ tale che esista un insieme di cardinalità $n$ privo di elementi minimali. Se $S$ è un tale insieme ordinato di cardinalità $n$ e $a\in S$, l'insieme $T$ costituito dagli elementi di $S$ strettamente minori di $a$ (cioè $T=\set a^{\downarrow}\setminus \set a$) non è vuoto …

30/11

Discussione di esercizi dalla lezione precedente.

Dimostrazione di parte del Teorema Fondamentale dell'Aritmetica (solo del fatto che ogni numero intero diverso da $0$, $1$ e $-1$ è prodotto di primi).

Ancora due osservazioni sulla divisibilità: se $X$ è una parte di un monoide commutativo $M$, l'insieme dei massimi comuni divisori degli elementi di $X$ o è vuoto o è una classe di equivalenza rispetto alla relazione 'essere elementi associati'; lo stesso vale per l'insieme dei minimi comuni multipli. Se $a,b,c$ sono elementi di un anello commutativo $R$ e $a$ divide sia $b$ che $c$, allora $a$ divide tutte le combinazioni lineari in $R$ tra $b$ e $c$ (cioè tutti gli elementi della forma $rb+sc$ al variare di $r$ e $s$ in $R$).

Come conseguenze del TFA: (1) un intero primo che divida un prodotto deve dividere almeno uno dei fattori; (2) descrizione dei divisori di un numero diverso da zero in $\N$ o in $\Z$; numero di questi divisori. Cenno all'estensione di questo risultato ad arbitrari monoidi fattoriali.

Problema: date un'operazione binaria $*$ ed una relazione di equivalenza $\sigma$ in un insieme $S$, si può usare $*$ per definire "nel modo più ovvio possibile" un'operazione binaria in $S/{\sigma}$? Alcuni esempi. Equivalenze compatibili con un'operazione binaria ed operazioni quoziente (cioè quelle indotte sull'insieme quoziente). Esempi. Congruenze in una struttura algebrica e strutture quoziente.

Se $\sigma$ è una congruenza in una struttura di sostegno $S$, la proiezione canonica $a\in S\mapsto [a]_\sim \in S/{\sigma}$ è 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 quindi strutture dello stesso tipo.

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

Le congruenze modulo un intero in $\Z$ (cioè le relazioni di equivalenza $\equiv_m$ al variare di $m\in\Z$). Loro descrizione esplicita nei casi in cui $m$ sia uno tra 0, 1 e 2; per ogni intero $m$, ${\equiv_m}={\equiv_{-m}}$; se due interi sono congrui modulo un intero $m$, essi sono congrui anche modulo ciascun divisore di $m$. Le relazioni $\equiv_m$ sono effettivamente congruenze nell'anello $\Z$ degli interi (a titolo di notizia: non ne esistono altre, anzi: non esistono altre relazioni di equivalenza compatibili con l'addizione in $\Z$). Notazione: per ogni $m\in\Z$ si scrive $\Z_m$ per $\Z/{\equiv_m}$ ed anche, per ogni $a\in\Z$, $[a]_m$ per $[a]_{\equiv_m}$.

Descrizione esplicita degli elementi degli anelli $\Z_m$: 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\in\Z$ e $m\in\Z\setminus\set 0$, $a\modbin m$ è definito come il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$. Descrizione esplicita dei quozienti di $\Z$: per ogni $m\in\Z\setminus\set0$, $\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\ne j$, allora $i\not\equiv_m j$), quindi $|\Z_m|=|m|$.

Aggiunta: Consiglio la lettura, da affiancare ad uno studio serio dell'argomento, di un articolo divulgativo, scritto per studenti delle scuole superiori, che introduce in modo informale (e ripeto, non da solo sufficiente ai nostri scopi) alcuni argumenti trattati in questa e nelle prossime lezioni.

Esercizi proposti:

1. In $\Z$, scrivere tutte le fattorizzazioni di 12 in prodotto di primi.
2. A lezione abbiamo descritto i divisori degli elementi non invertibili nei monoidi fattoriali. Quali sono i divisori degli elementi invertibili?
3. Descrivere i numeri naturali divisori di $5^6 13^2 17^9$ e dire quanti sono.
4. Supponiamo assegnati due interi $a$ e $b$ tali che $ab=240$ e $2$ sia un MCD tra $a$ e $b$. Trovare, se possibile, un mcm tra $a$ e $b$.
5. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
6. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
7. 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?
8. Decidere se la relazione di equivalenza $\sim$ definita in $\P(\Z)$ ponendo, per ogni $x,y\in\P(\Z)$, $x\sim y\iff x\cap\N=y\cap\N$ è o non è una congruenza nell'anello delle parti di $\Z$.
9. Nel monoide delle parole su un alfabeto, la relazione "avere la stessa lunghezza" è una congruenza?
10. 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 $*$. Se possibile, spiegare perché questo esercizio generalizza i precedenti.
11. Elencare gli elementi di $[50]_6\cap\set{n\in\Z\mid -10\le n\le 10}$.
12. Elencare gli interi $m$ tali che $11\equiv_m -7$ e gli interi $h$ tali che $11+3h\equiv_h -7$.
13. L'anello $\Z_6$ non è un dominio di integrità; come mai?
14. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_4$. In questo anello $[2]_4$ è cancellabile?
15. Calcolare: $13\modbin 7$, $(-13)\modbin 7$, $13\modbin -7$, $(-13)\modbin -7$,
16. Calcolare (a mente, ci mancherebbe!) $78598!\modbin 6756$.
17. Vero o falso? $\Z_5=\set{[12]_5,[9]_5,[-12]_5,[100]_5,[-4]_5}$

2/12

Discussione di esercizi dalla lezione precedente.

Metodi dell'aritmetica modulare, con esempi di calcoli rapidi; tra questi: alcuni criteri di divisibilità (per 3, 9, 11). (Per i più curiosi, altri esempi sono in un articolo divulgativo, già menzionato.)

Interpretazione delle funzioni caratteristiche come applicazioni a valori in $\Z_2$. 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' (che traducono i connettivi proposizionali $\xor$ e $\land$) alla luce di questo isomorfismo; espressione del complemento e negazione. A questo proposito, si veda la parte finale delle note sulle strutture booleane.

Algoritmo euclideo (delle divisioni successive) per la ricerca di un MCD tra due numeri interi (descrizione e giustificazione; si vedano anche le note su questo argomento; un altro file disponibile è nel sito docenti della Professoressa Celentani). Un'osservazione per la sua velocizzazione.

Estensione dell'algoritmo euclideo e teorema di Bézout (la dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, non quella nel libro di testo) nelle forme qui elencate: se $a,b\in\Z$ e $d$ è un massimo comun divisore tra $a$ e $b$ in $\Z$, allora:

• $d$ è una combinazione lineare di $a$ e $b$ in $\Z$;
• 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 qui 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 quoziente di $\Z$; equazioni congruenziali di primo grado ad una incognita: se $a$, $c$ ed $m$ sono interi, e $m\ne 0$, 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$. Criterio di esistenza di soluzioni per le equazioni congruenziali di questo tipo.

Esercizi proposti:

1. Calcolare (a mente) $\rest(72543618991175,9)$ e $\rest(72543618991175,3)$, e poi $\rest(626\cdot 3125,3)$.
2. Utilizzando l'algoritmo euclideo trovare in $\Z$ un MDC $d$ tra $125$ e $57$ e poi scrivere $d$ come combinazione lineare tra questi due numeri. Ripetere l'esercizio partendo da $125$ e $55$.
3. Nel granducato di Strampalia non circolano monete e la valuta locale, il tallero strampalese, viene emesso solo in due tagli: la banconota da 15 talleri e quella da 33 talleri. Usando il teorema di Bézout, spiegare quali pagamenti in talleri strampalesi possono essere effettuati in contanti (è ammessa la possibilità di pagare ricevendo un resto).
4. Svolgere gli esercizi da 5 ad 9, 11 e 12 da Tautologie, insiemi, aritmetica (la scrittura $ax\equiv c\pmod m$ sta per $ax\equiv_m c$).
5. Trovare due soluzioni dell'equazione congruenziale $87x+32\equiv_{100} x+4$.
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.

5/12

Rapidi commenti su esercizi della lezione precedente.

Come conseguenza del criterio di esistenza di soluzioni per un'equazione congruenziale di primo grado ad una incognita: determinazione degli elementi invertibili nei quozienti di $\Z$. Verifica diretta del fatto (già noto) che, per ogni intero $m\ne 0$, tutti gli elementi non invertibili in $\Z_m$ sono divisori dello zero. Sempre nel caso $m\ne 0$, sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità; (3) $m$ è primo.

Equazioni della forma $AX=C$ in un arbitrario anello commutativo unitario: discussione sui possibili insiemi di soluzioni nei casi in cui: $A$ è invertibile; $A$ è cancellabile; $A$ è un divisore dello zero. Di conseguenza: l'insieme delle soluzioni di un'equazione congruenziale $(*)$: $ax\equiv_m c$ (dove $a,c,m\in\Z$ e $m\ne 0$; d'ora in avanti queste notazioni restano fissate) è una classe di resto modulo $m$ se e solo se $a$ ed $m$ sono coprimi (in questo caso noi diciamo che $(*)$ è ridotta).

Metodi di semplificazione: data l'equazione congruenziale $(*)$ come sopra:

1. 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);
2. per ogni $k\in\Z$, se $k\ne 0$, l'equazione congruenziale $akx\equiv_{mk} ck$ è equivalente a $(*)$;
3. per ogni $t\in\Z$, se $t$ è coprimo con $m$, l'equazione congruenziale $atx\equiv_{m} ct$ è equivalente a $(*)$.

Come ovvio, le osservazioni (ii) e (iii) vengono usate per dividere gli interi $a$ e $c$ (e, nel caso di (ii) anche $m$) per loro divisori comuni. Alcuni esempi.

Un algoritmo (non l'unico possibile) per l'individuazione delle soluzioni dell'equazione congruenziale $(*)$: (1) detto $d$ un MCD tra $a$ ed $m$, se $d$ non divide $c$ l'equazione non ha soluzioni e l'algoritmo termina, altrimenti si sostituiscono $a$, $m$ e $c$ con $a_1=a/d$, $m_1=m/d$, $c_1=c/d$, ottenendo l'equazione $a_1x\equiv_{m_1} c_1$ equivalente a $(*)$; (2) $a_1$ ed $m_1$ sono coprimi, quindi $[a_1]_{m_1}$ è invertibile; se ne determina l'inverso $[u]_{m_1}$ (lo si può fare, in assenza di metodi più rapidi, utilizzando l'algorimo euclideo esteso descritto alla lezione precedente per ottenere interi $u$ e $v$ tali che $1=a_1u+m_1v$, sicché $[u]_{m_1}=[a_1]_{m_1}^{-1}$); (3) l'algoritmo ora termina fornendo $[uc_1]_{m_1}$, che è l'insieme delle soluzioni dell'equazione $(*)$.

Sia in partenza che al passo (2) è possibile (anzi, è bene farlo) applicare i metodi di semplificazione delle equazioni congruenziali discussi sopra.

Osservazione: risolvere l'equazione congruenziale $(*)$ è equivalente a risolvere l'equazione diofantea $ax+my=c$ e quindi anche a risolvere l'equazione congruenziale $my\equiv_a c$.

Ulteriore conseguenza: determinazione di tutte le soluzioni di un'equazione diofantea della forma $ax+by=c$ per interi $a,b,c$.

Elementi periodici in un gruppo; periodo di un elemento periodico; nei gruppi finiti tutti gli elementi sono periodici. Se $x$ è un elemento periodico di periodo $m$ di un gruppo (con operazione moltiplicativa), allora, per ogni $a\in\Z$, $x^a=x^{a\,\modbin\,m}$, quindi per ogni $a,b\in\Z$ si ha $x^a=x^b\iff a\equiv_m b$; come ulteriore conseguenza: il sottogruppo generato da $\set x$ in $G$ (cioè $\set{x^n\mid n\in\Z}$) ha esattamente $m$ elementi. Qualche esempio. Nozione di caratteristica di un anello unitario.

Esercizi proposti:

1. Delle equazioni congruenziali che seguono, dire quali hanno lo stesso insieme di soluzioni di $18x\equiv_{21}9$ (non calcolare le soluzioni):
   $6x\equiv_{21}3$, $6x\equiv_{7}3$, $2x\equiv_{7}1$, $x\equiv_{21}4x+9$, $60x\equiv_{7}30$, $60x\equiv_{70}30$, $54x\equiv_{21}27$, $54x\equiv_{63}27$, $-3x\equiv_{21}9$, $3x\equiv_{21}-9$, $x\equiv_{7}-3$, $-3x\equiv_{21}28$.
2. Dando per nota l'uguaglianza $3=117\cdot 13+66(-23)$, trovare gli insiemi delle soluzioni delle equazioni congruenziali $66 x\equiv_{117}10$, $660 x\equiv_{1170}90$ e $1170 x\equiv_{660}90$.
3. Svolgere l'esercizio 10 da Tautologie, insiemi, aritmetica.
4. 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. Si determinino tutti gli interi $u$ tali che $20(u-1)\equiv_{28}4(u-2)$ e tutti gli interi $v$ tali che $20(v-1)\equiv_{28}4v-2$.
7. In $\Z_{48}$ si determini, ove possibile, l'inverso di: $[7]_{48}$, $[9]_{48}$, $[11]_{48}$, $[-13]_{48}$, $[47]_{48}$. Capire perché c'è davvero bisogno di far calcoli in una sola occasione.
8. Calcolare il periodo di $[2]_9$ (nel gruppo degli invertibili di $\Z_9$) e quindi $2^{100} \modbin 9$.
9. Svolgere l'esercizio 3 dal compito del 4 ottobre 2022.
10. Svolgere l'esercizio 2 dal compito del 18 giugno 2019 (come di abitudine in casi analoghi, nel contesto di questo esercizio la scrittura $\bar a$, dove $a$ è un numero intero, indica $[a]_9$).

7/12

Anelli di polinomi (ad una indeterminata) su un anello commutativo unitario (si vedano le relative note, dove, fare attenzione!, l'insieme di numeri interi positivi è talvolta indicato con $\N^+$, ed anche le notazioni per la composizione tra applicazioni e l'immagine di elementi mediante applicazioni, lì spiegate, non coincidono con quelle usate in altre parti del corso). Definizione, primissime proprietà, terminologia essenziale (grado, successione dei coefficienti, coefficiente direttore, termine noto, polinomi monici, polinomi costanti); esempi. Proprietà universale per anelli di polinomi. Come conseguenze ed esempi: unicità a meno di isomorfismi dell'anello dei polinomi ad una indeterminata su un assegnato anello commutativo unitario (l'esistenza è non stata dimostrata); omomorfismi di sostituzione.

Gradi di somma, differenza e prodotto tra due polinomi.

Urgente: come indicato nell'avviso nella pagina principale del corso, si terrà una riunione teams di esercitazione nella mattina di venerdì 9; per potervi partecipare è necessario iscriversi al team dedicato al ricevimento; i dettagli sono nell'avviso.

Esercizi proposti:

1. Completare, come suggerito nelle note, la verifica della proprietà universale per anelli di polinomi.
2. 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]$ (qui e negli esercizi che seguono, per ogni intero $a$ il simbolo $\bar a$ rappresenta le classe di resto di $a$ nel modulo indicato dal contesto). Stabilire per quali $n$ il grado di $f_n$ è $5$ e trovare il grado di $f_n$ nei casi rimanenti.
3. Per ogni numero primo positivo $p$, si stabilisca il grado del polinomio $f_p:=\overline{22}x^5+\bar 8 x^4 - \bar7x^2+\bar 3$ a coefficienti nel campo $\Z_p$. Per quali primi positivi $p$ il polinomio $f_p$ è monico?
4. Vero o falso: Sia $A$ un anello commutativo unitario non nullo tale che ogni polinomio non nullo nell'anello di polinomi $A[x]$ sia monico. Allora $A$ è isomorfo a $\Z_2$ (l'osservazione inversa è stata vista a lezione).
5. Vero o falso: se $A$ è un anello booleano, anche $A[x]$ è booleano.
6. Sia $f$ il polinomio $\bar 7x^3-\bar 1\in\Z_{43}[x]$. Trovare, se esiste, (o spiegare perché non esiste)
   • un polinomio $g\in\Z_{43}[x]$ tale che $fg$ sia monico di grado 10;
   • un polinomio $h\in\Z_{43}[x]$ tale che $f+h$ abbia grado 2;

12/12

Se $n$ è un intero maggiore di 1 che non è primo, allora $n$ è divisibile per un primo positivo $p\le \sqrt n$.

Discussione dell'ultimo esercizio dalla lezione precedente.

Sia fissato un anello commutativo unitario $A$. Se il polinomio $f\in A[x]$ ha coefficiente direttore cancellabile (in $A$), allora $f$ stesso è cancellabile in $A[x]$ ed inoltre vale per $f$ ed un qualsiasi polinomio $g\in A[x]$ la regola di addizione dei gradi: $\nu(fg)=\nu(f)+\nu(g)$ e $\cd(fg)=\cd(f)\cd(g)$. $A[x]$ è un dominio di integrità se e solo se lo è $A$, ovvero se e solo se vale, in $A[x]$, la regola di addizione dei gradi per ogni coppia di polinomi. In questo caso si ha anche $\U(A[x])=\U(A)$. Un esempio che mostra come queste proprietà possano non valere se $A$ non è integro. Qualunque sia $A$, i polinomi in $A[x]$ di grado maggiore di zero e coefficiente direttore cancellabile in $A$ (ad esempio, $x$) non sono invertibili; di conseguenza gli anelli di polinomi non sono mai campi.

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. Se $A$ è 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 valgono il teorema di Bézout e le sue conseguenze (ma, vedi il primo degli esercizi, il teorema di Bézout non vale in $\Z[x]$). Senza dimostrazione: se $A$ è un anello fattoriale, allora $A[x]$ è fattoriale (ad esempio, questo accade se $A$ è un campo oppure $A=\Z$).

Applicazione polinomiale definita da un polinomio. Radici di un polinomio. Le radici di un polinomio sono radici anche dei suoi multipli (e quindi sono tutte e sole le radici di ciascuno dei suoi associati). Se $A$ è un dominio di integrità le radici di un prodotto sono tutti e soli gli elementi radici di almeno uno dei fattori.

Teorema del resto: se $f\in A[x]$ e $c\in A$, 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.

Esercizi proposti:

1. Provare che, in $\Z[x]$, il numero (ovvero: polinomio costante) $2$ è irriducibile e non divide $x$. Dedurne che $1$ è un MCD tra $2$ e $x$ ma, come suggerito in aula, non è una combinazione lineare tra $2$ e $x$ in $\Z[x]$.
2. Effettuare la divisione, in $\Q[x]$, del polinomio $2x^4+1$ per $3x+2$. Dividere poi, in $\Z_5[x]$, il polinomio $\bar 2x^4+\bar 1$ per $\bar 3x+\bar 2$ (sono gli stessi polinomi di prima "riguardati modulo 5").
3. In $\Z_3$, e con riferimento a polinomi in $\Z_3[x]$:
   • trovare tutte le radici del polinomio $x^2-x+\bar 1\in\Z_3[x]$,
   • quelle del polinomio $x^{50}+x^{35}+\bar 1$,
   • e quelle del polinomio $(x+\bar 1)^5((x-\bar 1)^7+\bar 1)$.
4. Si costruisca, se possibile, un polinomio di grado 300 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-100\le n \lt 100$.
5. Per ogni primo positivo $p$, sia $f_p$ il polinomio $\bar 3x^4+\bar 2 x^3 +\bar 2 x^2+ x+ \bar 2\in\Z_p[x]$. Determinare:
   1. i primi positivi $p$ tali che $f_p$ abbia $\bar 1$ come radice;
   2. i primi positivi $p$ tali che $f_p$ sia divisibile per $x+\bar 1$.
6. Decidere:
   1. quanti sono i polinomi di grado 2 in $\Z_5[x]$;
   2. quanti sono i polinomi monici di grado 4 in $\Z_5[x]$ che abbiano (almeno) $\bar 1$ e $\bar 2$ come radici.
7. Svolgere, almeno in piccola parte, gli esercizi nr. 1, 2 e 8 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo e senza preoccuparsi del `monico' nell'esercizio 1.

14/12

Conseguenze del Teorema di Ruffini generalizzato: se $A$ è dominio di integrità unitario si ha: (1) se $0_A\ne f\in A[x]$, allora $f$ ha al più $\nu(f)$ radici in $A$; (2) principio di identità dei polinomi: se, inoltre, $A$ è infinito due polinomi in $A[x]$ coincidono se e solo se definiscono la stessa applicazione polinomiale. Verifica del fatto che (1) e (2) non valgono per anelli non integri e (2) non vale per nessun anello finito né per anelli booleani.

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

Caratterizzazione dei polinomi irriducibili nell'anello dei polinomi su un campo; rapporti tra esistenza di radici ed irriducibilità. Un esempio: determinazione dei polinomi irriducibili di grado al più quattro in $\Z_2[x]$.

Cenni a metodi di fattorizzazione ed a metodi di ricerca di radici di polinomi.

Descrizione dei polinomi irriducibili sul campo reale; 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. Criterio di irriducibilità di Eisenstein (non dimostrato); come conseguenza: 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]$; come conseguenza: le radici razionali dei polinomi monici a coefficienti interi sono numeri interi.

Introduzione informale a diverse nozioni di grafo. Grafi semplici (definiti in termini di lati, o archi) e loro rappresentazione grafica. Definizione di multigrafo semplice (senza cappi).

Esercizi proposti:

1. Dedurre il fatto che i polinomi di grado dispari su $\R$ hanno sempre radici come conseguenza della fattorialità di $\R[x]$ e dalla descrizione dei polinomi irriducibili in $\R[x]$.
2. Se possibile, trovare un polinomio di coefficiente direttore 340 che sia associato in $\Q[x]$ a $3x^2-1$.
3. Sia $f=x^4-4\in \Z[x]$. Scrivere $f$ come prodotto di polinomi monici irriducibili in $\Q[x]$ e come prodotto di polinomi monici irriducibili in $\R[x]$.
4. Scrivere il polinomio $x^5-x\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Fare lo stesso per $x^5-x\in\Z_7[x]$.
5. 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]$.
6. Trovare tutte le radici in $\Q$ del polinomio $2x^{10}+x^9-x^8+12x^2-3$.
7. Il polinomio $50x^{12}-6x^5+18x-24$ è irriducibile in $\Q[x]$? E $x^3-9$?
8. Scrivere $x^3-3x^2+4$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
9. Per ogni $n\in\Z$, 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$.
10. 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$, $(8x^2+1)(x^2+3)$, $13x^9+50x^7+10$, $x^{1066}-7^{1066}$. Riguardati i polinomi precedenti a coefficienti in $\Z_5[x]$, dire quali sono irriducibili in $\Z_5[x]$.
11. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
12. 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, 6 dal compito di marzo 2019, 4 dal compito di giugno 2019, 4 dal compito di settembre 2019, 5 dal compito di febbraio 2020, 4 dal compito di giugno 2022, 5 dal compito di settembre 2022.

16/12

Definizione alternativa di grafo semplice, in termini di relazione di adiacenza. Terminologia: incidenza, grado, vertici isolati. Grafi completi.

Isomorfismi tra grafi (o tra multigrafi); proprietà che questi conservano. Esempi di grafi isomorfi e non. Sottografi.

Nozione di grafo planare (ovvero: piano).Esempi di grafi non planari e cenno al teorema di Kuratowski.

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

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

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$; è un albero se e solo se per ogni coppia $(a,b)$ di vertici distinti di $G$ esiste esattamente un cammino in $G$ da $a$ a $b$.

Rappresentazione radicale di un albero; foglie. Osservazione: le foreste finite sono grafi planari. 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. Numero di vertici e di lati in un albero finito.

Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso 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$.

Avviso: ricordo ancora la riunione dedicata agli esercizi che terremo lunedì 19 in aula G3, come da avviso nella pagina principale del corso.

Esercizi proposti:

1. Fornire (utilizzando i suggerimenti dati a lezione e ragionando per induzione sul numero dei lati) una seconda dimostrazione del fatto che il doppio del numero dei lati di un multigrafo finito è la somma dei gradi dei suoi vertici.
2. Se $G=(V,L)$ è un grafo semplice, si chiama grafo complementare di $G$ il grafo $(V,\P_2(V)\setminus L)$. Dimostrare che se due grafi $G$ e $G'$ sono isomorfi, anche il grafo complementare di $G$ ed il grafo complementare di $G'$ sono isomorfi tra loro.
3. Elencare, a meno di isomorfismi, i grafi con insieme dei vertici di cardinalità minore di 4. Quelli su quattri vertici sono elecati in lista dei grafi su quattro vertici; ma va verificato che i grafi lì rappresentati sono effettivamente a due a due non isomorfi e che la lista è esuastiva (cioè che ogni grafo su quattro vertici è isomorfo ad uno dei grafi nella lista). Nella stessa lista, decidere quali grafi sono connessi e quali sono alberi o foreste.
4. Esercizi da Grafi, ad esclusione del nr. 4.
5. Disegnare, a meno di isomorfismi, tutti gli alberi con (esattamente) cinque vertici.
6. Si considerino i grafi $G=(V,L)$ che verificano la proprietà $\Phi$: “$|V|=6=|L|$ ed esistono in $G$ (almeno) un vertice di grado 4 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, a meno di isomorfismi, tutti i grafi che verificano $\Phi$.
7. Stabilire per quali interi positivi $n$ il grafo completo su $n$ vertici abbia cammini euleriani e per quali abbia circuiti euleriani.