27/9

La prima parte delle lezione è stata dedicata ad informazioni generali sui servizi 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, proposizione (o formula chiusa), sintassi e semantica.

Introduzione ai connettivi proposizionali, descritti solo semanticamente. Tavole (o tabelle) di verità. I connettivi di di negazione (NOT, $\lnot$), congiunzione (AND, $\land$), disgiunzione inclusiva (OR, $\lor$) e disgiunzione esclusiva ($\xor$).

Per il contenuto di questa lezione e delle prossime, si veda Logica rudimentale.

Esercizi proposti:

1. Dal solo punto di vista dei valori di verità la frase 'Pippo è un simpatico canoista' è costituita da due frasi unite tra loro da un connettivo proposizionale. Quali frasi e quale connettivo?
2. Stesso esercizio relativo alla frase 'sono stanco ma soddisfatto'.

29/9

Discussione degli esercizi della lezione precedente.

Ancora sui connettivi proposizionali e sulla loro espressione nel linguaggio naturale: il bicondizionale ('doppia implicazione', 'se e solo se', $\shiff$). Forme proposizionali e loro tavole di verità; esempi. Forme proposizionali logicamente equivalenti. Tautologie e contraddizioni. Alcuni esempi di tautologie tra cui i principi del terzo escluso e di non contraddizione, doppia negazione; tautologie di iteratività (o idempotenza), commutatività, associatività e distributività per i connettivi $\land$ e $\lor$; commutatività per $\shiff$ e $\xor$. $\xor$ come negazione del condizionale. Leggi di De Morgan.

Connettivo condizionale (implicazione, $\implica$). Discussione della sua semantica, con esempi. Due tautologie: negazione di una implicazione ed implicazione come disgiunzione.

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

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. Negare la frase 'Se non studi ti boccio'.
4. Da Logica rudimentale, svolgere (alcuni tra) gli esercizi A, B, C2, D, E1.

1/10

Discussione di alcuni esercizi dalla lezione precedente. Espressioni verbali per le implicazioni. Altre tautologie sull'implicazione: doppia implicazione, contrapposizione, transitività.

Associatività del connettivo bicondizionale e del connettivo $\xor$ (con ulteriore discussione su forme equivalenti alla negazione di un bicondizionale). Tautologia della distributvità 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. Negazione di formule universali e di formule esistenziali.

Esercizi proposti:

1. 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?
2. Da Logica rudimentale, svolgere gli esercizi C3 ed E6.
3. Negare: “Se domani piove e l'auto funziona, o andremo a casa oppure mangeremo un gelato”.
4. Negare la forma proposizionale $(p\land q)\implica (r\lor s)$.
5. La forma proposizionale $\bigl(q\shiff r\bigr)\iff \bigl((p\land q)\shiff(p\land r)\bigr)$ è una tautologia? E $\bigl(q\implica r\bigr)\iff \bigl((p\land q)\implica(p\land r)\bigr)$? E $\bigl(q\implica r\bigr)\implica \bigl((p\land q)\implica(p\land r)\bigr)$?
6. Verificare (alcune tra) le tautologie in esempi di tautologie.
7. Supponendo che $\alpha$, $\beta$, $\gamma$ e $\delta$ siano formule, negare la formula $\alpha\lor(\forall x(\exists y(\beta)\implica\exists y(\gamma\land\delta)))$.

4/10

Discussione di esercizi dalla lezione precedente.

Occorrenze libere o vincolate di variabili. Formule chiuse. Predicati. Nelle sostituzioni di termini a variabili vengono sostituite solo le occorrenze libere delle variabili.

Il quantificatore $\exists!$.

Quantificatori ristretti e loro interpretazione. Negazione di formule con quantificatori ristretti. Esempi, tra cui: formule universali o esistenziali ristrette ad una condizione sempre falsa.

Alcune regole della logica dei predicati. Frasi contenenti più quantificatori; comparazione tra formule del tipo $\forall x(\exists y(\dots))$ e del tipo $\exists y(\forall x(\dots))$.

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

Esercizi proposti:

1. 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)))$?
2. Negare: Ogni mucca verde mangia cioccolata.
3. Negare: Ogni mese, se mi arriva la bolletta del gas la pago.
4. Da Logica rudimentale, svolgere gli esercizi H, dando priorità ad H1, H5 e H6.

6/10

Discussione di esercizi dalla lezione precedente.

Insieme vuoto e sua unicità. Inclusione tra insiemi (nozione di sottoinsieme o parte). Il singleton di un elemento. Comparazione tra inclusione ($\sseq$) e appartenenza: è fondamentale distinguere bene tra queste due nozioni. Alcuni esempi: per ogni $x$ si ha $\vuoto\subseteq x$ e $x\subseteq x$, ma $x\notin x$; invece $\vuoto\in x$ è vero per alcuni insiemi $x$, falso per altri.

Estensione di un predicato unario; cenni a problemi fondazionali. L'antinomia di Russell. Presentazione informale degli assiomi di separazione. Non esiste "l'insieme di tutti gli insiemi".

L'insieme $\P(x)$ delle parti di un insieme $x$. Il singleton $\set x$ di un insieme $x$.

Comparazione tra i connettivi di equivalenza e implicazione da una parte, le relazioni di uguaglianza e inclusione tra insiemi dall'altra. Esempio di traduzione di una tautologia in una formula insiemistica. Altri esempi dello stesso tipo verranno esaminati nella prossima lezione.

Esercizi proposti:

1. Descrivere, elencandone gli elementi, $\P(\vuoto)$, $\P(\set 1)$, $\P(\set {1,1})$ e $\P(\set {1,2})$.
2. Sia $x=\set{\set{\set{\set\vuoto}}}$. Quanti elementi ha $x$? Quante parti ha $x$?
3. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{2,1,3}$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{4,2,1,3}$.
4. Elencare gli elementi di questi insiemi: $x=\set{a\in\N\mid a\le 12 \land a>7}$; $y=\set{a\in\N\mid a \gt 2 \implica a^2=3}$; $z=\set{a\in\N\mid a \lt 2 \land a \ge 33}$; $t=\set{a\in\N\mid a = a+4}$.

8/10

Questa lezione si è svolta esclusivamente in remoto, per la non agibilità dell'edificio che ospita l'aula destinata al corso di algebra.

Discussione degli esercizi dalla lezione precedente.

Operazioni insiemistiche binarie di unione, intersezione e differenza simmetrica. Identità insiemistiche che coinvolgono queste operazioni dedotte da tautologie (proprietà associativa, commutativa, iterativa, distributiva). Alcune osservazioni sulla differenza simmetrica (per ogni $a$ si ha $a\ds a=\vuoto$ e $a\ds \vuoto=a$; esplicitazioni di $a\ds b$ (come $(a\cup b)\setminus (a\cap b)$ e come $(a\setminus b)\cup(b\setminus a)$) per insiemi $a$ e $b$). L'operazione binaria di differenza tra insiemi; complemento di un insieme in un insieme che lo contenga. Diverse formule tra quelle in Tautologie ed identità insiemistiche; formule insiemistiche di De Morgan (per terne arbitrarie di insiemi).

Diagrammi di (Euler-)Venn. Diagrammi di Venn generici e loro uso per dimostrare formule insiemistiche (di uguaglianza o di inclusione) o per la costruzione di controesempi. Diagrammi generici per coppie e per terne di insiemi. Diversi esempi.

L'unione unaria $\bigcup a=\set{x\mid \exists b\in a(x\in b)}$ di un insieme $a$; qualche esempio. Riduzione dell'unione binaria all'unione unaria: per ogni $a,b$ si ha $a\cup b=\bigcup \set{a,b}$.

Un file di annotazioni scritte durante questa lezione è disponibile, solo per gli iscritti al corso, nell'area destinata al materiale didattico per questo corso nel sito docenti unina.

Esercizi proposti:

1. 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$.
2. Dimostrare (lo si è fatto solo parzialmente a lezione) 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$.
3. Rappresentare, in un diagramma di Venn generico, il termine insiemistico $a\cap(b\ds c)$.
4. 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$.
5. Calcolare $\bigcup \vuoto$, $\bigcup\set{\vuoto}$, e poi $\bigcup\set{x}$ per un arbitrario insieme $x$.
6. Calcolare $\bigcup A$ in ciascuno dei seguenti casi: (1) $A=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $A$ è l'insieme delle parti 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$.

11/10

Discussione di esercizi dalla lezione precedente. Descrizioni di un insieme nella forma $\set{t(x,y,z,\dots)\mid \dots}$.

