5/10

La prima parte delle lezione è stata dedicata ad informazioni generali sul corso di laurea in informatica, con l'intervento del coordinatore, prof. Adriano Peron, poi sul corso di algebra in particolare e sui servizi a disposizione degli studenti. Sono stati presentati contenuto e finalità del corso, modalità di svolgimento e materiali didattici.

Introduzione molto informale alle nozioni di linguaggio, formula, proposizione (o formula chiusa), sintassi e semantica.

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

Per il contenuto di questa lezione e delle prossime, si vedano Logica rudimentale, tavola dei connettivi binari, esempi di tautologie. Potrebbe essere utile avere queste note a portata di mano (o di occhio).

Avviso: gli studenti che hanno partecipato alla prima lezione come ospiti sono pregati, non appena riceveranno le necessarie credenziali unina, di iscriversi al team del corso (possibilmente utilizzandone il codice) e di comunicarmelo, in modo che io possa cancellare l'invito a loro rivolto. Questo mi permetterebbe di ripulire l'elenco degli iscritti al team da duplicati.

Esercizi proposti:

1. Quale connettivo proposizionale è nascosto nell'affermazione affermazione 'Gesualdo è un vecchio imbroglione'?

7/10

Connettivi proposizionali e loro espressione nel linguaggio naturale. Disgiunzione (inclusiva: OR, $\lor$), disgiunzione esclusiva ($\xor$), congiunzione negata ($\nand$). Il connettivo bicondizionale ('doppia implicazione', 'se e solo se', $\shiff$). Forme proposizionali. Tautologie, contraddizioni (e forme contingenti). Forme proposizionali logicamente equivalenti. Alcuni esempi di tautologie, tra cui il principio del terzo escluso, il principio di non contraddizione, le tautologie di commutatività per i connettivi $\land$, $\lor$, $\shiff$ e $\xor$; di iteratività (o idempotenza) per $\land$ e $\lor$; di associatività per $\land$ e $\lor$, di distributività di $\land$ rispetto a $\lor$ e di $\lor$ rispetto a $\land$. Negazioni: $\xor$ e negazione di $\shiff$; leggi di De Morgan.

Il connettivo di implicazione (o condizionale). Discussione della sua semantica, con esempi. Espressioni verbali di uso comune per la sua espressione. Due tautologie: implicazione come disgiunzione, negazione di una implicazione.

Esercizi proposti:

1. Scrivere tavole di verità per le forme proposizionali $p\land (\lnot q)$,  $p\Leftrightarrow p$,  $p\land(p\lor q)$,  $(p\land(p\lor q))\Leftrightarrow p$,  $p\lor(p\land q)$.
2. Da Logica rudimentale, svolgere gli esercizi B, C2, D, E1, E3.
3. Negare la frase 'Se non studi ti boccio'.

9/10

Discussione degli esercizi dalla lezione precedente. Altre tautologie sull'implicazione (doppia implicazione, contrapposizione, transitività) e discussioni su metodi e applicazioni.

Associatività del connettivo bicondizionale e del connettivo $\xor$. Altre tautologie su $\xor$, tra cui: distributvità di $\land$ rispetto a $\xor$.

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

Esercizi proposti:

1. Abbiamo provato la distributività di $\land$ rispetto a $\xor$. Decidere se anche $\lor$ è distributivo rispetto a $\xor$, vale a dire: se $\big(p\lor (q\xor r)\big)\iff \big((p\lor q)\xor (p\lor r)\big)$ è 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, E2, E5, E6, E8, F1, F4.
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.

12/10

Discussione di alcuni esercizi dalla lezione precedente.

Cenni alla logica dei predicati. Variabili, quantificatori universale ed esistenziale: sintassi essenziale ed interpretazione. Occorrenze libere o vincolate di variabili. Formule chiuse. Predicati. Sostituzioni di termini a variabili (vengono sostituite solo le occorrenze libere).

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))$. Negazione di formule universali e di formule esistenziali.

Il quantificatore $\exists!$.

Esercizi proposti:

1. Da Logica rudimentale, ritornare sull'osservazione G1 e svolgere gli esercizi H5 e H6.
2. Verificare che $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)\land x\ne y))$ esprime la negazione di $\exists!x(\phi(x))$. Andrebbe bene anche $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)))$?
3. Negare: Ogni mucca verde mangia cioccolata.
4. Negare: Ogni mese, se mi arriva la bolletta del gas la pago.
5. Negare: $\exists x (\forall y (\varphi(x,y)))\implica \forall x(\exists y (\psi(x,y)))$, dove $\varphi$ e $\psi$ sono formule.

14/10

Discussione di alcuni esercizi dalla lezione precedente.

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

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). Insieme vuoto e sua unicità. Inclusione tra insiemi (nozione di sottoinsieme o parte). Il singleton di un elemento. Comparazione tra inclusione ($\sseq$) e appartenenza: è importante distinguere bene tra queste due nozioni, così come tra un insieme $x$ ed il suo singleton $\set x$; ad esempio tra $\vuoto$ e $\set\vuoto$. 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. L'insieme $\P(x)$ delle parti di un insieme $x$.

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

Esercizi proposti:

1. Vero o falso?: $(\forall x\in\vuoto)(x\ne x)$.
2. Vero o falso?: $\set{2,3,1,2,3}=\set{1,3,2}$.
3. Assegnati in qualche modo gli oggetti $a,b,c$, si può dire quanti elementi ha l'insieme $\set{a,b,c}$ i cui elementi sono (tutti e soli) $a$, $b$ e $c$?
4. Svolgere gli esercizi H1 e H3 da Logica rudimentale.
5. Sia $x=\set{\set{\set{\set\vuoto}}}$. Quanti elementi ha $x$? Quante parti ha $x$?
6. 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}$.
7. Descrivere, elencandone gli elementi, $\P(\vuoto)$, $\P(\set 1)$, $\P(\set {1,1})$ e $\P(\set {1,2})$.

16/10

Discussione di molti esercizi dalla lezione precedente.

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

Comparazione tra i connettivi di equivalenza e implicazione da una parte, e le relazioni di uguaglianza e inclusione tra insiemi dall'altra. Operazioni insiemistiche (binarie) di unione ($\cup$), intersezione ($\cap$), differenza simmetrica ($\ds$) e comparazione tra queste ed i connettivi proposizionali di disgiunzione, congiunzione, disgiunzione esclusiva. Differenza tra insiemi. Uso di tautologie per provare formule insiemistiche (come primi esempi: regola della 'doppia inclusione', transitività dell'inclusione, commutatività ed associatività per $\cup$, $\cap$ e $\ds$.)

Esercizi proposti:

1. Descrivere, elencandone gli elementi, $\P(\set {1,2,3})$.
2. Supposto fissato un insieme $a$, calcolare: $a\cup\vuoto$, $a\cap\vuoto$, $a\ds\vuoto$, $a\cup a$, $a\cap a$, $a\ds a$.
3. Quali formule insiemistiche si possono dedurre dalle tautologie della idempotenza?
4. Siano $a=\set{n\mid n\in\N\land n\lt 8}$, $b=\set{n\mid n\in\Z\land n\ne 6}$ e $c=\set{1,2,3}$. Descrivere, elencandone gli elementi, $a\setminus b$ e $a\ds c$.

19/10

La lezione è cominciata in gran ritardo a causa di problemi tecnici. Discussione di alcuni esercizi dalla lezione precedente.

Altre formule insiemistiche dedotte da tautologie (tra cui: distributività di $\cap$ rispetto a $\cup$ ed a $\ds$, di $\cup$ rispetto a $\cap$; esplicitazione della differenza simmetrica; formule insiemistiche di De Morgan; formule legate alla doppia negazione).

Diagrammi di (Euler-)Venn. Diagrammi di Venn generici e loro uso per dimostrare formule insiemistiche. Diagrammi per coppie e per terne di insiemi.

Esercizi proposti:

1. Abbiamo dimostrato a lezione che, per ogni $a$ e $b$ la formula $a\sseq b$ è equivalente a $a\cap b=a$. Provare che essa è equivalente anche a ciascuna delle seguenti: (1) $a\cup b=b$; (2) $a\setminus b=\vuoto$; (3) $a\ds b=b\setminus a$.
2. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
3. Rappresentare, in un diagramma di Venn generico, i termini insiemistici $a\cup(b\ds c)$ e $(a\cup b)\ds(a\cup c)$. Decidere se la formula $\forall a,b,c \big(a\cup(b\ds c)=(a\cup b)\ds(a\cup c)\big)$ è vera o falsa. Ripetere l'esercizio per i termini insiemistici $a\setminus(b\setminus c)$ e $(a\setminus b)\setminus c$.
4. Rappresentare, sempre in un diagramma di Venn generico, $a\cap(b\cap c)$, $a\ds(b\ds c)$ e $a\cap(b\ds c)$ .
5. Decidere quali tra questi due diagrammi di Venn per quattro insiemi sono generici: primo e secondo.

