Parte 1 (modA) · Matematica Discreta · Canali A, B e C · Lezione D01

Insiemi e induzione

Il linguaggio su cui si regge tutto il corso: gli insiemi, cioè raccolte di oggetti, e il modo di parlarne con precisione. Poi i numeri per contare e un modo nuovo di dimostrare le cose, l'induzione. Alla fine scopri quanti sottoinsiemi ha un insieme, un conto che all'esame torna spesso.

Libro: A. Mori, Lezioni di Matematica Discreta, cap. 1, pp. 1–8
Docenti: Andrea Mori (canale B), Ignazio Longhi e Lea Terracini (canali A e C) · A.A. 2026/27
Tempo di studio: 2–3 ore, anche in più volte

Definizione o risultato da sapere
Trappola / errore tipico
Conta all'esame
Oltre il libro
Esempio svolto
L'idea e il metodo, passo per passo
Da ricordare
Ripasso

La lezione in 8 punti

Un insieme è una raccolta di oggetti, che si chiamano i suoi elementi. Conta solo chi c'è dentro: l'ordine non importa e ogni elemento si conta una volta sola.
Un insieme si descrive in due modi: con l'elenco dei suoi elementi tra parentesi graffe, oppure con una regola che dice chi entra e chi no.
«Per ogni» ed «esiste» servono per parlare di tutti gli elementi o di almeno uno. Per far vedere che una frase con «per ogni» è falsa basta un solo caso contrario, il controesempio.
L'insieme vuoto non contiene niente. La cardinalità di un insieme è il numero dei suoi elementi.
Un sottoinsieme è una parte di un insieme: tutti i suoi elementi stanno anche nell'insieme di partenza. Tutti i sottoinsiemi, messi insieme, formano l'insieme delle parti.
I numeri naturali sono 0, 1, 2, 3 e così via. Il principio di induzione dimostra una proprietà per tutti i naturali in due mosse, come una fila di tessere del domino che cadono una dopo l'altra.
Un insieme con $n$ elementi ha $2^{n}$ sottoinsiemi: ogni elemento in più raddoppia il conto.
All'esame la prima domanda del quiz riguarda quasi sempre gli insiemi. Il punto delicato è distinguere «è un elemento di» da «è un sottoinsieme di».

Canali A, B e C

Matematica Discreta, la parte 1 di MDAG, ha lo stesso programma e la stessa prova d'esame nei canali A, B e C, quindi questi appunti valgono per tutti e tre. Cambiano i docenti e l'ordine degli argomenti. Nel canale B insegna Andrea Mori, che segue il suo libro Lezioni di Matematica Discreta: questi appunti seguono il capitolo 1 del libro (pp. 1–8) e il diario del canale B del 2025/26, dove la prima lezione trattava insiemi, insieme vuoto, numeri naturali e induzione, sottoinsiemi e il conto dei sottoinsiemi. Nei canali A e C insegnano Ignazio Longhi e Lea Terracini: nel 2025/26 anche lì si partiva dagli insiemi, poi venivano funzioni e combinatoria, in un ordine un po' diverso da quello del libro. Sulla pagina Moodle del 2025/26 (MDAG1, id 3501, aperta agli ospiti) ci sono appunti scritti a mano e video delle lezioni di A e C. La prima lezione del canale A copriva le stesse idee di base (insiemi, cardinalità, sottoinsiemi, insieme vuoto, uguaglianza) e scriveva $\subseteq$ dove Mori scrive $\subset$ .

§1

Un insieme è un sacchetto di oggetti

pp. 1–3

Pensa a un sacchetto della spesa con dentro una mela, una pera e una banana. Il sacchetto, con quello che contiene, è un esempio di insieme. Le cose che ci sono dentro si chiamano gli elementi dell'insieme.

Per scrivere un insieme si mettono i suoi elementi tra parentesi graffe, separati da virgole:

{mela, pera, banana}

Si legge «l'insieme che contiene mela, pera e banana».

Di solito un insieme si chiama con una lettera maiuscola, come $A$ o $B$ . I suoi elementi si chiamano con lettere minuscole, come $a$ o $x$ . Per esempio la riga

A = {1, 2, 3}

vuol dire: chiamo $A$ l'insieme che contiene i numeri 1, 2 e 3.

Dentro o fuori

Per dire che un oggetto sta in un insieme c'è un simbolo apposta. Assomiglia a una «e», l'iniziale di «elemento».

$x \in A$ si legge « $x$ appartiene ad $A$ », oppure « $x$ è un elemento di $A$ ».
$x \in / A$ si legge « $x$ non appartiene ad $A$ ». La barra sopra il simbolo vuol dire «non».

Riprendiamo l'insieme $A = {1, 2, 3}$ .

Il numero 2 è nella lista, quindi $2 \in A$ .
Il numero 5 nella lista non c'è, quindi $5 \in / A$ .

Il libro di Mori dà la definizione così.

Definizione 1.1 · Insieme

Un insieme è una collezione ben definita di oggetti distinti, detti gli elementi dell'insieme.

Come si legge. «Collezione» vuol dire raccolta: il sacchetto. «Ben definita» vuol dire che per ogni oggetto si può decidere, senza dubbi, se sta dentro oppure no. «Distinti» vuol dire diversi tra loro: lo stesso oggetto non si conta due volte.

Che cosa può stare in un insieme (p. 2)

Il libro aggiunge tre osservazioni.

Dentro può esserci qualunque cosa. Numeri, ma anche città, persone, parole. Gli elementi non devono nemmeno essere dello stesso tipo: esiste l'insieme che contiene il numero 4, la Mole Antonelliana e il tuo zaino.
Deve essere chiaro chi c'è dentro. «Gli attori bravi» non è un insieme, perché sull'essere bravi ognuno ha la sua opinione. «Gli attori che hanno vinto un Oscar» invece è un insieme: basta controllare l'elenco dei premi.
Un insieme può essere un elemento di un altro insieme. Un sacchetto chiuso può stare dentro un sacchetto più grande.

Un sacchetto dentro un sacchetto

La terza osservazione è quella che crea più confusione, quindi vediamola con calma.

Metti i numeri 1 e $- 1$ in un sacchetto piccolo: è l'insieme $B = {1, - 1}$ . Poi metti in un sacchetto grande il numero 0 e il sacchetto piccolo, chiuso. Il sacchetto grande è

A = {0, B} = {0, {1, - 1}}

0

1

- 1

A

B

L'insieme

A = {0, {1, - 1}}

ha due elementi: lo zero e il sacchetto piccolo

B

Guarda la figura: dentro il cerchio grande ci sono due oggetti, il punto dello zero e il cerchio piccolo. I numeri 1 e $- 1$ stanno nel cerchio piccolo, non direttamente in quello grande. Quindi:

$1 \in B$ : l'1 è nel sacchetto piccolo;
$B \in A$ : il sacchetto piccolo è nel sacchetto grande;
$1 \in / A$ : tra i due oggetti del sacchetto grande non c'è l'1.

È la Nota 1.2 del libro. Se un insieme è un elemento di un altro insieme, i suoi elementi non diventano per questo elementi di quello più grande.

Trappola · Le graffe interne contano

In ${0, {1, - 1}}$ gli elementi sono due, non tre. Un paio di graffe dentro la lista racchiude un solo elemento, che è a sua volta un insieme. All'esame questa trappola compare spesso nella prima domanda del quiz (vedi «Verso l'esame»).

Due modi per scrivere un insieme (pp. 2–3)

Il primo modo è l'elenco: si scrivono tutti gli elementi, uno per uno. Funziona bene quando gli elementi sono pochi.

Il secondo modo è la regola: si spiega che cosa deve avere un oggetto per entrare. Per esempio «i numeri pari tra 1 e 10». Con una regola si descrivono anche insiemi enormi o infiniti, che non si potrebbero mai elencare per intero.

Ecco qualche insieme scritto nei due modi.

Con una regola, a parole	Con l'elenco
i numeri pari tra 1 e 10	${2, 4, 6, 8, 10}$
le vocali	${a, e, i, o, u}$
i numeri naturali più piccoli di 4	${0, 1, 2, 3}$
i numeri pari maggiori di zero	non finisce mai: ${2, 4, 6, 8, \dots}$

I puntini dell'ultima riga si leggono «e così via»: gli elementi continuano con la stessa regola.

Per scrivere una regola con i simboli il libro usa questa forma (Nota 1.3):

X = {x \in U ∣ P (x)}

Si legge « $X$ è l'insieme degli $x$ di $U$ tali che $x$ ha la proprietà $P$ ». Vediamola un pezzo alla volta.

$U$ è l'insieme da cui si pescano gli oggetti, per esempio tutti i numeri naturali. Il libro lo chiama insieme universale: è l'ambito del discorso.
La sbarra verticale $∣$ si legge «tali che».
$P (x)$ è la proprietà da controllare: una frase su $x$ che può essere vera o falsa, come « $x$ è pari». La $P$ è una P in corsivo elegante.

Esempio · Una regola scritta con i simboli

{n \in N ∣ n \overset{e}{ˋ} pari} = {0, 2, 4, 6, \dots}

Si legge «i numeri naturali $n$ tali che $n$ è pari». Qui l'insieme universale è $N$ , l'insieme dei numeri naturali $0, 1, 2, 3, \dots$ (lo vediamo meglio più avanti). Lo zero è pari, quindi è dentro.

Ordine e ripetizioni non contano (p. 3)

Un insieme dipende soltanto da chi c'è dentro. Quindi:

l'ordine non conta: ${1, 3, 5}$ e ${5, 1, 3}$ sono lo stesso insieme;
le ripetizioni non contano: scrivere due volte lo stesso elemento non aggiunge niente. Per esempio ${0, 0, 1, 2}$ e ${0, 1, 2}$ sono lo stesso insieme.

Prova tu

Vero o falso? (a)

3 \in {1, 3, 5}

; (b)

4 \in {1, 3, 5}

; (c)

{1, 2}

{2, 1, 1}

sono lo stesso insieme.

(a) Vero: il 3 è nella lista.

(b) Falso: il 4 nella lista non c'è.

Quanti elementi ha l'insieme

{1, {2, 3}, 4}

? Il numero 2 è un suo elemento?

Gli elementi sono tre: il numero 1, l'insieme ${2, 3}$ e il numero 4.