L'intersezione (unaria) $\bigcap a=\set{x\mid \forall b\in a(x\in b)}$ di un insieme non vuoto $a$. Esempi. Riduzione dell'intersezione binaria all'intersezione unaria. Scritture alternative per rappresentare unioni o intersezioni unarie (come in $\bigcap_{x\in a}x$ per indicare $\bigcap a$). Formule di De Morgan e di distributività generalizzata per unione e intersezione unarie: per ogni $s$ ed $a$, se $a\ne\vuoto$, $s\setminus \bigcup a=\bigcap_{x\in a}(s\setminus x)$ e $s\setminus \bigcap a=\bigcup_{x\in a}(s\setminus x)$; per ogni $s$ ed $a$, $s\cap \bigcup a=\bigcup_{x\in a}(s\cap x)$ e, se $a\ne \vuoto$, $s\cup \bigcap a=\bigcap_{x\in a}(s\cup x)$.

Coppie ordinate e loro proprietà caratteristica. Prodotto cartesiano tra due insiemi. Terne ordinate ed analoga proprietà caratteristica. Se $a$ e $b$ sono due insiemi finiti, il numero degli elementi del prodotto cartesiano $a\times b$ è il prodotto tra il numero degli elementi di $a$ ed il numero degli elementi di $b$.

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)=\Corr(a,a)$ quello delle relazioni binarie in $a$.

Esercizi proposti:

1. Decidere quali tra questi due diagrammi di Venn per una quaterna di insiemi sono generici: primo e secondo.
2. Calcolare $\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$.
3. Svolgere l'esercizio nr. 6 da questa raccolta ("per le vacanze di pasqua"). Gli esercizi che precedono sono anche utili, per un ripasso generale.
4. Dimostrare che, per ogni $x$ e $y$:
   1. $x\times y=\vuoto$ se e solo se uno tra $x$ e $y$ è vuoto (un'implicazione è stata discussa in aula);
   2. $x\times y=y\times x$ se e solo se o $x=y$ oppure uno tra $x$ e $y$ è vuoto.
5. (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!).

13/10

Discussione di esercizi dalla lezione precedente.

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

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). Descrizioni di applicazioni 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 nunero naturale $k$, l'insieme $\P_k(a)$ delle $k$-parti, cioè parti con esattamente $k$ elementi, di $a$).

Prodotto relazionale tra corrispondenze.

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$. Sua descrizione esplicita.

Associatività del prodotto relazionale e quindi del prodotto operativo ('composizione') tra applicazioni.

Alcuni tipi di applicazioni: applicazioni costanti; l'applicazione identica $\id_a$ in un insieme $a$. L'immagine $\im f$ dell'applicazione $f$ (è una parte del codominio); applicazioni suriettive. Restrizioni (e, viceversa, prolungamenti) di applicazioni. L'immersione in un insieme di una sua parte. Restrizioni come composte con immersioni.

Esercizi proposti (sono tanti, non da svolgere tutti subito. Dare priorità a 3, 4, 5, 7, 8):

1. 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})$.
2. 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$.
   Come si potrebbe descrivere in modo sintetico la relazione binaria in $\Z$ che ha come grafico l'insieme $(\N\times\N)\cup ((\Z\setminus \N)\times(\Z\setminus \N))$?
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\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$;
   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. Siano $\N$ l'insieme dei numeri naturali e $S=\set{1,2,3}$. Siano poi $\alpha$ la relazione binaria in $S$ definita da: $(\forall x,y\in S)(x\mathrel\alpha y\iff x\lt y)$ e $\beta$ la corrispondenza da $S$ ad $\N$ di grafico $\set{2}\times\set{x\in\N\mid x\lt 10}$. Descrivere la corrispondenza prodotto $\alpha\beta$ e la relazione binaria $\alpha^2=\alpha\alpha$.
6. Siano $\alpha$ e $\bar\alpha$ 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{\bar\alpha}x\iff n\notin x$. Sia poi $\beta$ 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{\beta}y\iff x\sseq y$. Descrivere $\alpha\beta$ e $\bar\alpha\beta$.
7. Date le applicazioni $f\colon n\in\Z\mapsto n+1\in\Z$ e $g\colon n\in\Z\mapsto n^2\in\Z$, descrivere esplicitamente $g\circ f$ e $f\circ g$.
8. Date le applicazioni $f\colon x\in\P(\Z)\mapsto x\cap\N\in\P(\Z)$ e $g\colon n\in\Z\mapsto \set n\in\P(\Z)$, descrivere esplicitamente $f\circ g$.
9. 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$.
10. Svolgere gli esercizi nr. 7 e 8 dalla raccolta "per le vacanze di pasqua".

15/10

Discussione di molti esercizi dalla lezione precedente.

Ulteriori osservazioni sulla suriettività. Discussione su 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$ (!!!!!).

La composta tra due applicazioni (componibili) suriettive è certamente suriettiva; viceversa, se una composta $f\circ g$ è suriettiva, allora $f$ è suriettiva (ma $g$ può non esserlo).

Ridotte di un'applicazione; ridotta all'immagine.

Applicazioni iniettive. Definizione in due forme equivalenti. 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))$. Di conseguenza, ogni applicazione il cui dominio abbia meno di due elementi è certamente iniettiva. Le restrizioni delle applicazioni iniettive sono iniettive. Esempi. Applicazioni biettive.

La composta tra due applicazioni (componibili) iniettive è certamente iniettiva; viceversa, se una composta $f\circ g$ è iniettiva, allora $g$ è iniettiva (ma $f$ 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 $f\circ g$ tale che $f$ non sia iniettiva e $g$ non sia suriettiva (ecco una versione dell'esempio: $A=\set 1$ e $B=\set{1,2}$; $g$ è l'immersione di $A$ in $B$, $f$ è l'unica applicazione da $B$ ad $A$, cioè la costante $1$. Allora $f\circ g=\id_A$).

Esercizi proposti:

1. Verificare che ogni immersione è iniettiva.
2. Vero o falso? Ogni applicazione ha una restrizione iniettiva ed una ridotta suriettiva.
3. Sia $f\colon a\to b$ un'applicazione costante. Esattamente in quali casi $f$ è suriettiva? Ed esattamente in quali casi $f$ è iniettiva?
4. Delle applicazioni proposte negli esercizi della lezione scorsa, stabilire se sono iniettive.
5. 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$.
6. Di ciascuna delle seguenti applicazioni, decidere se sono iniettive e se sono suriettive:
   • $a\colon n\in\N\mapsto n+1 \in\N$
   • $c\colon n\in\N\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\N$
   • $b\colon n\in\Z\mapsto n+1 \in\Z$
   • $d\colon n\in\Z\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\Z$

18/10

Discussione di esercizi dalla lezione precedente.

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}$. Caratterizzazioni di iniettività, suriettività e biettività in termini di questi ultimi insiemi. Alcuni esempi.

Sezioni, retrazioni e inverse di un'applicazione (se $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$ ed è un inversa di $f$ se e solo se è sia una sezione che una retrazione). Un'applicazione $f\colon a\to b$ è suriettiva se e solo se ammette sezioni, è iniettiva se e solo se ammette retrazioni oppure $a=\vuoto$.

Proprietà di neutralità delle applicazioni identiche (se $f\colon a\to b$ è un'applicazione, allora $\id_b\circ f=f\circ \id_a=f$).

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$. Esempi di sezioni, retrazioni ed inverse.

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

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

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 (dare priorità a 1, 2, 6, 8, 10, 11, 12, 13):

1. Sia $f\colon x\in\P(\Z)\mapsto x\cup\N\in\P(\Z)$. Descrivere $\vecf(\P(\N))$ e $\avecf(\set\vuoto)$.
2. Provare che, se $f\colon a\to b$ è un'applicazione, allora $x\sseq\avecf(\vecf (x))$ per ogni $x\in\P(a)$ e $\vecf(\avecf (y))\sseq y$ per ogni $y\in\P(b)$ (queste inclusioni possono essere strette). Più in dettaglio: verificare che vale $\vecf(\avecf (y))=y\cap\im f$ per ogni $y\in\P(b)$.
3. 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 $f\circ g$ è $\vecg\circ \vecf$ e che, analogamente, $(g\circ f)\avec{\phantom 1}3=\avecf\circ\avecg$.
4. Provare che per ogni insieme $a$ sia l'applicazione immagine che l'applicazione antiimmagine definite da $\id_a$ coincidono con $\id_{\P(a)}$.
5. Sia $f$ un'applicazione biettiva. Provare che $\vecf$ e $\avecf$ sono biettive, l'una inversa dell'altra.
6. 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)$.
7. Provare che, come accade per le applicazioni, per ogni $a$ e $b$ ed ogni $\rho\in\Corr(a,b)$, si ha $\id_a f=f\id_b=f$ (stiamo qui facendo uso del prodotto relazionale).
8. 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 se ne 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.
9. Si trovi l'inversa dell'applicazione al punto (ii) dell'esercizio 7 di quelli per le vacanze di pasqua.
10. 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.
11. 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.
12. Per caso le due applicazioni agli esercizi precedenti sono l'una inversa dell'altra?
13. Verificare che l'immersione di $\set 1$ in $\set{1,2}$, pur non essendo biettiva ha un'unica retrazione.

20/10

Discussione di esercizi dalla lezione precedente. Osservazione: un'applicazione $f\colon a\to a$ (di dominio e codominio uguali) tale che $f\circ f=\id_a$ è sicuramente biettiva (ed ha sé stessa come inversa).

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. Osservazione: se $a$ è un insieme con più di un elemento, l'operazione di composizione nell'insieme $T(a)=\Map(a,a)$ delle trasformazioni di $a$ non è commutativa. Introdotta anche l'operazione di concatenazione tra parole. Cenno ai teoremi di associatività e di commutatività.

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

Elementi neutri a sinistra e a destra; elementi neutri. Gli elementi neutri (anche solo a destra o sinistra) rispetto ad operazioni binarie già introdotte (addizione, moltiplicazione e sottrazione in insiemi numerici, unione ed intersezione, composizione tra applicazioni)

Esercizi proposti (dare priorità a ):

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. Nell'insieme 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)$: 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. Per un arbitrario insieme $a$, determinare gli eventuali elementi neutri a destra, neutri a sinistra, neutri in $\P(a)$ rispetto alla differenza simmetrica e rispetto alla differenza insiemistica.
6. Studiare le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, e determinando gli elementi neutri a sinistra, a destra, neutri delle strutture da esse definite:
   • $\alpha\colon (a,b)\in \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}$.