21/10

Discussione approfondita di alcuni esercizi dalla lezione precedente.

Altri esempi di utilizzo di diagrammi di Venn, con ulteriori esercizi.

Operazioni di unione e intersezione unaria (l'intersezione unaria $\bigcap a$ è definita solo se $a\ne\vuoto$). Definizione e numerosi esempi. Riduzione di unione e intersezione binaria a unione e intersezione unaria: per ogni $a,b$ si ha $a\cup b=\bigcup\set{a,b}$ e $a\cap b=\bigcap\set{a,b}$.

Formule di De Morgan per unione e intersezione unarie: per ogni $S$ ed $A$, se $A\ne\vuoto$, $S\setminus \bigcup A=\bigcap_{a\in A}(S\setminus a)$ e $S\setminus \bigcap A=\bigcup_{a\in A}(S\setminus a)$. Formule di distributività generalizzata: per ogni $S$ ed $A$, $S\cap \bigcup A=\bigcup_{a\in A}(S\cap a)$ e, se $A\ne \vuoto$, $S\cup \bigcap A=\bigcap_{a\in A}(S\cup a)$.

Sintassi alternativa per la descrizione di un insieme, nella forma $\set{t(x,y,z,\dots)\mid \dots}$.

Esercizi proposti:

1. Facendo riferimento alla tautologia della contrapposizione, provare che per ogni insieme $s$ ed ogni $a,b\in \P(s)$ si ha $a\sseq b\iff s\setminus b\sseq s\setminus a$.
2. Calcolare $\bigcup \vuoto$, $\bigcup\set{\vuoto}$, $\bigcap\set{\vuoto}$, e poi $\bigcup\set{x}$ e $\bigcap\set{x}$ per un arbitrario insieme $x$.
3. Calcolare $\bigcup A$ e $\bigcap A$ in ciascuno dei seguenti casi: (1) $A=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $A$ è l'insieme delle parti infinite di $\N$; (3) $A=\set{x\subseteq\N\mid 13\notin x}$; (4) $A=\set{x\subseteq\N\mid 13\in x}$; (5) $A=\big\{\set{124,n}\mid n\in\N\big\}$; (6) $A=\set{[n-1,n+1]\mid n\in\N}$, dove, si ricorda, per ogni coppia $a,b$ di numeri reali, $[a,b]=\set{x\in\R\mid a\le x\le b}$ è l'insieme dei numeri reali compresi tra $a$ e $b$.
4. Svolgere l'esercizio nr. 6 da questa raccolta ("per le vacanze di pasqua").

23/10

Discussione di alcuni esercizi dalla lezione precedente.

Coppie ordinate e loro proprietà caratteristica. Terne ordinata ed analoga proprietà caratteristica. Prodotto cartesiano tra due insiemi. 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. Diversi modi per rappresentare le corrispondenze (tramite diagrammi, tabelle, proprietà che caratterizza gli elementi del grafico). 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$. Alcuni esempi.

Applicazioni (o funzioni) tra due insiemi. Dominio e codominio di un'applicazione $f$; immagine $f(x)$ di un elemento $x$ del dominio di $f$. 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.

Esercizi proposti:

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. Siano $a$ e $b$ due insiemi. Si ha $a\times b=b\times a$ se e solo se …?
3. Siano $a$ e $b$ due insiemi. Si ha $a\times b=\vuoto$ se e solo se …?
4. Vero o falso? (1): $(\set{0}\times\N)\cup (\set{1}\times\N)=\set{0,1}\times\N$; (2): $(\N\times\N)\cup ((\Z\setminus \N)\times(\Z\setminus \N))=\Z\times\Z$.
5. 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?
6. 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\Z$;
   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)$.

26/10

Discussione approfondita di alcuni esercizi dalla lezione precedente, con ulteriori discussione sul problema della buona definizione di un'applicazione.

Associatività del prodotto relazionale tra corrispondenze, con esempi.

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.

Applicazioni costanti. Per ogni insieme $a$: l'applicazione identica $\id_a$; per ogni $b\sseq a$, l'immersione $x\in b\mapsto x\in a$ di $b$ in $a$. Restrizioni e prolungamenti di un'applicazione (se $f\colon a\to b$ è un'applicazione e $s\sseq a$, la restrizione di $f$ a $s$ è l'applicazione $f_{|s}\colon x\in s\mapsto f(x)\in b$, ottenibile anche componendo $f$ con l'immersione di $s$ in $a$; un prolungamento di $f$ è un'applicazione di cui $f$ sia una restrizione).

Esercizi proposti:

1. 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$.
2. 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$.
3. 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$.
4. 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$.
5. 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$.

28/10

Discussione approfondita (anche troppo) degli esercizi dalla lezione precedente.

Immagine $\im f:=\set{f(x)\mid x\in a}$ di un'applicazione $f$ di dominio $a$. Applicazioni suriettive. Un'applicazione $f\colon a\to b$ è suriettiva (cioè: $\im f=b$) se e solo se: per ogni $y\in b$ esiste $x\in a$ tale che $f(x)=y$. Negazione della suriettività. Diversi esempi ed esercizi, con discussione su possibili errori e preghiera di non duplicarli. Ridotte di un'applicazione; la ridotta di un'applicazione alla sua immagine è sempre suriettiva.

Siano $f\colon a\to b$ e $g\colon b\to c$ applicazioni. Se $f$ e $g$ sono suriettive, allora $g\circ f$ è suriettiva; se $g\circ f$ è suriettiva allora $g$ è suriettiva.

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, ad esempio lo sono le immersioni. Esercizi ed esempi. Applicazioni biettive.

Siano $f\colon a\to b$ e $g\colon b\to c$ applicazioni. Se $f$ e $g$ sono iniettive (risp, biettive), allora $g\circ f$ è iniettiva (risp, biettiva); se $g\circ f$ è iniettiva allora $f$ è iniettiva. Un esempio in cui, con queste notazioni, $g\circ f$ è biettiva ma $g$ non è iniettiva e $f$ non è suriettiva.

Esercizi proposti:

1. Svolgere l'esercizio 7 di quelli per le vacanze di pasqua, decidendo anche quali delle applicazioni indicate sono e quali non sono iniettive. Descrivere le immagini delle applicazioni in (iii), (iv) e (xiii).
2. Svolgere l'esercizio 8 di quelli per le vacanze di pasqua, decidendo anche quali delle applicazioni prese in esame sono e quali non sono iniettive.
3. 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$.
4. Sia $f\colon a\to b$ un'applicazione. Per ogni $c\sseq a$ si pone $\vecf(c)=\set{f(x)\mid x\in c}$. Verificare che, per ogni tale $c$, $\vecf(c)$ coincide con $\im g$ se $g$ è la restrizione di $f$ a $c$. Verificare anche che l'applicazione $\vecf\colon c\in\P(a)\mapsto \vecf(c)\in\P(b)$ è ben definita, e che se $\vecf$ è suriettiva, allora $f$ è suriettiva, se $\vecf$ è iniettiva, allora $f$ è iniettiva.

30/10

Discussione approfondita di alcuni 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(X)=\set{f(x)\mid x\in X}$ per ogni $X\in\P(A)$ e $\avecf(Y)=\set{a\in A\mid f(a)\in Y}$ per ogni $Y\in\P(B)$. Diversi esempi. Si ha: $\vecf (\vuoto)=\avecf(\vuoto)=\vuoto$, $\vecf(A)=\im f$, $\,\avecf (B)=\avecf (\im f)=A$ e, per ogni $x\in A$, $\vecf(\set x)=\set{f(x)}$. Per ogni $y\in B$, descrizione di $\avecf(\set y)$. Caratterizzazioni di iniettività, suriettività e biettività in termini di questi ultimi insiemi.

Sezioni, retrazioni e inverse di un'applicazione. Un'applicazione $f\colon a\to b$ è suriettiva se e solo se ammette sezioni, è iniettiva se e solo se ammette retrazioni oppure $a=\vuoto$.

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: $a^f$ piuttosto che $f(a)$ come nel corso.

Esercizi proposti:

1. Sia $a=\set{-1,0,1,2}$ e sia $f$ l'applicazione $(x,y)\in a\times a\mapsto xy\in \Z$. Calcolare $\vecf(\set 0\times a)$ e $\avecf(\set{0,1,2})$. Scrivere tutte le sezioni e tutte le retrazioni di $f$.
2. Sia $f\colon x\in\P(\Z)\mapsto x\cup\N\in\P(\Z)$. Descrivere $\vecf(\P(\N))$ e $\avecf(\set\vuoto)$.
3. 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 $\vecf(\avecf (y))=y\cap\im f$ per ogni $y\in\P(b)$.
4. Scrivere tre diverse sezioni dell'applicazione $v\colon n\in\Z\mapsto |n|\in\N$. Scrivere tutte le sezioni dell'applicazione $w\colon n\in\Z\mapsto |n|\in\Z$.
5. Scrivere due diverse retrazioni dell'immersione di $\set{1,2}$ in $\set{1,2,3}$. Chissà se ce ne sono altre…