Il 2 non è un elemento: sta dentro il sacchetto piccolo ${2, 3}$ , non direttamente in quello grande.

Da ricordare

Un insieme è una raccolta di oggetti, i suoi elementi. Si scrive con le graffe: ${1, 2, 3}$ .
$x \in A$ vuol dire « $x$ è un elemento di $A$ ».
Ordine e ripetizioni non contano.
Un insieme può essere un elemento di un altro insieme, ma i suoi elementi non diventano elementi di quello grande.

§2

Tutti o almeno uno: per ogni ed esiste

pp. 3–4

Nelle frasi di tutti i giorni usiamo spesso due parole: «tutti» e «qualcuno». «Tutti gli studenti hanno superato l'esame.» «C'è uno studente che ha risolto tutti gli esercizi.» In matematica queste due idee hanno un nome e un simbolo, perché servono di continuo.

$\forall$ si legge «per ogni». È una A capovolta, da all, «tutti» in inglese. Una frase con «per ogni» dice che una proprietà vale per tutti gli elementi di un insieme, nessuno escluso.
$\exists$ si legge «esiste». È una E rovesciata, da exists. Una frase con «esiste» dice che c'è almeno un elemento con quella proprietà: può essercene uno solo, o anche tanti.

Il libro chiama questi due simboli quantificatori. Ecco come si usano.

Scrittura	Si legge	Un esempio vero
$\forall x \in A, P (x)$	«per ogni $x$ in $A$ , $x$ ha la proprietà $P$ »	$\forall n \in {2, 4, 6}$ , $n$ è pari
$\exists x \in A$ tale che $P (x)$	«esiste un $x$ in $A$ che ha la proprietà $P$ »	$\exists n \in {1, 2, 3}$ tale che $n > 2$ : è il 3

Come si dice il contrario

Prendi la frase «tutti i treni di oggi sono arrivati in orario». Quando è falsa? Non serve che tutti i treni siano in ritardo: basta un treno in ritardo. Quindi il contrario della frase è «almeno un treno è arrivato in ritardo».

Ora prendi la frase «c'è un negozio aperto». Quando è falsa? Quando non ce n'è nemmeno uno, cioè quando tutti i negozi sono chiusi.

L'idea

Quando dici il contrario di una frase, «per ogni» diventa «esiste» ed «esiste» diventa «per ogni». La proprietà, invece, diventa il suo contrario.

È la Nota 1.4 del libro. Il libro scrive «non» con il simbolo $\sim$ , che si legge «non»; molti altri testi usano $\neg$ . Con i simboli:

Frase	Il suo contrario
$\forall x \in A, P (x)$	$\exists x \in A$ tale che non vale $P (x)$
$\exists x \in A$ tale che $P (x)$	$\forall x \in A$ , non vale $P (x)$

Un esempio con i numeri. Prendi un insieme di numeri e la frase «ogni numero dell'insieme è maggiore o uguale a zero». Il contrario è «almeno un numero dell'insieme è negativo».

Con l'insieme ${3, 0, 7}$ la frase è vera: nessun numero è negativo.
Con l'insieme ${3, - 2, 7}$ la frase è falsa, perché c'è il numero $- 2$ .

Il controesempio

Per dimostrare che una frase con «per ogni» è vera bisogna controllare tutti gli elementi. Spesso sono infiniti, e servono ragionamenti come l'induzione, che vedi più avanti. Per dimostrare che è falsa, invece, basta un solo elemento per cui la proprietà non vale. Quell'elemento si chiama controesempio. Nell'esempio di prima il controesempio è il numero $- 2$ .

Esempio · Una domanda dell'appello del 06/06/2025 (domanda 2)

Il testo: «L'affermazione " $\forall x \in N, \forall y \in N, x^{2} + x \geq y$ " è contraddetta da: (1) $(x, y) = (2, 5)$ ; (2) $(x, y) = (- 4, 10)$ ; (3) $(x, y) = (1, 3)$ ; (4) $(x, y) = (0, - 1)$ ; (5) $(x, y) = (3, 12)$ .» L'inizio si legge «per ogni $x$ naturale e per ogni $y$ naturale».

In pratica chiede: per quale coppia di numeri naturali la disuguaglianza è falsa? Quella coppia è un controesempio. Controlliamo le cinque coppie una per una.

Coppia	Due naturali?	Quanto fa $x^{2} + x$	È almeno $y$ ?
$(2, 5)$	sì	$4 + 2 = 6$	$6 \geq 5$ : sì
$(- 4, 10)$	no: $- 4$ non è naturale		non conta
$(1, 3)$	sì	$1 + 1 = 2$	$2 \geq 3$ : no
$(0, - 1)$	no: $- 1$ non è naturale		non conta
$(3, 12)$	sì	$9 + 3 = 12$	$12 \geq 12$ : sì

La risposta è la (3). Le coppie (2) e (4) contengono un numero negativo: non sono coppie di naturali, quindi non possono contraddire una frase sui naturali.

Prova tu

Scrivi il contrario delle frasi: (a) «ogni numero della lista 2, 4, 6 è pari»; (b) «esiste un numero naturale minore di zero». Quale delle due frasi di partenza è vera?

(a) Il contrario è «almeno un numero della lista 2, 4, 6 è dispari».

(b) Il contrario è «ogni numero naturale è maggiore o uguale a zero».

È vera la frase (a) di partenza: 2, 4 e 6 sono tutti pari. La frase (b) di partenza è falsa, quindi è vero il suo contrario.

Trappola · Il contrario di «tutti» non è «nessuno»

Il contrario di «tutti gli studenti hanno superato l'esame» non è «nessuno studente ha superato l'esame». È «almeno uno studente non l'ha superato». Possono averlo superato in tanti: basta che uno sia stato bocciato.

Da ricordare

$\forall$ si legge «per ogni» e parla di tutti gli elementi; $\exists$ si legge «esiste» e parla di almeno uno.
Per dire il contrario: «per ogni» diventa «esiste», «esiste» diventa «per ogni», e la proprietà diventa il suo contrario.
Per dimostrare che una frase con «per ogni» è falsa basta un controesempio.

§3

Il sacchetto vuoto e quanti elementi ci sono

p. 4

Un sacchetto vuoto è pur sempre un sacchetto. Allo stesso modo c'è un insieme che non contiene niente: si chiama insieme vuoto e si scrive $\emptyset$ , uno zero tagliato da una barra.

L'insieme vuoto si può descrivere con tante regole diverse. Per esempio:

i numeri naturali più piccoli di zero;
i numeri interi che sono pari e dispari allo stesso tempo.

Nessun oggetto rispetta queste regole. Quindi descrivono tutte e due lo stesso insieme, quello senza elementi: di insieme vuoto ce n'è uno solo.

Il libro lo dice così.

Definizione 1.5 · Insieme vuoto

Si chiama insieme vuoto e si denota $\emptyset$ l'insieme privo di elementi, $\emptyset = {}$ . Esso è caratterizzato dalla proprietà $\forall x, x \in / \emptyset$ .

Come si legge. ${}$ sono due graffe con niente in mezzo: un sacchetto vuoto. L'ultima formula si legge «per ogni $x$ , $x$ non appartiene all'insieme vuoto»: qualunque oggetto tu prenda, nel vuoto non c'è.

Il vuoto dentro un sacchetto

Non confondere $\emptyset$ con ${\emptyset}$ .

$\emptyset$ è il sacchetto vuoto: non contiene niente.
${\emptyset}$ è un sacchetto che contiene un sacchetto vuoto. Contiene una cosa, quindi non è vuoto.

È la stessa idea del sacchetto dentro il sacchetto: le graffe esterne racchiudono un elemento, che qui è l'insieme vuoto.

Quanti elementi: la cardinalità

Il numero degli elementi di un insieme si chiama cardinalità. Si scrive mettendo l'insieme tra due sbarre verticali: $∣ A ∣$ si legge «cardinalità di $A$ ».

Definizione 1.6 · Cardinalità

Si dice cardinalità di un insieme $A$ , denotata $∣ A ∣$ , il numero degli elementi di $A$ .

Come si legge. Se l'insieme ha un numero finito di elementi, per esempio 5, si scrive $∣ A ∣ = 5$ . Se gli elementi sono infiniti si scrive $∣ A ∣ = \infty$ , e il simbolo $\infty$ si legge «infinito». Il libro avverte che questa definizione verrà resa precisa nel capitolo 3, con le funzioni.

Qualche esempio. Nell'ultima colonna c'è la cardinalità.

Insieme	I suoi elementi	Quanti
${a, b, c}$	$a$ , $b$ , $c$	$3$
${0, 0, 1}$	$0$ e $1$ : lo zero ripetuto conta una volta	$2$
$\emptyset$	nessuno	$0$
${\emptyset}$	il sacchetto vuoto	$1$
${1, {2, 3}}$	il numero $1$ e l'insieme ${2, 3}$	$2$
$N$	$0, 1, 2, 3, \dots$	$\infty$

Prova tu

Calcola la cardinalità di (a)

{0, 1, {0, 1}}

; (b)

{\emptyset, {\emptyset}}

; (c) l'insieme delle lettere della parola «mamma».

(a) Gli elementi sono tre: 0, 1 e l'insieme ${0, 1}$ . La cardinalità è 3.

(b) Gli elementi sono due: il sacchetto vuoto e il sacchetto che contiene il sacchetto vuoto. La cardinalità è 2.

Da ricordare

L'insieme vuoto $\emptyset$ non ha elementi. L'insieme ${\emptyset}$ invece ha un elemento.
La cardinalità $∣ A ∣$ è il numero degli elementi di $A$ , ognuno contato una volta sola.

§4

Un insieme dentro l'altro: i sottoinsiemi

pp. 4–5

Torna al sacchetto con mela, pera e banana. Togli la pera: ti resta un sacchetto con mela e banana. Ogni frutto del sacchetto nuovo viene dal sacchetto di partenza. Il sacchetto nuovo è un sottoinsieme di quello di partenza.

L'idea

Un insieme è un sottoinsieme di un altro quando ogni suo elemento sta anche nell'altro. Nessun elemento resta fuori.

A

B

Il sottoinsieme

B

sta tutto dentro l'insieme

A

: ogni punto di

B

è anche un punto di

A

