Settimana 1: insiemi, De Morgan, induzione e partizioni

Insiemi.

• Si scrive con le graffe: con l'elenco, $\{1,3,5\}$, o con una regola, $\{n\in \mathbb{N}\mid n<5\}=\{0,1,2,3,4\}$. La barra si legge «tali che».
• $\{1,2\}=\{2,1\}=\{1,1,2\}$: ordine e ripetizioni non contano.
• Un insieme può stare dentro un altro: $\{0,\{1,-1\}\}$ ha due elementi, lo zero e il sacchetto $\{1,-1\}$. Le graffe interne contano.
• L'insieme vuoto $\varnothing$ non ha elementi; $\{\varnothing \}$ invece ne ha uno, il vuoto.
• La cardinalità $|A|$ è il numero degli elementi: $|\{a,b,a\}|=2$.

Per ogni ed esiste. $\forall$ si legge «per ogni», $\exists$ «esiste». Per dire il contrario «per ogni» diventa «esiste» e la proprietà si nega: il contrario di «tutti hanno superato l'esame» è «almeno uno non l'ha superato», non «nessuno». Per smontare una frase con «per ogni» basta un controesempio.

Sottoinsiemi. $B\subset A$ se ogni elemento di $B$ sta in $A$. Il vuoto e $A$ stesso sono sempre sottoinsiemi di $A$. Mori scrive $\subset$ anche quando i due insiemi possono essere uguali. Due insiemi sono uguali quando ognuno è contenuto nell'altro: è la doppia inclusione. L'insieme delle parti $P(A)$ ha come elementi tutti i sottoinsiemi di $A$: $P(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}$.

Naturali e induzione.

• $\mathbb{N}=\{0,1,2,\dots \}$: per Mori lo zero è un naturale.
• Induzione, come il domino: passo base (la proprietà vale per il primo numero) e passo induttivo (se vale per $n$, vale per $n+1$). Allora vale per tutti. Il passo base non si salta.
• Esempi: $1+2+\cdots +n=\frac{n(n+1)}{2}$; quello del libro, $1^2+2^2+\cdots +n^2=\frac{n(n+1)(2n+1)}{6}$.
• Un insieme con $n$ elementi ha $2^n$ sottoinsiemi: per ogni elemento la scelta è «dentro» o «fuori». Quelli di $\{1,\dots ,6\}$ che contengono 1 sono $2^5=32$: fissi l'1 e scegli il resto.
• Le famiglie di numeri: $\mathbb{N}\subset \mathbb{Z}\subset \mathbb{Q}\subset \mathbb{R}$. Intervalli: $(a,b)$ con gli estremi esclusi, $[a,b]$ compresi.

L'esempio che gira per tutta la lezione: $X$ = le tessere da 1 a 10, $A$ = i pari $=\{2,4,6,8,10\}$, $B$ = i multipli di 3 $=\{3,6,9\}$.

• Due insiemi sono disgiunti se l'intersezione è vuota.
• L'intersezione è un insieme: se $A\cap B=\{6\}$ allora $6\in A\cap B$ e $\{6\}\subset A\cap B$; sono sbagliati $6\subset A\cap B$ e $\{6\}\in A\cap B$.
• $|A\cup B|=|A|+|B|-|A\cap B|$: $5+3-1=7$, perché gli elementi comuni si contano una volta.
• Proprietà distributive: $(A\cup B)\cap C=(A\cap C)\cup (B\cap C)$, e la stessa con $\cap$ e $\cup$ scambiati.
• Il complementare dipende da $X$: $\{2,4\}$ in $\{1,\dots ,5\}$ ha complementare $\{1,3,5\}$, nelle dieci tessere $\{1,3,5,6,7,8,9,10\}$. Il complementare del complementare è l'insieme di partenza.

Come si legge. Fuori dall'unione vuol dire fuori da tutti e due: con le tessere $\{1,5,7\}$. Fuori dall'intersezione vuol dire fuori da almeno uno: tutte tranne la 6. Il complementare entra nella parentesi e scambia $\cap$ e $\cup$, come nella logica: il contrario di «piove e fa freddo» è «non piove oppure non fa freddo». Le stesse leggi valgono con la differenza: $X\setminus (A\cap B)=(X\setminus A)\cup (X\setminus B)$.

Assiomi di Peano, spiegati con quello che va storto quando ne manca uno:

La regola 5 è il principio di induzione.

Insieme delle parti, ricoprimenti, partizioni.

• I sottoinsiemi di $\{1,2,3\}$ per grandezza sono $1+3+3+1=8=2^3$. Aggiungere un elemento raddoppia il conto: quelli senza più quelli con.
• Gli elementi di $P(A)$ sono insiemi: $\{1\}\in P(A)$ ma $1\notin P(A)$. $P(\varnothing )=\{\varnothing \}$. Vale $P(A)\cap P(B)=P(A\cap B)$, ma $P(A\cup B)$ in generale è più grande di $P(A)\cup P(B)$.
• Un ricoprimento di $X$ è un gruppo di sottoinsiemi di $X$ la cui unione è tutto $X$; le parti possono sovrapporsi.
• $n\mathbb{Z}$ sono i multipli di $n$: $2\mathbb{Z}$ i pari, $2\mathbb{Z}+1$ i dispari, e $\mathbb{Z}=2\mathbb{Z}\cup (2\mathbb{Z}+1)$.
• L'insieme quoziente ha come elementi le parti di una partizione; $[x]$ è la parte che contiene $x$. Per pari e dispari: $[0]$ e $[1]$.
• $\{1,2,3\}$ ha 5 partizioni; $\{a,b,c,d\}$ ne ha 15.

• Prova comune ai tre canali: 10 quiz a 5 risposte e 2 problemi, in 2 ore. Con meno di 6 nel quiz i problemi non si correggono; la sufficienza è 18. Si possono portare libro, appunti e una calcolatrice non programmabile.
• Appelli 2026/27: martedì 19/01/2027 e mercoledì 03/02/2027, alle 14:00 (su MyUniTo l'appello si chiama «M.D.A.G.1»).
• La domanda 1 riguarda quasi sempre gli insiemi: $\in$ contro $\subset$, unione e intersezione (appelli del 2025 e del 2026). La domanda 2 a volte chiede una partizione (04/02/2025) o «un ricoprimento ma non una partizione» (07/07/2025).
• Nei problemi tornano i conteggi con $2^n$ e, più avanti, «almeno uno» contato come «tutti meno nessuno», cioè con il complementare.
• Negli appelli di Matematica Discreta l'induzione non va scritta; a Fondamenti dell'Informatica il principio di induzione è tra gli argomenti dei quiz.

Tutte domande vere dei quiz di Matematica Discreta, con la data dell'appello. Le risposte giuste sono quelle delle soluzioni ufficiali, ricontrollate con un programma. All'esame ogni domanda vale 1 punto, e servono almeno 6 punti su 10 nel quiz perché i problemi vengano corretti.