24/9

Introduzione al corso: presentazione, informazioni generali, modalità di svolgimento del corso, 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). 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, associatività della congiunzione e della disgiunzione, distributività tra congiunzione e disgiunzione.

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

Esercizi proposti:

1. Verificare l'associatività del connettivo di disgiunzione (inclusiva).
2. Svolgere gli esercizi A.1, A.2, B.1 e B.5 da Logica rudimentale.
3. Se indichiamo con $p$ la formula “$3x\lt 4$” e con $q$ la formula “$y+1=z$”, quale connettivo proposizionale va inserito al posto di “$*$” in modo che la formula $p\mathop * q$ traduca (dal punto di vista logico) la frase “$3x\lt 4$ ma $y+1=z$”?
4. La forma proposizionale $\bigl(q\iff r\bigr)\iff \bigl((p\land q)\iff(p\land r)\bigr)$ è una tautologia?

26/9

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

Negazione di congiunzione e disgiunzione (leggi di De Morgan; il connettivo NOR di disgiunzione negata) e del bicondizionale (tramite XOR e in alte forme). Associatività del bicondizonale e di XOR.

Connettivo di implicazione (o condizionale); discussione approfondita sul suo uso. Alcune tautologie sull'implicazione (doppia implicazione, transitività, implicazione come disgiunzione, negazione dell'implicazione); per il connettivo di implicazione non vale la commutatività. Si veda anche l'esercizio nr. 1.

Interdipendenza tra i connettivi binari. Per esprimerli tutti bastano $\lnot$ e $\land$ (ovvero $\lnot$ e $\lor$) o, addirittura, il solo NAND (o il solo NOR).

Altre tautologie su XOR: esplicitazione; distributività di $\land$ rispetto a XOR.

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.

Esercizi proposti:

1. Verificare l'importante tautologia $(p\implica q) \iff((\lnot q)\implica(\lnot p))$ (legge di contrapposizione) e leggere, a questo proposito l'osservazione E.4 da Logica rudimentale.
2. Svolgere gli esercizi B.2, B.3 e B.4 da Logica rudimentale.
3. Svolgere gli esercizi C.2, tutti i D, E.1 ed E3 da Logica rudimentale.
4. Negare la frase: “se ti fa piacere ti accompagno”.
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))$.

1/10

Discussione di alcuni degli esercizi proposti nella lezione precedente. Legge di contrapposizione (e dimostrazioni per contrapposizione).

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

Discussione di alcuni (frequenti) errori di ragionamento.

Nozione di insieme. Il simbolo '$\in$' di appartenenza. 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 $y$ si ha $\vuoto\subseteq y$, (in particolare, $\vuoto\subseteq\vuoto$), ma $\vuoto\notin\vuoto$.

Esercizi proposti:

1. Svolgere gli esercizi H e I3 da Logica rudimentale.
2. Vero o falso? $\forall x(x\subseteq x)$.

3/10

Discussione di alcuni degli esercizi proposti nella lezione precedente.

Cenno all'assioma di fondazione (non esplicitato) ed alla sua conseguenza: $\forall x(x\notin x)$. Il singleton di un insieme; $\forall x(x\ne\set{x})$. Ancora sull'inclusione tra insiemi. L'insieme $\P(x)$ delle parti di un insieme $x$. Qualunque sia $x$, si ha $\vuoto,x\in\P(x)$. Qualche esempio.

