5/3

Introduzione al corso: presentazione, informazioni generali, modalità di svolgimento, contenuto del corso, materiali didattici.

Cenni sulla logica proposizionale: nozioni informali di linguaggio, formula, proposizione (formula chiusa). Alcuni connettivi proposizionali (introdotti e descritti solo semanticamente): negazione, congiunzione, disgiunzione inclusiva, disgiunzione esclusiva (XOR), congiunzione negata (NAND), equivalenza (o bicondizionale), implicazione (o condizionale). Comparazione tra il loro uso e quello di espressioni analoghe del linguaggio naturale. Tabelle (o tavole) di verità, con esempi del loro uso in calcolo proposizionale. Tautologie, contraddizioni e forme contingenti. Alcuni esempi di tautologie: principî del terzo escluso e di non contraddizione, commutatività di congiunzione, disgiunzione, disgiunzione esclusiva, bicondizionale, associatività della congiunzione.

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

Esercizi proposti (sono tanti, svolgerne qualcuno):

1. Verificare che le seguenti forme proposizionali sono tautologie: $\bigl(\lnot(\lnot p)\bigr)\iff p$ (legge della doppia negazione); $\bigl(p\lor(q\lor r)\bigr)\iff \bigl((p\lor q)\lor r\bigr)$ (associatività della disgiunzione); $\bigl(p\lor(q\land r)\bigr)\iff \bigl((p\lor q)\land (p\lor r)\bigr)$ (distributività della disgiunzione rispetto alla congiunzione); $\bigl(p\iff q\bigr)\iff \bigl((p\implica q)\land (q\implica p)\bigr)$ (tautologia della doppia implicazione).
2. Verificare che per ciascuna scelta di $*$ tra $\land$ e $\lor$, la forma proposizionale $(p * p)\iff p$ è una tautologia (tautologie dell'idempotenza).
3. La forma proposizionale $(p\iff p)\iff p$ è una tautologia, una contraddizione oppure contingente? La forma proposizionale $(p\xor p)\iff p$ è una tautologia, una contraddizione oppure contingente? La forma proposizionale $p\xor p$ è una tautologia, una contraddizione oppure contingente?
4. Verificare che $(p\implica q)\iff(q\implica p)$ non è una tautologia (in altri termini: non vale la commutatività per il il connettivo di implicazione).
5. La forma proposizionale $\bigl(q\iff r\bigr)\iff \bigl((p\land q)\iff(p\land r)\bigr)$ è una tautologia?

7/3

Rapida discussione di alcuni esercizi; altre tautologie elementari, tra cui: distributività del connettivo di disgiunzione rispetto a quello di congiunzione.

Approfondimenti sul connettivo di implicazione. Anche se ho dimenticato di richiamarle in aula, se non in parte, gli studenti sono caldamente invitati a leggere con attenzione le osservazioni sul connettivo di implicazione contenute intorno a pagina 5 di Logica rudimentale.

Alcune tautologie fondamentali sull'implicazione: legge di contrapposizione, transitività dell'implicazione, implicazione come disgiunzione. Comparazione tra i connettivi di implicazione, di implicazione inversa, di equivalenza. Espressioni di questi connettivi nella lingua italiana.

Negazioni di proposizioni. Leggi di De Morgan. Negazione di un'implicazione. Esempi di traduzione dal linguaggio ordinario a quello (semi)formalizzato e viceversa.

Rinnovo l'invito a consultare, e magari avere con sé a lezione, Logica rudimentale, tavola dei connettivi binari, esempi di tautologie.

Esercizi proposti:

1. Svolgere quanti più è possibile tra gli esercizi A, B, C, D, E da Logica rudimentale. Suggerisco in particolare di prendere in esame gli esercizi in D.
2. Verificare (alcune tra) le tautologie in esempi di tautologie.
3. Se indichiamo con $p$ la formula “$3x\lt 4$” e con $q$ la formula “$y+1=z$”, quale connettivo proposizionale va inserito al posto di “$*$” in modo che la formula $p\mathop * q$ traduca (dal punto di vista della logica proposizionale) la frase “$3x\lt 4$, nonostante $y+1=z$”?
4. Vero o falso? $10=10^2 \implica \log_3 5\lt 0$.
5. Negare: “Se domani nevica e l'aereo è puntuale, o andremo a mare oppure 33 è un numero primo”.
6. Negare la forma proposizionale $(p\land q)\implica (r\lor s)$.

12/3

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

Quantificatori ristretti.

Il quantificatore $\exists!$, descritto dall'equivalenza $(\exists!x(\psi(x)))\iff(\exists x\forall y(\psi(y)\iff x=y))$ per ogni formula $\psi$.

Alcune altre regole della logica dei predicati. Frasi contenenti più quantificatori; esempi di frasi delle forme $\forall x\exists y(\dots)$ o $\forall x\exists y(\dots)$. Negazione di formule universali e di formule esistenziali (anche nel caso dei quantificatori ristretti).

Nozione di insieme. Il simbolo '$\in$' di appartenenza. Assioma di estensionalità. Unicità del'insieme vuoto. Cenni a problemi fondazionali: estensione di un predicato unario, antinomia di Russell. Cenno agli assiomi di separazione.

Negazioni di formule universali o esistenziali, anche nel caso dei quantificatori ristretti.

Esercizi proposti:

1. Svolgere quanti più è possibile tra gli esercizi H di Logica rudimentale.
2. Vero o falso?: $(\forall x\in\vuoto)(x\ne x)$.
3. Negare: Ogni cavallo bianco mangia carote.
4. Negare: “Ogni giorno che passa mi sento più stanco”.
5. Negare la formula: $\exists x (\forall y (\phi(x,y)))\implica \forall x (\exists y (\psi(x,y)))$.
6. Decidere se esiste e, nel caso, descrivere esplicitamente ciascuno degli insiemi $\set{x\mid x=\vuoto}$, $\set{x\mid \forall y (x=y)}$, $\set{x\mid x=x}$, $\set{x\mid \forall y (x\ne y)}$.

14/3

Discussione di alcuni esercizi; formule universali o esistenziali ristrette ad una condizione sempre falsa.

Inclusione tra insiemi: definizione di $\subseteq$ e di $\subset$. È importante distinguere bene tra appartenenza e inclusione. Ad esempio, per ogni $a$ si ha $\vuoto\subseteq a$, (in particolare, $\vuoto\subseteq\vuoto$), ma $\vuoto\notin\vuoto$. Si ha, più in generale (è una conseguenza di un assioma noto come assioma di fondazione): $\forall a(a\notin a)$. Il singleton di un insieme.

L'insieme delle parti di un insieme. Alcuni esempi. $\forall x(x\in\P(x))$

Comparazione tra i connettivi di equivalenza e implicazione, da una parte, e le relazioni di uguaglianza o inclusione tra insiemi dall'altra. Operazioni insiemistiche (unione ed intersezione binarie, complemento relativo, differenza simmetrica) e loro proprietà. Formule insiemistiche ricavate da tautologie (come nella sezione finale di Logica rudimentale, ma si veda anche Tautologie e identità insiemistiche). Abbiamo, tra l'altro discusso le formule di idempotenza, commutatività, associatività, distributività per le operazioni di unione, intersezione, differenza simmetrica, nonché le formule insiemistiche di De Morgan per operazioni binarie. Nel farlo abbiamo verificato le tautologie di associatività per il bicondizionale e per la disgiunzione esclusiva ($\xor$), e la distributività della congiunzione rispetto a $\xor$.

Diagrammi di Euler-Venn; alcuni esempi. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare formule insiemistiche. Utilizzo dei diagrammi di Euler-Venn per costruire controesempi.

Esercizi proposti:

1. Elencare gli elementi di $\P(\set{1,2})$ e quelli di $\P(\set{\vuoto,\set\vuoto})$.
2. Svolgere gli esercizi J4, J5 e J6 di Logica rudimentale.
3. Verificare tutte le formule in Tautologie e identità insiemistiche.
4. Descrivere esplicitamente gli insiemi $\set{x\mid \forall y (x\subseteq y)}$, $\set{x\mid \forall y (x\cap y=\vuoto)}$, $\set{x\mid \exists y (x\cup y=\vuoto)}$. $\set{x\mid \forall y (x\cup y=\vuoto)}$.
5. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\setminus(b\ds c)$ e $(a\ds b)\setminus c$.
6. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
7. Descrivere, per un arbitario insieme $a$, $a\ds a$, $a\ds\vuoto$ e, se $b$ è un sottoinsieme di $a$, $a\ds b$.
8. Decidere se vale la proprietà distributiva dell'unione rispetto alla differenza simmetrica, cioè se: $(\forall a,c,b)\,\big(a\cup(b\ds c)=(a\cup b)\ds(a\cup c)\big)$. Come si esprimerebbe questa proprietà in termini di calcolo proposizionale?
9. Dimostrare che, per ogni $A,B$, si ha $A\subseteq B\iff A\cap B=A\iff A\cup B=B$.
10. Dimostrare che, per ogni $A,B,C$, si ha $(A\subseteq B\land A\subseteq C)\iff A\subseteq B\cap C$.
11. Utilizzando diagrammi di Venn, stabilire se per ogni terna di insiemi $a,b,c$ si ha o meno una tra $a\setminus (b\setminus c)\subseteq (a\setminus b)\setminus c$ e $(a\setminus b)\setminus c\subseteq a\setminus (b\setminus c)$; se qualcuna delle due formule non è universalmente valida, trovare un controesempio esplicito. Ripetere l'esercizio confrontando tra loro $a\setminus (b\ds c)$ e $(a\setminus b)\ds(a\setminus c)$.

19/3

Discussione di alcuni esercizi.

Unione (unaria) di un insieme $A$: per definizione $\bigcup A=\set {x\mid (\exists a\in A)(x\in a)}$. Intersezione unaria di un insieme non vuoto. Unioni ed intersezioni di famiglie. Formule di De Morgan per unioni o intersezioni unarie: per ogni $S$ e ogni $A\ne \vuoto$, $S\setminus\bigcap A=\bigcup\set{S\setminus a\mid a\in A}$ e $S\setminus\bigcup A=\bigcap\set{S\setminus a\mid a\in A}$.

Coppie ordinate. Prodotto cartesiano tra due insiemi. Alcuni esempi. Terne ordinate.

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

Operazioni binarie (ovunque definite) in un insieme. Definizione, esempi e prime proprietà.

Esercizi proposti:

1. Fissato un insieme $A$, calcolare $\bigcap \P(A)$.
2. Verificare le formule infinitarie di distributività tra unione e intersezione: se $S$ ed $A$ sono insiemi e $A\ne\vuoto$, $S\cup\big(\bigcap A\big)=\bigcap\set{S\cup a\mid a\in A}$ e $S\cap\big(\bigcup A\big)=\bigcup\set{S\cap a\mid a\in A}$.
3. (non facilissimo) Provare che, per ogni $a,b,c,d$, si ha: $\set{\set{a},\set{a,b}}=\set{\set{c},\set{c,d}}$ se e solo se $a=c$ e $b=d$. (Si può dunque usare questa osservazione per dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. Questa è la cosiddetta definizione di Kuratowski della nozione di coppia ordinata).
4. Elencare gli elementi di $\set{1,3}\times \set{1,2,3}$.
5. Provare: $(\forall a,b)(a\times b=\vuoto\iff (a=\vuoto\lor b=\vuoto))$.
6. Siano $a$ e $b$ due insiemi. Si ha $a\times b=b\times a$ se e solo se …?
7. Indicato con $\R^+_0$ l'insieme dei numeri reali non negativi (cioè: $\R^+_0=\set{a\in\R\mid a\ge 0}$), si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • $\alpha\colon \R\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\beta\colon \R^+_0\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\gamma\colon \R^+_0\to \R^+_0$, di grafico $\set{(a,b)\in\R\times\R^+_0\mid a=b^2}$;

21/3

Operazioni binarie commutative ed associative; cenni ai teoremi di associatività e di commutatività. Nozione di struttura algebrica; semigruppi. Diversi esempi. Tavola di Cayley di un'operazione binaria

Elementi neutri a sinistra e a destra; elementi neutri. Unicità: se, in una assegnata struttura, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura. Semigruppi e monoidi. Diversi esempi, tra i quali semigruppi con più di un elemento neutro a destra. Il monoide (in generale non commutativo) delle parole su un alfabeto.

Nozione di operazione opposta e dualità destra/sinistra per operazioni binarie.

Simmetrici destri e sinistri; simmetrici. Unicità dei simmetrici nei monoidi: se, per un elemento $x$ di un assegnato monoide $S$, $s$ è un simmetrico sinistro e $d$ è un simmetrico destro di $x$, allora $s=d$, quindi $s$ è l'unico simmetrico di $x$, l'unico simmetrico sinistro di $x$ e l'unico simmetrico destro di $x$ in $S$. Osservazione banale: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di se stesso. Elementi simmetrizzabili. Terminologia: uso di "inverso" (in notazione moltiplicativa) e di "opposto" (in notazione additiva) come sinonimi di "simmetrico".

Gruppi. Tra gli esempi, il gruppo $(\P(A),\ds)$ per un arbitrario insieme $A$.

Esercizi proposti:

1. Posto $A=\set{0,1}$, scrivere la tavola di Cayley di $(\P(A),\ds)$ e confrontarla con quella di $(\P(A),\cup)$ vista a lezione.
2. Dato un insieme $S$, determinare gli elementi simmetrizzabili nei monoidi $(\P(S),\cup,\vuoto)$ e $(\P(S),\cap,S)$.
3. Sia $*$ l'operazione binaria definita in $X:=\Z\times\Z$ da: $(\forall\; a,b,c,d\in\Z) \big((a,b)*(c,d)=(ac,ad)\big)$. Decidere se $(X,*)$ è un semigruppo, se è commutativo, se ammette elementi neutri a sinistra, se ne ammette a destra. Nel caso la richiesta abbia senso, determinare gli elementi simmetrizzabili in $(X,*)$, descrivendone i simmetrici.
4. Stesse domande come all'esercizio precedente, per le operazioni
   • $(a,b)\in\Z\times\Z\mapsto a+b+1\in\Z$
   • $(a,b)\in\Z\times\Z\mapsto ab+1\in\Z$
   • $(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\cup Y)\cap\N\in\P(\Z)$
   • $(X,Y)\in\P(\Z)\times\P(\Z)\mapsto(X\setminus Y)\cup\set 1\in\P(\Z)$
   al posto di $*$ (suggerimento per l'ultima operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).
5. Svolgere l'esercizio 4 dal compito proposto all'ultimo appello scritto.
6. Sia $S$ un insieme con almeno tre elementi e si fissi $a\in S$. Definiamo un'operazione binaria $*$ in $S$, ponendo, per ogni $x,y\in S$, $x*y=a$, se $a\notin \set{x,y}$, e $a*x=x=x*a$. L'operazione $*$ è commutativa? Costruirne la tavola di Cayley nel caso un cui $S$ abbia esattamente tre elementi. Verificare che $a$ è neutro in $(S,*)$ e che, per ogni $x\in S$, ogni elemento di $S\setminus\set a$ è simmetrico di $x$ rispetto a $*$.
   A questo punto, senza fare alcun calcolo rispondere alla domanda: $*$ è associativa?

26/3

Diversi esercizi sullo studio di proprietà di operazioni binarie.

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

Il gruppo degli invertibili (cioè degli elementi simmetrizzabili) di un monoide $S$: è l'insieme $\U(S)$ degli elementi simmetrizzabili in $S$ ed è un sottomonoide di $S$. Formula per il calcolo del simmetrico di un prodotto in un monoide (in notazione moltiplicativa, per ogni $a,b\in \U(S)$ si ha $(ab)^{-1}=b^{-1}a^{-1}$).

Esempi: i gruppi (moltiplicativi) degli invertibili dei monoidi $(\Z,\cdot)$ e $(\R,\cdot)$ (sono, rispettivamente, dati da $\set{1,-1}$ e $\R\setminus\set 0$); quelli di $(\P(A),\cap)$ e $(\P(A),\cup)$ sono gruppi identici (cioè coincidono con il singleton del loro elemento neutro).

Esercizi proposti:

1. Delle seguenti undici 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}$, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
2. In $D:=\Z\times\Z$ si definisca l'operazione binaria $*$ ponendo, per ogni $a,b,c,d\in\Z$, $(a,b)*(c,d)=(ac,b+d)$. Studiare $(D,*)$, decidendo che genere di struttura algebrica è, (se è un semigruppo, un monoide, un gruppo, se commutativa o meno, etc.) e, nel caso la domanda abbia senso, quali sono i suoi elementi simmetrizzabili. $\Z\times \set 0$ ne è una parte chiusa? Se lo è studiare la struttura indotta da $*$ su $\Z\times \set 0$. Fare lo stesso per $\Z\times \set{1}$.

28/3

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

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

Il prodotto relazionale tra due applicazioni componibili è sempre un'applicazione. Composizione (prodotto operativo) tra applicazioni; sua descrizione esplicita. Notazione: $\beta\circ\alpha:=\alpha\beta$. Il monoide delle trasformazioni di un insieme $S$ (lo indichiamo con $T(S)$). Applicazioni costanti. Se $S$ ha più di un elemento, $T(S)$ non è commutativo.

Diverse notazioni (sinistra, destra, esponenziale, a pedice: $f(a)$, $fa$, $(a)f$, $af$, $a^f$, $f_a$) per indicare l'immagine, mediante un'applicazione $f$, di un elemento $a$ del suo dominio.

L'immagine $\im f$ di un'applicazione $f$; applicazioni suriettive. Caratterizzazione della suriettività; sua negazione. Discussione sullo studio della suriettività o meno di un'applicazione; errori frequenti.

Esercizi proposti:

1. La corrispondenza: $n\in\Z\mapsto n^2/2\in\Z$ è un'applicazione ben definita?
2. Fissato un insieme $S$, sviluppando quanto visto a lezione, provare che:
   1. il monoide $T(S)$ delle trasformazioni di $S$ è commutativo se e solo se $S$ ha al massimo un elemento;
   2. l'insieme delle applicazioni costanti da $S$ a $S$ è una parte chiusa di $T(S)$.
   Scrivere la tavola di Cayley di $T(S)$ nel caso in cui $S=\set{0,1}$, e decidere se, in questo caso, $T(S)$ è un gruppo.
3. Siano $\N$ l'insieme dei numeri naturali e $S=\set{1,2,3}$. Siano poi $\alpha$ la relazione binaria in $S$ definita da: $(\forall x,y\in S)(x\mathrel\alpha y\iff x\lt y)$ e $\beta$ la corrispondenza da $S$ ad $\N$ di grafico $\set{2}\times\set{x\in\N\mid x\lt 10}$. Descrivere la corrispondenza prodotto $\alpha\beta$ e la relazione binaria $\alpha^2=\alpha\alpha$.
4. Rispondere alle domande poste negli esercizi 3 (tranne il punto f) e 4 di Tautologie, insiemi, aritmetica relative a parti del programma già affrontate. Si tratta dunque di rispondere alle domande sulla corretta (buona) definizione di applicazioni, sulla suriettività e sulla composizione tra applicazioni (prodotto operativo). Notazione: $\N^\#=\N\setminus\set0$, $2\N$ è l'insieme dei numeri naturali pari; la composta $fg$ è $g\circ f$.

È poi disponibile una lista (non cortissima) di esercizi sugli argomenti trattati finora nel corso. Ricordo che numerosi altri esercizi si possono trovare in Logica rudimentale, tra i testi di prove d'esame e nel sito della Prof. Leone. Si sconsiglia fortemente di fare esercizi su argomenti ancora non trattati nel corso.

9/4

Restrizioni e prolungamenti di un'applicazione. L'immersione in un insieme di una sua parte: se $X$ è una parte di un insieme $A$, l'immersione di $X$ in $A$, spesso indicata con $X\hookrightarrow A$, è l'applicazione $x\in X\mapsto x\in A$, cioè la restrizione ad $X$ di $\id_A$. Con le stesse notazioni, se $f\colon A\to B$ è un'applicazione, la restrizione di $f$ ad $X$ è la composta di $f$ con l'immersione $X\hookrightarrow A$. Cenno alla nozione di ridotta di un'applicazione.

Applicazione immagine $\vec f\colon\P(A)\to\P(B)$ ed applicazione antiimmagine $\antivecf\colon\P(B)\to\P(A)$ definite da un'applicazione $f\colon A\to B$. Esempi. Con queste notazioni si ha $\vec f(\vuoto)=\antivecf(\vuoto)=\vuoto$, $\,\vec f(A)=\im f$, $\,\antivecf (B)=\antivecf (\im f)=A$. Inoltre, $f$ è suriettiva se e solo se $\antivecf (\set{b})\ne\vuoto$ per ogni $b\in B$. Sezioni di un'applicazione suriettiva (una sezione dell'applicazione $f\colon A\to B$ è un'applicazione $g\colon B\to A$ tale che $f\circ g=\id_B$). Osservazione: per ogni $X\subseteq A$ e $Y\subseteq B$ si ha $X\subseteq\antivecf(\vec f(X))$ e $\vec f(\antivecf(Y))\subseteq Y$ (si vedano gli esercizi) ma, in generale, non valgono le corrispondenti uguaglianze.

Applicazioni iniettive; negazione della iniettività. Diversi esempi. Applicazioni biettive. Ogni applicazione il cui dominio ha meno due elementi è iniettiva. Un'applicazione $f\colon A\to B$ è ; iniettiva se e solo, per ogni $b\in B$, $\antivecf (\set{b})$ ha al massimo un elemento; biettiva se e solo se, per ogni $b\in B$, $\antivecf (\set{b})$ ha esattamente un elemento.

La composta di due applicazioni suriettive (risp. iniettive, biettive) è necessariamente suriettiva (risp. iniettiva, biettiva).

Teorema: se la composta $g\circ f$ di due applicazioni è suriettiva allora quella che agisce per seconda (cioè $g$) è suriettiva; se invece $g\circ f$ è iniettiva allora $f$ è iniettiva. Un esempio di applicazione identica (quindi biettiva) che si possa scrivere come applicazione composta $g\circ f$, dove $g$ non è iniettiva ed $f$ non è suriettiva.

Teorema: un'applicazione è suriettiva se e solo se ha almeno una sezione. Di conseguenza: nel monoide delle trasformazioni di un insieme $S$ gli elementi simmetrizzabili a destra sono tutte e sole le applicazioni suriettive (da $S$ a $S$). Nozioni di retrazione e di applicazione inversa.

Esercizi proposti:

1. Dimostrare che se $f$ è un'applicazione iniettiva, tutte le restrizioni di $f$ sono iniettive.
2. Delle applicazioni negli esercizi proposti per le vacanze, (esercizi 7 e 8; ho apportato alcune correzioni) si decida quali sono e quali non sono iniettive.
3. Si faccia lo stesso per le applicazioni negli esercizi 3 (tranne il punto f) e 4 di Tautologie, insiemi, aritmetica.
4. Si consideri l'applicazione $f\colon n\in\Z\mapsto n^2-3\in\Z$. Dopo aver stabilito se $f$ è iniettiva e se è suriettiva, posto $X=\set{n\in\N\mid n\le 10}$, calcolare $\vec f(X)$, $\antivecf (X)$, $\antivecf(\vec f(X))$ e $\vec f(\antivecf(X))$.
5. Sia $+\colon (a,b)\in\N\times\N\mapsto a+b\in\N$ la consueta operazione di addizione in $\N$. Stabilire se $+$ è iniettiva e se è suriettiva, e calcolare l'antiimmagine mediante $+$ di $\set{1,2,3}$.
6. Elencare tutte le sezioni dell'applicazione $f\colon X\to Y$, dove $X=\set{1,2,3,4}$, $Y=\set{a,b}$, con $a\ne b$ e, per ogni $n\in X$, $f(n)$ è $a$ se $n$ è pari, $b$ se $n$ è dispari. Elencare tutte le sezioni dell'immersione di $\N$ in $\Z$.
7. Siano $f\colon n\in\Z\mapsto n^2\in\Z$ e $X=\set{n\in\N\mid n\le 10}$. Calcolare $\vec f(X)$, $\antivecf (X)$, $\antivecf(\vec f(X))$ e $\vec f(\antivecf(X))$.
8. Sviluppando quanto detto a lezione, verificare in dettaglio che, se $f\colon A\to B$ è un'applicazione, $X\subseteq A$ e $Y\subseteq B$, si ha $X\subseteq\antivecf(\vec f(X))$ e $\vec f(\antivecf(Y))=Y\cap \im f$.
9. Siano $g\colon A\to B$ e $f\colon B\to C$ due applicazioni componibili. Verificare che $(f\circ g)\vecvuoto=\vec f\circ \vec g$. Si tratta di verificare che, per ogni $X\subseteq A$, $\vec f(\vec g(X))$ è l'immagine di $X$ nella funzione immagine definita da $f\circ g$.
   Si verifichi poi anche che $(f\circ g)\antivecvuoto=\antivecg\circ \antivecf$.

11/4

Teoremi: sia $f\colon A\to B$ un'applicazione. Allora $f$ è iniettiva se e solo se $A=\vuoto$ oppure $f$ ha una retrazione (cioè: esiste un'applicazione $g\colon B\to A$ tale che $g\circ f=\id_A$). Inoltre (unicità dell'inversa): se $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$. Infine (catterizzazione delle applicazioni biettive) sono equivalenti:

1. $f$ è biettiva;
2. $f$ ha inversa;
3. $(\forall b\in B)(\exists! a\in A)(b=f(a))$;
4. $f$ ha una ed una sola sezione.

Alcuni metodi per dimostrare la biettività di un'applicazione. Descrizione esplicita dell'inversa di un'applicazione biettiva. Diversi esempi.

Elementi simmetrizzabili a destra, a sinistra, simmetrizzabili nel monoide delle trasformazioni di un insieme.

Traslazioni in una struttura algebrica con un'operazione binaria; elementi cancellabili, a sinistra o a destra; elementi cancellabili. Rapporto tra simmetrizzabilità e cancellabilità in un monoide. Esempi. Questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità (che contiene più di quanto richiesto ai fini di questo corso).

Esercizi proposti:

1. Scrivere, se esiste, l'inversa dell'applicazione definita al 7(ii) degli esercizi proposti per le vacanze.
2. Siano $A=\set{1,2}$ e $B=\set{1,2,3}$. Scrivere tutte le retrazioni dell'immersione $\iota\colon A\hookrightarrow B$.
3. Sia $T=T(\N)$ il monoide delle trasformazioni di $\N$ (cioè il monoide delle applicazioni da $\N$ ad $\N$, con l'operazione di composizione). Data l'applicazione $f\colon n\in\N\mapsto n+1\in\N$, trovare, se possibile tre diversi simmetrici sinistri e/o tre diversi simmetrici destri di $f$ in $T$.
4. Verificare che se $f$ è un'applicazione biettiva e $g=f^{-1}$ è la sua inversa, $\vec f$ è biettiva e si ha $(\vec f)^{-1}=\vec g=\antivecf$.
5. Come si possono determinare, a prima vista, gli elementi cancellabili a destra o a sinistra in una struttura algebrica con un'operazione binaria guardando la sua tavola di Cayley?
6. Tornare al numero 9 degli esercizi proposti per le vacanze e decidere, per ciascuna delle stutture associative lì presentate, quali elementi sono cancellabili a destra e/o sinistra.
7. Siano $(S,*)$ un semigruppo e, per ogni $a\in S$, sia $\ell_a\colon x\in\ S\mapsto a*x\in S$, la traslazione sinistra definita da $S$. Provare che, per ogni $a,b\in S$, $\ell_a\circ\ell_b=\ell_{ab}$ (è necessario usare la proprietà associativa?). Dedurre che, in $(S,*)$ l'insieme degli elementi cancellabili a sinistra è una parte chiusa e che, se $(S,*)$ è un monoide e $a$ è simmetrizzabile in $(S,*)$, $\ell_a$ è biettiva (suggerimento: se $t$ è l'elemento neutro di $(S,*)$, $\ell_t$ è l'applicazione identica di $S$).

16/4

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

Il gruppo simmetrico su un insieme (è il gruppo degli invertibili di $T(S)$; i suoi elementi sono dunque le permutazioni di $S$, cioè le applicazioni biettive da $S$ a $S$).

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti.

Notazione: $B^A$ e ${}^AB$ come sinonimi di $\Map(A,B)$.

Criterio di esistenza di applicazioni iniettive/suriettive/biettive tra assegnati insiemi finiti: se $A$ e $B$ sono insiemi finiti, allora esistono applicazioni iniettive da $A$ a $B$ se e solo se $|A|\le |B|$; esistono applicazioni suriettive da $A$ ad $B$ se e solo se $|A|\ge |B|>0$ oppure $|A|=|B|=0$; esistono applicazioni biettive da $A$ ad $B$ se e solo se $|A|=|B|$. Per un'applicazione $f$ tra due insiemi finiti con lo stesso numero di elementi sono equivalenti: $f$ è iniettiva, $f$ è suriettiva, $f$ è biettiva.

Applicazione del precedente teorema: in un monoide finito, gli elementi cancellabili sono tutti e soli gli elementi simmetrizzabili (questo enunciato è generalmente falso per monoidi infiniti). La mia nota sulla cancellabilità che contiene una dimostrazione di un enunciato più forte di questo, che però non è in programma.

Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti, con verifica nel caso dell'unione di due o tre insiemi.

Esercizi proposti:

1. Sia $S$ un insieme con (almeno) tre elementi distinti $a$, $b$, $c$. Sia $f$ l'applicazione $S\to S$ definita da $f(a)=b$, $f(b)=a$ e $f(x)=x$ per ogni $x\in S\setminus\set{a,b}$. Analogamente, sia $g$ l'applicazione $S\to S$ definita da $g(a)=c$, $g(c)=a$ e $f(x)=x$ per ogni $x\in S\setminus\set{a,c}$. Provare che $f$ e $g$ sono biettive (suggerimento: verificare che $f\circ f=g\circ g=\id_S$), quindi sono permutazioni di $S$. Verificare poi che $f\circ g\ne g\circ f$ (suggerimento: calcolare $(f\circ g)(a)$ e $(g\circ f)(a)$).
   Concludere che, come detto a lezione, il gruppo simmetrico su un insieme $A$ è abeliano se e solo se $|A|\le 2$.
2. Utilizzando diagrammi di Venn, come fatto a lezione nel caso della formula analoga per due insiemi, verificare la formula di inclusione-esclusione per tre insiemi finiti (per ogni $A,B,C$ che siano insiemi finiti, $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$).
3. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=7$ e $|B|=10$.
   1. Se $|A\cap B|=2$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=12$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 5$, cosa possiamo dire su $|A\cup B|$?
   4. Indicare il numero delle applicazioni, delle applicazioni iniettive e delle applicazioni suriettive da $A$ a $B$.
   5. Sia $X$ una parte di $A$. Supponiamo che esista un'applicazione suriettiva da $X$ ad $A$. Cosa sappiamo dire su $X$?
   6. Indicare il numero delle applicazioni e quello delle applicazioni iniettive da $\P(A)$ a $\P(A\times B)$
4. Siano $S=\set{0,1,5}$ e $T=\set{1,2}$. Descrivere esplicitamente tutte le applicazioni iniettive da $T$ ad $S$ e le applicazioni suriettive da $S$ a $T$ (suggerimento per la seconda parte: si fa prima a dire quali non sono suriettive). Quante sono?

18/4

Discussione di un esercizio sulla non commutività di gruppi simmetrici.

Fattoriali. Per ogni numero naturale $n$, se $S$ è un insieme di cardinalità $n$, il numero delle permutazioni di $S$ (cioè la cardinalità di $|\Sym(S)|$) è $n!$.

Funzione caratteristica $\chi_{S,X}$ di una parte $X$ di un insieme $S$; biezione canonica $X\in\P(S)\mapsto \chi_{S,X}\in\set{0,1}^S$ e sua inversa. Di conseguenza: $|\P(S)|=2^{|S|}$ per ogni insieme finito $S$. Rappresentazione (in contesto informatico) di parti di un insieme finito come "stringhe di 0 e 1".

Anelli, anelli commutativi, anelli unitari. Terminologia essenziale per la teoria degli anelli (zero ed unità di un anello, inversi ed opposti). Esempi, tra cui: $(\Z,+,\cdot)$, $(\Q,+,\cdot)$, $(\R,+,\cdot)$, $(2\Z,+,\cdot)$ (non unitario), anelli di matrici (come esempi di anelli non commutativi), l'anello delle parti di un insieme.

Sottoanelli e sottoanelli unitari.

Alcune regole elementari di calcolo in un anello $R$: per ogni $a$, $b$ in $R$, $a0_R=0_R=0_Ra$, dove $0_R$ è lo zero di $R$, $a(-b)=-(ab)=(-a)b$.

Esercizi proposti:

1. Scrivere la tavola di Cayley del gruppo simmetrico $\S_3=\Sym(\set{1,2,3})$.
2. Dimostrare che, per ogni numero intero $n$, $n\Z=\set{nk\mid k\in\Z}$ costituisce un sottoanello dell'anello degli interi.
3. Esercizio 5 da Polinomi e strutture algebriche, solo relativamente alle nozioni introdotte a lezione.
4. Svolgere l'esercizio 9 da Polinomi e strutture algebriche, tralasciando le domande relative alla nozione di ideale e, in generale, tutto ciò che sia riferito a nozioni e notazioni che non abbiamo (ancora) definito.
5. Eseguire, per due arbitrari elementi $a$ e $b$ di un arbitrario anello, il calcolo di $(a+b)^2=(a+b)(a+b)$.

23/4

Altre regole di calcolo negli anelli; $a(b-c)=ab-ac$ e $(b-c)a=ba-ca$ per ogni scelta di elementi $a,b,c$ in un anello. Divisori dello zero (anche sinistri/destri) in un anello. Cancellabilità e divisori dello zero in anelli; vari esempi. Se $R$ è un anello unitario che ha più di un elemento, $0_R$ non è invertibile in $R$. Corpi e campi. Legge di annullamento del prodotto, anelli integri, domini di integrità. Esempi. I domini di integrità finiti (ma in verità tutti gli anelli integri finiti) sono campi.

Potenze (o, in notazione additiva, multipli) di un elemento secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari nel caso dei gruppi). Regole di calcolo (senza dimostrazione): per ogni elemento $x$ di un semigruppo e per ogni $n,m\in\Z$ per cui $x^n$ e $x^m$ siano definiti, $x^{n+m}=x^n x^m$ e $x^{nm}=(x^n)^m$. In notazione additiva queste formule diventano, con le stesse quantificazioni, $(n+m)x=nx+mx$ e $(nm)x=m(nx)$. Potenze (o multipli) secondo interi di uno stesso elemento di un semigruppo commutano sempre tra loro.

In ogni struttura algebrica, l'intersezioni di ogni insieme di parti chiuse è una parte chiusa; lo stesso vale se 'parte chiusa' è sostituita da 'sottomonoide' (in un monoide) o 'sottogruppo' in un gruppo. Parte chiusa (o sottomonoide, o sottogruppo) generata da una parte. Gruppi ciclici.

Esercizi proposti:

1. Siano $(R,+,\cdot)$ e $(S,\oplus,\odot)$ due anelli. Nel prodotto cartesiano $C=R\times S$ definiamo due operazioni binarie (che continuiamo a indicare con $+$ e $\cdot$) ponendo, per ogni $a,b\in R$ e $u,v\in S$, $(a,u)+(b,v)=(a+b,u\oplus v)$ e $(a,u)\cdot(b,v)=(a\cdot b,u\odot v)$. Provare che $C$, munito di queste due operazioni, è un anello, che questo anello è commutativo se e solo se lo sono sia $R$ che $S$ ed è unitario se e solo se lo sono sia $R$ che $S$. Supponendo $|R|>1$ e $|S|>1$, possiamo stabilire se $C$ è un anello integro? Nel caso in cui $R=S=\Z$ e nel caso in cui $R=S=\R$, dire quali sono i divisori dello zero in $C$.
2. Nell'anello delle matrici $2\times 2$ sul campo dei reali, stabilire se $\binom{0\;1}{0\;0}$ è un divisore dello zero.
3. $(\Z,+)$ è un gruppo ciclico?
4. Per ogni insieme $S$, sia $\P_1(S)=\set{\set x\mid x\in S}$. Trovare il sottomonoide di $(\P(S),\cup)$ generato da $\P_1(S)$ nel caso in cui $S=\set{1,2,3}$ e nel caso in cui $S=\N$. Attenzione alla trappola!
5. Nel gruppo $(\P(\N),\ds)$, trovare il sottogruppo generato da $A$ e quello generato da $B$, dove $A=\set{\set 1}$ e $B=\set{\set 0,\set 1}$.

30/4

Parti chiuse, sottomonoidi e sottogruppi generati da singleton. Periodo di un elemento e caratteristica di un anello unitario. Esempi. Permutazioni cicliche.

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

Isomorfismi. L'inversa di ogni isomorfismo è un isomorfismo. Discussione generale ed alcuni esempi. Invarianza delle proprietà algebriche per isomorfismi: questi conservano la commutatività e associatività; inoltre l'immagine mediante un isomorfismo di un elemento che sia (a destra o a sinistra) neutro o simmetrizzabile, o cancellabile ha la stessa proprietà (e gli isomorfismi conservano gli eventuali neutri e simmetrici).

Un altro esempio di isomorfismo: la funzione esponenziale è un isomorfismo da $(\R,+)$ a $(\R^+,\cdot)$ (il gruppo moltiplicativo dei reali positivi).

Anelli booleani. Proprietà: sono commutativi e, escluso l'anello con un solo elemento, hanno caratteristica 2. Enunciato del teorema di Stone e sue conseguenze: la cardinalità di un anello booleano è necessariamente una potenza di 2; due anelli booleani finiti della stessa cardinalità sono certamente isomorfi (si veda anche l'ultimo degli esercizi).