2/11

Discussione di esercizi dalla lezione precedente.

Ulteriori osservazioni su retrazioni e applicazioni iniettive.

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

(Notazione: si indica con $f^{-1}$ l'inversa dell'applicazione biettiva $f$.)

Per un'arbitraria applicazione $f\colon A\to B$ sono equivalenti: (1) $f$ ha una inversa; (2) $f$ ha una sezione ed una retrazione; (3) $f$ è biettiva; (4) $f$ ha una ed una sola sezione; (5) per ogni $b\in B$ esiste uno ed un solo $a\in A$ tale che $b=f(a)$.

Metodi per riconoscere che un'applicazione è biettiva e descrizione esplicita della sua inversa. Esempi ed esercizi.

Operazioni binarie (ovunque definite) in un insieme. Definizione ed esempi. Operazioni binarie commutative ed associative. Nozione di struttura algebrica; semigruppi.

Elementi neutri a sinistra e a destra; elementi neutri. Unicità dei neutri: se, in una assegnata struttura, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, inoltre $s$ è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura. Monoidi.

Esercizi proposti:

1. Tra le applicazioni $f\colon n\in\Z\mapsto 2n-1\in\Z$, $g\colon n\in\Z\mapsto 2n-1\in\Q$, $h\colon n\in\Q\mapsto 2n-1\in\Q$, $k\colon n\in\Z\mapsto 8-n\in\Z$ si dica quali sono biettive e 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.
2. Si trovi l'inversa dell'applicazione al punto (ii) dell'esercizio 7 di quelli per le vacanze di pasqua.
3. Si verifichi che l'applicazione $n\in\Z\mapsto\begin{cases}2n-1,&\text{se }n\gt0\\-2n,&\text{se }n\le0\end{cases}\in\N$ è biettiva.
4. Si verfichi che l'applicazione $n\in\N\mapsto \begin{cases}-n/2,&\text{se }n\text{ è pari}\\(n+1)/2,&\text{se }n\text{ è dispari}\end{cases}\in\Z$ è biettiva.
5. Per caso le due applicazioni agli esercizi precedenti sono l'una inversa dell'altra?
6. 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,*)$.
7. 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}$.

4/11

Discussione di molti esercizi dalla lezione precedente.

Parti chiuse (o 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à, mentre è possibile che non conservino elementi neutri. Sottosemigruppi, sottomonoidi. Diversi esempi.

Ulteriori esempi di monoidi; il monoide delle parole su un alfabeto.

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.

In una struttura con un'operazione binaria ed elemento neutro: simmetrici destri e sinistri; simmetrici.

Esercizi proposti:

1. Delle seguenti dodici parti di $\Z$: $\N$, $\Z\setminus \N$, $\vuoto$, $\set{x\in\Z \mid x > 8}$, $\set{x\in\Z \mid x> -8}$, $\set 0$, $\set 1$, $\set {0,1}$, $\set {-1}$, $\set {0,1,2}$, $\set {1,-1}$, l'insieme degli interi pari, l'insieme degli interi dispari dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione. Questo esercizio contiene un errore, quale?
2. L'insieme delle parti finite di $\N$ è chiuso in $(\P(\N),\cap)$, in $(\P(\N),\cup)$, in $(\P(\N),\ds)$? E quello delle parti infinite?
3. Nel monoide delle parole su un alfabeto che contenga la lettera y, dire se sono o non sono parti chiuse: 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 costuiscono parti chiuse nel monoide delle trasformazioni di $a$ e quali ne costituiscono sottomonoidi: 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. 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.
6. 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.
7. In ciascuno dei monoidi commutativi qui elencati, stabilire quali elementi hanno e quali non hanno simmetrici (descrivendo questi ultimi): $(\Z,+,0)$, $(\Q,\cdot,1)$, $(\Z,\cdot,1)$, per un insieme $a$: $(\P(a),\cup,\vuoto)$, $(\P(a),\cap,a)$, $(\P(a),\ds,\vuoto)$. Fare lo stesso per il monoide $(\Z,\alpha,-1)$, dove $\alpha$ è l'operazione definita nell'esercizio 7 della lezione scorsa.

6/11

Discussione degli esercizi dalla lezione precedente.

Gruppi e gruppi abeliani.

Ulteriori osservazioni ed esempi relativi alla nozione di simmetrico (ad esempio: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di sé stesso). Elementi simmetrizzabili (anche: simmetrizzabili a sinistra o a destra). Simmetrici destri e sinistri; simmetrici. 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".

Il gruppo degli invertibili (cioè degli elementi simmetrizzabili) $\U(S)$ di un monoide $S$. Formula per il calcolo del simmetrico di un prodotto in un monoide (in notazione moltiplicativa, per ogni $a,b\in \U(S)$ si ha $(ab)'=b'a'$ se gli apici indicano i simmetrici). Nel corso della discussione è stato fatto un cenno ai teoremi di associatività e di commutatività.

Esempi di gruppi degli invertibili in alcuni monoidi. Il gruppo simmetrico $\Sym(X)=\U(T(X))$ su un insieme $X$ (i suoi elementi sono le trasformazioni biettive di $X$ e si chiamano permutazioni di $X$).

Sottogruppi di un gruppo e loro caratterizzazione. Esempi. Tra questi: per ogni $n\in\Z$ l'insieme $m\Z:=\set{mk\mid k\in\Z}$ è un sottogruppo di $(\Z,+)$ (senza dimostrazione: tutti i sottogruppi di $(\Z,+)$ sono di questa forma).

Aggiunta: Alcune note scritte su tavoletta grafica durante la lezione sono disponibili nella sezione materiale didattico della mia area nella piattaforma web docenti. Hanno accesso a questo materiale gli studenti che si sono iscritti allle lezioni del corso (corso di Algebra codice U2353) nel sito web docenti.

Esercizi proposti:

1. $\Z$ costituisce un sottogruppo di $(\Q,+)$? $\P(\N)$ costituisce un sottogruppo di $(\P(\Z),\ds)$?
2. Sia $X=\set{1,2,3}$. Nel gruppo simmetrico $\Sym(X)$ si considerino le permutazioni $\alpha$ e $\beta$ definite ponendo $\alpha\colon 1\mapsto 2$, $2\mapsto 1$, $3\mapsto 3$ e $\beta\colon 1\mapsto 3$, $2\mapsto 2$, $3\mapsto 1$. Si verifichi che $\alpha\circ\beta$ è diverso da $\beta\circ\alpha$ e si concluda che $\Sym(X)$ è un gruppo non abeliano.
3. Sia $*$ l'operazione binaria definita in $X:=\Z\times\Z$ da: $(\forall\; a,b,c,d\in\Z) \big((a,b)*(c,d)=(ac,ad)\big)$. Decidere se $*$ è associativa, se è commutativa, se ammette elementi neutri a sinistra, se ne ammette a destra. Nel caso la richiesta abbia senso, determinare gli elementi simmetrizzabili in $(X,*)$, descrivendone i simmetrici. Che tipo di struttura (semigruppo, monoide, gruppo, commutativo o no?) è $(X,*)$?
4. Stesse domande come all'esercizio precedente, per le operazioni
   • $\varphi\colon(a,b)\in\Z\times\Z\mapsto a+b-1\in\Z$
   • $\psi\colon(a,b)\in\Z\times\Z\mapsto ab+1\in\Z$
   • $\mu\colon((a,b),(c,d))\in(\Z\times\Z)\times(\Z\times\Z) \mapsto (a+bc,bd)\in\Z\times\Z$
   • $\tau\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\cup Y)\cap\N\in\P(\Z)$
   • $\omega\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto(X\setminus Y)\cup\set 1\in\P(\Z)$
   al posto di $*$ (suggerimento per l'ultima operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).
5. Si verifichi che la strutture $(S,\kappa)$ implicitamente definita nell'esercizio 7 della lezione del 2 novembre è un gruppo non abeliano. Che nesso c'è tra questo gruppo e la struttura definita dall'operazione $\mu$ del gruppo precedente?

9/11

Discussione di esercizi dalla lezione precedente.

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). Le traslazioni definite da elementi simmetrizzabili sono biettive. Esempi. 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.

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

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,\mu)$, dove $\mu$ è l'operazione definita nell'esercizio 4 della lezione del 6 novembre.
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}$.
4. Scrivere le tavole di Cayley dei gruppi $(\P(\set 1),\ds)$ e $(\Sym(\set{1,2}),\circ)$; confrontarle con quella del gruppo $\U(\Z,\cdot)$ vista a lezione.
5. Scrivere le tavole di Cayley di $(\P(\set{1,2}),\cup)$ e di $(\P(\set{1,2}),\ds)$.
6. 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.