Predicati unari, loro estensioni e formule insiemistiche ricavate da tautologie (come nella sezione finale di Logica rudimentale, ma si veda ancheTautologie 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; diversi esempi. Utilizzando diagrammi di Euler-Venn sufficientemente generici è possibile dimostrare formule insiemistiche. Uso dei diagrammi di Euler-Venn per costruire controesempi.

Esercizi proposti:

1. Elencare gli elementi di $\P(\set{\vuoto, \set{\vuoto}, a})$, assumendo $a\notin\set{\vuoto, \set{\vuoto}}$.
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. Svolgere gli esercizi J da Logica rudimentale.
4. Utilizzando diagrammi di Venn, si stabilsca se, per ogni $a,b,c$ si ha $(a\cap b)\setminus c=(a\setminus c)\cap(b\setminus c)$.
5. È vero che: $\forall a,b (a\subseteq b \iff \P(a)\subseteq P(b))$?

8/10

Discussione di alcuni degli esercizi proposti nelle lezioni precedenti.

Descrizione di insiemi con scritture del tipo $\set{t(x_1,x_2,\ldots,x_n)\mid \varphi(x_1,x_2,\ldots,x_n)}$ (abbreviazione di $\set{a\mid \exists x_1,x_2,\ldots,x_n (a=t(x_1,x_2,\ldots,x_n)\land \varphi(x_1,x_2,\ldots,x_n))}$.

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, etc.). Relazioni binarie in un insieme. Notazioni: $\Corr(A,B)$ e $\Rel(A)$, per insiemi $A$ e $B$.

Prodotto relazionale tra corrispondenze.

Esercizi proposti:

1. Si verifichi la formula di inclusione-esclusione per l'unione di tre ternaria insiemi finiti utilizzando diagrammi di tipo Venn.
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{a, b}$, $T=\set{1,2,3}$ 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$.

10/10

Discussione, approfondita, di alcuni degli esercizi proposti nelle lezioni precedenti.

Associatività del prodotto relazionale. Cosiddetta “corrispondenza inversa” di una corrispondenza.

Applicazioni tra insiemi. Dominio e codominio. Notazioni: Il problema della "buona" (corretta) definizione di un'applicazione; vari esempi. Nel corso della presentazione di alcuni esempi è stato definito, per ogni insieme $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 tra applicazioni (prodotto operativo). Notazioni equivalenti: $\Map(A,B)$, $B^A$, ${}^AB$, per insiemi $A$ e $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$. La diagonale $\set{(x,x)\mid x\in S}$ di un insieme $S$. Esempio: due applicazioni (costanti) $\alpha$ e $\beta$ da un insieme $S$ a se stesso tali che $\alpha\beta\ne\beta\alpha$.

Immagine di un'applicazione. Applicazioni suriettive. Esempi. Ogni applicazione suriettiva ha una sezione (una sezione dell'applicazione $\alpha\colon A\to B$ è un'applicazione $\beta\colon B\to A$ tale che $\alpha\circ\beta=\id_B$).

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. Svolgere gli esercizi 3 e 4 da Tautologie, insiemi, aritmetica, escluse le domande su iniettività e biettività.
5. Di ciascuna delle seguenti applicazioni si stabilisca se è suriettiva e, nel caso lo sia, se ne esibisca una sezione:
   • $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$;

15/10

Discussione, approfondita, di esercizi proposti nella lezione precedente relativi a suriettività e costruzione di sezioni.

Restrizioni, prolungamenti, ridotte 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$. Ogni applicazione ha una ridotta ed infiniti prolungamenti suriettivi.

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 si applicazione biettiva che si possa scrivere come applicazione composta $g\circ f$, dove $g$ non è iniettiva ed $f$ non è suriettiva.

Teorema: un'applicazione è suriettiva se e solo se ha una sezione.

Esercizi proposti:

1. Completare gli esercizi 3 e 4 da Tautologie, insiemi, aritmetica (ma è escluso il punto f, di 3), rispondendo alle domande su iniettività e biettività.
2. 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.
3. Tra le applicazioni da $\N$ a $\Z$, trovarne: una iniettiva non suriettiva, una suriettiva non iniettiva, una biettiva, una né iniettiva né suriettiva.

17/10

Discussione di alcuni esercizi proposti nella lezione precedente

Retrazioni di un'applicazione; $f$ è una retrazione di $g$ se e solo se $g$ è una sezione di $f$; dunque tutte le retrazioni sono suriettive.

Teorema: un'applicazione è iniettiva se e solo se ha una retrazione oppure ha dominio vuoto. Alcuni esempi.

Applicazione inversa di un'applicazione. Unicità: 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. Costruzione esplicita dell'inversa di un'applicazione biettiva, con esempi. Rilevanza della nozione di invertibilità.

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

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.

Esercizi proposti:

1. 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$.
2. Scrivere l'inversa dell'applicazione biettiva che appare al secondo esercizio della lezione scorsa.
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. 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$.
5. Elencare tutte le applicazioni iniettive di cui all'esercizio precedente.
6. 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.

22/10

Discussione di esercizi proposti nella lezione precedente, con approfondimenti.

Il fattoriale $n!$ di un numero naturale $n$. 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|)$.

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)=A$, $\,\antivecf (\im f)=A$. Diversi esempi. 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. Diversi esempi.

