1 — 11/9

Gran parte delle lezione è stata dedicata ad informazioni generali sull'università, sui servizi di ateneo a disposizione degli studenti, su contenuti e finalità del corso di algebra, modalità di svolgimento e materiali didattici e sul tipo di impegno che aspetta gli studenti.

Per il resto: introduzione molto informale alle nozioni di linguaggio, formula e termine, cenni alla distinzione tra sintassi e semantica. Introduzione ai connettivi proposizionali: negazione, congiunzione, disgiunzione (inclusiva).

Più che per il (molto ridotto) contenuto di questa lezione, sarà pertinente per le prossime la nota Logica rudimentale.

2 — 13/9

Nozione, ancora da approfondire, di formula chiusa o proposizione. Introduzione al calcolo proposizionale. Tavole (o tabelle) di verità e loro uso per la descrizione (semantica) di connettivi proposizionali: il connettivo unario di negazione (NOT, $\lnot$), i connettivi binari di congiunzione (AND, $\land$), disgiunzione (inclusiva; OR, $\lor$), disgiunzione esclusiva ($\xor$), congiunzione negata ($\nand$), bicondizionale (o equivalenza; $\Leftrightarrow$, $\leftrightarrow$).

Comparazione tra l'uso di questi connettivi in un linguaggio semiformalizzato e nel linguaggio ordinario.

Forme proposizionali e calcolo dei loro valori di verità; alcuni esempi. Tautologie, contraddizioni, forme contingenti. Forme logicamente equivalenti tra loro.

Alcune tautologie fondamentali; tra queste i principi del terzo escluso e di non contraddizione, tautologia della doppia negazione; tautologie di iteratività (o idempotenza), commutatività, associatività; distributività per i connettivi $\land$ e $\lor$; leggi di De Morgan.

Il connettivo condizionale (implicazione; $\implica$ o $\to$), con discussione sulla semantica che lo descrive. Espressioni verbali usate per esprimere implicazioni. Antecedente e conseguente di una implicazione.

Si può trovare quanto discusso nella lezione di oggi (e nelle prossime) nella prima parte di Logica rudimentale. Possono essere anche utili: tavola dei connettivi binari ed esempi di tautologie.

Esercizi proposti (particolarmente consigliati: 1, 4, 5, 6):

1. Scrivere le tavole di verità delle forme proposizionali $p\implica(\lnot p)$, $p\lor(p\land q)$ e $(p\land (\lnot q)\land r)$.
2. Verificare che le forme proposizionali che a lezione, pur senza dimostrarlo, sono state indicate come tautologie lo sono effettivamente.
3. Decidere se la forma proposizionale $(p\nand (q\nand r))\iff ((p\nand q)\nand r)$ è una tautologia.
4. Molti utili esercizi sono nella prima parte di Logica rudimentale. Consiglio di provare, in particolare, gli esercizi B3, B4, B5, C2 e D2.
5. Negare le frasi "se piove mi bagno", "se piove non mi bagno", "se piove, mi bagno e mi ammalo".
6. Valutare cosa esprima il connettivo descritto da questa tavola di verità:

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

3 — 15/9

Discussione di molti esercizi dalla lezione precedente.

