16/9

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

Introduzione molto informale alle nozioni di linguaggio, formula, proposizione (o formula chiusa), sintassi e semantica. Comparazione tra linguaggio (semi)formalizzato e linguaggio non formalizzato.

Alcuni connettivi proposizionali, descritti solo semanticamente: negazione, congiunzione, disgiunzione inclusiva, disgiunzione esclusiva (XOR), congiunzione negata (NAND), equivalenza (o bicondizionale: se e solo se). Comparazione tra il loro uso e quello di espressioni corrispondenti nel linguaggio naturale. Forme proposizionali. Tabelle (o tavole) di verità, con esempi del loro uso in calcolo proposizionale.

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.

Avviso importante: Ho detto in aula che la lezione di lunedì prossimo (23) non si sarebbe tenuta per indisponibilità dell'aula. Per fortuna la situazione è cambiata: gli uffici preposti mi hanno appena comunicato che è venuta meno la ragione di questa indisponibilità, quindi, contrariamante a quanto annunciato (e salvo ulteriori sorprese), la lezione del 23 si terrà regolarmente.

Esercizi proposti:

1. Scrivere tavole di verità per le forme proposizionali $p\land p$,  $p\Leftrightarrow p$,  $p\land(p\lor q)$,  $(p\land(p\lor q))\Leftrightarrow p$,  $p\lor(p\land q)$,  $\lnot (p\lor q)$,  $(\lnot p)\lor q $.
2. Da Logica rudimentale, esercizio B4: punti (a) e (b).

18/9

Discussione di esercizi dalla lezione precedente. Forme (proposizionali) logicamente equivalenti tra loro. Tautologie e contraddizioni. Diversi esempi di tautologie, tra le quali quella della doppia negazione, il principio del terzo escluso, il principio di non contraddizione, le tautologie di commutatività per i connettivi $\land$, $\lor$, $\shiff$ e $\xor$; di iteratività (o idempotenza) per $\land$ e $\lor$; di associatività per $\land$, $\lor$, $\shiff$ e $\xor$; di idempotenza per $\land$ e $\lor$. Negazione di una equivalenza (in diverse forme).

Connettivo di implicazione (o condizionale). Discussione sul suo utilizzo, sugli errori più comuni nei quali si rischia di cadere e sulle espressioni verbali che lo esprimono nel linguaggio corrente e nel linguaggio matematico. Tautologie sull'implicazione: equivalenza come doppia implicazione, implicazione come disgiunzione, negazione di un'implicazione.

Continuano ad essere utili le note segnalate nel resoconto della scorsa lezione.

Esercizi proposti:

1. Da Logica rudimentale, svolgere (o completare) gli esercizi B.3, B.4 e B.5 (non che gli altri siano dannosi per la salute …).
2. Verificare, possibilmente senza usare tavole di verità come in Logica rudimentale, le tautologie $p\land (q\lor r)\shiff (p\land q)\lor (p\land r)$ e $p\lor (q\land r)\iff (p\lor q)\land (p\lor r)$ (distributività di $\land$ rispetto a $\lor$ e di $\lor$ rispetto a $\land$).
3. La forma proposizionale $(p\shiff p)\shiff p$ è una tautologia, una contraddizione oppure una forma contingente (cioè né una tautologia né una contraddizione)? 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. La forma proposizionale $\bigl(q\shiff r\bigr)\iff \bigl((p\land q)\shiff(p\land r)\bigr)$ è una tautologia?
5. (Un po' più difficile) Esercizio C.3 da Logica rudimentale.

20/9

Discussione di esercizi dalla lezione precedente (in particolare: comparazioni tra espressioni verbali e formule; tautologie della distributività di $\land$ rispetto a $\lor$ e viceversa). Altre tautologie: distributività della congiunzione rispetto alla disgiunzione esclusiva; transitività dell'implicazione; legge di contrapposizione; leggi di De Morgan (negazioni di congiunzioni e disgiunzioni).

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

Cenni alla logica dei predicati. Variabili, quantificatori universale ed esistenziale: sintassi essenziale ed interpretazione. Occorrenze libere o vincolate di variabili. Formule chiuse. Predicati unari in una variabile.

Esercizi proposti:

1. Abbiamo provato la distributività di $\land$ rispetto a $\xor$. Decidere se anche $\lor$ è distributivo rispetto a $\xor$, vale a dire, se $\big(p\lor (q\xor r)\big)\iff \big((p\lor q)\xor (p\lor r)\big)$ è una tautologia. Analogamente, $\lor$ è distributivo rispetto a $\shiff$? Ovvero: $\big(p\lor (q\shiff r)\big)\iff \big((p\lor q)\shiff (p\lor r)\big)$ è una tautologia?
2. Da Logica rudimentale, svolgere tutti gli esercizi D. Svolgere poi (o leggere) gli esercizi e le osservazioni E e, possibilmente, F.1.
3. Verificare (alcune tra) le tautologie in esempi di tautologie.
4. Vero o falso? $1+1=11 \implica 44^2=3$.
5. Negare: “Se domani piove e l'auto funziona, o andremo a casa oppure mangeremo un gelato”.
6. Negare la forma proposizionale $(p\land q)\implica (r\lor s)$.
7. Decidere, tra queste formule nel linguaggio dell'aritmetica, quali sono chiuse (cioè proposizioni) e quali sono predicati unari:
   1. $\forall x (x+1=y)$
   2. $\forall x(\exists y(x+1=y))$
   3. $\forall x(\exists y(x+1=y))\land x=y^2$
   4. $\forall x(\exists y(x+1=y)\land x=y^2)$

23/9

Discussione di esercizi dalla lezione precedente.

Approfondimenti sull'uso delle variabili e sulla distinzione tra le loro occorrenze libere e vincolate. Sostituzioni di termini a variabili (vengono sostituite solo le occorrenze libere).

Il quantificatore $\exists!$.

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

Alcune regole della logica dei predicati. Frasi contenenti più quantificatori; comparazione tra formule del tipo $\forall x(\exists y(\dots))$ e del tipo $\exists y(\forall x(\dots))$. Negazione di formule universali e di formule esistenziali (anche nel caso dei quantificatori ristretti).

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

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

Esercizi proposti:

1. Svolgere quanti più è possibile tra gli esercizi H di Logica rudimentale. Non tralasciare H.3.
2. Negare: Ogni mucca verde mangia cioccolata.
3. Negare: Ogni mese, se mi arriva la bolletta del gas la pago.
4. Negare: $\exists x (\forall y (\varphi(x,y)))\implica \forall x(\exists y (\psi(x,y)))$, dove $\varphi$ e $\psi$ sono formule.
5. Vero o falso?: $(\forall x\in\vuoto)(x\ne x)$.
6. Vero o falso?: $\set{2,3,1,2,3}=\set{1,3,2}$.
7. Assegnati in qualche modo gli oggetti $a,b,c$, si può dire quanti elementi ha l'insieme $\set{a,b,c}$ i cui elementi sono (tutti e soli) $a$, $b$ e $c$?

25/9

Discussione di esercizi dalla lezione precedente.

I singleton. Definizione di inclusione. Sottoinsiemi (o parti) di un insieme. Comparazione tra inclusione e appartenenza: è importante distinguere bene tra queste due nozioni, così come tra un insieme $x$ ed il suo singleton $\set x$; ad esempio tra $\vuoto$ e $\set\vuoto$. Alcuni esempi: per ogni $x$ si ha $\vuoto\subseteq x$ e $x\subseteq x$, ma $x\notin x$.

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

Esempi ed esercizi sulla descrizione di insiemi.

Comparazione tra i connettivi di equivalenza e implicazione, da una parte, e le relazioni di uguaglianza e inclusione tra insiemi dall'altra.

Si prenda nota dell'avviso nella pagina del corso: venerdì non ci sarà lezione, e probabilmente neanche lunedì.

Esercizi proposti:

1. Decidere se esistono e, nel caso, descrivere esplicitamente gli insiemi $\set{x\mid \forall y (x= y)}$, $\set{x\mid \forall y (x\ne y)}$, $\set{x\mid \exists y (x= y)}$, $\set{x\mid \exists y (x\ne y)}$, $\set{x\mid x=\vuoto}$, $\set{x\mid \forall y (y\subseteq x)}$, $\set{x\mid \forall y (x\subseteq y)}$, $\set{x\mid \forall y (x\in y)}$, $\set{x\mid \forall y (x\notin y)}$, $\set{x\mid \forall y (y\notin x)}$, $\set{x\mid x=\set{0,1,2}}$, $\set{y\mid y=\set{0,1,2}}$, $\set{x\mid x=\set{0,1,2,x}}$.
2. Sia $x=\set{\set{\set{\set\vuoto}}}$. Quanti elementi ha $x$? Quante parti ha $x$?
3. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto\subset\vuoto$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{2,1,3}$; $\set{1,1,2,2,2,3,3}$ è una parte di $\set{4,2,1,3}$.
4. Un assioma della teoria degli insiemi garantisce che, per ogni insieme $x$ esiste l'insieme $\P(x)=\set{y\mid y\sseq x}$ (che si chiama l'insieme delle parti di $x$). Descrivere $\P(\vuoto)$, $\P(\set 1)$, $\P(\set {1,1})$ e $\P(\set {1,2})$.
5. Svolgere gli esercizi 1, 2 e 4 da questa versione della prova in itinere del novembre 2019.
6. Elencare gli elementi di questi insiemi: $x=\set{a\in\N\mid a\le 12 \land a>7}$; $y=\set{a\in\N\mid a \gt 2 \implica a^2=3}$; $z=\set{a\in\N\mid a \lt 2 \land a \ge 33}$; $t=\set{a\in\N\mid a = a+4}$.

2/10

Discussione di molti esercizi dalla lezione precedente. Inclusione stretta. L'insieme $\P(x)$ delle parti di un insieme $x$; tra i suoi elementi ci sono sicuramente $\vuoto$ e $x$. Esempi: oltre a quelli visti tra gli esercizi, $\P(\set{1,2,3})$. Terminologia: per ogni $n\in\N$, e per ogni $x$, $\P_n(x)$ è l'insieme delle parti di $x$ che hanno esattamente $n$ elementi.