11/11

Discussione di esercizi dalla lezione precedente. In conseguenza di uno di essi, in un qualsiasi semigruppo, sia gli elementi cancellabili a sinistra che quelli cancellabili a destra costituiscono parti chiuse.

Omomorfismi tra strutture algebriche ad una operazione binaria. Alcuni esempi. Isomorfismi. L'inversa di ogni isomorfismo è un isomorfismo.

Gli omomorfismi suriettivi conservano: associatività, commutatività, elementi neutri (anche a destra o a sinistra), simmetrici (anche a destra o a sinistra). 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.

Esercizi proposti:

1. Sia $M$ il monoide delle parole su un fissato alfabeto non vuoto. Verificare che l'applicazione che ad ogni parola $w\in M$ associa la lunghezza di $w$ (in $\N$) è un omomorfismo (suriettivo) da $M$ a $(\N,+)$.
2. Siano $a$ un insieme e $b$ una sua parte. Decidere se l'applicazione $x\in\P(a)\mapsto x\cup b\in\P(a)$ è un omomorfismo da $(\P(a),\cap)$ a $(\P(a),\cap)$, da $(\P(a),\cap)$ a $(\P(a),\cup)$, da $(\P(a),\cup)$ a $(\P(a),\cup)$.
3. L'applicazione $n\in\Z\mapsto n^3\in\Q$ è un omomorfismo da $(\Z,+)$ a $(\Q,+)$? E da $(\Z,\cdot)$ a $(\Q,\cdot)$?
4. Siano $g\colon (A,*)\to (B,\bullet)$ e $f\colon (B,\bullet)\to (C,\lozenge)$ omomorfismi. Provare che $f\circ g$ è un omomorfismo da $(A,*)$ a $(C,\lozenge)$ e che se $f$ e $g$ sono isomorfismi anche $f\circ g$ lo è.
5. Sia $*$ un'operazione binaria nell'insieme $S$ e sia $T$ una parte chiusa (non vuota) in $(S,*)$. Verificare che l'immersione di $T$ in $S$ è un omomorfismo da $(T,*)$ a $(S,*)$.
6. Sia $G$ un gruppo abeliano. Verificare che l'applicazione $g\in G\mapsto g^{-1} \in G$, che ad ogni elemento $G$ associa l'inverso, è un isomorfismo da $G$ a $G$. Cambia qualcosa se $G$ non è abeliano?
7. Provare che l'applicazione $n\in\Z\mapsto n-1\in\Z$ è un isomorfismo da $(\Z,+)$ a $(\Z,\alpha)$, dove l'operazione $\alpha$ è quella definita nell'esercizio numero 7 della lezione del 2/11. Provare che l'applicazione $a\in\Q\mapsto a/2\in\Q$ è un isomorfismo da $(\Q,\cdot)$ a $(\Q,\varepsilon)$, dove l'operazione $\varepsilon$ è quella definita nello stesso esercizio.
8. Sia $S=\set{130}\times \Z$, e sia $*$ l'operazione binaria definita in $S$ ponendo, per ogni $(a,b),(c,d)\in S$, $(a,b)*(c,d)=(130,b+d)$. Dimostrare che $(S,*)$ è un gruppo abeliano, scrivendo direttamente un isomorfismo da $(S,*)$ a $(\Z,+)$.

13/11

Discussione di esercizi dalla lezione precedente.

Approfondimenti ed ulteriori esempi sulla nozione di isomorfismo. 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. Costruzione della tavola di Cayley dei gruppi di cardinalità due o tre, basate sul fatto che ciascuna delle righe e delle colonne della tavola di Cayley di un gruppo è sempre priva di ripetizioni.

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: per ogni elemento $x$ di un semigruppo e per ogni $n,m\in\Z$ per cui $x^n$ e $x^m$ siano definiti, $x^{n+m}=x^n x^m$ e $x^{nm}=(x^n)^m$ (è stata dimostrata solo la prima, e solo nel caso degli esponenti naturali). 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. Gruppi ciclici.

Esercizi proposti:

1. Dimostrare che il monoide delle parole su un alfabeto costituito da un solo carattere è isomorfo al monoide $(\N,+,0)$.
2. A lezione abbiamo verificato che se $X=\set{1,2,3,4}$ e $\sigma$ è la permutazione di $X$ definita da $\sigma\colon 1\mapsto 2\mapsto 3\mapsto 4\mapsto 1$, allora $S:=\set{\id_X,\sigma,\sigma^2,\sigma^3}$ è un sottogruppo di $\Sym(X)$. Costruire la tavola di Cayley di del gruppo $S$ (l'operazione è la composizione di applicazioni) e confrontarla con quella del gruppo $(\P(\set{1,2}),\ds)$. Questi due gruppi sono isomorfi?
3. 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$.

16/11

Discussione degli esercizi dalla lezione precedente.

Richiami sulle relazioni binarie. Proprietà riflessiva, antiriflessiva, simmetrica, antisimmetrica, transitiva; loro formulazioni equivalenti in termini di proprietà della relazione duale e del grafico; loro negazione; confronto tra alcune di esse. Diversi esempi.

Relazioni di equivalenza. Esempi di relazioni di equivalenza; tra queste le relazioni di equivalenza banali in un insieme (la relazione di uguaglianza e la relazione universale). Nucleo di equivalenza di un'applicazione (anche detto, nel libro di testo, equivalenza associata all'applicazione).

Quanto annotato su tavoletta grafica durante la lezione è disponibile nella sezione materiale didattico della mia area nella piattaforma web docenti; lo stesso varrà per i contenuti delle prossime lezioni che si terranno a distanza. Hanno accesso a questi materiali gli studenti che si sono iscritti allle lezioni del corso (corso di Algebra codice U2353) nel sito web docenti.

Importante: ricordo anche qui della lezione di recupero che terremo domani, 17 novembre, a partire dalle 8:30.

Esercizi proposti:

1. Esercizi 1 (esclusi i punti f e g) e 2 (esclusi i punti a e b) da relazioni binarie, tralasciando la nozione di ordinamento. Notazioni: $\N^\#=\N^*=\N^+=\N\setminus\set 0$; con $|X\cap Y|=3$ sin intende: $X\cap Y$ è un insieme costituito da esattamente tre elementi.

17/11

Discussione degli esercizi dalla lezione precedente. 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.

Classi di equivalenza. Alcuni esempi (classi di equivalenza rispetto alle equivalenze banali).

Proprietà fondamentali delle classi di equivalenza: fissata una relazione di equivalenza $\sim$ in un insieme $A$ per ogni $a,b\in A$ si ha:

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$;
• sono tra loro equivalenti: $a\sim b$, $b\sim a$, $ a\in[b]_\sim$, $b \in [a]_\sim$, $[a]_\sim\cap [b]_\sim\ne \vuoto$, $[a]_\sim=[b]_\sim$.

Descrizione delle classi di equivalenza del nucleo di equivalenza di un'applicazione $f$: per ogni elemento $x$ del dominio di $f$, questa classe è $\avecf(\set{f(x)})$. Il teorema fondamentale di omomorfismo per insiemi ed una sua conseguenza (ogni applicazione è la composta di un'applicazione iniettiva con una suriettiva). Qualche esempio.

Esercizi proposti:

1. Sia $\sim$ una relazione di equivalenza in un insieme $A$. Verificare che, per ogni $x\in A$, $[x]_{\sim}$ è l'unica classe di equivalenza modulo $\sim$ a cui $x$ appartenga.
2. 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.
3. 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})$.
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. Descrivere $\Z/\alpha$, elencando i suoi elementi e gli elementi di ciascuna delle classi modulo $\alpha$, dove $\alpha$ è la relazione di equivalenza descritta al punto a dell'esercizio 1 di relazioni binarie. Quanti elementi ha $\Z/\alpha$?
6. 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$.
7. 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$.

18/11

Discussione di alcuni esercizi dalla lezione precedente, con ulteriori proprietà delle classi di equivalenza.

Partizioni di un insieme. Definizione e prima caratterizzazione: $F$ è una partizione di un insieme $A$ se e solo se $\vuoto\notin F\subseteq \P(A)$ e $\forall x\in A(\exists! b\in F(x\in b))$. Esempi. Gli insiemi quoziente (definiti da relazioni di equivalenza) sono partizioni.

Teorema fondamentale su relazioni di equivalenza e partizioni: per ogni insieme $A$, l'applicazione $\sim\in\Eq(A)\mapsto A/{\sim}\in\Part(A)$ (dominio e codominio sono gli insiemi delle relazioni di equivalenza e delle partizioni di $A$) è biettiva.

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

Introduzione al calcolo combinatorio. Il principio di inclusione-esclusione, con verifica nel caso dell'unione tra due insiemi; presentazione del caso dell'unione di tre insiemi.