22/10

Discussione di esercizi dalla lezione precedente.

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.

Semigruppi e monoidi.

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

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

Elementi simmetrizzabili. Esempi; identificazione degli elementi simmetrizzabili a destra, a sinistra, simmetrizzabili nel monoide delle trasformazioni di un insieme. Gruppi; alcuni esempi.

Gli elementi simmetrizzabili di un monoide $M$ ne costituiscono una parte chiusa $\U(M)$ (lo chiameremo 'il gruppo degli invertibili di $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).

Esercizi proposti:

1. Partendo dall'esempio di $(\Z,-)$, trovare un'operazione binaria in $\Z$ rispetto alla quale esista uno ed un solo elemento neutro a sinistra e non esistano elementi neutri a destra.
2. Delle seguenti strutture algebriche, dire quali sono commutative e quali sono semigruppi, monoidi, gruppi. Dove possibile, identificare i neutri e determinare gli elementi simmetrizzabili, descrivendone i simmetrici: $(X,+)$ ed $(X,\cdot)$, dove $X$ è uno tra $\N^*=\N\setminus\set 0$, $\N$, $\Z$, $\Q$; $(\P(a),*)$, per un arbitario insieme $a$, dove $*$ è una tra $\cap$, $\cup$, $\ds$.
3. Tornare alle operazioni proposte tra gli esercizi della lezione scorsa e, in quelle dotate di elemento neutro, determinare gli elementi simmetrizzabili, descrivendone i simmetrici.
4. 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,*)$.
5. 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.
6. Studiare la struttura algebrica $(S,*)$ dove $S=\Z\times\Z$ e $*$ è 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.

25/10

Lunga discussione di esercizi dalla lezione precedente.

Nozione di sottostruttura; sottosemigruppi (parti chiuse non vuote in un semigruppo), sottomonoidi (in un monoide: parti chiuse a cui appartiene l'elemento neutro). Esempio: in ogni monoide $M$ il gruppo degli invertibili $\U(M)$ è un sottomonoide (ed un gruppo).

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

Esercizi proposti:

1. Determinare gli elementi cancellabili in $(\P(a),\cup)$ ed in $(\P(a),\cap)$ se $a$ è un insieme non vuoto.
2. Determinare gli elementi cancellabili (anche solo a sinistra o a destra) in $(\Z\times\Z,*)$, dove $*$ è l'operazione binaria in $\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+\alpha 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$, provare che $a$ è simmetrizzabile in $(S,*,t)$ se e solo se $\sigma_a$ e $\delta_a$ sono suriettive, e che in questo caso esse sono anche biettive.

27/10

Discussione di esercizi dalla lezione precedente.

Ulteriori considerazioni sui gruppi. Sottogruppi e loro caratterizzazione (non dimostrata). Il gruppo simmetrico (o gruppo delle permutazioni) $\Sym(a)=\U(T(a))$ su un insieme $a$; esso è abeliano (cioè commutativo) se e solo se $a$ ha al massimo due elementi.

Tavola di Cayley di un'operazione binaria; alcuni esempi. Visualizzazione di proprietà in una tavola di Cayley: commutatività, esistenza di neutri sinistri o destri, simmetrizzabilità e cancellabilità (anche a sinistra o a destra). Tavole di Cayley di gruppi; il caso dei gruppi con due o tre elementi.

Omomorfismi; definizione e vari esempi. Isomorfismi. L'inversa di un isomorfismo è necessariamente un isomorfismo.

Esercizi proposti:

1. 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)$.
2. Scrivere la tavola di Cayley di $(\P(\set{1,2,3}),\cap)$.
3. 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.
4. 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)$ e confrontarla con quella, vista a lezione, di $(\P(a),\ds)$ per un insieme $a$ di due elementi.
5. Verificare che l'applicazione che ad ogni elemento $w$ del monoide delle parole $W$ su un alfabeto associa la lunghezza di $w$ (in $\N$) è un omomorfismo da $W$ a $(\N,+)$.
6. 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)$.
7. 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 20 ottobre. Provare che $n\in (\Z,+)\mapsto n-1\in (\Z,\alpha)$ è un isomorfismo.
8. 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 in alcuni esercizi nelle lezioni recenti. 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)$?

29/10

Discussione di esercizi dalla lezione precedente.

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à (esempi a proposito sono rimandati ad una fase più avanzata del corso). Gli isomorfismi conservano anche la cancellabilità (anche a destra o a sinistra). Invarianza delle proprietà algebriche 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'applicazione $x\mapsto S\setminus x$, da $(\P(S),\cup)$ a $(\P(S),\cap)$ (o viceversa). Isomorfismi e tavole di Cayley; usando queste: due gruppi costruiti su insiemi che abbiano entrambi due o entrambi tre elementi sono certamente isomorfi tra loro; esempio di due gruppi non isomorfi su insiemi di quattro elementi.

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.

Esercizi proposti:

1. Dimostrare che il monoide delle parole su un alfabeto costituito da un solo carattere è isomorfo al monoide $(\N,+,0)$.
2. Sia $(M,\cdot,t)$ un monoide isomorfo a $(\P(\Z),\cup,\vuoto)$. Di ciascuna delle seguenti affermazioni si dica se è vera, se è falsa oppure se non è possibile stabilire se sia vera o falsa (quest'ultima opzione significa che i dati forniti non sono sufficienti a determinare la risposta):
   1. $M$ è commutativo;
   2. $M$ ha esattamente un elemento simmetrizzabile;
   3. $M$ ha esattamente un elemento cancellabile.
   4. $\forall x\in M(x^2=x)$;
   5. $M\cap\Z\ne \vuoto$;
   6. $t\in M$.
3. Sia $G=\set{t,a,b,c}$ sia un insieme di quattro elementi (distinti). Assumendo che $*$ sia un'operazione binaria in $G$ tale che $(G,*)$ sia un gruppo con elemento neutro $t$, costruire (col metodo "del sudoku" usato nella lezione precedente per insiemi di due o tre elementi) la tavola di Cayley di $(G,*)$ in questi due casi:
   • quello in cui ogni elemento di $(G,*)$ coincide con il suo simmetrico;
   • quello in cui ciò non accade, assumendo che il simmetrico di $a$ sia $c$.
   Confrontare le tavole ottenute con quelle costruite nelle ultime due lezioni (discussioni di esercizi inclusi) per concludere che non esistono tre gruppi con quattro elementi a due a due non isomorfi.

3/11

Discussione di esercizi dalla lezione precedente.

Introduzione alla combinatoria; cardinalità di un insieme finito. Il principio di inclusione-esclusione, con verifica nel caso dell'unione tra due o tre insiemi finiti; richiamo: cardinalità dei prodotti cartesiani.

Il numero delle applicazioni e delle applicazioni iniettive tra due insiemi finiti. (Nel corso della lezione sono poi state viste varianti dello stesso problema: numero delle stringhe in un dato insieme di caratteri e di data lunghezza). 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 biettive da $a$ a $b$ se e solo se $|a|=|b|$. Nel caso, il loro numero è $|a|!$. In particolare, $|\Sym(a)|=|a|!$;
• esistono applicazioni suriettive da $a$ a $b$ se e solo se $|a|\ge |b|$ e $b=\vuoto\implica a=\vuoto$;
• 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.

Notazione: $b^a=\Map(a,b)$.

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 $\set{0,1}^S$ che a ciascuna parte $T$ di $S$ associa $\chi_{T,S}$ è biettiva; l'inversa manda ogni $f\in \set{0,1}^S$ in $\avecf(\set 1)\in\P(S)$.

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

1. Verificare, in modo diverso da come fatto a lezione, la formula di inclusione-esclusione per tre insiemi finiti (per ogni $a,b,c$ che siano insiemi finiti, $|a\cup b\cup c|=|a|+|b|+|c|-|a\cap b|-|a\cap c|-|b\cap c|+|a\cap b\cap c|$) utilizzando diagrammi di Venn, come a lezione abbiamo fatto per la formula analoga per due insiemi.
2. Siano dati due insiemi $a$ e $b$ tali che $|a|=7$ e $|b|=11$. 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,92}$, Quante sono le applicazioni $f$ da $a$ a $b$ tali che $\forall x\in a$$(f(x)\le 50)$? 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?

5/11

Discussione di esercizi dalla lezione precedente.

Cenni all'equipotenza ed alla comparazione tra cardinalità per insiemi infiniti ($|\N^*|=|\N|=|\Z|=|\Q|\lt|\R|=|\P(\N)|=|\R\times\R|$; per ogni $a$ si ha $|a|\lt|\P(a)|$).

Il numero delle parti ($2^{|S|}$) di un insieme finito $S$.

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, verifica della formula (già presentata) $x^{m+n}=x^mx^n$ per ogni elemento $x$ di un arbitrario semigruppo (o monoide) ed ogni $n,m\in\N^*$ (o anche ogni $n,m\in\N$ nel caso dei monoidi). Nuova dimostrazione (per induzione) della formula $|\P(S)|=2^{|S|}$ (per insiemi finiti $S$) preceduta da un lemma: per ogni insieme finito $S$ ed ogni $a\in S$, $|\P(S)|=2|\P(S\setminus\set a)|$. Dimostrata anche una variante dello stesso lemma: per ogni insieme finito $S$, ogni $a\in S$ ed ogni $k\in\N$, $|\P_{k+1}(S)|=|\P_{k+1}(S\setminus\set a)|+|\P_k(S\setminus\set a)|$.

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

1. Usando il principo di induzione, provare che per ogni $n\in\N^*$ si ha che $n^2$ è uguale a $1+3+\cdots+2n-1$ (la somma dei primi $n$ interi positivi dispari).
2. Usando il principo di induzione, provare che per ogni semigruppo $(S,\cdot)$ ed ogni elemento $x\in S$ si ha $x^{mn}=(x^m)^n$ per ogni $n,m\in\N^*$.
3. 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à.
4. 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$?
5. 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…)
6. Sia $f\colon a\to b$ un'applicazione biettiva. Verificare (se non lo si è già fatto in precedenza) che anche $\vecf\colon\P(a)\to\P(b)$ è biettiva e, quindi, che per ogni $k\in\N$ l'applicazione $x\in\P_k(a)\to\vecf(x)\in\P_k(b)$ è (ben definita e) biettiva.

8/11

Discussione di esercizi dalla lezione precedente.

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$ (segue da uno degli esercizi della lezione scorsa che questo numero è ben definito, cioè non varia se $a$ è sostituito da un qualsiasi altro insieme di cardinalià $n$). Osservazioni sui casi, banali, in cui $k$ vale 0, 1 o $n$, oppure $k>n$. Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$. Un lemma dalla lezione precedente mostra la formula ricorsiva: 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 chiusa: per ogni $k,n\in \N$ tali che $k\le n$, $\binom nk=n!/(k!(n-k)!)$.

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

Partizioni di un insieme (si veda la prima parte delle nuove note su partizioni ed equivalenze). Definizione, esempi, caratterizzazione. Principio della partizione (se $F$ è una partizione di un insieme finito $a$, allora $|a|=\sum_{b\in F}|b|$). Come applicazione: per ogni $n\in\N$, $2^n=\sum_{k=0}^n\binom nk$.

Esercizi proposti (dare priorità a 2, 3, 4, 5, 8, 9, 10):

1. Usando il principo di induzione, provare che per ogni $n\in\N^*$ si ha $\sum_{i=1}^ni=1+2+3+\cdots+n=n(n+1)/2=\binom {n+1}2$.
2. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_7(S)$.
3. Utilizzando la porzione del triangolo di Tartaglia-Pascal disponibile in questo sito, calcolare $\binom {13}5$ e poi $\binom {14}5$.
4. 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)$?
5. 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?
6. 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. (Pubblicità progresso) Siano $S$ l'insieme dei primi 90 numeri interi positivi e $T$ una sua parte costituita da 10 elementi. Calcolare la cardinalità dell'insieme delle 5-parti di $S$ e quella dell'insieme delle 5-parti di $T$. Anacleto partecipa ad un gioco: deve scegliere dieci numeri interi compresi tra 1 e 90; tra i novanta numeri ne verranno poi estratti 5 ed Anacleto vince se (e solo se) tutti e cinque i numeri estratti sono tra quelli che lui aveva scelto. Che probabilità ha Anacleto di vincere?
8. 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}}$.
9. Trovare quattro partizioni distinte dell'insieme $\set{1,2,3,4}$.
10. Trovare tre partizioni non banali dell'insieme $\Z$.

10/11

Discussione di esercizi dalla lezione precedente.

Per elementi di un monoide finito le proprietà di essere cancellabile e quella di essere simmetrizzabile sono equivalenti.

Proprietà di relazioni binarie: proprietà riflessiva, antiriflessiva, 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 (si vedano le note su partizioni ed equivalenze). Esempi di relazioni di equivalenza; tra queste le relazioni di equivalenza banali in un insieme (la relazione di uguaglianza e la relazione universale). Nucleo di equivalenza di un'applicazione (anche detto, nel libro di testo, equivalenza associata all'applicazione).

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

Esercizi proposti (dare priorità a 1, 4, 5, 7, 8, 10):

1. Svolgere gli esercizi 1, 2 e 3 da relazioni binarie, tralasciando le domande relativa alla proprietà di antisimmetria e quelle sugli ordinamenti, e tralasciando anche i punti f e g dell'esercizio 1.
2. 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})$.
3. Verificare in dettaglio quanto detto nella parte finale della lezione:
   • se $\alpha$ è la relazione di equivalenza definita in $\Z$ ponendo, per ogni $x$, $y\in\Z$, $x\mathrel\alpha y$ se e solo se $x+y$ è pari, allora $P:=[0]_\alpha$ è l'insieme dei numeri interi pari e $D:=[1]_\alpha$ è l'insieme dei numeri interi dispari; inoltre $\Z/\alpha=\set{P,D}$.
   • se $S$ è un insieme finito di cardinalità $n$ e $\tau$ è il nucleo di equivalenza dell'applicazione $x\in\P(S)\mapsto |x|\in\N$, allora $\P(S)/\tau=\set{\P_k(S)\mid n\ge k\in\N}$.
4. 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$?
5. Siano $v\colon n\in\Z\mapsto |n|\in\N$ e $w\colon n\in\Z\mapsto n^2\in\N$. Descriverne i nuclei di equivalenza e, rispetto a ciascuno di essi, la classe di $-5$.
6. Verificare che il nucleo di equivalenza di un'applicazione $f$ di dominio $A$ è la relazione di uguaglianza in $A$ se e solo se $f$ è iniettiva; è la relazione universale in $A$ se e solo se $f$ è costante.
7. 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|)^3+1=y^4+(\log |y|)^3+1$ è di equivalenza.
8. Siano $s=\set{1,2,3}$ e $\rho$ la relazione binaria definita in $\P(s)$ da: per ogni $x,y\in\P(s)$, $(x\mathrel\rho y\shiff x\cup\set 1=y\cup\set 1)$. Stabilire se $\rho$ è una relazione di equivalenza e, nel caso lo sia, descrivere $\P(s)/\rho$, elencando i suoi elementi e gli elementi di ciascuna delle classi rispetto a $\rho$. Quanto vale $|\P(s)/\rho|$?
9. Descrivere il nucleo di equivalenza dell'applicazione $f\colon n\in\Z\mapsto (-1)^n\in\Z$ e, rispetto ad esso, calcolare la classe di equivalenza di $13765$.
10. 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/11