Alcune operazioni insiemistiche (unione ed intersezione binarie, differenza simmetrica, differenza insiemistica (detta anche complemento relativo), e loro proprietà ricavate a partire da tautologie. (come nella sezione finale di Logica rudimentale, e in Tautologie e identità insiemistiche). Illustrando il metodo generale, abbiamo tra l'altro discusso le formule di commutatività e associatività per le operazioni di unione e intersezione binarie e per la differenza simmetrica; di idempotenza per le prime due (verificando anche: $\forall a(a\ds a=\vuoto)$), la distributività dell'intersezione rispetto all'unione ed alla differenza simmetrica e dell'unione rispetto all'intersezione, le forme esplicite per la diferenza simmetrica (per ogni $a,b$ si ha $a\ds b=(a\cup b)\setminus (a\cap b)=(a\setminus b)\cup(b\setminus a)$) ed inoltre formule che coinvolgono la differenza insiemistica, tra cui le formule insiemistiche di De Morgan.

Diagrammi di Euler-Venn (o semplicemente di Venn); alcuni esempi; diagrammi di Venn generici. Utilizzando diagrammi di Venn generici è possibile dimostrare formule insiemistiche.

Esercizi proposti:

1. Dimostrare che per ogni $a,b$ sono equivalenti tra loro: (1): $a\subseteq b$; (2): $a\cap b=a$; (3): $a\cup b=b$.
2. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
3. Descrivere, per un arbitrario insieme $a$, $a\ds\vuoto$ e, più in generale, se $b$ è un sottoinsieme di $a$, $a\ds b$.
4. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\setminus(b\setminus c)$ e $(a\setminus b)\setminus c$. Decidere se è vera o falsa la proposizione: $(\forall a,b,c) \big(a\setminus(b\setminus c)=(a\setminus b)\setminus c\big)$.
   Ripetere l'esercizio per $a\cap(b\setminus c)$ e $(a\cap b)\setminus c$.
5. Rappresentare, sempre in un diagramma di Venn generico, $a\ds(b\ds c)$. Confrontare il risultato con quanto visto nella lezione del 18 settembre discutendo delle tautologie di associatività per i connettivi $\shiff$ e $\xor$ (quando è che la forma proposizionale $p\xor(q\xor r)$ vale vero?)
6. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\setminus(b\ds c)$ e $(a\ds b)\setminus c$.
7. Abbiamo verificato a lezione alcune formule che esprimono proprietà distributive, in cui appaiono $\cap$, $\cup$ o $\ds$. Tra queste, manca la proprietà distributiva di $\cup$ rispetto a $\ds$. In effetti, questa non l'abbiamo dimostrata perché non vale, cioè: la formula $(\forall a,b,c)$$\big(a\cup(b\ds c)=(a\cup b)\ds(a\cup c)\big)$ è falsa. Verificarlo utilizzando diagrammi di Venn. Confrontare questo esercizio con il primo esercizio della lezione del 20/9.
8. Svolgere il terzo esercizio da questa versione della prova in itinere del novembre 2019.
9. Esercizio J.3 da Logica rudimentale.

4/10

Ampia discussione di esercizi dalla lezione precedente.

Formule di De Morgan per unione e intersezione binarie.

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

È stato finalmente reso noto che le lezioni di mercoledì 9 si potranno tenere regolarmente. Dunque la prossima settimana faremo lezione sia lunedì che mercoledì all'orario usuale (8:30–10:30), e poi venerdì dalle 14 alle 16.

Esercizi proposti:

1. Esercizio J.5 da Logica rudimentale.
2. Calcolare $\bigcup A$ e $\bigcap A$ in ciascuno dei seguenti casi: (1) $A=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $A$ è l'insieme delle parti finite di $\N$; (3) $A$ è l'insieme delle parti infinite di $\N$; (4) $A=\set{x\subseteq\N\mid 13\notin x}$; (5) $A=\set{x\subseteq\N\mid 13\in x}$; (6) $A=\big\{\set{124,n}\mid n\in\N\big\}$; (7) $A=\set{[n-1,n+1]\mid n\in\N}$, dove, si ricorda, per ogni coppia $a,b$ di numeri reali, $[a,b]=\set{x\in\R\mid a\le x\le b}$ è l'insieme dei numeri reali compresi tra $a$ e $b$.
3. Svolgere l'esercizio nr. 6 da questa raccolta ("per le vacanze di pasqua").
4. Calcolare $\bigcup \vuoto$, $\bigcup\set{\vuoto}$, $\bigcap\set{\vuoto}$, e poi $\bigcup\set{x}$ e $\bigcap\set{x}$ per un arbitrario insieme $x$.
5. Verificare le formule di De Morgan (anche) usando diagrammi di Venn.

7/10

Discussione di esercizi dalla lezione precedente.

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

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

Corrispondenze tra due insiemi. Grafico di una corrispondenza. Diversi modi per rappresentare le corrispondente (tramite diagrammi o tabelle). Relazioni binarie in un insieme. Notazioni: per insiemi $A$ e $B$, $\Corr(A,B)$ indica l'insieme delle corrispondenze da $A$ a $B$; $\Rel(A)=\Corr(A,A)$ quello delle relazioni binarie in $A$.

Prodotto relazionale tra corrispondenze: definizione ed esempi.

Esercizi proposti:

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

9/10

Discussione di esercizi dalla lezione precedente.

Se $a$ e $b$ sono insiemi finiti, $a$ ha (esattamente) $n$ elementi e $b$ ha (esattamente) $m$ elementi, allora $a\times b$ ha (esattamente) $nm$ elementi.

Descrizione di corrispondenze tramite condizioni che ne caratterizzano il grafico. Sintassi alternativa per la descrizione di un insieme.

Associatività del prodotto relazionale, con esempi.

Applicazioni (o funzioni) tra due insiemi (notazioni: $\Map(A,B)$, o anche $B^A$, è l'insieme delle applicazioni da $A$ a $B$). Descrizioni di applicazioni nella forma $\dots\in A\mapsto\dots\in B$. Il problema della "buona definizione" di un'applicazione. Diversi esempi di applicazioni e di corrispondenze che non sono applicazioni.

Per un'applicazione $f$: dominio e codominio di $f$; immagine $f(x)$ di un elemento $x$ del dominio di $f$ (cenni a notazioni alternative). Descrizione esplicita del grafico di un'applicazione.

Applicazioni costanti. Restrizioni e prolungamenti di un'applicazione (se $f\colon A\to B$ è un'applicazione e $X\sseq A$, la restrizione di $f$ e $X$ è l'applicazione $f_{|X}\colon a\in X\mapsto f(a)\in B$; un prolungamento di $f$ è un'applicazione di cui $f$ sia una restrizione).

Si ricorda che venerdì faremo lezione non di mattina, ma di pomeriggio, dalle 14 alle 16..

Esercizi proposti:

1. Siano $\alpha$ e $\bar\alpha$ le corrispondenze da $\Z$ a $\P(\Z)$ definite ponendo, per ogni $n\in\Z$ e $X\in \P(\Z)$; $\quad n\mathrel{\alpha}X\iff n\in X$ e $n\mathrel{\bar\alpha}X\iff n\notin X$. Sia poi $\beta$ la relazione di inclusione in $\P(\Z)$, cioè la relazione binaria in $\P(\Z)$ definita ponendo, per ogni $X,Y\in\P(\Z)$, $X\mathrel{\beta}Y\iff X\sseq Y$. Descrivere $\alpha\beta$ e $\bar\alpha\beta$.
2. Si considerino l'applicazione $f\colon n\in\Z\mapsto\set n\in\P(\Z)$ e la corrispondenza $\beta$ dell'esercizio precedente. Si descriva il prodotto relazionale $f\beta$.
3. Quali tra queste sono applicazioni ben definite? Qui $P=\P(\Z)\setminus\set\vuoto$ è l'insieme delle parti non vuote di $\Z$.
   • $n\in\Z\mapsto n^2/2\in\Z$;
   • $X\in P\mapsto \min X\in\Z$;
   • $X\in P\mapsto \Z\setminus X\in P$;
   • $X\in \P(\Z)\mapsto X\cap\N\in\P(\N)$;
   • $X\in \P(\Z)\mapsto X\ds\N\in\P(\N)$;
4. Tra le corrispondenze elencate nell'esercizio 7 di quelli per le vacanze di pasqua, quali sono applicazioni?

11/10

Discussione di molti esercizi dalle lezioni precedenti.

L'immagine $\im f=\set{f(a)\mid a\in A}\sseq B$ di un'applicazione $f\colon A\to B$. Applicazioni suriettive. Un'applicazione $f\colon A\to B$ è suriettiva (cioè: $\im f=B$) se e solo se: per ogni $y\in B$ esiste $x\in A$ tale che $f(x)=y$. Negazione della suriettività. Diversi esempi ed esercizi, con discussione sui possibili errori e preghiera di non duplicarli. Ridotta di un'applicazione alla sua immagine.

Il prodotto relazionale tra due applicazioni $f\colon A\to B$ e $g\colon B\to C$ è ancora un'applicazione (da $A$ e $B$): l'applicazione composta $g\circ f$. Sua descrizione esplicita.

Esercizi proposti:

1. Completare l'esercizio 7 di quelli per le vacanze di pasqua, indicando quali delle applicazioni che vi appaiono sono suriettive. Descrivere le immagini delle applicazioni in (iii), (iv) e (xiii).
2. Sia $f\colon (a,b)\in\N\times\N\mapsto a+b\in\N$ (è la consueta operazione di addizione in $\N$). Decidere se $f$ è suriettiva.
3. Sappiamo che esiste un'applicazione suriettiva e costante da $\N$ ad un certo insieme $A$. Cosa possiamo dire su $A$?
4. Per quali sottoinsiemi $X$ di un assegnato insieme $A$ l'applicazione $x\in X\mapsto x\in A$ (che si chiama immersione di $X$ in $A$) è suriettiva?
5. Sia $f\colon A\to B$ un'applicazione, sia $X\sseq A$ e sia $\iota\colon X\to A$ l'applicazione immersione di $X$ in $A$ definita nell'esercizio precedente. Verificare che la restrizione $f_{|X}$ coincide con $f\circ\iota$.
6. Date le applicazioni $f\colon n\in\Z\mapsto n+1\in\Z$ e $g\colon n\in\Z\mapsto n^2\in\Z$, descrivere esplicitamente $g\circ f$ e $f\circ g$.
7. Date le applicazioni $f\colon x\in\P(\Z)\mapsto x\cap\N\in\P(\Z)$ e $g\colon n\in\Z\mapsto \set n\in\P(\Z)$, descrivere esplicitamente $f\circ g$.
8. Di ciascuna delle applicazioni che appaiono negli esercizi di questa lezione e della precedente, stabilire se è o meno suriettiva.

14/10

Discussione di esercizi dalle lezioni precedenti. Per una parte $X$ di un insieme $A$: immersione $\iota\colon x\in X\mapsto x\in A$ di $X$ in $A$. L'applicazione identica $\id_A\colon x\in A\mapsto x\in A$. L'immersione $\iota$ è una restrizione di $\id_A$ e, viceversa, $f_{|X}=f\circ\iota$ per ogni applicazione $f$ di dominio $A$.

Applicazione immagine $\vecf\colon\P(A)\to\P(B)$ ed applicazione antiimmagine $\avecf\colon\P(B)\to\P(A)$ definite da un'applicazione $f\colon A\to B$, ponendo $\vecf(X)=\set{f(x)\mid x\in X}=\im(f_{|X})$ per ogni $X\in\P(A)$ e $\avecf(Y)=\set{a\in A\mid f(a)\in Y}$ per ogni $Y\in\P(B)$. Esempi. Si ha: $\vecf (\vuoto)=\avecf(\vuoto)=\vuoto$, $\vecf(A)=\im f$, $\,\avecf (B)=\avecf (\im f)=A$ e, per ogni $X\sseq A$, $\vecf(X)=\im (f_{|X})$.

Siano $f\colon A\to B$ e $g\colon B\to C$ applicazioni. Se $f$ e $g$ sono suriettive, allora $g\circ f$ è suriettiva; se $g\circ f$ è suriettiva allora $g$ è suriettiva. $f$ è suriettiva se e solo se $\avecf(\set y)\ne\vuoto$ per ogni $y\in B$.

Sezioni di un'applicazione. Esempi. Un'applicazione è suriettiva se e solo se ammette sezioni.

Esistono in questo sito delle note su sezioni e retrazioni (il secondo argomento non è stato ancora introdotto) che consiglio di leggere (almeno in parte), tenendo però in conto che le notazioni lì usate non sono quelle seguite nel corso e che molto del materiale lì contenuto non ci riguarda necessariamente. In particolare, rispetto al corso:

1. le note usano una diversa notazione per la composizione di applicazioni: se $f\colon A\to B$ e $g\colon B\to C$ sono applicazioni componibili, nelle note la loro composta $g\circ f$ è scritta sempre come $fg$;
2. le note usano la notazione esponenziale per l'immagine di un elemento mediante un'applicazione: $a^f$ piuttosto che $f(a)$ come nel corso;
3. non fa parte del programma l'enunciato 5 né ciò che segue l'eunciato 8.

Applicazioni iniettive. Definizione in due forme equivalenti. Negazione dell'iniettività: un'applicazione $f\colon A\to B$ è non iniettiva se e solo se: $(\exists x,y\in A)$$(x\ne y\land f(x)=f(y))$. Di conseguenza, le applicazioni il cui dominio ha meno di due elementi sono certamente iniettive.

Esercizi proposti:

1. Provare che, se $f\colon A\to B$ è un'applicazione, allora $X\sseq\avecf(\vecf (X))$ per ogni $X\in\P(A)$ e $\vecf(\avecf (Y))\sseq Y$ per ogni $Y\in\P(B)$ (queste inclusioni possono essere strette). I più coraggiosi possono provare a verificare che $\vecf(\avecf (Y))=Y\cap\im f$ per ogni $Y\in\P(B)$.
2. Dati gli insiemi $A$ e $B$, verificare che, per ogni $\alpha\in\Corr(A,B)$, si ha $\alpha\id_B=\alpha=\id_A\alpha$.
3. Siano $A=\set{1,2}$ e $B=\set{1,2,3}$. Scrivere due diversi prolungamenti a $B$ dell'immersione di $A$ in $B$ (si richiedono, in altri termini, due applicazioni $B\to B$ che abbiano l'immersione di $A$ in $B$ come restrizione).
4. Estendere l'esercizio 7 di quelli per le vacanze di pasqua, indicando quali delle applicazioni che vi appaiono sono iniettive.
5. Siano $f\colon n\in\Z\mapsto 1+n^2\in\Z$ e $X=\set{n\in\N\mid n\le 10}$. Calcolare $\vecf(X)$, $\avecf (X)$, $\avecf(\vecf(X))$ e $\vecf(\avecf(X))$.
6. Sia $f\colon x\in\P(\Z)\mapsto x\cup\N\in\P(\Z)$. Descrivere $\vecf(\P(\N))$ e $\avecf(\set\vuoto)$.
7. Di tutte le applicazioni che appaiono negli esercizi di queste ultime lezioni, stabilire se sono iniettive.
8. Sia $f\colon \set{0,1,2}\to\set{1,2}$ l'applicazione definita da $f(0)=f(1)=1$ e $f(2)=2$. Scrivere tutte le sezioni di $f$.
9. Sia $v\colon n\in\Z\mapsto|n|\in\N$ (qui $|n|$ indica il valore assoluto dell'intero $n$, cioè $n$ se $n\in\N$, $-n$ se $n\notin\N$). Scrivere tre sezioni di $v$.

16/10

Discussione di esercizi dalle lezioni precedenti.

Applicazioni biettive. Ulteriori esercizi ed esempi sull'iniettività e la biettività. Le applicazioni identiche sono biettive; le restrizioni delle applicazioni iniettive sono iniettive, ad esempio lo sono le immersioni. Inoltre: un'applicazione $f\colon A\to B$ è iniettiva se e solo se per ogni $y\in B$ l'insieme $\avecf(\set y)$ ha al massimo un elemento, ovvero se e solo se per ogni $y\in\im f$, $\avecf(\set y)$ è un singleton.

Proprietà di neutralità delle applicazioni identiche: se $f\colon A\to B$ è un'applicazione, $f\circ\id_A=f=\id_B\circ f$.

Retrazioni di un'applicazione $f\colon A\to B$, cioè applicazioni $r\colon B\to A$ tali che $r\circ f=\id_A$. Ogni applicazione iniettiva con dominio non vuoto ammette retrazioni.

Se $f\colon A\to B$ e $g\colon B\to C$ sono applicazioni (componibili), si ha:

• se $f$ e $g$ sono entrambe iniettive $g\circ f$ è iniettiva;
• se $f$ e $g$ sono entrambe biettive $g\circ f$ è biettiva;
• se $g\circ f$ è iniettiva, allora $f$ è iniettiva;
• se $g\circ f$ è biettiva, allora $f$ è iniettiva e $g$ è suriettiva.

Esercizi proposti:

1. Si considerino le tre applicazioni $\alpha$, $\beta$ e $\gamma$ da $\Z$ a $\Z$ definite come segue; di ciascuna di esse si decida se è iniettiva e nel caso, si scriva una retrazione: $\alpha\colon n\mapsto 3n+1$; $\beta\colon n\mapsto 2-n$; $\gamma\colon n\mapsto\begin{cases}\alpha(n),&\text{se }n\ge 0\\\beta(n),&\text{se }n\lt0\end{cases}$.
2. Si ripeta lo stesso esercizio per le applicazioni: $h\colon n\in\Z\mapsto \set {1,n}\in\P(\Z)$, $k\colon n\in\Z\mapsto \set {1,2,n}\in\P(\Z)$, $\ell\colon x\in\P(\Z)\mapsto \Z\setminus x\in\P(\Z)$ e $m\colon x\in\P(\Z)\mapsto \N\setminus x\in\P(\Z)$.
3. Si verfichi che l'applicazione $n\in\Z\mapsto\begin{cases}2n-1,&\text{se }n\gt0\\-2n,&\text{se }n\le0\end{cases}\in\N$ è biettiva.
4. Si verfichi che l'applicazione $n\in\N\mapsto \begin{cases}-n/2,&\text{se }n\text{ è pari}\\(n+1)/2,&\text{se }n\text{ è dispari}\end{cases}\in\Z$ è biettiva.
5. Svolgere l'esercizio 8 in esercizi per le vacanze di pasqua, decidendo anche quali delle applicazioni che vi appaiono sono iniettive.
6. Svolgere l'esercizio 7 da questa versione della prova in itinere del novembre 2019.
7. Svolgere gli esercizi 3 (escluso il punto f) e 4 di Tautologie, insiemi, aritmetica (attenzione: qui $fg$ va letto come $g\circ f$).
8. Verificare quanto segue, come facile conseguenza delle definizioni e per il primo punto, dell'ultimo risultato della lezione (e del risultato analogo visto alla lezione precedente) per il secondo:
   • dire che una applicazione $f$ è una sezione di una applicazione $g$ equivale a dire che $g$ è una retrazione di $f$;
   • qualsiasi sia l'applicazione $f$, ogni sezione di $f$ è iniettiva ed ogni retrazione di $f$ è suriettiva.

18/10

Discussione di esercizi dalle lezioni precedenti; osservazioni su sezioni e retrazioni tratte dagli esercizi.

Teorema: un'applicazione $f\colon A\to B$ è iniettiva se e solo se $A=\vuoto$ o $f$ ammette retrazioni.

Applicazione inversa di un'applicazione (cioè: applicazione che sia una sezione ed una retrazione). 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$.

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

Descrizione esplicita dell'inversa di un'applicazione biettiva. Esempi ed esercizi. (Notazione: si indica con $f^{-1}$ l'inversa dell'applicazione biettiva $f$.)

Operazioni binarie (ovunque definite) in un insieme. Definizione ed esempi.

Esercizi proposti:

1. Si verifichi che le applicazioni agli esercizi 3 e 4 della lezione scorsa sono l'una inversa dell'altra. Attenzione: chiamando le due applicazioni, nell'ordine, $f$ e $g$, occorre verificare sia $f\circ g=\id_{\N}$ che $g\circ f=\id_{\Z}$. Ad esempio, verificare solo la prima uguaglianza permetterebbe di giustificare solo l'iniettività di $g$ e la suriettività di $f$. Perché?
2. Sia $f$ una delle applicazioni in (ii), (vi) o (vii) nell'esercizio 7 di quelli per le vacanze di pasqua. Verificare che $f\circ f$ è un'applicazione identica; dedurne che $f$ è biettiva e $f^{-1}=f$.
3. Supponiamo di sapere, a proposito di una certa applicazione $f$ di un insieme $A$ in sé, che $(f\circ f)\circ f=\id_A$. Possiamo concludere che $f$ è biettiva?
4. Svolgere l'esercizio 8 in esercizi per le vacanze di pasqua, decidendo anche quali delle applicazioni che vi appaiono sono iniettive.
5. Svolgere l'esercizio 7 da questa versione della prova in itinere del novembre 2019.
6. Svolgere gli esercizi 7 e 8 da questa versione della prova in itinere dell'aprile 2019.
7. Estendendo alcuni esempi fatti a lezione, dire quali di queste espressioni definiscono (informalmente) operazioni binarie (ad esempio: "moltiplicazione in $\Z$" definisce l'operazione $(a,b)\in\Z\times\Z\mapsto ab\in\Z$; la "sottrazione in $\N$" non è ben definita): "divisione in $\Z$"; "divisione in $\Q$"; "divisione in $\Q^*=\Q\setminus\set 0$"; "elevazione a potenza in $\N$"; "elevazione a potenza in $\Z$"; "differenza simmetrica in $\P(\N)$"; "composizione di applicazioni in $\Map(\N,\Z)$"; "composizione di applicazioni in $\Map(\N,\N)$".
8. Cercare gli errori di battitura nella pagina di informazioni sulla prova in itinere.

21/10

Discussione di esercizi dalle lezioni precedenti.

Operazioni binarie commutative ed associative. Nozione di struttura algebrica; semigruppi. Diversi esempi ed esercizi. Tavola di Cayley di un'operazione binaria.

Elementi neutri a sinistra e a destra; elementi neutri. Loro visualizzazione nelle tavole di Cayley. Unicità dei neutri: se, in una assegnata struttura, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, inoltre $s$ è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura. Discussione sulle conseguenze di quest'ultimo teorema; esempi e controesempi.

Monoidi. Diversi esempi, tra i quali il monoide $T(A)=(A^A,\circ,\id_A)$ delle trasformazioni di un insieme ed il monoide delle parole su un alfabeto come esempi di monoidi generalmente non commutativi. Il primo è commutativo se e solo se $A$ ha al massimo un elemento.

Esercizi proposti:

1. Siano dati gli insiemi $A$, $B$ e $C$, ed inoltre $b\in B$, un'applicazione $f\colon B\to C$ e l'applicazione costante $c_b\colon a\in A\mapsto b\in B$. Descrivere l'applicazione $f\circ c_b$. Questa è costante?
2. Verificare che, come detto a lezione, per ogni insieme $S$ le operazioni $*$ e $\bullet$ definite in $S$ ponendo $a*b=a$ e $a\bullet b=b$ per ogni $a,b\in S$ sono associative.
3. Verificare che il monoide delle parole su un alfabeto $A$ è commutativo se e solo se $A$ ha al massimo un elemento.
4. Vero o falso? Per ogni insieme non vuoto $S$ ed ogni operazione binaria $*$ in $S$, …
   1. … in $S$ esiste sempre un elemento neutro a destra o un elemento neutro a sinistra;
   2. … se $*$ è commutativa tutti gli elementi neutri a destra in $(S,*)$ sono anche neutri a sinistra;
   3. … se $*$ è commutativa in $S$ esiste al massimo un elemento neutro a sinistra;
   4. … se $a$ e $b$ sono due elementi neutri a sinistra distinti in $(S,*)$, in $(S,*)$ non esistono elementi neutri a destra;
   5. … se $a$ è un elemento neutro a sinistra in $(S,*)$, nessun elemento di $S\setminus\set a$ è neutro a destra in $(S,*)$.
5. Posto $A=\set{0,1}$, scrivere le tavole di Cayley di $(\P(A),\cap)$ e di $(\P(A),\ds)$. Identificare gli eventuali elementi neutri.
6. Studiare le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, e determinando gli elementi neutri a sinistra, a destra, neutri delle strutture da esse definite:
   • $\alpha\colon (a,b)\in \Z\times\Z\mapsto a+b+1\in\Z$;
   • $\beta\colon (a,b)\in \Z\times\Z\mapsto -ab\in\Z$;
   • $\gamma\colon (a,b)\in \Q\times\Q\mapsto (a+b)/2\in\Q$;
   • $\delta\colon (a,b)\in \Z\times\Z\mapsto 2ab\in\Z$;
   • $\varepsilon\colon (a,b)\in \Q\times\Q\mapsto 2ab\in\Q$;
   • $\zeta\colon (a,b)\in \N\times\N\mapsto a10^b\in\N$;
   • $\eta\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto a\cup b\cup \set 1\in\P(\Z)$;
   • $\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}$.
7. Ripetere l'esercizio precedente per l'operazione $*$ definita in $\set{0,1,2,3}$ da questa tavola di Cayley:

   	0	1	2	3
   0	1	1	0	1
   1	1	1	1	1
   2	1	1	2	1
   3	1	1	3	1

   Suggerimento: dopo aver osservato che, per ogni $x,c\in S$, si ha $x*2=x$ e $x*c=1$ se $c\ne 2$, per ogni scelta di $a,b,c\in S$ si calcolino $a*(b*c)$ e $(a*b)*c$ considerando separatamente i casi $c=2$ e $c\ne 2$.
8. (Sarà discusso ed ampliato in aula) Data un'operazione binaria $*$ definita in un insieme $S$, si chiama operazione opposta a $*$ l'operazione $\bullet$ definita sempre in $S$ ponendo $a\bullet b=b*a$ per ogni $a,b\in S$. Dimostrare:
   1. $*=\bullet$ se e solo se $*$ è commutativa;
   2. $*$ è l'operazione opposta a $\bullet$;
   3. $\bullet$ è associativa se e solo se $*$ è associativa;
   4. per ogni $t\in S$, $t$ è neutro a sinistra in $(S,\bullet)$ se e solo se $t$ è neutro a destra in $(S,*)$, e viceversa.
   Partendo dall'esempio di $(\Z,-)$, trovare un'operazione binaria in $\Z$ rispetto alla quale esista uno ed un solo elemento neutro a sinistra e non esistano elementi neutri a destra.

23/10

Ampia discussione di esercizi dalla lezione precedente. Partendo dal numero 8: operazione opposta di una operazione binaria e dualità destra/sinistra. Notazione $(S,*,t)$ per indicare un monoide (con elemento neutro $t$).

Cenno ai teoremi di associatività e di commutatività.

Simmetrici destri e sinistri; simmetrici. Vari esempi. Unicità dei simmetrici nei monoidi: se, per un elemento $a$ di un assegnato monoide $S$, $s$ è un simmetrico sinistro e $d$ è un simmetrico destro di $a$, allora $s=d$, quindi $s$ è l'unico simmetrico di $a$, l'unico simmetrico sinistro di $a$ e l'unico simmetrico destro di $a$ in $S$. Osservazione banale: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di sé stesso. Elementi simmetrizzabili. Esempio: determinazione degli elementi simmetrizzabili del monoide $(\Z,\cdot)$ e del monoide delle parole. Simmetrici sinistri e destri nel monoide delle trasformazioni di un insieme: sono rispettivamente le retrazioni e le sezioni. Terminologia: uso di "inverso" (prevalentemente in notazione moltiplicativa) e di "opposto" (prevalentemente in notazione additiva) come sinonimi di "simmetrico".

Gruppi.

Esercizi proposti:

1. Determinare (i neutri e) gli elementi simmetrizzabili nei monoidi qui elencati, stabilendo quali di questi sono gruppi: $(\Q,+)$, $(\Q,\cdot)$, $(\N,+)$; per un insieme $A$: $(\P(A),\cap)$, $(\P(A),\cup)$, $(\P(A),\ds)$.
2. Fare lo stesso per le strutture definite dalle operazioni $\alpha$, $\beta$, $\varepsilon$ e $\kappa$ che appaiono nell'esercizio 6 della lezione scorsa.
3. Sia $*$ l'operazione binaria definita in $X:=\Z\times\Z$ da: $(\forall\; a,b,c,d\in\Z) \big((a,b)*(c,d)=(ac,ad)\big)$. Decidere se $*$ è associativa, se è commutativa, se ammette elementi neutri a sinistra, se ne ammette a destra. Nel caso la richiesta abbia senso, determinare gli elementi simmetrizzabili in $(X,*)$, descrivendone i simmetrici. Che tipo di struttura (semigruppo, monoide, gruppo, commutativo o no?) è $(X,*)$?
4. Stesse domande come all'esercizio precedente, per le operazioni
   • $\varphi\colon(a,b)\in\Z\times\Z\mapsto a+b-1\in\Z$
   • $\psi\colon(a,b)\in\Z\times\Z\mapsto ab+1\in\Z$
   • $\mu\colon((a,b),(c,d))\in(\Z\times\Z)\times(\Z\times\Z) \mapsto (a+bc,bd)\in\Z\times\Z$
   • $\tau\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\cup Y)\cap\N\in\P(\Z)$
   • $\omega\colon(X,Y)\in\P(\Z)\times\P(\Z)\mapsto(X\setminus Y)\cup\set 1\in\P(\Z)$
   al posto di $*$ (suggerimento per l'ultima operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).
5. Sia $S=\set{a,x,y}$ un insieme di tre elementi e si consideri in $S$ l'operazione $*$ definita in $S$ da questa tavola di Cayley:

   	$a$	$x$	$y$
   $a$	$a$	$x$	$y$
   $x$	$x$	$a$	$a$
   $y$	$y$	$y$	$a$

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

25/10

Discussione di esercizi dalla lezione precedente. Visualizzazioni di simmetrici destri o sinistri in tavole di Cayley.

Gruppi abeliani. Vari esempi; tra questi il gruppo $(\P(A),\ds)$ per un arbitrario insieme $A$.

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

Arbitrarie intersezioni tra parti chiuse (in una struttura algebrica con una operazione binaria). La parte chiusa generata da una parte.

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

Esercizi proposti:

1. 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.
2. L'insieme delle parti finite di $\N$ è chiuso in $(\P(\N),\cap)$, in $(\P(\N),\cup)$, in $(\P(\N),\ds)$? E quello delle parti infinite?
3. Nel monoide delle parole su un alfabeto che contenga la lettera y, dire se sono o non sono parti chiuse: l'insieme delle parole di lunghezza (nel senso ovvio) maggiore di 55; l'insieme delle parole di lunghezza pari; l'insieme delle parole che iniziano per y; l'insieme delle parole che finiscono per yyy; l'insieme delle parole in cui y non appare; l'insieme delle parole in cui y appare al massimo tre volte; l'insieme delle parole che se hanno lunghezza maggiore di 10 allora non hanno y tra le lettere che vi appaiono.
4. Svolgere l'esercizio 9 di quelli per le vacanze di pasqua.
5. Svolgere l'esercizio 4 dal compito del 16 marzo 2018.
6. In $D:=\Z\times\Z$ si definiscano le operazioni binarie $*$ e $\bullet$ ponendo, per ogni $a,b,c,d\in\Z$, $(a,b)*(c,d)=(ac,b+d)$ e $(a,b)\bullet(c,d)=(ac,b-d)$. Studiare $(D,*)$ e $(D,\bullet)$, decidendo che genere di strutture algebriche siano, (semigruppi, monoidi, gruppi; commutative o meno) e, nel caso la domanda abbia senso, quali siano i loro elementi simmetrizzabili. Stabilire poi se $\Z\times \set 0$ e $\Z\times\set{1}$ sono o non sono parti chiuse rispetto a $*$ o rispetto a $\bullet$ e studiare, ove esistano, le corrispondenti strutture indotte.
7. Sia $S=\set{1,2,3,4}$. Descrivere la parte chiusa generata da $\P_1(S)=\set{\set x\mid x\in S}$ in $(\P(S),\cup)$. Più difficile: descrivere la parte chiusa generata da $\P_1(\N)$ in $(\P(\N),\cup)$.
8. Determinare il gruppo degli invertibili di ciascuno dei seguenti monoidi: $(\Z,\cdot)$, $(\R,\cdot)$, $(\Z,+)$, per un insieme $A$: $(\P(A),\cap)$, $(\P(A),\cup)$ e il monoide delle parole su $A$.
9. Verificare che la struttura definita dall'operazione $\kappa$ dell'esercizio 6 della lezione del 21/10 è il gruppo degli invertibili del monoide definito dall'operazione $\mu$ dell'esercizio 4 della lezione del 23/10.

28/10

Discussione di esercizi dalla lezione precedente.

Ancora sulla conservazione di proprietà nel passaggio da operazioni ad operazioni indotte su parti chiuse. Esempi in cui non si conservano neutri o simmetrici. Sottomonoidi.

Il gruppo simmetrico $\Sym(A)=\U(T(A))$ su un insieme $A$. I suoi elementi sono le permutazioni di $A$ (cioè le applicazioni biettive da $A$ a sé stesso). $\Sym(A)$ è abeliano se e solo $A$ ha meno di tre elementi. Cenno a permutazioni cicliche e trasposizioni.

Traslazioni in una struttura algebrica con un'operazione binaria; elementi cancellabili, a sinistra o a destra; elementi cancellabili. Negazione della cancellabilità. In ogni monoide, gli elementi simmetrizzabili a sinistra (rispettivamente a destra) sono tutti cancellabili a sinistra (rispettivamente a destra). Il viceversa non vale in generale (ad esempio, non vale in $(\Z,\cdot)$) ma vale nel caso dei monoidi finiti. Questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità, che contiene più di quanto richiesto ai fini di questo corso. Per il momento, a noi serve solo il contenuto della prima pagina.

Visualizzazione delle cancellabilità nelle tavole di Cayley.

Esercizi proposti:

1. Determinare gli elementi cancellabili in $(\N,+)$, in $(\N,\cdot)$ e, per un insieme $S$, in $(\P(S),\cap)$, in $(\P(S),\cup)$ e in $(\P(S),\ds)$.
2. Sia $(S,*)$ un semigruppo. Indicando, per ogni $a\in S$, con $\sigma_a\colon x\in S\mapsto a*x\in S$ e con $\delta_a\colon x\in S\mapsto x*a\in S$ le traslazioni sinistra e destra determinate da $a$ in $(S,*)$, verificare che:
   • se $t\in S$, $t$ è neutro a sinistra (rispettivamente, a destra) in $(S,*)$ se e solo $\sigma_a=\id_A$ (rispettivamente, $\delta_a=\id_A$);
   • per ogni $a,b\in S$, si ha $\sigma_{a*b}=\sigma_a\circ\sigma_b$ e $\delta_{a*b}=\delta_{b}\circ\delta_{a}$.
   (La prima affermazione vale anche nel caso in cui $*$ non sia associativa, l'altra, in generale, no.)
3. Verificare (magari utilizzando l'esercizio precedente) che, in ogni semigruppo, l'insieme degli elementi cancellabili a sinistra e quello degli elementi cancellabili a destra sono parti chiuse.
4. Svolgere l'esercizio 6 da questa versione della prova in itinere dell'aprile 2019.
5. Assegnato un insieme $A$, si individuino gli elementi cancellabili a sinistra, a destra, cancellabili nel monoide delle parole su $A$.
6. In ciascuna delle strutture definite dalle operazioni proposte negli esercizi numeri 6 e 7 della lezione del 21/10 e numeri 4 e 5 della lezione del 23/10, si individuino gli elementi cancellabili a sinistra, a destra, cancellabili.
7. Sia $A=\set{1,2,3}$. Scrivere tutti gli elementi di $\Sym(A)$ (sono sei in tutto).

30/10

Discussione di esercizi dalla lezione precedente.

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

Potenze (o, in notazione additiva, multipli) di un elemento di un semigruppo secondo interi (positivi nel caso dei semigruppi, naturali nel caso dei monoidi, arbitrari nel caso dei gruppi). Regole di calcolo (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.

Aggiunta: la prova in itinere del 12 novembre verterà solo su argomenti trattati sino a questo punto del corso.

Sottomonoidi e sottogruppi generati da una parte. Se $(S,\cdot)$ è un semigruppo e $x\in S$, la parte chiusa di $(S,\cdot)$ generata da $\set x$ è $\set{x^n\mid n\in\N^+}$; se $(S,\cdot)$ è un monoide il sottomonoide generato da $\set x$ in $(S,\cdot)$ è $\set{x^n\mid n\in\N}$; se $(S,\cdot)$ è un gruppo il sottogruppo generato da $\set x$ in $(S,\cdot)$ è $\set{x^n\mid n\in\Z}$. Gruppi ciclici; esempio: $(\Z,+)$.

Omomorfismi tra strutture algebriche ad una operazione binaria. 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.

Avviso: Come detto in aula, la prossima lezione (lunedì 4) non si terrà di mattina ma dalle 14 alle 16.

Esercizi proposti:

1. Siano $A$ un insieme e $B$ una sua parte. Dimostrare che $\P(B)$ costituisce un sottogruppo di $(\P(A),\ds)$.
2. Siano $A$ un insieme e $x\in A$. Dimostrare che $\set{\sigma\in\Sym(A)\mid \sigma(x)=x}$ costituisce un sottogruppo di $\Sym(A)$.
3. L'applicazione $n\in\Z\mapsto 3n\in\Z$ è un omomorfismo da $(\Z,+)$ a $(\Z,+)$? E da $(\Z,\cdot)$ a $(\Z,\cdot)$?
4. L'applicazione $X\in \P(\Z)\mapsto X\cap \N\in\P(\N)$ è un omomorfismo da $(\P(\Z),\cap)$ a $(\P(\N),\cap)$? e da $(\P(\Z),\cup)$ a $(\P(\N),\cup)$?
5. Siano $g\colon (A,*)\to (B,\bullet)$ e $f\colon (B,\bullet)\to (C,\lozenge)$ omomorfismi. Provare che $f\circ g$ è un omomorfismo da $(A,*)$ a $(C,\lozenge)$ e che se $f$ e $g$ sono isomorfismi anche $f\circ g$ lo è.
6. Sia $*$ un'operazione binaria nell'insieme $S$ e sia $T$ una parte chiusa (non vuota) in $(S,*)$. Verificare che l'immersione di $T$ in $S$ è un omomorfismo da $(T,*)$ a $(S,*)$.
7. 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?
8. Provare che l'applicazione $n\in\Z\mapsto n-1\in\Z$ è un isomorfismo da $(\Z,+)$ a $(\Z,\alpha)$, dove l'operazione $\alpha$ è quella definita nell'esercizio numero 6 della lezione del 21/10.

4/11

Discussione di esercizi dalla lezione precedente.

Gli omomorfismi suriettivi conservano l'associatività, la commutatività, gli elementi neutri (anche a destra o a sinistra), i simmetrici (anche a destra o a sinistra). L'inversa di ogni isomorfismo è un isomorfismo. Invarianza delle proprietà algebriche per isomorfismi. Discussione generale ed alcuni esempi sull'importanza e utilità dell nozione di isomorfimo. Invarianza delle proprietà algebriche (inclusa la cancellabilità) per isomorfismi.

Alcuni esempi di isomorfismi. Tra questi: la funzione esponenziale da $(\R,+)$ a $(\R^+,\cdot)$ (il gruppo moltiplicativo dei reali positivi); per un fissato insieme $S$, l'applicazione $X\mapsto S\setminus X$, da $(\P(S),\cup)$ a $(\P(S),\cap)$ (o viceversa).

Isomorfismi e tavole di Cayley. Costruzione della tavola di Cayley dei gruppi di cardinalità due, tre o quattro, basate sul fatto che ciascuna delle righe e delle colonne della tavola di Cayley di un gruppo è sempre priva di ripetizioni.

Esercizi proposti:

1. Provare che l'applicazione $a\in\Q\mapsto a/2\in\Q$ è un isomorfismo da $(\Q,\cdot)$ a $(\Q,\varepsilon)$, dove l'operazione $\varepsilon$ è quella definita nell'esercizio numero 6 della lezione del 21/10.
2. Sia $S=\set{13}\times \Z$, e sia $*$ l'operazione binaria definita in $S$ ponendo, per ogni $(a,b),(c,d)\in S$, $(a,b)*(c,d)=(13,b+d)$. Dimostrare che $(S,*)$ è un gruppo abeliano, scrivendo direttamente un isomorfismo da $(S,*)$ a $(\Z,+)$.
3. Sia $f\colon S\to T$ un'applicazione biettiva. Dimostrare che l'applicazione $\vecf\colon \P(S)\to\P(T)$ è un isomorfismo da $(\P(S),\cap)$ a $(\P(T),\cap)$.
4. Ricordando, da un esercizio precedente, che se $A=\set{0,1}$, $\Sym(A)=\set{\id_A,\sigma}$, dove $\sigma$ è la permutazione di $A$ definita da $\sigma(0)=1$ e $\sigma(1)=0$, scrivere un isomorfismo tra i gruppi $(\set{1,-1},\cdot)$ e $(\Sym(A),\circ)$.
5. Sia $A=\set{1,2,3,4}$. Si considerino le permutazioni $\sigma$ e $\tau$ appartenenti a $\Sym(A)$ definite da: $\sigma(1)=\tau(1)=2$, $\sigma(2)=\tau(2)=3$, $\sigma(3)=1$, $\sigma(4)=4$, $\tau(3)=4$, $\tau(4)=1$. Si verifichi che $\sigma^3=\id_A=\tau^4$ e che $G=\set{\id_A,\sigma,\sigma^2}$ e $H=\set{\id_A,\tau,\tau^2,\tau^3}$ costituiscono sottogruppi di $\Sym(A)$ che hanno, rispettivamente, tre e quattro elementi. Scrivere le tavole di Cayley di $G$ e di $H$ (ovviamente l'operazione è quella indotta dall'operazione di $\Sym(A)$, ovvero la composizione) e confrontarle con quelle discusse a lezione.

8/11

Discussione di esercizi dalla lezione precedente.

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

Il numero delle applicazioni tra due insiemi finiti. Varianti dello stesso problema (numero delle stringhe di data lunghezza sottoposte a vincoli). Fattoriali e fattoriali discendenti. Scelti comunque due insiemi finiti $A$ e $B$:

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

Esercizi proposti:

1. 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|$?
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. Quante sono le parole di lunghezza 10 che si possono ottenere utilizzando un alfabeto di 15 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?

11/11

Discussione di esercizi dalla lezione precedente.

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

Alcune regole elementari di calcolo in un anello $R$: per ogni $a$, $b$ in $R$, $a0_R=0_R=0_Ra$, e $a(-b)=-(ab)=(-a)b$. Notazione $a-b=a+(-b)$.

In un anello che abbia più di un elemento lo zero non può essere cancellabile, quindi non può essere invertibile. Corpi e campi (esempi: i campi dei razionali e dei reali; anche $\P(S)$ è un campo, di cardinalità 2, se $|S|=1$.)

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

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$. Questo anello si chiama anello prodotto diretto di $R$ per $S$ e questo esercizio generalizza la costruzione, accennata a lezione, dell'anello prodotto diretto $\Z\times\Z$.
2. Nell'anello prodotto diretto $\Z\times\Z$, definito come all'esercizio precedente si decida quali tra questi elementi sono divisori dello zero e quali cancellabili: $(1,1)$, $(1,2)$, $(0,4)$. Fatto questo, provare a descrivere l'insieme dei divisori dello zero in $\Z\times\Z$.
3. Ancora con riferimento allo stesso anello $\Z\times\Z$ dell'esercizio precedente, verificare che $\set{0}\times \Z$ è un sottoanello di $\Z\times\Z$. Ne è un sottoanello unitario? Che tipo di anello è $\set{0}\times \Z$ (munito delle operazioni indotte da quelle di $\Z\times\Z$)? Per caso è isomorfo ad un anello che ben conosciamo?
   Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
4. Provare che, se $S$ è un insieme non vuoto, l'anello delle parti di $S$ ha esattamente un elemento che non è divisore dello zero.
5. Sia $R$ un anello unitario. È possibile che $1_R$ sia un divisore dello zero in $R$?
6. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?

13/11

Approfondimento sull'ultimo enunciato della lezione dell'8 novembre, con una dimostrazione alternativa. Equipotenza e comparazione tra cardinalità per insiemi infiniti: cenni.

Caratterizzazioni degli anelli integri e dei domini di integrità. I domini di integrità finiti sono campi (la dimostrazione è stata solo accennata, e solo per il caso degli anelli unitari).

Per una parte $A$ di un insieme $S$, funzione caratteristica $\chi_{A,S}\colon S\to \set{0,1}$ di $A$ in $S$. Teorema: l'applicazione da $\P(S)$ a $\set{0,1}^S$ che a ciascuna parte $A$ di $S$ associa $\chi_{A,S}$ è biettiva. Conseguenza: per ogni insieme finito $S$ si ha $|\P(S)|=2^{|S|}$. Codifica delle parti di un fissato insieme $S$ come funzioni caratteristiche; se $S$ è, per un intero positivo $n$, l'insieme dei primi $n$ interi positivi, queste ultime si rappresentano come stringhe di lunghezza $n$ nei caratteri 0 e 1. (Questo è un importante esempio di come le biezioni—e gli isomorfismi—permettono di tradurre problemi e soluzioni, e codificare dati, da un ambito ad un altro in modo reversibile e senza perdita di informazione.)

Principio di induzione (prima forma). Seconda dimostrazione (per induzione) dell'uguaglianza $|\P(S)|=2^{|S|}$ per ogni insieme finito $S$.

Esercizi proposti:

1. Scrivere la funzione caratteristica di $\N$ in $\Z$. Di quale parte di $\N$ l'applicazione $n\in\N\mapsto ((-1)^n+1)/2\in\set{0,1}$ è la funzione caratteristica? Rappresentare come stringa di zeri ed uno il sottoinsieme $\set{8}$ di $\set{n\in\N^*\mid n\le 10}$.
2. Usando il principio di induzione, dimostrare che, come detto a lezione qualche tempo fa, se $x$ è un elemento del semigruppo $(S,\cdot)$, scelti comunque i numeri interi positivi $n$ e $m$, si ha $x^{n+m}=x^n x^m$ e $(x^n)^m=x^{nm}$.
3. Usando il principio di induzione, dimostrare che per ogni $n\in\N^*$ si ha $\sum_{i=1}^ni=n(n+1)/2$.

15/11

Discussione di esercizi dalle due ultime lezioni.

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 $k>n$. Per ogni $n\in\N$ si ha $\sum_{k=0}^n\binom nk=2^n$.

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

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

Esercizi proposti:

1. Calcolare $\binom 74$ utilizzando il triangolo di Tartaglia-Pascal.
2. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_7(S)$.
3. Sia $S$ un insieme di cardinalità 11. Quante sono le parti di $S$ di cardinalità 5? E quante quelle di cardinalità 6? Quante sono le 8-parti di $\P(S)$?
4. Sia $S$ un insieme di cardinalità 5. Le funzioni caratteristiche delle 2-parti di $S$ sono tutte e sole le applicazioni da $S$ a $\set{0,1}$ tali che …? Quante sono?
5. Posto $A=\set{n\in\N\mid n\lt10}$ 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|=5}$, $V:=\set{X\in\P(A)\mid 0\in X\land |X|=5}$, $W=\set{X\in\P(A)\mid B\sseq X\land |X|=6 }$ e $Z:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X) \land |X|=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?

18/11

Discussione degli esercizi dalla lezione precedente.

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

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

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 ordine (largo), relazioni di ordine stretto, 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). Il nucleo di equivalenza di un'applicazione $f$ è la relazione di uguaglianza (risp. quella universale) nel dominio di $f$ se e solo se $f$ è iniettiva (risp. costante).

Classi di equivalenza. Descrizione delle classi di equivalenza del nucleo di equivalenza di un'applicazione $f$: per ogni elemento $x$ del dominio, questa classe è $\avecf(\set{f(x)})$.

Esercizi proposti:

1. Provare che una relazione binaria in un insieme $A$ è sia simmetrica che antisimmetrica se e solo se il suo grafico è contenuto nella diagonale di $A$.
2. 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$.
3. Detto $\rho$ il nucleo di equivalenza dell'applicazione $X\in\P(\Z)\mapsto X\cap\N\in\P(\N)$, descrivere $[\vuoto]_\rho$.
4. Esercizi 1 (esclusi i punti f e g) e 2 (esclusi i punti a e b) da relazioni binarie. Terminologia e notazioni: per ‘ordinamento’ si intende una relazione d'ordine stretto o largo; $\N^\#=\N^*=\N^+=\N\setminus\set 0$.
5. Dimostrare che se $A$ è un insieme finito di cardinalità $n$ esistono esattamente $2^{n^2}$ relazioni binarie in $A$ (suggerimento: quante sono le parti di $A\times A$?).
6. Sia $A=\set{0,1}$. Delle 16 relazioni binarie in $A$ (vedi esercizio precedente), dire quali e quante sono riflessive, quali e quante antiriflessive, quali e quante sono simmetriche, quali e quante sono antisimmetriche. Usando l'osservazione sulla verifica della transitività fatta nella lezione di oggi, provare che se una relazione binaria $\alpha$ in $A$ non è transitiva, allora $0\mathrel\alpha 1$ e $1\mathrel\alpha 0$. A questo punto, quali e quante sono le relazioni binarie non transitive e quante quelle transitive in $A$?

20/11

Discussione di esercizi dalla lezione precedente.

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

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$;
• sono tra loro equivalenti: $a\sim b$, $b\sim a$, $ a\in[b]_\sim$, $b \in [a]_\sim$, $[a]_\sim\cap [b]_\sim\ne \vuoto$, $ [a]_\sim=[b]_\sim$;
• ogni elemento di $A$ appartiene ad esattamente una classe di equivalenza.

Con le stesse notazioni, insieme quoziente $A/{\sim}=\set{[x]_{\sim}\mid x\in A}$ e 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.

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

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

Utilizzo di questa biezione per lo studio delle relazioni di equivalenza su un insieme. Ad esempio: descrizione delle relazioni di equivalenza su un insieme di cardinalità 3 (sono in tutto cinque). Le partizioni banali di un insieme $A$, (cioè $\P_1(A)$ e, se $A\ne\vuoto$, $\set A$) corrispondono alle relazioni di equivalenza banali di $A$.

Esercizi proposti (hanno priorità i numeri 2, 4, 6 e 8):

1. Vero o falso? Per ogni insieme $A$, ogni relazione di equivalenza $\sim$ in $A$, ed ogni $a,b\in A$ si ha $[a]_{\sim}\sseq[b]_{\sim}$ se e solo se $a\sim b$.
2. Svolgere l'esercizio 1 dal compito del 16 luglio 2013.
3. Svolgere le parti (i) e (ii) dell'esercizio 3 dal compito del 18 giugno 2019.
4. Siano $S=\set{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 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$.
6. Sia $A=\set{0,1,2,3,4,5,6}$. Stabilire quante sono, e descrivere esplicitamente, le relazioni di equivalenza $\sim$ in $A$ tali che $1\sim 3\not\sim 2\sim 4$ e $4\in[0]_\sim=[6]_\sim$.
7. Sia $A=\set{0,1,2,3,4,5,6}$. Quante (e quali) sono le relazioni di equivalenza $\rho$ in $A$ tali che $0\mathrel\rho 3$, $\set{2,5,6}\subseteq [3]_\rho$ e $6\in[4]_\rho$?
8. 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|$.

22/11

Discussione di vari esercizi dalla lezione precedente.

Teorema fondamentale di omomorfismo per insiemi: se $f$ è un'applicazione di dominio $A$ e $\sim$ è il suo nucleo di equivalenza, l'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in\text{coim}(f)=A/{\sim}$ è biettiva, quindi si ha $|A/{\sim}|=|\im f|$. Si consiglia di consultare le note, scritte a questo riguardo, anche se con stile e notazioni diverse da quelle usate a lezione (le composizioni tra applicazioni sono indicate nel verso naturale, quindi come $fg$ piuttosto che $g\circ f$; per le immagini degli elementi mediante applicazioni è usata la notazione esponenziale quindi come $x^f$ laddove a lezione usiamo scrivere $f(x)$). Si legga, in particolare, l'esempio conclusivo.

Richiamo sulle relazioni d'ordine. Fissato un insieme $A$, biezioni (una è l'inversa dell'altra) $\rho\in\OL(A)\mapsto\rho_{\ne}\in\OS(A)$ e $\sigma\in \OS(A)\mapsto\sigma_{=}\in\OL(A)$ tra gli insiemi $\OL(A)$ e $\OS(A)$ delle relazioni di ordine largo e di ordine stretto in $A$. Non sono state fornite (e non saranno richieste) dimostrazioni a riguardo. Qui $\rho_{\ne}$ è descritta da: $(\forall x,y\in A)$$(x\mathrel{\rho_{\ne}}y \iff (x\mathrel\rho y \land x\ne y))$; analogamente $\sigma_{=}$ è descritta da: $(\forall x,y\in A)$$(x\mathrel{\sigma_{=}}y \iff (x\mathrel\sigma y \lor x=y))$. Descrizione di queste applicazioni in termini dei grafici delle relazioni coinvolte.

Insiemi ordinati. Principio di dualità per insiemi ordinati. Ordinamenti indotti su parti; sottoinsiemi ordinati.

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

Elementi minimi ed elementi minimali in un insieme ordinato (degli elementi minimali sono state date due definizioni equivalenti); nozioni duali: elementi massimi ed elementi massimali. Se un insieme ordinato $(S,\rho)$ ha un minimo $a$, allora $a$ è l'unico minimo e l'unico minimale in $(S,\rho)$.

Esercizi proposti (hanno priorità i numeri 1, 4 e 5):

1. Vero o Falso? Se un insieme ordinato $(S,\rho)$ ha un massimo $a$, allora $a$ è l'unico massimo e l'unico massimale in $(S,\rho)$.
2. Sia $S=\set{1,2,3,4}$ e sia $f\colon X\in\P(S)\mapsto X\cup\set{1,2}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim}$, dove $\sim$ è il nucleo di equivalenza di $f$? Descriverli esplicitamente, elencandone cioè gli elementi.
3. 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$?
4. 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$.
5. Siano $S=\set{1,2,3,4}$ e $f\colon x\in\P(S)\mapsto |x|\in\N$; siano poi $\rho$ e $\tau$ le relazioni binarie in $\P(S)$ definite da: per ogni $x,y\in\P(S)$, $x\mathrel\rho y\iff f(x)\le f(y)$ e $x\mathrel\tau y\iff (x=y \lor f(x)\lt f(y))$. Di ciascuna delle due stabilire se è o non è una relazione d'ordine (largo) e, nel caso lo sia, determinare nel corrispondente insieme ordinato gli eventuali elementi minimali, massimali, minimo, massimo, stabilendo poi quali elementi di $\P(S)$ sono e quali non sono confrontabili con $\set{1,2}$.

25/11

Discussione di esercizi dalla lezione precedente. Come applicazione del principio di dualità: in ogni insieme ordinato con massimo, questo è l'unico elemento massimale.

In ogni insieme ordinato finito (non vuoto) esistono sia elementi minimali che elementi massimali.

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

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

Relazione di divisibilità in semigruppi ed in monoidi commutativi. 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$. Questo avviene se e solo se $a$ e $b$ hanno lo stesso insieme di divisori; di conseguenza: la relazione "essere elementi associati" è una relazione di equivalenza in $M$.

Esercizi proposti (sono prioritari i numeri 1, 2, 3 e 5):

1. Trovare gli elementi minimali e qualli massimali in ciascuno degli insiemi $A:=\set{n\in\N\mid n\le 10}$ e $B=A\setminus\set{1}$ ordinati per divisibilità (cioè dalla relazione indotta da quella di divisibilità in $(\N,\cdot\,)$).
2. Siano $A=\set{n\in\Z\mid n^2\le 20}$ e $f\colon a\in A\mapsto a^2+2\in\N$. Siano poi $\sigma$ e $\rho$ le relazioni d'ordine definite in $A$ ponendo, per ogni $a,b\in A$, $a\mathrel\sigma b\iff (a=b \lor f(a)\lt f(b))$ e $a\mathrel\rho b\iff (a=b \lor f(a)$ divide propriamente $f(b))$. Determinare, sia in $(A,\sigma)$ che in $(A,\rho)$, gli elementi minimali, massimali, gli eventuali minimo e massimo e gli elementi non confrontabili con $2$.
3. Svolgere i punti da (i) a (iv) dell'esercizio 6 dal compito del 16 gennaio 2019.
4. Dimostrare per via diretta (cioè provando le proprietà riflessiva, simmetrica, transitiva) che, in un monoide comutativo, la relazione "essere elementi associati" è di equivalenza.
5. Se $a,a', b,b'$ sono elementi di un monoide commutativo tali che $a\sim a'$ e $b\sim b'$, allora $a$ divide $b$ se e solo se $a'$ divide $b'$.
6. Dimostrare che due elementi di un monoide commutativo sono associati se e solo se hanno lo stesso insieme di multipli.

27/11

Discussione di esercizi dalla lezione precedente. Le proprietà relative alla divisibilità sono invarianti per il passaggio ad elementi associati.

Intervalli in insiemi ordinati.

Minoranti e (dualmente) maggioranti di una parte $X$ di un insieme ordinato $(S,\rho)$. Un elemento $S$ è il minimo di $X$ se e solo se ne è un minorante ed un elemento. Vari 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$ (o di $A$ se $X=\vuoto$) ed i sottoinsiemi di $A$ contenenti $\bigcup X$.

Estremo inferiore $\inf_{(S,\rho)}(X)=\max(\minor_{(S,\rho)}(X))$ ed estremo superiore $\sup_{(S,\rho)}(X)=\min(\maggior_{(S,\rho)}(X))$ di una parte $X$ di un insieme ordinato $(S,\rho)$. Ad esempio, se $\vuoto\ne X\sseq\P(A)$, $\inf_{(\P(A),\sseq)}(X)=\bigcap X$ e $\sup_{(\P(A),\sseq)}(X)=\bigcup X$.

Applicazioni crescenti ed isomorfismi tra insiemi ordinati; proprietà che questi ultimi conservano. Esempio di un'applicazione biettiva crescente che non è un isomorfismo: l'applicazione identica da $(\N^*,|\,)$ a $(\N^*,\le)$.

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.

Esercizi proposti (il 5 è più complesso degli altri; lasciarlo per ultimo):

1. Disegnare diagrammi di Hasse di $(\P(\set{49}), \sseq)$, di $(\P(\set{4,9}), \sseq)$ e, per ciascun $n\in\set{2,4,6,9,12}$, dell'insieme $\Div(n)$ dei numeri naturali divisori di $n$ (ordinato per divisibilità). Scrivere, se possibile, isomorfismi da $(\Div(4),|\,)$ a $(\Div(9),|\,)$, da $(\Div(9),|\,)$ a $(\Div(6),|\,)$, da $(\Div(6),|\,)$ a $(\P(\set{4,9}),\sseq)$.
2. Siano $A=\set{1,2,3,5,60}$, $B=A\cup\set{25, 600}$ e $C=B\cup\set{100}$. disegnare (in quest'ordine) i diagrammi di Hasse di $A$, $B$ e $C$, ordinati per divisibilità. Trovare poi, in $(C,|\,)$, gli insiemi dei minoranti e dei maggioranti di $X:=\set{25,60}$ e di $Y:=\set{60,100}$; decidere infine se esistono (e nel caso, quali elementi di $C$ sono) $\inf(X)$, $\sup(X)$, $\inf(Y)$, $\sup(Y)$.
3. Siano $A$ e $B$ parti di un insieme ordinato $(S,\rho)$. Dimostrare: $\minor_{(S,\rho)}(A\cup B)=\minor_{(S,\rho)}(A)\cap\minor_{(S,\rho)}(B)$. Qual è l'affermazione duale?
4. Provare che, in $\Q$ la relazione d'ordine usuale e quella di uguaglianza definiscono la stessa relazione di copertura.
5. Disegnare diagrammi di Hasse degli insiemi ordinati $(A,\sigma)$ e $(A,\rho)$ descritti nel secondo esercizio della lezione scorsa. Individuare in ciascuno dei due insiemi $\minor(\set{2,4,-4})$, $\minor(\set{4,-4})$ e $\maggior(\set{4,-4})$.

29/11

Discussione di esercizi dalla lezione precedente. Costruzione di diagrammi di Hasse. Due insiemi ordinati finiti sono isomorfi se e solo se si possono rappresentare con lo stesso diagramma di Hasse.

Reticoli. Esempi e controesempi. Per verificare che un insieme ordinato sia un reticolo basta verificare l'esistenza di estremi inferiore e superiore dei sottoinsiemi costituiti da due elementi non confrontabili tra loro. Esempi importanti: sono reticoli tutti gli insiemi ordinati, per ogni insieme $A$, $(\P(A),\subseteq)$ ed $(\N,\mid)$. Questi ultimi due sono reticoli completi (cioè reticoli in cui ogni sottoinsieme ha estremo inferiore ed estremo superiore).

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

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

Un elemento minimale (risp. massimale) in un reticolo è necessariamente minimo (risp. massimo). Di conseguenza i reticoli finiti non vuoti sono limitati, cioè hanno minimo e massimo; questo non è sempre vero per reticoli infiniti.

Siano $(S,\rho)$ un insieme ordinato e $A, B\subseteq S$. Supponiamo che esistano $a=\inf_{(S,\rho)} A$ e $b=\inf_{(S,\rho)}B$. Allora i minoranti di $A\cup B$ sono precisamente i minoranti di $\set{a,b}$; esiste $\inf_{(S,\rho)}(A\cup B)$ se e solo se esiste $\inf_{(S,\rho)}(\set{a,b})$ e, nel caso esistano, questi estremi inferiori coincidono. Enunciato duale per gli estremi superiori. Di conseguenza, se $(S,\rho)$ è un reticolo, esistono $\inf_{(S,\rho)}(X)$ e $\sup_{(S,\rho)}(X)$ per ogni sottoinsieme finito e non vuoto $X$ di $S$ (anche da ciò segue la limitatezza dei reticoli finiti non vuoti).

Le due operazioni (binarie) reticolari (meet/inf/intersezione reticolare/$\land$ e join/sup/unione reticolare/$\lor$) definite in un reticolo. Loro proprietà algebriche (commutatività, associatività, leggi di assorbimento, iteratività). Reticoli come strutture algebriche. Equivalenza tra le nozioni di reticolo come insieme ordinato e di reticolo come struttura algebrica, discussa come segue. Assegnato un insieme $S$, siano $R$ l'insieme delle relazioni d'ordine $\rho$ in $S$ tali che $(S,\rho)$ sia un reticolo e $B$ l'insieme delle coppie ordinate di operazioni binarie in $S$ che soddisfino le proprietà associativa, commutativa e le leggi di assorbimento. Allora l'applicazione da $R$ a $B$ che a ogni $\rho\in R$ associa la coppia $(\land,\lor)$ di operazioni reticolari definite da $\rho$ è biettiva. Esempio particolarmente significativo: per ogni insieme $A$, le operazioni reticolari corrispondenti alla relazione di inclusione in $\P(A)$ sono quelle di intersezione e di unione.

Esercizi proposti (i meno urgenti sono il 3 ed il 4):

1. Determinare, in $(\Z,\cdot)$, l'insieme dei massimi comuni divisori e l'insieme dei minimi comuni multipli di $\set{0,10}$.
2. Da relazioni binarie: decidere quali degli insiemi rappresentati dai diagrammi di Hasse nell'esercizio 5 sono e quali non sono reticoli. Svolgere l'esercizio 6 tralasciando le domande su reticoli distributivi e algebre di Boole.
3. Svolgere le parti da (iii) a (vii) dell'esercizio 3 dal compito del 18 giugno 2019. Ignorare, al punto (vi), tutte le domande tranne la prima.
4. Trovare, tra i sottoinsiemi di $\P(\N)$, ordinati per inclusione:
   1. un sottoinsieme infinito totalmente ordinato;
   2. un sottoinsieme di cardinalità 5 che non sia un reticolo;
   3. un sottoinsieme di cardinalità 5 che sia un reticolo, ma non totalmente ordinato.
5. Posto $U=\set{0,2,-2}$ e $V=\set{0,2,4}$, disegnare il diagramma di Hasse dell'insieme $S=\set{\vuoto,\set 0,\set 2,U,V,2\Z,\Z\setminus\set9}$ ordinato per inclusione. $(S\sseq)$ non è un reticolo; spiegare perché. Trovare, se possibile, un $x\in S$ tale che $(S\setminus\set x,\sseq)$ sia un reticolo.
6. Dimostrare che, se $(S,\rho)$ è un reticolo e $\land$ (estremo inferiore) e $\lor$ (estremo superiore) sono le due operazioni reticolari definite in esso, allora un elemento $a$ di $S$ è neutro rispetto a $\land$ se e solo se $a=\max(S,\rho)$, è neutro rispetto a $\lor$ se e solo se $a=\min(S,\rho)$.

2/12

Discussione di esercizi dalla lezione precedente.

Per un applicazione tra reticoli sono equivalenti le proprietà di essere un isomorfismo di insiemi ordinati e quella di essere un isomorfismo tra le strutture agebriche definite dalle operazioni reticolari.

Sottoreticoli. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo. Esempi di sottoreticoli; sono sottoreticoli gli intervalli chiusi (non vuoti) nei reticoli.

Proprietà di buon ordinamento di $(\N,\le)$; giustificazione del principio di induzione (prima forma). Dimostrazioni di proprietà dei numeri naturali 'per controesempio minimo' e seconda forma del principio di induzione (o principio di induzione completa).

Divisori banali di un elemento in un monoide commutativo. Elementi irriducibili; numeri primi. Monoidi (commutativi) cancellativi, fattorizzazioni "essenzialmente uguali" e monoidi fattoriali. Teorema fondamentale dell'aritmetica (i monoidi $(\N^*,\cdot)$ e $(\Z\setminus\set0,\cdot)$ sono fattoriali); di questo teorema è stata dimostrata solo una parte: l'esistenza delle fattorizzazioni in prodotti di primi (come esempio di dimostrazione per controesempio minimo), ma non la loro essenziale unicità.

Se $M$ è un monoide commutativo, $a\in M$ e $u\in \U(M)$, allora $au$ è associato ad $a$ in $M$; se $a$ è cancellabile vale anche il viceversa: gli associati ad $a$ in $M$ sono tutti e soli gli elementi della forma $au$ al variare di $u\in \U(M)$. Esempi.

Descrizione (e numero) dei divisori in $\N^*$ di un assegnato numero intero positivo (per una generalizzazione si veda l'ultimo degli esercizi).

Esercizi proposti (i più urgenti sono i numeri 1 e 4):

1. Di ciascuna delle parti dei reticoli $(\P(\Z),\subseteq)$ o $(\R,\le)$ elencate nell'esercizio 4 della lezione del 22/11 dire se è o non è un sottoreticolo del relativo reticolo.
2. Quali sono gli elementi irriducibili in $(\N,+)$? $(\N,+)$ è un monoide fattoriale?
3. Assegnato un insieme finito $S$, quali sono gli elementi irriducibili in $(\P(S),\cup)$? $(\P(S),\cup)$ è un monoide fattoriale? $(\P(S),\cap)$ è un monoide fattoriale? Cambia qualcosa se $S$ è infinito?
4. Sia $n=2^{15}\cdot 7^{9}\cdot17\cdot 23^{4}$. Dare una descrizione dell'insieme dei divisori di $n$ in $\N$. Quanti sono? Quanti sono i divisori di $n$ in $\Z$?
5. (Descrizione dei divisori degli elementi di un monoide fattoriale) Sia $M$ un monoide fattoriale e sia $a\in M\setminus\U(M)$. Provare che se $a=p_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una fattorizzazione di $a$ in potenze di irriducibili non associati (cioè: 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$.

4/12

Discussione di esercizi dalla lezione precedente. I divisori in $\Z$ di un numero intero. Esistenza a descrizione di MCD e mcm in monoidi fattoriali. Anelli fattoriali.

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

Operazioni indotte su quozienti: discussione del problema. 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 $\sigma$ è una congruenza in una struttura di sostegno $S$, la proiezione canonica $a\in S\mapsto [a]_\sigma \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 strutture dello stesso tipo. Avvertenza: non viene conservata la cancellabilità (un controesempio è fornito più avanti).

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 equivalenze $\equiv_m$ al variare di $m\in\Z$). Sono effettivamente congruenze dell'anello $(\Z,+,\cdot)$ (è stato anche detto, ma non dimostrato, che sono le sole congruenze in $(\Z,+)$). Loro descrizione esplicita nei casi in cui $m$ è uno tra 0, 1 e 2. Per ogni intero $m$, ${\equiv_m}={\equiv_{-m}}$. Gli anelli quoziente $\Z_m$ di $(\Z,+,\cdot)$. Esempio: $\Z_4$ non è un dominio di integrità perché $[2]_4$ è in esso un divisore dello zero non nullo.

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

Esempi di calcoli in aritmetica modulare.

Esercizi proposti (sono necessari i numeri 7,8 e 9):

1. Verificare che se $a$ e $b$ sono elementi di un monoide fattoriale $(M,\cdot)$ e $d$ ed $m$ ne sono un MCD ed un mcm, allora $ab$ è associato a $dm$ in $(M,\cdot)$.
2. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
3. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con una delle operazioni $\cap$ o $\ds$?
4. 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?
5. 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$.
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 il precedente.
7. Elencare gli elementi di $[20]_6\cap\set{n\in\Z\mid -10\le n\le 10}$.
8. Provare che, per ogni $a,b,m,n\in\Z$, se $a\equiv_m b$ e $n$ divide $m$, allora $a\equiv_n b$.
9. Elencare gli interi $m$ tali che $11\equiv_m -7$ e gli interi $h$ tali che $11+3h\equiv_h -7$.
10. Scrivere le tavole di Cayley, rispetto alle operazioni di addizione e moltiplicazione, dell'anello $\Z_4$.
11. Calcolare (a mente, ci mancherebbe!) $78598!\mod 6756$.
12. Determinare (eseguendo solo calcoli a mente) $674\mod 6$, poi $674\mod -6$ ed infine $n\mod 7$ dove $n=7005(2^{10}-140)$.
13. (Esercizio a futura memoria) Sia $n$ un numero intero positivo. Come è noto, $n$ si può scrivere in base 10 rappresentandolo con la stringa “$a_t a_{t-1} a_{t-2}\dots a_2 a_1 a_0$”, dove $t\in\N^*$ e ciascuno degli $a_i$ (le 'cifre' di $n$) è un numero naturale minore di 10, intendendo con questo $n=\sum_{i=0}^t a_i 10^i$. Allora:
    • $n\equiv_{10}a_0$;
    • $n\equiv_{100}10a_1+a_0$ (il numero descritto dalle ultime due cifre di $n$);
    • $n\equiv_4 10a_1+a_0$.
    Partendo poi dall'osservazione che $10\equiv_9 1$ e $10\equiv_{11} -1$, verificare che:
    • $n\equiv_9 \sum_{i=0}^t a_i$;
    • $n$ è divisibile per 9 se e solo se la somma delle sue cifre è divisibile per 9;
    • $n$ è divisibile per 3 se e solo se la somma delle sue cifre è divisibile per 3;
    • giustificare il 'criterio di divisibilità per 3' e la 'prova del 9' che vengono insegnati nella scuola elementare;
    • $n\equiv_{11} \sum_{i=0}^t (-1)^i a_i$.
    Usare quanto visto sopra per calcolare (a mente) $\rest(72543618991175,9)$ e $\rest(72543618991175,3)$, e poi $\rest(626\cdot 3125,3)$.

6/12

Discussione di esercizi dalla lezione precedente.

Il teorema sulla divisione con resto (o divisione aritmetica) in $\Z$. Relazione di congruenza modulo un intero non nullo $m$ come nucleo di equivalenza della funzione $n\in\Z\mapsto n\mod m\in\N$.

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

Estensione dell'algoritmo euclideo e teorema di Bézout, nella forma: se $a,b\in\Z$ e $d$ è un massimo comun divisore tra $a$ e $b$, allora $d$ è una combinazione lineare di $a$ e $b$ a coefficienti in $\Z$. La dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, diversa da quella nel libro di testo. Equazioni diofantee (di primo grado in due incognite). Versioni alternative del teorema di Bézout: se $a,b\in\Z$ e $d$ è un MCD tra $a$ e $b$,

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

Se un'equazione diofantea (del tipo appena descritto) ha soluzioni, ne ha infinite.

Equazioni di primo grado in un quoziente di $\Z$; equazioni congruenziali di primo grado ad una incognita: 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.

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

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

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

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

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

Esercizi proposti (sono prioritari i primi 3):

1. Calcolare $\rest(10,7)$, $\rest(10,-7)$, $\rest(-10,7)$, $\rest(-10,-7)$.
2. 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).
3. Svolgere l'esercizio 7 dal compito del 16 gennaio 2019 e calcolare, poi, l'insieme delle soluzioni dell'equazione congruenziale $16x+7\equiv_{144}2x+1$.
4. Utilizzando la conclusione $3=117\cdot 13+66(-23)$ ottenuta in aula illustrando l'algoritmo euclideo esteso, trovare gli insiemi delle soluzioni delle equazioni congruenziali $66 x\equiv_{117}10$, $660 x\equiv_{1170}90$ e $1170 x\equiv_{660}90$.
5. Svolgere gli esercizi 5 a 12 da Tautologie, insiemi, aritmetica.
6. Di ciascuno degli elementi di $\Z_4$, $\Z_{11}$, $\Z_{10}$, $\Z_{12}$ dire se è o non è un elemento invertibile, un elemento cancellabile, un divisore dello zero. Degli elementi invertibili di $\Z_{10}$ trovare anche gli inversi.
7. Indicando, per ogni $n\in\Z$, con $\bar n$ la classe $[n]_{66}$, in $\Z_{66}$ dire quali tra $\bar 7$, $\bar 8$, $\overline {667}$, $\overline{1000}$ sono invertibili, e di questi determinare gli inversi.
8. 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$.
9. Autoassegnarsi e risolvere un gran numero di equazioni congruenziali a caso.
10. Usando l'algoritmo euclideo esteso, trovare, ove possibile, soluzioni delle equazioni diofantee $14x+6y=1$, $14x+6y=4$, $140x+60y=20$. Di una di esse, trovare tre diverse soluzioni.
11. 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$
12. 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.
13. Bertrando deve dare a Filiberto un certo numero $n$ di chiodi (non uno di più, non uno di meno) di un certo tipo, ma questi chiodi sono disponibili solo in confezioni da 36 e da 120 chiodi, che non vanno assolutamente aperte. Sapendo che Bertrando e Filiberto hanno a disposizione quantità illimitate di entrambi i tipi di queste confezioni, per quali valori di $n$ è possibile che Bertrando dia a Filiberto i chiodi richiesti (senza aprire nessuna confezione)? È, ad esempio, possibile farlo per $n=100$? E, nel caso, in che modo? E per $n=300$?

9/12

Discussione di esercizi dalla lezione precedente.

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

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

L'anello dei polinomi (ad una indeterminata) su un anello commutativo unitario $A$ (come dalle note, che sono state appena aggiornate). Definizione e terminologia essenziale (grado, successione dei coefficienti, coefficiente direttore, termine noto, polinomi monici, polinomi costanti). Proprietà universale per anelli di polinomi. Conseguenze: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata); l'omomorfismo di sostituzione; per ogni intero positivo $m$, l'omomorfismo suriettivo da $\Z[x]$ a $\Z_m[x]$ che ad ogni polinomio $f$ a coefficienti interi associa "$f$ riguardato modulo $m$".

Grado di somma, differenza e prodotto tra due polinomi. Se il polinomio $f\in 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)$.

Esercizi proposti (concentrarsi in primo luogo sugli ultimi quattro):

1. Sia $x$ un elemento periodico di periodo $n$ di un gruppo $(G,\cdot)$ con elemento neutro $t$. Mostrare che, per ogni $\ell\in\Z$ si ha: $x^\ell$ se e solo se $n$ divide $\ell$. Mostrare anche che il sottogruppo generato da $\set x$ in $G$ ha esattamente $n$ elementi.
2. Calcolare il periodo di $[1]_8$ in $(\Z_8,+)$.
3. Calcolare il periodo di $[7]_{25}$ in $(\U(\Z_{25}),\cdot)$ e calcolare, di conseguenza, $7^{82}\mod 25$.
4. Trovare tutti gli elementi periodici nel gruppo $(\R\setminus\set 0,\cdot)$.
5. 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.
6. Per ogni numero primo positivo $p$, si stabilisca il grado del polinomio $f_p:=\overline{22}x^5+\bar 8 x^4 - \bar7x^2+\bar 3$ a coefficienti nel campo $\Z_p$. Per quali primi positivi $p$ il polinomio $f_p$ è monico?
7. Vero o falso: tutti i polinomi non nulli in $\Z_2[x]$ sono monici.
8. Sia $f$ il polinomio $\bar 7x^3-\bar 1\in\Z_{10}[x]$. Supposto assegnato (ma non noto) $g\in\Z_{10}[x]$, sapendo che $g$ ha grado 6 siamo in grado di stabilire che grado ha $fg$? Ripetere l'esercizio dopo aver sostituito $f$ con $\bar 6x^3-\bar 1\in\Z_{10}[x]$.
9. Sia $f$ il polinomio $\bar 7x^3-\bar 1\in\Z_{43}[x]$. Trovare, se esiste, (o spiegare perché non esiste) un polinomio $g\in\Z_{43}[x]$ tale che $fg$ sia monico di grado 10.

11/12

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

Discussione di esercizi dalla lezione precedente.

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

$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. Qualunque sia $A$ i polinomi in $A[x]$ che siano cancellabili e di grado maggiore di zero (ad esempio, $x$) non sono invertibili; di conseguenza $A[x]$ non è un campo.

Divisione con resto (o divisione lunga) tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto, con un esempio. Se $A$ è un campo è sicuramente possibile effettuare la divisione per un qualsiasi polinomio non nullo. Di conseguenza, nell'anello dei polinomi su un campo si può eseguire l'algoritmo euclideo per la ricerca di un MCD e valgono il teorema di Bézout ed il lemma di Euclide (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; due qualunque polinomi associati hanno esattamente le stesse radici.

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

Anelli fattoriali. 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.

Se $A$ è un campo, un polinomio in $A[x]$ ha radici in $A$ se e solo se ha un divisore di grado uno in $A[x]$. Caratterizzazione dei polinomi irriducibili nell'anello dei polinomi su un campo; esistenza di radici ed irriducibilità.

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

Polinomi in $\Q[x]$. Ciascuno di essi è associato (in $\Q[x]$) ad un polinomio a coefficienti interi, che ha quindi le stesse radici e fattorizzazioni in irriducibii essenzialmente uguali a quelle del polinomio originale. 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. Il criterio di Eisenstein ed il risultato sulle radici in $\Q$ non sono stati dimostrati.

Esercizi proposti (sono tanti; hanno priorità i numeri 2, 4 e 8):

1. Provare che se $A$ è un anello commutativo unitario e la regola di addizione dei gradi vale per tutti i prodotti tra polinomi di $A[x]$, allora $A$ è un dominio di integrità.
2. Se possibile, trovare un polinomio di coefficiente direttore 340 che sia associato in $\Q[x]$ a $3x^2-1$.
3. 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]$).
4. Si costruisca, se possibile, un polinomio di grado 300 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-100\le n \lt 100$.
5. Determinare in $\Z_2[x]$ tutti i polinomi di grado 2, 3 o 4 che siano irriducibili.
6. Sia $f=x^4-4\in \Z[x]$. Scrivere $f$ come prodotto di polinomi monici irriducibili in $\Q[x]$ e come prodotto di polinomi monici irriducibili in $\R[x]$.
7. Scrivere il polinomio $x^5-x\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Fare lo stesso per $x^5-x\in\Z_7[x]$.
8. Utilizzando il teorema di Ruffini come punto di partenza, scrivere il polinomio $f=\bar 2 x^4+x+\bar 1\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Trovare poi l'associato monico di $f$ in $\Z_5[x]$.
9. Svolgere, almeno in parte, gli esercizi nr. 1, 2, 3 e 8 da Polinomi e strutture algebriche, facendo uso dell'algoritmo euclideo.
10. Trovare tutte le radici in $\Q$ del polinomio $2x^{10}+x^9-x^8+12x^2-3$.
11. Il polinomio $50x^{12}-6x^5+18x-24$ è irriducibile in $\Q[x]$? E $x^3-9$?
12. Scrivere $x^3-3x^2+4$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
13. Per ogni $n\in\Z$, sia $f_n=(100+4n)x^4+(n+8)x^3+nx^2+1$ e sia $\bar {f_n}\in \Z_{11}[x]$ il polinomio $f_n$ riguardato come polinomio a coefficienti in $\Z_{11}[x]$. Sia $L=\{n\in\N \mid \nu \bar {f_n}=2\}$. Decidere se $L=\vuoto$ o $L\ne\vuoto$; nel secondo caso, posto $m=\min L$, scrivere l'associato monico di $\bar {f_m}$ in $\Z_{11}[x]$. Ripetere l'esercizio dopo aver ridefinito $f_n$ come $(100+4n)x^4+(n-8)x^3+nx^2+1$.
14. Tra i seguenti polinomi, dire quali sono e quali non sono irriducibili in $\Q[x]$ e quali sono e quali non sono irriducibili in $\R[x]$: $x^3+1$, $x^2+1$, $(8x^2+1)(x^2+3)$, $13x^9+50x^7+10$, $x^{1066}-7^{1066}$. Riguardati i polinomi precedenti a coefficienti in $\Z_5[x]$, dire quali sono irriducibili in $\Z_5[x]$.
15. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
16. I testi delle prove scritte contengono un gran numero di esercizi sui polinomi. Si guardino, ad esempio, gli esercizi 4 dal compito di gennaio 2015, 5 dal compito di ottobre 2016, 4 dal compito di maggio 2016, 4 dal compito di giugno 2016, 5 dal compito di ottobre 2016, 5 dal compito di gennaio 2017, 6 dal compito di maggio 2018, 6 dal compito di marzo 2019, 4 dal compito di giugno 2019, 4 dal compito di settembre 2019.