Esercizi proposti:

1. Svolgere l'esercizio 1 dal compito del 16 luglio 2013.
2. Determinare tutte le relazioni di equivalenza nell'insieme $\set{1,2}$.
3. 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$.
4. Sia $A=\set{0,1,2,3,4,5,6}$. Quante (e quali) sono 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. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=11$ e $|B|=8$.
   1. Se $|A\cap B|=2$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=15$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 6$, cosa possiamo dire su $|A\cup B|$?
6. Utilizzando diagrammi di Venn, come fatto a lezione nel caso della formula analoga per due insiemi, verificare la formula di inclusione-esclusione per tre insiemi finiti (per ogni $A,B,C$ che siano insiemi finiti, $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$).

20/11

Discussione di alcuni esercizi dalla lezione precedente, con ulteriore illustrazione del principio di inclusione-esclusione.

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

L'ultimo risultato non vale per insiemi infiniti: esempi. Cenni ad equipotenza e comparazione tra cardinalità per insiemi infiniti.

Esercizi proposti:

1. Siano dati tre insiemi $A$, $B$ e $C$ tali che $|A|=6$, $|B|=8$ e $|C|=2$. Quante sono le applicazioni da $A$ a $B$? Quante tra queste sono iniettive? Quante suriettive? quante costanti? Quante sono le applicazioni suriettive da $A$ a $C$?
2. Siano $A=\set{n\in\N\mid n \lt 10}$, e $B=\set{4,16,92}$, Quante sono le applicazioni $f$ da $A$ a $B$ tali che $\forall a\in A$$(f(a)\le 50)$? Quante sono le applicazioni $g$ da $B$ ad $A$ tali che $g(4)=g(92)\ne g(16)$?
3. Quante sono le parole di lunghezza 9 che si possono ottenere utilizzando un alfabeto di 12 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?

23/11

Discussione degli esercizi dalla lezione precedente.

Il numero delle parti di un insieme finito (per ogni insieme finito $S$, si ha $|\P(S)|=2^{|S|}$): dimostrazione per induzione.

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

Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$. Formula ricorsiva: per ogni $k,n\in \N$ tali che $k\le n$, $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$; il triangolo di Tartaglia-Pascal. 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.

Esercizi proposti:

1. Dato un insieme finito $S$ e posto $n=|S|$, determinare il nucleo di equivalenza dell'applicazione $X\in\P(S)\mapsto |X|\in\N$ ed il relativo insieme quoziente.
2. Posto $S=\set{1,2,3,4}$, scrivere esplicitamente i 16 elementi di $\P(S)$, raggruppandoli per cardinalità.
3. Dimostrare in dettaglio che, come detto al lezione, se $f\colon S\to T$ è un'applicazione biettiva, allora $\vecf\colon\P(S)\to\P(T)$ è anch'essa biettiva e la sua inversa è $\avecf$. Dedurne anche che, per ogni $k\in\N$, l'applicazione $x\in\P_k(S)\mapsto x\in\P_k(T)$ è biettiva (questa osservazione è importante per la corretta definizione dei coefficienti binomiali).
4. 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?
5. Calcolare $\binom 73$ utilizzando il triangolo di Tartaglia-Pascal.
6. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_7(S)$.
7. 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)$?
8. 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}$.
9. 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?

25/11

Discussione di alcuni esercizi dalla lezione precedente.

Anelli. Definizione ed esempi; anelli commutativi, anelli unitari. Sottoanelli, sottoanelli 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 delle ultime due regole è stata lasciata per esercizio.

Discussione sulla legge di annullamento del prodotto ed esempi di anelli in cui essa non vale. Divisori dello zero sinistri, destri, divisori dello zero negli anelli. I divisori sinistri (risp. destri) dello zero sono precisamente gli elementi non cancellabili a sinistra (risp. a destra), i divisori dello zero sono precisamente gli elementi non cancellabili. Anelli integri, domini di integrità. Esempi; tra questi l'anello prodotto diretto $\Z\times\Z$ (non integro). Per questi argomenti si vedano le note sulla cancellabilità.

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). I campi sono domini di integrità; il viceversa non vale: un controesempio è fornito dall'anello degli interi.

Esercizi proposti:

1. Dimostrare le regole di calcolo non provate a lezione: per ogni anello $R$ e per ogni $a,b,c\in R$ si ha $a(b-c)=ab-ac$ e $(b-c)a=ba-ca$; inoltre, se $R$ è unitario, per ogni $n\in\Z$ si ha $(n 1_R)a=na$. Per quest'ultima uguaglianza si suggerisce di dimostrare prima l'asserto per numeri naturali $n$ (procedendo per induzione) e poi estendere il risultato agli interi arbitrari.
2. Siano $(R,+,\cdot)$ e $(S,\oplus,\odot)$ due anelli. Nel prodotto cartesiano $C=R\times S$ definiamo due operazioni binarie (che continuiamo a indicare con $+$ e $\cdot$) ponendo, per ogni $a,b\in R$ e $u,v\in S$, $(a,u)+(b,v)=(a+b,u\oplus v)$ e $(a,u)\cdot(b,v)=(a\cdot b,u\odot v)$. Provare che $C$, munito di queste due operazioni, è un anello, che questo anello è commutativo se e solo se lo sono sia $R$ che $S$ ed è unitario se e solo se lo sono sia $R$ che $S$. Questo anello si chiama anello prodotto diretto di $R$ per $S$ e questo esercizio generalizza la costruzione, accennata a lezione, dell'anello prodotto diretto $\Z\times\Z$.
3. Nell'anello prodotto diretto $\Z\times\Z$, definito come all'esercizio precedente si decida quali tra questi elementi sono divisori dello zero e quali cancellabili: $(1,1)$, $(1,2)$, $(0,4)$. Fatto questo, provare a descrivere il gruppo degli elementi invertibili e l'insieme dei divisori dello zero in $\Z\times\Z$.
4. 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 ben conosciamo?
   Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
5. Provare che, se $S$ è un insieme non vuoto, l'anello delle parti di $S$ ha esattamente un elemento che non è divisore dello zero.
6. Sia $R$ un anello unitario. È possibile che $1_R$ sia un divisore dello zero in $R$?
7. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?
8. Provare che l'anello delle parti di un singleton è necessariamente un campo.

27/11

Discussione di alcuni esercizi dalla lezione precedente.

Teorema: nei monoidi commutativi finiti gli elementi cancellabili sono tutti e soli quelli invertibili; gli anelli (unitari) integri finiti sono corpi, i domini di integrità unitari finiti sono campi.

Applicazione dei coefficienti binomiali: formula di Newton per l'espansione delle potenze di un binomio, relativa alla somma tra due elementi che commutano tra loro in un anello unitario.

Anelli booleani; esempio: per ogni insieme $S$ l'anello delle parti di $S$ è booleano. Proprietà degli anelli booleani: sono commutativi e, in essi, ogni elemento coincide col suo opposto (cioè: $2a=0_R$ per ogni elemento $a$ di un anello booleano).

Per una parte $T$ di un insieme $S$, funzione caratteristica $\chi_{T,S}\colon S\to \set{0,1}$ di $T$ in $S$. Teorema: l'applicazione da $\P(S)$ a $\set{0,1}^S$ che a ciascuna parte $T$ di $S$ associa $\chi_{T,S}$ è biettiva. Si ritrova così il fatto che per ogni insieme (finito) $S$ si ha $|\P(S)|=2^{|S|}$.

Relazioni d'ordine (largo o stretto). Tre esempi importanti: la relazione d'ordine usuale ($\le$) in $\R$ o in suoi sottoinsiemi, la relazione di inclusione nell'insieme delle parti di un insieme, la relazione di divisibilità in $(\N,\cdot)$. In generale: la relazione di divisibilità in un semigruppo commutativo: è sempre transitiva, è riflessiva nel caso dei monoidi, ma anche in questo caso può non essere d'ordine (ad esempio, non lo è in $(\Z,\cdot)$).

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)$ tra gli insiemi $\OL(A)$ e $\OS(A)$ delle relazioni di ordine largo e di ordine stretto in $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 fornite dimostrazioni a questo riguardo (si vedano magari gli esercizi).

Insiemi ordinati. Principio di dualità per insiemi ordinati. Minimi e massimi in insiemi ordinati.

Esercizi proposti:

1. Dimostrare che gli anelli booleani con più di due elementi non sono domini di integrità. (Suggerimento: gli elementi idempotenti possono essere cancellabili?)
2. Sia $S$ un insieme di cardinalità 6. Le funzioni caratteristiche delle 3-parti di $S$ sono tutte e sole le applicazioni da $S$ a $\set{0,1}$ tali che …? Quante sono?
3. Scrivere la funzione caratteristica di $\N$ in $\Z$. Di quale parte di $\N$ l'applicazione $n\in\N\mapsto ((-1)^n+1)/2\in\set{0,1}$ è la funzione caratteristica?
4. Determinare, se esistono, minimi e massimi negli insiemi ordinati $(\Z,\le)$, $(\N,\le)$, $(\N,\mid\,)$, $(\P(\Z),\sseq)$.
5. Sia $A$ un insieme. La relazione d'uguaglianza in $A$ è una reazione d'ordine? E la relazione universale in $A$?
6. Per un arbitrario insieme $A$ e con riferimento alle applicazioni biettive $\OL(A)\to\OS(A)$ e $\OS(A)\to\OL(A)$ descritte nel resoconto della lezione, verificare:
   • che sono ben definite (cioè che, per ogni $\sigma\in\OS(A)$ e $\rho\in\OL(A)$, si ha $\sigma_=\in\OL(A)$ e $\rho_{\ne}\in\OS(A)$);
   • che sono l'una inversa dell'altra.
7. Siano $S=\set{1,2,3,4,5}$ e $f\colon x\in\P(S)\mapsto |x|\in\N$; siano poi $\rho$ e $\tau$ le relazioni binarie in $\P(S)$ definite da: per ogni $x,y\in\P(S)$, $x\mathrel\rho y\iff f(x)\le f(y)$ e $x\mathrel\tau y\iff (x=y \lor f(x)\lt f(y))$. Di ciascuna delle due stabilire se è o non è una relazione d'ordine (largo) e, nel caso lo sia, determinare nel corrispondente insieme ordinato gli eventuali elementi minimo e massimo.

30/11

Discussione di alcuni esercizi dalla lezione precedente.

Relazioni d'ordine indotte su parti, sottoinsiemi ordinati. Applicazioni crescenti ed isomorfismi tra insiemi ordinati. Esempio di un'applicazione biettiva crescente che non è un isomorfismo: l'applicazione identica da $(\N^*,|\,)$ a $(\N^*,\le)$.

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

Elementi massimali ed elementi minimali (sono nozioni duali tra loro). Se un insieme ordinato $(S,\rho)$ ha un minimo $a$, allora $a$ è l'unico minimo e l'unico minimale in $(S,\rho)$. Risultato duale per gli elementi massimali. Comparazione tra la nozione di minimo e quella di elemento minimale; In ogni insieme ordinato finito (non vuoto) esistono sia elementi minimali che elementi massimali.

Senza dimostrazione: se un insieme ordinato finito ha un unico elemento minimale (risp. massimale), questo è necessariamente minimo (risp. massimo) nell'insieme. Per insiemi infiniti, lo stesso risultato è generalmente falso: abbiamo costruito un insieme ordinato un cui esiste un unico elemento minimale (che è anche l'unico elemento massimale) che però non è minimo (né massimo) nell'insieme.

Date un'applicazione $f\colon A\to B$ ed una relazione d'ordine largo $\sigma$ in $B$, relazione d'ordine definita in $A$ da $f$ e $\sigma$ e descrizione dei suoi elementi minimali o massimali ed altre osservazioni.

Importante: ricordo che si terrà domani, 1 dicembre, una lezione di recupero a partire dalle 8:30.

Esercizi proposti:

1. Esiste in $\P(\N)$ una parte infinita che sia totalmente ordinata per inclusione (cioè dall'ordinamento indotto dall'inclusione in $\P(\N)$)?
2. Trovare gli elementi minimali e qualli massimali in ciascuno degli insiemi $A:=\set{n\in\N\mid n\le 10}$ e $B=A\setminus\set{1}$ ordinati dalla relazione indotta da quella di divisibilità in $(\N,\cdot\,)$.
3. 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$.
4. Svolgere i punti da (i) a (v) dell'esercizio 6 dal compito del 16 gennaio 2019.

1/12

Discussione degli esercizi dalla lezione precedente.

Intervalli 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. Due insiemi ordinati finiti sono isomorfi se e solo se si possono rappresentare con lo stesso diagramma di Hasse.

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 gli insiemi dei divisori comuni degli elementi di $X$; 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$.

Reticoli; definizione ed esempi: sono reticoli tutti gli insiemi ordinati, $(\N,\mid)$ e, per ogni insieme $S$, $(\P(S),\subseteq)$.

Esercizi proposti:

1. Stabilire quali elementi coprono 2 in $(\N,\le)$, $(\N,\mid\,)$, in $(\Q,\le)$.
2. Siano $(S,\rho)$ un insieme ordinato e $a\in S$. Verificare in dettaglio che $a=\inf_{(S,\rho)}(\set a)$.
3. Siano $(S,\rho)$ un insieme ordinato, $a\in S$ e $T\sseq S$. Spiegare perché sono equivalenti le affermazioni: (1) $a=\min(T,\rho)$; (2) $a\in T\cap\minor_{(S,\rho)}(T)$; (3) $a=\inf_{(S,\rho)}(T)\in T$ (questo esercizio generalizza il precedente).
4. Verificare che $(\Z,\le)$ è un reticolo, ma non tutte le sue parti non vuote ammettono in esso estremo inferiore ed estremo superiore.
5. 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\,)$. $(S,\mid\,)$ è un reticolo?
6. Posto $A=\set{-3,-2,-1,0,1,2}$, sia $\rho$ la relazione binaria in $A$ definita da: per ogni $a,b\in A$, $a\mathrel\rho b\iff$$(a=b\lor a^2\lt b^2)$. Decidere se $\rho$ è una relazione d'ordine; se lo è rappresentare $(A,\rho)$ con un diagramma di Hasse, determinarne (eventuali) minimo, massimo elementi minimali ed elementi massimali e stabilire se $(A,\rho)$ è un reticolo.

2/12

Discussione di alcuni degli esercizi dalla lezione precedente. 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. Ulteriori esempi.

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

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, ogni parte finita e non vuota di un reticolo ha, nel reticolo stesso, estremo inferiore ed estremo superiore (questo non è sempre vero per parti infinite).

Le due operazioni (binarie) reticolari (meet/inf/intersezione reticolare/$\land$ e join/sup/unione reticolare/$\lor$) 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. Teorema: se $(L,\land,\lor)$ è una struttura algebrica in cui $\land$ e $\lor$ 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 $\land$ e $\lor$ 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$.)

Esercizi proposti:

1. Siano $X=\set{1,2,3,5,30000}$ e $Y=\set{\vuoto,\set 1, \set 4,\set{2,8,9},\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.
2. Svolgere l'esercizio 6 da relazioni binarie, fermandosi alla prima occorrenza della parola 'reticolo' al penultimo rigo.
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/12

Discussione di alcuni degli esercizi dalla lezione precedente.

A completamento di quanto dimostrato nella parte finale della lezione precedente, equivalenza tra le nozioni di reticolo come insieme ordinato e di reticolo come struttura algebrica, discussa come segue. Assegnato un insieme non vuoto $S$, siano $A$ l'insieme delle relazioni d'ordine $\rho$ in $S$ tali che $(S,\rho)$ sia un reticolo e $B$ l'insieme delle coppie ordinate di operazioni binarie in $S$ che soddisfino le proprietà associativa, commutativa e le leggi di assorbimento. Allora l'applicazione da $A$ a $B$ che a ogni $\rho\in A$ associa la coppia $(\land,\lor)$ di operazioni reticolari definite da $\rho$ è biettiva. Esempio particolarmente significativo: per ogni insieme $X$, le operazioni reticolari corrispondenti alla relazione di inclusione in $\P(X)$ sono quelle di intersezione e di unione.

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. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo. Esempi di sottoreticoli; sono sottoreticoli gli intervalli chiusi (non vuoti) nei reticoli. Ad esempio, per ogni $n\in\N$ l'insieme dei divisori di $n$ costituisce un sottoreticolo di $(\N,\mid\,)$.

Se $(S,\rho)$ è un reticolo e $\land$ (estremo inferiore) e $\lor$ (estremo superiore) sono le due operazioni reticolari definite in esso, allora un elemento $a$ di $S$ è neutro rispetto a $\land$ se e solo se $a=\max(S,\rho)$, è neutro rispetto a $\lor$ se e solo se $a=\min(S,\rho)$.

Reticoli limitati. Lo sono i reticoli finiti non vuoti (fornite due dimostrazioni di questo fatto). Reticoli completi; lo sono $(\N,\mid\,)$ e, per ogni insieme $S$, $(\P(S),\sseq)$; i reticoli completi sono ovviamente limitati.

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.

Reticoli distributivi. Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), gli insiemi totalmente ordinati. Ciascuna delle due leggi distributive in un reticolo implica l'altra (senza dimostrazione). I sottoreticoli dei reticoli distributivi sono distributivi. Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff.

Alcuni argomenti trattati nelle ultime lezioni sono presentati, tra altre cose, nelle note sulle strutture booleane disponibili in questo sito.

Ancora sulla divisibilità in semigruppi commutativi. Elementi tra loro associati (cioè che si dividono a vicenda). La relazione "essere elementi associati" è di equivalenza.