Funzione caratteristica $\chi_{X,S}$ di una parte $X$ di un insieme $S$; biezione $X\in\P(S)\mapsto \chi_{X,S}\in\set{0,1}^S$.

Proprietà di relazioni binarie: relazioni riflessive, antiriflessive, simmetriche. 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.

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. Provare che, se $f$ è l'applicazione identica in un insieme $A$, $\vec f$ e $\antivecf$ coincidono con l'applicazione identica di $\P(A)$.
3. Provare che, se $f$ e $g$ sono applicazioni componibili, $(f\circ g)\vecvuoto=\vec f\circ \vec g$  e $(f\circ g)\antivecvuoto=\antivecg\circ \antivecf$. Se $f$ è biettiva, allora anche $\vec f$ è biettiva e la sue inversa è $\antivecf$.
4. Sia $f\colon A\to B$ un'applicazione. Provare che,
   • Se $U\subseteq V\subseteq A$ allora $\vec f(U)\subseteq \vec f(V)$; se $U\subseteq V\subseteq B$ allora $\antivecf(U)\subseteq \antivecf(V)$.
   • 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))$; $f$ è suriettiva se e solo se per ogni $Y\subseteq B$ si ha $\vec f(\antivecf (Y))=Y$.
   • 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)$.
   • $\vec f$ è iniettiva se e solo se $f$ è iniettiva; $\vec f$ è suriettiva se e solo se $f$ è suriettiva (suggerimento: si possono usare gli esercizi precedenti e le caratterizzazioni di iniettività e suriettività in termini di esistenza di retrazioni e sezioni).

24/10

Discussione di alcuni esercizi proposti nella lezione precedente.

Altre proprietà di relazioni binarie: relazioni antisimmetriche e relazioni transitive, descritte anche in termini di proprietà del grafico.. Esempi; negazione di queste proprietà. 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.

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

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

• $a\in [a]_\sim$, quindi $[a]_\sim\ne \vuoto$; $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$;
• $[a]_\sim\cap [b]_\sim\ne \vuoto \Implica [a]_\sim=[b]_\sim$.

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 $\pi_F\colon A\to F$ che manda ogni $x\in A$ nell'unico $b\in F$ a cui $x$ appartiene. Quest'applicazione è suriettiva.

Esercizi proposti:

1. Esercizi da 1 a 4 in relazioni binarie, ad esclusione di 1.f (per ‘ordinamento’ si intende una relazione d'ordine stretto o largo)
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 (cioè $(A,A,A\times A)$) in $A$.
3. 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|$.
4. Scrivere tutte le partizioni degli insiemi $\set{1,2}$ e $\set{1,2,3}$.
5. Scrivere cinque partizioni (distinte) di $\Z$.

29/10

Discussione di alcuni esercizi proposti nella lezione precedente.

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.

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$ (definita nella lezione precedente: due elementi di $A$ risultano equivalenti se e solo se appartengono allo stesso blocco della partizione $F$). Diversi esempi. Tra questi: elenco delle relazioni di equivalenza di $\set{1,2}$ e di $\set{1,2,3}$.

Descrizione esplicita delle classi di equivalenza e dell'insieme quoziente definito da un nucleo di equivalenza: 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, quindi si ha $|A/{\sim}|=|\im f|$.

Esercizi proposti:

1. Esercizio 1 dal compito del 16 luglio 2013.
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. 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$.
4. 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)$. Detto $\rho$ il nucleo di equivalenza di $f$, quanti elementi ha $\P(S)/\rho$? Descriverli esplicitamente.

31/10

Discussione di alcuni esercizi proposti nella lezione precedente.

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. 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à. Le intersezioni tra parti chiuse sono a loro volta chiuse. La parte chiusa generata da una parte in una struttura. Alcuni esempi.

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.

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

Monoidi. Tra gli esempi: vari insiemi numerici con l'operazione di addizione o di moltiplicazione; per un arbitrario insieme $S$ sono monoidi $(\P(S),\cap,S)$ e $(T(S),\circ,\id_S)$ (il monoide delle trasformazioni di $S$).

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

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 retrazioni le sezioni.

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

Esercizi proposti:

1. 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$.
2. Osservare che, per ogni insieme $S$, $(\P(S),\cup,\vuoto)$ è un monoide. Descriverne gli elementi simmetrizzabili. Trovare, se possibile, un suo sottosemigruppo che sia un monoide ma non un sottomonoide.
3. Si dimostri che l'operazione $*$ definita nell'esercizio 3 del compito del 14 novembre 2013 è associativa, e si risolva poi l'esercizio (tralasciando le domande relative alla nozione di gruppo).
4. Verificare che, come accennato a lezione, l'operazione $(a,b)\in\R\times\R\mapsto |a-b|\in\R$ (distanza tra due punti della retta reale) è commutativa ma non associativa.
5. 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? Questo prodotto è commutativo?
6. 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.
7. Si determini, in $(\P(\N),\cap)$, la parte chiusa generata da $\P_4(\N)$.

5/11

Discussione di esercizi proposti nella lezione precedente.

L'insieme $\U(M)$ degli elementi simmetrizzabili in un monoide $M$ è un sottomonoide. 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}$).

Gruppi; gruppi abeliani. Esempi, come $(\Z,+,0,-)$, $(\Q\setminus\set\vuoto,\cdot,1,{}^{-1})$, $(\P(S),\ds,\vuoto,\id_S)$ per un insieme $S$. Il gruppo degli invertibili (cioè degli elementi simmetrizzabili) di un monoide.

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

Cenni ad alcune proprietà delle permutazioni e dei gruppi simmetrici: cicli (permutazioni cicliche); trasposizioni (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.

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à. Tavole di Cayley e isomorfismi; a titolo di esempio abbiamo costruito e confrontato tra loro le tavole di Cayley dei gruppi $(\P({1}),\ds)$ e $(\set{1,-1},\cdot)$, tra loro isomorfi.

Un altro esempio di isomorfismo: per un insieme $S$, l'applicazione $X\mapsto S\setminus X$ da $(\P(S),\cup)$ a $(\P(S),\cap)$.

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. Provare che se $\alpha$ è una trasposizione in un insieme $S$, allora $\alpha\circ\alpha=\id_S$ e $\alpha$ coincide con la sua inversa. Provare anche che se $\beta$ è un ciclo di lunghezza 3 in $S$, allora $\beta\circ\beta\circ\beta=\id_S$. È vero che, in questo caso, l'inversa di $\beta$ è $\beta\circ\beta$?
3. Siano $X$ e $Y$ sono insiemi equipotenti (cioè tali che $|X|=|Y|$). Provare che i corrispondenti gruppi simmetrici ed i corrisponenti monoidi delle trasformazioni sono tra loro isomorfi: $\Sym(X)\iso\Sym(Y)$ e $T(X)\iso T(Y)$. (Suggerimento: detta $f\colon X\to Y$ un'applicazione biettiva, si consideri l'applicazione $\sigma\in T(X)\mapsto f\circ \sigma \circ f^{-1} \in T(Y)$.)
4. 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.
5. Tra i monoidi $(\Z,\cdot)$, $(\Z, +)$, $(\N,+)$, $(\P(\N),\cap)$, $(\P(\N),\ds)$ ce ne sono due isomorfi tra loro?
6. 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)$.

7/11

Discussione di esercizi proposti nella lezione precedente, con qualche osservazione ulteriore. Notazione: per ogni $n\in\N^+$, $\S_n=\Sym(\set{1,2,\dots,n})$.

Esempio: la funzione esponenziale come isomorfismo da $(\R,+)$ a $(\R^+,\cdot)$.

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 in una nota sulla cancellabilità. Semigruppi e monoidi (commutativi) cancellativi, Visualizzazione della cancellabilità in tavole di Cayley.

Tavole di Cayley per gruppi finiti. 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.

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

Esercizi proposti:

1. Determinare gli elementi cancellabili nel monoide $(\P(\Z),\cup)$.
2. Provare che l'insieme degli elementi cancellabili a sinistra in un semigruppo (risp. monoide) è una parte chiusa (risp. un sottomonoide).
3. L'insieme $2\Z$ dei numeri interi pari costituisce un sottogruppo di $(\Z,+)$? E l'insieme dei numeri dispari? $\P(\N)$ costituisce un sottogruppo di $(\P(\Z),\ds)$? E $\P(\Z\setminus\N)$?
4. Siano $S$ un insieme non vuoto e $x\in S$. Provare che $\set{\alpha\in \Sym(S)\mid \alpha(x)=x}$ è un sottogruppo di $\Sym(S)$.
5. 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 (risp. un gruppo), allora $C$ ne costituisce un sottomonoide (risp., un sottogruppo).
6. Provare anche che se $\beta$ è un ciclo di lunghezza 3 in un insieme $S$, allora $\set{\id_S,\beta,\beta\circ\beta}$ è un sottogruppo di $\Sym (S)$, precisamente il sottogruppo generato da $\set\beta$.

