22/9

Introduzione al corso: presentazione, informazioni generali, modalità di svolgimento. Informazioni sugli appelli d'esame.

Cenni sulla logica proposizionale: nozioni informali di linguaggio, formula, proposizione (formula chiusa). I principali connettivi proposizionali (introdotti e descritti solo semanticamente): negazione, congiunzione, disgiunzione inclusiva, disgiunzione esclusiva (XOR), congiunzione negata (NAND), equivalenza (o bicondizionale), implicazione (condizionale). Comparazione tra il loro uso e quello di espressioni analoghe del linguaggio naturale. Tabelle (o tavole) di verità, con esempi del loro uso in calcolo proposizionale. Tautologie e contraddizioni. Diversi esempi di tautologie: principî del terzo escluso e di non contraddizione, legge delle doppia negazione, commutatività di congiunzione, disgiunzione, bicondizionale, idempotenza e associatività della congiunzione e della disgiunzione (quest'ultima lasciata per esercizio); alcune tautologie sull'implicazione (doppia implicazione, implicazione come disgiunzione, negazione dell'implicazione, legge di contrapposizione); leggi di De Morgan. Per il connettivo di implicazione non vale la commutatività.

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

Esercizi proposti:

1. Negare la frase "Se non piove, Aldo, Bruno e Carlo giocano a golf".
2. Verificare l'associatività del connettivo di disgiunzione (inclusiva).
3. Svolgere quanti più è possibile tra gli esercizi A, B, C, D, E da Logica rudimentale (alcuni li abbiamo visti a lezione); dovendo fare una selezione, consiglio gli A, B.1, B.4, C.1, C.2, i D, E.1, E.4. Prima di svolgere C.1 si può guardare come, nel paragrafo che precede l'esercizio, viene verificata la distributività della congiunzione rispetto alla disgiunzione.
4. Se indichiamo con $p$ la formula “$3x\lt 4$” e con $q$ la formula “$y+1=z$”, quale connettivo proposizionale va inserito al posto di “$*$” in modo che la formula $p\mathop * q$ traduca (dal punto di vista della logica proposizionale) la frase “$3x\lt 4$, nonostante $y+1=z$”?
5. La forma proposizionale $\bigl(q\iff r\bigr)\iff \bigl((p\land q)\iff(p\land r)\bigr)$ è una tautologia?

24/9

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Altre tautologie: transitività dell'implicazione, distributività della congiunzione rispetto alla disgiunzione ed a XOR, associatività di bicondizionale e XOR.

Osservazioni sulla interdipendenza tra i connettivi binari: per esprimerli tutti bastano $\lnot$ e $\land$ (ovvero $\lnot$ e $\lor$) o, addirittura, il solo NOR (o il solo NAND).

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

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

Quantificatori ristretti. Formule con quantificatori ristretti ad una condizione impossibile (come $(\forall x\in\varnothing)(\dots)$ o $(\exists x\in\vuoto)(\dots)$.

Negazione di formule universali e di formule esistenziali (anche con quantificatori ristretti). Interdipendenza tra $\forall$ e $\exists$.

Alcune altre regole della logica dei predicati. Frasi contenenti più quantificatori; esempi di frasi delle forme $\forall x\exists y(\dots)$ o $\forall x\exists y(\dots)$.

Esercizi proposti:

1. Svolgere gli esercizi proposti nella lezione precedente e non ancora svolti.
2. Quali tra le seguenti sono tautologie? $(p\xor q)\xor (p\xor (\lnot q))$, $\quad(p\implica q)\implica ((p\xor q)\implica q)$
3. Esercizi G.1, G.3, tutti gli H da Logica rudimentale.
4. Negare la formula: $\exists x (\forall y (\phi(x,y))\implica \forall x (\exists y (\psi(x,y))$.
5. Assumendo che tutte le variabili varino nell'insieme dei numeri interi positivi, ed assumendo l'usuale interpretazione dei simboli, dire quali proposizioni sono vere e quali false:
   1. $\forall x (x>5\Implica x>1)$;
   2. $\forall x (x>1\Implica x>5)$;
   3. $\exists x (x>1\Implica x>5)$;
   4. $\exists x (x>1\iff x>5)$;
   5. $\forall x (\exists y(y>x\Implica y\lt x))$;
   6. $\forall x (\exists y(y>x\iff y\lt x))$.

29/9

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Nozione di insieme. Il simbolo '$\in$' di appartenenza. Assioma di estensionalità. Cenni a problemi fondazionali: estensione di un predicato unario. Antinomia di Russell. Schema di assiomi di separazione.

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

Predicati unari, loro estensioni e formule insiemistiche ricavate da tautologie (come nella sezione finale di Logica rudimentale, ma si veda anche Tautologie e identità insiemistiche): operazioni insiemistiche (unione ed intersezione binarie, complemento relativo, differenza simmetrica) e loro proprietaà. Tra queste: formule (insiemistiche) di De Morgan.

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

Esercizi proposti:

1. Svolgere gli esercizi J da Logica rudimentale.
2. Descrivere esplicitamente gli insiemi $\set{x\mid x=\vuoto}$, $\set{x\mid \forall y (x\subseteq y)}$, $\set{x\mid \forall y (x\in y)}$, $\set{x\mid \forall y (x=y)}$.
3. Rappresentare, in diagrammi di Venn generici, i termini insiemistici $a\ds b$, $(a\ds b)\ds c$, $(a\ds b)\setminus c$.
4. Dimostrare: $(\forall a,b)(a\ds b)=(a\cup b)\setminus(a\cap b)=(a\setminus b)\cup (b\setminus a)$.
5. Per quali coppie di insiemi $a, b$ si ha $a\setminus b=b\setminus a$?
6. Utilizzando diagrammi di Venn, stabilire se per ogni terna di insiemi $a,b,c$ si ha o meno una tra $a\setminus (b\setminus c)\subseteq (a\setminus b)\setminus c$ e $(a\setminus b)\setminus c\subseteq a\setminus (b\setminus c)$; se qualcuna delle due formule non è universalmente valida, trovare un controesempio esplicito. Ripetere l'esercizio confrontando tra loro $a\setminus (b\ds c)$ e $(a\setminus b)\ds(a\setminus c)$.

1/10

Discussione di alcuni degli esercizi proposti nella lezione precedente, con approfondimenti.

Unione unaria ($\bigcup a$, per un arbitrario insieme $a$) e intersezione unaria ($\bigcap a$, solo per $a\ne\vuoto$). Scritture del tipo $\bigcup_{i\in\ I}A_i$ e $\bigcap_{i\in\ I}A_i$ (unioni ed intersezioni di famiglie; sulla nozione di famiglia bisognerà tornare). Formule infinitarie di De Morgan (se $S$ ed $A$ sono insiemi e $A\ne\vuoto$, $S\setminus\bigcap A=\bigcup\set{S\setminus a\mid a\in A}$ e $S\setminus\bigcup A=\bigcap\set{S\setminus a\mid a\in A}$).

Diagrammi di Euler-Venn e cardinalià (numero degli elementi) di un insieme finito. Il principio di inclusione-esclusione per il calcolo del numero degli elementi di unioni finite di insiemi finiti, con verifica dettagliata nel caso dell'unione di due o tre insiemi.

Coppie ordinate (solo un cenno alla definizione di Kuratowski, vedi esercizi). Prodotto cartesiano tra due insiemi. $\forall a,b(a\times b=\vuoto\iff (a=\vuoto\lor b=\vuoto))$. Se $a$ e $b$ sono finiti, $|a\times b|=|a|\cdot|b|$. Terne ordinate. Corrispondenze tra due insiemi; diversi modi per rappresentarle (diagrammi, tabelle). Relazioni binarie in un insieme. La diagonale $\Delta_S=\set{(x,x)\mid x\in S}$ di un insieme $S$ (è il grafico della relazione di uguaglianza in $S$). Notazioni: $\Corr(A,B)$ e $\Rel(A)=\Corr(A,A)$, per insiemi $A$ e $B$.

Prodotto relazionale tra corrispondenze e sua associatività.

Esercizi proposti:

1. Si verifichi la formula infinitaria di De Morgan non dimostrata a lezione.
2. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=10$ e $|B|=7$. Sapendo che $3\le |A\cap B|\lt 5$, cosa possiamo dire su $|A\cup B|$?
3. 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ò usare questa osservazione per dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. Questa è la cosiddetta definizione di Kuratowski della nozione di coppia ordinata).
4. Elencare gli elementi di $S\times T$, dove $S=\set{1,2,3}$, $T=\set{a,b}$ e $a\ne b$.
5. Siano $a$ e $b$ due insiemi. Si ha $a\times b=b\times a$ se e solo se …?
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$.

6/10

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Applicazioni tra insiemi. Dominio e codominio. Il problema della "buona" (corretta) definizione di un'applicazione; vari esempi. Nel corso della presentazione di alcuni esempi è sono stati definiti, per ogni insieme $S$, l'insieme $\P(S)$ delle parti di $S$ e, per ogni $n\in\N$, l'insieme $\P_n(S)$ delle $n$-parti (cioè parti di cardinalità $n$) di $S$.

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

Composizione (prodotto operativo) tra applicazioni: il prodotto relazionale tra due applicazioni componibili è sempre un'applicazione. Notazioni equivalenti: $\Map(A,B)$, $B^A$, ${}^AB$, per l'insieme delle applicazioni da $A$ a $B$. Notazione: $\beta\circ\alpha:=\alpha\beta$. Applicazione identica $\id_S$ di un insieme $S$ e sua proprietà di neutralità: se $\alpha$ è una corrispondenza da un insieme $A$ ad un insieme $B$, allora $\alpha\id_B=\id_A\alpha=\alpha$. Esempio: due applicazioni (costanti) $\alpha$ e $\beta$ da un insieme $S$ a se stesso tali che $\alpha\beta\ne\beta\alpha$. Trasformazioni di un insieme, cioè applicazioni da un insieme a se stesso.

Immagine $\im f$ di un'applicazione $f$. Applicazioni suriettive.

Ridotte, restrizioni, prolungamenti, di un'applicazione. L'immersione in un insieme di una sua parte (se $X$ è una parte di un insieme $Y$, l'immersione di $X$ in $Y$, spesso indicata con $X\hookrightarrow Y$, è l'applicazione $x\in X\mapsto x\in Y$, cioè la restrizione ad $X$ di $\id_Y$). Restrizioni di un'applicazione $f$ come composte tra un'immersione ed $f$.

Esercizi proposti:

1. La corrispondenza: $n\in\Z\mapsto n^2/2\in\Z$ è un'applicazione ben definita?
2. Indicato con $\R^+_0$ l'insieme dei numeri reali non negativi (cioè: $\R^+_0=\set{a\in\R\mid a\ge 0}$), si stabilisca quali delle seguenti corrispondenze sono applicazioni:
   • $\alpha\colon \R\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\beta\colon \R^+_0\to \R$, di grafico $\set{(a,b)\in\R\times\R\mid a=b^2}$;
   • $\gamma\colon \R^+_0\to \R^+_0$, di grafico $\set{(a,b)\in\R\times\R^+_0\mid a=b^2}$;
3. Date le applicazioni $f\colon X\in\P(\N)\mapsto X\cup \set 1 \in\P(\N)$ e $g\colon X\in\P(\N)\mapsto X\setminus \set 1 \in\P(\N)$, descrivere le applicazioni composte $f\circ g$ e $g\circ f$. Di ciascuna delle due, si stabilisca se è suriettiva.
4. Di ciascuna delle seguenti applicazioni si stabilisca se è suriettiva:
   • $n\in\Z\longmapsto |n|\in\N$;
   • $\set{a,b,c}\in\P_3(\Z)\longmapsto a+b+c\in\Z$;
   • $\set{a,b,c}\in\P_3(\N)\longmapsto a+b+c\in\N$;
5. Sia $S=\set{a,b,c}$, dove $|S|=3$, e $T=\set{0,1}$. Descrivere tutte le applicazioni da $S$ a $T$ e stabilire quali tra esse non sono suriettive.
6. Siano $A=\set{0,1,2}$ e $B=A\setminus\set 2$. Scrivere tutti i prolungamenti ad $A$ (cioè: che abbiano $A$ come dominio) dell'immersione di $B$ in $A$. Quanti sono?

8/10

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Applicazioni iniettive; negazione della iniettività. Diversi esempi. Applicazioni biettive. Ogni applicazione il cui dominio ha meno due elementi è iniettiva; ogni applicazione ha un restrizioni iniettive. Le restrizioni di applicazioni iniettive sono a loro volta iniettive.

La composta di due applicazioni suriettive (risp. iniettive, biettive) è necessariamente suriettiva (risp. iniettiva, biettiva). Parziale inversione di questo risultato: se la composta $g\circ f$ di due applicazioni è suriettiva allora quella che agisce per seconda (cioè $g$) è suriettiva; se invece $g\circ f$ è iniettiva allora $f$ è iniettiva. Un esempio di applicazione identica (quindi biettiva) che si possa scrivere come applicazione composta $g\circ f$, dove $g$ non è iniettiva ed $f$ non è suriettiva.

Sezioni e retrazioni di un'applicazione. Nozione di applicazione inversa. Teorema: un'applicazione è suriettiva se e solo se ha una sezione; è iniettiva se e solo se ha una retrazione oppure ha dominio vuoto. Alcuni esempi.

Osservazione: dire che un'applicazione $f$ è una retrazione di un'applicazione $g$ equivale a dire che $g$ è una sezione di $f$; dunque tutte le sezioni sono iniettive e tutte le retrazioni sono suriettive.

Unicità dell'inversa: se un'applicazione $f$ ha sia una retrazione $r$ che una sezione $s$, allora $r=s$, dunque $r$ è inversa di $f$; inoltre, $r$ è l'unica retrazione, l'unica sezione e dunque l'unica inversa di $f$. Teorema: le applicazioni invertibili (cioè dotate di inversa) sono precisamente quelle biettive. Osservazione ulteriore: un'applicazione è biettiva se e solo se ammette una ed una sola sezione.

Esercizi proposti:

1. Svolgere gli esercizi 3 (escluso il punto f) e 4 da Tautologie, insiemi, aritmetica. (Notazione: $\N^\#=\N^+=\N\setminus\set0$).
2. Siano $f$ e $g$ due applicazioni suriettive componibili. Descrivere, in termini di una sezione di $f$ ed una di $g$, una sezione di $g\circ f$.
3. Elencare tutte le sezioni dell'applicazione $f\colon X\to Y$, dove $X=\set{1,2,3,4}$, $Y=\set{a,b}$, con $a\ne b$ e, per ogni $n\in X$, $f(n)$ è $a$ se $n$ è pari, $b$ se $n$ è dispari.
4. Descrivere tutte le sezioni ed almeno tre retrazioni distinte dell'immersione di $\N$ in $\Z$.
5. Assegnato un insieme $S$, supponiamo che $f\colon S\to S$ sia un'applicazione tale che $f\circ f=\id_S$. Possiamo concludere che $f$ è biettiva? Nel caso, ne conosciamo l'inversa?
6. Usando l'esercizio precedente, dimostrare che, scelto comunque un insieme $A$, l'applicazione $X\in\P(A)\mapsto A\setminus X\in \P(A)$ è biettiva e trovarne l'inversa.
7. Provare che l'applicazione $f\colon n\in\N\longmapsto \begin{cases} n/2,&\text{se $n$ è pari}\\ -(n+1)/2,&\text{se $n$ è dispari}\end{cases}\in\Z$ è biettiva. Qual è l'inversa?
8. Tra le applicazioni da $\N$ a $\Z$ trovarne: una iniettiva non suriettiva, una suriettiva non iniettiva, una né iniettiva né suriettiva.

13/10

Discussione di uno degli esercizi proposti nella lezione precedente, con approfondimenti. Costruzione esplicita dell'inversa di un'applicazione biettiva, con esempi. Rilevanza della nozione di invertibilità.

Applicazione immagine $\vec f\colon\P(A)\to\P(B)$ ed applicazione antiimmagine $\antivecf\colon\P(B)\to\P(A)$ definite da un'applicazione $f\colon A\to B$. Con queste notazioni si ha $\vec f(\vuoto)=\antivecf(\vuoto)=\vuoto$, $\,\vec f(A)=\im f$, $\,\antivecf (B)=\antivecf (\im f)=A$. Diversi esempi. Alcune proprietà (non tutte dimostrate, le dimostrazioni mancanti sono tra gli esercizi): per ogni $X\subseteq A$ e $Y\subseteq B$ si ha $X\subseteq\antivecf(\vec f( X))$ e $\vec f(\antivecf(Y))\subseteq Y$, ma, in generale, possono non valere le corrispondenti uguaglianze. Se $U,V\subseteq A$, $\vec f(U\cup V)=\vec f(U)\cup\vec f(V)$ e $\vec f(U\cap V)\subseteq \vec f(U)\cap\vec f(V)$, ma anche in questo caso, l'uguaglianza può non valere. Le applicazioni immagine e antiimmagine definite da applicazioni identiche sono applicazioni identiche; se $f$ e $g$ sono applicazioni componibili, $(f\circ g)\vecvuoto=\vec f\circ \vec g$  e $(f\circ g)\antivecvuoto=\antivecg\circ \antivecf$. Per ogni $X\subseteq A$ e $Y\subseteq B$ si ha $X\subseteq\antivecf(\vec f( X))$ e $\vec f(\antivecf(Y))\subseteq Y$, ma, in generale, possono non valere le corrispondenti uguaglianze. Se $U,V\subseteq A$, $\vec f(U\cup V)=\vec f(U)\cup\vec f(V)$ e $\vec f(U\cap V)\subseteq \vec f(U)\cap\vec f(V)$, ma anche in questo caso, l'uguaglianza può non valere; inoltre $\vec f(U)\subseteq \vec f(V)$ se $U\subseteq V$; analogamente, se $S\subseteq T\subseteq B$ allora $\antivecf(S)\subseteq\antivecf(T)$. Diversi esempi.

Il numero delle applicazioni ed il numero delle applicazioni iniettive tra due insiemi finiti. Fattoriali discendenti (notazione: $n^{\underline m}=n(n-1)(n-2)\cdots(n-m+1)$). Fattoriali.

Criterio di esistenza di applicazioni iniettive/suriettive/biettive tra assegnati insiemi finiti: se $A$ e $B$ sono insiemi finiti, allora esistono applicazioni iniettive da $A$ a $B$ se e solo se $|A|\le |B|$; esistono applicazioni suriettive da $A$ ad $B$ se e solo se $|A|\ge |B|$ e $B=\vuoto\implica A=\vuoto$; esistono applicazioni biettive da $A$ ad $B$ se e solo se $|A|=|B|$. Per un'applicazione $f$ tra due insiemi finiti con lo stesso numero di elementi sono equivalenti: $f$ è iniettiva, $f$ è suriettiva, $f$ è biettiva. L'insieme delle trasformazioni $T(A)=A^A$ e quello $\Sym(A)$ delle permutazioni di un insieme $A$; se $A$ è finito, $|\Sym(A)|=|A|!$.

Cenni al confronto tra cardinalità tra insiemi infiniti (cardinalità di $\N$, $\Z$, $\Q$, $\R$), menzione del teorema di Cantor: $\forall x (|\P(x)|>|x|)$.

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

Esercizi proposti:

1. Sia $v$ l'applicazione valore assoluto in $\Z$, cioè $v\colon n\in\Z\mapsto |n|\in\Z$. Posto $A=\set{n\in\Z\mid -10 \lt n \lt 20}$, si calcolino $\vec v(A)$, $\antivecv(A)$, $\vec v(\antivecv(A))$, $\antivecv(\vec v (A))$.
2. [Parte di questo esercizio è stato svolto a lezione.] Sia $f\colon A\to B$ un'applicazione. Provare che,
   • per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y\cap \im f$.
   • $f$ è iniettiva se e solo se per ogni $X\subseteq A$ si ha $X=\antivecf (\vec f(X))$ (cioè se e solo se $\antivecf\circ\vec f$ è l'identità di $\P(A)$); $f$ è suriettiva se e solo se per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y$ (cioè se e solo se $\vec f\circ\antivecf$ è l'identità di $\P(A)$).
   • $f$ è iniettiva se e solo se per ogni $U,V\subseteq A$ si ha $\vec f(U\cap V)= \vec f(U)\cap\vec f(V)$.
   • Sono equivalenti: $f$ è iniettiva; $\vec f$ è iniettiva; $\antivecf$ è suriettiva. Dualmente, sono equivalenti: $f$ è suriettiva; $\vec f$ è suriettiva; $\antivecf$ è iniettiva. Infine, sono equivalenti: $f$ è biettiva; $\vec f$ è biettiva; $\antivecf$ è biettiva. Se queste ultime si verificano, $\vec f$ e $\antivecf$ sono una l'inversa dell'altra.
   • Per ogni $U, V\subseteq B$, $\antivecf(U\cup V)=\antivecf(U)\cup \antivecf(V)$ e $\antivecf(U\cap V)=\antivecf(U)\cap \antivecf(V)$.
3. Siano $A=\set{1,2,3,4}$ e $B=\set{x,y}$, dove $|B|=2$. Dire quante sono le applicazioni da $A$ a $B$, quante quelle da $B$ ad $A$, quante quelle iniettive da $A$ a $B$ e quante quelle iniettive da $B$ ad $A$.
4. Elencare tutte le applicazioni iniettive di cui all'esercizio precedente.
5. Siano $A=\set{1,2,3}$ e $B=\set{u,v,w}$, dove $|B|=3$. Quante sono le applicazioni biettive da $A$ a $B$? Elencarle tutte. Descrivere l'inversa di almeno due di esse.

15/10

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

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

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

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

Esercizi proposti:

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

20/10

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche, antisimmetriche, transitive. Confronto tra queste proprietà; negazione di ciascuna di esse, loro espressione in termini di proprietà (insiemistiche) del grafico. Esempi, tra gli altri con relazioni in insiemi finiti descritte da tabelle quadrate. Un'osservazione su come semplificare la verifica della transitività di una relazione binaria $\rho$ su un insieme $A$: se $x,z\in A$ e $y\in \set{x,z}$, allora l'implicazione $((x\mathrel\rho y)\land(y\mathrel\rho z))\implica x\mathrel\rho z$ è banalmente verificata.

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

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

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$;
• $a\sim b \iff b\sim a \iff a\in[b]_\sim\iff b \in [a]_\sim\iff [a]_\sim=[b]_\sim\iff [a]_\sim\cap [b]_\sim\ne \vuoto$.

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

Proiezione canonica $a\in A\mapsto [a]_\sim\in A/{\sim}$ definita da una relazione di equivalenza $\sim$ su un insieme $A$. Ogni equivalenza è il nucleo di equivalenza di un'applicazione: ad esempio, della proiezione canonica che essa definisce.

Classi di equivalenza rispetto al nucleo di equivalenza di un'applicazione: se $\sim$ è il nucleo di equivalenza di un'applicazione $f$ di dominio $A$, per ogni $x\in A$ si ha $[x]_\sim=\antivecf(\set{f(x)})$. Di conseguenza, $A/{\sim}=\set{\antivecf(\set{y})\mid y\in \im f}$. L'applicazione $y\in\im f\mapsto \antivecf(\set{y})\in A/{\sim}$ è biettiva (teorema fondamentale di omomorfismo per insiemi), quindi si ha $|A/{\sim}|=|\im f|$.

Esercizi proposti:

1. Esercizi 1 (esclusi i punti f e g), 2, 3, 4 da relazioni binarie. Terminologia e notazioni: per ‘ordinamento’ si intende una relazione d'ordine stretto o largo; $\N^\#=\N^*=\N^+=\N\setminus\set 0$.
2. Sia $f\colon A\to B$ un'applicazione. Provare che $f$ è iniettiva se e solo se il nucleo di equivalenza di $f$ è la relazione di uguaglianza in $A$; provare che $f$ è costante se e solo se il nucleo di equivalenza di $f$ è la relazione di universale in $A$.
3. Sia $S=\set{1,2,3,4,5}$ e sia $f\colon X\in\P(S)\mapsto X\cup \set{1,2,3}\in \P(S)$. Quanti elementi ha $\P(S)/{\sim_f}$, dove $\sim_f$ è il nucleo di equivalenza di $f$? Descriverli esplicitamente.
4. Siano $S=\set{1,2,3,4}$ e $A=\set{1,2}$; si consideri l'applicazione $f\colon x\in\P(S)\mapsto x\setminus A\in \P(S)$. $f$ è iniettiva? $f$ è suriettiva? Detto $\rho$ il nucleo di equivalenza di $f$, si descriva, innanzitutto, $[\vuoto]_\rho$ in modo esplicito (elencandone cioè gli elementi) e se ne calcoli la cardinalità. Si descrivano poi, sempre in modo esplicito, tutti gli elementi di $\P(S)/\rho$ e si calcoli $|\P(S)/\rho|$.
5. Esercizio 2, punti (i) e (ii), dal compito del 22 giugno 2015.
6. Esercizio 2 dal compito del 5 marzo 2015.

22/10

Discussione di uno degli esercizi proposti nella lezione precedente, con commenti vari.

Partizioni di un insieme. Definizione e prima caratterizzazione: $F$ è una partizione di un insieme $A$ se e solo se $F\subseteq \P(A)\setminus\set\vuoto$ e $(\forall x\in A)(\exists! b\in F)(x\in b)$. Vari esempi; tra questi le partizioni banali di un insieme $A$, cioè $\P_1(A)$ e, se $A\ne\vuoto$, $\set A$. Proiezione di $A$ in una sua partizione $F$: è l'applicazione (suriettiva) $\pi_F\colon A\to F$ che manda ogni $x\in A$ nell'unico $b\in F$ a cui $x$ appartiene.

Per un arbitrario insieme $A$, biezione canonica da $\Eq(A)$ a $\Part(A)$ (insiemi delle relazioni di equivalenza e delle partizioni di $A$): questa è l'applicazione $\rho\in\Eq(A)\mapsto A/\rho\in\Part(A)$; la sua inversa è l'applicazione che ad ogni partizione $F$ di $A$ associa il nucleo di equivalenza della proiezione di $A$ su $F$ (due elementi di $A$ risultano equivalenti se e solo se appartengono allo stesso blocco della partizione $F$). Diversi esempi. Tra questi: corrispondenza tra partizioni ed equivalenze banali; elenco delle relazioni di equivalenza in $\set{1,2}$ ed in $\set{1,2,3}$.

Operazioni (binarie, interne, ovunque definite) in un insieme. Operazioni associative e operazioni commutative; esempi. Nozione di struttura algebrica. Diversi esempi di strutture associative e non, commutative e non. Semigruppi.

Elementi neutri a sinistra e a destra; elementi neutri e loro unicità (se, in una assegnata struttura, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, ed è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra). Esempi, tra i quali, semigruppi con più di un elemento neutro a destra. Monoidi. Tra gli esempi, il monoide $T(S)$ delle trasformazioni di un insieme $S$.

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

Esercizi proposti:

1. Scrivere cinque partizioni (distinte) di $\Z$.
2. Sia $A=\set{1,2,3,4,5,6,7}$. Quante (e quali) sono le relazioni di equivalenza $\rho$ in $A$ tali che $1\mathrel\rho 3$, $\set{2,5,6}\subseteq [3]_\rho$ e $6\in[7]_\rho$?
3. Esercizio 1 dal compito del 16 luglio 2013.
4. Sia $S$ un insieme e sia $|S|=4$. Calcolare il numero delle partizioni di $S$ ed il numero delle relazioni di equivalenza in $S$.
5. Ricordando quanto visto in lezioni precedenti, provare che, per ogni insieme $S$, il monoide $T(S)$ delle trasformazioni di $S$ è commutativo se e solo se $|S|\le 1$.
6. Sia $*$ l'operazione binaria definita in $X:=\Z\times\Z$ da: $(\forall\; a,b,c,d\in\Z) \big((a,b)*(c,d)=(ac,ad)\big)$. Decidere se $(X,*)$ è un semigruppo, se è commutativo, se ammette elementi neutri a sinistra, se ne ammette a destra.
7. Stesse domande come all'esercizio precedente, per le operazioni $(a,b)\in\Z\times\Z\mapsto a+b+1\in\Z$ e $(X,Y)\in\P(\Z)\times\P(\Z)\mapsto (X\setminus Y)\cup\set 1\in\P(\Z)$ al posto di $*$ (suggerimento per la seconda operazione: considerare terne $X,Y,Z$ di parti di $\Z$ tali che $X\subseteq Y\subseteq Z$).

27/10

Discussione di alcuni degli esercizi proposti nella lezione precedente, con approfondimenti.

Cenno ai teoremi di associatività e di commutatività.

Parti chiuse (o stabili) in una struttura (rispetto ad una operazione); operazioni indotte e sottostrutture. Operazioni indotte da operazioni associative o commutative hanno le stesse proprietà.

Sottosemigruppi e sottomonoidi. Esempi di sottosemigruppi di un monoide che non sono monoidi oppure sono monoidi ma non sottomonoidi.

Le intersezioni tra parti chiuse sono a loro volta chiuse. La parte chiusa generata da una parte in una struttura. Alcuni esempi.

Simmetrici destri e sinistri; simmetrici. Unicità dei simmetrici nei monoidi: se, per un elemento $x$ di un assegnato monoide $S$, $s$ è un simmetrico sinistro e $d$ è un simmetrico destro di $x$, allora $s=d$, quindi $s$ è l'unico simmetrico di $x$, l'unico simmetrico sinistro di $x$ e l'unico simmetrico destro di $x$ in $S$. Ancora un richiamo al monoide $T(S)$ delle trasformazioni di un insieme $S$: i simmetrici destri e sinistri sono in questo caso le sezioni e le retrazioni.Osservazione banale: in ogni struttura con elemento neutro, quest'ultimo è simmetrico di se stesso.

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

Gruppi; gruppi abeliani. Esempi.

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

Esempi, i gruppi (moltiplicativi) degli invertibili dei monoidi $(\Z,\cdot)$ e $(\Q,\cdot)$ (sono, rispettivamente, dati da $\set{1,-1}$ e $\Q\setminus\set 0$), il gruppi simmetrico $\Sym(S)$ su un insieme $S$ (è il gruppo degli invertibili del monoide delle trasformazioni di $S$; i suoi elementi sono le permutazioni di $S$). Alcuni esempi in cui il gruppo degli invertibili è identico (consiste, cioè del solo elemento neutro): accade per i monoidi $(\P(S),\cup,\vuoto)$, $(\P(S),\cap,S)$, per il monoide delle parole su un alfabeto.

Alcuni esempi importanti: il gruppo moltiplicativo $\set{1,-1}$ degli invertibili del monoide $(\Z,\cdot)$; il gruppi simmetrico $\Sym(S)$ su un insieme $S$ (è il gruppo degli invertibili del monoide delle trasformazioni di $S$; i suoi elementi sono le permutazioni di $S$). $\Sym(S)$ è abeliano se e solo se $|S|\le 2$. Altri esempi: non esistono elementi simmetrizzabili, se non quello neutro, nei monoidi $(\P(S),\cup,\vuoto)$, $(\P(S),\cap,S)$ e nel monoide delle parole su un alfabeto.

Se $S$ è un insieme con più di due elementi, $\Sym(S)$ non è abeliano (questo risultato si inverte, vedi esercizi). Trasposizioni.

Esercizi proposti:

1. (Per chi ha seguito il corso di geometria.) Sia $M$ l'insieme delle matrici $2\times 2$ di numeri reali, munito del prodotto $\cdot$ righe per colonne. $(M,\cdot)$ è un semigruppo? È un monoide? È commutativo? Il sottoinsieme di $M$ costituito dalle matrici $2\times 2$ di numeri razionali è una parte chiusa di $M$ rispetto a $\cdot$? Da quali matrici è costituito il gruppo degli invertibili di $M$? Questo gruppo è abeliano?
2. Delle seguenti dieci 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 {-1}$, $\set {0,1,2}$, $\set {1,-1}$, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
3. Si determini, in $(\P(\N),\cap)$, la parte chiusa generata da $\P_4(\N)$.
4. Sia $S=\set{a,b}$ un insieme di cardinalità 2. Descrivere in dettaglio $\Sym(S)$ e provare che è un gruppo abeliano (benché $T(S)$ non sia commutativo). Dedurre che, per ogni insieme $X$, $\Sym (X)$ è abeliano se e solo se $|X|\le 2$.
5. Per un arbitrario insieme $S$, che tipo di struttura è $(\P(S),\ds)$? (È un semigruppo? un monoide? un gruppo? È commutativa?)
6. Per ciascuna delle operazioni considerate negli esercizi 6 e 7 della lezione scorsa, decidere, laddove la richiesta abbia senso, queli elementi della struttura sono simmetrizzabili, descrivendone i simmetrici.

29/10

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Cenni ad alcune proprietà delle permutazioni e dei gruppi simmetrici: cicli (permutazioni cicliche; le trasposizioni sono i cicli di lunghezza 2). Ogni ciclo è prodotto di trasposizioni, infatti ogni ciclo $(a_1\,a_2\,\dots\,a_k)$ si fattorizza come $(a_1\,a_k)\circ(a_1\,a_{k-1})\circ\cdots\circ(a_1\,a_3)\circ(a_1\,a_2)$. Permutazioni tra loro disgiunte; esse commutano tra loro. Ogni permutazione su un insieme finito $S$ è prodotto di cicli a due a due disgiunti (in modo unico, a meno dell'ordine dei fattori) e quindi è prodotto di trasposizioni. Non è stata fornita dimostrazione di questi fatti.

Tavole di Cayley (ovvero di moltiplicazione) per operazioni binarie. Visualizzazione di proprietà tramite tavole di Cayley: commutatività, esistenza di neutri e di simmetrici.

Elementi cancellabili, a sinistra o a destra rispetto ad un'operazione binaria; elementi cancellabili. Traslazioni in una struttura algebrica. Rapporto tra simmetrizzabilità e cancellabilità in un monoide. Esempi. Equivalenza tra cancellabilità e simmetrizzabilità per semigruppi finiti (senza dimostrazione). Questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità. Semigruppi e monoidi (commutativi) cancellativi, Visualizzazione della cancellabilità in tavole di Cayley.

Omomorfismi tra strutture algebriche (per ora, solo nel caso di strutture ad una operazione binaria); monomorfismi ed epimorfismi. Alcuni esempi; tra essi: l'epimorfismo dal monoide delle parole su un alfabeto al monoide additivo dei naturali che ad ogni parola associa la sua lunghezza.

Isomorfismi. Discussione generale ed alcuni esempi. Invarianza delle proprietà algebriche per isomorfismi: questi conservano la commutatività e associatività; inoltre l'immagine mediante un isomorfismo di un elemento che sia (a destra o a sinistra) neutro o simmetrizzabile ha la stessa proprietà (e gli isomorfismi conservano gli eventuali neutri e simmetrici). Tavole di Cayley e isomorfismi; a titolo di esempio abbiamo costruito e confrontato tra loro le tavole di Cayley dei gruppi $\Sym (S)$, per un insieme $S$ di cardinalità 2, $\U(\Z,\cdot)$, $(\P({x}),\ds)$ (per un arbitrario $x$), tra loro isomorfi.

Altri esempi di isomorfismo: la funzione esponenziale è un isomorfismo da $(\R,+)$ a $(\R^+,\cdot)$; se $X$ e $Y$ sono insiemi equipotenti $T(X)\iso T(Y)$ e $\Sym(X)\iso\Sym(Y)$ (dettagli tra gli esercizi), per un arbitrario insieme $S$, l'applicazione $X\mapsto S\setminus X$ è un isomorfismo da $(\P(S),\cap)$ a $(\P(S),\cup)$.

Esercizi proposti:

1. Sia $S$ un insieme tale che $|S|>2$, e si fissi $a\in S$. Definiamo un'operazione binaria $*$ in $S$, ponendo, per ogni $x,y\in S$, $x*y=a$, se $a\notin \set{x,y}$, e $a*x=x=x*a$. L'operazione $*$ è commutativa? Verificare che $a$ è neutro in $(S,*)$ e che, per ogni $x\in S$, ogni elemento di $S\setminus\set a$ è simmetrico di $x$ rispetto a $*$.
   A questo punto, senza fare alcun calcolo rispondere alla domanda: $*$ è associativa? Cosa cambierebbe in questo esercizio se si assumesse $|S|=2$?
2. Scrivere la tavola di Cayley di $\P(\set{0,1},\cup)$.
3. Provare che se $\beta$ è un ciclo di lunghezza 3 in un insieme $S$, allora $\beta\circ\beta\circ\beta=\id_S$. È vero che, in questo caso, l'inversa di $\beta$ è $\beta\circ\beta$?
4. Scrivere la tavola di Cayley del gruppo simmetrico su un insieme di cardinalità 3.
5. Verificare la formula $(a_1\,a_2\,\dots\,a_k)=(a_1\,a_k)\circ(a_1\,a_{k-1})\circ\cdots\circ(a_1\,a_3)\circ(a_1\,a_2)$ di fattorizzazione di un ciclo proposta a lezione.
6. Sia $f\colon X\to Y$ un'applicazione biettiva. Verificare in dettaglio che, come detto a lezione, l'applicazione $\alpha\in T(X)\mapsto f\circ \alpha \circ f^{-1} \in T(Y)$ è un isomorfismo tra in monoidi delle trasformazioni indicate e che $\alpha\in \Sym(X)\mapsto f\circ \alpha \circ f^{-1} \in \Sym(Y)$ è un insomorfismo tra i due gruppi simmetrici indicati.
7. Sia $(G,\cdot)$ un gruppo costituito da due elementi (distinti): $G=\set{1,a}$, dove $1$ è l'elemento neutro. È possibile, con queste sole informazioni, costruire la tavola di Cayley di $G$? Dedurne che i gruppi di cardinalità 2 sono tutti isomorfi tra loro.
8. Tra i monoidi $(\Z,\cdot)$, $(\Z, +)$, $(\N,+)$, $(\P(\N),\cap)$, $(\P(\N),\ds)$ ce ne sono due isomorfi tra loro?
9. Verificare in dettaglio che, se $f\colon S\to T$ è un isomorfismo da una struttura $(S,*)$ dotata di elemento neutro ad una struttura $(T,\diamond)$, se $x$ è un elemento simmetrizabile in $(S,*)$ allora $f(x)$ è un elemento simmetrizabile in $(T,\diamond)$, individuando il simmetrico di $f(x)$.
10. Determinare gli elementi cancellabili nel monoide $(\P(\Z),\cup,\vuoto)$ e quindi quelli di $(\P(\Z),\cap,\Z)$.
11. Provare che l'insieme degli elementi cancellabili a sinistra in un semigruppo è una parte chiusa.

3/11

Discussione di uno degli esercizi proposti nella lezione precedente, con approfondimenti: determinazione (a meno di isomorfismi) di tutti i gruppi di ordine al più 4, attraverso tavole di Cayley.

Sottogruppi e loro caratterizzazione. Qualche esempio. Sottogruppi generati. Gruppi ciclici.

Relazione d'ordine stretto $\rho_{\ne}$ definita da una relazione d'ordine largo $\rho$ in un insieme $A$ (definita da: ($\forall x,y\in A)(x\mathrel {\rho_{\ne}}y\iff (x\mathrel\rho y\, \land\, x\ne y))$) e relazione d'ordine largo $\underline\sigma$ definita da una relazione d'ordine stretto $\sigma$ in $A$ (definita da: ($\forall x,y\in A)(x\mathrel {\underline\sigma}y\iff (x\mathrel \sigma y \,\lor\, x=y))$). Si ottiene in questo modo la biezione canonica $\rho\in\OL(A)\mapsto \rho_{\ne}\in\OS(A)$, di inversa $\sigma\in\OS(A)\mapsto \underline\sigma\in\OL(A)$.

Insiemi ordinati. Applicazioni crescenti ed isomorfismi tra insiemi ordinati. Elementi tra loro confrontabili in insiemi ordinati; ordinamenti totali (relazioni di ordine totale), insiemi totalmente ordinati.

Ordinamenti duali e principio di dualità per insiemi ordinati.

Minimi e massimi in insiemi ordinati. Unicità di minimo e di massimo.

Esercizi proposti:

1. Quali tra questi sono e quali non sono sottogruppi di $(\Z,+)$? $\N^*$, $\N$, $\Z\setminus\N$, $\set{10^7n\mid n\in\Z}$, $\set{-1,0,1}$, $\set 0$.
2. Siano $S$ un insieme non vuoto e $x\in S$. Provare che $G_x:=\set{\alpha\in \Sym(S)\mid \alpha(x)=x}$ è un sottogruppo di $\Sym(S)$. Provare poi che, se $T=S\setminus\set x$, l'applicazione che ad ogni $g\in G_x$ associa la restrizione di $g$ a $T$ ridotta a $T$ (cioè l'applicazione $t\in T\mapsto f(t)\in T$) è (ben definita e) un isomorfismo di gruppi da $G_x$ a $\Sym(T)$.
3. Sia $x$ un elemento del semigruppo $(S,\cdot)$. Si verifichi che $C:=\set{a\in S\mid ax=xa}$ è una parte non vuota di $S$, chiusa rispetto a $\cdot$. Verificare, inoltre, che se $(S,\cdot)$ è un monoide (rispettivamente un gruppo), allora $C$ ne costituisce un sottomonoide (rispettivamente, un sottogruppo).
4. Fornire un esempio di insieme ordinato che abbia minimo ma non massimo, uno dotato di massimo ma non di minimo, uno privo sia di minimo che di massimo.
5. Provare che se $(S,\sigma)$ e $(T,\tau)$ sono due insiemi ordinati isomorfi, $(S,\sigma)$ ha minimo se e solo se $(T,\tau)$ ha minimo e, detto $f\colon S\to T$ un isomorfismo tra essi, se $x=\min(S,\sigma)$ allora $f(x)=\min(T,\tau)$. Questo risultato continua a valere se sostituiamo “massimo” a “minimo”?
6. Siano $X$ e $Y$ sono insiemi equipotenti e sia $f\colon X\to T$ un'applicazione biettiva. Provare che la funzione immagine $\vec f\colon\P(X)\to \P(Y)$ è un isomorfismo di insiemi ordinati (considerando $\P(X)$ e $\P(Y)$ ordinati per inclusione).
7. Osservare che la relazione di uguaglianza $=_S$ in un arbitrario insieme $S$ è una relazione di ordine largo. Posto $S=\set{0,1}$, osservare poi che $\id_S$ è un'applicazione biettiva da $S$ a $S$, che è crescente da $(S,=_S)$ a $(S,\le)$ ma non è un isomorfismo tra questi due insiemi ordinati (qui con $\le$ intendiamo la relazione d'ordine usuale: quella per cui $0\le 1$).

5/11

Discussione di uno degli esercizi proposti nella lezione precedente, con approfondimenti.

Ordinamenti indotti su parti di un insieme ordinato.

Elementi minimali, massimali in insiemi ordinati. Esempi. I minimi (risp. massimi) sono minimali (risp. massimali); in insiemi totalmente ordinati la nozione di elemento minimale (risp. massimale) coincide con quella di minimo (risp. massimo). Se $a$ è minimo (risp. massimo) in un insieme ordinato $(S,\le)$, $a$ è l'unico elemento minimale (risp. massimale) in $(S,\le)$. Esempio di un insieme ordinato privo di minimo e di massimo in cui, però, esiste un elemento che è, allo stesso tempo, l'unico elemento minimale e l'unico elemento massimale.

Insiemi ben ordinati. Buon ordinamento di $(\N,\le)$. Principio di induzione, nelle sue due forme. Dimostrazioni per induzione e dimostrazioni per assurdo via controesempio minimo.

Applicazione: in ogni insieme ordinato finito non vuoto, esistono elementi minimali ed elementi massimali.

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

Discussione (su richiesta) di un problema: se in un insieme ordinato finito esiste un unico elemento minimale, questo è il minimo dell'insieme? (la risposta è sì; si veda uno degli esercizi per una versione semplificata di quanto fatto in aula).

Esercizi proposti:

1. Sia $\Pf(\N)$ l'insieme delle parti finite di $\Z$. In $(\Pf(\N),\subseteq)$, determinare gli eventuali elementi minimali, massimali, minimo, massimo.
2. Sia $f$ l'applicazione $x\in\Pf(\N)\mapsto |x\cap \set{1,2,3,4,5}| \in\N$, e sia $\rho$ la relazione binaria in $\Pf(\N)$ definita da: $(\forall x,y\in\Pf(\N))(x\mathrel\rho y\iff (x=y \lor f(x)\lt f(y)))$. Provare che $\rho$ è una relazione di ordine (largo o stretto?) e determinare in $(\Pf(\N),\rho)$ gli eventuali elementi minimali, massimali, minimo, massimo.

   La relazione $\sigma\in\Rel(\Pf(\N))$ definita da $(\forall x,y\in\Pf(\N))(x\mathrel\sigma y\iff f(x)\le f(y))$ è d'ordine?

3. Dimostrare, usando il principio d'induzione, che per ogni $n\in\N^+$ vale $\sum_{i=1}^{n}(2i-1)=n^2$.
4. Svolgere l'esercizio 2 del 16 febbraio 2015, tralasciando (per ora) le domande su inf, sup, reticoli.
5. Sia $S$ un insieme ordinato e sia $x$ un suo elemento minimale. Allora $x$ è minimo in $S$ se e solo se è $x$ è minimale in $S$ ed è confrontabile con ogni elemento di $S$.
6. Sia $(S,\le)$ un insieme ordinato finito e supponiamo che $x$ sia il suo unico elemento minimale. Provare che $x=\min(S,\le)$ ragionando in modo che segue. Sia $X$ l'insieme degli elementi di $S$ non confrontabili con $x$. Se $X\ne \vuoto$, allora $X$ ha un elemento minimale $y$. Allora $y$ non è minimale in $S$ (perché $y\ne x$), dunque esiste $z\in S$ tale che $z\lt y$.Ora, $z\notin X$, altrimenti sarebbe contraddetta la minimalità di $y$ in $X$). Dunque $z$ è confrontabile con $x$. Dedurne $x\le z$ e, da ciò, $x \lt y$. Ma questo contraddice $y\in X$. Questa contraddizione mostra che $X=\vuoto$. Usando l'esercizio precedente, si ricava $x=\min(S,\le)$.
7. Sia $S$ un insieme ordinato finito con un solo elemento massimale. $S$ ha massimo?

10/11

Discussione di esercizi proposti nella lezione precedente, con approfondimenti. Data un'applicazione $f\colon S\to T$, dove $(T,\le)$ è un insieme ordinato (con $\le$ ordine stretto), la relazione binaria $\sigma$ in $S$ definita da $\forall x,y\in S(x\mathrel\sigma y\iff (f(x)\lt f(y)\lor x=y))$ è di ordine largo. Abbiamo descritto gli elementi minimali, massimali, minimo, massimo in $(S,\sigma)$. Ad esempio, l'insieme degli elementi minimali è l'antimmagine mediante $f$ dell'insieme degli elementi minimali di $(\im f,\le)$. Abbiamo anche osservato che, se $f$ non è iniettiva, la relazione binaria $\tau$ definita in $S$ da $\forall x,y\in S(x\mathrel\tau y\iff f(x)\le f(y))$ non è d'ordine.

Relazione di divisibilità in semigruppi e monoidi commutativi: transitività e (nel caso dei monoidi) riflessività. L'insieme ordinato $(\N,\mid)$: minimo e massimo; minimali e massimali in alcuni suoi sottoinsiemi. Ogni elemento invertibile in un monoide commutativo divide tutti gli elementi del monoide. Ulteriori esercizi ed esempi. Tra questi: la relazione d'ordine usuale in $\N$ vista come relazione di divisibilità in $(\N,+)$; la relazione di inclusione in $(\P(S),\subseteq)$, per un insieme $S$, vista come relazione di divisibilità in $(\P(S),\cup)$.

La relazione $\sim$ ("essere elementi associati") in un monoide commutativo $(M,\cdot)$, definita da: $(\forall a,b\in M)(a\sim b\iff (a|b \land b|a))$. Dunque, $|$ è una relazione d'ordine in $M$ se e solo se $\sim$ è la relazione di uguaglianza. Indicando, per ogni $x\in M$ con $\Div(x)$ e $xM$, nell'ordine, gli insiemi dei divisori e dei multipli di $x$ in $M$, per ogni $a, b \in M$ si ha $a\sim b$ se e solo se $\Div(a)=\Div(b)$, ovvero se e solo se $aM=bM$. Da ciò segue che $\sim$ è una relazione di equivalenza. Per ogni $a\in M$ e $u\in \U(M)$, si ha $a\sim au$; se $a$ è cancellabile vale anche il viceversa e dunque $[a]_\sim=a\U(M)$. Esempio: elementi associati in $(\Z,\cdot)$.

Esercizi proposti:

1. Sia $S=\set{n\in\N\mid 2\le n\le 10}$ ordinato dalle relazione di divisibilità in $\N$. Disegnarne il diagramma di Hasse e indicarne gli elementi minimali, massimali e gli eventuali minimo e massimo in $S$.
2. Date un'applicazione $f\colon S\to T$ ed una relazione di ordine stretto $\rho$ in $T$, provare che la relazione binaria $\tau$ in $S$ definita da $\forall x,y\in S(x\mathrel\sigma y\iff f(x)\mathrel\rho f(y))$ è di ordine stretto. Qual è la relazione di ordine largo ad essa corrispondente? Può essere definita a partire da $f$?
3. Sia $A=\set{2,8,10,20,25,30,90,100,770}$ e sia $\Pr$ l'insieme dei numeri naturali primi. Sia $\pi$ l'applicazione da $A$ a $\P(\Pr)$ che ad ogni $a\in A$ associa l'insieme dei primi che dividono $a$. $\pi$ è iniettiva? $\pi$ è suriettiva? Disegnare il diagramma di Hasse di $(\im\pi,\subseteq)$ e individuare gli elementi minimali, massimali, minimo, massimo in questo insieme. Detta poi $\sigma$ la relazione binaria definita in $A$ ponendo, per ogni $a,b\in A$, $a\mathrel\sigma b$ se e solo se $a=b$ oppure $\pi(a)\subseteq\pi(b)$, verificare che $\sigma$ è una relazione d'ordine, disegnare il diagramma di Hasse di $(A,\sigma)$ e individuare gli elementi minimali, massimali, minimo, massimo in questo insieme ordinato.
4. Costruire un isomorfismo di insiemi ordinati da $(\P(\set{0,1}),\subseteq)$ a $(\Div_{(\N,\cdot)}(6),|)$ (cioè l'insieme dei numeri naturali divisori di 6 ordinato dalla relazione indotta dalla divisibilità in $\N$). Suggerimento: un isomorfismo deve conservare minimi e massimi.

12/11

Discussione di esercizi proposti nelle lezioni precedenti.

Minoranti e maggioranti di un sottoinsieme in un insieme ordinato. Confronto tra queste proprietà e qualle di essere minimo o massimo nel sottoinsieme.

Estremo inferiore ed estremo superiore di una parte di un insieme ordinato. Esempi. Gli estremi inferiori e superiori in $(\P(S),\subseteq)$ per un insieme $S$ ed in $(\N,\mid)$ sono descritti da intersezione ed unione nel primo caso, da MCD e mcm nel secondo.

Definizione di massimo comun divisore e minimo comune multiplo di una parte $X$ di un semigruppo commutativo $(M,\cdot)$. Se $d$ è un MCD (risp. mcm) di $X$ in $(M,\cdot)$, allora l'insieme di tutti i MCD (risp. mcm) di $X$ in $(M,\cdot)$ coincide con la classe degli associati di $d$. Qualche esempio.

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

Le due operazioni (binarie) reticolari (meet/inf/$\land$ e join/sup/$\lor$).

Esercizi proposti:

1. Sia $S=\set{2^{3n+5}\mid n\in\N}$. Determinare, in $(\N,\mid)$, l'insieme dei minoranti e l'insieme dei maggioranti di $S$ e, se esistono, $\inf S$ e $\sup S$.
2. Sia $S$ un insieme tale che $|S|=7$. Si consideri la relazione binaria $\tau$ in $\P(S)$ definita da: $(\forall x,y\in\P(S))\bigl(x\mathrel\tau y\iff x=y\lor |x|\lt |y|\bigr)$. Dimostrare che $\tau$ è una relazione d'ordine largo, descrivere l'insieme dei maggioranti in $(\P(S),\tau)$ di $\P_4(S)$ e stabilire se $(\P(S),\tau)$ è un reticolo.
3. L'insieme $\set{1,2,3,18,20,36}$, ordinato per divisibilità (in $\N$), è un reticolo?
4. Per ogni $n\in\set{4,9,10,12,19,20,30}$ disegnare il diagramma di Hasse dell'insieme $\Div_\N(n)$ dei numeri naturali divisori di $n$, ordinato per divisibilità (in $\N$), e si decida se si tratta o meno di un reticolo. Tra gli insiemi ordinati così ottenuti si cerchino tutte le coppie di insiemi ordinati tra loro isomorfi.

17/11

Discussione di un esercizio proposto nella lezione precedente, con approfondimenti.

Sia $(S,\rho)$ un insieme ordinato. Per ogni $A\subseteq S$, sia $M_A$ l'insieme dei minoranti di $A$ in $(S,\le)$. Se esiste $a=\inf_{(S,\le)} A$, allora $M_A=\set{x\in S\mid x\le a}=M_{\set a}$. Inoltre, se $B\subseteq S$, allora $M_{A\cup B}=M_A\cap M_B$, e se esistono $a=\inf_{(S,\le)} A$ e $b=\inf_{(S,\le)} B$, allora $M_{A\cup B}=M_{\set{a,b}}$, dunque esiste $\inf_{(S,\le)}(A\cup B)$ se e solo se esiste $\inf_{(S,\le)}\set{a,b}$, ed in questo caso $\inf_{(S,\le)}(A\cup B)=\inf_{(S,\le)}\set{a,b}$. Vale l'enunciato duale per gli estremi superiori.

Di conseguenza: in ogni reticolo, ogni parte finita non vuota ha estremo inferiore ed estremo superiore (abbiamo così una seconda dimostrazione del fatto che i reticoli finiti sono limitati).

Proprietà algebriche delle operazioni reticolari (commutatività, associatività, leggi di assorbimento, iteratività). Reticoli come strutture algebriche. Minimo e massimo come elementi neutri. Equivalenza tra le nozioni di reticolo come insieme ordinato e di reticolo come struttura algebrica (in particolare: coincidenza tra le due possibili nozioni di isomorfismo); passaggio da un tipo di struttura all'altro tramite biezioni canoniche. Esempio particolarmente significativo: per un insieme $S$, le strutture $(S,\subseteq)$ e $(S,\cap,\cup)$.

Sottoreticoli; esempi, tra cui gli intervalli chiusi in un reticolo; in particolare: $\Div(n)$ in $(\N,\mid)$, per un $n\in \N$; $\P(T)$ per un sottoinsieme $T$ di un insieme $S$, in $(\P(S),\subseteq)$. Esempio di una parte di un reticolo che non è un sottoreticolo, ma che, munita dell'ordinamento indotto, è un reticolo.

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.

Nozione di complemento in un reticolo limitato; esempi di elementi privi di complemento, con un solo complemento, con più complementi. Reticoli complementati. Le catene (cioè: gli insiemi totalmente ordinati) sono complementati se e solo se hanno al più due elementi. Esempi.

In un reticolo distributivo (limitato) ciascun elemento ha al massimo un complemento. Reticolo trirettangolo e reticolo pentagonale; enunciato del criterio di distributività di Birkhoff.

Reticoli booleani.

Esercizi proposti:

1. In $(\P(\Z),\subseteq)$, individuare il sottoreticolo generato da $\set{A,\N}$ e quello generato da $\set{A, B,\N}$, dove $A=\set{n\in\Z\mid -3\le n\le 5}$ e $B=A\cup\set{7}$. Questi due reticoli sono distributivi? Sono complementati?
2. Esibire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi.
3. Di ciascuno dei seguenti sottoinsiemi di $\N$, ordinati per divisibilità, disegnare il diagramma di Hasse e dire se costituiscono reticoli, e nel caso se sono sottoreticoli di $(\N,\mid)$, se sono reticoli complementati, se sono reticoli distributivi: $S_1=\set{1,3,6,9}$; $S_2=\set{2,4,6,12}$; $S_3=\set{1,2,10,70}$; $S_4=\set{0,1,2,6,7}$; $S_5=\set{1,2,3,5,7,210}$; $S_6=\set{1,2,5,10,50,60,300}$.
4. Svolgere l'esercizio 3 dal compito del 18 marzo 2014.
5. Svolgere l'esercizio 3 dal compito del 14 luglio 2014.
6. Svolgere l'esercizio 6 da relazioni binarie (traducendo "algebra di Boole" in "reticolo booleano").
7. Mostrare con un esempio che un sottoreticolo di un reticolo complementato può non essere complementato.

19/11

Richiami e discussione di esercizi proposti nella lezione precedente.

I duali dei reticoli distributivi (risp. complementati, booleani) sono distributivi (risp. complementati, booleani). Esempi di reticoli booleani. Dualità per reticoli booleani.

Algebre di Boole. Equivalenza tra la nozione di reticolo booleano e quella di algebra di Boole. Sottoalgebre di Boole. Enunciato del teorema di Stone (nel caso finito e, poi, nel caso generale). Conseguenze: i reticoli booleani finiti hanno per cardinalità una potenza di 2; due reticoli booleani finiti equipotenti sono necessariamente isomorfi. Esempio di un algebra di Boole (infinita) che non è isomorfa all'algebra delle parti di alcun insieme. A titolo di notizia: se $n$ è un numero intero positivo, il reticolo dei divisori di $n$ in $\N$ è booleano se e solo se $n$ non è diviso dal quadrato di alcun primo.

Anelli, anelli commutativi, anelli unitari. Esempi: $(\Z,+,\cdot)$, $(2\Z,+,\cdot)$ (non unitario), anelli di matrici (come esempi di anelli non commutativi), l'anello delle parti di un insieme.

Sottoanelli, sottoanelli unitari di un anello unitario. Esempi di sottoanelli di un anello unitario che non sono unitari oppure lo sono ma non come sottoanelli.

Notazioni ed alcune regole di calcolo negli anelli: se $(R,+,\cdot)$ è un anello, per ogni $x\in R$ si indica con $-x$ l'opposto (simmetrico in $(R,+)$) di $x$ in $R$; per ogni coppia di elementi $a$ e $b$ dell'anello $R$ si scrive $a-b$ per $a+(-b)$; si ha $a0_R=0_R=0_Ra$, dove $0_R$ è lo zero di $R$, e $a(-b)=-(ab)=(-a)b$. Conseguenza: se $|R|>1$, lo zero di $R$ non può essere invertibile (cioè simmetrizzabile rispetto alla moltiplicazione in $R$, qualora $R$ sia unitario). Corpi e campi. Esempi. Formula del binomio di Newton. Ne è stata data dimostrazione solo per cenni; chi desidera approfondirla può consultare la parte finale (enunciato numero 5) delle note sui coefficienti binomiali.

Anelli booleani. Proprietà: sono commutativi ed ogni loro elemento coincide con il suo opposto. Costruzione di un reticolo booleano a partire da un anello booleano. La dimostrazione va ancora completata.

Esercizi proposti:

1. Scrivere esplicitamente un isomorfismo tra il reticolo dei divisori di 30 (ordinato per divisibilità) e quello delle parti di un insieme di cardinalità 3.
2. Di due reticoli booleani $L$ e $M$ sappiamo che hanno entrambi cardinalità compresa tra 400 e 900. Che conclusioni possiamo trarre? Possiamo, in particolare, stabilire se $L$ e $M$ sono isomorfi?
3. Provare che, in ogni algebra di Boole, l'operazione unaria di complemento è involutoria (cioè: il complemento del complemento di ogni elemento $x$ è $x$ stesso).
4. Esercizio 5 da Polinomi e strutture algebriche.

24/11

Discussione di esercizi proposti nella lezione precedente, con approfondimenti.

Completamento delle verifiche a proposito delle costruzione di un reticolo booleano a partire da un anello booleano. Costruzione, inversa, di un reticolo booleano a partire da un anello booleano (senza verifiche).

Leggi di De Morgan nelle algebre di Boole.

Equivalenza tra le nozioni di anello booleano e di reticolo booleano. Le sottoalgebre di Boole di un'algebra di Boole sono precisamente i sottoanelli unitari dell'anello booleano costruito su di essa Teorema di Stone per anelli booleani: ogni anello booleano finito è isomorfo a $(\P(S),\ds,\cap)$ per un opportuno insieme finito $S$; ogni anello booleano è isomorfo ad un sottoanello unitario di $(\P(S),\ds,\cap)$ per un opportuno insieme $S$.

Anelli booleani, funzioni caratteristiche e "stringhe di 0 e 1".

Partizioni ed equivalenze compatibili con un'operazione binaria. Esempio: l'equivalenza "avere lo stesso segno" in $\Z$, definita dichiarando equivalenti due interi se e solo se essi sono o entrambi positivi, o entrambi negativi o entrambi zero, è compatibile con l'usuale moltiplicazione ma non con l'usuale addizione in $\Z$. Altro esempio: l'equivalenza "avere la stessa lunghezza" è compatibile con l'operazione binaria (concatenazione) nel monoide delle parole su un alfabeto.

Esercizi proposti:

1. Sia $S=\set{1,2,3,4,5,6}$ e, per ogni $X\subseteq S$, sia $s(X)$ la stringa di 0 e 1, di lunghezza 6, che abbia in posizione $i$-esima l'immagine di $i$ nella funzione caratteristica di $X$ in $S$ (cioè: 1 se $i\in X$, 0 se $i\notin X$). Ai fini di questo esercizio chiameremo $s(X)$ la $s$-stringa corrispondente a $X$. Per ciascuno degli insiemi $\vuoto$, $\set{1,3,5}$ e $\set{1,2,4,6}$ scrivere esplicitamente la corrispondente $s$-stringa. Scelti, in tutti i modi possibili, tralasciando l'ordine, (ce ne sono sei, perché?) due insiemi $A$ e $B$ tra i tre proposti, Si calcolino $A\cap B$ e $A\ds B$ e si confrontino i risultati con quelli ottenuti applicando le operazioni AND e XOR tra le corrispondenti stringhe $s(A)$ e $s(B)$.
2. Verificare la correttezza della costruzione di un anello booleano a partire da un reticolo booleano descritta a lezione (serve un pò di pazienza).
3. La relazione di equipotenza in $\P(\set{1,2,3})$ è compatibile con qualcuna delle operazioni $\cap$, $\cup$, $\ds$?
4. Sia $(M,*,t)$ un monoide commutativo. La relazione "essere elementi associati" in $M$ (si veda la lezione del 10/11) è compatibile con $*$?
5. Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è compatibile con $*$.
6. Sia $W$ il monoide delle parole su un alfabeto. Ricordando l'omomorfismo da $W$ a $(\N,+,0)$ che ad ogni parola associa la sua lunghezza, usare l'esercizio precedente per riottenere quanto osservato a lezione: che l'equivalenza "avere la stessa lunghezza" è compatibile la concatenazione in $W$.
7. La relazione di equivalenza "avere la stessa parità" è compatibile l'operazione di elevazione a potenza ($(a,b)\mapsto a^b$) in $\N^\#$?. E in $\N$?.

26/11

Discussione di esercizi proposti nelle lezioni precedenti.

Operazione quoziente (cioè quella indotta sul quoziente determinato da un'equivalenza compatibile con un'operazione binaria). Questa è ben definita se e solo se l'equivalenza è compatibile con l'operazione.

Congruenze in una struttura algebrica. Struttura quoziente. Proprietà che si conservano passando alla struttura quoziente (come associatività, commutatività, esistenza di neutri e simmetrici, distributività — verifiche lasciate per esercizio); i quozienti di semigruppi, monoidi, gruppi (abeliani e non), anelli, anelli unitari sono strutture dello stesso tipo.

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

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

Le congruenze modulo un intero in $\Z$ (cioè le equivalenze $\equiv_m$ al variare di $m\in\Z$). Osservazioni: $\equiv_0$ è la relazione uguaglianza, $\equiv_1$ è la relazione universale, $\equiv_2$ è la relazione "avere la stessa parità"; per ogni $m\in \Z$, $\equiv_{-m}$ coincide con $\equiv_m$. Verifica diretta del fatto che tutte queste sono congruenze nell'anello $(\Z,+,\cdot)$. Solo a titolo di notizia, è stato menzionato il fatto che queste sono le sole congruenze dell'anello $(\Z,+,\cdot)$, anzi le sole relazioni di equivalenza in $\Z$ compatibili con l'addizione. I quozienti $\Z_m:=\Z/{\equiv_m}$. Descrizione esplicita delle classi resto: per ogni $m,a\in \Z$, la classe di resto $[a]_m:=[a]_{\equiv_m}$ di $a$ modulo $m$ è $a+m\Z:=\set{a+mk\mid k\in \Z}$. L'operazione parziale mod (per ogni $a,m\in\Z$, se $m\ne0$, $a\modbin m$ è, per definizione, il minimo numero naturale in $[a]_m$; questo numero è minore di $|m|$). Descrizione esplicita dei quozienti di $\Z$: per ogni $m\in\N^+$, $\Z_m=\set{[0]_m, [1]_m, [2]_m, \dots, [m-1]_m}$. Gli elementi di $\Z_m$ appena elencati sono a due a due distinti (vale a dire: se $i$ e $j$ sono numeri naturali minori di $m$ e $i\equiv_m j$, allora $i=j$), quindi $|\Z_m|=m$.

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

Esercizi proposti:

1. Calcolare $25\modbin 11$ (ovvero: $\rest(25,11)$), $25\modbin (-11)$, $(-25)\modbin 11$, $(-25)\modbin (-11)$.
2. Si elenchino gli elementi di $S\cap [17]_4$, dove $S=\set{n\in\Z\mid -10 \le n \le 10}$.
3. Fissato $m\in\N$, quali sono le classi resto in $\Z_m$ che sono sottogruppi di $(\Z,+)$? Suggerimento: si parta da $[0]_m$.
4. Calcolare $876984737830287! \modbin 123456789$.
5. Calcolare $(87698473)^2 \modbin 2$.

1/12

Discussione di esercizi proposti nella lezione precedente.

Cancellabilità e divisori dello zero negli anelli; anelli integri e domini di integrità (legge di annullamento del prodotto) (si veda la seconda parte delle note sulla cancellabilità). I corpi sono anelli integri, i campi sono domini di integrità. Alcuni esempi. Se $S\ne\vuoto$, l'unità $S$ è l'unico elemento cancellabile in $(\P(S),\ds,\cap)$, che quindi non è un domino di itegrità. Anche l'anello $\Z_6$ non è un dominio di integrità. Invece $\Z$ è un dominio di integrità unitario che non è un campo.

Divisori banali; elementi irriducibili ed elementi primi in un monode commutativo cancellativo. Divisori propri. Sia la proprietà di essere primo che quella di essere irriducibile si conserva nel passaggio da un elemento ad un suo associato.

Fattorizzazioni "essenzialmente uguali" (cioè uguali a meno dell'ordine dei fattori e della sostituzione di essi con associati) in monoidi cancellativi. Monoidi fattoriali ed anelli fattoriali. Alcuni esempi immediati e poco interessanti (i gruppi abeliani, $(\N,+)$). Teorema fondamentale dell'aritmetica (fattorialità dei monoidi $(\N^+,\cdot)$ e $(\Z\setminus\set0,\cdot)$), cioè dell'anello $(\Z,+,\cdot)$.

Descrizione dell'insieme dei divisori di un elemento in un monoide fattoriale $M$ a partire da una sua fattorizzazione in irriducibili (o, meglio, da una fattorizzazione primaria): se $a\in M$ e $a=up_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una sua decomposizione primaria (dunque, $u$ è invertibile e i $p_i$ sono 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 della forma $v p_1^{b_1} p_2^{b_2}\cdots p_n^{b_n}$, dove $v$ è un invertibile e ciascuno degli esponenti $b_i$ è un numero intero positivo minore o uguale ad $a_i$. Esistenza ed espressione di un MCD $d$ e di un mcm $m$ tra due elementi $a$ e $b$ di un monoide fattoriale. Osservazione: $ab$ e $md$ risultano associati.

Algoritmo euclideo delle divisioni successive per la determinazione di un massimo comun divisore tra due interi.

Esercizi proposti:

1. DA FARE; IMPORTANTE PER LA PROSSIMA LEZIONE: utilizzando l'algoritmo euclideo, calcolare il MCD positivo tra i numeri 498 e 114.
2. In un anello unitario, tutti gli elementi idempotenti diversi dall'unità sono divisori dello zero.
3. Descrivere tutti i divisori, in $\Z$, di $2^{12} 3^5 17^8$. Quanti ne sono?
4. Stesso esercizio per $5!$ per $-3^4 25^2$.
5. Dalla descrizione dei massimi comuni divisori e dei minimi comuni multipli tra elementi $a$ e $b$ di un monoide fattoriale dedurre che se $d$ è un MCD e $m$ un mcm tra $a$ e $b$ allora $dm$ è associato ad $ab$.

3/12

Discussione di esercizi proposti nella lezione precedente, con approfondimenti.

Qualche idea per la velocizzazione dell'algoritmo euclideo. Se $a,b\in \Z$ e $b\ne 0$, esistono interi $q$ ed $r$ tali che $a=bq+r$ e $|r|\le |b/2|$.

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, a due indeterminate) e ulteriori formulazioni del Teorema di Bézout: scelti comunque due interi $a$ e $b$, e detto $d$ un loro MCD,

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

Lemma di Euclide: siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$.

Dimostrazione del Teorema fondamentale dell'aritmetica.

Equazioni congruenziali (di primo grado, ad una indeterminata). Equivalenza tra il problema di risolvere l'equazione congruenziale $ax\equiv_m b$ e quello di risolvere l'equazione diofantea $ax+my=b$ (dove $a, b$ ed $m$ sono interi). Criterio di esistenza di soluzioni per le equazioni congruenziali. Di conseguenza: determinazione degli elementi invertibili nei quozienti di $\Z$. Gli elementi non invertibili nei quozienti propri di $\Z$ sono tutti divisori dello zero. Se $m$ è un intero maggiore di 1, $\Z_m$ è un campo se e solo se $m$ è primo; non è integro se $m$ è composto.

Algoritmo per la risoluzione delle equazioni congruenziali. Equazioni congruenziali ridotte. Qualche cenno a metodi per la semplificazione.

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

Esercizi proposti:

1. Di ciascuno degli elementi dell'anello $\Z_{12}$ si dica se è invertibile, cancellabile, un divisore dello zero, idempotente. Degli invertibili si trovi l'inverso.
2. Esercizi da 5 a 9 e 11 da Tautologie, insiemi, aritmetica. (NB: l'espressione $ax\equiv b\pmod m$ è equivalente a $ax\equiv_m b$.)
3. Trovare, se possibile, soluzioni delle equazioni congruenziali $302x\equiv_{144} 6$, $144x\equiv_{302} 6$ e $151x\equiv_{72} 3$.
4. Trovare, se possibile, soluzioni dell'equazione congruenziale $200x+10\equiv_{72} 49x+13$.
5. Trovare, se possibile, cento soluzioni di ciascuna delle equazioni congruenziale $102 x \equiv_{11}17$; $10! x \equiv_{7} 33$; $260 x \equiv_{34}80$
6. Aldo deve a Bice 147 talleri boemi. Sapendo che il tallero boemo viene emesso solo in monete da 357 e da 700 talleri (e non esiste in forma di banconota, e nessuna banca o servizio finanziario permette operazioni in talleri boemi), potrà Aldo pagare a Bice la somma che le deve? Se sì, in che modo?

10/12

Discussione di esercizi proposti nella lezione precedente, con approfondimenti.

Metodi di semplificazione e di soluzione di equazioni congruenziali di primo grado ad una incognita (sostituzioni di coefficienti con numeri a loro congrui; divisione dei due coefficienti per un invertibile; divisione di coefficienti e modulo per un divisore comune); diversi esempi. Equazioni congruenziali ridotte. Determinazione dell'insieme di tutte le soluzioni intere di un'equazione congruenziale (del tipo considerato). Dati gli interi $a$, $m$ e $k$, con $mk\ne 0$, confronto tra le classi resto $[a]_m$ e $[a]_{km}$. Descrizione dell'insieme di tutte le soluzioni di un'equazione diofantea di primo grado in due incognite.

Alcune considerazioni sui numeri primi. Per verificare che un intero $n\ge 1$ sia primo basta verificare che non sia divisibile per alcun primo minore o uguale alla sua radice quadrata.

(Solo) definizione della funzione di Eulero. Abbiamo appena accennato, e solo a titolo di notizia, alle applicazioni della funzione di Eulero in crittografia. Chi è interessato può consultare in questo sito delle note sulla funzione di Eulero o anche un articolo elementare sulla crittografia.

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

Sottosemigruppi, sottomonoidi e sottogruppi generati da singleton; sono tutte strutture commutative. Gruppi ciclici. Esempio: $(\Z,+)$ e, per ogni $n\in\N^+$, $(\Z_n,+)$ sono gruppi ciclici. A titolo di notizia: ogni gruppo ciclico è isomorfo ad uno di questi.

Elementi periodici ed aperiodici, e periodo di un elemento $x$ in un gruppo $G$. Se $x$ ha periodo finito $n$, allora, per ogni $a$, $b\in \Z$, si ha $x^a=x^b\iff a\equiv_n b$ (vale a dire: $\equiv_n$ è il nucleo di equivalenza dell'applicazione $n\in\Z\mapsto x^n\in G$). Dunque: $x^a=x^{a\,\modbin\,n}$, e $x^a=1_G$ se e solo se $n$ divide $a$; inoltre, l'inverso di $x$ è $x^{n-1}$. In un gruppo finito $G$ ogni elemento è periodico; si è poi menzionato, senza dimostrarlo, il fatto che questo periodo divide $|G|$.

Diversi esempi. Caratteristica di un anello unitario. In ogni anello unitario $R$ si ha $(n 1_R)a=nx$ per ogni $n\in\Z$ e $a\in R$; quindi $na=0_R$ se $n$ è la caratteristica di $R$. Esempi: caratteristiche di $\Z$ e dei suoi quozienti, e degli anelli booleani.

Calcoli in aritmetica modulare (calcolo di somme, prodotti, potenze). Diversi esempi. Rappresentazione degli interi positivi in base 10 e criteri di divisibilità per 2, 5, 4, 25, etc., 3, 9, 11, in $\N$; ‘prova del nove’. Osservazione: se due interi sono congrui modulo un intero $m$, essi sono congrui modulo ogni divisore di $m$.

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

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

Proprietà universale per gli anelli dei polinomi. Come conseguenza: unicità a meno di isomorfismi dell'anello dei polinomi (l'esistenza è non stata dimostrata). La proprietà universale è stata anche utilizzata per definire l'omomorfismo di sostituzione.

Per la prossima lezione: (1) si raccomanda la puntualità; dobbiamo sfruttare tutto il tempo a disposizione; (2) potrebbe essere utile avere con sé le note sui polinomi.

Esercizi proposti:

1. Esercizi da 10 e 12 da Tautologie, insiemi, aritmetica.
2. Che giorno (delle settimana) è $3^{500}$ giorni dopo una domenica (se nel frattempo non viene riformato il calendario)?
3. Trovare tutte le soluzioni dell'equazione congruenziale $224 x\equiv_{690}18$,
4. Calcolare $\rest(7^{92746221747},19)$.
5. Indicando, per ogni $n\in\Z$, con $\bar n$ la classe di resto $[n]_{13}$, decidere per quali valori di $k\in\Z_{13}$ il polinomio $(5k+\bar 3)x^5+k^2 x^2+\bar 1\in \Z_{13}[x]$ ha grado pari.

15/12

Rinnovo l'invito alla compilazione dei questionari sulla valutazione della didattica

Il materiale coperto in questa lezione è tutto nelle note sui polinomi.

Discussione di esercizi proposti nella lezione precedente, con approfondimenti. Per ogni intero $n\ne 0$, l'epimorfismo da $\Z[x]$ a $\Z_n[x]$, indotto dall'epimorfismo canonico $\Z\epi \Z_n$, che ad ogni polinomio $f$ associa $f$ stesso "riguardato modulo $n$". Polinomi monici.

D'ora in avanti, nel resoconto di questa lezione $A$ indica sempre un anello commutativo unitario.

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)$. Esempi nei quali questa regola fallisce.

Teorema: sono equivalenti: (1) $A[x]$ è un dominio di integrità; (2) $A$ è un dominio di integrità; (3) vale in $A[x]$ la regola di addizione dei gradi (per ogni coppia di polinomi). Inoltre, se queste si verificano si ha $\U(A[x])=\U(A)$. Esempi che mostrano come quest'ultima proprietà (né la regola di addizione dei gradi) valga necessariamente se $A$ non è integro. Qualunque sia $A$, $x\notin\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.

Divisione lunga tra polinomi. Dimostrazione (costruttiva) dell'esistenza e dell'unicità di quoziente e resto. È sicuramente possibile effettuare la divisione se (1): $g$ è monico; oppure (2): $A$ è un campo e $g\ne 0$.

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

Applicazione polinomiale definita da un polinomio. Radici di un polinomio. Osservazione: polinomi distinti possono definire la stessa applicazione polinomiale (anzi, poiché $A[x]$ è infinito, se $A$ è finito ciò accade sempre per opportuni polinomi in $A[x]$).

Teorema del resto: con le notazioni di sopra, se $g=x-c$ per un $c\in A$, allora il resto nella divisione di $f$ per $g$ è $f(c)$. Come conseguenza, Teorema di Ruffini (per anelli commutativi unitari arbitrari).

Teorema di Ruffini generalizzato e sue e conseguenze. Se $A$ è dominio di integrità unitario si ha: (1) se $0_A\ne f\in A[x]$, allora $f$ ha al più $\nu(f)$ radici in $A$; (2) principio di identità dei polinomi: se, inoltre, $A$ è infinito due polinomi in $A[x]$ coincidono se e solo se definiscono la stessa applicazione polinomiale. Controesempi mostrano che questi tutti risultati non valgono per anelli commutativi unitari arbitrari.

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.

Cenni a metodi di fattorizzazione. Caratterizzazione dei polinomi irriducibili su un campo $K[x]$; esistenza di radici ed irriducibilità. Descrizione dei polinomi irriducibili sul campo reale e sul campo complesso; i polinomi di grado dispari in $\R[x]$ hanno sempre radici in $\R$. Polinomi in $\Q[x]$. Ciascuno di essi ha un associato in $\Z[x]$. Radici razionali di un polinomio $f\in\Z[x]$; se $f$ è monico tali radici sono intere. Criterio di irriducibilità di Eisenstein. Per ogni $n\in\N^+$ ed ogni primo positivo $p$, $x^n-p$ è irriducibile in $\Q[x]$.

Diversi esempi sono nelle note sui polinomi, che possono essere di aiuto anche per gli esercizi proposti.

Esercizi proposti:

1. Per ogni $n\in\N^*$, sia $f_n=(100+4n)x^4+(n+8)x^3+nx^2+1$ e sia $\bar {f_n}\in \Z_{11}[x]$ il polinomio $f_n$ riguardato come polinomio a coefficienti in $\Z_{11}[x]$. Sia $L=\{n\in\N^* \mid \nu \bar {f_n}=2\}$. Decidere se $L=\vuoto$ o $L\ne\vuoto$; nel secondo caso, posto $m=\min L$, scrivere l'associato monico di $\bar {f_m}$ in $\Z_{11}[x]$. Ripetere l'esercizio dopo aver ridefinito $f_n$ come $(100+4n)x^4+(n-8)x^3+nx^2+1$.
2. 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]$).
3. Svogere, almeno in parte, gli esercizi nr. 1 e nr. 2 da Polinomi e strutture algebriche.
4. Si costruisca, se possibile, un polinomio di grado 500 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-20\le n \lt 100$.
5. Sia $A$ un anello booleano. Costruire in $A[x]$ infiniti polinomi distinti che determinano la stessa applicazione polinomiale.
6. Siano $A$ un anello commutativo unitario, $f, g, d\in A[x]$ e $c\in A$. Provare che se $d$ è un MCD tra $f$ e $g$ e $f(c)=g(c)=0$, allora $d(c)=0$.

17/12

Ulteriore (e ultimo) invito alla compilazione dei questionari sulla valutazione della didattica

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

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

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

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

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. Come conseguenza: gli alberi finiti sono grafi planari (e di conseguenza sono planari le foreste finite). Inoltre, 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.

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

Caratterizzazione degli alberi: un grafo finito $G=(V,L)$ è un albero se e solo se: (1) è connesso e $|V|=|L|+1$, ovvero se e solo se: (2) è una foresta e $|V|=|L|+1$. Con le stesse notazioni, $G$ è una foresta se e solo se $G$ ha esattamente $|V|-|L|$ componenti connesse. In generale, il numero delle componenti connesse in un grafo finito è sempre maggiore o uguale a $|V|-|L|$; in particolare, se il grafo è connesso, allora $|L|\ge|V|-1$.

Esercizi proposti:

1. Esercizi da Grafi, ad esclusione del nr. 4.
2. Disegnare, a meno di isomorfismi, tutti i grafi (semplici) connessi su cinque vertici. Indentificare tra questi gli alberi.
3. Si considerino i grafi $G=(V,L)$ che verificano la proprietà $p$: “$|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 $p$, quali sono i gradi dei suoi vertici?
   2. Disegnare, se possibile, un grafo che verifichi $p$.
   3. Disegnare, se possibile, due grafi tra loro non isomorfi che verifichino $p$.
   4. Disegnare, se possibile, un grafo non connesso che verifichi $p$.
   5. Disegnare, a meno di isomorfismi, tutti i grafi che verificano $p$.