Il simbolo è $\subset$ . La scrittura $B \subset A$ si legge « $B$ è contenuto in $A$ », oppure « $B$ è un sottoinsieme di $A$ ». Se invece almeno un elemento di $B$ sta fuori da $A$ , si scrive $B \neq \subset A$ , che si legge « $B$ non è contenuto in $A$ ».

Definizione 1.7 · Sottoinsieme

Un insieme $B$ è un sottoinsieme di $A$ , e scriviamo $B \subset A$ , se ogni elemento di $B$ è anche un elemento di $A$ : $\forall b \in B, b \in A$ .

Come si legge. La formula alla fine si legge «per ogni $b$ in $B$ , $b$ appartiene ad $A$ ». È la stessa frase della definizione, scritta con i simboli.

Proviamo con l'insieme $A = {1, 2, 3}$ .

Domanda	Risposta	Perché
${1, 3} \subset A$ ?	sì	1 e 3 stanno tutti e due in $A$
${2} \subset A$ ?	sì	il 2 sta in $A$
${1, 4} \subset A$ ?	no	il 4 non sta in $A$
$A \subset A$ ?	sì	ogni elemento di $A$ sta in $A$
$\emptyset \subset A$ ?	sì	il vuoto non ha elementi che possano stare fuori

Il vuoto e l'insieme intero

Gli ultimi due casi della tabella valgono per qualunque insieme.

Ogni insieme è un sottoinsieme di sé stesso, perché tutti i suoi elementi stanno in lui.
Il vuoto è un sottoinsieme di ogni insieme. Per dire che il vuoto non è contenuto in un insieme servirebbe un controesempio: un elemento del vuoto che sta fuori. Ma il vuoto non ha elementi, quindi un controesempio non c'è.

Il libro chiama il vuoto e l'insieme intero «sottoinsiemi banali». I sottoinsiemi diversi dall'insieme intero si chiamano sottoinsiemi propri. Per esempio ${1, 3}$ è un sottoinsieme proprio di ${1, 2, 3}$ .

Nota · Due modi di scrivere «contenuto»

Nel libro di Mori, e nei testi d'esame, $B \subset A$ vuol dire « $B$ è contenuto in $A$ , e può anche essere uguale». Altri libri, e gli appunti dei canali A e C, scrivono per questo $\subseteq$ , e usano $⊊$ per «contenuto ma non uguale». Quando apri un testo nuovo, controlla quale convenzione usa.

Elemento o sottoinsieme?

Questa è la distinzione più importante della lezione. Riprendiamo $A = {1, 2, 3}$ .

Scrittura	Vera?	Perché
$2 \in A$	sì	il numero 2 è uno degli elementi
${2} \subset A$	sì	l'insieme che contiene solo il 2 è una parte di $A$
${2} \in A$	no	tra gli elementi di $A$ c'è il numero 2, non l'insieme ${2}$
$2 \subset A$	no	2 è un numero, non un insieme: non può essere una parte di $A$

A parole: il simbolo $\in$ collega un oggetto a un insieme, il simbolo $\subset$ collega due insiemi. Nota anche che le prime due righe dicono la stessa cosa: un oggetto sta in un insieme esattamente quando l'insieme che contiene solo lui è un sottoinsieme.

Metodo · Elemento o sottoinsieme?

Guarda l'oggetto a sinistra del simbolo: è un insieme, cioè ha le graffe o è il nome di un insieme?
Se il simbolo è $\in$ , cerca l'oggetto, così com'è e con le sue graffe, nella lista degli elementi a destra.
Se il simbolo è $\subset$ , l'oggetto a sinistra deve essere un insieme. Controlla i suoi elementi uno per uno: devono stare tutti nella lista a destra.
Se tra gli elementi a destra ci sono altri insiemi, conta le graffe con calma: ogni paio di graffe interne è un elemento.

Esempio · Il metodo su un insieme con un insieme dentro

Prendi $X = {a, {b, c}}$ . Ha due elementi: la lettera $a$ e l'insieme ${b, c}$ .

${b, c} \in X$ : vera, è il secondo elemento.
${b, c} \subset X$ : falsa. Servirebbe $b \in X$ , ma $b$ sta dentro il sacchetto interno.
${a} \subset X$ : vera, perché $a \in X$ .
${{b, c}} \subset X$ : vera. È l'insieme che contiene un solo elemento, ${b, c}$ , e quell'elemento sta in $X$ .

Tutte le parti di un insieme

Ora prendi tutti i sottoinsiemi di un insieme e mettili in un sacchetto nuovo. Quel sacchetto si chiama insieme delle parti.

Per esempio i sottoinsiemi di ${a, b}$ sono quattro: il vuoto, ${a}$ , ${b}$ e ${a, b}$ . L'insieme delle parti di ${a, b}$ è quindi

{\emptyset, {a}, {b}, {a, b}}

Ha quattro elementi, e ogni suo elemento è a sua volta un insieme.

Definizione 1.8 · Insieme delle parti

Se $A$ è un insieme, si dice insieme delle parti di $A$ , denotato $P (A)$ , l'insieme i cui elementi sono i sottoinsiemi di $A$ ,

P (A) = {B ∣ B \subset A} .

Come si legge. $P (A)$ si legge «parti di $A$ ». La formula si legge «l'insieme dei $B$ tali che $B$ è contenuto in $A$ »: dentro $P (A)$ ci sono tutti i sottoinsiemi di $A$ , e nient'altro. Attenzione: questa $P$ è una lettera normale e indica un insieme; la $P$ elegante di prima indica una proprietà.

Il libro fa tre esempi (p. 5).

Insieme	I suoi sottoinsiemi	Quanti
$\emptyset$	solo $\emptyset$	$1$
${*}$ , con un solo elemento	$\emptyset$ e ${*}$	$2$
${a, b, c}$	$\emptyset$ , ${a}$ , ${b}$ , ${c}$ , ${a, b}$ , ${a, c}$ , ${b, c}$ , ${a, b, c}$	$8$

La prima riga merita due parole. Il vuoto ha un sottoinsieme, sé stesso. Quindi $P (\emptyset) = {\emptyset}$ : l'insieme delle parti del vuoto ha un elemento, e non è vuoto.

L'idea

Essere un sottoinsieme di $A$ ed essere un elemento di $P (A)$ sono la stessa cosa.

Prova tu

Prendi

A = {1, 2}

. (a) Scrivi

P (A)

. (b) È vero che

1 \in P (A)

? (c) È vero che

{1} \in P (A)

(a) $P (A) = {\emptyset, {1}, {2}, {1, 2}}$ .

(b) No. Gli elementi di $P (A)$ sono insiemi, e il numero 1 da solo non è tra loro.

Con

X = {a, {b, c}}

: è vero che

b \in X

? E che

{b, c} \in X

$b \in X$ è falso: $b$ sta dentro il sacchetto interno ${b, c}$ , non direttamente in $X$ .

${b, c} \in X$ è vero: è il secondo elemento di $X$ .

Da ricordare

$B \subset A$ vuol dire che ogni elemento di $B$ sta anche in $A$ . Il vuoto e l'insieme stesso sono sempre sottoinsiemi.
$\in$ collega un oggetto a un insieme, $\subset$ collega due insiemi.
L'insieme delle parti $P (A)$ ha come elementi tutti i sottoinsiemi di $A$ .

§5

Quando due insiemi sono uguali

p. 5

Due sacchetti sono uguali quando contengono esattamente le stesse cose. Per controllarlo si fanno due verifiche: tutto quello che c'è nel primo sta anche nel secondo, e tutto quello che c'è nel secondo sta anche nel primo.

Esempio · Due verifiche

Prendi $A$ = i numeri naturali il cui quadrato è minore di 10, e $B = {0, 1, 2, 3}$ .

Da $A$ a $B$ . I quadrati dei naturali sono $0, 1, 4, 9, 16, 25, \dots$ e crescono sempre. Sono minori di 10 soltanto quelli di 0, 1, 2 e 3. Quindi ogni elemento di $A$ sta in $B$ : $A \subset B$ .
Da $B$ ad $A$ . I quadrati di 0, 1, 2 e 3 sono 0, 1, 4 e 9, tutti minori di 10. Quindi ogni elemento di $B$ sta in $A$ : $B \subset A$ .

Le due verifiche riescono, quindi $A = B$ .

Il libro lo scrive come una proposizione.

Proposizione 1.9 · Uguaglianza tra insiemi

Siano $A$ e $B$ due insiemi. Allora

A = B ⟺ A \subset B e B \subset A .

Come si legge. Il simbolo $⟺$ si legge «se e solo se», cioè «esattamente quando». A parole: due insiemi sono uguali esattamente quando ognuno dei due è contenuto nell'altro. Questo modo di dimostrare che due insiemi sono uguali si chiama doppia inclusione, e nella prossima lezione servirà spesso.

Dimostrazione · perché vale la proposizione 1.9

Se $A = B$ , i due insiemi hanno gli stessi elementi. Quindi ogni elemento di $A$ sta in $B$ , cioè $A \subset B$ . E ogni elemento di $B$ sta in $A$ , cioè $B \subset A$ .
Al contrario, supponiamo che valgano $A \subset B$ e $B \subset A$ . Se ci fosse un elemento di $A$ fuori da $B$ , non varrebbe $A \subset B$ . Se ci fosse un elemento di $B$ fuori da $A$ , non varrebbe $B \subset A$ . Quindi nessun elemento sta in uno solo dei due insiemi: hanno gli stessi elementi, cioè $A = B$ .

Prova tu

(a)

{1, 2, 3}

{3, 1, 2, 2}

sono uguali? (b) L'insieme degli interi il cui quadrato è 4 è uguale a

{2}

(a) Sì. Ogni elemento del primo (1, 2 e 3) sta nel secondo, e ogni elemento del secondo sta nel primo.

(b) No. Anche $- 2$ ha quadrato 4, perché $(- 2) \cdot (- 2) = 4$ . Quindi $- 2$ sta nel primo insieme ma non in ${2}$ : il primo insieme non è contenuto nel secondo.

Da ricordare

Due insiemi sono uguali quando hanno gli stessi elementi.
Per dimostrarlo si controllano due contenimenti, il primo nel secondo e il secondo nel primo: è la doppia inclusione.

§6

I numeri per contare e l'induzione