Esercizi proposti:

1. Sia $(L,\rho)$ un reticolo e siano $\land$ (estremo inferiore) e $\lor$ (estremo superiore) le due operazioni reticolari definite in esso. L'applicazione biettiva menzionata nella prima parte della lezione fa dunque corrispondere la coppia $(\land,\lor)$ a $\rho$. Quale relazione d'ordine in $S$ ha per corrispondente la coppia $(\lor,\land)$?
2. Verificare che nessun numero intero positivo, tranne 1, ha complemento nel reticolo $(\N,\mid\,)$.
3. Per ogni $n$ in $\set{6,7,8,9,10}$, stabilire se l'insieme dei numeri naturali divisori di $n$, ordinato per divisibilità in $\N$, è un reticolo complementato.
4. 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.
5. Completare l'esercizio 5 dal compito dell'8 marzo 2019, già segnalato per la lezione scorsa.
6. Provare che se $S$ è un monoide commutativo, $a\in S$ e $u\in \U(S)$, allora $au$ è associato ad $a$ in $S$.

7/12

Discussione di alcuni degli esercizi dalla lezione precedente.

In un monoide commutativo, gli elementi associati ad un fissato elemento cancellabile sono tutti e soli i multipli di questo con un elemento invertibile. In un semigruppo commutativo: la condizione di divisibilità è invariante rispetto al passaggio ad elementi associati; due qualsiasi elementi sono associati se e solo se hanno lo stesso insieme di divisori, ovvero: se e solo se hanno lo stesso insieme di multipli.

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

Divisori banali di un elemento in un monoide commutativo. Elementi irriducibili; numeri primi. Monoidi (commutativi) cancellativi, fattorizzazioni "essenzialmente uguali" e monoidi fattoriali, anelli fattoriali. Teorema fondamentale dell'aritmetica (i monoidi $(\N^*,\cdot)$ e $(\Z\setminus\set0,\cdot)$ sono fattoriali; $(\Z,+,\cdot)$ è un anello fattoriale).

Proprietà di buon ordinamento di $(\N,\le)$; dimostrazioni "per controesempio minimo"; giustificazione del principio di induzione (prima forma). Seconda forma del principio di induzione (o principio di induzione completa); la dimostrazione è da completare.

Esercizi proposti:

1. Quali sono gli elementi irriducibili nel monoide $(\N,+,0)$? $(\N,+,0)$ è un monoide fattoriale?
2. Assegnato un insieme finito $S$, quali sono gli elementi irriducibili in $(\P(S),\cup,\vuoto)$? $(\P(S),\cup)$ è un monoide fattoriale?
3. Dimostrare, per induzione, che per ogni intero positivo $n$ si ha $\sum_{i=1}^n (2i-1)=n^2$.

9/12

Discussione degli esercizi dalla lezione precedente.

Principio di induzione nella seconda forma: dimostrazione e qualche commento.

Dimostrazione parziale del teorema fondamentale dell'aritmetica: ogni intero maggiore di 1 è un prodotto di numeri primi (non abbiamo dimostrato l'essenziale unicità della fattorizazione).

Descrizione dei divisori di un fissato elemento non invertibile di un monoide fattoriale, in termini di una fattorizzazione in prodotto di irriducibili. I divisori in $\N$ di un numero intero positivo ed il loro numero. Esistenza a descrizione di MCD e mcm in monoidi fattoriali. Se $d$ ed $m$ sono un MCD ed un mcm di due elementi $a$ e $b$ di un monoide fattoriale, allora $ab$ è associato a $dm$.

In un anello commutativo, un elemento che divida due elementi ne divide tutte le combinazioni lineari.

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}}$. Notazioni: per ogni $a,m\in\Z$, $\Z_m:=\Z/{\equiv_m}$ e $[a]_m:=[a]_{\equiv_m}$. Descrizione esplicita delle classi di equivalenza: per ogni $m,a\in \Z$ si ha $[a]_m=a+m\Z:=\set{a+mk\mid k\in \Z}$. L'operazione parziale mod (per ogni $a,m\in\Z$, se $m\ne0$, $a\modbin m$ è, per definizione, il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$). 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|$.

Il teorema sulla divisione con resto (o divisione aritmetica) in $\Z$.

Introduzione ad un problema: date un'operazione binaria ed una relazione di equivalenza $\sim$ in un insieme $S$, come usare la prima per definire un'operazione binaria $S/{\sim}$: non sempre lo si può fare nel modo che sembra più naturale; un esempio a questo riguardo.

Esercizi proposti:

1. Provare che ogni numero intero diverso da 0, 1 e -1 è prodotto di numeri 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 e i mcm di $\set{a,b}$ in $M$?
3. Quali e quanti sono i divisori in $\Z$ di $60$?
4. Vero o falso: $\Z_5=\set{[7]_5,[-2]_5,[20]_5,[6]_5,[-6]_5}$.
5. Vero o falso: $\Z_3=\set{[7]_3,[-2]_3,[20]_3,[6]_3,[-6]_3}$.
6. Vero o falso: $\Z_9=\set{[7]_9,[-2]_9,[20]_9,[6]_9,[-6]_9}$.
7. Elencare gli elementi di $[20]_7\cap\set{n\in\Z\mid -15\le n\le 15}$.
8. Provare che, per ogni $a,b,m,n\in\Z$, se $a\equiv_m b$ e $n$ divide $m$, allora $a\equiv_n b$.
9. Elencare gli interi $m$ tali che $12\equiv_m -6$ e gli interi $h$ tali che $12+5h\equiv_h -6$.
10. Calcolare $16\modbin 7$, $16\modbin -7$, $(-16)\modbin 7$, $(-16)\modbin -7$.
11. Calcolare (a mente) $76756464!\modbin 92747$.

11/12

Discussione degli esercizi dalla lezione precedente.

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

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 sono effettivamente congruenze nell'anello degli interi. Gli anelli quoziente di $\Z$. Esempio: $\Z_6$ non è un dominio di integrità.

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

Estensione dell'algoritmo euclideo e teorema di Bézout, nella forma: se $a,b\in\Z$ e $d$ è un massimo comun divisore tra $a$ e $b$, allora $d$ è una combinazione lineare di $a$ e $b$ a coefficienti in $\Z$. La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo. Equazioni diofantee (di primo grado in due incognite). Versioni alternative 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 appena descritto) ha soluzioni, ne ha infinite.

Equazioni di primo grado in un quoziente di $\Z$; equazioni congruenziali di primo grado ad una incognita: per interi $a$, $c$ ed $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 del tipo considerato. Come conseguenza: determinazione degli elementi invertibili nei quozienti di $\Z$.

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

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

Esercizi proposti:

1. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
2. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cup$ o $\ds$?
3. 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?
4. 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$.
5. 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 l'esercizio precedente ed anche l'esempio, menzionato a lezione, della relazione "avere la stessa lunghezza" nel monoide delle parole.
6. Indicando, per ogni $n\in\Z$, con $\bar n$ la classe $[n]_{44}$, in $\Z_{44}$ dire quali tra $\bar 7$, $\bar 8$, $\overline {447}$, $\overline{1000}$ sono invertibili.
7. Elencare gli elementi invertibili di $\Z_{8}$ e quelli di $\Z_{12}$.
8. Usare l'algoritmo euclideo per trovare un massimo comun divisore tra $209$ e $76$.
9. Trovare due soluzioni di ciascuna delle seguenti equazioni congruenziali, o spiegare perché non ce ne sono: $44x+18y=23$, $42x+18y=12$.
10. Nel granducato di Strampalia non circolano monete e la valuta locale, il tallero strampalese, viene emesso solo in due tagli: la banconota da 18 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).

14/12

Discussione di esercizi dalla lezione precedente.

Struttura degli anelli quoziente di $\Z$: se $m$ è un intero diverso da $0$ sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità; (3) $m$ è primo. Abbiamo anche fornito una verifica diretta di una proprietà già nota: gli elementi non invertibili nei quozienti propri di $\Z$ sono tutti divisori dello zero.

Lemma di Euclide (come conseguenza del teorema di Bézout): siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$. Un esempio di applicazione.

Equazioni di primo grado $ax=b$ in anelli commutativi unitari: discussione sul numero delle possibili soluzioni in dipendenza dalle proprietà di $a$.

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

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

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

Elementi periodici in un gruppo; periodo di un elemento periodico. Se se $x$ è un elemento periodico di periodo $m$ di un gruppo (moltiplicativo) $G$, allora, per ogni $a,b\in\Z$, si ha $x^a=x^b\iff a\equiv_m b$. Qualche esempio.

Espressione di un numero intero positivo $n$ in base 10; modulo 9, $n$ è congruo alla somma delle sue cifre.

Esercizi proposti:

1. Utilizzando 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$.
2. Svolgere gli esercizi 5 a 12 da Tautologie, insiemi, aritmetica.
3. Di ciascuno degli elementi di $\Z_4$, $\Z_{6}$, $\Z_{10}$, $\Z_{11}$ dire se è o non è un elemento invertibile, un elemento cancellabile, un divisore dello zero. Degli elementi invertibili di $\Z_{10}$ trovare anche gli inversi.
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. Usando l'algoritmo euclideo esteso, trovare, ove possibile, soluzioni delle equazioni diofantee $14x+6y=1$, $14x+6y=4$, $140x+60y=20$. Di una di esse, trovare tre diverse soluzioni.
7. 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$
8. 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.
9. Sia $n$ un numero intero positivo, rappresentato in base 10 con la stringa “$a_t a_{t-1} a_{t-2}\dots a_2 a_1 a_0$”, (dunque $t\in\N^*$, ciascuno degli $a_i$ è un numero naturale minore di 10 e $n=\sum_{i=0}^t a_i 10^i$). Allora:
   • $n\equiv_{10}a_0$;
   • $n\equiv_{100}10a_1+a_0$ (il numero descritto dalle ultime due cifre di $n$);
   • $n\equiv_4 10a_1+a_0$.
   • $n$ è divisibile per 9 se e solo se la somma delle sue cifre è divisibile per 9;
   • $n$ è divisibile per 3 se e solo se la somma delle sue cifre è divisibile per 3;
   • giustificare il 'criterio di divisibilità per 3' e la 'prova del 9' che vengono insegnati nella scuola elementare;
   • $n\equiv_{11} \sum_{i=0}^t (-1)^i a_i$.
   Usare quanto visto sopra per calcolare (a mente) $\rest(72543618991175,9)$ e $\rest(72543618991175,3)$, e poi $\rest(626\cdot 3125,3)$.
10. Calcolare a mente $2^{100000001}\modbin 7$; $2^{100000001}\modbin 4$ e, dopo aver calcolato il periodo di $[2]_5$ in $\U(\Z_5)$, anche $2^{100000001}\modbin 5$.
11. Determinare (eseguendo solo calcoli a mente) $674\mod 6$, poi $674\modbin -6$ ed infine $n\modbin 7$ dove $n=7005(2^{10}-140)$.

16/12

La lezione è iniziata in ritardo ed è terminata in larghissimo anticipo a causa dei malfunzionamenti della piattaforma informatica utilizzata. Il tempo perso dovrà essere recuperato.

Rapida discussione di un esercizio dalla lezione precedente.

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario $R$ (come dalle note sui polinomi. Attenzione: nelle note l'insieme degli interi positivi è indicato con $\N^+$.); in quesro resoconto $R$ sarà sempre inteso come anello commutativo unitario. Definizione e terminologia essenziale (grado, successione dei coefficienti, coefficiente direttore, termine noto, polinomi monici, polinomi costanti). Proprietà universale per anelli di polinomi. Conseguenze: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata); per ogni intero positivo $m$, l'omomorfismo suriettivo da $\Z[x]$ a $\Z_m[x]$ che ad ogni polinomio $f$ a coefficienti interi associa "$f$ riguardato modulo $m$".

Grado di somma, differenza e prodotto tra due polinomi. Se il polinomio $f\in R[x]$ ha coefficiente direttore cancellabile (in $R$), allora $f$ stesso è cancellabile in $R[x]$ ed inoltre vale per $f$ ed un qualsiasi polinomio $g\in R[x]$ la regola di addizione dei gradi: $\nu(fg)=\nu(f)+\nu(g)$ e $\cd(fg)=\cd(f)\cd(g)$. $R[x]$ è un dominio di integrità se e solo se lo è $R$, ovvero se e solo se vale, in $R[x]$, la regola di addizione dei gradi per ogni coppia di polinomi. Se $R$ è un dominio di integrità si ha $\U(R[x])=\U(R)$. Esempi che mostrano come queste proprietà possano non valere se $R$ non è integro. Qualunque sia $R$ i polinomi in $R[x]$ di grado maggiore di zero e coefficiente direttore cancellabile in $R$ non sono invertibili; di conseguenza $R[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 $R$ è un campo è sicuramente possibile effettuare la divisione per un qualsiasi polinomio non nullo. Di conseguenza, nell'anello dei polinomi su un campo si può eseguire l'algoritmo euclideo per la ricerca di un MCD e valgono il teorema di Bézout e le sue conseguenze (informazione: il teorema di Bézout non vale in $\Z[x]$).

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

Esercizi proposti:

1. 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.
2. 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?
3. Vero o falso: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.
4. 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]$.
5. 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.
6. 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").

18/12

Questa lezione è durata più a lungo del solito per recuperare il tempo perso nella lezione precedente.

Rapidissima discussione su esercizi dalla lezione precedente.

Omomorfismo di sostituzione definito su anelli di polinomi. Applicazione polinomiale definita da un polinomio. Radici di un polinomio. Ogni radice di un polinomio è radice anche di ogni suo multiplo.

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

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

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]$. Caratterizzazione dei polinomi irriducibili nell'anello dei polinomi su un campo; esistenza di radici ed irriducibilità.

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

Polinomi in $\Q[x]$. Ciascuno di essi è associato (in $\Q[x]$) ad un polinomio a coefficienti interi. Criterio di irriducibilità di Eisenstein. Per ogni $n\in\N^*$ ed ogni primo $p$, $x^n-p$ è irriducibile in $\Q[x]$. Radici razionali di un polinomio $f\in\Z[x]$. Il criterio di Eisenstein ed il risultato sulle radici in $\Q$ non sono stati dimostrati. Un esempio: polinomi di grado 2 o 4 irriducibili in $\Z_2[2]$.

Algebre di Boole (e reticoli booleani: equivalenza tra le nozioni).

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 (solo enunciato) per reticoli booleani e per algebre di Boole, e corollari: gli anelli booleani finiti hanno per cardinalità una potenza di 2; due anelli booleani finiti equipotenti sono necessariamente isomorfi (ed enunciati analoghi per le algebre di Boole ed i reticoli booleani).

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$ (come lasciato da dimostrare per esercizio). Interpretazione delle operazioni 'bit a bit' (che traducono i connettivi proposizionali $\xor$ e $\land$) alla luce di questo isomorfismo.

Esercizi proposti:

1. Provare che se $R$ è un anello commutativo unitario e $f$ e $g$ sono polinomi in $R[x]$ tra loro associati, $f$ e $g$ hanno le stesse radici in $R$.
2. Se possibile, trovare un polinomio di coefficiente direttore $-97$ 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. Determinare in $\Z_2[x]$ tutti i polinomi di grado 2, 3 o 4 che siano irriducibili.
5. 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]$.
6. 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]$.
7. 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]$.
8. Svolgere gli esercizi nr. 3 e 8 da Polinomi e strutture algebriche.
9. Trovare tutte le radici in $\Q$ del polinomio $2x^{10}+x^9-x^8+12x^2-3$.
10. Provare che se $f$ è un polinomio monico a coefficienti in $\Z$, tutte le radici di $f$ nel campo razionale sono numeri interi.
11. Il polinomio $50x^{12}-6x^5+18x-24$ è irriducibile in $\Q[x]$? E $x^3-9$?
12. Scrivere $x^3-3x^2+4$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
13. 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$.
14. 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]$.
15. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
16. 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.

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

Sottoalberi massimali (ovvero alberi di supporto) di un multigrafo connesso finito.

Rappresentazione radicale di un albero; foglie. Le foreste finite sono grafi planari. In ogni albero finito con almeno due vertici esistono almeno due vertici di grado uno. Lemma: il sottografo ottenuto da un albero cancellandone un vertice di grado uno ed il lato esso incidente è ancora un albero. Numero di vertici e di lati in un albero finito.

Sia $G$ un multigrafo finito, con insiemi $V$ di vertici e $L$ di lati e con esattamente $c$ componenti connesse. Allora $|L|\ge |V|-c$ (dunque, $|L|\ge |V|-1$ se $G$ è connesso), e vale $|L|=|V|-c$ 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. Elencare, a meno di isomorfismi, i grafi con insieme dei vertici di cardinalità minore di 4. Verificare che nell'elenco dei grafi su quattro vertici disponibile in questo sito i grafi rappresentati sono effettivamente a due a due non isomorfi. Verificare che la lista è esaustiva. Nella stessa lista, decidere quali grafi sono connessi e quali sono alberi o foreste.
3. Esercizi da Grafi, ad esclusione del nr. 4.
4. Disegnare, a meno di isomorfismi, tutti gli alberi con (esattamente) cinque vertici.
5. 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$.
6. Stablire per quali interi positivi $n$ il grafo completo su $n$ vertici abbia cammini euleriani e per quali abbia circuiti euleriani.
7. (A proposito del teorema sui cammini euleriani). Un grafo finito può avere esattamente un vertice di grado dispari?