Esercizi proposti:

1. Sia $(S,*)$ una struttura algebrica ad una operazione binaria e sia $T$ una sua parte chiusa non vuota. L'immersione di $T$ in $S$ è un omomorfismo da $(S,*)$ a $(T,*)$?
2. Per un arbitrario insieme $S$, dimostrare che l'applicazione $X\mapsto S\setminus X$ è un isomorfismo da $(\P(S),\cap)$ a $(\P(S),\cup)$. Avendo osservato ciò, riconsiderare il fatto che le proprietà algebriche di $(\P(S),\cup)$ già studiate (ad esempio, descrizione di neutri, simmetrizzabili, cancellabili) corrispondano alle analohe proprietà per $(\P(S),\cap)$.
3. Scrivere, a meno di isomorfismi, tutte le possibili tavole di Cayley per gruppi di cardinalità 4, e dedurne che esistono, a meno di isomorfismi, solo due tali gruppi.
4. Completando quanto fatto a lezione, verificare in dettaglio il fatto che gli isomorfismi conservano tutte le proprietà algebriche menzionate. Quali tra queste vengono conservate dagli omomorfismi suriettivi?
5. Verificare che l'applicazione $f\colon n\in\Z\mapsto n-1\in\Z$ è un isomorfismo di anelli dal consueto anello $(\Z,+,\cdot)$ alla struttura $(\Z,\oplus,\odot)$ definita nell'esercizio 5 di Polinomi e strutture algebriche.
6. Sia $G$ un gruppo abeliano. Verificare che l'applicazione $g\in G\mapsto g^{-1} \in G$, che ad ogni elemento $G$ associa l'inverso, è un isomorfismo da $G$ a $G$. Cambia qualcosa se $G$ non è abeliano?
7. Dati due insiemi equipotenti $S$ e $T$, ed un'applicazione biettiva $f\colon S\to T$, provare che:
   1. l'applicazione $X\in \P(S)\mapsto \vec f(X)\in\P(T)$ è un isomorfismo dall'anello delle parti di $S$ all'anello delle parti di $T$;
   2. l'applicazione $\sigma\in T(S)\mapsto f\circ \sigma\circ f^{-1}\in T(T)$ è un isomorfismo dal monoide delle trasformazioni di $S$ al monoide delle trasformazioni di $T$;
   3. l'applicazione $\sigma\in \Sym(S)\mapsto f\circ \sigma\circ f^{-1}\in \Sym(T)$ è un isomorfismo dal gruppo simmetrico su $S$ al gruppo simmetrico su di $T$.