pp. 5–6

I numeri che si usano per contare sono 0, 1, 2, 3, 4 e così via, senza fine. Si chiamano numeri naturali, e il loro insieme si scrive $N$ , una N con una doppia barra:

N = {0, 1, 2, 3, \dots}

Nel libro di Mori lo zero è un numero naturale. Alcuni libri lo escludono, ma in questo corso c'è.

Ogni naturale ha un successivo: il successivo di 0 è 1, quello di 1 è 2, quello di un numero $n$ è $n + 1$ . Il libro scrive il successivo di $n$ come $s (n)$ , che si legge «esse di $n$ ».

L'idea che conta è questa: partendo da 0 e andando avanti di uno alla volta si arriva a ogni numero naturale. A 5 si arriva in cinque passi: 0, 1, 2, 3, 4, 5. A un milione si arriva in un milione di passi. Nessun naturale resta fuori.

Nota · Serve per capire, non per l'esame

Il libro descrive i naturali con cinque regole, gli assiomi di Peano. Sono nel riquadro qui sotto, che puoi saltare: all'esame non vengono chiesti.

Approfondimento · gli assiomi di Peano (p. 5)

Il libro dice che l'insieme $N$ dei numeri naturali è caratterizzato da questi cinque assiomi (Peano, 1889):

$0 \in N$ ;
ogni $n \in N$ ha un successore $s (n) \in N$ ;
se $m, n \in N$ e $m \neq = n$ allora $s (m) \neq = s (n)$ ;
$\forall n \in N, 0 \neq = s (n)$ ;
se $U \subset N$ è tale che $0 \in U$ e $s (n) \in U$ , $\forall n \in U$ , allora $U = N$ .

Come si legge. (1) Lo zero è un naturale. (2) Ogni naturale ha un successivo, che è ancora un naturale. (3) Numeri diversi hanno successivi diversi. (4) Lo zero non è il successivo di nessuno: è il primo. (5) Se un insieme di naturali contiene lo zero e, ogni volta che contiene un numero, contiene anche il suo successivo, allora contiene tutti i naturali. La regola 5 si chiama principio di induzione. Le regole 2, 3 e 4 insieme dicono che i naturali sono infiniti: $0$ , $s (0)$ , $s (s (0))$ e così via sono tutti diversi tra loro.

Il domino

Immagina una fila infinita di tessere del domino, in piedi una dietro l'altra e numerate 0, 1, 2, 3 e così via. Vuoi essere sicuro che cadano tutte. Bastano due cose:

la prima tessera cade: qualcuno spinge la tessera 0;
ogni tessera che cade fa cadere la successiva: le tessere sono abbastanza vicine.

Allora cade la 0, che fa cadere la 1, che fa cadere la 2, e così via. Nessuna resta in piedi.

L'idea

Per dimostrare che una proprietà vale per tutti i numeri naturali bastano due controlli: che valga per 0, e che ogni volta che vale per un numero valga anche per il successivo.

Una proprietà dei naturali è una frase che parla di un numero $n$ e che, per ogni $n$ , è vera o falsa. Il libro la scrive $P (n)$ . Due esempi:

« $n + n$ è pari». Per $n = 3$ dice « $3 + 3 = 6$ è pari»: è vera.
« $n$ è minore di 10». Per $n = 3$ è vera, per $n = 12$ è falsa.

Il libro enuncia il principio come un teorema, che dice quando si può concludere che una proprietà vale per tutti.

Teorema 1.10 · Dimostrazione per induzione

Supponiamo assegnata per ogni $n \in N$ una certa proprietà $P (n)$ e supponiamo che

la proprietà $P (0)$ è vera;
$\forall n \in N$ la verità di $P (n)$ implica la verità di $P (n + 1)$ .

Allora la proprietà $P (n)$ è vera per ogni $n$ .

Come si legge. I due punti sono i due controlli del domino.

Il primo, « $P (0)$ è vera», si chiama passo base: la prima tessera cade.
Il secondo si legge «per ogni $n$ naturale, se $P (n)$ è vera allora è vera anche $P (n + 1)$ ». Si chiama passo induttivo: ogni tessera fa cadere la successiva. Mentre lo dimostri, la frase « $P (n)$ è vera» si chiama ipotesi induttiva: la supponi vera e la usi.

Dimostrazione · perché il teorema 1.10 viene dal principio di induzione

Prendi l'insieme $U$ dei numeri naturali per cui la proprietà è vera. Lo zero sta in $U$ , perché $P (0)$ è vera. Se un numero $n$ sta in $U$ , anche $n + 1$ sta in $U$ , per il passo induttivo. Per la regola 5 degli assiomi di Peano, $U$ contiene tutti i naturali: la proprietà è vera per ogni $n$ .

Partire da 1, o da un altro numero

Spesso una formula ha senso solo da 1 in poi, come «la somma dei numeri da 1 a $n$ ». Allora il passo base si fa con $n = 1$ invece che con $n = 0$ , e la conclusione vale per ogni $n$ maggiore o uguale a 1. È la Nota 1.11 del libro.

Si può partire anche da 3 o da 5: la proprietà vale allora da quel numero in poi. Lo vedi negli esercizi 7 e 8.

Trappola · Il passo base non si salta

Prendi la proprietà « $n = n + 1$ ». È falsa per ogni numero, eppure il passo induttivo funziona: se fosse $n = n + 1$ , aggiungendo 1 a tutti e due i lati verrebbe $n + 1 = n + 2$ . Quello che manca è il passo base: $0 = 1$ è falso. Senza la prima tessera non cade niente.

Prova tu

Sai che

P (0)

è vera e che il passo induttivo funziona. Perché è vera

P (3)

Dal passo base $P (0)$ è vera.

Il passo induttivo con $n = 0$ dà $P (1)$ . Con $n = 1$ dà $P (2)$ . Con $n = 2$ dà $P (3)$ .

Sono tre tessere che cadono una dopo l'altra.

Da ricordare

I naturali sono $0, 1, 2, 3, \dots$ e il loro insieme si scrive $N$ .
Induzione: 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 può saltare.

§7

Dimostrare per induzione, passo per passo

pp. 6–7

Vediamo l'induzione al lavoro su una formula famosa: la somma dei numeri da 1 a un numero $n$ .

Prima proviamo con numeri piccoli. Nella seconda colonna c'è la somma, nella terza un conto che sembra dare sempre lo stesso risultato.

$n$	Somma da 1 a $n$	$\frac{n ( n + 1 )}{2}$
1	$1$	$\frac{1 \cdot 2}{2} = 1$
2	$1 + 2 = 3$	$\frac{2 \cdot 3}{2} = 3$
3	$1 + 2 + 3 = 6$	$\frac{3 \cdot 4}{2} = 6$
4	$1 + 2 + 3 + 4 = 10$	$\frac{4 \cdot 5}{2} = 10$
10	$1 + 2 + \dots + 10 = 55$	$\frac{10 \cdot 11}{2} = 55$

In ogni riga le ultime due colonne coincidono. Sembra che valga sempre questa formula:

1 + 2 + 3 + \dots + n = \frac{n ( n + 1 )}{2}

Si legge «la somma dei numeri da 1 a $n$ è uguale a $n$ per $n$ più uno, diviso due».

Però cinque righe di tabella non bastano: i numeri sono infiniti, e nessuno può controllarli tutti. L'induzione permette di dimostrarlo per tutti in un colpo solo.

Esempio · La somma dei numeri da 1 a $n$

La proprietà è la formula qui sopra, e parte da $n = 1$ .

Passo base. Per $n = 1$ a sinistra c'è solo il numero 1. A destra c'è $\frac{1 \cdot 2}{2} = 1$ . I due lati sono uguali.

Ipotesi induttiva. Supponiamo che la formula sia vera per un certo numero $n$ :

1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

Obiettivo. Arrivare alla stessa formula con $n + 1$ al posto di $n$ , cioè a

1 + 2 + \dots + n + (n + 1) = \frac{( n + 1 ) ( n + 2 )}{2}

Passo induttivo. Partiamo dal lato sinistro dell'obiettivo, un passo per riga.

I primi addendi, da 1 a $n$ , per l'ipotesi induttiva fanno $\frac{n ( n + 1 )}{2}$ . Quindi il lato sinistro è $\frac{n ( n + 1 )}{2} + (n + 1)$ .
Il primo pezzo è $(n + 1)$ per $\frac{n}{2}$ , il secondo è $(n + 1)$ per 1. Raccogliamo il fattore comune $n + 1$ : viene $(n + 1) (\frac{n}{2} + 1)$ .
Dentro la parentesi, $\frac{n}{2} + 1 = \frac{n}{2} + \frac{2}{2} = \frac{n + 2}{2}$ .
Quindi il lato sinistro è $\frac{( n + 1 ) ( n + 2 )}{2}$ : proprio il lato destro dell'obiettivo.

Conclusione. Passo base e passo induttivo funzionano. Per il principio di induzione la formula vale per ogni $n \geq 1$ .

Ripasso · raccogliere un fattore comune

Se due addendi hanno lo stesso fattore, lo si può «tirare fuori»: $a \cdot b + a \cdot c = a \cdot (b + c)$ . Con i numeri: $3 \cdot 4 + 3 \cdot 5 = 12 + 15 = 27$ , e anche $3 \cdot (4 + 5) = 3 \cdot 9 = 27$ . Nel passo 2 qui sopra il fattore comune è $n + 1$ .

L'esempio del libro: la somma dei quadrati

Il libro fa la stessa cosa con i quadrati. Prima una scrittura che usa per le somme lunghe.

Ripasso · il simbolo di sommatoria

Una somma lunga si scrive con la lettera greca $Σ$ , «sigma» maiuscola. La scrittura $\sum_{k = 1}^{n} F (k)$ si legge «somma per $k$ che va da 1 a $n$ di $F (k)$ ». Vuol dire $F (1) + F (2) + \dots + F (n)$ : al posto di $k$ metti 1, poi 2, e così via fino a $n$ , e sommi tutto. Per esempio $\sum_{k = 1}^{3} k^{2} = 1^{2} + 2^{2} + 3^{2} = 1 + 4 + 9 = 14$ .

La formula del libro è

k = 1 \sum n k^{2} = 1^{2} + 2^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}

Prima la controlliamo con i numeri piccoli.