12/11

Discussione di esercizi proposti nella lezione precedente.

Insiemi ordinati. Ordinamenti duali. Ordinamenti indotti su parti di un insieme ordinato. Esempi. Elementi tra loro confrontabili in insiemi ordinati; ordinamenti totali (o catene); gli ordinamenti indotti su parti di un insieme totalmente ordinato sono totalmente ordinati. Per ogni insieme $S$, $(\P(S),\subseteq)$ è totalmente ordinato se e solo se $|S|\le 1$.

Elementi minimi, massimi, 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). Unicità di minimi e massimi; più in generale: 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 varie 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.

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

14/11

Discussione di esercizi proposti nella lezione precedente, con approfondimenti. Data un'applicazione $f\colon S\to T$, dove $(T,\lt)$ è un insieme ordinato (con $\lt$ 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))$ è di ordine stretto (non si ottiene l'analoga conclusione se si parte da una relazione di ordine largo al posto di $\lt$). Con queste notazioni: descrizione degli 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,\lt)$.

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}$. Per ogni $k,n\in \N$, formula ricorsiva: $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$ e, se $k\le n$, formula chiusa: $\binom nk=n!/(k!(n-k)!)=n^{\underline k}/k!$. 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 binomiale è stata dimostrata in aula per induzione e non come nelle note.

Esercizi proposti:

1. Posto $S=\set{0,1,2,3}$, elencare gli elementi di $\P_3(S)$ e quelli di $\P_6(S)$.
2. Sia $S$ un insieme di cardinaltà 13. Quante sono le parti di $S$ di cardinalità 5? E quante quelle di cardinalità 8? Quante sono le 10-parti di $\P(S)$?
3. Posto $A=\set{1,2,3,\ldots,7}$ e $B=\set{2,5}$, indicare le cardinalità di $L_1:=\set{X\in\P(A)\mid (3\in X)\land(|X|=5)}$ e di $L_2:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X)\land(|X|=5)}$.
4. 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. Quale probabilità ha Anacleto di vincere?

19/11

Discussione di esercizi proposti nella lezione precedente.

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