2/5

Discussione di un esercizio: isomorfismo tra $(\P(S),\cup)$ e $(\P(S),\cap)$ per un arbitario insieme $S$.

Omomorfismi di monoidi e di anelli unitari.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche, antisimmetriche, transitive. Negazione di ciascuna di queste proprietà; loro espressione in termini di proprietà (insiemistiche) del grafico. Diversi esempi.

Un'osservazione su come semplificare la verifica della transitività di una relazione binaria $\rho$ su un insieme $A$: se $x,z\in A$ e $y\in \set{x,z}$, allora l'implicazione $((x\mathrel\rho y)\land(y\mathrel\rho z))\implica x\mathrel\rho z$ è banalmente verificata.

Relazioni di equivalenza, relazioni di ordine largo, relazioni di ordine stretto. Diversi esempi. Notazioni introdotte: $\Eq(A)$, $\OL(A)$, $\OS(A)$, per gli insiemi delle relazioni di equivalenza, di ordine largo, di ordine stretto in un insieme $A$.

Nucleo di equivalenza di un'applicazione (anche detto equivalenza associata all'applicazione).

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

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

Le relazioni di equivalenza banali in un insieme (relazione di uguaglianza e relazione universale). Il nucleo di equivalenza du un'applicazione $f$ è la reazione di uguaglianza (risp. quella universale) nel dominio di $f$ se e solo se $f$ è iniettiva (risp. costante).