$n$	Somma dei quadrati	$\frac{n ( n + 1 ) ( 2 n + 1 )}{6}$
1	$1$	$\frac{1 \cdot 2 \cdot 3}{6} = 1$
2	$1 + 4 = 5$	$\frac{2 \cdot 3 \cdot 5}{6} = 5$
3	$1 + 4 + 9 = 14$	$\frac{3 \cdot 4 \cdot 7}{6} = 14$

Esempio · La somma dei quadrati per induzione (pp. 6–7)

Passo base. Per $n = 1$ : a sinistra $1^{2} = 1$ , a destra $\frac{1 \cdot 2 \cdot 3}{6} = 1$ .

Ipotesi induttiva. La formula vale per $n$ : $1^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ .

Obiettivo. Con $n + 1$ al posto di $n$ la formula diventa

1^{2} + \dots + (n + 1)^{2} = \frac{( n + 1 ) ( n + 2 ) ( 2 n + 3 )}{6}

perché $(n + 1) + 1 = n + 2$ e $2 (n + 1) + 1 = 2 n + 3$ .

Passo induttivo.

Per l'ipotesi induttiva il lato sinistro è $\frac{n ( n + 1 ) ( 2 n + 1 )}{6} + (n + 1)^{2}$ .
Raccogliamo $n + 1$ , che sta in tutti e due gli addendi: $(n + 1) (\frac{n ( 2 n + 1 )}{6} + (n + 1))$ .
Nella parentesi mettiamo tutto su 6: $\frac{2 n ^{2} + n}{6} + \frac{6 n + 6}{6} = \frac{2 n ^{2} + 7 n + 6}{6}$ .
Controlliamo che $(n + 2) (2 n + 3) = 2 n^{2} + 3 n + 4 n + 6 = 2 n^{2} + 7 n + 6$ .
Quindi il lato sinistro è $\frac{( n + 1 ) ( n + 2 ) ( 2 n + 3 )}{6}$ , che è l'obiettivo.

Conclusione. Per il principio di induzione la formula vale per ogni $n \geq 1$ .

Metodo · Dimostrare una formula per induzione

Scrivi la formula e da quale numero parte: 0, 1 o un altro.
Passo base. Metti il primo numero nei due lati e controlla che vengano uguali.
Ipotesi induttiva. Scrivi «supponiamo che la formula valga per $n$ », con la formula.
Obiettivo. Riscrivi la formula con $n + 1$ al posto di $n$ , e semplifica i conti come $(n + 1) + 1 = n + 2$ .
Passo induttivo. Parti dal lato sinistro dell'obiettivo. Trova il pezzo che compare nell'ipotesi e sostituiscilo. Poi fai i conti fino al lato destro.
Conclusione. Scrivi «per il principio di induzione la formula vale per ogni $n$ », dal numero di partenza in poi.

Prova tu

Controlla la formula

1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

per

n = 1, 2, 3, 4

. La dimostrazione completa è l'esercizio 6.

L'ultimo numero della somma è $2 n - 1$ : per $n = 4$ è 7.

Per $n = 1$ a sinistra c'è solo 1, e $1^{2} = 1$ .

Per $n = 2$ : $1 + 3 = 4 = 2^{2}$ .

Per $n = 3$ : $1 + 3 + 5 = 9 = 3^{2}$ .

Per $n = 4$ : $1 + 3 + 5 + 7 = 16 = 4^{2}$ .

Da ricordare

Prima si controlla la formula con i numeri piccoli, poi la si dimostra per induzione.
Nel passo induttivo si parte dal lato sinistro con $n + 1$ , si usa l'ipotesi induttiva e si arriva al lato destro.

§8

Quanti sottoinsiemi ha un insieme

p. 7

In pizzeria puoi aggiungere alla margherita tre ingredienti: olive, funghi, basilico. Puoi prenderne quanti vuoi, anche nessuno o tutti e tre. Quante pizze diverse puoi ordinare?

Per ogni ingrediente la scelta è doppia: lo metti o non lo metti. Tre scelte da due possibilità l'una danno $2 \cdot 2 \cdot 2 = 8$ pizze. Ogni pizza è un sottoinsieme dell'insieme degli ingredienti: la margherita semplice è il vuoto, la pizza con tutto è l'insieme intero.

Contiamo i sottoinsiemi di insiemi sempre più grandi.

Insieme	I suoi sottoinsiemi	Quanti
$\emptyset$	$\emptyset$	$1$
${a}$	$\emptyset$ , ${a}$	$2$
${a, b}$	$\emptyset$ , ${a}$ , ${b}$ , ${a, b}$	$4$
${a, b, c}$	i quattro di prima, più gli stessi con dentro anche $c$	$8$

Ogni volta che si aggiunge un elemento, il numero dei sottoinsiemi raddoppia: 1, 2, 4, 8, 16 e così via. Sono le potenze di 2.

Ripasso · le potenze di 2

$2^{n}$ si legge «due alla $n$ » e vuol dire 2 moltiplicato per sé stesso $n$ volte. Per convenzione $2^{0} = 1$ .

$n$	0	1	2	3	4	5	6	10
$2^{n}$	1	2	4	8	16	32	64	1024

Passando da $n$ a $n + 1$ si moltiplica per 2: $2^{n + 1} = 2 \cdot 2^{n}$ .

Perché raddoppia

Prendi i sottoinsiemi di ${a, b, c}$ e dividili in due righe. In alto metti quelli senza $c$ . In basso, sotto ognuno, lo stesso insieme con $c$ in più.

Senza $c$	$\emptyset$	${a}$	${b}$	${a, b}$
Con $c$	${c}$	${a, c}$	${b, c}$	${a, b, c}$

La riga in alto contiene esattamente i sottoinsiemi di ${a, b}$ , che sono 4. La riga in basso ne ha altrettanti, perché ognuno nasce da quello sopra aggiungendo $c$ . In tutto $4 + 4 = 8$ .

L'idea

Un insieme con $n$ elementi ha $2^{n}$ sottoinsiemi. Con i simboli: se $∣ A ∣ = n$ , allora $∣ P (A)∣ = 2^{n}$ .

Esempio · La dimostrazione per induzione del libro (p. 7)

La proprietà è «ogni insieme con $n$ elementi ha $2^{n}$ sottoinsiemi». Parte da $n = 0$ .

Passo base. L'unico insieme con 0 elementi è il vuoto. Il suo unico sottoinsieme è il vuoto stesso: $P (\emptyset) = {\emptyset}$ ha 1 elemento, e $2^{0} = 1$ .

Ipotesi induttiva. Ogni insieme con $n$ elementi ha $2^{n}$ sottoinsiemi.

Passo induttivo. Prendi un insieme con $n + 1$ elementi e chiamali $a_{1}, a_{2}, \dots, a_{n + 1}$ . Il numerino in basso, l'indice, dice solo il posto nella lista: $a_{1}$ è il primo elemento, $a_{n + 1}$ l'ultimo.

Dividi i sottoinsiemi in due righe: in alto quelli che non contengono l'ultimo elemento, in basso quelli che lo contengono.
La riga in alto contiene i sottoinsiemi di $B = {a_{1}, \dots, a_{n}}$ , che ha $n$ elementi. Per l'ipotesi induttiva sono $2^{n}$ .
Sotto ogni insieme della riga in alto c'è lo stesso insieme con in più $a_{n + 1}$ . Quindi la riga in basso ha tanti insiemi quanti quella in alto: altri $2^{n}$ .
In tutto sono $2^{n} + 2^{n} = 2 \cdot 2^{n} = 2^{n + 1}$ .

È la formula con $n + 1$ al posto di $n$ . Per il principio di induzione vale per ogni $n$ .

Oltre il libro · un altro modo di contare: i bit

Metti in fila gli elementi, per esempio $a$ , $b$ , $c$ . A ogni sottoinsieme associa una parola di tre cifre, ognuna 0 oppure 1. La prima cifra dice se $a$ c'è (1) o no (0), la seconda fa lo stesso per $b$ , la terza per $c$ . Per esempio $101$ è ${a, c}$ e $000$ è il vuoto. Sottoinsiemi diversi danno parole diverse, e ogni parola dà un sottoinsieme. Le parole di $n$ cifre fatte di 0 e 1 sono $2^{n}$ : è lo stesso conto che si fa con i bit nella lezione 01 di Fondamenti dell'Informatica.

Contare con una condizione: un problema d'esame

Nei problemi d'esame il conto dei sottoinsiemi arriva spesso con una condizione.

Esempio · Un problema dell'appello del 09/06/2023 (problema 1, primo punto)

Il testo: «Sia $S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ , $T = {0, 1, 3, 4}$ . Quanti sono i sottoinsiemi di $S$ non contenenti il sottoinsieme $T$ ?» (3 punti).

In pratica chiede: quanti sottoinsiemi di $S$ non hanno dentro tutti e quattro i numeri 0, 1, 3 e 4?

Tutti i sottoinsiemi. $S$ ha 10 elementi, quindi ha $2^{10} = 1024$ sottoinsiemi.
Quelli che contengono $T$ . Devono avere dentro 0, 1, 3 e 4. Gli altri sei elementi, cioè 2, 5, 6, 7, 8 e 9, si possono mettere o no a piacere. Sono 6 scelte libere, quindi questi sottoinsiemi sono $2^{6} = 64$ .
Quelli che non contengono $T$ sono tutti gli altri: $1024 - 64 = 960$ .

La soluzione ufficiale scrive il risultato come $2^{10} - 2^{6}$ : in alcuni appelli il testo chiede proprio di lasciare indicate le potenze.

Prova tu

(a) Quanti sottoinsiemi ha

{1, 2, 3, 4, 5}

? (b) Quanti di questi contengono il numero 1?

(a) Gli elementi sono 5, quindi i sottoinsiemi sono $2^{5} = 32$ .

(b) L'1 deve esserci. Per gli altri quattro elementi la scelta è libera: $2^{4} = 16$ . È esattamente la metà: è la riga «con» della tabella divisa in due righe.

Da ricordare

Un insieme con $n$ elementi ha $2^{n}$ sottoinsiemi: per ogni elemento la scelta è «dentro» o «fuori».
Per contare i sottoinsiemi che contengono certi elementi, si fissano quelli e si sceglie liberamente il resto.

§9

