1 — 6/3

Introduzione al corso; contenuti, finalità, modalità, materiali didattici.

Per il resto: introduzione molto informale alle nozioni di linguaggio, formula e termine, cenni alla distinzione tra sintassi e semantica. I connettivi proposizionali, introdotti per via semantica, cioè tramite tavole (o tabelle) di verità. Comparazione tra l'uso di tali connettivi in un linguaggio semiformalizzato e quello di parole corrispondenti nel linguaggio ordinario.

Forme proposizionali e calcolo dei loro valori di verità; alcuni esempi. Tautologie e contraddizioni Forme logicamente equivalenti tra loro. Antecedente e conseguente di una implicazione.

Alcune tautologie; tra queste: tautologia della doppia negazione; tautologie di iteratività (o idempotenza) per $\land$ e $\lor$, commutatività per $\land$, $\lor$, $\xor$, bicondizionale; principi del terzo escluso e di non contraddizione.

Per il contenuto di questa lezione e delle prossime si vedano Logica rudimentale e tavola dei connettivi binari.

Esercizi proposti:

1. Esercizi A e B da Logica rudimentale.
2. Scrivere le tavole di verità delle forme proposizionali $p\implica(\lnot p)$, $p\lor(p\land q)$ e $(p\land (\lnot q)\land r)$.
3. Cosa esprime il connettivo descritto da questa tavola di verità?

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

2 — 10/3