Esercizi proposti:

1. Esercizi 1 (esclusi i punti f e g), 2, 3, 4 da relazioni binarie. Terminologia e notazioni: per ‘ordinamento’ si intende una relazione d'ordine stretto o largo; $\N^\#=\N^*=\N^+=\N\setminus\set 0$.
2. Sia $A=\set{1,2,3,4,5,6,7,8}$ e sia $B$ l'insieme degli interi pari appartenenti ad $A$. Detta $f$ l'applicazione $A\to\Z$ definita ponendo $f(a)=16$ se $a\in B$ e $f(a)=(a-3)^2$ se $a\in A\setminus B$, sia $\rho$ il nucleo di equivalenza di $f$. Si descrivano in modo esplicito (elencandone cioè gli elementi) tutte le classi di equivalenza modulo $\rho$ e $A/\rho$. Quanti elementi ha $A/\rho$?
3. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cup \set{1,2,3}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim_f}$, dove $\sim_f$ è il nucleo di equivalenza di $f$? Descriverli esplicitamente.
4. Siano $S=\set{1,2,3,4}$ e $A=\set{1,2}$; si consideri l'applicazione $f\colon x\in\P(S)\mapsto x\setminus A\in \P(S)$. $f$ è iniettiva? $f$ è suriettiva? Detto $\rho$ il nucleo di equivalenza di $f$, si descriva, innanzitutto, $[\vuoto]_\rho$ in modo esplicito (elencandone cioè gli elementi) e se ne calcoli la cardinalità. Si descrivano poi, sempre in modo esplicito, tutti gli elementi di $\P(S)/\rho$ e si calcoli $|\P(S)/\rho|$.
5. Siano $f$ un'applicazione da un insieme $A$ ad un insieme $B$ e $\beta$ una relazione di equivalenza in $B$. Verificare che la relazione binaria $\alpha$ definita in $A$ ponendo, per ogni $x,y\in A$, $x\mathrel\alpha y \iff f(x)\mathrel\beta f(y)$ è di equivalenza. Identificare $\alpha$ nel caso in cui $\beta$ sia una delle relazioni di equivalenza banali in $B$.