Gli altri insiemi di numeri

p. 8

Dai numeri naturali, con le regole degli insiemi, si costruiscono le altre famiglie di numeri che conosci. Il libro le elenca nella Nota 1.12 e le considera note: la loro costruzione non fa parte del corso.

Simbolo	Si legge	Che cosa contiene	Esempi
$Z$	«zeta»	gli interi: i naturali e i loro opposti	$- 5$ , $0$ , $7$
$Q$	«cu»	i razionali: le frazioni $\frac{a}{b}$ con $a$ e $b$ interi, e $b \neq = 0$	$\frac{1}{2}$ , $- \frac{3}{4}$
$R$	«erre»	i reali: anche i numeri con infinite cifre dopo la virgola	$2$ , $π$

Ogni famiglia contiene la precedente: ogni naturale è un intero, ogni intero è una frazione, ogni frazione è un numero reale. Con i simboli: $N \subset Z \subset Q \subset R$ . Ne parla per esteso la lezione L01 della parte 2, Algebra lineare e Geometria.

Il libro ricorda anche due scritture per i numeri reali compresi tra due numeri $a$ e $b$ , con $a$ minore o uguale a $b$ .

$(a, b)$ è l'intervallo aperto: i numeri compresi tra $a$ e $b$ , estremi esclusi.
$[a, b]$ è l'intervallo chiuso: i numeri compresi tra $a$ e $b$ , estremi compresi.

Prova tu

(a)

- 3

sta in

N

? E in

Z

? (b) Il numero 2 sta in

(1, 2)

? E in

[1, 2]

(a) $- 3$ non è un naturale, perché i naturali non sono mai negativi. È un intero, quindi $- 3 \in Z$ .

(b) $2 \in / (1, 2)$ , perché nell'intervallo aperto gli estremi sono esclusi. $2 \in [1, 2]$ , perché nell'intervallo chiuso gli estremi sono compresi.

Da ricordare

$N$ naturali, $Z$ interi, $Q$ frazioni, $R$ reali: ogni famiglia contiene la precedente.
Tonde: estremi esclusi. Quadre: estremi compresi.

§10

I simboli di questa lezione

Simbolo	Si legge	Vuol dire	Esempio
${}$	«l'insieme che contiene…»	le graffe racchiudono gli elementi	${1, 2, 3}$
$\in$	«appartiene a»	è un elemento di	$2 \in {1, 2, 3}$
$\in /$	«non appartiene a»	non è un elemento di	$5 \in / {1, 2, 3}$
$\dots$	«e così via»	gli elementi continuano con la stessa regola	${0, 2, 4, \dots}$
$∣$	«tali che»	introduce la regola per entrare nell'insieme	${n \in N ∣ n < 3}$
$P (x)$	«pi di $x$ »	una proprietà di $x$ , vera o falsa	« $x$ è pari»
$\forall$	«per ogni»	per tutti gli elementi, nessuno escluso	$\forall n \in N, n \geq 0$
$\exists$	«esiste»	ce n'è almeno uno	$\exists n \in N$ con $n > 5$
$\sim$ , $\neg$	«non»	il contrario di una frase	$\sim (x \geq 0)$ vuol dire $x < 0$
$\emptyset$	«insieme vuoto»	l'insieme senza elementi	$∣ \emptyset ∣ = 0$
$∣ A ∣$	«cardinalità di $A$ »	il numero degli elementi di $A$	$∣{a, b}∣ = 2$
$\infty$	«infinito»	la cardinalità di un insieme infinito	$∣ N ∣ = \infty$
$\subset$	«è contenuto in»	è un sottoinsieme (può anche essere uguale)	${1} \subset {1, 2}$
$\neq \subset$	«non è contenuto in»	almeno un elemento sta fuori	${1, 4} \neq \subset {1, 2}$
$\subseteq$ , $⊊$	«contenuto o uguale», «contenuto strettamente»	le scritture di altri testi e dei canali A e C	${1} ⊊ {1, 2}$
$P (A)$	«parti di $A$ »	l'insieme di tutti i sottoinsiemi di $A$	$P ({a}) = {\emptyset, {a}}$
$⟺$	«se e solo se»	esattamente quando	$A = B ⟺ A \subset B$ e $B \subset A$
$N$	«enne»	i numeri naturali, zero compreso	$0, 1, 2, \dots$
$s (n)$	«esse di $n$ »	il successivo di $n$	$s (4) = 5$
$P (n)$	«pi di $n$ »	una proprietà che dipende dal numero $n$	« $n + n$ è pari»
$\sum_{k = 1}^{n}$	«somma per $k$ da 1 a $n$ »	somma dei termini con $k = 1, 2, \dots, n$	$\sum_{k = 1}^{3} k = 6$
$a_{1}, \dots, a_{n}$	«a uno, …, a enne»	un elenco di $n$ oggetti numerati	$a_{1}$ è il primo
$2^{n}$	«due alla $n$ »	2 moltiplicato per sé stesso $n$ volte	$2^{3} = 8$
$Z$ , $Q$ , $R$	«zeta», «cu», «erre»	interi, razionali, reali	$- 3 \in Z$
$(a, b)$ , $[a, b]$	«intervallo aperto», «intervallo chiuso»	i reali tra $a$ e $b$ , estremi esclusi o compresi	$2 \in [1, 2]$

§11

Verso l'esame

esame

La prova di Matematica Discreta, la parte 1 di MDAG, è scritta ed è la stessa per i canali A, B e C: la preparano e la correggono insieme i docenti dei tre canali. Al 01/10/2026 le regole del 2026/27 non sono ancora uscite. Quelle del 2025/26 dicono così.

Com'è fatta la prova

10 domande a risposta multipla, ognuna con 5 risposte e una sola giusta. Una risposta giusta vale 1 punto; una sbagliata o vuota vale 0.
2 problemi a risposta aperta, divisi in più domande con il punteggio scritto accanto.
Sbarramento. Con meno di 6 punti nel quiz la prova non è superata, e i problemi non vengono nemmeno corretti.
Sufficienza: almeno 18 punti in tutto. Durata: 2 ore.
Materiale ammesso: libro di testo e appunti del corso, e una calcolatrice non programmabile. È diverso dalla prova di Algebra lineare, dove si possono portare solo 4 facciate scritte a mano e niente calcolatrice.

Appello 2026/27	Iscrizioni su MyUniTo (appello «M.D.A.G.1»)	Ora
mar 19/01/2027	30/12/2026 – 12/01/2027	14:00
mer 03/02/2027	14/01 – 27/01/2027	14:00

Le iscrizioni chiudono circa una settimana prima e non si riaprono. Il voto di MDAG è la media delle due prove, Matematica Discreta e Algebra lineare. Dettagli e fonti nella scheda del corso.

Che cosa serve di questa lezione

La domanda 1 del quiz. In tutti i nove appelli del 2025 e del 2026 di cui ho trovato il quiz, la prima domanda riguarda gli insiemi. A volte basta questa lezione: elementi e sottoinsiemi, come il 13/01/2026 e il 10/09/2026. A volte servono anche unione, intersezione e prodotto cartesiano, che arrivano nella prossima lezione. Quasi sempre le risposte sbagliate giocano sulla differenza tra elemento e sottoinsieme.
«Per ogni» ed «esiste». Nell'appello del 06/06/2025 la domanda 2 chiedeva un controesempio. È l'esempio svolto nella sezione sui quantificatori.
Contare i sottoinsiemi. Nei problemi torna il conto delle potenze di 2, spesso con una condizione: appelli del 09/06/2023 (problema 1, primo punto) e del 06/06/2025 (problema 1, punto b).
L'induzione. Negli appelli di Matematica Discreta dal 2021 al 2026 non ho trovato domande che chiedano di scrivere una dimostrazione per induzione: serve per capire le dimostrazioni del libro. A Fondamenti dell'Informatica, invece, il principio di induzione è tra gli argomenti dei quiz.

Una domanda vera, letta insieme

Esempio · Appello del 13/01/2026, domanda 1 (una delle versioni)

Il testo: «Sia $A = {b, e, h, k, m, p, q, s, u, x}$ . Allora: 1. $t \in A$ ; 2. $h \in / A$ ; 3. ${h, s} \in A$ ; 4. ${k, q, u} \subset A$ ; 5. ${e, s, y} \subset A$ .»

In pratica chiede: quale delle cinque frasi è vera? $A$ ha dieci elementi, e sono tutti lettere, nessuno è un insieme. Vediamo le risposte una per una.

$t \in A$ : la lettera $t$ non è nella lista. Falsa.
$h \in / A$ : la lettera $h$ è nella lista, quindi appartiene ad $A$ . Falsa.
${h, s} \in A$ : gli elementi di $A$ sono lettere, e l'insieme ${h, s}$ non è tra loro. Falsa. Sarebbe vera la frase ${h, s} \subset A$ .
${k, q, u} \subset A$ : le lettere $k$ , $q$ e $u$ sono tutte nella lista. Vera.
${e, s, y} \subset A$ : la lettera $y$ non è nella lista. Falsa.

La risposta è la 4. La trappola è la 3: le lettere $h$ e $s$ ci sono, ma le graffe e il simbolo di appartenenza chiedono un'altra cosa.

Errori da evitare

Confondere «è un elemento di» con «è un sottoinsieme di». Usa il metodo della sezione sui sottoinsiemi.
Contare due volte un elemento ripetuto, oppure contare uno per uno gli elementi chiusi dentro graffe interne.
Dimenticare il vuoto e l'insieme intero quando elenchi i sottoinsiemi.
Dire il contrario di «tutti» con «nessuno».
Nel passo induttivo, usare la formula per $n + 1$ invece di arrivarci.

Conta all'esame · Libro e appunti sono ammessi, ma il tempo è poco

Alla prova di Matematica Discreta puoi portare libro e appunti. Le ore però sono solo 2, per 10 domande e 2 problemi: non c'è tempo per cercare le cose. Conviene preparare un foglio di riepilogo. Da questa lezione: il metodo «elemento o sottoinsieme?» e il conto dei sottoinsiemi con una condizione. Un riepilogo già pronto, scritto da uno studente seguendo il libro di Mori, è Rigurgiti di Unicorno: teoria ed esercizi svolti, con licenza CC BY-NC-SA. Non è materiale ufficiale.