Applicazioni crescenti ed isomorfismi tra insiemi ordinati. Invarianza di proprietà per isomorfismi tra insiemi ordinati. Esempio di una applicazione biettiva e crescente che non è un isomorfismo (l'applicazione identica da $(A,\le)$ a $(A,|)$, dove $A=\set{2,3,6}$; i due insiemi non sono isomorfi tra loro).

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

Esercizi proposti:

1. Sia $S=\set{n\in\N\mid 2\le n\le 10}$ ordinato dalle relazione di divisibilità in $\N$. Indicare gli elementi minimali, massimali e gli eventuali minimo e massimo in $S$. Quali sono i minoranti ed i maggioranti di $S$ in $(\N,|)$?
2. Generalizzando un esempio visto a lezione, provare che se $S$ è un insieme e $X\subseteq\P(S)$, l'insieme dei minoranti di $X$ in $(\P(S),\subseteq)$ è l'insieme delle parti di $\bigcap X$. Come si può descrivere l'insieme dei maggioranti di $X$?
3. Fornire un esempio di insieme ordinato (non vuoto) $(S,\rho)$ ed una sua parte $X$ tale che $X$ non abbia maggioranti in $(S,\rho)$.
4. Costruire un isomorfismo di insiemi ordinati da $(\P(\set{0,1}),\subseteq)$ a $(\Div_{(\N,\cdot)}(6),|)$. Suggerimento: un isomorfismo deve conservare minimi e massimi.

21/11

Discussione di alcuni esercizi proposti nella lezione precedente.

Intervalli 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. Vari esempi; visualizzazione di proprietà di insiemi ordinati sui loro diagrammi di Hasse.

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 monoide commutativo $(M,\cdot)$. Se $d$ è un MCD (risp. mcm) $d$ 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$.

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

In ogni reticolo, ogni parte finita non vuota ha estremo superiore ed estremo inferiore. Per dimostrarlo, abbiamo usato l'osservazione che segue.
Sia $(S,\rho)$ un insieme ordinato. Per ogni $A\subseteq S$, sia $M_A$ l'insieme dei minoranti di $A$ in $(S,\rho)$. Se $A$ e $B$ sono parti di $S$, allora $M_{A\cup B}=M_A\cap M_B$. Se poi esistono in $(S,\rho)$ sia $a=\inf A$ che $b=\inf B$, allora $M_{A\cup B}=M_{\set{a,b}}$; dunque in $(S,\rho)$ esiste $\inf(A\cup B)$ se e solo se esiste $\inf\set{a,b}$, ed in questo caso questi due estremi inferiori coincidono. Vale l'enunciato duale per gli estremi superiori.

Esercizi proposti:

1. L'insieme ordinato $(\Pf(\N),\rho)$ descritto nel secondo esercizio della lezione del 12/11 è un reticolo?
2. L'insieme $\set{1,2,3,18,20,36}$, ordinato per divisibilità, è un reticolo?
3. 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.

26/11

Discussione di esercizi proposti nella lezione precedente, con approfondimenti e varianti.

I reticoli finiti sono completi, e di conseguenza limitati (cioè: hanno minimo e massimo). Per un reticolo arbitrario, le nozioni di minimo e minimale (risp.  e massimo e massimale) sono tra loro equivalenti.

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

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

Sottoreticoli; 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 un reticoli distributivi sono distributivi.

Esercizi proposti:

1. Sia $(L,\le)$ un reticolo, con operazioni reticolari $\land$ e $\lor$. In quali casi le le due operazioni reticolari hanno elementi neutri, e, nel caso, quali sono?
2. 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?
3. Esibire un esempio di reticolo complementato in cui esiste un elemento con esattamente 1000 complementi.
4. 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,30}$; $S_6=\set{1,2,5,10,50,60,300}$.

28/11

Discussione di alcuni degli esercizi proposti nella lezione precedente.

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 ed algebre di Boole. Il duale di un reticolo complementato (risp. distributivo, booleano) è necessariamente complementato (risp. distributivo, booleano). Dualità per reticoli booleani. 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.

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. Equivalenza tra le nozioni di anello booleano e di reticolo booleano: costruzione di un reticolo booleano a partire da un anello booleano e costruzione inversa. Teorema di Stone per anelli booleani. (Le sottoalgebre di Boole di un'algebra di Boole sono precisamente i sottoanelli unitari dell'anello booleano costruito su di essa).

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

Operazione quoziente (cioè quella indotta sul quoziente determinato da un'equivalenza compatibile con un'operazione binaria). Questa è ben definita solo nel caso in cui l'equivalenza sia compatibile con l'operazione.

Esercizi proposti:

1. Il reticolo dei divisori di 30, ordinato per divisibilità, è booleano. Si scriva un isomorfismo tra esso e $(\P(\set{1,2,3}),\subseteq)$.
2. Provare che, in ogni algebra di Boole, l'operazione unaria di complemento è involutoria (cioè: il complemento del complemento di ogni elemento $x$ è $x$ stesso).
3. Verificare, in una arbitraria algebra di Boole $B$, le leggi di De Morgan: per ogni $a$, $b\in B$, $(a\land b)'=a'\lor b'$ e $(a\lor b)'=a'\land b'$.
4. Verificare in dettaglio la correttezza della costruzione di un'anello booleano a partire da un reticolo booleano e di un reticolo booleano a partire da un anello booleano.
5. Siano $a$ e $b$ elementi di un anello $R$. Provare che se $(a+b)^2=a^2+b^2+2ab$ allora $ab=ba$.
6. Se $(M,\cdot)$ è un monoide commutativo, la relazione "essere elementi associati in $M$" è compatibile con $\cdot$.
7. La relazione "avere la stessa parità", che abbiamo definito in $\Z$, è compatibile con le usuali operazioni di addizione e moltiplicazione in $\Z$.
8. La relazione "avere la stessa lunghezza", che abbiamo definito nel monoide delle parole su un arbitario alfabeto, è compatibile con l'operazione di concatenazione tra parole.
9. (Generalizzazione dell'esercizio precedente.) Sia $f\colon A\to B$ un omomorfismo tra le strutture algebriche $(A,*)$ e $(B,\bullet)$. Provare che il nucleo di equivalenza di $f$ è una congruenza in $(A,*)$.
10. La relazione di equipotenza in $\Pf(\N)$ è compatibile con una delle operazioni $\cap$, $\cup$, $\ds$?

3/12

Congruenze in una struttura algebrica. Struttura quoziente ed epimorfismo canonico. 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.

Cancellabilità e divisori dello zero negli anelli; anelli integri e domini di integrità (si veda la seconda parte delle note sulla cancellabilità). I corpi sono anelli integri, i campi sono domini di integrità. Alcuni esempi. In un anello unitario, gli elementi idempotenti diversi dall'unità sono divisori dello zero.

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. Gli anelli quoziente $\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$).