7/5

Per ogni relazione di equivalenza $\sim$ su un insieme $A$, proiezione canonica di $A$ su $A/{\sim}$: è l'applicazione (suriettiva) $A\to A/{\sim}$ che manda ogni $x\in A$ in $[x]_\sim$. Ogni equivalenza è il nucleo di equivalenza di un'applicazione: ad esempio, della proiezione canonica che essa definisce.

Classi di equivalenza rispetto al nucleo di equivalenza di un'applicazione: se $\sim$ è il nucleo di equivalenza di un'applicazione $f$ di dominio $A$, per ogni $x\in A$ si ha $[x]_\sim=\antivecf(\set{f(x)})$.

L'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in A/{\sim}$ è biettiva, quindi si ha $|A/{\sim}|=|\im f|$. Teorema fondamentale di omomorfismo per insiemi. Si consiglia di consultare le note, scritte a questo riguardo, anche se con stile e notazioni non identiche a quelle della lezione. Si legga, in particolare, l'esempio conclusivo.

Partizioni di un insieme. Definizione e prima caratterizzazione: $F$ è una partizione di un insieme $A$ se e solo se $\vuoto\notin F\subseteq \P(A)$ e $(\forall x\in A)(\exists! b\in F)(x\in b)$. Vari esempi; tra questi le partizioni banali di un insieme $A$, cioè $\P_1(A)$ e, se $A\ne\vuoto$, $\set A$.

Per un arbitrario insieme $A$, biezione canonica da $\Eq(A)$ a $\Part(A)$ (insiemi delle relazioni di equivalenza e delle partizioni di $A$): questa è l'applicazione $\rho\in\Eq(A)\mapsto A/\rho\in\Part(A)$; la sua inversa è l'applicazione che ad ogni partizione $F$ di $A$ associa la relazione di equivalenza definita dichiarando due elementi di $A$ equivalenti se e solo se appartengono allo stesso blocco della partizione $F$. (questa relazione di equivalenza è il nucleo di equivalenza dell'applicazione $A\to F$ che ad ogni $x\in A$ asocia l'unico elemento di $F$ a cui $x$ appartenga). L'esistenza di questa biezione è il contenuto del teorema fondamentale su relazioni di equivalenza e partizioni. Diversi esempi.

Esercizi proposti:

1. Riguardare, alla luce della lezione di oggi, gli esercizi 3 e 4 della lezione precedente.
2. Scrivere cinque partizioni (distinte) di $\Z$.
3. A quali relazioni di equivalenza corrispondono (tramite la biezione canonica) le partizioni banali su un insieme $A$?
4. Sia $A=\set{1,2,3,4,5,6}$. Stabilire quante sono, e descrivere esplicitamente, le relazioni di equivalenza $\sim$ in $A$ tali che $1\sim 3\not\sim 2\sim 4$ e $4\in[5]_\sim$.
5. Sia $A=\set{1,2,3,4,5,6,7}$. Quante (e quali) sono le relazioni di equivalenza $\rho$ in $A$ tali che $1\mathrel\rho 3$, $\set{2,5,6}\subseteq [3]_\rho$ e $6\in[7]_\rho$?
6. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cap \set{1,2,3}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim_f}$, dove $\sim_f$ è il nucleo di equivalenza di $f$? Dopo aver risposto a questa domanda, descrivere esplicitamente gli elementi di $\P(S)/{\sim_f}$.
7. Esercizio 2, punti (i) e (ii), dal compito del 22 giugno 2015.
8. Esercizio 2 dal compito del 5 marzo 2015.
9. Esercizio 1 dal compito del 16 luglio 2013.

9/5

Discussione di alcuni esercizi.

Richiami sulle relazioni d'ordine. Insiemi ordinati e ordinamenti indotti sui loro sottoinsiemi. Senza dimostrazioni: biezione canonica tra gli insiemi delle relazioni di ordine stretto e quello delle relazioni di ordine largo in un fissato insieme (si veda uno degli esercizi). Elementi tra loro confrontabili in insiemi ordinati; relazioni di ordine totale e insiemi totalmente ordinati.

Ordinamenti duali e principio di dualità per insiemi ordinati.

Minimi e massimi in insiemi ordinati; elementi minimali e massimali. Vari esempi. Se $a$ è minimo (risp. massimo) in un insieme ordinato $(S,\rho)$, $a$ è l'unico elemento minimale (risp. massimale) in $(S,\rho)$, quindi anche l'unico minimo (risp. massimo). Esempio di un insieme ordinato privo di minimo e di massimo in cui, però, esiste un elemento che è, allo stesso tempo, l'unico elemento minimale e l'unico elemento massimale. In ogni insieme ordinato finito non vuoto esistono elementi minimali ed elementi massimali.

Relazione di divisibilità in un semigruppo commutativo ed in un monoide commutativa. Essa è transitiva e, nel caso dei monoidi, anche riflessiva. Nel caso del monoide $(\N,\cdot)$ (ma non nel caso del monoide $(\Z,\cdot)$) è una relazione d'ordine. Elementi associati in un monoide commutativo (due elementi $a$ e $b$ sono associati se e solo se $a$ divide $b$ e $b$ divide $a$). Teorema: due elementi di un monoide commutativo sono associati se e solo se hanno lo stesso insieme di divisori. Di conseguenza: la relazione "essere elementi associati", in un monoide commutativo, è una relazione di equivalenza.

Confermo l'incontro per la discussione degli esercizi della prova in itinere per il prossimo venerdì 11. Ci vedremo in aula B8 alle 9.

Esercizi proposti:

1. Trovare gli elementi minimali, gli elementi massimali, eventuali minimo e massimo nell'insieme $\set{2,4,7,8,14,21}$ ordinato per divisibilità (cioè: tramite l'ordinamento indotto dalla divisibilità in $(\N,\cdot)$).
2. Trovare gli eventuali elementi minimali, massimali, minimo e massimo nell'insieme $\Pf(\N)$ delle parti finite di $\N$, ordinato per inclusione.
3. Si dimostrino i seguenti enunciati presentati a lezione: per ogni insieme $A$,
   1. per ogni relazione di ordine largo $\rho$ in $A$, la relazione binaria $\rho_{\ne}$ definita in $A$ da: $(\forall x,y\in A)(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$ è una relazione di ordine stretto;
   2. per ogni relazione di ordine stretto $\sigma$ in $A$, la relazione binaria $\underline{\sigma}$ definita in $A$ da: $(\forall x,y\in A)(x\mathrel{\underline{\sigma}}y \iff (x\mathrel\sigma y \lor x=y))$ è una relazione di ordine largo;
   3. le applicazioni $\rho\in \OL(A)\mapsto \rho_{\ne}\in\OS(A)$ e $\sigma\in \OS(A)\mapsto \underline{\sigma}\in\OL(A)$ sono biettive, una inversa dell'altra.
4. Siano $a$ un elemento e $u$ un elemento invertibile in un monoide commutativo. Dimostrare che $a$ e $au$ sono associati.
5. Dimostrare per via diretta (cioè provando le proprietà riflessiva, simmetrica, transitiva) che, in un monoide comutativo, la relazione "essere elementi associati" è di equivalenza.
6. Provare che due elementi di un monoide commutativo sono associati se e solo se hanno lo stesso insieme di multipli.

14/5

Discussione di un esercizio e caratterizzazione degli associati in di un elemento cancellabile $a$ in un monoide commutativo $M$ (sono tutti e soli gli elementi della forma $au$ al variare di $u\in\U(M)$).

Buon ordinamento dell'insieme dei naturali ordinato nel modo usuale. Di conseguenza: principio di induzione (prima e seconda forma, anche detta induzione completa), con dimostrazione. Dimostrazione induttiva della formula $|\P(S)|=2^{|S|}$ per ogni insieme finito $S$.

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

Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$. Per ogni $k,n\in \N$ tali che $k\le n$, formula ricorsiva: $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$ e formula chiusa: $\binom nk=n!/(k!(n-k)!)$. Il triangolo di Tartaglia-Pascal.

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

Divisori banali di un elemento ed elementi irriducibili in un monoide commutativo.

Esercizi proposti:

1. Dimostrare per induzione questa proposizione: per ogni $n\in\N^\#$, $\sum_{i=1}^{n}=\binom {n+1}2$.
2. Posto $S=\set{0,1,2,3,4}$, elencare gli elementi di $\P_4(S)$ e quelli di $\P_6(S)$.
3. Sia $S$ un insieme di cardinalità 12. Quante sono le parti di $S$ di cardinalità 5? E quante quelle di cardinalità 7? Quante sono le 10-parti di $\P(S)$?
4. Sia $S$ un insieme di cardinalità 5. Le funzioni caratteristiche delle 3-parti di $S$ sono tutte e sole le applicazioni da $S$ a $\set{0,1}$ tali che …? Quante sono?
5. Posto $A=\set{1,2,3,\ldots,7}$ e $B=\set{2,5}$, indicare le cardinalità degli insiemi $L_1:=\set{X\in\P(A)\mid (4\in X)\land(|X|=5)}$ e $L_2:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X)\land(|X|=5)}$.
6. Siano $S$ l'insieme dei primi 90 numeri interi positivi e $T$ una sua parte costituita da 10 elementi. Calcolare la cardinalità dell'insieme delle 5-parti di $S$ e quella dell'insieme delle 5-parti di $T$. Anacleto partecipa ad un gioco: deve scegliere dieci numeri interi compresi tra 1 e 90; tra i novanta numeri ne verranno poi estratti 5 ed Anacleto vince se (e solo se) tutti e cinque i numeri estratti sono tra quelli che lui aveva scelto. Che probabilità ha Anacleto di vincere?

16/5

Teorema fondamentale dell'aritmetica (in $\N^\#$); ne è stata dimostrata solo una parte (ogni intero maggiore di 1 è prodotto di numeri primi), ma non quella relativa all'essenziale unicità della fattorizzazione. Nozione di monoide fattoriale; anelli fattoriali. Fattorialità di $\Z$.

Descrizione dell'insieme dei divisori di un elemento in un monoide fattoriale $M$ a partire da una sua fattorizzazione in irriducibili, con particolare enfasi sul caso in cui il monoide è quello moltiplicativo degli interi positivi o quello degli interi non nulli. Nel caso generale, se $a\in M\setminus\U(M)$ e $a=p_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una sua decomposizione in potenze di irriducibili (i $p_i$ sono elementi irriducibili a due a due non associati tra loro, e gli esponenti $a_i$ sono interi positivi), i divisori di $a$ in $M$ sono tutti e soli gli elementi associati a quelli della forma $p_1^{b_1} p_2^{b_2}\cdots p_n^{b_n}$, dove ciascuno degli esponenti $b_i$ è un numero naturale minore o uguale ad $a_i$.

Relazione di divisibilità in anelli commutativi. In un anello commutativo $R$, un elemento che divida due elementi ne divide tutte le combinazioni lineari a coefficienti in $R$.

Le congruenze modulo un intero in $\Z$ (cioè le equivalenze $\equiv_m$ al variare di $m\in\Z$). Loro descrizione esplicita nei casi in cui $m$ è uno tra 0, 1 e 2. Per ogni intero $m$, ${\equiv_m}={\equiv_{-m}}$.

Equivalenze compatibili con un'operazione binaria ed operazioni quoziente (cioè quelle indotte sull'insieme quoziente). Esempi. Congruenza in una struttura algebrica e struttura quoziente. Se $\sim$ è un'equivalenza compatibile con l'operazione binaria $*$ in un insieme $S$, la proiezione canonica $a\in (S,*)\mapsto [a]_\sim \in(S/{\sim},*)$ è un omomorfismo suriettivo. Nel passaggio da una operazione ad una sua operazione quoziente vengono conservati: commutatività, associatività, esistenza di neutri e simmetrici (anche solo a destra o sinistra); nel caso in cui compaiano più operazioni: distributività. I quozienti di semigruppi, monoidi, gruppi (eventualmente abeliani), anelli (eventualmente commutativi o unitari) sono strutture dello stesso tipo.

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

Le congruenze $\equiv_m$ al variare di $m\in\Z$ sono effettivamente congruenze nell'anello $(\Z,+,\cdot)$. Notazioni: per interi $a$ ed $m$, $[a]_m=[a]_{\equiv m}$ e $\Z_m=\Z/{\equiv_m}$.

Esercizi proposti:

1. Quanti sono, in $\N$, i divisori di $n=2\cdot 3^{7}\cdot 11^3$? E quanti tra essi sono multipli di $9$? E quanti sono i divisori di $n$ in $\Z$?
2. Verificare che la relazione "avere la stessa lunghezza" è una congruenza nel monoide delle parole su un alfabeto.
3. Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è compatibile con $*$. Spiegare perché questo esercizo generalizza il precedente.
4. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
5. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
6. La relazione di equivalenza "avere la stessa parità" (cioè quella indotta dalla congruenza modulo 2 in $\Z$) è compatibile con l'operazione di elevazione a potenza ($(a,b)\mapsto a^b$) in $\N^\#$? E in $\N$?
7. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_2$ (i cui elementi, ricordiamo, sono l'insieme degli interi pari e quello degli interi dispari).
8. Come accennato a lezione, il passaggio ad un'operazione quoziente non conserva sempre la proprietà di cancellabilità. Verificarlo su questo esempio: il numero $2$ è cancellabile nell'anello $\Z$, ma $[2]_4$ non è cancellabile nell'anello $\Z_4$. In effetti, vediamo così che benché $\Z$ sia un dominio di integrità, il suo anello quoziente $\Z_4$ non è un dominio di integrità.

21/5

Descrizione esplicita delle classi resto: per ogni $m,a\in \Z$, la classe di resto $[a]_m:=[a]_{\equiv_m}$ di $a$ modulo $m$ è $a+m\Z:=\set{a+mk\mid k\in \Z}$. L'operazione parziale mod (per ogni $a,m\in\Z$, se $m\ne0$, $a\modbin m$ è, per definizione, il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$ e viene anche indicato con $\rest(a,m)$). Descrizione esplicita dei quozienti di $\Z$: per ogni $m\in\N^*$, $\Z_m=\set{[0]_m, [1]_m, [2]_m, \dots, [m-1]_m}$. Gli elementi di $\Z_m$ appena elencati sono a due a due distinti (vale a dire: se $i$ e $j$ sono numeri naturali minori di $m$ e $i\equiv_m j$, allora $i=j$), quindi $|\Z_m|=m$. Inoltre: $\Z_m$ ha caratteristica $m$.

Divisione con resto (o divisione aritmetica) in $\Z$: $(\forall a, b\in\Z)$$(b\ne 0\implica (\exists!(q,r)\in\Z\times\N)$$(a=bq+r \land r\lt |b|) )$. Con queste notazioni, $a$, $b$, $q$ ed $r$ prendono rispettivamente i nomi di dividendo, divisore, quoziente e resto (nella divisione di $a$ per $b$) e si ha $r=a\modbin b$; si scrive anche $r=\rest(a,b)$. Congruenze in $\Z$ come nuclei di equivalenza di funzioni resto (due interi sono congrui modulo un intero non nullo $m$ se e solo se hanno lo stesso resto nella divisione per $m$).

Aritmetica modulare e periodicità: se $x$ è un elemento periodico di periodo $m$ di un gruppo (moltiplicativo) $G$, allora, per ogni $a,b\in\Z$, si ha $x^a=x^b\iff a\equiv_m b$. In particolare, $x^a=x^{a\,\modbin\,n}$, e $x^a=1_G$ se e solo se $m$ divide $a$.

Calcoli in aritmetica modulare; alcuni esempi. Come applicazione: criteri di divisibilità di numeri naturali per 3, 9, 11. Osservazione: due interi congrui modulo un intero $m$ sono congrui anche modulo ciascun divisore di $m$.

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

Esistenza ed espressione di un MCD $d$ e di un mcm $m$ tra due elementi $a$ e $b$ di un monoide fattoriale. Osservazione: $ab$ e $md$ risultano associati.

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

Estensione dell'algoritmo euclideo e Teorema di Bézout, nella forma: se $a,b\in\Z$ e $d$ è un massimo comun divisore tra $a$ e $b$, allora $d$ è una combinazione lineare di $a$ e $b$ a coefficienti in $\Z$. La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo.

Esercizi proposti:

1. Calcolare $\rest(10,6)$, $\rest(10,-6)$, $\rest(-10,6)$, $\rest(-10,-6)$.
2. Calcolare $\rest(12340456789,9)$, $\rest(12340456789,3)$, $\rest(12340456789,11)$.
3. Senza eseguire calcoli, si trovi $\rest(93\cdot 901,9)$.
4. Sia $n\in\N^*$. Supponiamo che $a_1$ e $a_0$ siano rispettivamente la cifra delle decine e quella delle unità di $n$, se $n$ è scritto in base 10. Provare che $n\equiv_5 a_0$, $n\equiv_2 a_0$ e $n\equiv_4 10a_1+a_0$. Calcolare $\rest(1234045679,4)$ e $\rest(1234045679,5)$.
5. Similmente a quanto fatto in aula per $\Z_6$, si dica di ciascun elemento di $\Z_8$ se è o meno un divisore dello zero, se è o meno invertibile. (Suggerimento: calcolare i quadrati delle classi di 3 e di 5.)
6. Eseguendo solo facilissimi calcoli a mente, si calcoli $\rest(2^{14},15)$ e $\rest(2^{15},15)$. (Suggerimento: partire da $\rest(2^4,15)$.)
7. Esercizio 12 da Tautologie, insiemi, aritmetica.
8. Che giorno (delle settimana) è $3^{500}$ giorni dopo una domenica (se nel frattempo non viene riformato il calendario)?
9. Calcolare $\rest(786761!,1111)$.
10. Sia $x$ un elemento di un gruppo (moltiplicativo) $G$. Verificare che $x$ è periodico se e solo se l'applicazione $f\colon n\in\Z\mapsto x^n\in G$ non è iniettiva. Dedurne che se $G$ è finito ogni elemento di $G$ è periodico. Supposto poi che $x$ sia periodico e che $m$ sia il suo periodo, Identificare il nucleo di equivalenza di $f$.
11. Usando l'algoritmo euclideo, svolgere l'esercizio 5 da Tautologie, insiemi, aritmetica. Trovare poi due interi $u$ e $v$ tali che il massimo comun divisore positivo tra $155$ e $688$ sia $155u+688v$. Trovare anche un minimo comune multiplo tra $155$ e $688$.

23/5

Equazioni diofantee (di primo grado a due incognite) ed altre formulazioni del teorema di Bézout: se $a,b\in\Z$ e $d$ è un MCD tra $a$ e $b$,

• l'insieme delle combinazioni lineari di $a$ e $b$ in $\Z$ coincide con $d\Z$;
• $a$ e $b$ sono coprimi se e solo se esistono interi $u$ e $v$ tali che $1=au+bv$;
• per ogni $c\in\Z$, l'equazione diofantea $ax+by=c$ ha soluzioni (intere) se e solo $d$ divide $c$.

Metodo di risoluzione di equazioni diofantee (del tipo appena descritto). Se una tale equazione ha soluzioni, ne ha infinite.

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

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

Algoritmo per la risoluzione delle equazioni congruenziali. Equazioni congruenziali ridotte. L'insieme di tutte le soluzioni di un'equazione congruenziale. Metodi per la semplificazione delle equazioni congruenziali: se $a,b\in\Z$ e $m\in\N^*$, con qualche esempio.

• se $a'\in[a]_m$ e $c'\in[c]_m$, le equazioni congruenziali $ax\equiv_m c$ e $a'x\equiv_m c'$ hanno le stesse soluzioni;
• per ogni $s,t,k\in\Z$, se $k\ne 0$, si ha $s|t$ se e solo se $sk|tk$. Di conseguenza, le equazioni congruenziali $ax\equiv_m c$ e $akx\equiv_{mk} ck$ hanno le stesse soluzioni;
• se $\ell$ è un intero coprimo con $m$, le equazioni congruenziali $ax\equiv_m c$ e $a\ell x\equiv_{m} c\ell$ hanno le stesse soluzioni (questo perché $[\ell]_m$ è invertibile in $\Z_m$).

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

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario.

Proprietà universale per gli anelli dei polinomi (come dalle note). Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata); l'omomorfismo di sostituzione; per ogni intero $m\ne 0$, l'epimorfismo (omomorfismo suriettivo) da $\Z[x]$ a $\Z_m[x]$, indotto dalla proiezione canonica $\Z\epi \Z_m$, che ad ogni polinomio $f$ associa "$f$ stesso riguardato modulo $m$".