Discussione di esercizi dalla lezione precedente.

Ulteriori osservazioni sulle classi di equivalenza: due diverse classi rispetto alla stessa relazione di equivalenza sono necessariamente disgiunte.

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. Ad esempio: descrizione delle relazioni di equivalenza su un insieme di cardinalità 3 (sono in tutto cinque). 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$.

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

Descrizione delle classi di equivalenza rispetto ad un nucleo di equivalenza. Teorema di omomorfismo per insiemi e conseguenze (tra cui la fattorizzazione di un'arbitraria applicazione come composta tra un'immersione, una biezione ed una proiezione. canonica). Anche il contenuto di questa lezione è in partizioni ed equivalenze.

Esercizi proposti:

1. Siano $a=\set{1,2,3,4}$ e $b=\set{1,2}$, e sia $\sim$ il nucleo di equivalenza di $f\colon x\in\P(a)\mapsto x\cup b\in\P(a)$. Determinare $|\P(a)/{\sim}|$ ed elencare gli elementi di $[a]_{\sim}$.
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. 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$.
5. 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}|$?
6. 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|$.
7. In questo sito è anche disponibile una vecchia nota sul teorema di omomorfismo per insiemi. Come detto per altri materiali del sito, essa è 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$.

15/11

Discussione di pochi esercizi dalla lezione precedente.