13/12

Dimostrazione del teorema sulle radici razionali dei polinomi a coefficienti interi enunciato alla fine della lezione precedente.

Il materiale del resto di questa lezione è coperto dalle note sulle strutture booleane.

Anelli booleani; esempio: per ogni insieme $S$ l'anello delle parti di $S$ è booleano. Proprietà degli anelli booleani: sono commutativi e, in essi, ogni elemento coincide col suo opposto (cioè: questi anelli hanno caratteristica al più 2). Enunciato del teorema di Stone (per ogni anello booleano $R$ esiste un insieme $S$ tale che $R$ sia isomorfo ad un sottoanello unitario di $(\P(S),\ds,\cap)$; se inoltre $R$ è finito esiste un insieme $S$ tale che $R\iso\P(S)$). Conseguenze: la cardinalità di un anello booleano finito è necessariamente una potenza di 2; due anelli booleani finiti della stessa cardinalità sono necessariamente isomorfi.

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.

Reticoli booleani. Algebre di Boole. Equivalenza tra queste due nozioni (compresa l'equivalenza tra le rispettive nozioni di isomorfismo). Sottoalgebre di Boole. Alcune identità, tra cui le leggi di De Morgan, in algebre di Boole.

Dualità per reticoli complementati, per reticoli distributivi, per reticoli booleani, per algebre di Boole. L'operazione unaria di complemento definisce un isomorfismo tra un'algebra di Boole e la sua duale.

Costruzione di un'algebra di Boole (ovvero, di un reticolo booleano) a partire da un anello booleano e costruzione (inversa) di un'anello booleano a partire da un'algebra di Boole (per la seconda costruzione non sono state effettuate verifiche). I sottoanelli unitari di un anello booleano sono tutte e sole le sottoalgebre della corrispondente algebra di Boole. Equivalenza tra lo studio dei reticoli booleani, delle algebre di Boole, degli anelli booleani; coincidenza delle corrispondenti nozioni di isomorfismo. Di conseguenza: teorema di Stone per reticoli booleani e per algebre di Boole, e corollari: 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).

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

Esercizi proposti:

1. Armatisi di pazienza, trovare due radici in $\Q$ del polinomio $f=x^5+(4/3)x^4-(17/3)x^3-x^2-(5/3)x-(2/3)$. Scrivere poi $f$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
2. Si disegni il diagramma di Hasse dell'insieme dei divisori di $30$, stabilendo se si tratta di un reticolo, di un reticolo distributivo, di un reticolo complementato, di un reticolo booleano. Se possibile, trovarne un sottoreticolo di cardinalità 7 e/o un sottoreticolo di cardinalità 5.
3. Completare gli esercizi 5, 6 e 7 da relazioni binarie, intendendo 'algebra di Boole' come sinonimo di 'reticolo booleano'.
4. Svolgere gli esercizi 2, 4, 8 e 11 dalle note sulle strutture booleane.
5. 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, nel caso se è distributivo, complementato, booleano, se è 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}$.
6. Costruire un esempio di reticolo complementato con un sottoreticolo non complementato. Suggerimento: cercare una catena nel reticolo delle parti di un insieme.
7. Costruire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi e tutti gli altri elementi hanno esattamente un complemento.
8. Di un reticolo $L$ sappiamo che è complementato e che ha esattamente 675 elementi. Possiamo stabilire se è distributivo?
9. Degli insiemi ordinati discussi nell'esercizio 4 della lezione del 22/11 e nei primi due della lezione del 27/11, dire quali sono reticoli distributivi e quali sono reticoli complementati.
10. Stabilire per quali $n\in\set{0,15,16,20,15\cdot 77}$ il reticolo dei numeri naturali divisori di $n$ (ordinato per divisibilità in $\N$) è booleano.
11. Sia $S=\set{n\in\N\mid n\lt 10}$. Verificare che $B=\set{x\in\P(S)\mid 1\in x\iff 5\in x}$ è una sottoalgebra di Boole dell'algebra di Boole delle parti di $S$.
12. Completare l'esercizio 3 dal compito del 18 giugno 2019.
13. Svolgere gli esercizi nr. 3 dai compiti di marzo 2014 e di novembre 2018. Esercizi su insiemi ordinati e reticoli si trovano, del resto, in ogni prova d'esame.

16/12

Cenni informali a 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. Sottografi.

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; nei multigrafi finiti questi ultimi sono in numero pari.

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

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.

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

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

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

Esercizi proposti:

1. Esercizi da Grafi, ad esclusione del nr. 4.
2. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) su meno di cinque vertici. Identificare tra questi gli alberi.
3. 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, un grafo connesso che verifichi $\Phi$.
   4. Disegnare, se possibile, due grafi tra loro non isomorfi che verifichino $\Phi$.
   5. Disegnare, a meno di isomorfismi, tutti i grafi che verificano $\Phi$.
4. Stablire per quali interi positivi $n$ il grafo completo su $n$ vertici abbia cammini euleriani e per quali abbia circuiti euleriani.