Terminologia essenziale: successione dei coefficienti di un polinomio, polinomi costanti, grado e coefficiente direttore di un polinomio, polinomi monici.

Grado della somma e della differenza tra due polinomi.

Esercizi proposti:

1. Esercizi da 5 a 11 da Tautologie, insiemi, aritmetica.
2. Di ciascuno degli elementi di $\Z_{12}$ si stabilisca se è invertibile e, nel caso, si trovi l'inverso.
3. Siano $m=2^5 3^8 19$ e $a:=3^4 7^2 19^3$. Sapendo che $1897a\equiv_ m 1539$, si descriva l'insieme di tutte le soluzioni dell'equazione congruenziale $ax \equiv_m 1539$.
4. Si determini l'insieme di tutte le soluzioni dell'equazione congruenziale $12x\equiv_{34} 6$ e, quindi l'insieme di tutte le soluzioni dell'equazione diofantea $12x+34y=6$.
5. 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$
6. 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.
7. Nella 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).
8. Per ogni numero primo positivo $p$, sia $f_p$ il polinomio $\overline{22}x^5+\bar 8 x^4 - \bar7x^2+\bar 3$ a coefficienti nel campo $\Z_p$. Stabilire, per ogni primo $p$, qual è il grado di $f_p$. Per quali primi $p$ il polinomio $f_p$ è monico?

28/5

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

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

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

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. Se $A$ è un campo è sicuramente possibile effettuare la divisione per un qualsiasi polinomio non nullo.

Per l'anello dei polinomi su un campo: algoritmo euclideo per la ricerca di un MCD e Teorema di Bézout (informazione: questo teorema non vale in $\Z[x]$).

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

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

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

Caratterizzazione dei polinomi irriducibili su un campo $K[x]$; esistenza di radici ed irriducibilità.

Descrizione dei polinomi irriducibili sul campo reale e sul campo complesso (segue da questa descrizione che i polinomi di grado dispari in $\R[x]$ hanno sempre radici in $\R$. Polinomi in $\Q[x]$; criterio di irriducibilità di Eisenstein. Per ogni $n\in\N^*$ ed ogni primo $p$, $x^n+p$ è irriducibile in $\Q[x]$. Radici razionali di un polinomio $f\in\Z[x]$; se $f$ è monico tali radici sono intere. I risultati in questo paragrafo non sono stati dimostrati.

Esercizi proposti:

1. Sia $A$ un anello commutativo unitario. Verificare che l'anello dei polinomi $A[x]$ è infinito (Suggerimento: se $n$ e $m$ sono numeri naturali distinti, si può avere $x^n=x^m$?), Fornire un esempio di anello infinito di caratteristica 3.
2. Vero o falso: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.
3. Per ogni intero $n>1$ si consideri il polinomio $f_n=\overline{30}x^5+\overline{10}x^3+\overline{3}x^2+ \overline{6}\in\Z_n[x]$. Stabilire per quali $n$ il grado di $f_n$ è $5$ e trovare il grado di $f_n$ nei casi rimanenti.
4. Dividere, in ciascuno degli anelli $\Q[x]$ e $\Z_5[x]$ il polinomio $2x^4+1$ per $3x+2$ (nel secondo caso, ovviamente, i polinomi vanno riguardati come polinomi a coefficienti in $\Z_5[x]$).
5. Svolgere, almeno in parte, gli esercizi nr. 1, 2, 3 e 8 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo.
6. Provare che, qualunque sia l'anello commutativo $A$ ed $f$ un polinomio monico in $A[x]$, $f$ è cancellabile ma non invertibile in $\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.
7. Il polinomio $35x^{11}-6x^7+3x+15$ è irriducibile in $\Q[x]$? E $x^3+4$?
8. Si costruisca, se possibile, un polinomio di grado 500 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-20\le n \lt 100$.
9. Per ogni $n\in\N^*$, sia $f_n=(100+4n)x^4+(n+8)x^3+nx^2+1$ e sia $\bar {f_n}\in \Z_{11}[x]$ il polinomio $f_n$ riguardato come polinomio a coefficienti in $\Z_{11}[x]$. Sia $L=\{n\in\N^* \mid \nu \bar {f_n}=2\}$. Decidere se $L=\vuoto$ o $L\ne\vuoto$; nel secondo caso, posto $m=\min L$, scrivere l'associato monico di $\bar {f_m}$ in $\Z_{11}[x]$. Ripetere l'esercizio dopo aver ridefinito $f_n$ come $(100+4n)x^4+(n-8)x^3+nx^2+1$.
10. Tra i seguenti polinomi, dire quali sono e quali non sono irriducibili in $\Q[x]$ e quali sono e quali non sono irriducibili in $\R[x]$: $x^3+1$, $x^2+1$, $(10x^2+11)(x^2+2)$, $27x^8+100x^7+15$, $x^{896}-4^{896}$. Riguardati i polinomi precedenti a coefficienti in $\Z_5[x]$, dire quali sono irriducibili in $\Z_5[x]$.
11. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
12. I testi delle prove scritte contengono un gran numero di esercizi sui polinomi. Si guardino, ad esempio, gli esercizi 4 dal compito di gennaio 2015, 5 dal compito di ottobre 2016, 4 dal compito di maggio 2016, 4 dal compito di giugno 2016, 5 dal compito di ottobre 2016, 5 dal compito di gennaio 2017, 6 dal compito di maggio 2018.
13. Si trovino, in $\Z_5[x]$, tutti i polinomi monici irriducibili di secondo grado e tutti i polinomi di quarto grado che siano riducibili ma privi di radici. Quanti sono?

30/5

Una coda alla lezione precedente: nell'anello di polinomi $\Q[x]$, ogni polinomio è associato ad un polinomio a coefficienti interi. Su ogni anello commutativo unitario $A$, polinomi associati hanno sempre le stesse radici e, nel caso in cui $A$ sia fattoriale, stesse decomposizioni in prodotto di irriducibili, a meno di una costante invertibile.

Intervalli (aperti e chiusi) in un insieme ordinato; relazione di copertura definita da una relazione d'ordine. Nel caso finito, essa determina l'ordinamento (ma questo non è vero nel caso degli insiemi infiniti). Diagrammi di Hasse, con esempi.

Isomorfismi tra insiemi ordinati. Due insiemi ordinati finiti sono isomorfi se e solo se si possono rappresentare con lo stesso diagramma di Hasse. Esempio di un'applicazione biettiva crescente che non è un isomorfismo.

Minoranti e maggioranti di un sottoinsieme in un insieme ordinato. Esempi; tra questi: in $(\N,|)$ i minoranti (risp. maggioranti) di una parte $X$ sono gli insiemi dei divisori (risp. multipli) comuni degli elementi di $X$; se $A$ è un insieme e $X\subseteq\P(A)$, i minoranti ed i maggioranti di $X$ in $(\P(A),\subseteq)$ sono, rispettivamente i sottoinsiemi di $\bigcap X$ ed i sottoinsiemi di $A$ contenenti $\bigcup X$.

Estremo inferiore ed estremo superiore di una parte $X$ di un insieme ordinato $(S,\le)$ in $S$. Diversi esempi. In particolare: gli estremi inferiori e superiori in $(\N,\mid)$ ed in $(\P(A),\subseteq)$ per un insieme $A$ sono descritti da MCD e mcm nel primo caso, da intersezione ed unione nel secondo. Osservazioni (valgono ovviamente anche gli enunciati duali): l'estremo inferiore di $S$ in $(S,\le)$ è (l'eventuale) minimo di $S$; se $a=\inf_{(S,\le)} X$ allora i minoranti di $X$ in $S$ sono precisamente gli elementi minori o uguali ad $a$; se $X$ ha minimo allora questo è anche l'estremo inferiore di $X$ in $S$.