§13

Esercizi

con soluzioni

1 · Dall'elenco alla regola e ritorno base

Scrivi con l'elenco: (a) ${n \in N ∣ n < 5}$ ; (b) ${n \in N ∣ n \overset{e}{ˋ} dispari e n < 10}$ . Scrivi con una regola: (c) ${0, 3, 6, 9, 12}$ .

Soluzione

(a) I naturali minori di 5 sono 0, 1, 2, 3 e 4. L'insieme è ${0, 1, 2, 3, 4}$ . Lo zero c'è, perché nel libro è un naturale.
(b) I numeri dispari minori di 10 sono 1, 3, 5, 7 e 9. L'insieme è ${1, 3, 5, 7, 9}$ .
(c) Sono i multipli di 3 da 0 a 12. Una regola possibile: ${n \in N ∣ n \overset{e}{ˋ} multiplo di 3 e n \leq 12}$ .

Controllo della (c): i multipli di 3 fino a 12 sono $3 \cdot 0$ , $3 \cdot 1$ , $3 \cdot 2$ , $3 \cdot 3$ e $3 \cdot 4$ , cioè proprio 0, 3, 6, 9 e 12.

2 · Contare gli elementi base

Calcola la cardinalità: (a) ${x, y, x, z}$ ; (b) ${{x, y}, z}$ ; (c) ${\emptyset, 0}$ ; (d) $P ({1, 2, 3})$ .

Soluzione

(a) Gli elementi sono $x$ , $y$ e $z$ : la $x$ ripetuta si conta una volta. La cardinalità è 3.
(b) Gli elementi sono due: l'insieme ${x, y}$ e la lettera $z$ . La cardinalità è 2.
(c) Gli elementi sono due: il vuoto e il numero zero, che sono oggetti diversi. La cardinalità è 2.
(d) L'insieme ha 3 elementi, quindi i suoi sottoinsiemi sono $2^{3} = 8$ . La cardinalità è 8.

3 · Esercizio 1.1 del libro: vero o falso base

Prendi $A = {a, b, c}$ . Di' quali di queste affermazioni sono vere e quali false: $b \in A$ , $\emptyset \subset A$ , ${\emptyset} \subset A$ , ${c, d} \neq \subset A$ , ${a, {c}} \subset A$ .

Soluzione

Affermazione	Vera o falsa	Perché
$b \in A$	vera	la lettera $b$ è nella lista
$\emptyset \subset A$	vera	il vuoto è un sottoinsieme di ogni insieme
${\emptyset} \subset A$	falsa	servirebbe che il vuoto fosse un elemento di $A$ , ma gli elementi sono le lettere $a$ , $b$ , $c$
${c, d} \neq \subset A$	vera	la lettera $d$ non sta in $A$ , quindi ${c, d}$ non è contenuto in $A$
${a, {c}} \subset A$	falsa	$a$ sta in $A$ , ma l'insieme ${c}$ no: in $A$ c'è la lettera $c$ , non l'insieme ${c}$

La terza e la quinta riga sono la stessa trappola: un insieme dentro le graffe è un elemento diverso dai suoi elementi.

4 · Esercizio 1.3 del libro: l'insieme delle parti base

Prendi $A = {a, e, i, o, u}$ . Di' quali di queste affermazioni sono vere e quali false: $\emptyset \in P (A)$ , $a \in P (A)$ , ${i, u} \subset P (A)$ , ${e, o} \in P (A)$ , ${{e}, {o}} \subset P (A)$ .

Soluzione

Ricorda: gli elementi di $P (A)$ sono i sottoinsiemi di $A$ .

Affermazione	Vera o falsa	Perché
$\emptyset \in P (A)$	vera	il vuoto è un sottoinsieme di $A$ , quindi un elemento di $P (A)$
$a \in P (A)$	falsa	$a$ è una lettera, non un sottoinsieme di $A$
${i, u} \subset P (A)$	falsa	servirebbe che $i$ e $u$ fossero elementi di $P (A)$ , ma sono lettere
${e, o} \in P (A)$	vera	${e, o}$ è un sottoinsieme di $A$
${{e}, {o}} \subset P (A)$	vera	i suoi due elementi, ${e}$ e ${o}$ , sono sottoinsiemi di $A$ , quindi elementi di $P (A)$

Nella terza riga sarebbe vera la frase ${i, u} \in P (A)$ .

5 · Dire il contrario base

Scrivi il contrario di queste frasi, e di' se è vera la frase o il suo contrario: (a) «ogni numero naturale è pari»; (b) «esiste un numero naturale maggiore di 100»; (c) «per ogni numero naturale $n$ esiste un naturale più grande di $n$ ».

Soluzione

(a) Il contrario è «esiste un numero naturale dispari». È vero il contrario: 3 è dispari, ed è il controesempio della frase di partenza.
(b) Il contrario è «ogni numero naturale è minore o uguale a 100». È vera la frase di partenza: per esempio 101 è maggiore di 100.
(c) Ci sono due quantificatori, e cambiano tutti e due: «per ogni» diventa «esiste» ed «esiste» diventa «per ogni». Il contrario è «esiste un numero naturale $n$ per cui ogni naturale è minore o uguale a $n$ ». È vera la frase di partenza: qualunque $n$ prendi, il numero $n + 1$ è più grande.

6 · Esercizio 1.19 (b) del libro: la somma dei dispari medio

Dimostra per induzione che $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ per ogni $n \geq 1$ .

Soluzione

Passo base, $n = 1$ . A sinistra c'è solo 1. A destra $1^{2} = 1$ . I due lati sono uguali.
Ipotesi induttiva. Supponiamo $1 + 3 + \dots + (2 n - 1) = n^{2}$ .
Obiettivo. Con $n + 1$ al posto di $n$ , l'ultimo numero della somma è $2 (n + 1) - 1 = 2 n + 1$ . Vogliamo arrivare a $1 + 3 + \dots + (2 n - 1) + (2 n + 1) = (n + 1)^{2}$ .
Passo induttivo. Per l'ipotesi, la somma fino a $2 n - 1$ vale $n^{2}$ . Quindi il lato sinistro è $n^{2} + 2 n + 1$ .
Il quadrato di $n + 1$ è $(n + 1) (n + 1) = n^{2} + n + n + 1 = n^{2} + 2 n + 1$ . È lo stesso numero del passo 4, quindi il lato sinistro è $(n + 1)^{2}$ .
Conclusione. Per il principio di induzione la formula vale per ogni $n \geq 1$ .

Controllo con $n = 5$ : $1 + 3 + 5 + 7 + 9 = 25 = 5^{2}$ .

7 · Esercizio 1.19 (d) del libro: una disuguaglianza medio

Dimostra per induzione che $n^{2} > 2 n + 1$ per ogni $n \geq 3$ .

Soluzione

Passo base, $n = 3$ . A sinistra $3^{2} = 9$ , a destra $2 \cdot 3 + 1 = 7$ . Ed è vero che $9 > 7$ . Con $n = 2$ invece non funziona: $4 > 5$ è falso. Per questo si parte da 3.
Ipotesi induttiva. Supponiamo $n^{2} > 2 n + 1$ , per un certo $n \geq 3$ .
Obiettivo. $(n + 1)^{2} > 2 (n + 1) + 1$ , cioè $(n + 1)^{2} > 2 n + 3$ .
Il quadrato è $(n + 1)^{2} = n^{2} + 2 n + 1$ .
Per l'ipotesi $n^{2}$ è più grande di $2 n + 1$ . Quindi $n^{2} + 2 n + 1$ è più grande di $(2 n + 1) + 2 n + 1 = 4 n + 2$ .
Ora confrontiamo $4 n + 2$ con l'obiettivo $2 n + 3$ . La differenza è $(4 n + 2) - (2 n + 3) = 2 n - 1$ , che è positiva per ogni $n \geq 1$ . Quindi $4 n + 2 > 2 n + 3$ .
Mettendo insieme i passi 5 e 6: $(n + 1)^{2} > 4 n + 2 > 2 n + 3$ .
Conclusione. Per il principio di induzione la disuguaglianza vale per ogni $n \geq 3$ .

Controllo: con $n = 4$ , $16 > 9$ ; con $n = 5$ , $25 > 11$ .

8 · Esercizio 1.19 (e) del libro: le potenze di 2 battono i quadrati difficile

Dimostra per induzione che $2^{n} > n^{2}$ per ogni $n \geq 5$ .

Soluzione

Passo base, $n = 5$ . A sinistra $2^{5} = 32$ , a destra $5^{2} = 25$ . Ed è vero che $32 > 25$ . Con $n = 4$ non funziona: $2^{4} = 16$ e $4^{2} = 16$ sono uguali.
Ipotesi induttiva. Supponiamo $2^{n} > n^{2}$ , per un certo $n \geq 5$ .
Obiettivo. $2^{n + 1} > (n + 1)^{2}$ .
Raddoppiare una potenza di 2 vuol dire aggiungere 1 all'esponente: $2^{n + 1} = 2 \cdot 2^{n}$ . Per l'ipotesi $2^{n}$ è più grande di $n^{2}$ , quindi $2 \cdot 2^{n}$ è più grande di $2 n^{2}$ .
Scriviamo $2 n^{2} = n^{2} + n^{2}$ . Per l'esercizio precedente, siccome $n \geq 3$ , vale $n^{2} > 2 n + 1$ . Quindi $n^{2} + n^{2} > n^{2} + 2 n + 1$ .
E $n^{2} + 2 n + 1 = (n + 1)^{2}$ , come nell'esercizio 6.
Mettendo insieme: $2^{n + 1} > 2 n^{2} > (n + 1)^{2}$ .
Conclusione. Per il principio di induzione la disuguaglianza vale per ogni $n \geq 5$ .

Controllo: con $n = 6$ , $2^{6} = 64 > 36$ ; con $n = 10$ , $2^{10} = 1024 > 100$ .

9 · Esercizio 1.19 (c) del libro: la somma dei cubi difficile

Dimostra per induzione che $1^{3} + 2^{3} + \dots + n^{3} = \frac{n ^{2} ( n + 1 ) ^{2}}{4}$ per ogni $n \geq 1$ .

Soluzione