Alcune tautologie sulla implicazione: negazione dell'implicazione, implicazione come disgiunzione, legge di contrapposizione, tautologia della doppia implicazione, transitività dell'implicazione (e dell'equivalenza). Espressioni verbali usate per esprimere equivalenze.

Negazioni alternative del bicondizionale, tautologie di associatività per $\shiff$ e $\xor$, distributività di $\land$ rispetto a $\xor$.

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

Introduzione alla logica dei predicati. Variabili e loro sostituzioni. I quantificatori universale ed esistenziale. Occorrenze libere ed occorrenze vincolate di variabili.

Avvertenza: come indicato in un avviso nella pagina principale del corso, non faremo lezione il prossimo lunedì 18 per il buon, anche se non particolarmente giustificato, motivo che l'ateneo sarà, quel giorno, chiuso.

Esercizi proposti (con priorità a 3, 4, 5 ed a E1, E2, E5, E8 in 1):

1. Esercizi: D (completare) ed E da Logica rudimentale.
2. Verificare le tautologie in esempi di tautologie.
3. Abbiamo provato la distributività di $\land$ rispetto a $\xor$. Verificare che $\lor$ non è distributivo rispetto a $\xor$, vale a dire: $\big(p\lor (q\xor r)\big)\iff \big((p\lor q)\xor (p\lor r)\big)$ non è una tautologia. Analogamente, $\lor$ è distributivo rispetto a $\shiff$? Ovvero: $\big(p\lor (q\shiff r)\big)\iff \big((p\lor q)\shiff (p\lor r)\big)$ è una tautologia?
4. Negare: “Se esco di casa o mi affaccio al balcone, vedo Maria e Franco”.
5. Negare la forma proposizionale $(p\lor q)\implica (r\land s)$.

4 — 20/9

Discussione di molti esercizi dalla lezione precedente.

Ancora sulla sintassi dei quantificatori e sulle occorrenze libere o vincolate delle variabili; esempi ed abbreviazioni. Proposizioni (o formule chiuse). Predicati. Nelle sostituzioni di termini a variabili vengono sostituite solo le occorrenze libere delle variabili.

Quantificatori ristretti.

Alcune regole del calcolo dei predicati (come in Logica rudimentale), tra esse: negazione di formule con quantificatori (anche ristretti).

Esercizi proposti:

1. Da Logica rudimentale: esercizi H ad eccezione di H4. Notazione: $\in$ è il simbolo di appartenenza insiemistica; $\N$ e $\Z$ sono, nell'ordine, gli insiemi dei numeri naturali (cioè interi non negativi) ed interi. Quindi, ad esempio, `$x\in\Z$' va letta come `x è un numero intero'.
2. Si stabilisca il valore di verità delle formule $\forall x\mathrel\lozenge 3(x>100)$ e $\exists x\mathrel\lozenge 3(x>100)$ nell'ambito della teoria dei numeri interi, dove il simbolo $\lt$ e le costanti 3 e 100 sono interpretati nel modo usuale e $\lozenge$ è interpretato in accordo con questa definizione: per ogni coppia di numeri interi $a$ e $b$, $a\mathrel\lozenge b$ se e solo se $(a\lt b\land b\lt a)$.

5 — 22/9

Discussione di alcuni esercizi dalla lezione precedente.

Ancora sulle regole del calcolo dei predicati: quantificatori ripetuti; comparazione tra formule del tipo $\forall x(\exists y(\dots))$ e del tipo $\exists y(\forall x(\dots))$. Il quantificatore $\exists!$.

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

L'insieme vuoto $\vuoto$; sua unicità. Il singleton $\set x$ di un insieme $x$ (èsempre diverso da $x$). Informazione importante: vale $\forall x(x\notin x)$.

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

Esercizi proposti:

1. Da Logica rudimentale, in aggiunta a quanto visto a lezione, consiglio di riflettere su G1, I3, I4.
2. Verificare che $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)\land x\ne y))$ esprime la negazione di $\exists!x(\phi(x))$. Andrebbe bene anche $(\forall x(\lnot \phi(x)))\lor (\exists x,y(\phi(x)\land \phi(y)))$?
3. Quanti elementi ha $\set{\vuoto,\set\vuoto}$? Quanti elementi ha $\set{\N}$? E quanti $\set{\set\N}$? E quanti $\set{\set{\set{\set\vuoto}}}$?
4. Per assegnati $a,b,c$, sia $x=\set{a,b,c}$. Quanti elementi ha $x$?

6 — 25/9

Discussione degli esercizi dalla lezione precedente.

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

Nozioni insiemistiche e connettivi proposizionali. Comparazione tra i connettivi di equivalenza e implicazione da una parte, le relazioni di uguaglianza e inclusione tra insiemi dall'altra; operazioni insiemistiche binarie di unione, intersezione e differenza simmetrica, ed identità insiemistiche che coinvolgono queste operazioni dedotte da tautologie (di commutatività, associatività, iteratività, distributività) che coinvolgano $\lor$, $\land$, $\xor$. Osservazione aggiuntiva: per ogni $a$ si ha $a\ds a=\vuoto$. L'operazione binaria di differenza tra insiemi; complemento di un insieme in un insieme che lo contenga e connettivo di negazione. Diverse formule tra quelle in Tautologie ed identità insiemistiche; formule insiemistiche di De Morgan (per terne arbitrarie di insiemi).

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

L'unione unaria $\bigcup a=\set{x\mid \exists b\in a(x\in b)}$ di un insieme $a$.

Esercizi proposti (dare priorità a 1, 4, 5, 9, 10, 12, 13):

1. Vero o falso?: $\vuoto\in\vuoto$; $\vuoto\subseteq\vuoto$; $\vuoto=\set\vuoto$; $\vuoto\subseteq\set\vuoto$; $\vuoto\in\set\vuoto$; $\vuoto\sseq\set{1,2,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{2,1,3}$; $\set{1,1,2,2,2,3,3}\sseq\set{4,2,1,3}$.
2. Esercizi J da Logica rudimentale (essenzialmente già visti a lezione).
3. Verificare le formule in Tautologie ed identità insiemistiche (ne abbiamo già viste molte a lezione).
4. Siano $a=\set{1,2,3,4,5,6,7}$, $b=\set{5,6,7,8,9}$, $c=\set{0,5,9}$. Elencare gli elementi di: $a\cap b$, $a\ds b$, $b\setminus c$, $(c \setminus b)\ds a$.
5. Calcolare, per un arbitario insieme $a$, $a\cup\vuoto$, $a\cap\vuoto$, $a\setminus\vuoto$ e $a\ds\vuoto$.
6. Dimostrare che per ogni $a,b$ sono equivalenti: (1) $a\sseq b$; (2) $a\cap b=a$; (3) $a\cup b=b$; (4) $a\setminus b=\vuoto$; (5) $a\ds b=b\setminus a$.
7. Rappresentare, in un diagramma di Venn generico, il termine insiemistico $a\cap(b\ds c)$.
8. Svolgere l'esercizio 2 dal compito del 13 novembre 2013.
9. Spiegare perché questo non è un diagramma di Venn generico mentre quest'altro lo è.
10. Provare, utilizzando diagrammi di Venn, che per ogni $a$, $b$ $c$, si ha $(a\cup b)\setminus c= (a\setminus c)\cup (b\setminus c)$ e $(a\cap b)\setminus c= (a\setminus c)\cap (b\setminus c)$ (distributività da destra della differenza insiemistica rispetto ad unione e intersezione binarie).
11. Rappresentare, in un diagramma di Venn generico, i termini insiemistici $a\cup(b\cap c)$ e $a\cap(b\cup c)$. Decidere se vale una delle formule $\forall a,b,c \big(a\cup(b\cap c)\sseq a\cap(b\cup c)\big)$ e $\forall a,b,c \big(a\cup(b\cap c)\supseteq a\cap(b\cup c)\big)$.
12. Verificare che, per ogni $a,b$, si ha $a\cup b=\bigcup\set{a,b}$.
13. Calcolare $\bigcup \vuoto$, $\bigcup\set{\vuoto}$, e poi $\bigcup\set{a}$ e $\bigcup\P(a)$ per un arbitrario insieme $a$.

7 — 27/9

Discussione di alcuni esercizi dalla lezione precedente.

L'intersezione (unaria) $\bigcap a=\set{x\mid \forall b\in a(x\in b)}$ di un insieme non vuoto $a$. Discussione sul motivo per cui $\bigcap \vuoto$ non è definito. Riduzione di unione ed intersezione binaria alle corrispondenti operazioni unarie: per ogni $a,b$ si ha $a\cup b=\bigcup \set{a,b}$ e $a\cap b=\bigcap \set{a,b}$.

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

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

Esercizi proposti:

1. Calcolare $\bigcup s$ e $\bigcap s$ in ciascuno dei seguenti casi: (1) $s=\big\{\set{1,5,7},\set{1,5,8,9},\set{2,15,66}\big\}$; (2) $s$ è l'insieme delle parti finite di $\N$; (3) $s=\set{x\subseteq\N\mid 3\notin x}$; (4) $s=\set{x\subseteq\N\mid 3\in x}$; (5) $s=\big\{\set{124,n}\mid n\in\N\big\}$; (6) $s=\set{[n-1,n+1]\mid n\in\N}$, dove, si ricorda, per ogni coppia $a,b$ di numeri reali, $[a,b]=\set{x\in\R\mid a\le x\le b}$ è l'insieme dei numeri reali compresi tra $a$ e $b$.
2. Completare le dimostrazioni delle formule presentate a lezione.
3. Vero o falso? (1): $3\in\set{2n^2+1\mid n\in\Z}$; (2): $10\in\set{2n^2+1\mid n\in\Z}$; (3): $\set{1}\in\set{\set{a,b}\mid a,b\in\Z}$; (4): $\set{1,2}\in\set{\set{a,b}\mid a,b\in\Z}$; (5): $\set{1,2,3}\in\set{\set{a,b}\mid a,b\in\Z}$; (6): $\Z=\set{a-b\mid a,b\in\Z}$.

8 — 29/9

Discussione di alcuni esercizi dalla lezione precedente.

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

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

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

Prodotto relazionale tra corrispondenze; sua associatività.

AVVISO: come indicato in un avviso nella pagina principale del corso, lunedì prossimo (il 2) faremo quattro ore lezione (non si terrà la lezione mattutina di analisi).

Esercizi proposti (sono prioritari quelli con numero pari):

1. (per i più curiosi). Provare che per ogni $a$, $b$, $c$ e $d$, si ha $\set{\set a,\set{a,b}}=\set{\set c,\set{c,d}}$ se e solo se $a=c$ e $b=d$. (Suggerimento: se $x=\set{\set a,\set{a,b}}$, allora $a=\bigcap\big(\bigcap x\big)\;\dots$) Tenendo conto di questa proprietà, si può dunque dare una definizione esplicita delle coppie ordinate, ponendo $(a,b):=\set{\set{a},\set{a,b}}$ per ogni $a$ e $b$. In effetti, questa è la definizione di coppia ordinata proposta da Kuratowski (ma ce ne sono altre!).
2. Dimostrare che, per ogni $x$ e $y$:
   1. $x\times y=\vuoto$ se e solo se uno tra $x$ e $y$ è vuoto;
   2. $x\times y=y\times x$ se e solo se o $x=y$ oppure uno tra $x$ e $y$ è vuoto.
3. Elencare gli elementi di $\set{1,2}\times \set{1,2,3}$, quelli di $\set{1,2,3}\times \set{1,2}$ e quelli di $(\set{1,2}\times \set{1,2,3})\cap (\set{1,2,3}\times \set{1,2})$.
4. Vero o falso?
   1. $(\set{0}\times\N)\cup (\set{1}\times\N)=\set{0,1}\times\N$;
   2. $(\N\times\N)\cup ((\Z\setminus \N)\times(\Z\setminus \N))=\Z\times\Z$.
5. Siano $a=\set{1,2,3}$ e $b=\set{0,5,10}$. Sia poi $\rho$ la corrispondenza da $a$ a $b$ definita da: per ogni $x\in a$ e $y\in b$ si ha $x\mathrel\rho y\iff x^2\le y$. Elencare gli elementi del grafico di $\rho$. Rappresentare poi $\rho$ con un diagramma con frecce e con una tabella.
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$.
7. Siano $\alpha$ e $\beta$ le corrispondenze da $\Z$ a $\P(\Z)$ definite ponendo, per ogni $n\in\Z$ e $x\in \P(\Z)$, $\quad n\mathrel{\alpha}x\iff n\in x\quad$ e $\quad n\mathrel{\beta}x\iff n\notin x$. Sia poi $\gamma$ la relazione di inclusione in $\P(\Z)$, cioè la relazione binaria in $\P(\Z)$ definita ponendo, per ogni $x,y\in\P(\Z)$, $x\mathrel{\gamma}y\iff x\sseq y$. Descrivere $\alpha\gamma$ e $\beta\gamma$.
8. Sia $a=\set{x\in\N\mid x\lt 10}$ e sia $\tau$ la relazione binaria in $a$ definita da: $\forall x,y\in a (x\mathrel\tau y\iff x\lt y)$. Descrivere $\tau^2=\tau\tau$ e $\tau^3=\tau\tau\tau$. Se, per ogni intero positivo $n$, indichiamo con $\tau^n$ il prodotto $\tau\tau\cdots\tau$ con $n$ fattori, è vero o falso che esiste un intero positivo $n$ tale che $\tau^n$ sia la relazione binaria in $a$ con grafico vuoto?

11 — 4/10

Discussione di molti (troppi?) esercizi dalla coppia di lezioni precedenti.

Sia $f\colon a\to b$ un'applicazione. Allora $f$ è suriettiva se e solo se $\forall y\in b(\avecf(\set{b})\ne\vuoto)$. Inoltre, per ogni $c\in\P(a)$ e $d\in\P(b)$ si ha $c\sseq\avecf(\vecf (c))$ (e l'inclusione può essere stretta) e $\vecf(\avecf (d))=d\cap\im f$, quindi $f$ è suriettiva se e solo se $\forall d\in\P(b)(\vecf(\avecf (d))=d)$.

Applicazioni iniettive. Negazione dell'iniettività: un'applicazione $f\colon a\to b$ non è iniettiva se e solo se: $\exists x,y\in a$$(x\ne y\land f(x)=f(y))$. Se $a$ è un insieme con non più di un elemento, ogni applicazione di dominio $a$ è iniettiva. Sono iniettive le immersioni ed anche tutte le restrizioni delle applicazioni iniettive. Applicazioni biettive; lo sono le applicazioni identiche.

La composta tra due applicazioni (componibili) iniettive è certamente iniettiva; viceversa, se un'applicazione composta $g\circ f$ è iniettiva, allora $f$ è iniettiva (ma $g$ può non esserlo, anche se $g\circ f$ è biettiva). È stata dimostrata solo la prima di queste affermazioni; il resto verrà provato nella prossima lezione.

AVVISO: come indicato in un avviso nella pagina principale del corso, venerdì 6 non faremo lezione.

Esercizi proposti:

1. Provare che, come già visto per le applicazioni, per ogni $a$ e $b$ ed ogni $f\in\Corr(a,b)$, si ha $\id_a f=f\id_b=f$ (stiamo qui facendo uso del prodotto relazionale).
2. Dimostrare che se $f\colon a\to b$ è un'applicazione, $f$ è iniettiva se e solo se $\forall c\in\P(a)(\avecf(\vecf (c))=c)$.
3. Siano $f\colon a\to b$ e $g\colon b\to a$ applicazioni. Provare che l'applicazione immagine $(g\circ f)\vec{\phantom 1}3$ definita da $g\circ f$ è $\vecg\circ \vecf$ e che, analogamente, $(g\circ f)\avec{\phantom 1}3=\avecf\circ\avecg$.
4. Provare che per ogni insieme $a$ sia l'applicazione immagine che l'applicazione antiimmagine definite da $\id_a$ coincidono con $\id_{\P(a)}$.
5. Delle applicazioni proposte negli esercizi della lezione scorsa (inclusi quelli dalla raccolta "per le vacanze di pasqua"), stabilire se sono iniettive.
6. L'applicazione $h\colon a\in\Z\mapsto \begin{cases}a+1&\text{se $a$ è pari}\\a+2&\text{se $a$ è dispari}\end{cases}\in\Z$ è iniettiva? Determinare $\im h$.
7. Di ciascuna delle seguenti applicazioni, decidere se sono iniettive e se sono suriettive:
   • $a\colon n\in\N\mapsto n+1 \in\N$
   • $b\colon n\in\Z\mapsto n+1 \in\Z$
   • $c\colon n\in\N\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\N$
   • $d\colon n\in\Z\mapsto \begin{cases}n-1&\text{se $n\ne 0$}\\8137&\text{se $n=0$}\end{cases}\in\Z$

12 — 9/10

Discussione di alcuni esercizi dalle lezioni precedenti.

Dimostrazione dell'enunciato lasciato in sospeso alla lezione precedente: se un'applicazione composta $g\circ f$ è iniettiva, allora $f$ è iniettiva (ma $g$ può non esserlo, anche se $g\circ f$ è biettiva). Conseguenze ovvia di questo e di altri risultati già visti, a proposito della biettività.

Un'applicazione $f\colon a\to b$ è iniettiva se e solo se $|\avecf(\set y)|\le 1$ (cioè: $\avecf(\set y)$ o è vuoto o è un singleton) per ogni $y\in b$; conseguenti caratterizzazioni della biettività (sulle quali torneremo)

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

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

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

Esercizi proposti:

1. Siano $a=\set{0,1,2}$ e $b=\set{0,1,2,3}$. Trovare tutte le sezioni delle applicazioni qui definite:
   • $f\colon x\in a\mapsto x+1\in b$
   • $\alpha\colon b\to a$ che manda 3 in 1 ed ogni altro elemento di $b$ in sé stesso.
2. Si scrivano tre diverse sezioni dell'applicazione $x\in\P(\Z)\mapsto x\cap\N\in\P(\N)$.

13 — 11/10

Discussione degli esercizi dalle lezioni precedente.

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

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

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

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

Esempi di inverse; vari metodi che permettono di riconoscere che un'applicazione sia biettiva. Osservazione: per un'applicazione $f\colon a\to a$ (di dominio e codominio uguali), poniamo $f^2=f \circ f$, $f^3=f \circ f\circ f$ e, più in generale, per ogni intero $n>1$, $f^n=f\circ f\circ \cdots\circ f$, composizione con $n$ fattori (tutti uguali a $f$). Se $f^n=\id_a$, allora $f$ è biettiva, con inversa $f^{n-1}$ (ad esempio, $f=f^{-1}$ se e solo se $f^2=\id_a$).

Osservazioni sull'importanza della nozione di invertibilità.

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

Esercizi proposti:

1. Trovare tutte le sezioni e retrazioni delle applicazioni nell'esercizio nr. 7 dalla lezione numero 11.
2. Tra le applicazioni $f\colon n\in\Z\mapsto 2n-1\in\Z$, $g\colon n\in\Z\mapsto 2n-1\in\Q$, $h\colon n\in\Q\mapsto 2n-1\in\Q$, $k\colon n\in\Z\mapsto 8-n\in\Z$ si dica quali sono biettive e di queste si determinino le inverse. Fare lo stesso per l'applicazione $\alpha$ da $a=\set{1,2,3,4}$ ad $a$ che manda 1 in 3, 2 in 4, 3 in 2 e 4 in 1.
3. Si trovi l'inversa dell'applicazione al punto (ii) dell'esercizio 7 di quelli per le vacanze di pasqua.
4. Si verifichi che l'applicazione $n\in\Z\mapsto\begin{cases}2n-1,&\text{se }n\gt0\\-2n,&\text{se }n\le0\end{cases}\in\N$ è biettiva.
5. Si verifichi che l'applicazione $n\in\N\mapsto \begin{cases}-n/2,&\text{se }n\text{ è pari}\\(n+1)/2,&\text{se }n\text{ è dispari}\end{cases}\in\Z$ è biettiva.
6. Per caso le due applicazioni agli esercizi precedenti sono l'una inversa dell'altra?
7. L'operazione $*\colon(x,y)\in \Z\times \Z\mapsto x+y+1\in \Z$ è associativa? È commutativa?

14 — 13/10

Discussione degli esercizi dalla lezione precedente.

Ulteriori esempi di operazioni, associative e non, commutative e non. Nozione di struttura algebrica. Semigruppi. Cenno ai teoremi di associatività e di commutatività.

Osservazione: se $a$ è un insieme, il semigruppo delle trasformazioni di $a$ è commutativo se e solo se $a$ ha al massimo un elemento.

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

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

Elementi neutri a sinistra e a destra; elementi neutri. Vari esempi. Rispetto ad un'operazione binaria, un elemento è neutro a sinistra (risp. a destra) se e solo se è neutro a destra (risp. a sinistra) rispetto all'operazione opposta. Cenno al principio di dualità destra/sinistra per operazioni binarie (ad esempio, rispetto ad un'operazione binaria $*$, un elemento è neutro a sinistra (risp. a destra) se e solo se è neutro a destra (risp. a sinistra) rispetto a $*^{op}$. Neutri e passaggio ad una struttura indotta.

Teorema (unicità dei neutri): se, in una assegnata struttura con un'operazione binaria, $s$ è un elemento neutro a sinistra e $d$ è un elemento neutro a destra, allora $s=d$ e quindi $s$ è neutro, inoltre $s$ è l'unico elemento neutro a destra nonché l'unico elemento neutro a sinistra nella struttura. Esempi di strutture con più di un neutro a destra o a sinistra.

Esercizi proposti: (dare priorità a: 2, 3, 4, 6 per quanto si può, 7):

1. Sia $*$ un'operazione binaria associativa e commutativa sull'insieme $S$. Senza fare uso dei teoremi di associatività e commutatività, dimostrare in modo diretto che, per ogni $a,b,c,d\in S$, si ha: $(a*b)*(c*d)=(a*c)*(b*d)$.
2. Delle seguenti tredici parti di $\Z$: $\N$, $\Z\setminus \N$, $\vuoto$, $\set{x\in\Z \mid x > 8}$, $\set{x\in\Z \mid x> -8}$, $\set 0$, $\set 1$, $\set {0,1}$, $\set {-1}$, $\set {0,1,2}$, $\set {1,-1}$, l'insieme degli interi pari, l'insieme degli interi dispari, dire quali sono chiuse rispetto alle (usuali) operazioni di addizione o di moltiplicazione.
3. L'insieme delle parti finite di $\N$ è chiuso in $(\P(\N),\cap)$, in $(\P(\N),\cup)$, in $(\P(\N),\ds)$? E quello delle parti infinite?
4. Nella struttura formata dall'insieme delle parole su un alfabeto che contenga la lettera y con l'operazione di concatenazione, dire se sono o non sono parti chiuse: l'insieme delle parole di lunghezza (nel senso ovvio) maggiore di 55; l'insieme delle parole di lunghezza pari; l'insieme delle parole che iniziano per y; l'insieme delle parole che finiscono per yyy; l'insieme delle parole in cui y non appare; l'insieme delle parole in cui y appare al massimo tre volte; l'insieme delle parole che se hanno lunghezza maggiore di 10 allora non hanno y tra le lettere che vi appaiono.
5. Fissato un insieme $a$, dire quali dei seguenti insiemi costituiscono parti chiuse in $(T(a),\circ)$: l'insieme delle applicazioni (da $a$ in $a$) iniettive, l'insieme di quelle suriettive, l'insieme di quelle biettive, l'insieme di quelle non iniettive, l'insieme di quelle non suriettive, l'insieme di quelle non biettive, l'insieme di quelle costanti, l'insieme di quelle non costanti. In alcuni casi la risposta potrebbe dipendere dalla scelta di $a$.
6. Studiare le operazioni binarie qui elencate, stabilendo per ciascuna di esse se è commutativa e se è associativa, determinandone gli elementi neutri a sinistra, a destra, neutri delle strutture da esse definite
   • $\alpha\colon (a,b)\in \Z\times\Z\mapsto a+b+1\in\Z$;
   • $\beta\colon (a,b)\in \Z\times\Z\mapsto -ab\in\Z$;
   • $\gamma\colon (a,b)\in \Q\times\Q\mapsto (a+b)/2\in\Q$;
   • $\delta\colon (a,b)\in \Z\times\Z\mapsto 2ab\in\Z$;
   • $\varepsilon\colon (a,b)\in \Q\times\Q\mapsto 2ab\in\Q$;
   • $\zeta\colon (a,b)\in \N\times\N\mapsto a10^b\in\N$;
   • $\eta\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto a\cup b\cup \set 1\in\P(\Z)$;
   • $\theta\colon (a,b)\in \N\times\N\mapsto a(b^{a+b}+3ab^2)+1\in\N\quad$ (suggerimento: calcolare $1\mathbin\theta2$, $2\mathbin\theta1$, $0\mathbin\theta(1\mathbin\theta 1)$, $(0\mathbin\theta1)\mathbin\theta 1$);
   • $\iota\colon (a,b)\in \P(\Z)\times\P(\Z)\mapsto (a\cap\N)\cup b\in\P(\Z)$;
   • $\kappa\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+\alpha b,\alpha\beta)\in S$, dove $S=\Z\times\set{-1,1}$;
   • $\lambda\colon (a,b)\in\Q\times\Q\mapsto a/(|b|+1)\in\Q$.
7. Vero o falso? Per ogni insieme non vuoto $S$ ed ogni operazione binaria $*$ in $S$, …
   1. … in $S$ esiste sempre un elemento neutro a destra o un elemento neutro a sinistra;
   2. … se $*$ è commutativa tutti gli elementi neutri a destra in $(S,*)$ sono anche neutri a sinistra;
   3. … se $*$ è commutativa in $S$ esiste al massimo un elemento neutro a sinistra;
   4. … se $a$ e $b$ sono due elementi neutri a sinistra distinti in $(S,*)$, in $(S,*)$ non esistono elementi neutri a destra;
   5. … se $a$ è un elemento neutro a sinistra in $(S,*)$, nessun elemento di $S\setminus\set a$ è neutro a destra in $(S,*)$.

15 — 16/10

Discussione di molti esercizi dalle lezioni precedente. Osservazioni su possibili errori in cui si cade quando si omettono (o si usano male) i quantificatori mentre si cercano, ad esempio, elementi neutri rispetto ad una operazione binaria e si finisce per dare risposte prive di alcun senso.

Monoidi; vari esempi, tra questi: il monoide delle trasformazioni di un insieme ed il monoide delle parole su un alfabeto. Notazione per denotare monoidi con la specificazione dell'elemento neutro. Sottostrutture; sottosemigruppi e sottomonoidi. Esempi di parti chiuse di un monoide $M$ che, muniti dell'operazione indotta, non sono monoidi, sono sottomonoidi di $M$, sono monoidi ma non sottomonoidi di $M$.

In una struttura con un'operazione binaria ed elemento neutro: simmetrici destri o sinistri; simmetrici. L'eventuale elemento neutro è simmetrico di sé stesso. Elementi simmetrizzabili (anche: simmetrizzabili a sinistra o a destra). Vari esempi. Identificazione degli elementi simmetrizzabili a destra, a sinistra, simmetrizzabili nel monoide delle trasformazioni di un insieme. Gruppi (esempio: $(\Z,+)$).

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

Esercizi proposti:

1. Vero o falso? Per ogni insieme $S$ ed ogni operazione binaria $*$ in $S$, tale che $(S,*)$ abbia elemento neutro $t$ …
   1. … $t$ ammette simmetrico in $(S,*)$;
   2. … se $t$ ammette simmetrico in $(S,*)$, questo è $t$ stesso;
   3. … se $*$ è commutativa, in $(S,*)$ ogni elemento dotato di un simmetrico sinistro ha un simmetrico;
   4. … se $x$ è un elemento di $S$ che ha in $(S,*)$ due distinti simmetrici destri, allora $x$ non ha simmetrici sinistri in $(S,*)$;
   5. … se $*$ è associativa e $x$ è un elemento di $S$ che ha in $(S,*)$ due distinti simmetrici destri, allora $x$ non ha simmetrici sinistri in $(S,*)$.
2. Determinare gli elementi simmetrizzabili nei monoidi $(\N,\cdot, 1)$, $(\Z,\cdot, 1)$ e $(\Q,\cdot, 1)$.
3. Per le operazioni proposte nell'esercizio nr. 6 della lezione scorsa che abbiano elemento neutro, individuare gli elementi simmetrizzabili (anche solo a destra o a sinistra) descrivendone anche gli eventuali simmetrici (destri o sinistri).
4. Posto $S=\Z\times\Z$, studiare le strutture algebriche $(S,*)$, $(S,\bullet)$ e $(S,\diamond)$ (le operazioni sono definite avanti), stabilendo di che tipo di strutture si tratta, tra quelle già introdotte (un semigruppo?, un monoide?, un gruppo?; commutativo o no?), se (e quali) elementi neutri a destra, a sinistra, neutri hanno e, nel caso la domanda abbia senso, quali siano i loro elementi simmetrizzabili (anche solo a destra o a sinistra), identificandone i simmetrici.
   • $*\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto(a+b,\alpha\beta)\in S$
   • $\bullet\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+b,\beta)\in S$
   • $\diamond\colon \big((a,\alpha),(b,\beta)\big)\in S\times S\mapsto (a+\alpha b,\alpha\beta)\in S$.
   In ciascuna di queste strutture si stablisca poi quali tra $\Z\times\N$ e $\N\times\Z$ costituiscano parti chiuse e, per quelle che lo sono, si ripeta l'esercizio per le strutture indotte su esse.
5. Se $a$ è un insieme, stabilire quali tra i monoidi $(\P(a),\cup)$, $(\P(a),\cap)$ e $(\P(a),\ds)$ sono gruppi, o per quali scelte di $a$ lo sono.

16 — 18/10

Discussione di esercizi dalla lezione precedente.

Tavola di Cayley di un'operazione binaria. Visualizzazione di proprietà in una tavola di Cayley: commutatività, eventuali elementi neutri sinistri o destri (e quindi neutro); eventuali simmetrizzabili e loro simmetrici (anche sinistri o destri).

Terminologia: uso di "inverso" e "invertibile" (prevalentemente in notazione moltiplicativa) e di "opposto" (prevalentemente in notazione additiva) come sinonimi di "simmetrico" e, nel primo caso, di "simmetrizzabile".

Il gruppo (abeliano) $(\P(a),\ds)$ (per ogni insieme $a$). Gruppi identici (cioè con un solo elemento).

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

In una struttura algebrica con una operazione binaria: traslazioni destra e sinistra determinate da un elemento. Elementi cancellabili a sinistra o a destra, elementi cancellabili. Esplicitazione e negazione della cancellabilità. In ogni monoide, gli elementi simmetrizzabili a sinistra (rispettivamente a destra) sono tutti cancellabili a sinistra (rispettivamente a destra). Il viceversa non vale in generale (ad esempio, non vale in $(\Z,\cdot)$) ma vale nel caso dei monoidi finiti (quest'ultima cosa non è stata per ora dimostrata). Molti esempi. Nei gruppi tutti gli elementi sono cancellabili (questi contenuti sono disponibili nella prima parte di una nota sulla cancellabilità, che contiene più di quanto richiesto ai fini di questo corso; per il momento, a noi serve solo il contenuto della prima pagina).

Esercizi proposti:

1. Per un l'insieme $a=\set{0,1}$, scrivere le tavole di Cayley di $(\P(a),\cup)$, $(\P(a),\cap)$, $(\P(a),\ds)$, $(\P(a),\setminus)$ e $(T(a),\circ)$ (un aiuto: $T(a)$ ha quattro elementi).
2. Per un arbitrario insieme $a$, determinare gli elementi cancellabili in $(\P(a),\cup)$, $(\P(a),\cap)$ e $(\P(a),\ds)$.
3. Nelle strutture algebriche proposte nell'esercizio nr. 6 della lezione nr. 14 e nell'esercizio nr. 4 della lezione nr. 15, individuare gli elementi cancellabili (anche solo a destra o a sinistra).
4. Determinare gli elementi cancellabili nel monoide delle parole su un prefissato alfabeto.
5. Sia $(M,*,t)$ un monoide e sia $a$ un suo elemento. Provare che $a$ è simmetrizzabile in $(M,*,t)$ se e solo se le traslazioni destra e sinistra determinate da $a$ in $(M,*,t)$ sono suriettive. Dimostrare anche che, in questo caso, esse sono anche biettive (con quali inverse?).
6. Chissà se anche la cancellabilità può essere facilmente letta da una tavola di Cayley…
7. Sia $S=\set{t,a,b}$ un insieme di tre elementi e si consideri in $S$ l'operazione $*$ definita da questa tavola di Cayley:

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

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

17 — 20/10

Discussione di alcuni esercizi dalla lezione precedente.

Visualizzazione della cancellabilità in una tavola di Cayley.

Semigruppi cancellativi. Lo sono i gruppi, $(\N,+)$ ed anche il monoide delle parole, su un qualsiasi alfabeto.

La tavola di Cayley dei gruppi con due o con tre elementi.

Per ogni insieme $a$, il gruppo simmetrico (o gruppo delle permutazioni) su $a$: $\Sym(a)=\U(T(a))$ (le permutazioni di $a$ sono, per definizione, le trasformazioni biettive di $a$). Questo gruppo è abeliano se e solo se $a$ ha meno di tre elementi. Cenno alle permutazioni cicliche.

Sottogruppi di un gruppo. Una caratterizzazione dei sottogruppi: una parte non vuota $H$ di un gruppo ne è un sottogruppo se e solo se per ogni $x,y\in H$ il prodotto (in notazione moltiplicativa) $xy'$ appartiene ad $H$; qui $y'$ indica il simmetrico di $x$ nel gruppo (la condizione $xy'\in H$ può essere equivalentemente sostituita da $x'y\in H$). Ad esempio, per ogni intero $n$, l'insieme dei multipli di $n$ costituisce un sottogruppo di $(\Z,+)$; solo a titolo di notizia: $(\Z,+)$ non ha sottogruppi diversi da questi.

Esercizi proposti:

1. Siano $a$ un insieme, $b$ una sua parte e $x$ un suo elemento. Provare che $\P(b)$ costituisce un sottogruppo di $(\P(a),\ds)$ e $\set{\alpha\in\Sym(a)\mid \alpha(x)=x}$ costituisce un sottogruppo di $(\Sym(a),\circ)$.
2. Siano $a=\set{1,2,3,4}$ e $\sigma$ l'applicazione di $a$ in $a$ che manda 1 in 2, 2 in 3, 3 in 4 e 4 in 1. Dopo aver verificato che $\sigma^4(=\sigma\circ\sigma\circ\sigma\circ\sigma)$ coincide con $\id_a$ e di conseguenza che $\sigma$ è biettiva e $\Sigma:=\set{\id_a,\sigma,\sigma^2,\sigma^3}$ costituisce un sottogruppo di $\Sym(a)$, scrivere la tavola di Cayley di $(\Sigma,\circ)$. Confrontare questa con la tavola di Cayley di $(\P(a),\ds)$ per un insieme $a$ costituito da due elementi.

18 — 23/10

Discussione degli esercizi dalla lezione precedente.

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

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

Il principio del buon ordinamento per i naturali (ogni parte non vuota di $\N$ ha minimo; questo fatto non è stato e non sarà dimostrato). Definizione: se $n$ è un numero naturale ed $a$ è un insieme, si dice che $a$ ha $n$ elementi se e solo se esiste un'applicazione biettiva da $I_n:=\set{i\in\N^*\mid i\le n}$ ad $a$.

Esercizi proposti:

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

19 — 25/10

Discussione degli esercizi dalla lezione precedente.

Teorema: se $n$ ed $m$ sono due numeri naturali distinti, non esistono applicazioni biettive da $I_n:=\set{i\in\N^*\mid i\le n}$ a $I_m=\set{i\in\N^*\mid i\le m}$. Insiemi tra loro equipotenti ($a$ e $b$ sono equipotenti se e solo se esiste un'applicazione biettiva da $a$ a $b$; se ciò accade ne esiste anche una da $b$ ad $a$).

Cardinalità dell'unione tra un numero finito di insiemi finiti a due a due disgiunti tra loro. Assegnati insiemi finiti $a, b, c$, cardinalità di $a\times b$, di $a\cup b$, di $a\cup b \cup c$, più in generale: principio di inclusione-esclusione (con verifica limitata al caso dell'unione tra due o tre insiemi finiti). Il numero delle applicazioni e quello delle applicazioni iniettive $a\to b$. Notazione: $b^a=\Map(a,b)$. Fattoriali e fattoriali discendenti. Scelti comunque due insiemi finiti $a$ e $b$:

• esistono esattamente $|b|^{|a|}$ applicazioni da $a$ a $b$. In particolare, non ne esistono se e solo se $b=\vuoto\ne a$;
• esistono applicazioni iniettive da $a$ a $b$ se e solo se $|a|\le |b|$. Nel caso, il loro numero è $|b|!/(|b|-|a|)!$;

Esercizi proposti:

1. Verificare in dettaglio, utilizzando come aiuto un diagramma di Venn come fatto a lezione nel caso di una coppia di insiemi, la validità della formula che esprime il principio di inclusione-esclusione per una terna di insiemi finiti.
2. Siano $A$ e $B$ due insiemi finiti; supponiamo $|A|=15$ e $|B|=10$.
   1. Se $|A\cap B|=8$, quanto vale $|A\cup B|$?
   2. Se $|A\cup B|=20$, quanto vale $|A\cap B|$?
   3. Se sappiamo che $3\le |A\cap B|\lt 8$, cosa possiamo dire su $|A\cup B|$?
3. Siano dati due insiemi $a$ e $b$ tali che $|a|=6$ e $|b|=12$. Quante sono le applicazioni da $a$ a $b$? Quante tra queste sono iniettive? Quante sono costanti?
4. Siano $a=\set{n\in\N\mid n \lt 9}$, e $b=\set{5,11,33,76}$, Quante sono le applicazioni $f$ da $a$ a $b$ tali che $\forall x\in a$$(f(x)\le 30)$? Quante sono le applicazioni $g$ da $b$ ad $a$ tali che $g(5)=g(33)\ne g(11)$?
5. Quante sono le parole di lunghezza 6 che si possono ottenere utilizzando un alfabeto di 10 caratteri? Tra queste, quante sono quelle che hanno tutte le lettere in posizione dispari (la prima, la terza etc.) uguali? E quelle palindrome? E quelle in cui nessuna lettera è ripetuta? E quelle in cui non ci sono lettere consecutive ripetute?

20 — 27/10

Discussione di alcuni esercizi dalla lezione precedente.

Ancora sulla buona definizione del numero di elementi (o cardinalità) per un insieme finito $a$. Se $a$ è un insieme finito, $a$ non è equipotente ad alcuna sua parte propria (cosa che può accadere, in realtà accade sempre, per insiemi infiniti; ad esempio, $|\Z|=|\N|$).

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

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

Cenni alla comparazione tra cardinalità per insiemi infiniti, come da questa pagina. (se $a$ e $b$ sono insiemi arbitrari, $|a|=|b|$, $|a|\le|b|$ e $|a|\lt |b|$ significano, nell'ordine, che esiste un'applicazione biettiva da $a$ a $b$, che ne esiste una iniettiva, che ne esiste una iniettiva ma non ne esistono di biettive). A titolo di notizia (salvo che per i casi già verificati): $|\N^*|=|\N|=|\Z|=|\Q|=|\N\times\N|\lt|\R|=|\R\times\R|=|\P(\N)|$; per ogni $a$ si ha $|a|\lt|\P(a)|$.

Come applicazioni di uno dei risultati precedenti: (1) se $x$ è un elemento di un monoide finito, se $x$ è cancellabile a sinistra (risp. destra) in $x$ allora $x$ è simmetrizzabile a destra (risp. sinistra) in $M$; (2) se $S$ un semigruppo finito ed $S$ ha un elemento cancellabile, allora $S$ è un monoide ed ogni suo elemento cancellabile è simmetrizzabile (si vedano le note sulla cancellabilità, dove è dimostrato anche qualcosa in più, non richiesto ai fini del corso).

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

Osservazione ed un esempio: codifica delle parti di un insieme finito in termini delle corrispondenti funzioni caratteristiche e, quindi, per un insieme finito, di "stringhe di 0 e 1" (cioè parole sull'alfabeto ${0,1}$) di lunghezza la cardinalità dell'insieme.

Osservazione: se $f$ è un'applicazione biettiva, allora anche $\vecf$ è biettiva e la sua inversa è $(f^{-1})\vec{}3$. Di conseguenza: se $a$ e $b$ sono insiemi equipotenti, anche $\P(a)$ e $\P(b)$ e, per ogni numero naturale $k$, $\P_k(a)$ e $\P_k(b)$ sono equipotenti. Definizione dei coefficienti binomiali (si vedano le note dedicate).

Esercizi proposti:

1. Vero o falso? Siano $a$ e $b$ due insiemi finiti. Allora, necessariamente:
   1. … se $|b|\le |a|$, esistono applicazioni suriettive da $a$ a $b$;
   2. … se $0\lt |b|\le |a|$, esistono applicazioni suriettive da $a$ a $b$;
   3. … se $|a|=|b|$ ogni applicazione suriettiva da $a$ a $b$ è iniettiva;
   4. … esiste un sottoinsieme proprio di $b$ equipotente ad $a$ se e solo se $|a|\lt |b|$;
2. Siano $a$, $b$ e $c$ insiemi. Se $|a|=8$, $|b|=10$ e $|c|=2$, quante sono le applicazioni suriettive da $a$ a $b$? E quante da $b$ a $c$?
3. Sia $S$ un insieme di cardinalità $3$. Quante sono le operazioni binarie in $S$? E, in generale, se $S$ ha un'arbitraria cardinalità finita $n$?
4. Siano $a$ e $b$ insiemi tali che $|a|=5$ e $|b|=7$. Quante sono le corrispondenze da $a$ a $b$? E, in generale, per arbitrari insiemi finiti $a$ e $b$, come possiamo esprimere $|\Corr(a,b)|$ in termini di $|a|$ e $|b|$?
5. Posto $a=\set{1,2,3}$, elencare gli elementi di $\P(a)$ e le sei (sei?) permutazioni di $a$. Scrivere la tavola di Cayley del gruppo simmetrico $\Sym(a)$.
6. Siano $S$ un insieme e $T$ una sua parte. Quale parte di $S$ ha per funzione caratteristica l'applicazione $x\in S\mapsto 1-\chi_{T,S}(x)\in \set{0,1}$?
7. Posto $a=\set{n\in\N^*\mid n\le 9}$, rappresentare, nel senso spiegato a lezione, le parti $\vuoto$, $\set 1$ e $\set{2,3,5}$ di $a$ come "stringhe di 0 e 1".
8. Calcolare $\binom {8763} 0$, $\binom {8763} 1$ e $\binom {8763} {100000000}$.

21 — 30/10

Discussione di alcuni esercizi dalla lezione precedente.

Proprietà elementari dei coefficienti binomiali: per ogni $n,k\in\N$, $\binom n0=\binom nn=1$, $\binom n1=n$, $\binom nk=0$, per ogni intero $k>n$. Per ogni $n\in\N$, $\sum_{k=0}^n\binom nk=2^n$. Proprietà di simmetria dei coefficienti binomiali: se $k,n\in\N$ e $k\le n$ allora $\binom nk=\binom n{n-k}$. Questo argomento è anche esposto in una nota, Coefficienti Binomiali, il cui stile espositivo, però, non coincide del tutto, (particolarmente per quanto seguirà) con quello usato a lezione.

Il principio di induzione. Nella prima forma: se $\phi$ è un predicato unario, $b\in\N$ e $N_b=\set{n\in\N\mid b\le n}$, se valgono $\phi(b)$ e, per ogni $n\in N_b$, l'implicazione $\phi(n)\implica \phi(n+1)$, allora vale $\phi(n)$ per ogni $n\in N_b$. Come esempi di applicazione: per ogni $n\in\N^*$, $1+2+\cdots+n=n(n+1)/2$; dimostrazione del fatto che, se $x$ è un elemento del semigruppo $(S,\cdot)$, per ogni $n,m\in\N^*$ si ha $x^{n+m}=x^n x^m$. Seconda forma del principio di induzione (o principio di induzione completa): offre una versione alternativa (e non consigliata) del metodo di dimostrazione per controesempio minimo.

Osservazione: se $f\colon a\to b$ è un'applicazione biettiva $c\sseq a$, l'applicazione $x\in c\mapsto f(x)\in \vecf(c)$ (ridotta all'immagine della restrizione di $f$ a $c$) è biettiva. Per ogni insieme (non vuoto) $S$ ed ogni $a\in S$, biezione tra $\set{x\in \P(S)\mid a\in S}$ e $\P(S\setminus\set a)$. Da ciò, lemma: per ogni insieme finito (non vuoto) $S$ ed ogni $a\in S$, $|\P(S)|=2|\P(S\setminus\set a)|$; inoltre, per ogni $k\in\N$, $|\P_{k+1}(S)|=|\P_{k+1}(S\setminus\set a)|+|\P_k(S\setminus\set a)|$. Dalla seconda parte segue la formula ricorsiva per i coefficienti binomiali: per ogni $k,n\in \N$, $\binom{n+1}{k+1}=\binom nk + \binom n{k+1}$.

Esercizi proposti:

1. Usando il principo di induzione, provare che per ogni $n\in\N^*$ si ha che $1+3+\cdots+(2n-1)$ (la somma dei primi $n$ interi positivi dispari) è uguale a $n^2$.
2. Dimostrare, per induzione, la formula $x^{nm}=(x^n)^m$ valida per ogni elemento $x$ di un semigruppo ed ogni $n,m\in\N^*$. Fatto questo, completare le dimostrazioni delle formule, enunciate nella lezione nr. 18, sulle potenze in monoidi e gruppi.
3. Posto $a=\set{1,2,3,4}$, scrivere esplicitamente i 16 elementi di $\P(a)$ (come facciamo a sapere che sono $16$?), raggruppandoli per cardinalità. Quanto vale $\binom 42$?
4. Dando per noto che $\binom{44}{20}=1761039350070$, calcolare $\binom{44}{24}$.
5. Ricordando quanto valgono $\binom 60$ e $\binom 61$ (e quindi $\binom 66$ e $\binom 65$) e dando per noto che $\binom 62=15$, calcolare prima $\binom 64$ e, come conseguenza, $\binom 63$. Utilizzare solo quanto visto nella lezione di oggi.
6. Sviluppando il ragionamento svolto (?) per l'esercizio precedente, calcolare $\binom 52$.

22 — 3/11

Discussione di alcuni esercizi dalla lezione precedente.

Il triangolo di Tartaglia-Pascal e sue proprietà (simmetria e somma delle righe). Dimostrazione per induzione delle formula $|\P(S)|=2^{|S|}$ per gli insiemi finiti $S$. Formula esplicita per i coefficienti binomiali (con dimostrazione svolta per induzione, come in questa pagina).

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

Isomorfismi e tavole di Cayley. Strutture isomorfe tra loro. Centralità della nozione di isomorfismo in algebra.

Esempi di isomorfismi. Tra questi la funzione esponenziale come isomorfismo dal gruppo additivo dei numeri reali a quello moltiplicativo dei reali positivi.

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

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

Esercizi proposti:

1. Utilizzando la porzione del triangolo di Tartaglia-Pascal disponibile in questo sito, calcolare $\binom {13}5$ e poi $\binom {14}5$.
2. Sia $S$ un insieme di cardinalità 11. Quante sono le parti di $S$ di cardinalità 4? E quante quelle di cardinalità 7? Quante sono le 5-parti di $\P(S)$?
3. Posto $S=\set{1,2,3,4,5,6}$, calcolare in numero delle parti di $S$ contenenti $\set{2,6}$. Quante di queste hanno cardinalità 5?
4. Posto $A=\set{n\in\N\mid n\lt 9}$ e $B=\set{2,5}$, esprimere (utilizzando coefficienti binomiali; non calcolare!) le cardinalità degli insiemi $U:=\set{X\in\P(A)\mid 0\notin X\land|X|=6}$, $V:=\set{X\in\P(A)\mid 0\in X\land |X|=6}$, $W=\set{X\in\P(A)\mid B\sseq X\land |X|=6}$ e $Z:=\set{X\in\P(A)\mid (3\in X\implica B\subseteq X) \land |X|=6}$.
5. Verificare che le seguenti applicazioni sono omomorfismi: $n\in(\Z,\cdot)\mapsto |n|\in (\N,\cdot)$, $n\in(\Z,+)\mapsto -n\in (\Z,+)$; per ogni gruppo $G$ ed ogni $a\in G$, l'applicazione $n\in(\Z,+)\mapsto a^n\in G$, se poi $G$ è abeliano, generalizzando l'esempio precedente, $x\in G\mapsto x^{-1}\in G$. Cosa sappiamo dire su $n\in(\Z,\cdot)\mapsto -n\in (\Z,\cdot)$?
6. Sia $*$ l'operazione binaria in $S:=\Z\times\Z$ definita da $(a,\alpha)*(b,\beta)=(a+\alpha b,\alpha\beta)$ per ogni $a,b,\alpha,\beta\in\Z$, già discussa in un esercizio della lezione 15. Per ciascuna delle applicazioni $n\in\Z\mapsto (n,1)\in S$ e $n\in\Z\mapsto (0,n)\in S$ decidere se di tratta di un omomorfismo da $(\Z,+)$, o da $(\Z,\cdot)$, a $(S,*)$. L'applicazione $(a,\alpha)\in S\mapsto \alpha\in\Z$ è un omomorfismo da $(S,*)$ a $(\Z,+)$? Ed a $(\Z,\cdot)$?
7. A lezione non abbiamo verificato che gli omomorfismi suriettivi conservano l'associatività ed i simmetrici. Farlo.
8. Verificare che, per ogni insieme $a$ l'applicazione $x\in \P(a)\mapsto a\setminus x\in \P(a)$ è un isomorfismo da $(\P(a),\cap)$ a $(\P(a),\cup)$ (e viceversa) ed usare questa per spiegarsi le coincidenze tra le proprietà algebriche dell'intersezione e dell'unione binaria.
9. Sia $(S,*)$ un semigruppo. L'applicazione $a\in S\mapsto \sigma_a \in T(S)$ è un omomorfismo? E se $(S,*)$ non è un semigruppo? ($T(S)$ è il monoide delle trasformazioni di $S$, $\sigma_a$ la traslazione sinistra definita da $a$ in $(S,*)$.)
10. Utilizzando le considerazioni fatte sulle tavole di Cayley dei gruppi di cardinalità 2 o 3 fatte nella lezione 17 e l'esercizio 2 della stessa lezione, provare che due qualsiasi gruppi, entrambi di cardinalità 2 o entrambi di cardinalità 3, sono necessariamente isomorfi tra loro, ma esistono gruppi di cardinalità 4 non isomorfi tra loro. Scrivere esplicitamente un isomorfismo da $\mathcal (U(\Z), \cdot)$ a $(\P(\set 0),\ds)$.
11. Vero o falso? Supponendo che esista un omomorfismo suriettivo da una struttura $(S,*)$ ad una struttura $(T,\bullet)$, dove $*$ e $\bullet$ sono operazioni binarie, …
    • se $(S,*)$ è un semigruppo, $(T,\bullet)$ è un semigruppo;
    • se $(T,\bullet)$ è un semigruppo, $(S,*)$ è un semigruppo;
    • se $(S,*)$ è un monoide, $(T,\bullet)$ è un monoide;
    • se $(T,\bullet)$ è un monoide, $(S,*)$ è un monoide;
    • se $(S,*)$ è un gruppo, $(T,\bullet)$ è un gruppo;
    • se $(T,\bullet)$ è un gruppo, $(S,*)$ è un gruppo.

23 — 20/11

Discussione di alcuni esercizi dalla lezione precedente.

Partizioni di un insieme (si vedano le note su partizioni ed equivalenze). Definizione, caratterizzazione, esempi; partizioni banali. Proiezione di un insieme su una sua partizione. Se $F$ è una partizione di un insieme finito $a$, allora $|a|=\sum_{b\in F}|b|$.

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

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

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

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

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

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

Esercizi proposti:

1. Sia $a=\set{n\in\N\mid n\lt 10}$. Stabilire quali tra questi sono e quali non sono partizioni di $a$: $a$, $b=\set a$, $c=\set{\vuoto,\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $d=\set{\set{1,3,5,7,9},\set{0,2,4},\set{6,8}}$, $e=\set{\set{1,2,3,4,5,7,9},\set{0,2},\set{6,8}}$.
2. Trovare quattro partizioni distinte dell'insieme $\set{1,2,3,4}$.
3. Trovare tre partizioni non banali dell'insieme $\Z$.
4. Svolgere gli esercizi 1 (esclusi i punti f e g) e 2 (solo i punti d ed e) da relazioni binarie, limitatamente alle proprietà di essere, riflessiva, simmetrica, transitiva, di equivalenza.
5. Utilizzando quanto detto a lezione (e riportato in questo registro) sulla semplificazione nella verifica della transitività di una relazione binaria, trovare tutte le relazioni binarie non transitive sull'insieme $\set{0,1}$.
6. Sia $a$ un insieme. Descrivere le partizioni $F$ di $a$ tali che $|F|=2$. Calcolarne il numero se $|a|=10$.
7. Sia $a$ un insieme di cardinalità 7. Calcolare il numero della partizioni di $a$ in cui appaia un blocco di cardinalità 4.
8. Sia $f$ l'applicazione da $A=\set{0,1,2,3,4,5,6,7}$ a $\Z$ definita da $f(0)=10$, $f(1)=f(2)=50$ e $f(a)=a^2+1$ per ogni altro elemento $a$ di $A$. Detto $\rho$ il nucleo di equivalenza di $f$, descrivere $A/\rho$, elencando i suoi elementi e gli elementi di ciascuna delle classi modulo $\rho$. Quanti elementi ha $A/\rho$?
9. Siano $v\colon n\in\Z\mapsto |n|\in\N$ e $w\colon n\in\Z\mapsto n^2\in\Z$. Descriverne i nuclei di equivalenza e, rispetto a ciascuno di essi, la classe di $-5$.
10. Siano $a$ un insieme finito e $k\colon \P(a)\to\N$ l'applicazione che ad ogni parte $x$ di $a$ associa la sua cardinalità. Descrivere il nucleo di equivalenza $\tau$ di $k$ e l'insieme quoziente $Q:=\P(a)/\tau$. Quanti elementi ha $Q$?
11. Provare che la relazione binaria $\sigma$ definita in $\R$ ponendo, per ogni $x,y\in\R$, $x\mathrel\sigma y$ se e solo $x^4+(3-\log (|x|+1))^3+1=y^4+(3-\log(|y|+1))^3+1$ è di equivalenza.
12. Detto $\rho$ il nucleo di equivalenza dell'applicazione $X\in\P(\Z)\mapsto X\cap\N\in\P(\N)$, descrivere $[\set{-1}]_\rho$ e $[\vuoto]_\rho$.

24 — 22/11

Discussione di alcuni esercizi dalla lezione precedente.

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

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

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

Anelli. Definizione ed esempi (tra questi, gli anelli su $\Z$, $2\Z$, $\Q$, $\R$ con le usuali operazioni di addizione e moltiplicazione, l'anello delle parti di un insieme, con le operazioni di differenza simmetrica ed intersezione); anelli commutativi, anelli unitari. Sottoanelli, sottoanelli unitari; omomorfismi di anelli, omomorfismi di anelli unitari. Lo zero $0_R$ e (se esiste) l'unità $1_R$ di un anello. Terminologia per gli anelli: opposti (cioè simmetrici rispetto all'operazione additiva) e inversi (cioè eventuali simmetrici rispetto all'operazione moltiplicativa).

Esercizi proposti:

1. Svolgere le parti (i) e (ii) dell'esercizio 3 dal compito del 18 giugno 2019.
2. Siano $S=\set{n\in\N\mid n\lt 15}$, $T=\set{n\in\N\mid n\lt 6}$ e $\theta$ l'applicazione $X\in\P(S)\mapsto |X|\in\N$. Detto $\rho$ il nucleo di equivalenza di $\theta$, descrivere $[T]_\rho$ e $|[T]_\rho|$. Trovare, se possibile, una parte $V$ di $S$ tale che $[V]_\rho\ne[T]_\rho$ ma $|[V]_\rho|=|[T]_\rho|$.
3. Descrivere il nucleo di equivalenza dell'applicazione $f\colon n\in\Z\mapsto (-1)^n\in\Z$ e, rispetto ad esso, calcolare la classe di equivalenza di $13765$.
4. Sia $a=\set{0,1,2,3,4,5,6}$. Stabilire quante sono, e descrivere esplicitamente, …
   • … le relazioni di equivalenza $\sim$ in $a$ tali che $1\sim 3\not\sim 2\sim 4$ e $5\in[0]_\sim=[6]_\sim$
   • … le relazioni di equivalenza $\rho$ in $a$ tali che $0\mathrel\rho 3$, $\set{2,5}\subseteq [3]_\rho$ e $6\in[4]_\rho\iff 1\mathrel\rho 6$.
5. Sia $a$ un insieme tale che $|a|=21$. Quante sono le relazioni di equivalenza $\rho$ in $a$ tali che $a/\rho$ abbia esattamente due elementi?
6. Sia $f\colon a\to b$ un'applicazione e sia $\sim$ il suo nucleo di equivalenza. Supponiamo di non conoscere $f$, ma di conoscere $|a|$ e $|b|$. Possiamo stabilire quanto vale $|a/{\sim}|$? Se sappiamo che $f$ è iniettiva, possiamo stabilire quanto vale $|a/{\sim}|$? Se sappiamo che $f$ è suriettiva, possiamo stabilire quanto vale $|a/{\sim}|$?
7. Posto $a=\set{1,2,3}$, e detta $F$ la partizione $\set{\set 1,\set{2,3}}$ di $a$, stabilire quante sono le applicazioni $f\colon a\to a$ tali che $F=a/\rho$, dove $\rho$ è il nucleo di equivalenza di $f$.
8. Siano $(R,+,\cdot)$ e $(S,\oplus,\odot)$ due anelli. Nel prodotto cartesiano $C=R\times S$ definiamo due operazioni binarie (che continuiamo a indicare con $+$ e $\cdot$) ponendo, per ogni $a,b\in R$ e $u,v\in S$, $(a,u)+(b,v)=(a+b,u\oplus v)$ e $(a,u)\cdot(b,v)=(a\cdot b,u\odot v)$. Provare che $C$, munito di queste due operazioni, è un anello, che questo anello è commutativo se e solo se lo sono sia $R$ che $S$ ed è unitario se e solo se lo sono sia $R$ che $S$. Questo anello si chiama anello prodotto diretto di $R$ per $S$.
9. Nell'anello prodotto diretto $\Z\times\Z$, definito come all'esercizio precedente, verificare che $\set{0}\times \Z$ è un sottoanello di $\Z\times\Z$. Ne è un sottoanello unitario? Che tipo di anello è $\set{0}\times \Z$ (munito delle operazioni indotte da quelle di $\Z\times\Z$)? Per caso è isomorfo ad un anello che già conosciamo? Cambia qualcosa se si considera $\set{1}\times \Z$ al posto di $\set{0}\times \Z$?
10. L'insieme delle parti finite di $\N$ costituisce un sottoanello di $\P(\N)$? Come anello, è unitario?

25 — 24/11

Discussione di alcuni esercizi dalla lezione precedente. Esempio: l'anello prodotto diretto tra due anelli.

Alcune regole elementari di calcolo in un anello $R$: per ogni $a$, $b$ in $R$, $a0_R=0_R=0_Ra$, e $a(-b)=-(ab)=(-a)b$; notazione per la differenza: $a-b=a+(-b)$; distributività della moltiplicazione rispetto all'operazione di differenza così definita; se $R$ è unitario, per ogni $n\in\Z$ si ha $(n1_R)a=na$.

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

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

Leggere l'avviso riportato pagina principale del corso, a proposito delle lezioni previste per lunedì 27 e mercoledì 29.

Esercizi proposti:

1. Verificare in dettaglio, usando il principio di induzione per il caso $n\ge 0$, che se $a$ è un elemento di un anello unitario $R$ e $n\in\Z$, allora $na=(n 1_R)a$.
2. Verificare che, per ogni insieme $a$, nell'anello delle parti di $a$ ogni elemento diverso dall'unità $a$ è un divisore dello zero.
3. Nell'anello prodotto diretto $\Z\times\Z$, definito come nell'esercizio 9 della lezione precedente, si decida quali tra questi elementi sono divisori dello zero, quali cancellabili e quali invertibili: $(1,1)$, $(7,-3)$, $(0,2)$ $(1,-1)$. Fatto questo, provare a descrivere l'insieme dei divisori dello zero in $\Z\times\Z$.
4. Sia $a$ un elemento invertibile in un anello unitario $R$. È possibile che $a$ sia un divisore dello zero in $R$?
5. Sia $T=\Z\times\Z\times\Z$ l'insieme delle terne ordinate di numeri interi. In $T$ definiamo le operazioni binarie $\oplus$ e $*$ ponendo, per ogni $a,b,c$, $u,v,w\in\Z$, $(a,b,c)\oplus(u,v,w)=(a+u,b+v,c+w)$, e $(a,b,c)*(u,v,w)=(au,av+bw,cw)$. Verificare che $(T,\oplus,*)$ è un anello, decidere se è commutativo e se è unitario. Stabilire anche se $(1,1,0)$ è un divisore dello zero (destro? sinistro?) in $R$. Nel caso in cui $R$ sia unitario, determinarne gli elementi invertibili.
6. Provare (ammesso che sia vero) quanto segue: se $a$ e $b$ sono elementi di un anello $R$, in $R$ si ha $(a+b)^2=a^2+2ab+b^2$ se e solo se $ab=ba$.

28 — 1/12

Discussione di pochi esercizi dalla lezione precedente.

Ancora sulla divisibilità: siano $M$ un monoide commutativo e $a\in M$; allora, per ogni $u\in\U(M)$, $a$ e $au$ sono associati; se $a$ è cancellabile vale anche il viceversa: gli elementi associati ad $a$ in $M$ sono tutti e soli quelli della forma $au$ per un opportuno $u\in\U(M)$. Esempio: associati in $\N$ e in $\Z$ rispetto alla moltiplicazione.

Divisori banali di un elemento $a$: sono gli invertibili e gli associati ad $a$. Divisori propri (sono i divisori non associati). Elementi irriducibili (cioè non invertibili e privi di divisori non banali). In $(\N,\cdot)$ ed in $(\Z,\cdot)$ gli elementi irriducibili sono i consueti numeri primi.

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

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

Estensione dell'algoritmo euclideo e prima versione del teorema di Bézout (vedi oltre; la dimostrazione fornita è quella, costruttiva, data dalla validità dell'algoritmo euclideo esteso, non quella nel libro di testo).

Lemma di Euclide (come conseguenza del teorema di Bézout): siano $a,b,c\in\Z$; se $a$ e $b$ sono coprimi e $a$ divide $bc$, allora $a$ divide $c$. Teorema fondamentale dell'aritmetica (esistenza ed essenziale unicità delle fattorizzazioni in prodotti di primi per numeri interi positivi diversi da $1$, per interi di valore assoluto maggiore di $1$).

Fattorizzazioni (in prodotto di irriducibili) "essenzialmente uguali" in monoidi commutativi. Monoidi fattoriali (cioè: monoidi cancellativi (ovvero: ad elementi tutti cancellabili) in cui ogni elemento non invertibile è prodotto di irriducibili e lo è in modo essenzialmente unico). Anelli fattoriali (domini di integrità unitari in cui gli elementi non nulli costituiscono, rispetto alla moltiplicazione dell'anello, un monoide fattoriale). Dunque, il teorema fondamentale dell'aritmetica si può anche enunciare dicendo che sono fattoriali il monoide $(\N^*,\cdot)$ e l'anello degli interi.

Esercizi proposti:

1. Sia $(M,*)$ un monoide commutativo. Provare che la relazione "essere elementi associati" in $M$ è compatibile con $*$.
2. Assegnato un arbitrario insieme $a$, nel monoide $(\P(a),\cap,a)$ descrivere gli elementi associati ad un arbitrario elemento $x$.
3. Quali sono gli elementi irriducibili nel monoide $(\N,+,0)$? $(\N,+,0)$ è un monoide fattoriale?
4. Assegnato un insieme finito $S$, quali sono gli elementi irriducibili in $(\P(S),\cup,\vuoto)$? $(\P(S),\cup)$ è un monoide fattoriale?
5. In $\Z$, scrivere tutte le fattorizzazioni di 12 in prodotto di primi.
6. Utilizzando l'algoritmo euclideo trovare in $\Z$ un MDC $d$ tra $125$ e $57$ e poi scrivere $d$ come combinazione lineare tra questi due numeri. Ripetere l'esercizio partendo da $125$ e $55$ (e, volendo, farlo ancora, usando altre coppie di numeri interi scelti a caso).
7. Svolgere gli esercizi da 5 ad 8 e 11 da Tautologie, insiemi, aritmetica.

29 — 4/12

Descrizione dei divisori di un intero positivo a partire dalla sua decomposizione in prodotto di potenze di primi distinti. Analoga descrizione di MCD e mcm tra due numeri naturali. Estensione al caso degli interi e dei monoidi fattoriali. Se $d$ ed $m$ sono, nell'ordine, un MCD ed un mcm tra due elementi $a$ e $b$ di un monoide commutativo fattoriale, $ab$ è associato a $dm$.

Osservazione: se $n$ è un numero naturale composto (cioè maggiore di $1$ e non primo), e $p$ è il suo minimo divisore primo positivo, allora $p\le\sqrt n$.

Equazioni diofantee e ulteriori versioni del teorema di Bézout: se $a$ e $b$ sono numeri interi e $d$ è un MCD tra essi,

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

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

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

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

Equazioni della forma $AX=C$ in un arbitrario anello commutativo unitario: discussione sui possibili insiemi di soluzioni nei casi in cui: $A$ è invertibile; $A$ è cancellabile; $A$ è un divisore dello zero. Di conseguenza: l'insieme delle soluzioni di un'equazione congruenziale $(*)$: $ax\equiv_m c$ (dove $a,c,m\in\Z$ e $m\ne 0$; d'ora in avanti queste notazioni restano fissate) è una classe di resto modulo $m$ se e solo se $a$ ed $m$ sono coprimi (in questo caso noi diciamo che $(*)$ è ridotta).

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

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

Come ovvio, le osservazioni (ii) e (iii) vengono usate per dividere gli interi $a$ e $c$ (e, nel caso di (ii) anche $m$) per loro divisori comuni. Alcuni esempi.

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

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

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

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

Esercizi proposti:

1. Nel granducato di Strampalia non circolano monete e la valuta locale, il tallero strampalese, viene emesso solo in due tagli: la banconota da 15 talleri e quella da 33 talleri. Usando il teorema di Bézout, spiegare quali pagamenti in talleri strampalesi possono essere effettuati in contanti (è ammessa la possibilità di pagare ricevendo un resto).
2. Svolgere gli esercizi 9 e 10 da Tautologie, insiemi, aritmetica (la scrittura $ax\equiv c\pmod m$ sta per $ax\equiv_m c$).
3. Delle equazioni congruenziali che seguono, dire quali hanno lo stesso insieme di soluzioni di $18x\equiv_{21}9$ (non calcolare le soluzioni):
   $6x\equiv_{21}3$, $6x\equiv_{7}3$, $2x\equiv_{7}1$, $x\equiv_{21}4x+9$, $60x\equiv_{7}30$, $60x\equiv_{70}30$, $54x\equiv_{21}27$, $54x\equiv_{63}27$, $-3x\equiv_{21}9$, $3x\equiv_{21}-9$, $x\equiv_{7}-3$, $-3x\equiv_{21}28$.
4. Trovare le soluzioni dell'equazione congruenziale $87x+32\equiv_{100} x+4$.
5. Usando l'algoritmo euclideo esteso, trovare tutte le soluzioni delle equazioni diofantee $14x+6y=1$, $14x+6y=4$, $140x+60y=20$.
6. Dando per nota l'uguaglianza $3=117\cdot 13+66(-23)$, trovare gli insiemi delle soluzioni delle equazioni congruenziali $66 x\equiv_{117}10$, $660 x\equiv_{1170}90$ e $1170 x\equiv_{660}90$.
7. Trovare l'insieme delle (cioè: di tutte le) soluzioni delle equazioni congruenziali: $2000000055x\equiv_{100} 11$; $2000000055x\equiv_{100} 15$; $100x\equiv_{55} 15$; $300x\equiv_{55} 45$; $80x+2 \equiv_{120} 6x+27$; $80x+1 \equiv_{120} 6x+27$.
8. Autoassegnarsi e risolvere un gran numero di equazioni congruenziali a caso.
9. Si determinino tutti gli interi $u$ tali che $20(u-1)\equiv_{28}4(u-2)$ e tutti gli interi $v$ tali che $20(v-1)\equiv_{28}4v-2$.
10. In $\Z_{48}$ si determini, ove possibile, l'inverso di: $[7]_{48}$, $[9]_{48}$, $[11]_{48}$, $[-13]_{48}$, $[47]_{48}$. Capire perché c'è davvero bisogno di far calcoli in una sola occasione.

30 — 6/12

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

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

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

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

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

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

Come da avviso nella pagina principale del corso, sabato 9, nel canale teams del corso, a partire dalle ore 9, si terrà una riunione dedicata allo svolgimento di esercizi.

Esercizi proposti:

1. Calcolare il periodo di $[7]_{25}$ in $\U(\Z_{25})$ e quindi $7^{193569265764322974}\modbin 25$.
2. Esercizi nr. 4 dal compito del 9 settembre 2022, nr. 2 dal compito del 10 febbraio 2023, nr. 4 dal compito del 2 marzo 2023, nr. 4 dal compito del 16 giugno 2023 (viene spesso utilizzata la notazione $\bar n$ per indicare la classe di resto di un intero $n$ rispetto ad un modulo specificato a parte nel testo dell'esercizio).
3. Completare gli esercizi 1 e 2 da relazioni binarie (per "ordinamento" si intende "relazione d'ordine stretto o largo") e, dallo stesso file, svolgere l'esercizio 6 sino alla prima occorrenza della parola 'reticolo' (esclusa).
4. Verificare in dettaglio che la relazione binaria $\rho$ sull'insieme $a=\Z\cup\set h$ (dove $h\notin\Z$) discussa a lezione e definita da $\forall x,y\in a$$(x\mathrel\rho y\iff{}$$ ((x,y\in\Z \land x\le y) \lor (x=y=h))$ è effettivamente d'ordine.
5. Svolgere i punti da (i) a (v) dell'esercizio 6 dal compito del 16 gennaio 2019.
6. Siano $\rho$ e $\sigma$ le relazioni binarie in $\Z$ definite ponendo, per ogni $a,b\in\Z$: $a\mathrel\rho b$ se e solo se $a^2+2\le b^2+2$ e $a\mathrel\sigma b$ se e solo se $a=b$ oppure $a^2+a+1\lt b^2+b+1$. Di ciascuna delle due decidere se è una relazione d'ordine.
7. La relazione binaria $\tau$ definita in $\N$ ponendo, per ogni $a,b\in\N$, $a\mathrel\tau b$ se e solo se $b-a\in\N\setminus\set 1$ è d'ordine?
8. Siano $A=\set{0,1,2,3}$ e $\rho$ la relazione binaria definita in $\P(A)$ ponendo, per ogni $x,y\in\P(A)$, $x\mathrel\rho y$ se e solo se $x=y \lor |x|\lt|y|$. Provare che $\rho$ è una relazione d'ordine, decidere se è totale e determinare in $(\P(A),\rho)$ gli elementi minimo, massimo, minimali e massimali.
9. Costruire un esempio di insieme ordinato con esattamente due elementi minimali.
10. Esiste in $\P(\N)$ una parte infinita che sia totalmente ordinata per inclusione (cioè dall'ordinamento indotto dall'inclusione in $\P(\N)$)?
11. In ciascuno dei seguenti insiemi, ordinati dalla relazione di inclusione, determinare gli eventuali elementi minimali, massimali, minimo, massimo: $\P(\Z)$, $\Pf(\Z)$ (l'insieme delle parti finite di $\Z$), $\P(\Z)\setminus\Pf(\Z)$ (l'insieme delle parti infinite di $\Z$), $\P(\Z)\setminus\P(\N)$, $\P_7(\Z)$, $\P_4(\Z)\cup\P_9(\Z)$, $\set{\set{1,2,3}, \set{4},\set{n\in\Z\mid n>1}}$. Fare lo stesso per gli insiemi $\set{x\in\Q\mid 0\lt x \le 3}$ e $\set{x\in\Q\mid 0\lt x \le\sqrt 2}$ ordinati dall'ordinamento indotto da quello usuale di $\R$.

31 — 11/12

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

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

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

Minoranti e (dualmente) maggioranti di una parte $T$ di un insieme ordinato $(S,\rho)$. Notazione: indichiamo gli insiemi da essi formati come $T^{\downarrow_{(S,\rho)}}$ e $T^{\uparrow_{(S,\rho)}}$ rispettivamente. Alcuni esempi; tra questi: se $T=\vuoto$, $T^{\downarrow_{(S,\rho)}}=T^{\uparrow_{(S,\rho)}}= S$; se $X$ è un insieme di numeri naturali, i minoranti ed i maggioranti di $X$ in $(\N,|)$ sono, rispettivamente, gli insiemi dei divisori comuni e dei multipli comuni agli elementi di $X$; se $S$ è un insieme e $T\subseteq\P(S)$, i minoranti ed i maggioranti di $T$ in $(\P(S),\subseteq)$ sono, rispettivamente, i sottoinsiemi di $\bigcap T$ (o di $S$ se $T=\vuoto$) ed i sottoinsiemi di $S$ contenenti $\bigcup T$. Per arbitrari parti $X$ e $Y$ di un insieme ordinato si ha $(X\cup Y)^{\downarrow}=X^{\downarrow}\cap Y^{\downarrow}$ e $(X\cup Y)^{\uparrow}=X^{\uparrow}\cap Y^{\uparrow}$.

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

Esercizi proposti:

1. Disegnare un diagramma di Hasse dell'insieme $\set{n\in\N\mid n\lt 10}$ ordinato per divisibilità in $\N$ e decidere se questo insieme ordinato è un reticolo.
2. Per ogni $n\in\set{8,12,18,30,31,2^{10}}$ disegnare un diagramma di Hasse dell'insieme $D_n$ dei divisori (in $(\N,\cdot)$) di $n$, ordinato per divisibilità in $\N$, e decidere se $(D_n,\mid)$ è o non è un reticolo. Trovare tra questi insiemi ordinati, quali sono isomorfi tra loro.
3. Svolgere il punto $(i)$ dell'esercizio 4 del compito del 6 novembre 2023 e decidere se $(S,\sseq)$ è un reticolo.
4. Degli insiemi ordinati discussi negli esercizi della lezione precedente, decidere se sono o non sono reticoli.
5. Svolgere l'esercizio 5 dal compito dell'8 marzo 2019, fermandosi dopo aver stabilito, al punto (iv), se $(T,\rho)$ è un reticolo. Ampliare l'esercizio dimostrando che $\rho$ è una relazione d'ordine in $S$ e decidendo se $(S,\rho)$ è o non è un reticolo.
6. Svolgere l'esercizio 3 dal compito del primo ottobre 2019.

32 — 13/12

Parte del contenuto della lezione di oggi e della prossima è discusso nelle note sulle strutture booleane.

Diagrammi di Hasse di un insieme ordinato e del suo duale.

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

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

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

Siano $(S,\rho)$ un insieme ordinato e $X,Y\sseq S$. Allora, in $(S,\rho)$, si ha $(X\cup Y)^{\downarrow}=X^{\downarrow}\cap Y^{\downarrow}$, supposti poi esistenti $x=\inf_{(S,\rho)}X$ e $y=\inf_{(S,\rho)}Y$, vale $X^{\downarrow}=\set{x}^{\downarrow}=\set{a\in S\mid a\mathrel\rho x}$, dunque $(X\cup Y)^{\downarrow}=\set{x,y}^{\downarrow}=\set{a\in S\mid a\mathrel\rho x\land a\mathrel\rho y}$ (valgono anche gli enunciati duali). Pertanto, se $(S,\rho)$ è un reticolo e $X$ e $Y$ sono sue parti dotate di estremo inferiore (risp. superiore), anche $X\cup Y$ ha estremo inferiore (risp. superiore). Di conseguenza: tutte le parti finite e non vuote di un (arbitrario) reticolo hanno estremo inferiore ed estremo superiore, dunque: i reticoli finiti non vuoti sono completi.

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

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

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

Sottoreticoli (cioè parti non vuote di un reticolo chiuse rispetto alle operazioni reticolari). Esempi di sottoreticoli; lo sono tutti gli intervalli chiusi e tutti i sottoinsiemi di minoranti o di maggioranti di un singleton. Esempio di una parte di un reticolo che, rispetto all'ordinamento indotto, è un reticolo ma non è un sottoreticolo.

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

Esercizi proposti:

1. Sia $x$ un elemento di un insieme ordinato $S$. Allora, in $S$, $x$ è minimale e e solo se $\set x^\downarrow= \set x$.
2. Trovare un isomorfismo di reticoli dall'insieme delle parti di $\set{0,1}$ all'insieme delle parti di $\set{3,4}$, ordinati per inclusione.
3. Provare che se due insiemi $a$ e $b$ sono equipotenti, gli insiemi ordinati $(\P(a),\sseq)$ e $(\P(b),\sseq)$ sono isomorfi.
4. Svolgere l'esercizio 3 dal compito del 12 novembre 2018.
5. Stabilire per quali interi $n$ nell'insieme $\set{2,14,18,27,30}$ il reticolo dei numeri naturali divisori di $n$ (sottoreticolo di $(\N,\mid\,))$ è complementato.
6. $2$ ha un complemento in $(\N,\mid)$? $(\N,\mid)$ è complementato?
7. Riguardare gli esercizi delle lezioni precedenti stabilendo se i reticoli lì presentati sono o meno complementati.
8. Verificare: se $a$ e $b$ sono parti di un insieme ordinato $(S,\rho)$, allora $(a\cap b)^{\downarrow_{(S,\rho)}}\supseteq a^{\downarrow_{(S,\rho)}}\cup b^{\downarrow_{(S,\rho)}}$ e $(a\cap b)^{\uparrow_{(S,\rho)}}\supseteq a^{\uparrow_{(S,\rho)}}\cup b^{\uparrow_{(S,\rho)}}$, dove le inclusioni possono essere strette.
9. Disegnare il diagramma di Hasse di un reticolo in cui esista un elemento con sei complementi.
10. Trovare, tra i sottoinsiemi di $\P(\N)$, ordinati per inclusione:
    1. un sottoinsieme di cardinalità 5 che non sia un reticolo;
    2. un sottoinsieme di cardinalità 5 che sia un reticolo trirettangolo.
    3. un sottoinsieme di cardinalità 5 che sia un reticolo pentagonale.

33 — 15/12

Discussione di un esercizio dalla lezione precedente: $2$ non ha complemento in $(N,|\,)$ che è quindi un reticolo) non complementato.

Interpretazione della dualità in un reticolo come scambio tra le due operazioni reticolari.

Reticoli distributivi (senza dimostrazione: la distributività anche di una sola delle due operazioni reticolari rispetto all'altra implica la distributività del reticolo). Esempi: sono distributivi $(\P(S),\subseteq)$ per ogni insieme $S$, $(\N,\mid)$ (questo non lo abbiamo dimostrato), gli insiemi totalmente ordinati. I sottoreticoli dei reticoli distributivi sono distributivi. Unicità dei complementi nei reticoli distributivi. Reticolo trirettangolo e reticolo pentagonale; criterio di distributività di Birkhoff (dimostrata solo l'implicazione banale); esempi di applicazione.

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

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

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

Ricordo la riunione dedicata allo svolgimento di esercizi che si terrà, come da avviso nella pagina principale del corso, domani, a partire, 16 dicembre, dalle ore 9, nel canale teams del corso.

Esercizi proposti:

1. Dimostrare in modo diretto (cioè senza usare il teorema di Birkhoff) che gli insiemi totalmente ordinati sono reticoli distributivi.
2. Completare gli esercizi sugli insiemi ordinati da tracce d'esame già proposti solo in forma parziale nelle lezioni precedenti.
3. Provare che, come detto a lezione, l'insieme delle parti $x$ di $\N$ tali che uno tra $x$ e $\N\setminus x$ sia finito costituisce una sottoalgebra di Boole dell'algebra delle parti di $\N$.
4. Verificare che un'applicazione tra i sostegni di due algebre di Boole è un isomorfismo di algebre di Boole se e solo se è un isomorfismo tra i corrispondenti reticoli (visti come insiemi ordinati).
5. Verificare che, in ogni algebra di Boole vale $(a\lor b)\land(a\land b)'=(a'\land b)\lor (a\land b')$ per ogni coppia di elementi $a$ e $b$.
6. Spiegare perché un reticolo complementato di cardinalità 1000 non può essere distributivo.

34 — 18/12

Anelli di polinomi (ad una indeterminata) su un anello commutativo unitario (si vedano le relative note, dove, fare attenzione!, l'insieme di numeri interi positivi è talvolta indicato con $\N^+$, ed anche le notazioni per la composizione tra applicazioni e l'immagine di elementi mediante applicazioni, lì spiegate, non coincidono con quelle usate in altre parti del corso). Definizione, primissime proprietà, terminologia essenziale (grado, successione dei coefficienti, coefficiente direttore, termine noto, polinomi monici, polinomi costanti); esempi. Proprietà universale per anelli di polinomi. Come conseguenze ed esempi: unicità a meno di isomorfismi dell'anello dei polinomi ad una indeterminata su un assegnato anello commutativo unitario (l'esistenza è non stata dimostrata); omomorfismi di sostituzione; per ogni $n\in\N^*$, l'omomorfismo suriettivo $\Z[x]\to\Z_n[x]$ che ad ogni polinomio $f$ associa '$f$ riguardato modulo $n$'.

Gradi di somma, differenza e prodotto tra due polinomi. Sia fissato un anello commutativo unitario non nullo $A$. Se il polinomio $f\in A[x]$ ha coefficiente direttore cancellabile (in $A$), allora $f$ stesso è cancellabile in $A[x]$ ed inoltre vale per $f$ ed un qualsiasi polinomio $g\in A[x]$ la regola di addizione dei gradi: $\nu(fg)=\nu(f)+\nu(g)$ e (quindi) $\cd(fg)=\cd(f)\cd(g)$. $A[x]$ è un dominio di integrità se e solo se lo è $A$, ovvero se e solo se vale, in $A[x]$, la regola di addizione dei gradi per ogni coppia di polinomi; in questo caso si ha anche $\U(A[x])=\U(A)$. Un esempio che mostra come queste proprietà possano non valere se $A$ non è integro. Qualunque sia $A$, i polinomi in $A[x]$ di grado maggiore di zero e coefficiente direttore cancellabile in $A$ (ad esempio, $x$) non sono invertibili; di conseguenza gli anelli di polinomi non sono mai campi.

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

Esercizi proposti:

1. Completare, come suggerito nelle note, la verifica della proprietà universale per anelli di polinomi.
2. Per ogni intero $n>1$ si consideri il polinomio $f_n=\overline{30}x^5+\overline{10}x^3+\overline{3}x^2+\overline{6}\in\Z_n[x]$ (qui e negli esercizi che seguono, per ogni intero $a$ il simbolo $\bar a$ rappresenta le classe di resto di $a$ nel modulo indicato dal contesto). Stabilire per quali $n$ il grado di $f_n$ è $5$ e trovare il grado di $f_n$ nei casi rimanenti. Stabilire per quali $n$ il polinomio $f_n$ è monico.
3. Per ogni numero primo positivo $p$, si stabilisca il grado del polinomio $f_p:=\overline{22}x^5+\bar 8 x^4 - \bar7x^2+\bar 3$ a coefficienti nel campo $\Z_p$. Per quali primi positivi $p$ il polinomio $f_p$ è monico?
4. Vero o falso: Sia $A$ un anello commutativo unitario non nullo tale che ogni polinomio non nullo nell'anello di polinomi $A[x]$ sia monico. Allora $A$ è isomorfo a $\Z_2$ (l'osservazione inversa è stata vista a lezione).
5. Vero o falso: se $A$ è un anello booleano, anche $A[x]$ è booleano.
6. Sia $f$ il polinomio $\bar 7x^3-\bar 1\in\Z_{43}[x]$. Trovare, se esiste, (o spiegare perché non esiste)
   • un polinomio $g\in\Z_{43}[x]$ tale che $fg$ sia monico di grado 10;
   • un polinomio $h\in\Z_{43}[x]$ tale che $f+h$ abbia grado 2;
7. Effettuare la divisione, in $\Q[x]$, del polinomio $2x^4+1$ per $3x+2$. Dividere poi, in $\Z_5[x]$, il polinomio $\bar 2x^4+\bar 1$ per $\bar 3x+\bar 2$ (sono gli stessi polinomi di prima "riguardati modulo 5").
8. Decidere:
   1. quanti sono i polinomi di grado 2 in $\Z_5[x]$;
   2. quanti sono i polinomi monici di grado 4 in $\Z_5[x]$.
9. In $\Z_4[x]$ individuare i polinomi invertibili e quelli cancellabili tra $\bar 2x -\bar 1$, $\bar 2x -\bar 2$, $\overline{1000}x^{1000}+ \overline{480}x^{333}- \overline{24}$ e $\overline{1000}x^{1000}+ \overline{999}x^{999}$

35 — 20/12

Anche per il contenuto di questa lezione è si consiglia di consultare le note sui polinomi

Applicazione polinomiale definita da un polinomio. Radici di un polinomio. Le radici di un polinomio sono radici anche dei suoi multipli (e quindi sono tutte e sole le radici di ciascuno dei suoi associati). Se $A$ è un dominio di integrità le radici di un prodotto sono tutti e soli gli elementi che sono radici di almeno uno dei fattori.

Teorema del resto: se $f\in A[x]$ e $c\in A$, allora il resto nella divisione di $f$ per $x-c$ è $f(c)$. Come conseguenza, Teorema di Ruffini: $c$ è radice di $f$ se e solo se $x-c$ divide $f$. Teorema di Ruffini generalizzato (per polinomi su domini di integrità).

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

Questioni di fattorizzazione in anelli di polinomi $A[x]$. Senza dimostrazione: se $A$ è un anello fattoriale, allora $A[x]$ è fattoriale (ad esempio, questo accade se $A$ è un campo oppure $A=\Z$). Associati in $A[x]$, con particolare riferimento al caso in cui $A$ sia un dominio di integrità (nel qual caso dei polinomi associati devono avere lo stesso grado) o un campo nel qual caso ogni classe di polinomi associati non nulli ha uno ed un solo rappresentante con preassegnato coefficiente direttore, in particolare ha uno ed un solo rappresentante monico, di conseguenza (se $A$ è un campo) 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.

I divisori non banali di un polinomio non nullo a coefficienti in un campo e di grado $n$ sono quelli di grado strettamente compreso tra $0$ e $n$; conseguente caratterizzazione dei polinomi irriducibili nell'anello dei polinomi su un campo. Rapporti tra esistenza di radici ed irriducibilità. Un esempio: determinazione dei polinomi irriducibili di grado al più quattro in $\Z_2[x]$.

Descrizione dei polinomi irriducibili sul campo reale; i polinomi di grado dispari in $\R[x]$ hanno sempre radici in $\R$.

Polinomi in $\Q[x]$. Ciascuno di essi è associato (in $\Q[x]$) ad un polinomio a coefficienti interi. Criterio di irriducibilità di Eisenstein (non dimostrato); come conseguenza: per ogni $n\in\N^*$ ed ogni primo $p$, $x^n-p$ è irriducibile in $\Q[x]$. Ancora non dimostrato: radici razionali di un polinomio $f\in\Z[x]$; come conseguenza: le radici razionali dei polinomi monici a coefficienti interi sono numeri interi.

Esercizi proposti:

1. Si costruisca, se possibile, un polinomio di grado 300 in $\Q[x]$ le cui radici in $\Q$ siano tutti e soli gli interi $n$ tali che $-100\le n \lt 100$.
2. Per ogni primo positivo $p$, sia $f_p$ il polinomio $\bar 3x^4+\bar 2 x^3 +\bar 2 x^2+ x+ \bar 2\in\Z_p[x]$. Determinare:
   1. i primi positivi $p$ tali che $f_p$ abbia $\bar 1$ come radice;
   2. i primi positivi $p$ tali che $f_p$ sia divisibile per $x-\bar 1$.
3. Decidere quanti sono i polinomi monici di grado 6 in $\Z_{11}[x]$ che abbiano (almeno) $\bar 1$ e $\bar 2$ come radici.
4. In $\Z_3$, e con riferimento a polinomi in $\Z_3[x]$:
   • trovare tutte le radici del polinomio $x^2-x+\bar 1\in\Z_3[x]$,
   • quelle del polinomio $x^{50}+x^{35}+\bar 1$,
   • e quelle del polinomio $(x+\bar 1)^5((x-\bar 1)^7+\bar 1)$.
5. Esercizio nr. 8 da Polinomi e strutture algebriche.
6. Se possibile, trovare un polinomio di coefficiente direttore 340 che sia associato in $\Q[x]$ a $3x^2-1$.
7. Sia $f=x^4-9\in \Z[x]$. Scrivere $f$ come prodotto di polinomi monici irriducibili in $\Q[x]$ e come prodotto di polinomi monici irriducibili in $\R[x]$.
8. Scrivere il polinomio $x^5-x\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Fare lo stesso per $x^5-x\in\Z_7[x]$.
9. Utilizzando il teorema di Ruffini come punto di partenza, scrivere il polinomio $f=\bar 2 x^4+x+\bar 1\in\Z_5[x]$ come prodotto di polinomi irriducibili in $\Z_5[x]$. Trovare poi l'associato monico di $f$ in $\Z_5[x]$.
10. Trovare tutte le radici in $\Q$ del polinomio $2x^{10}+x^9-x^8+12x^2-3$.
11. Il polinomio $50x^{12}-6x^5+18x-24$ è irriducibile in $\Q[x]$? E $x^3-9$?
12. Scrivere $x^3-3x^2+4$ come prodotto di polinomi monici irriducibili in $\Q[x]$.
13. Per ogni $n\in\Z$, sia $f_n=(100+4n)x^4+(n+8)x^3+nx^2+1$ e sia $\bar {f_n}\in \Z_{11}[x]$ il polinomio $f_n$ riguardato come polinomio a coefficienti in $\Z_{11}[x]$. Sia $L=\{n\in\N \mid \nu \bar {f_n}=2\}$. Decidere se $L=\vuoto$ o $L\ne\vuoto$; nel secondo caso, posto $m=\min L$, scrivere l'associato monico di $\bar {f_m}$ in $\Z_{11}[x]$. Ripetere l'esercizio dopo aver ridefinito $f_n$ come $(100+4n)x^4+(n-8)x^3+nx^2+1$.
14. Tra i seguenti polinomi, dire quali sono e quali non sono irriducibili in $\Q[x]$ e quali sono e quali non sono irriducibili in $\R[x]$: $x^3+1$, $x^2+1$, $(8x^2+1)(x^2+3)$, $13x^9+50x^7+10$, $x^{1066}-7^{1066}$. Riguardati i polinomi precedenti a coefficienti in $\Z_5[x]$, dire quali sono irriducibili in $\Z_5[x]$.
15. Leggere con attenzione gli esempi (esercizi svolti) nella parte finale delle note sui polinomi.
16. Molti esercizi contenuti tra le prove d'esame sono riferiti ad anelli di polinomi; si consiglia di risolverli. Ad esempio, si svolgano gli esercizi 6 dai compiti del 4 ottobre 2023, del 13 luglio 2023, del 2 marzo 2023, del 23 febbraio 2023, del 23 gennaio 2023, i numero 5 dai compiti del 14 febbraio 2020 e del 16 gennaio 2019.

36 — 22/12

Introduzione informale a diverse nozioni di grafo. Grafi semplici (definiti in termini di lati, o archi) e loro rappresentazione grafica. Definizione di multigrafo semplice (senza cappi). Definizione alternativa di grafo semplice, in termini di relazione di adiacenza. Terminologia: incidenza, grado, vertici isolati. Grafi completi. Grafo complementare di un grafo. Sottografi.

Isomorfismi tra grafi (o tra multigrafi); proprietà che questi conservano. Esempi.

Nozione di grafo planare (ovvero: piano). Esempi di grafi non planari e cenno al teorema di Kuratowski.

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

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

Cammini e circuiti euleriani. Condizione necessaria e sufficiente per la loro esistenza in termini del numero di vertici dispari. 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$; è un albero se e solo se per ogni coppia $(a,b)$ di vertici distinti di $G$ esiste esattamente un cammino in $G$ da $a$ a $b$.

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

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

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

Esercizi proposti:

1. Fornire (utilizzando i suggerimenti dati a lezione e ragionando per induzione sul numero dei lati) una seconda dimostrazione del fatto che il doppio del numero dei lati di un multigrafo finito è la somma dei gradi dei suoi vertici.
2. Dimostrare che se due grafi $G$ e $G'$ sono isomorfi, anche il grafo complementare di $G$ ed il grafo complementare di $G'$ sono isomorfi tra loro.
3. Elencare, a meno di isomorfismi, i grafi con insieme dei vertici di cardinalità minore di 4. Quelli su quattri vertici sono elecati in lista dei grafi su quattro vertici; ma va verificato che i grafi lì rappresentati sono effettivamente a due a due non isomorfi e che la lista è esuastiva (cioè che ogni grafo su quattro vertici è isomorfo ad uno dei grafi nella lista). Nella stessa lista, decidere quali grafi sono connessi e quali sono alberi o foreste.
4. Esercizi da Grafi, ad esclusione del nr. 4.
5. Disegnare, a meno di isomorfismi, tutti gli alberi con (esattamente) cinque vertici.
6. Vero o falso? Le foreste finite sono grafi planari.
7. Si considerino i grafi $G=(V,L)$ che verificano la proprietà $\Phi$: “$|V|=6=|L|$ ed esistono in $G$ (almeno) un vertice di grado 4 ed (almeno) tre vertici di grado 2”.
   1. Se un grafo $G$ verifica $\Phi$, quali possono essere i gradi dei suoi vertici?
   2. Disegnare, se possibile, un grafo che verifichi $\Phi$.
   3. Disegnare, a meno di isomorfismi, tutti i grafi che verificano $\Phi$.
8. Stabilire per quali interi positivi $n$ il grafo completo su $n$ vertici abbia cammini euleriani e per quali abbia circuiti euleriani.