Reticoli. Definizione ed esempi. Il duale di un reticolo è necessariamente un reticolo; principio di dualità per reticoli. Sono reticoli tutti gli insiemi totalmente ordinati; $(\N,\mid)$ e, per ogni insieme $A$, $(\P(A),\subseteq)$ ed. Questi ultimi due sono reticoli completi (cioè reticoli in cui ogni sottoinsieme ha estremo inferiore ed estremo superiore). Un elemento minimale (risp. massimale) in un reticolo è necessariamente minimo (risp. massimo). Di conseguenza i reticoli finiti sono limitati, ciè hanno minimo e massimo, ma questo non è sempre vero per reticoli infiniti.

La limitatezza dei reticoli finiti non vuoti è stata dimostrata anche come conseguenza dell'enunciato che segue e del suo duale. Siano $(S,\sigma)$ un insieme ordinato e $A, B\subseteq S$. Supponiamo che esistano $a=\inf_{(S,\sigma)} A$ e $b=\inf_{(S,\sigma)}B$. Allora i minoranti di $A\cup B$ sono precisamente i minoranti di $\set{a,b}$; esiste $\inf_{(S,\sigma)}(A\cup B)$ se e solo se esiste $\inf_{(S,\sigma)}(\set{a,b})$ e, nel caso esistano, questi estremi inferiori coincidono. Enunciato duale per gli estremi superiori.

Le due operazioni (binarie) reticolari (meet/inf/$\land$ e join/sup/$\lor$). Loro proprietà algebriche (commutatività, associatività, leggi di assorbimento, iteratività). Reticoli come strutture algebriche. Equivalenza tra le nozioni di reticolo come insieme ordinato e di reticolo come struttura algebrica (in particolare: coincidenza tra le due possibili nozioni di isomorfismo); passaggio da un tipo di struttura all'altro tramite biezioni canoniche. Esempio particolarmente significativo: per un insieme $S$, le strutture $(S,\subseteq)$ e $(S,\cap,\cup)$.

Sottoreticoli. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

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

Esercizi proposti:

1. Determinare i minoranti ed i maggioranti di $\Pf(\N)$, l'insieme delle parti finite di $\N$, in $(\P(\N),\subseteq)$.
2. Esercizi da 5 e 7 di relazioni binarie, rimandando al futuro (prossimo) ciò che non è ancora stato definito a lezione.
3. Per ciascuno dei seguenti insiemi, ordinati per divisibilità (in $\N$), disegnare il diagramma di Hasse e decidere se si tratta o meno di un reticolo ed eventualmente di un sottoreticolo di $(\N,|)$: $\set{n\in\N\mid n\le 10}$, $\set{2^n\mid n\in\N}$, $\set{n\in\Div_\N(60)\mid n \text{ è pari}}$, $\set{1,2,3,5,45,60,900}$.
4. Sia $f\colon A\to B$ un'applicazione e sia $\beta$ una relazione d'ordine (largo) in $B$. Stabilire sotto quali condizioni la relazione binaria $\alpha$ definita in $A$ ponendo $(\forall x,y\in A)(x\mathrel\alpha y\iff f(x)\mathrel \beta f(y))$ è una relazione d'ordine.

4/6

Il contenuto di questa lezione è anche nelle mie note sulle strutture booleane.

Complementi di elementi in reticoli limitati. Esempi di elementi privi di complemento, con un solo complemento, con più complementi. In ogni reticolo limitato, il minimo ha il massimo come unico complemento e viceversa. Reticoli complementati; esempi. Sia in $(\N,\mid)$ che in un arbitrario reticolo totalmente ordinato e limitato, nessun elemento diverso da minimo e massimo ha complemento.

Reticoli distributivi. Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), le catene. Ciascuna delle due leggi distributive in un reticolo implica l'altra (senza dimostrazione). I sottoreticoli dei reticoli distributivi sono distributivi.

Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff. Esempi di uso (corretto e non) del criterio di Birkhoff.

Reticoli booleani. Algebre di Boole. Equivalenza tra queste due nozioni. Leggi di De Morgan ed altre proprietà in algebre di Boole. Sottoalgebre di Boole e loro caratterizzazione tra i sottoreticoli.

Costruzione di un'anello booleano a partire da un'algebra di Boole (ovvero, da un reticolo booleano) e construzione, inversa, di un'algebra di Boole a partire da un anello booleano (è stata verificata la correttezza solo di questa seconda costruzione). I sottoanelli unitari di un anello booleano sono le sottoalgebre della corrispondente algebra di Boole. Equivalenza te lo studio dei reticoli booleani, delle algebre di Boole, degli anelli booleani; coincidenza delle corrispondenti nozioni di isomorfismo.

Di conseguenza: teorema di Stone per reticoli booleani e per algebre di Boole, e sue conseguenze: i reticoli booleani finiti hanno per cardinalità una potenza di 2; due reticoli booleani finiti equipotenti sono necessariamente isomorfi (ed enunciati analoghi per le algebre di Boole).

Richiamo sulle funzioni caratteristiche. Cenni alla costruzione dell'anello $R^n$ delle $n$-ple di elementi di $R$ a partire da un anello $R$ e da un intero positivo $n$; quest'anello è booleano se $R$ è booleano e si può anche descrivere come anello costituito dalle applicazioni da $S=\set{1,2,\dots,n}$ a $R$. Identificazione delle "stringhe di zeri e uno" di fissata lunghezza $n$ con gli elementi dell'anello $\Z_2^n$ delle applicazioni da $S$ a $\Z_2$. L'applicazione che ad ogni parte di $S$ associa la sua funzione caratteristica è un isomorfismo di anelli (booleani) da $\P(S)$ a $\Z_2^n$. Interpretazione delle operazioni 'bit a bit' alla luce di questo isomorfismo.

Esercizi proposti:

1. Costruire un esempio di reticolo complementato con un sottoreticolo non complementato. Suggerimento: cercare una catena nel reticolo delle parti di un insieme.
2. Costruire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi e tutti gli altri elementi hanno esattamente un complemento.
3. Svolgere l'esercizio 3 dal compito del 18 marzo 2014.
4. Completare gli esercizi da relazioni binarie.
5. Scrivere esplicitamente un isomorfismo tra il reticolo dei divisori di 30 (ordinato per divisibilità) e quello delle parti di un insieme di cardinalità 3 (leggendo i riferimenti al diagramma di Hasse di un'algebra di Boole come riferiti al corrispondente reticolo booleano).
6. Di due reticoli booleani $L$ e $M$ sappiamo che hanno entrambi cardinalità compresa tra 400 e 900. Che conclusioni possiamo trarre? Possiamo, in particolare, stabilire se $L$ e $M$ sono isomorfi?
7. Di un reticolo $L$ sappiamo che è complementato e che ha esattamente 675 elementi. possiamo stabilire se è distributivo?
8. Sia $R$ l'insieme delle parti $X$ di $\N$ tali che o $X$ o $\N\setminus X$ sia finito. Dimostrare che $R$ è un sottoanello unitario dell'anello delle parti di $\N$, e quindi un anello booleano. Questo esempio è di particolare interesse perché si può dimostrare (ma non si chiede qui di farlo) che $R$ non è isomorfo all'insieme delle parti di $S$ per alcun insieme $S$.
9. Stabilire per quali $n\in\set{0,15,16,20,15\cdot 77}$ il reticolo dei naturali divisori di $n$ (ordinato per divisibilità in $\N$) è booleano.

6/6

Rapido cenno ad applicazioni delle algebre di Boole in logica.

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

Isomorfismi tra grafi (o tra multigrafi); proprietà che questi conservano. Esempi di grafi isomorfi e non, tecniche di costruzione di isomorfismi. Elenco, a meno di isomorfismi, dei grafi su al più quattro vertici. Sottografi.

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

Nozione di grafo planare (ovvero: piano). Grafi bipartiti ed enunciato del teorema di Kuratowski.

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

Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari (solo enunciato). Esempi, tra cui il problema dei sette ponti di Königsberg.

Foreste e alberi. Teorema: un grafo finito $G$ è una foresta se e solo se per ogni coppia $(a,b)$ di vertici distinti di $G$ esiste al più un cammino in $G$ da $a$ a $b$. Corrispondente caratterizzazione degli alberi.

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

Rappresentazione radicale di un albero; foglie. In ogni albero finito con almeno due vertici esistono almeno due vertici di grado uno.

Lemma: il sottografo ottenuto da un albero cancellandone un vertice di grado uno ed il lato esso incidente è ancora un albero.

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

Esercizi proposti:

1. Esercizi da Grafi, ad esclusione del nr. 4.
2. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) connessi su cinque vertici. Indentificare tra questi gli alberi.
3. Utilizzando la rappresentazione radicale di un albero, provare che le foreste finite sono grafi planari.
4. Si considerino i grafi $G=(V,L)$ che verificano la proprietà $\Phi$: “$|V|=6=|L|$ ed esistono in $G$ (almeno) due vertici di grado 3 ed (almeno) tre vertici di grado 2”.
   1. Se un grafo $G$ verifica $\Phi$, quali sono i gradi dei suoi vertici?
   2. Disegnare, se possibile, un grafo che verifichi $\Phi$.
   3. Disegnare, se possibile, due grafi tra loro non isomorfi che verifichino $\Phi$.
   4. Disegnare, se possibile, un grafo non connesso che verifichi $\Phi$.
   5. Disegnare, a meno di isomorfismi, tutti i grafi che verificano $\Phi$.