Anelli. Definizione ed esempi; anelli commutativi, anelli unitari. Sottoanelli, sottoanelli unitari; omomorfismi di anelli e di anelli unitari. Lo zero $0_R$ e (se esiste) l'unità $1_R$ di un anello. Terminologia per gli anelli: opposti (cioè simmetrici rispetto all'operazione additiva) e inversi (cioè eventuali simmetrici rispetto all'operazione moltiplicativa).

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$; la verifica di quest'ultima regola è stata lasciata per esercizio.

Discussione sulla legge di annullamento del prodotto con un esempio di anello 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. A titolo di notizia: gli anelli unitari finiti integri sono, tutti, campi. Per questi argomenti si vedano le note sulla cancellabilità.

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

1. Sia $R$ un anello unitario e sia $a\in R$. Verificare, per induzione, che per ogni $n\in\N$ si ha $(n1_R)a=na$; estendere poi il risultato ad ogni $n\in\Z$.
2. Provare che, per ogni insieme $a$, nell'anello delle parti ai $a$ ogni elemento diverso dall'unità $a$ è un divisore dello zero.
3. 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$.
4. Nell'anello prodotto diretto $\Z\times\Z$, definito come all'esercizio 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$.
5. Ancora con riferimento allo stesso anello $\Z\times\Z$ dell'esercizio precedente, verificare che $\set{0}\times \Z$ è un sottoanello di $\Z\times\Z$. Ne è un sottoanello unitario? Che tipo di anello è $\set{0}\times \Z$ (munito delle operazioni indotte da 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$?
6. Sia $R$ un anello unitario. È possibile che $1_R$ sia un divisore dello zero in $R$?
7. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?
8. Vero o falso: per ogni anello $R$ ed ogni $a$, $b\in R$, $(a+b)^2=a^2+2ab+b^2$.

17/11

Discussione di esercizi dalla lezione precedente.

Elementi idempotenti ed anelli booleani (si veda la prima sezione delle note sulle strutture booleane; non è essenziale la nozione di caratteristica); 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.

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

La relazione $|_S$ di divisibilità in un semigruppo commutativo $S$: è sempre transitiva, è riflessiva se $S$ è un monoide. Nei monoidi ogni elemento è diviso da ciascun elemento invertibile (quindi nei gruppi la relazione di divisibilità è la relazione universale). Divisibilità negli anelli commutativi (riferita ovviamente all'operazione moltiplicativa): se $(R,+,\cdot)$ è un anello commutativo, allora, in $R$, ogni elemento divide $0_R$, se inoltre $a,b,c\in 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$).

Relazioni (binarie) antisimmetriche. Relazioni d'ordine (largo) e relazioni d'ordine stretto. Esempi; tra gli altri: la relazione di divisibilità in $(\N,\cdot)$ è d'ordine, quella in $(\Z,\cdot)$ non lo è.

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$. 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 $\rho_{\ne}$ è descritta da: $(\forall x,y\in a)$$(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$; analogamente $\sigma_{=}$ è descritta da: $(\forall x,y\in a)$$(x\mathrel{\sigma_{=}}y \iff (x\mathrel\sigma y \lor x=y))$. Non sono state per il momento fornite dimostrazioni a questo riguardo (ma si consiglia di provare a trovarne, per esercizio).

Esercizi proposti:

1. 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)$.
2. Svolgere l'esercizio 4 dalle note sulle strutture booleane.
3. Descrivere, per un arbitrario insieme $a$, la relazione di divisibilità nel monoide $(\P(a),\cup)$ e quella nel monoide $(\P(a),\cap)$.
4. Completare gli esercizi 1 (esclusi i punti f e g) e 2 da relazioni binarie (dove 'ordinamento' sta per 'relazione di ordine o di ordine stretto').
5. 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.
6. 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?

19/11

Discussione di esercizi dalla lezione precedente.

Verifiche relative alle biezioni, per ogni insieme $a$, tra $\OL(a)$ e $\OS(a)$ presentate nella scorsa lezione.

Insiemi ordinati. Relazioni d'ordine (stretto o largo) indotte su parti.

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

Dualità per relazioni d'ordine ed insiemi ordinati. Confrontabilità ed insiemi totalmente ordinati.

Elementi minimi e minimali (e, dualmente, massimi e massimali). 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.

Esercizi proposti (dare priorità a 2, 3 e 7):

1. Sia $A$ un insieme. La relazione d'uguaglianza in $A$ è una reazione d'ordine? E la relazione universale in $A$?
2. Siano $A=\set{0,1,2,3}$ e $B=\set{1,2,3,4}$. 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.
4. Costruire un esempio di insieme ordinato con esattamente due elementi minimali.
5. Tornare agli ultimi due esercizi della lezione scorsa, in cui sono definite delle relazioni binarie $\rho$, $\sigma$ e $\tau$, e per ciascuna di esse che sia una relazione d'ordine, decidere se è totale e determinare gli eventuali elementi minimo, massimo, minimali e massimali del corrispondente insieme ordinato.
6. Esiste in $\P(\N)$ una parte infinita che sia totalmente ordinata per inclusione (cioè dall'ordinamento indotto dall'inclusione in $\P(\N)$)?
7. 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$.
8. Svolgere i punti da (i) a (v) dell'esercizio 6 dal compito del 16 gennaio 2019.

22/11

Discussione di esercizi dalla lezione precedente.

Solo a titolo di notizia: se un insieme ordinato finito ha un unico elemento minimale, questo ne è il minimo (ma, ricordiamo, questo non è necessariamente vero nel caso degli insiemi ordinati infiniti).

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

Date un'applicazione $f\colon A\to B$ ed una relazione d'ordine largo $\rho$ in $B$, relazione d'ordine definita in $A$ da $f$ e $\rho$ (quella rispetto alla quale, scelti comunque $x$ e $y$ in $A$, $x$ è in relazione con $y$ se e solo se $x=y$ oppure $f(x)\mathrel{\rho_{\ne}}f(y)$), descrizione dei suoi elementi minimali o massimali ed altre osservazioni.

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. Costruzione di diagrammi di Hasse.

Esercizi proposti:

1. Siano $a=\set{n\in\Z \mid \, |n|\lt 5}$ e $f$ l'applicazione $n\in a\mapsto |n|\in\N$. Sia poi $\rho$ la relazione binaria definita in $a$ ponendo, per ogni $x,y\in a$, $x\mathrel\rho y$ se e solo se $x=y$ oppure $f(x)\lt f(y)$. Spiegare perché $\rho$ è una relazione d'ordine e determinare gli elementi minimali e gli elementi massimali in $(a,\rho)$.
2. Siano $s=\set{n\in\N \mid n\lt4}$ e $\alpha$ la relazione binaria definita in $\P(s)$ ponendo, per ogni $x,y\in \P(s)$, $x\mathrel\alpha y$ se e solo se $x=y$ oppure $x\cap\set{0,1}\subset y\cap\set{0,1}$. Spiegare perché $\alpha$ è una relazione d'ordine e determinare gli elementi minimali e gli elementi massimali in $(\P(s),\alpha)$.
3. Stabilire quali elementi coprono 2 in $(\N,\le)$, $(\N,\mid\,)$, in $(\Q,\le)$.
4. Per ogni $n\in\set{2,3,6,8,9,10,12}$ disegnare il diagramma di Hasse dell'insieme dei divisori di $n$ in $(\N,\cdot)$, ordinato per divisibilità.
5. Siano $X=\set{1,2,5,9,900}$ e $Y=\set{\vuoto,\set 1,\set{2,3}, \set 4,\N}$, ordinati dalle relazioni indotte rispettivamente dalla divisibilità in $(\N,\cdot)$ e dall'inclusione in $\P(\N)$. Se ne disegnino i diagrammi di Hasse, si decida se sono reticoli e se, come insiemi ordinati, $X$ e $Y$ sono tra loro isomorfi.
6. Rappresentare con un diagramma di Hasse l'insieme $S=\set{1,2,3,4,5}$ ordinato per divisibilità (in $\N$, cioè dalla relazione indotta da quella di divisibilità in $\N$). Determinare (eventuali) minimo, massimo elementi minimali ed elementi massimali in $(S,\mid\,)$.
7. Svolgere l'esercizio 6 da relazioni binarie, fermandosi all'indicazione degli elementi massimali.
8. Disegnare il diagramma di Hasse dell'insieme ordinato $(\P(a),\tau)$, dove $a=\set{1,2,3}$ e, per ogni $x,y\in\P(a)$, $x\mathrel\tau y$ se e solo se $x=y$ oppure $|x|\lt|y|$.

24/11

Discussione di esercizi dalla lezione precedente.

Osservazione: due insiemi ordinati finiti sono isomorfi se e solo se si possono rappresentare con lo stesso diagramma di Hasse; un esempio di costruzione di isomorfismo.

Minoranti e (dualmente) maggioranti di una parte $T$ di un insieme ordinato $(S,\rho)$. Vari esempi; tra questi: in $(\N,|)$ i minoranti di una parte $X$ sono i divisori comuni degli elementi di $X$, i maggioranti i multipli comuni; 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$.

Estremo inferiore $\inf_{(S,\rho)}(X)=\max(\minor_{(S,\rho)}(X))$ ed estremo superiore $\sup_{(S,\rho)}(X)=\min(\maggior_{(S,\rho)}(X))$ di una parte $X$ di un insieme ordinato $(S,\rho)$. Ad esempio, se $T\sseq\P(S)$, allora $\sup_{(\P(S),\sseq)}(T)=\bigcup T$, mentre $\inf_{(\P(S),\sseq)}(T)=\bigcap T$ se $T\ne\vuoto$ e $\inf_{(\P(S),\sseq)}(\vuoto)=S$. Inoltre, per ogni $a\in T$, sono equivalenti: (1) $a=\min T$, (2) $a\in T\cap\minor_{(S,\rho)}(T)$, (3) $a\in T$ e $a=\inf_{(S,\rho)}(T)$ (vale ovviamente l'enunciato duale).

Reticoli; definizione ed esempi: sono reticoli tutti gli insiemi totalmente ordinati, $(\N,\mid)$ e, per ogni insieme $S$, $(\P(S),\subseteq)$. Quest ultimi due sono reticoli completi (quelli in cui ogni sottoinsieme ammette estremo inferiore e superiore). Osservazione: allo scopo di verificare che un insieme ordinato sia un reticolo basta verificare l'esistenza di estremi inferiore e superiore dei sottoinsiemi costituiti da due elementi non confrontabili tra loro.

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

Un elemento minimale (risp. massimale) in un reticolo è necessariamente minimo (risp. massimo).

Reticoli limitati; lo sono 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 $A, B\subseteq S$. Allora $\minor_{(S,\rho)} (A\cup B)= \minor_{(S,\rho)} (A)\cap \minor_{(S,\rho)} (B)$; se esiste $a=\inf_{(S,\rho)}(A)$ allora $\minor_{(S,\rho)} (A)=\minor_{(S,\rho)} (\set a)=\set{x\in S\mid x\mathrel\rho a}$. Dunque, se esistono $a=\inf_{(S,\rho)} (A)$ e $b=\inf_{(S,\rho)}(B)$ allora $\minor_{(S,\rho)} (A\cup B)= \minor_{(S,\rho)} (\set{a,b})$. Di conseguenza, se $(S,\rho)$ è un reticolo e $A$ e $B$ ammettono estremo inferiore, anche $A\cup B$ ammette estremo inferiore (valgono gli enunciati duali per maggioranti ed estremi superiori).

Esercizi proposti:

1. L'insieme ordinato descritto nell'esercizio 6 da relazioni binarie, è un reticolo? E quello descritto nell'ultimo esercizio della lezione scorsa?
2. Svolgere l'esercizio 3 dal compito del 12 novembre 2018, escluso il punto (vii).
3. Svolgere l'esercizio 5 dal compito dell'8 marzo 2019, fermandosi dopo aver stabilito, al punto (iv), se $(T,\rho)$ è un reticolo. Ampliare l'esercizio dimostrando che $\rho$ è una relazione d'ordine in $S$ e decidendo se $(S,\rho)$ è o non è un reticolo.
4. Svolgere l'esercizio 3 dal compito del primo ottobre 2019.

26/11

Discussione di esercizi dalla lezione precedente.

In un reticolo $(S,\rho)$, siano $A$ e $B$ due sottoinsiemi dotati di estremi inferiori, $a$ e $b$, allora $\inf\set{a,b}$ è anche $\inf (A\cup B)$; vale l'enunciato duale per gli estremi superiori. Di conseguenza, in $(S,\rho)$ ogni parte finita e non vuota di $S$ ha estremo inferiore ed estremo superiore (questo non è sempre vero per parti infinite).

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 vale la legge 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(S,\rho)$, è neutro rispetto a $\land$ se e solo se $a=\max(S,\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 agebriche definite dalle operazioni reticolari.

Sottoreticoli (cioè parti non vuote di un reticolo chiuse rispetto alle operazioni reticolari). Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

Complementi di elementi in reticoli limitati e reticoli complementati. Esempi. Due elementi tra loro confrontabili in un reticolo limitato sono uno complemento dell'altro se e solo se sono il minimo ed il massimo del reticolo; un insieme (limitato) totalmente ordinato è complementato se e solo se ha al massimo due elementi.

Esercizi proposti:

1. Mostrare che, in ogni reticolo, ogni intervallo chiuso non vuoto costituisce un sottoreticolo. Dedurne che, per ogni insieme $a$ ed ogni sua parte $b$, $\P(b)$ costituisce un sottoreticolo di $\P(a)$ e che, per ogni $n\in\N$, l'insieme dei naturali divisori di $n$ costituisce un sottoreticolo di $(\N,\mid\,)$ (è l'intervallo di estremi $1$ ed $n$).
2. Verificare in dettaglio che, come detto a lezione, per ogni insieme $a$, il reticolo $(\P(a),\subseteq)$ è complementato.
3. Disegnare il diagramma di Hasse di un reticolo in cui esiste un elemento con cinque complementi.
4. Stabilire per quali interi $n$ nell'insieme $\set{2,14,18,27,30}$ il reticolo dei naturali divisori di $n$ (sottoreticolo di $(\N,\mid\,))$ è complementato.
5. $2$ ha un complemento in $(\N,\mid\,)$?

29/11

Discussione un esercizio dalla lezione precedente. In ogni reticolo, gli intervalli chiusi non vuoti sono sottoreticoli. Ad esempio, per ogni $n\in\N$ l'insieme dei divisori di $n$ costituisce un sottoreticolo di $(\N,\mid\,)$.

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. Isomorfismi tra algebre di Boole (sono precisamente gli isomorfismi reticolari); 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).

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; coincidenza delle corrispondenti nozioni di isomorfismo. Teorema di Stone per reticoli booleani e per algebre di Boole, con corollari come per gli anelli booleani.

Questi argomenti sono anche presentati nelle note sulle strutture booleane.

Esercizi proposti:

1. Riguardare gli esercizi proposti nelle ultimi lezioni, stabilendo, per ciascuno dei reticoli che vi appaiono, se sono complementati, distributivi, booleani.
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. Completare l'esercizio 5 dal compito dell'8 marzo 2019, già segnalato (in forma ampliata) alla lezione del 24 novembre.

1/12

Discussione di esercizi dalla lezione precedente.

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. Le proprietà relativa 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. Prima parte del teorema fondamentale dell'aritmetica per numeri interi maggiori di $1$ (: sono prodotti di primi). Per dimostrarlo abbiamo introdotto le nozioni che seguono.

Proprietà di buon ordinamento di $(\N,\le)$; dimostrazioni "per controesempio minimo". Esempio: dimostrazione del risultato appena enunciato sulle fattorizzazioni di interi in prodotti di primi. Giustificazione del principio di induzione (prima forma). Seconda forma del principio di induzione (o principio di induzione completa).

Fattorizzazioni "essenzialmente uguali" (ed "essenzialmente uniche") in monoidi commutativi. Monoidi fattoriali (cioè: monoidi cancellativi (ovvero: ad elementi tutti cancellabili) in cui ogni elemento non invertibili è prodotto di irriducibili e lo è in modo essenzialmente unico). Teorema fondamentale dell'aritmetica nella forma: $(\N,\cdot)$ è un monoide fattoriale ed in forma esplicita. La parte relativa all'essenziale unicità delle fattorizzazioni in primi non è stata dimostrata.

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?

3/12

Discussione di esercizi dalla lezione precedente.

Anelli fattoriali (cioè domini di integrità unitari in cui gli elementi diversi dallo zero costituiscono, rispetto alla moltiplicazione, un monoide fattoriale); nuova versione del teorema fondamentale dell'aritmetica: l'anello degli interi è fattoriale.

Alcune 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. Rapido cenno all'estensione di questo risultato ad arbitrari monoidi fattoriali.

Nozione di massimo comun divisore (MCD) e di minimo comune multiplo (mcm) di parti in monoidi commutativi; se ne esistono, costituiscono classi di elementi associati. Loro esistenza e descrizione in monoidi. Se $d$ ed $m$ sono un MCD ed un mcm tra due elementi $a$ e $b$ di un monoide fattoriale, allora $ab$ è associato a $dm$.

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. Congruenza in una struttura algebrica e struttura quoziente.

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}}$. Le relazioni $\equiv_m$ sono effettivamente congruenze nell'anello $\Z$ degli interi (a titolo di notizia: non ne esistono altre). Notazione: per ogni $m\in\Z$, si scrive $\Z_m$ per $\Z/{\equiv_m}$.

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. In particolare: i quozienti $\Z_m$ si strutturano così come anelli commutativi unitari. Non sono sempre domini di integrità (si veda perché tra gli esercizi).