Passo base, $n = 1$ . A sinistra $1^{3} = 1$ . A destra $\frac{1 \cdot 4}{4} = 1$ .
Ipotesi induttiva. Supponiamo $1^{3} + \dots + n^{3} = \frac{n ^{2} ( n + 1 ) ^{2}}{4}$ .
Obiettivo. $1^{3} + \dots + (n + 1)^{3} = \frac{( n + 1 ) ^{2} ( n + 2 ) ^{2}}{4}$ .
Per l'ipotesi il lato sinistro è $\frac{n ^{2} ( n + 1 ) ^{2}}{4} + (n + 1)^{3}$ .
In tutti e due gli addendi c'è $(n + 1)^{2}$ , perché $(n + 1)^{3} = (n + 1)^{2} \cdot (n + 1)$ . Raccogliendo: $(n + 1)^{2} (\frac{n ^{2}}{4} + n + 1)$ .
Nella parentesi mettiamo tutto su 4: $\frac{n ^{2}}{4} + \frac{4 n}{4} + \frac{4}{4} = \frac{n ^{2} + 4 n + 4}{4}$ .
E $n^{2} + 4 n + 4 = (n + 2)^{2}$ , perché $(n + 2) (n + 2) = n^{2} + 2 n + 2 n + 4$ .
Quindi il lato sinistro è $\frac{( n + 1 ) ^{2} ( n + 2 ) ^{2}}{4}$ , l'obiettivo.
Conclusione. Per il principio di induzione la formula vale per ogni $n \geq 1$ .

Controllo con $n = 3$ : $1 + 8 + 27 = 36$ , e $\frac{9 \cdot 16}{4} = 36$ .

10 · Sottoinsiemi con una condizione tipo esame

Prendi $S = {1, 2, 3, 4, 5, 6, 7, 8}$ . (a) Quanti sono i sottoinsiemi di $S$ ? (b) Quanti contengono sia 1 sia 2? (c) Quanti non contengono il sottoinsieme ${1, 2}$ ? (d) Quanti non contengono né 1 né 2?

Soluzione

(a) $S$ ha 8 elementi, quindi i sottoinsiemi sono $2^{8} = 256$ .
(b) 1 e 2 devono esserci. Gli altri sei elementi, da 3 a 8, si scelgono liberamente: $2^{6} = 64$ .
(c) Sono tutti i sottoinsiemi tranne quelli del punto (b): $256 - 64 = 192$ .
(d) Né 1 né 2: si sceglie liberamente solo tra i sei elementi da 3 a 8. Sono $2^{6} = 64$ .

Controllo: dividiamo i sottoinsiemi secondo che cosa succede a 1 e a 2. Ci sono quattro casi: tutti e due dentro, solo 1, solo 2, nessuno dei due. In ogni caso gli altri sei elementi sono liberi, quindi ogni caso ha 64 sottoinsiemi. In tutto $4 \cdot 64 = 256$ , come al punto (a). I sottoinsiemi del punto (c) sono gli ultimi tre casi: $3 \cdot 64 = 192$ .

§14

Domande di ripasso

autoverifica

Che cos'è un insieme? Che cosa vuol dire che deve essere «ben definito»?

Un insieme è una raccolta di oggetti diversi tra loro, i suoi elementi. «Ben definito» vuol dire che per ogni oggetto si può decidere senza dubbi se sta dentro o no: «gli attori bravi» non è un insieme, «gli attori che hanno vinto un Oscar» sì.

Perché

x \in A

{x} \subset A

dicono la stessa cosa? E perché

{x} \in A

dice un'altra cosa?

${x} \subset A$ vuol dire che l'unico elemento di ${x}$ , cioè $x$ , sta in $A$ : è proprio $x \in A$ . Invece ${x} \in A$ vuol dire che l'insieme ${x}$ , intero, è uno degli elementi di $A$ . Con $A = {1, 2}$ la prima frase è vera per $x = 1$ , la seconda è falsa.

Qual è il contrario di una frase con «per ogni»? E di una frase con «esiste»?

«Per ogni» diventa «esiste» ed «esiste» diventa «per ogni»; la proprietà diventa il suo contrario. Il contrario di «tutti i numeri della lista sono positivi» è «almeno un numero della lista non è positivo».

Che differenza c'è tra

\emptyset

{\emptyset}

$\emptyset$ è l'insieme vuoto e ha 0 elementi. ${\emptyset}$ è un insieme con un elemento, che è l'insieme vuoto: un sacchetto che contiene un sacchetto vuoto.

Perché il vuoto è un sottoinsieme di ogni insieme?

Per dire che non lo è servirebbe un elemento del vuoto che sta fuori dall'altro insieme. Il vuoto non ha elementi, quindi un controesempio così non esiste.

Come si dimostra che due insiemi sono uguali?

Con la doppia inclusione: si fa vedere che ogni elemento del primo sta nel secondo e che ogni elemento del secondo sta nel primo (proposizione 1.9).

Che cosa dice il principio di induzione? Che cosa sono il passo base e il passo induttivo?

Servono due controlli. Il passo base: la proprietà vale per il primo numero. Il passo induttivo: ogni volta che vale per un numero $n$ , vale anche per $n + 1$ . Allora la proprietà vale per tutti i numeri da lì in poi. È come una fila di tessere del domino.

Perché un insieme con

n

elementi ha

2^{n}

sottoinsiemi?

Per ogni elemento la scelta è doppia: dentro o fuori. Le scelte sono $n$ , e ognuna raddoppia il conto. Il libro lo dimostra per induzione: aggiungendo un elemento, i sottoinsiemi si dividono in quelli senza e quelli con il nuovo elemento, che sono tanti quanti i primi.

§15

Glossario

termini

Insieme: Una raccolta ben definita di oggetti diversi tra loro, i suoi elementi. Esempio: ${1, 2, 3}$ .
Elemento: Un oggetto che sta in un insieme. Si scrive $x \in A$ , « $x$ appartiene ad $A$ ».
Insieme universale: L'insieme da cui si pescano gli oggetti quando si descrive un insieme con una regola, per esempio $N$ .
Proprietà: Una frase su un oggetto che può essere vera o falsa, come « $n$ è pari».
Quantificatori: Le parole «per ogni» ed «esiste». I loro simboli, $\forall$ e $\exists$ , si leggono proprio così.
Controesempio: Un elemento per cui una frase con «per ogni» è falsa. Ne basta uno per smentirla.
Insieme vuoto: L'insieme senza elementi, $\emptyset$ . È un sottoinsieme di ogni insieme.
Cardinalità: Il numero degli elementi di un insieme, $∣ A ∣$ . Esempio: $∣{a, b}∣ = 2$ .
Sottoinsieme: Un insieme i cui elementi stanno tutti in un altro: $B \subset A$ . Esempio: ${1, 3} \subset {1, 2, 3}$ .
Sottoinsieme proprio: Un sottoinsieme diverso dall'insieme intero.
Insieme delle parti: L'insieme $P (A)$ che ha come elementi tutti i sottoinsiemi di $A$ . Se $A$ ha $n$ elementi, $P (A)$ ne ha $2^{n}$ .
Doppia inclusione: Il modo di dimostrare che due insiemi sono uguali: ognuno è contenuto nell'altro.
Numeri naturali: I numeri per contare, $0, 1, 2, 3, \dots$ ; il loro insieme è $N$ .
Successivo: Il numero che viene subito dopo: il successivo di $n$ è $n + 1$ , che il libro scrive $s (n)$ .
Principio di induzione: Se una proprietà vale per 0 e passa da ogni numero al successivo, vale per tutti i naturali.
Passo base: Il controllo della proprietà sul primo numero.
Passo induttivo: La dimostrazione che, se la proprietà vale per $n$ , vale anche per $n + 1$ .
Ipotesi induttiva: La frase «la proprietà vale per $n$ », che nel passo induttivo si suppone vera e si usa.

§16

Checklist

0 su 8

Spunta quando sai fare la cosa senza guardare gli appunti. Le spunte restano salvate in questo browser.

So scrivere un insieme con l'elenco e con una regola.
So distinguere $x \in A$ , ${x} \subset A$ e ${x} \in A$ .
So contare gli elementi di un insieme che contiene altri insiemi.
So dire il contrario di una frase con «per ogni» o «esiste», e trovare un controesempio.
So scrivere tutti i sottoinsiemi di un insieme con 3 elementi.
So dimostrare che due insiemi sono uguali con la doppia inclusione.
So fare una dimostrazione per induzione: passo base, ipotesi, passo induttivo, conclusione.
So contare i sottoinsiemi di un insieme, anche con una condizione come «contiene questi elementi».

La lezione in 8 punti

Un insieme è un sacchetto di oggetti

Dentro o fuori

Che cosa può stare in un insieme (p. 2)

Un sacchetto dentro un sacchetto

Due modi per scrivere un insieme (pp. 2–3)

Ordine e ripetizioni non contano (p. 3)

Tutti o almeno uno: per ogni ed esiste

Come si dice il contrario

Il controesempio

Il sacchetto vuoto e quanti elementi ci sono

Il vuoto dentro un sacchetto

Quanti elementi: la cardinalità

Un insieme dentro l'altro: i sottoinsiemi

Il vuoto e l'insieme intero

Elemento o sottoinsieme?

Tutte le parti di un insieme

Quando due insiemi sono uguali

I numeri per contare e l'induzione

Il domino

Partire da 1, o da un altro numero

Dimostrare per induzione, passo per passo

L'esempio del libro: la somma dei quadrati

Quanti sottoinsiemi ha un insieme

Perché raddoppia

Contare con una condizione: un problema d'esame

Gli altri insiemi di numeri

I simboli di questa lezione

Verso l'esame

Quiz

Esercizi

1 · Dall'elenco alla regola e ritorno base

2 · Contare gli elementi base

3 · Esercizio 1.1 del libro: vero o falso base

4 · Esercizio 1.3 del libro: l'insieme delle parti base

5 · Dire il contrario base

6 · Esercizio 1.19 (b) del libro: la somma dei dispari medio

7 · Esercizio 1.19 (d) del libro: una disuguaglianza medio

8 · Esercizio 1.19 (e) del libro: le potenze di 2 battono i quadrati difficile

9 · Esercizio 1.19 (c) del libro: la somma dei cubi difficile

10 · Sottoinsiemi con una condizione tipo esame

Domande di ripasso

Glossario

Checklist