Discussione di esercizi (connettivi e linguaggio naturale ). Altre tautologie: associatività e distributività per $\land$ e $\lor$; leggi di De Morgan; tautologie sul condizionale (implicazione come disgiunzione, negazione dell'implicazione, bicondizionale come doppia implicazione, contrapposizione, transitività); associatività per $\shiff$ e $\xor$; distributività di $\land$ (ma non di $\lor$) rispetto $\xor$.

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

Introduzione alla logica dei predicati. Variabili e loro sostituzioni. I quantificatori universale ed esistenziale. Occorrenze libere ed occorrenze vincolate di variabili. Proposizioni (o formule chiuse). Predicati. Le sostituzioni di termini a variabili sono limitate alle occorrenze libere delle variabili.

Esercizi proposti:

1. Verificare che le forme proposizionali che a lezione, pur senza dimostrarlo, sono state indicate come tautologie lo sono effettivamente.
2. Decidere se la forma proposizionale $(p\nand (q\nand r))\iff ((p\nand q)\nand r)$ è una tautologia.
3. Negare le frasi "se piove mi bagno", "se piove non mi bagno", "se piove, mi bagno e mi ammalo".
4. Molti utili esercizi sono nella prima parte (sino agli esercizi F) di Logica rudimentale. Consiglio poi di verificare (alcune tra) le forme in esempi di tautologie.

3 — 17/3

Ancora su quantificatori e variabili. Il quantificatore $\exists!$. Quantificatori ristretti. Alcune regole del calcolo dei predicati (come in Logica rudimentale), tra esse: quantificatori ripetuti, negazione di formule con quantificatori (anche ristretti), regola di specializzazione.

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

Descrizioni di insiemi. Estensione di un predicato unario e cenno all'antinomia di Russell; notazione $\set{x\mid \phi(x)}$ per un predicato unario nella variabile $x$. Cenno agli assiomi di separazione (o di comprensione). Anche per il contenuto di questa lezione si può fare riferimento a Logica rudimentale.

Esercizi proposti:

1. Da Logica rudimentale: esercizi H1, H2, H3, H5, H6. Notazione: $\N$ e $\Z$ sono, nell'ordine, gli insiemi dei numeri naturali (cioè interi non negativi) e quello degli interi. Quindi, ad esempio, `$x\in\Z$' va letta come `x è un numero intero'.
2. Si stabilisca il valore di verità delle formule $\forall x\mathrel\lozenge 3(x>100)$ e $\exists x\mathrel\lozenge 3(x>100)$ nell'ambito della teoria dei numeri interi, dove il simbolo $\lt$ e le costanti 3 e 100 sono interpretati nel modo usuale e $\lozenge$ è interpretato in accordo con questa definizione: per ogni coppia di numeri interi $a$ e $b$, $a\mathrel\lozenge b$ se e solo se $(a\lt b\land b\lt a)$.
3. 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)))$?
4. Quanti elementi ha $\set{\vuoto,\set\vuoto}$?
5. Tenendo presente l'antinomia di Russell, verificare che degli assiomi segue che non esiste "l'insieme di tutti gli insiemi".

4 — 20/3

Esercizi ed osservazioni: non esiste l'insieme di tutti gli insiemi; unicità dell'insieme vuoto. Il singleton $\set x$ di un insieme $x$ (è diverso da $x$, per ogni $x$).

Inclusione tra insiemi (ed inclusione stretta). Comparazione tra inclusione ($\sseq$) e appartenenza: è fondamentale distinguere bene tra queste due nozioni. Ad esempio: per ogni $x$ si ha $\vuoto\subseteq x$, quindi in particolare $\vuoto\sseq\vuoto$, ma $\vuoto\notin\vuoto$. Più in generale, sempre per ogni $x$, si ha $x\subseteq x$ e (in conseguenza dell'assioma di fondazione, a cui si è solo accennato) $x\notin x$. L'insieme delle parti $\P(a):=\set{x\mid x\sseq a}$ di un insieme $a$. Esempi.

Nozioni insiemistiche e connettivi proposizionali. Comparazione tra i connettivi di equivalenza e implicazione da una parte, le relazioni di uguaglianza e inclusione tra insiemi dall'altra; operazioni insiemistiche binarie di unione, intersezione e differenza simmetrica, ed identità insiemistiche che coinvolgono queste operazioni dedotte da tautologie (di commutatività, associatività, iteratività, distributività) che coinvolgano $\lor$, $\land$, $\xor$.

L'operazione binaria di differenza tra insiemi; complemento di un insieme in un insieme che lo contenga e connettivo di negazione. Diverse formule tra quelle in Tautologie ed identità insiemistiche; formule insiemistiche di De Morgan (per terne arbitrarie di insiemi, come in Logica rudimentale).

Diagrammi di (Euler-)Venn. Diagrammi di Venn generici e loro uso per dimostrare formule insiemistiche (di uguaglianza o di inclusione) universali o per la costruzione di controesempi (un diagramma di Venn per un certo insieme $V$, in cui quindi ogni elemento di $V$ sia rappresentato da un'area, è generico quando, per ogni parte non vuota $P$ di $V$ nel diagramma appare, non vuota, un'area che descriva gli oggetti appartenenti a ciascuno degli elementi di $P$ ed a nessuno degli elementi di $V\setminus P$). Esempi di diagrammi generici per coppie, terne e quaterne di insiemi (per le quaterne: questo è un diagramma di Venn generico mentre quest'altro non lo è.).

Esercizi proposti:

1. Elencare gli elementi di $\P(\set{0,1})$ e quelli di $\P(\set{0,1,2})$.
2. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\vuoto\sseq\set{1,2,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{2,1,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{4,2,1,3}$.
3. Esercizi J da Logica rudimentale (in buona parte, essenzialmente, già visti a lezione).
4. Verificare le formule in Tautologie ed identità insiemistiche (ne abbiamo già discusse molte a lezione).
5. Siano $a=\set{1,2,3,4,5,6,7}$, $b=\set{5,6,7,8,9}$, $c=\set{0,5,9}$. Elencare gli elementi di: $a\cap b$, $a\ds b$, $b\setminus c$, $(c \setminus b)\ds a$.
6. Calcolare, per un arbitario insieme $a$, $a\cup\vuoto$, $a\cap\vuoto$, $a\setminus\vuoto$, $\vuoto\setminus a$, $a\ds\vuoto$, $a\ds a$.
7. Dimostrare che per ogni $a,b$ sono equivalenti: (1) $a\sseq b$; (2) $a\cap b=a$; (3) $a\cup b=b$; (4) $a\setminus b=\vuoto$; (5) $a\ds b=b\setminus a$.
8. Rappresentare in diagrammi di Venn (generici!) i termini insiemistici $a\ds b$; $a\cap (b\cup c)$; $a\cup (b\cap c)$.

5 — 24/3

Discussione di alcuni esercizi. Vari esempi di diagrammi di Euler-Venn, per descrivere e comparare tra loro termini insiemistici, tra i quali: $a\ds(b\ds c)$, $a\setminus(b\setminus c)$, $(a\setminus b)\setminus c$, $(a\cup b)\setminus c$, $(a\setminus c)\cup (b\setminus c)$.

Osservazioni: per ogni $a$ e $b$ si ha $a\ds a=\vuoto$, $a\ds \vuoto=a$ e $(a\cup b)\setminus b=a\setminus b$.

L'unione unaria $\bigcup a=\set{x\mid \exists b\in a(x\in b)}$ di un insieme $a$; l'intersezione unaria $\bigcap a=\set{x\mid \forall b\in a(x\in b)}$ di un insieme non vuoto $a$. Discussione sul motivo per cui $\bigcap \vuoto$ non è definito. Riduzione di unione ed intersezione binaria alle corrispondenti operazioni unarie: per ogni $a,b$ si ha $a\cup b=\bigcup \set{a,b}$ e $a\cap b=\bigcap \set{a,b}$. Altri esempi di unioni ed intersezioni unarie. Nel corso di queste discussioni abbiamo introdotto le notazioni $\P_k(a)$ e $\Pf(a)$ per l'insieme delle $k$-parti (cioè: sottoinsiemi con esattamente $k$ elementi) e quello delle parti finite di un insieme $a$. Osservazione: $\Pf(a)=\bigcup\set{\P_k(a)\mid k\in\N}$.

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

Coppie ordinate e loro proprietà caratteristica; cenno alla definizione di coppia ordinata proposta da Kuratowski (vedi gli esercizi). Terne ordinate ed analoga proprietà caratteristica. Prodotto cartesiano tra due insiemi.

Avvertenza: come indicato nell'avviso nella pagina principale del corso, a partire dal prossimo giovedì (27) le lezioni del giovedì sono anticipate di un quarto d'ora ed inizieranno dunque lle 16:15.

Esercizi proposti:

1. Calcolare $\bigcup s$ e $\bigcap s$ in ciascuno dei seguenti casi: (1) $s=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $s=\set{x\subseteq\N\mid 3\notin x}$; (3) $s=\big\{\set{124,n}\mid n\in\N\big\}$; (4) $s=\set{[n,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$.
2. Vero o falso? (1): $3\in\set{2n^2+1\mid n\in\Z}$; (2): $10\in\set{2n^2+1\mid n\in\Z}$; (3): $\set{1}\in\set{\set{a,b}\mid a,b\in\Z}$; (4): $\set{1,2}\in\set{\set{a,b}\mid a,b\in\Z}$; (5): $\set{1,2,3}\in\set{\set{a,b}\mid a,b\in\Z}$; (6): $\Z=\set{a-b\mid a,b\in\Z}$.
3. (per i più curiosi). Provare che per ogni $a$, $b$, $c$ e $d$, si ha $\set{\set a,\set{a,b}}=\set{\set c,\set{c,d}}$ se e solo se $a=c$ e $b=d$. (Suggerimento: se $x=\set{\set a,\set{a,b}}$, allora $a=\bigcap\big(\bigcap x\big)\;\dots$) Tenendo conto di questa proprietà, si può dunque dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. In effetti, questa è la definizione di coppia ordinata proposta da Kuratowski (ma ce ne sono altre!).
4. Dimostrare che, per ogni $x$ e $y$:
   1. $x\times y=\vuoto$ se e solo se uno tra $x$ e $y$ è vuoto;
   2. $x\times y=y\times x$ se e solo se o $x=y$ oppure uno tra $x$ e $y$ è vuoto.
5. Elencare gli elementi di $\set{1,2}\times \set{1,2,3}$, quelli di $\set{1,2,3}\times \set{1,2}$ e quelli di $(\set{1,2}\times \set{1,2,3})\cap (\set{1,2,3}\times \set{1,2})$.
6. 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$.

6 — 27/3

Discussione di alcuni esercizi.

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

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

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

Prodotto relazionale tra corrispondenze; sua associatività.

Applicazioni (o funzioni) tra due insiemi; definizione ed esempi. Terminologia e notazioni: dominio e codominio di un'applicazione $f$, l'immagine $f(x)$ di un elemento $x$ del dominio di $f$ (è un elemento del codominio); $\Map(a,b)$, ovvero $b^a$, è l'insieme delle applicazioni di dominio $a$ e codominio $b$.

Descrizioni di applicazioni (o, più in generale, di corrispondenze) nella forma $\dots\in a\mapsto\dots\in b$. Il problema della "buona definizione" di un'applicazione. Alcuni esempi di corrispondenze descritte con questa sintassi che sono o che non sono applicazioni.

Esercizi proposti:

1. Siano $a=\set{1,2,3}$ e $b=\set{0,5,10}$. Sia poi $\rho$ la corrispondenza da $a$ a $b$ definita da: per ogni $x\in a$ e $y\in b$ si ha $x\mathrel\rho y\iff x^2\le y$. Elencare gli elementi del grafico di $\rho$. Rappresentare poi $\rho$ con un diagramma con frecce e con una tabella.
2. Siano $\N$ l'insieme dei numeri naturali e $S=\set{1,2,3}$. Siano poi $\alpha$ la relazione binaria in $S$ definita da: $(\forall x,y\in S)(x\mathrel\alpha y\iff x\lt y)$ e $\beta$ la corrispondenza da $S$ ad $\N$ di grafico $\set{2}\times\set{x\in\N\mid x\lt 10}$. Descrivere la corrispondenza prodotto $\alpha\beta$.
3. Siano $\alpha$ e $\beta$ le corrispondenze da $\Z$ a $\P(\Z)$ definite ponendo, per ogni $n\in\Z$ e $x\in \P(\Z)$, $\quad n\mathrel{\alpha}x\iff n\in x\quad$ e $\quad n\mathrel{\beta}x\iff n\notin x$. Sia poi $\gamma$ la relazione di inclusione in $\P(\Z)$, cioè la relazione binaria in $\P(\Z)$ definita ponendo, per ogni $x,y\in\P(\Z)$, $x\mathrel{\gamma}y\iff x\sseq y$. Descrivere $\alpha\gamma$ e $\beta\gamma$.
4. Sia $a=\set{x\in\N\mid x\lt 10}$ e sia $\tau$ la relazione binaria in $a$ definita da: $\forall x,y\in a (x\mathrel\tau y\iff x\lt y)$. Descrivere $\tau^2=\tau\tau$ e $\tau^3=\tau\tau\tau$. Se, per ogni intero positivo $n$, indichiamo con $\tau^n$ il prodotto $\tau\tau\cdots\tau$ con $n$ fattori, è vero o falso che esiste un intero positivo $n$ tale che $\tau^n$ sia la relazione binaria in $a$ con grafico vuoto?
5. (Già in parte discusso in aula) Indicato con $\R^+_0$ l'insieme dei numeri reali non negativi (cioè: $\R^+_0=\set{a\in\R\mid a\ge 0}$), si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • $\alpha$ da $\R$ a $\R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\beta$ da $\R^+_0$ a $\R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\gamma$ da $\R^+_0$ a $\R^+_0$, di grafico $\set{(a,b)\in\R\times\R^+_0\mid a=b^2}$;
6. Quali tra le corrispondenze qui descritte sono applicazioni? Qui $P=\P(\Z)\setminus\set\vuoto$ è l'insieme delle parti non vuote di $\Z$, come sempre $\P_2(\Z)$ è l'insieme delle parti di $\Z$ che hanno esattamente due elementi.
   1. $n\in\Z\mapsto n^2/2\in\Z$;
   2. $n\in\Z\mapsto \set {n,2n}\in\P(\Z)$;
   3. $n\in\Z\mapsto n^2/2\in\Q$;
   4. $\set{a,b}\in\P_2(\Z)\mapsto a+b\in\N$;
   5. $\set{a,b}\in\P_2(\Z)\mapsto a+b\in\Z$;
   6. $\set{a,b}\in\P_2(\N)\mapsto a^b\in\N$;
   7. $(a,b)\in\Z\times\Z\mapsto a-b\in\N$;
   8. $(a,b)\in\Z\times\Z\mapsto a-b\in\Z$;
   9. $(a,b)\in\N\times\N\mapsto a^b\in\N$;
   10. $X\in P\mapsto \min X\in\Z$; (qui $\min X$ è, se esiste, il più piccolo numero appartenente ad $X$)
   11. $X\in P\mapsto \Z\setminus X\in P$;
   12. $X\in \P(\Z)\mapsto X\cap\N\in\P(\N)$;
   13. $X\in \P(\Z)\mapsto X\ds\N\in\P(\N)$.

7 — 31/3

Discussione di alcuni esercizi.

Alcuni esempi di applicazioni: l'applicazione identica $\id_a=(a,a,\Delta_a)$ di un insieme (dove $\Delta_a=\set{(x,x)\mid x\in a}$ è la diagonale di $a$) e, più in generale, l'immersione $x\in c\mapsto x\in a$ in un insieme $a$ di una sua parte $c$. Restrizioni (se $f\in\Map(a,b)$ e $c\sseq b$, $f_{|c}\colon x\in c\mapsto f(x)\in b$ è la restrizione di $f$ a $c$) e, viceversa, prolungamenti di applicazioni (ad esempio, le immersioni sono restrizioni di applicazioni identiche). Ridotte di applicazioni (se $f\colon a\to b$ è un'applicazione e $\im f\sseq c\sseq b$, la ridotta di $f$ a $c$ è l'applicazione $f^{|c}\colon x\in a\mapsto f(x)\in c$. Ridotta all'immagine.

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 $fg=g\circ f$. Descrizione esplicita di $g\circ f$. Alcuni esempi.

Applicazioni suriettive (cioè con immagine e codominio uguali); forme equivalenti della definizione di suriettività; sua negazione. Esempi. Discussione di un frequente, insensatissimo errore consistente nella pretesa di dimostrare che un'applicazione $f$ sia suriettiva a partire dal fatto che $\im f$ è contenuto in $\im f$.

La composta tra due applicazioni (componibili) suriettive è certamente suriettiva; viceversa, se un'applicazione composta $g\circ f$ è suriettiva, allora $g$ è suriettiva (ma, come abbiamo visto con un esempio, $f$ può non esserlo).

Esercizi proposti:

1. Siano $f\colon a\to b$ un'applicazione e $\iota$ l'immersione di una parte $c$ di $a$ in $a$. In quale modo abbiamo chiamato l'applicazione $f\circ\iota$?
2. Tra le applicazioni (correttamente) descritte nell'ultimo esercizio della lezione scorsa, stabilire quali sono suriettive.
3. Date le applicazioni $f\colon n\in\N\mapsto 2n+3\in\N$ e $g\colon n\in\N\mapsto 6n\in\N$, descrivere esplicitamente $g\circ f$ e $f\circ g$. Quali tra queste quattro applicazioni sono suriettive?
4. Svolgere gli esercizi nr. 7 e 8 dalla raccolta "per le vacanze di pasqua".

8 — 3/4

Applicazione immagine $\vecf\colon\P(a)\to\P(b)$ ed applicazione antiimmagine $\avecf\colon\P(b)\to\P(a)$, definite da un'applicazione $f\colon a\to b$ ponendo $\vecf(c)=\im f_{|c}=\set{f(x)\mid x\in c}$ per ogni $c\in\P(a)$ e $\avecf(c)=\set{x\in a\mid f(x)\in c}$ per ogni $c\in\P(b)$. Vari esempi ed osservazioni. Tra queste: $\vecf (\vuoto)=\avecf(\vuoto)=\vuoto$, $\vecf(a)=\im f$, $\,\avecf (b)=\avecf (\im f)=a$; per ogni $y\in b$, $\avecf(\set y)=\set{x\in a\mid f(x)=y}$; $f$ è suriettiva se e solo se $\forall y\in b(\avecf(\set{b})\ne\vuoto)$. Per ogni $c\in\P(a)$ e $d\in\P(b)$ si ha $c\sseq\avecf(\vecf (c))$ (e l'inclusione può essere stretta) e $\vecf(\avecf (d))=d\cap\im f$, quindi $f$ è suriettiva se e solo se $\forall d\in\P(b)(\vecf(\avecf (d))=d)$.

Applicazioni iniettive. Forme equivalenti della definizione; 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))$. Se $a$ è un insieme con meno di due elementi, ogni applicazione di dominio $a$ è iniettiva. Sono iniettive le immersioni ed anche tutte le restrizioni delle applicazioni iniettive. Applicazioni biettive; lo sono le applicazioni identiche.

La composta tra due applicazioni (componibili) iniettive è certamente iniettiva; viceversa, se un'applicazione composta $g\circ f$ è iniettiva, allora $f$ è iniettiva (ma $g$ può non esserlo, anche se $g\circ f$ è biettiva). Conseguenze ovvie, di questo e di altri risultati precedenti, a proposito della biettività.

Un'applicazione $f\colon a\to b$ è iniettiva se e solo se, per ogni $y\in b$, $\avecf(\set y)$ ha al massimo un elemento (cioè: $\avecf(\set y)$ o è vuoto o è un singleton); conseguente caratterizzazioni della biettività.

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

Teorema: un'applicazione $f\colon a\to b$ è iniettiva se e solo se ammette retrazioni o ha dominio vuoto.

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

Nota: esistono in questo sito delle note su sezioni e retrazioni. Chi volesse leggerne almeno una parte tenga presente che molto del materiale lì contenuto non fa parte del nostro programma e le notazioni lì usate non sono quelle seguite nel corso. In particolare, rispetto al corso:

1. le note usano una diversa notazione per la composizione di applicazioni: se $f\colon a\to b$ e $g\colon b\to c$ sono applicazioni componibili, nelle note la loro composta $g\circ f$ è scritta sempre come $fg$ (facendo cioè riferimento al prodotto relazionale);
2. le note usano la notazione esponenziale per l'immagine di un elemento mediante un'applicazione: $x^f$ piuttosto che $f(x)$ come nel corso.

Esercizi proposti:

1. Provare che per ogni insieme $a$ sia l'applicazione immagine che l'applicazione antiimmagine definite da $\id_a$ coincidono con $\id_{\P(a)}$.
2. Siano $f\colon a\to b$ e $g\colon b\to a$ applicazioni. Provare che l'applicazione immagine $(g\circ f)\vec{\phantom 1}3$ definita da $g\circ f$ è $\vecg\circ \vecf$ e che, analogamente, $(g\circ f)\avec{\phantom 1}3=\avecf\circ\avecg$.
3. Sia $f\colon a\to b$ un'applicazione. Provare:
   • Per ogni $x\in a$, $\vecf(\set x)=\set{f(x)}$.
   • $f$ è iniettiva se e solo se $\forall c\in\P(a)(\avecf(\vecf (c))=c)$.
   • Se $f$ è biettiva, $\vecf$ è biettiva e la sua inversa è $\avecf$.
4. Considerata l'applicazione ("valore assoluto") $f\colon n\in\Z\mapsto |n|\in\Z$ e gli insiemi $a=\set{0,1,2}$ e $b=\set{-1,3}$, si calcolino: $\im f$, $\vecf(a)$, $\avecf(a)$, $\vecf(b)$, $\avecf(b)$, $\vecf(\avecf(b))$, $\avecf(\vecf(b))$, $\avecf(\Z\setminus\N)$.
5. Considerata l'applicazione $f\colon x\in\P(\Z)\mapsto \N\cap x\in\P(\N)$, si calcolino: $\im f$, $\vecf(\P(\N))$, $\avecf(\set{\vuoto})$, $\avecf(\set{\set{0}})$.
6. Tra le applicazioni (correttamente) descritte nell'ultimo esercizio della lezione nr. 6, stabilire quali sono iniettive. Fare lo stesso per quelle dalla raccolta "per le vacanze di pasqua" (numeri 7 e 8).
7. 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$.
8. Di ciascuna delle seguenti applicazioni, decidere se è iniettiva e se è suriettiva; descriverne poi (tutte) le sezioni e le retrazioni:
   • $a\colon n\in\N\mapsto n+1 \in\N$
   • $b\colon n\in\Z\mapsto n+1 \in\Z$
   • $c\colon n\in\N\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\N$
   • $d\colon n\in\Z\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\Z$
9. Siano $a=\set{0,1,2}$ e $b=\set{0,1,2,3}$. Trovare tutte le sezioni delle applicazioni qui definite:
   • $f\colon x\in a\mapsto x+1\in b$
   • $\alpha\colon b\to a$ che manda 3 in 1 ed ogni altro elemento di $b$ in sé stesso.
10. Si scrivano tre diverse sezioni dell'applicazione $x\in\P(\Z)\mapsto x\cap\N\in\P(\N)$.

9 — 7/4

Osservazione: le retrazioni sono suriettive, le sezioni sono iniettive.

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

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

Esempi di inverse; vari metodi che permettono di riconoscere che un'applicazione sia biettiva. Osservazione: per un'applicazione $f\colon a\to a$ (di dominio e codominio uguali), poniamo $f^2=f \circ f$, $f^3=f \circ f\circ f$ e, più in generale, per ogni intero $n>1$, $f^n=f\circ f\circ \cdots\circ f$, composizione con $n$ fattori (tutti uguali a $f$). Se $f^n=\id_a$, allora $f$ è biettiva, con inversa $f^{n-1}$ (ad esempio, $f=f^{-1}$ se e solo se $f^2=\id_a$; l'applicazione $x\in\P(s)\mapsto s\setminus x\in\P(s)$ è biettiva, qualunque sia l'insieme $s$). Trasposizioni (se $s$ è un insieme e $a$ e $b$ due suoi elementi distinti, la trasposizione in $s$ definita da $a$ e $b$ è l'applicazione $\tau\colon s\to s$ descritta da $\tau(a)=b$, $\tau(b)=a$ e $\tau(x)=x$ per ogni $x\in s\setminus\set{a,b}$. Essa è biettiva, perché $\tau\circ\tau=\id_s$).

Osservazioni sull'importanza della nozione di invertibilità. Un esempio di applicazione non biettiva con esattamente una retrazione.

Equipotenza tra insiemi: se $a$ e $b$ sono insiemi $a$ è equipotente a $b$ (in simboli: $|a|=|b|$) se e solo se esiste un'applicazione biettiva $a\to b$; se ciò accade si ha anche $|b|=|a|$. Esempio: $|\Z|=|\N|$ (si veda uno degli esercizi di questa lezione). Solo informazione: anche $\Q$ è equipotente a $\N$, invece $\R$ non lo è; per ogni insieme $s$, $\P(s)$ non è equipotente a $s$.

Introduzione alla combinatoria. Principio di buon ordinamento per i naturali (ogni parte non vuota di $\N$ ha minimo). Dimostrazioni per controesempio minimo. Teorema: per ogni $n\in\N$, non esistono applicazioni iniettive dall'insieme $\set{1,2,3,\dots,n}$ dei primi $n$ interi positivi ad una sua parte propria. La dimostrazione va ancora completata.

Esercizi proposti:

1. Sia $f\colon a\to b$ un'applicazione. Allora $f$ è biettiva se e solo se: $\forall y\in b(|\avecf(\set y)|=1)$.
2. Dimostrare: $|\N|=|\N^*|$ (qui e altrove, $\N^*=\N\setminus\set 0$).
3. Tra le applicazioni $f\colon n\in\Z\mapsto 3n-2\in\Z$, $g\colon n\in\Z\mapsto 3n-2\in\Q$, $h\colon n\in\Q\mapsto 2n-1\in\Q$, $k\colon n\in\Z\mapsto 8-n\in\Z$ si dica quali sono biettive e di queste si determinino le inverse. Fare lo stesso per l'applicazione $\alpha$ da $a=\set{1,2,3,4}$ ad $a$ che manda 1 in 3, 2 in 4, 3 in 2 e 4 in 1.
4. Si trovi l'inversa dell'applicazione al punto (ii) dell'esercizio 7 di quelli per le vacanze di pasqua.
5. Si verifichi che l'applicazione $n\in\N\mapsto \begin{cases}-n/2,&\text{se }n\text{ è pari}\\(n+1)/2,&\text{se }n\text{ è dispari}\end{cases}\in\Z$ è l'inversa dell'applicazione $n\in\Z\mapsto\begin{cases}2n-1,&\text{se }n\gt0\\-2n,&\text{se }n\le0\end{cases}\in\N$ discussa a lezione.

10 — 10/4

Discussione di esercizi

Completamento della dimostrazione lasciata in sospeso la lezione scorsa. Conseguenze: se $n$ e $m$ sono numeri naturali distinti, non esistono applicazioni biettive da $\set{1,2,3,\dots,n}$ a $\set{1,2,3,\dots,m}$; buona definizione della cardinalità ("numero degli elementi") di un insime finito; nessun insieme finitoè equipotente ad una sua parte propria (cosa che può accadere, in realtà accade sempre, per insiemi infiniti; ad esempio).

Teorema: siano $a$ e $b$ insiemi finiti. Allora:

• esistono applicazioni iniettive da $a$ a $b$ se e solo se $|a|\le |b|$;
• esistono applicazioni suriettive da $a$ a $b$ se e solo se $|a|\ge |b|$ e $|b|=0\implica |a|=0$;
• esistono applicazioni biettive da $a$ a $b$ se e solo se $|a|=|b|$;
• se $|a|=|b|$ e $f\colon a\to b$ è un'applicazione, sono equivalenti: (1) $f$ è iniettiva, (2) $f$ è biettiva, (3) $f$ è suriettiva. (Questo è falso per insiemi infiniti.)

Cenni alla comparazione tra cardinalità per insiemi infiniti, come da questa vecchia pagina (dove quanto marcato come meno ovvio, ad eccezione delle prime due uguaglianze, stabilite alla lezione precedente, va inteso solo a titolo di notizia).

Il principio di induzione. Nella prima forma: se $\phi$ è un predicato unario, $b\in\N$ e $N_b=\set{n\in\N\mid b\le n}$, se valgono $\phi(b)$ e, per ogni $n\in N_b$, l'implicazione $\phi(n)\implica \phi(n+1)$, allora vale $\phi(n)$ per ogni $n\in N_b$. Come esempio di applicazione: per ogni $n\in\N^*$, $n^2$ è la somma $\sum_{i=1}^n (2i-1)$ (vale a dire: $1+3+\cdots+(2n-1)$) dei primi $n$ interi positivi dispari. Seconda forma del principio di induzione (o principio di induzione completa): offre una versione alternativa (e non consigliata) del metodo di dimostrazione per controesempio minimo.

Esercizi proposti:

1. Vero o falso? Siano $a$ e $b$ due insiemi finiti. Allora, necessariamente:
   1. … se $|b|\le |a|$, esistono applicazioni suriettive da $a$ a $b$;
   2. … se $0\lt |b|\le |a|$, esistono applicazioni suriettive da $a$ a $b$;
   3. … se $|a|=|b|$ ogni applicazione suriettiva da $a$ a $b$ è iniettiva;
   4. … esiste un sottoinsieme proprio di $b$ equipotente ad $a$ se e solo se $|a|\lt |b|$;
2. Dimostrare, per induzione, che per ogni intero positivo $n$:
   1. $t_n:=\sum_{i=1}^n i=n(n+1)/2$;
   2. $\sum_{i=1}^n i^3=n^2(n+1)^2/4$, ovvero: $\sum_{i=1}^n i^3=t_n^2$.
   Ad esempio, il numero dell'anno in corso, 2025, è il quadrato di 45, che è $t_9=1+2+\cdots+9$, quindi $2025=1^3+2^3+\cdots+9^3$.
   3. $\sum_{i=1}^n i^2=n(n+1)(2n+1)/6$.

11 — 14/4

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

• esistono esattamente $|b|^{|a|}$ applicazioni da $a$ a $b$;
• il numero delle applicazioni iniettive da $a$ a $b$ è il fattoriale discendente $|b|^{\underline{|a|}}$ dunque, se ne esistono (cioè se $|a|\le |b|$), il loro numero è $|b|!/(|b|-|a|)!$;
• se esistono applicazioni biettive da $a$ a $b$ (cioè se $|a|=|b|$), il loro numero è $|a|!$. In particolare, $|\Sym(a)|=|a|!$.

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

Dimostrazione alternativa (ed indipendente) del fatto che per ogni insieme $S$ ed ogni $a\in S$, si ha $|\P(S)\setminus\P(S\setminus\set a)|=|\P(S\setminus\set a)|$ e quindi $|\P(S)|=2|\P(S\setminus\set a)|$.

Esercizi proposti:

1. Verificare in dettaglio, utilizzando come aiuto un diagramma di Venn come fatto a lezione nel caso di una coppia di insiemi, la validità della formula che esprime il principio di inclusione-esclusione per una terna di insiemi finiti.
2. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=15$ e $|B|=10$.
   1. Se $|A\cap B|=8$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=20$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 8$, cosa possiamo dire su $|A\cup B|$?
3. Siano dati due insiemi $a$ e $b$ tali che $|a|=6$ e $|b|=12$. Quante sono le applicazioni da $a$ a $b$? Quante tra queste sono iniettive? Quante sono costanti?
4. Siano $a=\set{n\in\N\mid n \lt 9}$, e $b=\set{5,11,33,76}$, Quante sono le applicazioni $f$ da $a$ a $b$ tali che $\forall x\in a$$(f(x)\le 30)$? Quante sono le applicazioni $g$ da $b$ ad $a$ tali che $g(5)=g(33)\ne g(11)$?
5. Siano $a$ e $b$ insiemi di cardinalità, nell'ordine, 5 e 2. Quante sono le applicazioni suriettive da $a$ a $b$? E quante quelle da $b$ ad $a$? (Attenzione: non c'è bisogno di usare formule di carattere generale).
6. Quante sono le parole di lunghezza 6 che si possono ottenere utilizzando un alfabeto di 10 caratteri? Tra queste, quante sono quelle che hanno tutte le lettere in posizione dispari (la prima, la terza etc.) uguali? E quelle palindrome? E quelle in cui nessuna lettera è ripetuta? E quelle in cui non ci sono lettere consecutive ripetute?
7. Utilizzando il consueto alfabeto della lingua italiana, con 21 lettere di cui cinque vocali, quante sono le parole di lunghezza sette in cui appaiono, alternate, consonanti e vocali (cioè: ogni vocale se non è la prima lettera della parola è preceduta da una consonante e se non è l'ultima è seguita da una consonante)?
8. Se $S$ è un insieme, quali sono le funzioni caratteristiche delle 3-parti di $S$?

12 — 24/4

Completamento della seconda dimostrazione (per induzione) del fatto che ogni insieme finito di cardinalità $n$ ha esattamente $2^n$ parti.

Se $a$ e $b$ sono insiemi equipotenti, allora $\P(a)$ e $\P(b)$, ma anche, per ogni $k\in\N$, $\P_k(a)$ e $\P_k(b)$) sono equipotenti. Per verificarlo si è fatto uso dell'osservazione che se $f\colon a\to b$ è un'applicazione biettiva e $c\sseq a$, l'applicazione $x\in c\mapsto f(x)\in \vecf(c)$ (ridotta all'immagine della restrizione di $f$ a $c$) è biettiva.

Coefficienti binomiali: per ogni $n,k\in\N$, $\binom nk$ è per definizione la cardinalità di $\P_k(a)$, per un qualsiasi insieme $a$ di cardinalità $n$. Osservazioni sui casi, banali, in cui $k$ vale 0, 1 o $n$, oppure $k>n$. Per ogni $n\in\N$, $\sum_{k=0}^n\binom nk=2^n$. Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$.

Formula ricorsiva per i coefficienti binomiali: per ogni $k,n\in \N$, $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$. Il triangolo di Tartaglia-Pascal e sue proprietà (tra cui: simmetria e somma delle righe). Formula esplicita per i coefficienti binomiali: $\forall n,k\in\N \bigl(k\le n\implica\binom nk=n!/k!(n-k)!\bigr)$, con dimostrazione svolta per induzione su $n$.

Esempi ed esercizi su calcolo del numero delle parti di assegnata cardinalità e soggetti ad altri vincoli in un insieme finito.

I contenuti di questa parte di programma relativa alla combinatoria sono in una nuova nota.

Partizioni di un insieme (si vedano le note su partizioni ed equivalenze). Definizione, caratterizzazione, esempi; partizioni banali. Se $F$ è una partizione di un insieme finito $a$, allora $|a|=\sum_{b\in F}|b|$. Proiezione canonica di un insieme su una sua partizione (è un'applicazione suriettiva). Altri esempi: le partizioni su insiemi di cardinalità al più $3$; partizioni di cardinalità $2$.

Esercizi proposti:

1. Sia $S$ un insieme di cardinalità 11. Quante sono le parti di $S$ di cardinalità 4? E quante quelle di cardinalità 7? E quante quelle di cardinalità 17? Quante sono le 5-parti di $\P(S)$?
2. Sapendo che valgono le uguaglianze $\binom {15}6=5005$ e $\binom {15}7=6435$, calcolare $\binom {15}7$ e poi $\binom {15}8$.
3. 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?
4. 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}$, $Z:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X) \land |X|=6}$ e $T:=\{X\in\P(A)\mid{} $esattamente un elemento di $X$ è maggiore di $5\land|X|=4\}$.
5. Sia $a=\set{n\in\N\mid n\lt 10}$. Stabilire quali tra questi sono e quali non sono partizioni di $a$: $a$, $b=\set a$, $c=\set{\vuoto,\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $d=\set{\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $e=\set{\set{1,2,3,4,5,7,9},\set{0,2},\set{6,8}}$.
6. Trovare quattro partizioni distinte dell'insieme $\set{1,2,3,4}$.
7. Trovare tre partizioni non banali dell'insieme $\Z$.

13 — 28/4

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

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

Classi di equivalenza; loro proprietà fondamentali: fissata una relazione di equivalenza $\sim$ in un insieme $A$ per ogni $a,b\in A$ si ha:

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$;
• sono tra loro equivalenti: $a\sim b$, $b\sim a$, $ a\in[b]_\sim$, $b \in [a]_\sim$, $[a]_\sim=[b]_\sim$;
• $[a]_\sim$ è l'unica classe di equivalenza rispetto a $\sim$ a cui $a$ appartenga.

Con le stesse notazioni: l'insieme quoziente $A/{\sim}$. Questo insieme è una partizione di $A$. Di conseguenza, per ogni $a,b\in A$ sono equivalenti: $a\sim b$, $[a]_\sim\cap[b]_\sim\ne\vuoto$, $[a]_\sim\sseq [b]_\sim$.

Descrizione delle classi di equivalenza rispetto ad un nucleo di equivalenza.

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

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

Esercizi proposti:

1. Svolgere gli esercizi 1 (esclusi i punti f e g) e 2 (solo i punti d ed e) da relazioni binarie, limitatamente alle proprietà di essere, riflessiva, simmetrica, transitiva, di equivalenza.
2. Utilizzando quanto detto a lezione (e riportato in questo registro) sulla semplificazione nella verifica della transitività di una relazione binaria, trovare tutte le relazioni binarie non transitive sull'insieme $\set{0,1}$.
3. Provare che se $f\colon a\to b$ e $g\colon b\to c$ sono applicazioni componibili e $g$ è iniettiva, $g\circ f$ ed $f$ hanno lo stesso nucleo di equivalenza.
4. Sia $a$ un insieme di cardinalità 7. Calcolare il numero della partizioni di $a$ in cui appaia un blocco di cardinalità 4.
5. 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$?
6. Siano $a$ un insieme finito e $k\colon \P(a)\to\N$ l'applicazione che ad ogni parte $x$ di $a$ associa la sua cardinalità. Descrivere il nucleo di equivalenza $\tau$ di $k$ e l'insieme quoziente $Q:=\P(a)/\tau$. Quanti elementi ha $Q$?
7. Provare che la relazione binaria $\sigma$ definita in $\R$ ponendo, per ogni $x,y\in\R$, $x\mathrel\sigma y$ se e solo $x^4+(3-\log (|x|+1))^3+1=y^4+(3-\log(|y|+1))^3+1$ è di equivalenza.
8. 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$.
9. Svolgere le parti (i) e (ii) dell'esercizio 3 dal compito del 18 giugno 2019.
10. Siano $S=\set{n\in\N\mid n\lt 15}$, $T=\set{n\in\N\mid n\lt 6}$ e $\theta$ l'applicazione $X\in\P(S)\mapsto |X|\in\N$. Detto $\rho$ il nucleo di equivalenza di $\theta$, descrivere $[T]_\rho$ e $|[T]_\rho|$. Trovare, se possibile, una parte $V$ di $S$ tale che $[V]_\rho\ne[T]_\rho$ ma $|[V]_\rho|=|[T]_\rho|$.
11. 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$.
12. 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 $5\in[0]_\sim=[6]_\sim$
    • … le relazioni di equivalenza $\rho$ in $a$ tali che $0\mathrel\rho 3$, $\set{2,5}\subseteq [3]_\rho$ e $6\in[4]_\rho\iff 1\mathrel\rho 6$.
13. Sia $a$ un insieme tale che $|a|=6$. Quante sono le relazioni di equivalenza $\rho$ in $a$ tali che $a/\rho$ abbia esattamente due elementi?
14. Posto $a=\set{1,2,3}$, e detta $F$ la partizione $\set{\set 1,\set{2,3}}$ di $a$, stabilire quante sono le applicazioni $f\colon a\to a$ tali che $F=a/\rho$, dove $\rho$ è il nucleo di equivalenza di $f$.

14 — 5/5

Teorema di omomorfismo per insiemi (a proposito del quale, oltre a quanto nelle note su partizioni ed equivalenze, si veda anche l'esempio 2 dalla precedente nota su questo stesso teorema, (nella quale si usano notazioni diverse da quelle del corso: per comporre applicazioni viene usato il prodotto relazionale e non la composizione `$\circ$', per le immagini di elementi viene usata la notazione esponenziale). Ogni applicazione è la composta di un'applicazione iniettiva per una suriettiva. Esempi.

Operazioni binarie (ovunque definite) in un insieme. Definizione ed esempi. Operazioni binarie commutative ed associative. Strutture algebriche con un'operazione binaria; semigruppi. Molti esempi (operazioni di addizione, di moltiplicazione e di sottrazione in insiemi numerici; operazioni insiemistiche nell'insieme delle parti di un insieme; prodotto relazionale in $\Rel(S)$ e composizione tra applicazioni in $T(S)=\Map(S,S)$; per un insieme $S$; concatenazione tra stringhe (ovvero parole) su un alfabeto).