Avviso: Ricordo anche qui che il prossimo martedì 7 terremo, solo in remoto, una lezione di recupero, seguita, per chi è interessato, da una sessione di esercitazione e chiarimenti.

Esercizi proposti (dare priorità a 1, 3, 4, 7, 9, 11):

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? Inoltre, se $a$ e $b$ sono elementi di un monoide fattoriale $M$ e $b$ è invertibile, quali sono i MCD ed i mcm di $\set{a,b}$ in $M$?
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. In $(\Z,\cdot)$ trovare i MDC e i mcm dell'insieme dei numeri interi positivi pari.
6. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
7. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
8. 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?
9. 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$.
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 il precedente.
11. Provare che, per ogni $a,b,m,n\in\Z$, se $a\equiv_m b$ e $n$ divide $m$, allora $a\equiv_n b$.

6/12

Discussione di esercizi dalla lezione precedente. In particolare: due numeri congrui modulo un intero $m$ sono congrui anche modulo ciascun divisore di $m$.

Descrizione esplicita degli elementi $[a]_m:=[a]_{\equiv_m}$ 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|$. Per ogni $m\in\Z\setminus\set 0$, $\equiv_m$ è il nucleo di equivalenza dell'applicazione $a\in\Z\mapsto a\modbin m\in\N$.

Il teorema sulla divisione con resto (o divisione aritmetica) in $\Z$; nozione di quoziente e resto; notazione: $\rest(a,m):=a\mod m$.

Discussione sui metodi dell'aritmetica modulare, con esempi di calcoli rapidi; tra questi: alcuni criteri di divisibilità (per 2, 5, 10, 4, 8, etc; per 3, 9, 11). (Per i più curiosi, altri esempi sono in un articolo divulgativo, originariamente rivolto a studenti delle scuole superiori ma che può essere utile per supportare lo studio di tutti.)

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'osservazione per la sua velocizzazione.

Estensione dell'algoritmo euclideo; una forma iniziale del teorema di Bézout: 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$ a coefficienti in $\Z$. La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo.

Ricordo ancora una volta la lezione, esclusivamente in remoto, di domani, che inizierà alla 8:30 e sarà seguita da una sessione di discussione di esercizi o di spiegazioni a richiesta.

Esercizi proposti (dare priorità a 1, 4, 5, 8):

1. Elencare gli elementi di $[50]_6\cap\set{n\in\Z\mid -10\le n\le 10}$.
2. Elencare gli interi $m$ tali che $11\equiv_m -7$ e gli interi $h$ tali che $11+3h\equiv_h -7$.
3. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_4$. In questo anello $[2]_4$ è cancellabile?
4. Calcolare (a mente, ci mancherebbe!) $78598!\mod 6756$.
5. Calcolare $\rest(10,7)$, $\rest(10,-7)$, $\rest(-10,7)$, $\rest(-10,-7)$.
6. Determinare (eseguendo solo calcoli a mente) $674\mod 6$, poi $674\mod -6$ ed infine $n\mod 7$ dove $n=7005(2^{10}-140)$.
7. Calcolare (a mente) $\rest(72543618991175,9)$ e $\rest(72543618991175,3)$, e poi $\rest(626\cdot 3125,3)$.
8. 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$.
9. Svolgere gli esercizi da 5 ad 8 e 12 da Tautologie, insiemi, aritmetica.

7/12

Discussione di esercizi dalla lezione precedente.

Altre versioni, più complete, del teorema di Bézout: se $a,b\in\Z$ e $d$ è un MCD tra $a$ e $b$,

• l'insieme delle combinazioni lineari di $a$ e $b$ in $\Z$ coincide con $d\Z$;
• 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: siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$.

Equazioni della forma $ax=c$ in un anello commutativo unitario: discussione sui possibili insiemi di soluzioni nei casi in cui: $a$ è invertibile, $a$ è cancellabile, $a$ è un divisore dello zero. 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. Come conseguenza: per ogni intero positivo $m$, determinazione degli elementi invertibili di $\Z_m$. Verifica diretta del fatto (già noto) che tutti gli elementi non invertibili in $\Z_m$ sono divisori dello zero. Sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità; (3) $m$ è primo.

Metodi effettivi per la semplificazione e la risoluzione delle equazioni congruenziali (l'argomento non è stato esaurito, la discussione proseguirà nella prossima lezione). Se $a,b\in\Z$ e $m\in\N^*$, indicando con $(*)$ l'equazione congruenziale $ax\equiv_m c$, si ha:

• se $a'\in[a]_m$ e $c'\in[c]_m$, l'equazione congruenziale $a'x\equiv_m c'$ è equivalente a $(*)$ (nel senso che le due equazioni hanno lo stesso insieme di soluzioni);
• per ogni $a,c,k\in\Z$, se $k\ne 0$, l'equazione congruenziale $akx\equiv_{mk} ck$ è equivalente a $(*)$;

in particolare, se $d$ è un MCD tra $a$ ed $m$, e $d$ divide $c$, $(*)$ è equivalente a $a_1x\equiv_{m_1} c_1$, dove $a_1=a/d$, $c_1=c/d$ e $m_1=m/d$, quindi $a_1$ ed $m_1$ sono coprimi e da ciò segue che l'insieme delle soluzioni di $(*)$ è una classe di resto modulo $m_1$ (mentre, se $d$ non divide $c$, $(*)$ non ha soluzioni).

Esercizi proposti:

1. 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).
2. Svolgere gli esercizi 9 e 10 da Tautologie, insiemi, aritmetica (la scrittura $ax\equiv c\pmod m$ sta per $ax\equiv_m c$).
3. 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.
4. Svolgere l'esercizio 7 dal compito del 16 gennaio 2019 e calcolare, poi, l'insieme delle soluzioni dell'equazione congruenziale $16x+7\equiv_{144}2x+1$.
5. Di ciascuno degli elementi di $\Z_4$, $\Z_{6}$, $\Z_{11}$, $\Z_{12}$ dire se è o non è un elemento invertibile, un elemento cancellabile, un divisore dello zero. Degli elementi invertibili di $\Z_{12}$ trovare anche gli inversi.
6. Indicando, per ogni $n\in\Z$, con $\bar n$ la classe $[n]_{66}$, in $\Z_{66}$ dire quali tra $\bar 7$, $\bar 8$, $\overline {667}$, $\overline{1000}$ sono invertibili, e di questi determinare gli inversi.

