Insiemi, relazioni e funzioni: esercizi con soluzioni passo passo

1Insiemi e operazioni tra insiemi

Un insieme è una collezione di elementi distinti: A = {1, 2, 3}. L’ordine e le ripetizioni non contano. |A| è il numero di elementi, e U è l’insieme universo che contiene tutto ciò di cui si parla.

• A ∪ B (unione): gli elementi in A o in B o in entrambi.
• A ∩ B (intersezione): gli elementi in entrambi.
• A − B (differenza): gli elementi di A che non sono in B.
• A′ (complementare): gli elementi di U che non sono in A.

In un diagramma di Venn due cerchi dividono U in quattro regioni: solo A, entrambi, solo B e nessuno dei due. Ogni espressione insiemistica è un’unione di alcune di queste regioni, quindi puoi sempre contarla regione per regione.

Qui |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 e |(A ∪ B)′| = 15.

2Conteggio con inclusione-esclusione

Sommare |A| e |B| conta due volte l’intersezione, quindi sottraila una volta:

Per tre insiemi si sottraggono le intersezioni a coppie, ma allora il centro è stato tolto tre volte, quindi lo si somma di nuovo:

Nei problemi a parole di solito è più sicuro riempire un diagramma di Venn dal centro verso l’esterno: prima gli elementi in tutti e tre gli insiemi, poi ogni coppia meno il centro, poi ogni insieme singolo meno ciò che è già stato collocato.

Altri due conteggi ricorrono spesso: un insieme con n elementi ha 2ⁿ sottoinsiemi (il suo insieme delle parti 𝒫(A)), e |A × B| = |A|·|B| coppie ordinate.

3Un esempio svolto

Segui ogni passaggio. Prova a prevedere il successivo prima di aprirlo.

4Relazioni

Una relazione R su un insieme X è un insieme di coppie ordinate (x, y) con x e y in X. Disegnata come grafo orientato, ogni coppia è una freccia e (x, x) è un cappio.

• Riflessiva: (x, x) ∈ R per ogni x: un cappio in ogni vertice.
• Simmetrica: (x, y) ∈ R comporta sempre (y, x) ∈ R.
• Antisimmetrica: (x, y) e (y, x) sono entrambe in R solo quando x = y.
• Transitiva: (x, y) e (y, z) in R implicano (x, z) ∈ R.

Una relazione riflessiva, simmetrica e transitiva è una relazione di equivalenza. Divide X in classi disgiunte, come i resti 0, 1 e 2 per “x ≡ y (mod 3)”. Una classe con s elementi contribuisce con s² coppie ordinate.

Per confutare una proprietà basta un controesempio; per dimostrarla, verifica ogni coppia.

5Funzioni

Una funzione f: A → B assegna a ogni elemento di A esattamente un’immagine in B.

• Iniettiva (uno a uno): elementi diversi hanno immagini diverse; nessun elemento di B riceve due frecce.
• Suriettiva (su): ogni elemento di B riceve almeno una freccia.
• Biiettiva: entrambe. Solo allora f ha un’inversa f⁻¹.

La funzione in figura è iniettiva ma non suriettiva: d non riceve alcuna freccia. Un’iniezione richiede |A| ≤ |B| e una suriezione |A| ≥ |B|.

Con |A| = m e |B| = n ci sono nᵐ funzioni e n!/(n − m)! funzioni iniettive. La composizione (g ∘ f)(x) = g(f(x)) applica prima f.

6Errori comuni

• Sommare |A| + |B| senza sottrarre l’intersezione.
• Dimenticare di sommare di nuovo il centro nell’inclusione-esclusione a tre insiemi.
• Scrivere mⁿ invece di nᵐ per il numero di funzioni da m elementi a n elementi.
• Pensare che una relazione non possa essere sia simmetrica sia antisimmetrica: la relazione {(1, 1)} è entrambe.
• Applicare g ∘ f nell’ordine sbagliato: agisce prima f.

7Come sono fatte le domande d’esame

• Facile: diagrammi di Venn e sottoinsiemi. Conti un’espressione insiemistica da un diagramma di Venn, clicchi la regione di un’espressione o trovi la dimensione di un insieme delle parti, di un prodotto cartesiano o di una famiglia di sottoinsiemi.
• Medio: inclusione-esclusione e relazioni. Risolvi problemi di conteggio con due e tre insiemi, conti espressioni a partire dai totali delle regioni, decidi quale proprietà ha una relazione o conti le coppie necessarie per una chiusura.
• Difficile: funzioni e conteggio. Classifichi una funzione come iniettiva, suriettiva o biiettiva, conti funzioni, iniezioni e suriezioni, calcoli composizioni e inverse e conti le coppie nelle relazioni di equivalenza.