Cenno ai teoremi di associatività e di commutatività.

L'operazione opposta $*^{op}$ definita da una operazione binaria $*$ (se $*$ è definita sull'insieme $a$, allora $*^{op}$ è definita da: per ogni $x$, $y\in a$, $x\mathbin{*^{op}} y=y*x$), con cenno al principio di dualità destra/sinistra per operazioni binarie. Si ha $(*^{op})^{op}=*$; inoltre $*^{op}=*$ se e solo se $*$ è commutativa; $*^{op}$ è associativa se e solo se lo è $*$. Esempio: il caso del prodotto relazionale e della composizione tra applicazioni.

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

Elementi neutri a sinistra e a destra; elementi neutri. Vari esempi (n tutte le strutture già presentate). Rispetto ad un'operazione binaria, un elemento è neutro a sinistra (risp. a destra) se e solo se è neutro a destra (risp. a sinistra) rispetto all'operazione opposta.

Teorema (unicità dei neutri): se, in una assegnata struttura con un'operazione binaria, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, inoltre $s$ è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura. Esempi di strutture con più di un neutro a destra o a sinistra. Monoidi; vari esempi, tra questi: il monoide delle trasformazioni di un insieme ed il monoide delle parole su un alfabeto.

In una struttura con un'operazione binaria ed elemento neutro: simmetrici destri o sinistri; simmetrici (uso, alternativo, dei termini 'inverso' e 'opposto' per 'simmetrico'). L'eventuale elemento neutro è simmetrico di sé stesso. Elementi simmetrizzabili (anche: simmetrizzabili a sinistra o a destra). Vari esempi, tra cui: identificazione degli elementi simmetrizzabili a destra, a sinistra, simmetrizzabili nel monoide delle trasformazioni di un insieme.