10/12

Discussione di esercizi dalla lezione precedente.

Ancora sulla risoluzione di equazioni congruenziali $ax\equiv_m c$, dove $a,b\in\Z$ e $m\in\N^*$. Se $\ell$ è un intero coprimo con $m$ che divida $a$ e $c$, l'insieme delle soluzioni di una tale equazione non cambia se $a$ e $c$ vengono sostituiti, rispettivamente, da $a/\ell$ e $c/\ell$. Un algoritmo (non l'unico possibile) per l'individuazione delle soluzioni di $ax\equiv_m c$: (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'=a/d$, $m'=m/d$, $c'=c/d$, ottenendo l'equazione $a'x\equiv_{m'} c'$ equivalente a quella data; (2) $a'$ ed $m'$ sono coprimi, quindi $[a']_{m'}$ è invertibile; se ne determina l'inverso in questo modo: utilizzando l'algoritmo euclideo esteso si ottengono interi $u$ e $v$ tali che $1=a'u+m'v$, allora $[u]_{m'}$ è l'inverso di $[a']_{m'}$; (3) l'algoritmo ora termina fornendo $[uc']_{m'}$, 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 ed alla lezione precedente.

Vari esempi di risoluzione di equazioni congruenziali. Osservazione: dall'insieme delle soluzioni di un'equazione congruenziale $ax\equiv_b c$ si può dedurre l'insieme di tutte le soluzioni dell'equazione diofantea $ax+by=c$.

Elementi periodici e aperiodici 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\in\Z$ si ha $x^a=x^b\iff a\equiv_m b$. Qualche esempio. Permutazioni cicliche.

Per gli argomenti trattati nelle ultime due lezioni si possono consultare le note sull'Algoritmo euclideo ed un'altra nota disponibile nel sito docenti della Professoressa Celentani.

Avviso: confermo che, come detto in aula, terremo una riunione (in remoto, nel canale teams del corso) di esercitazioni il prossimo martedì 14, a partire dalle 8:30.

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

13/12

Discussione di esercizi dalla lezione precedente.

Osservazione: se un numero intero $n>1$ non è primo allora esiste un intero positivo $p$ che divide $n$ e tale che $p\le\sqrt n$ (il minimo primo naturale divisore di $n$ ha questa proprietà).

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. Traduzione di questa struttura come algebra di Boole e interpretazione delle corrispondenti operazioni anche in termini dei connettivi di disgiunzione e negazione. A questo proposito, si veda la parte finale delle note sulle strutture booleane.

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario (si vedano le relative note, dove, fare attenzione!, l'insieme di numeri interi positivi è 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 esempio: per ogni intero positivo $m$, l'omomorfismo da $\Z[x]$ a $\Z_m[x]$ che ad ogni polinomio $f\in\Z[x]$ associa "$f$ riguardato modulo $m$", appartenente a $\Z_m[x]$.

Ricordo ancora la riunione dedicata ad esercizi e chiarimenti, domani (14/12) a partire dalle 8:30, in remoto.

Esercizi proposti:

1. Se $p$ è un numero intero primo positivo, qual è il più piccolo numero naturale $n$ che non è primo ma non è divisibile per alcun primo (positivo) minore di $p$? Come (se) cambia la risposta se aggiungiamo la condizione $n>1$?
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: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.

15/12

Conseguenze della proprietà universale per anelli di polinomi: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata) di un assegnato anello commutativo unitario; omomorfismi di sostituzione.

Gradi di somma, differenza e prodotto tra due polinomi. D'ora in avanti, 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 non nulli. Se $A$ è un dominio di integrità si ha $\U(A[x])=\U(A)$. Un esempio che mostra come queste proprietà possa 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 $A[x]$ non è un campo.

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto, con un esempio. 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 (informazione: il teorema di Bézout non vale in $\Z[x]$).

Applicazione polinomiale definita da un polinomio. Radici di un polinomio. 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$. Se $K$ è un campo, un polinomio in $K[x]$ ha radici in $K$ se e solo se ha un divisore di grado uno in $K[x]$.

Esercizi proposti:

1. Verificare che in $\Z_4[x]$ si ha $\bar 1=(\bar 1+ \bar 2x)(\bar 1- \bar 2x)$, quindi $\bar 1+ \bar 2x$ è invertibile pur avedo grado 1 (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).
2. Sia $f$ il polinomio $\bar 7x^3-\bar 1\in\Z_{10}[x]$. Supposto assegnato (ma non noto) $g\in\Z_{10}[x]$, sapendo che $g$ ha grado 6 siamo in grado di stabilire che grado ha $fg$? Ripetere l'esercizio dopo aver sostituito $f$ con $\bar 6x^3-\bar 1\in\Z_{10}[x]$.
3. 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.
4. 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").

17/12

Discussione di esercizi dalla lezione precedente; in particolare: esempio di un polinomio invertibile non costante in $\Z_4[x]$.

Ogni radice di un polinomio è radice anche di ogni suo multiplo; polinomi tra loro associati hanno esattamente le stesse radici. Viceversa, se $A$ è un dominio di integrità e $f,g\in A[x]$, le radici di $fg$ in $A$ sono tutte e sole le radici di $f$ o di $g$.

Teorema di Ruffini generalizzato e sue conseguenze: se $A$ è dominio di integrità unitario si ha: (1) se $0_A\ne f\in A[x]$, allora $f$ ha al più $\nu(f)$ radici in $A$; (2) principio di identità dei polinomi: se, inoltre, $A$ è infinito due polinomi in $A[x]$ coincidono se e solo se definiscono la stessa applicazione polinomiale. 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.

Teorema (non dimostrato): se $A$ è un anello fattoriale, anche $A[x]$ è un anello fattoriale. Sono dunque fattoriali gli anelli di polinomi (ad una indeterminata) sui campi ed anche $\Z[x]$.

Questioni di fattorizzazione in anelli di polinomi. 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à.

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

Polinomi in $\Q[x]$. Ciascuno di essi è associato (in $\Q[x]$) ad un polinomio a coefficienti interi. 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.

Ricordo cha la prossima lezione, quella conclusiva del corso, si terrà lunedì 20, a partire dalle ore 8:30 ed esclusivamente in remoto.

Esercizi proposti:

1. Seguendo le indicazioni date a lezione, determinare in $\Z_2[x]$ tutti i polinomi di grado 2, 3 o 4 che siano irriducibili.
2. Se possibile, trovare un polinomio di coefficiente direttore 340 che sia associato in $\Q[x]$ a $3x^2-1$.
3. 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$.
4. 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]$.
5. 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]$.
6. 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]$.
7. Svolgere, almeno in parte, gli esercizi nr. 1, 2, 3 e 8 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo.
8. Trovare tutte le radici in $\Q$ del polinomio $2x^{10}+x^9-x^8+12x^2-3$.
9. Il polinomio $50x^{12}-6x^5+18x-24$ è irriducibile in $\Q[x]$? E $x^3-9$?
10. Scrivere $x^3-3x^2+4$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
11. 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$.
12. 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]$.
13. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
14. 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.

20/12

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

Isomorfismi tra grafi (o tra multigrafi); proprietà che questi conservano. Esempi di grafi isomorfi e non. 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.

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 di $G$ esiste al più un cammino in $G$ da $a$ a $b$. Corrispondente caratterizzazione degli alberi.

Rappresentazione radicale di un albero; foglie. In ogni albero finito con almeno due vertici esistono almeno due vertici di grado uno. Lemma: il sottografo ottenuto da un albero cancellandone un vertice di grado uno ed il lato esso incidente è ancora un albero. 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$.

Esercizi proposti:

1. Fornire (utilizzando i suggerimenti dati a lezione e ragionando per induzione sul numero dei lati) una seconda dimostrazione del fatto il doppio del numero dei lati di un multigrafo finito è la somma dei gradi dei suoi vertici.
2. Utilizzando rappresentazioni radicali degli alberi, verificare che la foreste finite sono grafi planari.
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, mostrato a lezione; 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.
8. (A proposito del teorema sui cammini euleriani). Un grafo finito può avere esattamente un vertice di grado dispari?