Se $m$ è un intero positivo composto (cioè il prodotto di due interi maggiori di 1), $\Z_m$ non è un dominio di integrità.

Algoritmo euclideo delle divisioni successive per la determinazione di un massimo comun divisore tra due interi. Un esempio; giustificazione dell'algoritmo, qualche idea per la sua velocizzazione (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.

Esercizi proposti:

1. Calcolare $15\modbin 9$ (ovvero: $\rest(15,9)$), $15\modbin (-9)$, $(-15)\modbin 9$, $(-15)\modbin (-9)$.
2. Si elenchino gli elementi di $S\cap [17]_3$, 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. Si descriva in dettaglio l'anello $\Z_6$, stabilendo per ogni suo elemento $c$ se $c$ è o meno: invertibile, divisore dello zero, cancellabile, idempotente.
6. Provare che gli anelli $\Z_2$ e $\Z_3$ sono campi.
7. Utilizzando l'algoritmo euclideo, calcolare il massimo comun divisore positivo $d$ tra 214 e 453. Trovare poi due interi $u$ e $v$ tali che $d=214u+453v$. Esistono due interi positivi $h$ e $k$ tali che $8=214h+453k$?

5/12

Rapida discussione di alcuni degli esercizi proposti nella lezione precedente.

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,

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

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

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$. (Solo) definizione della funzione di Eulero.

Metodi di semplificazione e di soluzione di equazioni congruenziali; 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.

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

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.

Esercizi proposti:

1. Esercizi da 5 a 11 da Tautologie, insiemi, aritmetica. (NB: l'espressione $ax\equiv b\pmod m$ è equivalente a $ax\equiv_m b$.)
2. Trovare, se possibile, soluzioni delle equazioni congruenziali $302x\equiv_{144} 6$, $144x\equiv_{302} 6$ e $151x\equiv_{72} 3$.
3. Trovare, se possibile, soluzioni dell'equazione congruenziale $200x+10\equiv_{72} 49x+13$.
4. 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?
5. Si individuino gli elementi invertibili, quelli cancellabili, quelli idempotenti e i divisori dello zero nell'anello $\Z_{20}$.
6. Verificare che, se $S$ è un insieme, il gruppo $(\P(S),\ds)$ è abeliano, ma è ciclico se e solo se $|S|\lt 2$.

10/12

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

Cenno al prodotto diretto di anelli; per ogni intero positivo $n$, l'anello booleano $\Z_2^n$ e sua rappresentazione come insieme di "stringhe di zeri ed uno" di lunghezza $n$. Anelli booleani e funzioni caratteristiche: l'isomorfismo canonico di anelli da $\P(\set{1,2,\dots,n})$ a $\Z_2^n$; interpretazione insiemistica delle algebre di Boole costituite da stringhe di 0 ed 1 di assegnata lunghezza.

Divisori banali; elementi irriducibili ed elementi primi in un monode commutativo cancellativo. 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. Alcuni esempi (i gruppi abeliani, $(\N,+)$). Teorema fondamentale dell'aritmetica (fattorialità dei monoidi $(\N^+,\cdot)$ e $(\Z\setminus\set0,\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=p_1^{a_1} p_2^{a_2}\cdots p_n^{a_n}$ è una sua decomposizione primaria (dunque, 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 $u p_1^{b_1} p_2^{b_2}\cdots p_n^{b_n}$, dove $u$ è 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.

Esercizi proposti:

1. Sia $G$ un gruppo e sia $x\in G$. Allora l'applicazione $n\in\Z\mapsto x^n\in G$ è un omomorfismo, e la sua immagine è il sottogruppo (ciclico) $\gen x$ di $G$ generato da $x$.
2. Nelle notazioni dell'esercizio precedente, se $x$ è periodico, il periodo di $x$ coincide con $|\gen x|$.
3. Determinare il periodo di ciascun elemento del gruppo $(\R\setminus\set 0,\cdot)$.
4. Determinare il periodo degli elementi $[7]_{30}$ e $[29]_{30}$ del gruppo degli invertibili dell'anello $\Z_{30}$.
5. Esercizio nr. 12 da Tautologie, insiemi, aritmetica.
6. Verificare in dettagli le affermazioni fatte a proposito della descrizione di divisori, MCD e mcm in monoidi fattoriali.
7. Quanti sono i divisori in $\Z$ di $5!\;$? E quanti quelli di $2^4 13^7 49$?

12/12

Alcune considerazioni sui numeri primi. Per ogni intero positivo $n$, l'anello $\Z_n$ è un campo se e solo se $n$ è primo. Cenni al crivello di Eratostene. 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.

Abbiamo appena accennato, e solo a titolo di notizia, alle applicazioni della funzione di Eulero ed al fatto che il calcolo dei suoi valori è collegato al problema (non risolto da alcun algoritmo efficiente) di fattorizzare un intero positivo in prodotto di numeri primi. Chi è interessato può consultare in questo sito delle note a questo proposito.

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

Aggiornamento: è ora disponibile una nuova versione delle mie note sui polinomi, più conforme alla presentazione dell'argomento svolta a lezione.

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 e, per ogni intero positivo $n$, l'epimorfismo da $\Z[x]$ a $\Z_n[x]$ che ad ogni polinomio $f$ associa $f$ stesso "riguardato modulo $n$".

Terminologia essenziale: successione dei coefficienti di un polinomio, grado e coefficiente direttore di un polinomio, termine noto, polinomi costanti, 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: $A[x]$ è un dominio di integrità se e solo se lo è $A$; in questo caso vale in $A[x]$ la regola di addizione dei gradi (per ogni coppia di polinomi) e si ha $\U(A[x])=\U(A)$. Esempi che mostrano come queste due proprietà non valgano necessariamente se $A$ non è integro. Qualunque sia $A$, $x\notin\U(A[x])$ e, di conseguenza, $A[x]$ non è un campo.

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

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.

Note alternative sugli anelli polinomi sono nel sito docenti della Professoressa Leone.

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_n}$ 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\in A[x]$. Provare che, se $f$ divide $g$ in $A[x]$, allora ogni radice di $f$ è radice anche di $g$.
7. 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

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.

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. Metodi di fattorizzazione di polinomi a coefficienti in un campo. I polinomi irriducibili in $\Z_2[x]$ di grado 2, 3 o 4.

Per questi contenuti ed ulteriori esempi, si possono consultare le mie note sui polinomi, che possono essere di aiuto anche per gli esercizi proposti.

Introduzione ai grafi. Definizione di grafo semplice (sia in termini di lati che in termini di relazione di adiacenza; equivalenza tra le due definizioni). Rappresentazione grafica.

Esercizi proposti:

1. Determinare il massimo comun divisore monico in $\Q[x]$ tra $x^8-1$ e $x^5-1$.
2. Elencare i polinomi irriducibili di grado 2 o 3 in $\Z_3[x]$.
3. In $\Z_3[x]$ si consideri il polinomio $f=x^4+x^3+x^2+2x+1$. Dopo averne determinato le radici, lo si fattorizzi nel prodotto di un invertibile e di polinomi irriducibili monici. Si ripeta l'esercizio (sempre in $\Z_3[x]$) per $2x^4+x^3+x^2+x+2$ al posto di $f$.
4. Esercizio nr. 3 da Polinomi e strutture algebriche
5. Si fattorizzi $f=x^7+3x^6-4x^5+10x-10$ in prodotto di polinomi irriducibili monici in $\Q[x]$. (Si ricorda che l'esercizio non è completo se non si è dimostrata l'irriducibilità dei fattori trovati). Quanti sono i divisori monici di $f$ in $\Q[x]$? I divisori di $f$ irriducibili in $\Q[x]$ sono irriducibili anche in $\R[x]$?

19/12

Cenni alle diverse nozioni di grafo; 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$.