Teorema di unicità dei simmetrici nei monoidi: se, per un elemento $a$ di un assegnato monoide $S$, $s$ è un simmetrico sinistro e $d$ è un simmetrico destro di $a$, allora $s=d$, quindi $s$ è l'unico simmetrico di $a$, l'unico simmetrico sinistro di $a$ e l'unico simmetrico destro di $a$ in $S$.

Esercizi proposti:

1. 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$?
2. Sia $a=\set{n\in\Z\mid -5\le m\le 8}$. Usando il teorema di omomorfismo per insiemi, verificare che la relazione binaria $\sim$ in $a$ definita ponendo, per ogni $x,y\in a$, $x\sim y$ se e solo se $x^2+3=y^2+3$ è di equivalenza e determinare $|a/{\sim}|$.
3. Verificare che se $a$ è un insieme, il monoide delle trasformazioni di $a$ è commutativo (cioè: ha operazione commutativa) se e solo se $|a|\le 1$.
4. Verificare che il monoide delle parole su un alfabeto è, effettivamente, un monoide.
5. Sia $*$ un'operazione binaria associativa e commutativa sull'insieme $S$. Senza fare uso dei teoremi di associatività e commutatività, dimostrare in modo diretto che, per ogni $a,b,c,d\in S$, si ha: $(a*b)*(c*d)=(a*c)*(b*d)$.
6. Delle seguenti tredici parti di $\Z$: $\N$, $\Z\setminus \N$, $\vuoto$, $\set{x\in\Z \mid x > 8}$, $\set{x\in\Z \mid x> -8}$, $\set 0$, $\set 1$, $\set {0,1}$, $\set {-1}$, $\set {0,1,2}$, $\set {1,-1}$, l'insieme degli interi pari, l'insieme degli interi dispari, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
7. L'insieme delle parti infinite di $\N$ è chiuso in $(\P(\N),\cap)$, in $(\P(\N),\cup)$, in $(\P(\N),\ds)$, in $(\P(\N),\setminus)$?
8. Nel monoide delle parole su un alfabeto che contenga la lettera y (con l'operazione di concatenazione), 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.
9. Fissato un insieme $a$, dire quali dei seguenti insiemi costituiscono parti chiuse in $(T(a),\circ)$: l'insieme delle applicazioni (da $a$ in $a$) iniettive, l'insieme di quelle suriettive, l'insieme di quelle biettive, l'insieme di quelle non iniettive, l'insieme di quelle non suriettive, l'insieme di quelle non biettive, l'insieme di quelle costanti, l'insieme di quelle non costanti. In alcuni casi la risposta potrebbe dipendere dalla scelta di $a$.
10. 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,*)$.
11. Vero o falso? Per ogni insieme $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;
    4. … se $x$ è un elemento di $S$ che ha in $(S,*)$ due distinti simmetrici destri, allora $x$ non ha simmetrici sinistri in $(S,*)$;
    5. … se $*$ è associativa e $x$ è un elemento di $S$ che ha in $(S,*)$ due distinti simmetrici destri, allora $x$ non ha simmetrici sinistri in $(S,*)$.
12. Studiare (non tutte subito) le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, determinandone gli (eventuali) elementi neutri a sinistra, a destra, neutri delle strutture da esse definite e, se l'elemento neutro esiste, gli elementi simmetrizzabili a sinistra, a destra, simmetrizzabili (descrivendo anche i rispettivi simmetrici a sinistra o a destra).
    • $\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)$;
    • $\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}$;
    • $\lambda\colon (a,b)\in\Q\times\Q\mapsto a/(|b|+1)\in\Q$.

15 — 8/5

Verifica di alcuni esercizi di carattere teorico (sono risultati da conoscere) dalla lezione precedente: numeri 3 e 4.

Un elemento che sia neutro (o neutro a sinistra, o a destra) in una struttura algebrica ed appartenga ad una parte chiusa di essa, è neutro (o neutro a sinistra, o a destra) anche nella corrispondente struttura indotta. Notazione per denotare monoidi con la specificazione dell'elemento neutro. Sottosemigruppi e sottomonoidi. Esempi di parti chiuse di un monoide $M$ che, muniti dell'operazione indotta, non sono monoidi, sono sottomonoidi di $M$, sono monoidi ma non sottomonoidi di $M$.

Gruppi e gruppi abeliani (esempi: $(\Z,+)$; per ogni insieme $a$, $(\P(a),\ds)$; gruppi identici). Sottogruppi, esempi. Loro caratterizzazione: una parte non vuota $H$ di un gruppo ne è un sottogruppo se e solo se per ogni $x,y\in H$ il prodotto (in notazione moltiplicativa) $xy'$ appartiene ad $H$; qui $y'$ indica il simmetrico di $x$ nel gruppo (la condizione $xy'\in H$ può essere equivalentemente sostituita da $x'y\in H$).

Gli elementi simmetrizzabili di un monoide $M$ ne costituiscono un sottomonoide $\U(M)$, che è, a sua volta, un gruppo (il gruppo degli invertibili di $M$). Espressione del simmetrico di un prodotto in un monoide $M$ (in notazione moltiplicativa, per ogni $a,b\in\U(M)$ si ha $(ab)'=b'a'$, se gli apici indicano simmetrici). Descrizione del gruppo degli invertibili di alcuni monoidi, tra i quali $(\Z,\cdot)$, $(\P(a),\cup)$, $(\P(a),\cap)$. Il gruppo simmetrico $\Sym(a)=\U(T(a))$ su un insieme $a$. Questo gruppo è abeliano se e solo se $|a|\le 2$.

In una struttura algebrica con una operazione binaria: traslazioni destra e sinistra determinate da un elemento. 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 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. Nei gruppi tutti gli elementi sono cancellabili. In un semigruppo finito la presenza di un elemento cancellabile a sinistra implica la presenza di un elemento neutro a sinistra. (questi contenuti sono disponibili in una nota sulla cancellabilità).

Tavola di Cayley di un'operazione binaria. Visualizzazione di proprietà in una tavola di Cayley: commutatività, eventuali elementi neutri sinistri o destri (e quindi neutro); eventuali simmetrizzabili e loro simmetrici (anche sinistri o destri); cancellabilità (anche a sinistra o destra). Qualche esempio. Le tavole di Cayley dei gruppi di cardinalità $2$ o $3$.

Esercizi proposti:

1. Determinare il gruppo degli invertibili dei monoidi $(\N,+,0)$ e $(\P(\N),\cup, \vuoto)$.
2. Determinare gli elementi cancellabili nel monoide delle parole su un prefissato alfabeto.
3. Posto $S=\Z\times\Z$, studiare le strutture algebriche $(S,*)$, $(S,\bullet)$ e $(S,\diamond)$ (le operazioni sono definite avanti), stabilendo di che tipo di strutture si tratta, tra quelle già introdotte (un semigruppo?, un monoide?, un gruppo?; commutativo o no?), se (e quali) elementi neutri a destra, a sinistra, neutri hanno, gli elementi cancellabili (anche solo a destra o a sinistra) e, nel caso la domanda abbia senso, quali siano i loro elementi simmetrizzabili (anche solo a destra o a sinistra), identificandone i simmetrici.
   • $*\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto(a+b,\alpha\beta)\in S$
   • $\bullet\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+b,\beta)\in S$
   • $\diamond\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+\alpha b,\alpha\beta)\in S$.
   In ciascuna di queste strutture si stablisca poi quali tra $\Z\times\N$ e $\N\times\Z$ costituiscano parti chiuse (o, eventualmente, sottomonoidi) e, per quelle che lo sono, si ripeta l'esercizio per le strutture indotte su esse.
4. Decidere se l'insieme delle parti finite di $\N$ costituisce un sottogruppo di $(\P(\N),\ds)$, un sottomonoide di $(\P(\N),\cup)$, un sottomonoide di $(\P(\N),\cap)$.
5. Verificare che per ogni intero $n$, l'insieme dei multipli di $n$ costituisce un sottogruppo di $(\Z,+)$.
6. Siano $a$ un insieme e $x$ un suo elemento. Provare che $\set{\alpha\in\Sym(a)\mid \alpha(x)=x}$ costituisce un sottogruppo di $(\Sym(a),\circ)$.
7. Determinare gli elementi cancellabili a destra o a sinistra rispetto alle operazioni proposte nell'ultimo esercizio della lezione scorsa.
8. Per l'insieme $a=\set{0,1}$, scrivere le tavole di Cayley di $(\P(a),\cup)$, $(\P(a),\cap)$, $(\P(a),\ds)$, $(\P(a),\setminus)$.
9. Siano $a=\set{1,2,3,4}$ e $\sigma$ l'applicazione di $a$ in $a$ che manda 1 in 2, 2 in 3, 3 in 4 e 4 in 1. Dopo aver verificato che $\sigma^4(=\sigma\circ\sigma\circ\sigma\circ\sigma)$ coincide con $\id_a$ e di conseguenza che $\sigma$ è biettiva e $\Sigma:=\set{\id_a,\sigma,\sigma^2,\sigma^3}$ costituisce un sottogruppo di $\Sym(a)$, scrivere la tavola di Cayley di $(\Sigma,\circ)$. Confrontare questa con la tavola di Cayley di $(\P(a),\ds)$ per un insieme $a$ costituito da due elementi.
10. Sia $S=\set{t,a,b}$ un insieme di tre elementi e si consideri in $S$ l'operazione $*$ definita da questa tavola di Cayley:

    	$t$	$a$	$b$
    $t$	$t$	$a$	$b$
    $a$	$a$	$t$	$a$
    $b$	$b$	$b$	$b$

    Dopo aver verificato che $t$ è neutro in $(S,*)$ ed aver determinato i simmetrici destri e sinistri degli elementi di $S$, senza fare ulteriori calcoli si decida se $*$ è associativa.

16 — 12/5

Molti esercizi sulle operazioni binarie e le strutture con una operazione binaria (verifiche di commutatività, associatività, esistenza o meno di neutri, simmetrici, cancellabili, anche solo a sinistra o destra).

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

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

Invarianza delle proprietà algebriche (inclusa la cancellabilità) per isomorfismi. Centralità della nozione di isomorfismo in algebra. Determinazione del tipo di una struttura algebrica (essere un semigruppo, un monoide, un gruppo etc.) attraverso l'individuazione di un isomorfismo. Ad esempio, se $\alpha$ è l'operazione definita nell' esercizio 12 della lezione nr. 14, $(\Z,\alpha)$ è un gruppo abeliano perché isomorfo a $(\Z,+)$ tramite l'isomorfismo $n\in(\Z,+)\mapsto n-1\in(\Z,*)$.

Isomorfismi e tavole di Cayley.

Esercizi proposti:

1. Verificare che le seguenti applicazioni sono omomorfismi: $n\in(\Z,\cdot)\mapsto |n|\in (\N,\cdot)$, $n\in(\Z,+)\mapsto -n\in (\Z,+)$; più in generale, se $G$ è un gruppo abeliano l'applicazione $G\to G$ che ad ogni elemento associa il simmetrico è un isomorfismo (e se $G$ non è abeliano?). Cosa sappiamo dire su $n\in(\Z,\cdot)\mapsto -n\in (\Z,\cdot)$? E su $x\in\P(\Z)\mapsto x\ds\N\in\P(\N)$?
2. Sia $*$ l'operazione binaria in $S:=\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+\alpha b,\alpha\beta)$ per ogni $a,b,\alpha,\beta\in\Z$, già discussa in un esercizio della lezione 15. Per ciascuna delle applicazioni $n\in\Z\mapsto (n,1)\in S$ e $n\in\Z\mapsto (0,n)\in S$ decidere se di tratta di un omomorfismo da $(\Z,+)$, o da $(\Z,\cdot)$, a $(S,*)$. L'applicazione $(a,\alpha)\in S\mapsto \alpha\in\Z$ è un omomorfismo da $(S,*)$ a $(\Z,+)$? Ed a $(\Z,\cdot)$?
3. A lezione non abbiamo verificato che gli omomorfismi suriettivi conservano l'associatività. Farlo.
4. Verificare che, per ogni insieme $a$ l'applicazione $x\in \P(a)\mapsto a\setminus x\in \P(a)$ è un isomorfismo da $(\P(a),\cap)$ a $(\P(a),\cup)$ (e viceversa) ed usare questa per spiegarsi le coincidenze tra le proprietà algebriche dell'intersezione e dell'unione binaria.
5. Sia $(S,*)$ un semigruppo. L'applicazione $a\in S\mapsto \sigma_a \in T(S)$ è un omomorfismo? E se $(S,*)$ non è un semigruppo? ($T(S)$ è il monoide delle trasformazioni di $S$, $\sigma_a$ la traslazione sinistra definita da $a$ in $(S,*)$.)
6. Utilizzando le considerazioni fatte sulle tavole di Cayley dei gruppi di cardinalità 2 o 3 fatte nella lezione 15, provare che due qualsiasi gruppi, entrambi di cardinalità 2 o entrambi di cardinalità 3, sono necessariamente isomorfi tra loro. Scrivere esplicitamente un isomorfismo da $\mathcal (U(\Z), \cdot)$ a $(\P(\set 0),\ds)$. Scrivere la tavola di Cayley del gruppo degli invertibili del monoide $(\Z\times\Z,*)$ discusso nella lezione di oggi, in cui $*$ è definito dall'essere $(a,α)*(b,β)=(ab,αβ)$ per ogni $a,b,α,β\in\Z$ e, utilizzando quanto (sperabilmente) fatto negli esercizi 8 e 9 della lezione scorsa, provare che $\U(\Z\times\Z,*)$ è isomorfo $\P(\set{0,1},\ds)$ ma non al gruppo $(\Sigma,\circ)$ dell'esercizio 9 (dunque, esistono gruppi di cardinalità 4 non isomorfi tra loro).
7. Vero o falso? Supponendo che esista un omomorfismo suriettivo da una struttura $(S,*)$ ad una struttura $(T,\bullet)$, dove $*$ e $\bullet$ sono operazioni binarie, …
   • se $(S,*)$ è un semigruppo, $(T,\bullet)$ è un semigruppo;
   • se $(T,\bullet)$ è un semigruppo, $(S,*)$ è un semigruppo;
   • se $(S,*)$ è un monoide, $(T,\bullet)$ è un monoide;
   • se $(T,\bullet)$ è un monoide, $(S,*)$ è un monoide;
   • se $(S,*)$ è un gruppo, $(T,\bullet)$ è un gruppo;
   • se $(T,\bullet)$ è un gruppo, $(S,*)$ è un gruppo.

17 — 15/5

Ulteriori esercizi sulle operazioni binarie.

Osservazione: in generale, gli omomorfismi iniettivi possono non conservare le usuali proprietà algebriche.

Altri (importanti) esempi di isomorfismi ed osservazioni a riguardo: la funzione esponenziale come isomorfismo dal gruppo additivo dei numeri reali a quello moltiplicativo dei reali positivi; per un arbitrario insieme $a$, l'applicazione complemento come isomorfismo da $(\P(a),\cup)$ o $(\P(a),\cap)$ e viceversa.

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 di elementi invertibili, in particolare per 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$. In notazione additiva queste formule diventano, con le stesse quantificazioni, $(n+m)x=nx+mx$ e $(nm)x=m(nx)$. Potenze (o multipli) secondo interi di uno stesso elemento di un qualsiasi semigruppo commutano sempre tra loro.

In una struttura algebrica, l'intersezione di un qualsiasi insieme non vuoto di parti chiuse è una parte chiusa. La parte chiusa generata da una parte. Sottomonoidi (in monoidi) e sottogruppi (in gruppi) generati da parti. Descrizione delle parti chiuse, dei sottomonoidi e dei sottogruppi generati da un singleton; gruppi ciclici (esempio: $(\Z,+)$ è ciclico, generato da $\set 1$).

Esercizi proposti:

1. Per ogni gruppo $G$ ed ogni $a\in G$, l'applicazione $n\in(\Z,+)\mapsto a^n\in G$ è un omomorfismo.
2. Nel gruppo $(\Z,+)$, determinare le parti chiuse generate da $\set{-1}$ e da $\set{1,-1}$, la parte chiusa, il sottomonoide ed il sottogruppo generati da $\set{-2,2}$ ed il sottogruppo generato da $\set{8,14}$.
3. In $(\P(\N),\cup,\vuoto)$, determinare il sottomonoide generato da $\P_1(\N)$ (l'insieme dei singleton dei numeri naturali).
4. Nel gruppo $(\P(\Z),\ds)$, determinare la parte chiusa, il sottomonoide ed il sottogruppo generati da $\set{\N}$ e quelli generati da $\set{\N,\set 1}$.
5. Dimostrare che, per ogni insieme $a$ e per ogni $T\sseq \P(a)\setminus\set\vuoto$ la parte chiusa, il sottomonoide ed il sottogruppo generati da $T$ in $(\P(a),\ds)$ coincidono.

18 — 19/5

Anelli. Definizione ed esempi (tra questi, gli anelli su $\Z$, $2\Z$, $\Q$, $\R$ con le usuali operazioni di addizione e moltiplicazione, l'anello delle parti di un insieme, con le operazioni di differenza simmetrica ed intersezione); anelli commutativi, anelli unitari. Omomorfismi di anelli ed omomorfiami di anelli unitari. L'anello prodotto diretto tra due anelli. Sottoanelli, sottoanelli unitari; omomorfismi di anelli, omomorfismi di anelli unitari (anche, in parallelo: di semigruppi e di monoidi). Terminologia e notazioni per anelli: lo zero $0_R$ e (se esiste) l'unità $1_R$ di un anello $R$. Opposti (cioè simmetrici rispetto all'operazione additiva) e inversi (cioè eventuali simmetrici rispetto all'operazione moltiplicativa), differenza: per ogni $a,b\in R$, $a-b=a+(-b)$.

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

Legge di annullamento del prodotto con esempi di anelli in cui essa non vale. Divisori dello zero sinistri, destri, divisori dello zero negli anelli (si vedano le note sulla cancellabilità). Teorema: i divisori sinistri (risp. destri) dello zero sono precisamente gli elementi non cancellabili a sinistra (risp. a destra), i divisori dello zero sono precisamente gli elementi non cancellabili. Anelli integri, domini di integrità. In un anello con più di un elemento, lo zero è sicuramente un divisore dello zero, quindi non invertibile. Corpi e campi (i primi sono integri, i secondi sono domini di integrità. Il viceversa non vale in generale). Esempi di campi: $\R$, $\Q$, l'insieme delle parti di un singleton.

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

Esercizi proposti:

1. Sia $*$ l'operazione binaria definita in $\Z$ ponendo, per ogni $a,b\in\Z$, $a*b=b$. Verificare che la struttura $(\Z,+,*)$ (dove $+$ è l'addizione usuale tra interi) non è un anello, benché $(\Z,+)$ sia un gruppo abeliano, $*$ sia associativa e distributiva a sinistra rispetto a $+$.
2. Verificare in dettaglio quanto accennato a lezione: se $R$ è un anello unitario, per ogni $n\in\Z$ e $a\in R$ si ha $(n1_R)a=na$.
3. Verificare in dettaglio quanto affermato a lezione a proposito della nozione di prodotto diretto di anelli: che è un anello, che è commutativo, o unitario, se e solo se i due anelli che lo definiscono hanno la stessa proprietà.
4. Siano $R$ ed $S$ due anelli e sia $P$ il loro prodotto diretto. Allora l'applicazione $(r,s)\in P\mapsto s\in S$ è un omomorfismo suriettivo di anelli.
5. Nell'anello prodotto diretto $\Z\times\Z$, verificare che $\set{0}\times \Z$ è un sottoanello. È anche un sottoanello unitario? Che tipo di anello è $\set{0}\times \Z$ (munito delle operazioni indotte da quelle di $\Z\times\Z$)? Per caso è isomorfo ad un anello che già conosciamo? Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
6. Nell'anello prodotto diretto $\Z\times\Z$, si decida quali tra questi elementi sono divisori dello zero, quali cancellabili e quali invertibili: $(1,1)$, $(7,-3)$, $(0,2)$ $(1,-1)$. Fatto questo, provare a descrivere l'insieme dei divisori dello zero in $\Z\times\Z$.
7. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $(\P(\N)\ds,\cap)$? Come anello, è unitario?
8. Sia $a$ un elemento invertibile in un anello unitario $R$. È possibile che $a$ sia un divisore dello zero in $R$?
9. Sia $T=\Z\times\Z\times\Z$ l'insieme delle terne ordinate di numeri interi. In $T$ definiamo le operazioni binarie $\oplus$ e $*$ ponendo, per ogni $a,b,c$, $u,v,w\in\Z$, $(a,b,c)\oplus(u,v,w)=(a+u,b+v,c+w)$, e $(a,b,c)*(u,v,w)=(au,av+bw,cw)$. Verificare che $(T,\oplus,*)$ è un anello, decidere se è commutativo e se è unitario. Stabilire anche se $(1,1,0)$ è un divisore dello zero (destro? sinistro?) in $R$. Nel caso in cui $R$ sia unitario, determinarne gli elementi invertibili.
10. Provare (ammesso che sia vero) quanto segue: se $a$ e $b$ sono elementi di un anello $R$, in $R$ si ha $(a+b)^2=a^2+2ab+b^2$ se e solo se $ab=ba$.

19 — 22/5

Gli anelli integri finiti con più di un elemento sono corpi (anzi, a titolo di notizia, campi).

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

Nozioni di caratteristica di un anello e periodo di un elemento in un gruppo.

In un anello, un elemento idempotente che non sia neutro a destra è certamente divisore dello zero a destra.

La relazione $|_S$ di divisibilità in un semigruppo commutativo $S$: è sempre transitiva, è riflessiva se $S$ è un monoide. In un monoide commutativo, gli elementi invertibili sono precisamente quelli che dividono ogni elemento del monoide. In $(\Z,\cdot)$ ogni elemento divide $0$. Nei gruppi commutativi, la divisibilità è la relazione universale. Divisibilità in anelli commutativi: un elemento che divida due elementi $a$ e $b$ divide tutte le loro combinazioni lineari (cioè gli elementi della forma $au+bv$ per elementi $u$ e $v$ dell'anello).

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

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

Se $\sigma$ è una congruenza in una struttura di sostegno $S$, la proiezione canonica $a\in S\mapsto [a]_\sim \in S/{\sigma}$ è un omomorfismo suriettivo (dalla struttura assegnata alla struttura quoziente), quindi conserva: commutatività, associatività, esistenza di neutri e simmetrici (anche solo a destra o sinistra), distributività. I quozienti di semigruppi, monoidi, gruppi (eventualmente abeliani), anelli (eventualmente commutativi o unitari) sono quindi strutture dello stesso tipo.

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

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

Descrizione esplicita degli elementi degli anelli $\Z_m$: per ogni $m,a\in \Z$ si ha $[a]_m=a+m\Z:=\set{a+mk\mid k\in \Z}$.

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

Esercizi proposti:

1. Identificare la relazione di divisibilità nei monoidi $(\N,+)$, $(\P(\N),\cap)$, $(\P(\N),\cup)$, $(\P(\N),\ds)$ (si chiede, ad esempio, di chiarire sotto quali condizioni, se $a$ e $b$ sono numeri naturali, $a$ divide $b$ in $(\N,+)$; similmente per gli altri monoidi).
2. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ 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. Nel monoide delle parole su un alfabeto, la relazione "avere la prima lettera in comune" (dove si intende che la parola vuota è in relazione solo con sé stessa) è una congruenza?
6. Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è compatibile con $*$. Se possibile, spiegare perché questo esercizio generalizza i precedenti.
7. Elencare gli elementi di $[40]_6\cap\set{n\in\Z\mid -10\le n\le 10}$.
8. Elencare gli interi $m$ tali che $1\equiv_m -9$ e gli interi $h$ tali che $1+8h\equiv_h -9$.
9. Provare che se due interi sono congrui modulo un intero $m$, essi sono congrui anche modulo ciascun divisore di $m$.

20 — 26/5

Per ogni $a,m\in\Z$, se $m\ne 0$ esistono interi positivi in $[a]_m$. L'operazione parziale $\modbin$ (o $\%$): per ogni $a\in\Z$ e $m\in\Z\setminus\set 0$, $a\modbin m$ è definito come il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$. Descrizione esplicita dei quozienti di $\Z$: per ogni $m\in\Z\setminus\set0$, $\Z_m=\set{[0]_m, [1]_m, [2]_m, \dots, [|m|-1]_m}$. Gli elementi di $\Z_m$ appena elencati sono a due a due distinti (vale a dire: se $i$ e $j$ sono numeri naturali minori di $|m|$ e $i\ne j$, allora $i\not\equiv_m j$), quindi $|\Z_m|=|m|$. Se $m$ è un intero positivo, $(\Z_m,+,\cdot)$ costituisce un esempio di anello commutativo unitario di cardinalità (e caratteristica) $m$, non necessariamente integro; il suo gruppo additivo $(\Z_m,+)$ è ciclico.

Divisione con resto (o divisione aritmetica) tra numeri interi (il secondo dei quali non nullo). Esistenza ed unicità della coppia quoziente-resto. Terminologia: classi di resto.

Metodi dell'aritmetica modulare, con esempi di calcoli rapidi (ad esempio, di potenze); tra questi: alcuni criteri di divisibilità (per 3, 9, 2, 5, 4, 11).

Elementi periodici nei gruppi. Se un elemento $x$ di un gruppo ha periodo un numero intero positivo $m$, allora, per ogni $a,b\in\Z$ si ha $x^a=x^b\iff a\equiv_m b$; di conseguenza $m$ è anche la cardinalità del sottogruppo generato da $\set x$ . Senza dimostrazione: se $G$ è un gruppo finito di cardinalità $n$ e con elemento neutro $1_G$, per ogni $x\in G$ si ha $x^n=1_G$, quindi il periodo di $x$ divide $n$.

Massimi comuni divisori (MCD) e minimi comuni multipli (mcm) di una parte di un semigruppo commutativo. Laddove esistano, costituiscono una classe di elementi associati.

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

Estensione dell'algoritmo euclideo e teorema di Bézout (la dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, non quella nel libro di testo): se $a$ e $b$ sono numeri interi e $d$ è un MCD tra essi,

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

Equazioni di primo grado in un quoziente proprio di $\Z$, ovvero equazioni congruenziali di primo grado ad una incognita: se $a$, $c$ ed $m$ sono interi, e $m\ne 0$, l'equazione congruenziale $ax\equiv_m c$ (in $\Z$) è un modo per esprimere l'equazione $[a]_m X= [c]_m$ in $\Z_m$. Equivalenza tra il problema di risolvere l'equazione congruenziale $ax\equiv_m c$ e quello di risolvere l'equazione diofantea $ax+my=c$. Criterio di esistenza di soluzioni per le equazioni congruenziali di questo tipo (è un'ulteriore versione del teorema di Bézout).

Esercizi proposti:

1. L'anello $(\Z_{30},+,\cdot)$ non è un dominio di integrità. Trovare in esso qualche divisore non nullo dello zero.
2. Provare che, invece, $(\Z_3,+,\cdot)$ è un campo.
3. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_4$. In questo anello $[2]_4$ è cancellabile?
4. Calcolare: $15\modbin 6$, $(-15)\modbin 6$, $15\modbin -6$, $(-15)\modbin -6$,
5. Vero o falso? $\Z_5=\set{[12]_5,[9]_5,[-12]_5,[100]_5,[-4]_5}$
6. Sono le 15. Che ora sarà tra $16\cdot 9\cdot 7^2 + 5^{40}-3^{10}$ ore?
7. Calcolare (a mente, ci mancherebbe!) $72543618991175\modbin 9$ e $72543618991175\modbin 3$, poi $(626\cdot 3125)\modbin 3$ ed infine $78598!\modbin 9743$.
8. Nel granducato di Strampalia non circolano monete e la valuta locale, il tallero strampalese, viene emesso solo in due tagli: la banconota da 15 talleri e quella da 33 talleri. Usando il teorema di Bézout, spiegare quali pagamenti in talleri strampalesi possono essere effettuati in contanti (è ammessa la possibilità di pagare ricevendo un resto).
9. Utilizzando l'algoritmo euclideo esteso, trovare una coppia soluzione dell'equazione diofantea $62x-27y=8$.
10. Svolgere gli esercizi 5 e 9 da Tautologie, insiemi, aritmetica (la scrittura $ax\equiv c\pmod m$ sta per $ax\equiv_m c$).

21 — 29/5

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

Divisori banali ed elementi irriducibili in monoidi commutativi; numeri interi primi. Il teorema fondamentale dell'aritmetica: ogni numero intero diverso da $0$, $1$ e $-1$ è prodotto di primi, in modo essenzialmente unico. Conseguenza: determinazione dei divisori di un intero e di MCD e mcm di insiemi di interi di cui siano note fattorizzazioni in primi. Osservazione: se $a,b\in\Z$ e $d$ e $m$ sono MCD e mcm di $\set{a,b}$ allora $|ab|=|dm|$.

Conseguenze ulteriori: determinazione degli elementi invertibili nei quozienti di $\Z$. Verifica diretta del fatto (già noto) che, per ogni intero $m\ne 0$, tutti gli elementi non invertibili in $\Z_m$ sono divisori dello zero. Sempre nel caso $m\ne 0$, sono equivalenti: (1) $\Z_m$ è un campo; (2) $\Z_m$ è un dominio di integrità non nullo; (3) $m$ è primo. Cenni alla funzione di Eulero ed al teorema di Fermat-Eulero.

Metodi per la risoluzione dell'equazione congruenziale $(*)$: $ax\equiv_m c$ (dove $a,c,m\in\Z$ e $m\ne 0$; d'ora in avanti queste notazioni restano fissate). Prima osservazione: l'insieme delle soluzioni è una unione di classi di resto modulo $m$. È precisamente una classe di resto modulo $m$ se e solo se $a$ ed $m$ sono coprimi (in questo caso diciamo che $(*)$ è ridotta).

“Pseudodivisione euclidea” e suo utilizzo per la velocizzazione dell'algoritmo euclideo (per ogni $a,b\in\Z$, se $b\ne 0$ esistono $q,r\in\Z$ tali che $a=bq+r$ e $|r|\le|b/2|$).

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

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

La (ii) segue dal fatto che, per ogni $a,b,m,k\in\Z$ se $k\ne0$ si ha $a\equiv_m b$ se e solo se $ak\equiv_{mk} bk$. Come ovvio, le osservazioni (ii) e (iii) vengono usate per dividere gli interi $a$ e $c$ (e, nel caso di (ii) anche $m$) per loro divisori comuni.

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

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

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

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

Esercizi proposti:

1. Determinare, in $\N$ e poi in $\Z$ i divisori di $3^5\cdot 5^4\cdot 23^3$ ed il loro numero. Ripetere l'esercizio per $3^5\cdot 5^4\cdot 22^3$.
2. Completare nei dettagli la dimostrazione di quanto affermato a proposto della “pseudodivisione euclidea”: esistenza (per ogni $a,b\in\Z$, se $b\ne 0$ esistono $q,r\in\Z$ tali che $a=bq+r$ e $|r|\le|b/2|$). Osservare che la coppia non è necessariamente unica (porre $b=2$ ed $a$ un intero dispari).
3. Trovare le soluzioni dell'equazione congruenziale $87x+32\equiv_{100} x+4$.
4. Usando l'algoritmo euclideo esteso, trovare tutte le soluzioni delle equazioni diofantee $14x+6y=1$,  $14x+6y=4$  e  $140x+60y=20$.
5. Svolgere gli esercizi da 6 a 12 di Tautologie, insiemi, aritmetica (la scrittura $ax\equiv c\pmod m$ sta per $ax\equiv_m c$).
6. Dando per nota l'uguaglianza $3=117\cdot 13+66(-23)$, trovare gli insiemi delle soluzioni delle equazioni congruenziali $66 x\equiv_{117}10$, $660 x\equiv_{1170}90$ e $1170 x\equiv_{660}90$.
7. 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$.
8. Autoassegnarsi e risolvere un gran numero di equazioni congruenziali a caso.
9. 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$.
10. 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.
11. Delle equazioni congruenziali che seguono, dire quali hanno lo stesso insieme di soluzioni di $18x\equiv_{21}9$ (non calcolare le soluzioni):
    $6x\equiv_{21}3$, $6x\equiv_{7}3$, $2x\equiv_{7}1$, $x\equiv_{21}4x+9$, $60x\equiv_{7}30$, $60x\equiv_{70}30$, $54x\equiv_{21}27$, $54x\equiv_{63}27$, $-3x\equiv_{21}9$, $3x\equiv_{21}-9$, $x\equiv_{7}-3$, $-3x\equiv_{21}28$.

22 — 5/6

Relazioni (binarie) antiriflessive e antisimmetriche. Relazioni d'ordine (largo) e relazioni d'ordine stretto. Esempi. Osservazione: le relazioni di ordine stretto sono antisimmetriche. La relazione duale (cioè capovolta) ad una relazione binaria $\rho$ è d'ordine se e solo se $\rho$ è d'ordine, d'ordine stretto se e solo se $\rho$ è d'ordine stretto.

Notazione: fissato un insieme $a$, $\OL(a)$ e $\OS(a)$ denotano gli insiemi delle relazioni di ordine largo e di ordine stretto nell'insieme $a$. Biezioni (l'una inversa dell'altra) $\rho\in\OL(a)\mapsto\rho_{\ne}\in\OS(a)$ e $\sigma\in \OS(a)\mapsto\sigma_{=}\in\OL(a)$, dove $\rho_{\ne}$ e $\sigma_{=}$ sono descritte da: $(\forall x,y\in a)$$(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$ e $(\forall x,y\in a)$$(x\mathrel{\sigma_{=}}y \iff (x\mathrel\sigma y \lor x=y))$.

Insiemi ordinati. Esempi essenziali (relazione d'ordine usuale in $\R$ e nei suoi sottoinsiemi, relazione di inclusione e relazione di uguaglianza in qualsiasi insieme, relazione di divisibilità in $\N$ (ma non in $\Z$). Relazione d'ordine (stretto o largo) indotta su una parte; sottoinsiemi ordinati. Confrontabilità ed insiemi totalmente ordinati. Principio di dualità per insiemi ordinati.

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

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

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

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

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

Esercizi proposti:

1. Completare gli esercizi 1 e 2 da relazioni binarie (per "ordinamento" si intende "relazione d'ordine stretto o largo") e, dallo stesso file, svolgere l'esercizio 6 sino alla prima occorrenza della parola 'reticolo' (esclusa).
2. Verificare in dettaglio che la relazione binaria $\rho$ sull'insieme $a=\R\cup\set h$ (dove $h\notin\R$) discussa a lezione e definita da $\forall x,y\in a$$(x\mathrel\rho y\iff{}$$ ((x,y\in\R \land x\le y) \lor (x=y=h))$ è effettivamente d'ordine.
3. Siano $\rho$ e $\sigma$ le relazioni binarie in $\Z$ definite ponendo, per ogni $a,b\in\Z$: $a\mathrel\rho b$ se e solo se $a^2+2\le b^2+2$ e $a\mathrel\sigma b$ se e solo se $a=b$ oppure $a^2+a+1\lt b^2+b+1$. Di ciascuna delle due decidere se è una relazione d'ordine.
4. La relazione binaria $\tau$ definita in $\N$ ponendo, per ogni $a,b\in\N$, $a\mathrel\tau b$ se e solo se $b-a\in\N\setminus\set 1$ è d'ordine?
5. Siano $A=\set{0,1,2,3}$ e $\rho$ la relazione binaria definita in $\P(A)$ ponendo, per ogni $x,y\in\P(A)$, $x\mathrel\rho y$ se e solo se $x=y \lor (x\cap\set{0,1}\subset y\cap\set{0,1})$. Provare che $\rho$ è una relazione d'ordine, decidere se è totale e determinare in $(\P(A),\rho)$ gli (eventuali) elementi minimo, massimo, minimali e massimali.
6. Costruire un esempio di insieme ordinato con esattamente tre elementi minimali.
7. Esiste in $\P(\N)$ una parte infinita che sia totalmente ordinata per inclusione (cioè dall'ordinamento indotto dall'inclusione in $\P(\N)$)?
8. 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$.
9. Disegnare un diagramma di Hasse dell'insieme $\set{n\in\N\mid n\lt 10}$ ordinato per divisibilità in $\N$.
10. Per ogni $n\in\set{8,12,18,30,31,2^{10}}$ disegnare un diagramma di Hasse dell'insieme $D_n$ dei divisori (in $(\N,\cdot)$) di $n$, ordinato per divisibilità in $\N$. Trovare, tra questi insiemi ordinati, quali sono isomorfi tra loro.

23 — 9/6

Minoranti e (dualmente) maggioranti di una parte $T$ di un insieme ordinato $(S,\rho)$. Notazione: indichiamo gli insiemi da essi formati come $T^{\downarrow_{(S,\rho)}}$ e $T^{\uparrow_{(S,\rho)}}$ rispettivamente. Alcuni esempi; tra questi: se $T=\vuoto$, $T^{\downarrow_{(S,\rho)}}=T^{\uparrow_{(S,\rho)}}= S$; se $X$ è un insieme di numeri naturali, i minoranti ed i maggioranti di $X$ in $(\N,|)$ sono, rispettivamente, gli insiemi dei divisori comuni e dei multipli comuni agli 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$.

Estremi inferiori ed estremi superiori. Esempi. Per ogni parte $X$ di un insieme ordinato $(S,\rho)$ ed ogni $a\in X$, sono equivalenti: (1) $a=\min (X,\rho)$, (2) $a\in X^{\downarrow_{(S,\rho)}}$, (3) $a=\inf_{(S,\rho)}(X)$. Definizione di reticolo e di reticolo completo. Il duale di un reticolo è necessariamente un reticolo; principio di dualità per reticoli. Sono reticoli tutti gli insiemi totalmente ordinati, sono reticoli completi $(\P(S),\sseq)$ (per qualsiasi insieme $S$) e $(\N,\mid)$.

Un reticolo non può avere più di un elemento minimale o più di un elemento massimale, per motivi ovvi. Un motivo meno ovvio: un elemento minimale (risp. massimale) in un reticolo è necessariamente il minimo (risp. massimo) del reticolo.

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

Lemma: se $(S,\rho)$ è un insieme ordinato e $X$ ne è una parte con estremo inferiore $a$, allora $X^\downarrow=\set a^\downarrow$; se poi $b\in S$ si ha $(X\cup\set b)^\downarrow=\set{a,b}^\downarrow$, quindi le proprietà di essere, in $(S,\rho)$, estremo inferiore di $X\cup\set b$ o di $\set{a,b}$ sono equivalenti (vale ovviamente anche l'enunciato duale). Conseguenza: tutte le parti finite e non vuote di un (arbitrario) reticolo hanno estremo inferiore ed estremo superiore, dunque: i reticoli finiti non vuoti sono completi.

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

Se $(L,\rho)$ è un reticolo, con operazioni reticolari $\lor$ (estremo superiore) e $\land$ (estremo inferiore), e $a\in L$, allora $a$ è neutro rispetto a $\lor$ se e solo se $a=\min(L,\rho)$, è neutro rispetto a $\land$ se e solo se $a=\max(L,\rho)$.

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

Sottoreticoli (cioè parti di un reticolo chiuse rispetto alle operazioni reticolari). Esempi di sottoreticoli; lo sono. per ogni $x\in S$, i sottoinsiemi $\set x^\downarrow$ o $\set x^\uparrow$, quindi tutti gli intervalli chiusi. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

Complementi in un reticolo limitato; reticoli complementati (esempio: il reticolo delle parti di un insieme lo è; $(\N,|)$ non lo è; un insieme totalmente ordinato con più di due elementi non lo è). Esempi. In un reticolo (limitato) un elemento $a$ ha per complemento un elemento $b$ con cui è confrontabile se e solo se $a$ e $b$ sono il minimo ed il massimo del reticolo; inoltre il minimo è l'unico complemento del massimo e viceversa. Esempi di reticoli in cui un elemento ha più di un complemento. Reticolo trirettangolo ($M_3$) e reticolo pentagonale ($N_5$).

Reticoli distributivi. Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), gli insiemi totalmente ordinati. I sottoreticoli dei reticoli distributivi sono distributivi. Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; criterio di distributività di Birkhoff (dimostrata solo l'implicazione banale); esempi di applicazione.

Esercizi proposti:

1. Per arbitrarie parti $X$ e $Y$ di un insieme ordinato si ha $(X\cup Y)^{\downarrow}=X^{\downarrow}\cap Y^{\downarrow}$ e $(X\cup Y)^{\uparrow}=X^{\uparrow}\cap Y^{\uparrow}$. Inoltre, se $a=\inf(X)$ e $b=\inf(Y)$, allora $(X\cup Y)^\downarrow=\set{a,b}^\downarrow$ e le proprietà di essere estremo inferiore di $X\cup Y$ o di $\set{a,b}$ sono equivalenti. Verificare anche gli enunciati duali.
2. Degli insiemi ordinati discussi negli esercizi della lezione scorsa, decidere se sono o non sono reticoli e, se lo sono, se sono complementati e se sono distributivi.
3. Sia $x$ un elemento di un insieme ordinato $S$. Allora, in $S$, $x$ è minimale e e solo se $\set x^\downarrow= \set x$.
4. Trovare un isomorfismo di reticoli dall'insieme delle parti di $\set{0,1}$ all'insieme delle parti di $\set{3,4}$, ordinati per inclusione.
5. Provare che se due insiemi $a$ e $b$ sono equipotenti, i reticoli $(\P(a),\sseq)$ e $(\P(b),\sseq)$ sono isomorfi.
6. Verificare: se $a$ e $b$ sono parti di un insieme ordinato $(S,\rho)$, allora $(a\cap b)^{\downarrow_{(S,\rho)}}\supseteq a^{\downarrow_{(S,\rho)}}\cup b^{\downarrow_{(S,\rho)}}$ e $(a\cap b)^{\uparrow_{(S,\rho)}}\supseteq a^{\uparrow_{(S,\rho)}}\cup b^{\uparrow_{(S,\rho)}}$, dove le inclusioni possono essere strette.
7. Disegnare il diagramma di Hasse di un reticolo in cui esista un elemento con sei complementi.
8. 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.
9. Usando il teorema di Birkhoff, provare che tutti i reticoli con meno di quattro elementi sono distributivi.
10. Dimostrare in modo diretto (cioè senza usare il teorema di Birkhoff) che gli insiemi totalmente ordinati sono reticoli distributivi.

24 — 12/6

Per i contenuti di questa lezione e della precedente consiglio di far riferimento alle note sulle strutture booleane (appena aggiornate).

Esempi di applicazione del teorema di Birkhoff. Senza dimostrazione: in un qualsiasi reticolo la distributività anche di una sola delle due operazioni reticolari rispetto all'altra implica la distributività del reticolo.

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

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

Interpretazione delle funzioni caratteristiche come applicazioni a valori in $\Z_2$. Per ogni $n\in\N^*$, l'anello (booleano) $(\Z_2)^n$ delle $n$-ple di elementi di $\Z_2$, ovvero delle applicazioni da $S=\set{1,2,\dots,n}$ a $\Z_2$. Identificazione delle "stringhe di zeri e uno" di fissata lunghezza $n$ con gli elementi di $(\Z_2)^n$. L'applicazione che ad ogni parte di $S$ associa la sua funzione caratteristica è un isomorfismo di anelli (booleani) da $\P(S)$ a $(\Z_2)^n$. Interpretazione delle operazioni 'bit a bit' (che traducono i connettivi proposizionali $\xor$ e $\land$) alla luce di questo isomorfismo. Corrispondenti strutture di reticolo booleano e di algebra di Boole su $(\Z_2)^n$.

Ricordo la riunione dedicata alla discussione di argomenti a richiesta che si terrà, come da avviso nella pagina principale del corso, martedì 17, a partire dalle ore 9, nell'aula H3.

Esercizi proposti:

1. Provare che, nell'algebra di Boole delle parti di $\N$, l'insieme delle parti finite $\N$ costituisce un sottoreticolo non booleano, e che la sottoalgebra di Boole da esso generata (nel senso già introdotto in altri contesti: la minima sottoalgebra di Boole di $\P(\N)$ che lo contiene) è costituita dalle parti $x$ di $\N$ tali che uno tra $x$ e $\N\setminus x$ sia finito.
2. Verificare in dettaglio che un'applicazione tra i sostegni di due algebre di Boole è un isomorfismo di algebre di Boole se e solo se è un isomorfismo tra i corrispondenti reticoli (visti come insiemi ordinati).
3. Verificare che, in ogni algebra di Boole, per ogni coppia di elementi $a$ e $b$ vale $(a\lor b)=a\lor(a'\land b)$.
4. Spiegare perché un reticolo complementato di cardinalità 1000 non può essere distributivo.