Una raccolta avanzata: i primi problemi lavorano sulle regioni di Venn, gli ultimi su famiglie di sottoinsiemi, immagini di funzioni e insiemi infiniti. Ogni soluzione è inizialmente nascosta. |A| indica la cardinalità, A∖B gli elementi di A non appartenenti a B, AΔB=(A∖B)∪(B∖A) la differenza simmetrica, 𝒫(A) l’insieme di tutti i sottoinsiemi di A. C(n,k) conta le scelte di k elementi fra n. Le intersezioni tra due insiemi comprendono anche gli eventuali elementi dell’intersezione tripla. Le aree delle figure sono schematiche, non proporzionali alle cardinalità.
- Ricostruire otto regioni da dati sovrapposti
- Quali intersezioni triple sono possibili?
- Le distanze simmetriche non raccontano tutto
- Semplificare una differenza simmetrica annidata
- Un insieme incognito con vincoli e cardinalità
- L’insieme delle parti non distribuisce sull’unione
- Quattro insiemi: un archivio impossibile
- Quando l’immagine conserva l’intersezione
- Una famiglia enorme senza elemento comune
- Appartenere infinite volte non significa restare per sempre
1. Ricostruire otto regioni da dati sovrapposti
In un universo U di 120 elementi, |A|=70, |B|=65, |C|=60. Inoltre |A∩B|=40, |A∩C|=35, |B∩C|=30. Dieci elementi non appartengono a nessuno dei tre insiemi. Determina tutte le otto regioni, il numero di elementi in esattamente un insieme e in esattamente due.
Suggerimento
Parti dall’unione e dall’intersezione tripla, poi procedi dal centro verso l’esterno.
Soluzione con diagramma
1. L’unione ha 110 elementi. Per inclusione-esclusione, la somma delle tre cardinalità va corretta sottraendo le intersezioni a coppie e aggiungendo quella tripla t.
|A∪B∪C|=120−10=110 110=70+65+60−40−35−30+t t=20 AB: 40−20=20; AC: 35−20=15; BC: 30−20=10
2. Le regioni in esattamente due insiemi sono 20, 15 e 10. Solo A: 70−40−35+20=15; solo B: 65−40−30+20=15; solo C: 60−35−30+20=15.
Risposta e verifica. Esattamente uno: 45; esattamente due: 45; tutti e tre: 20; nessuno: 10. Totale 45+45+20+10=120. Non sottrarre la tripla due volte dalle cardinalità dei singoli insiemi.
2. Quali intersezioni triple sono possibili?
|U|=100, |A|=60, |B|=55, |C|=50. Le intersezioni a coppie hanno cardinalità 35, 30 e 25 rispettivamente per AB, AC e BC. Determina tutti i valori interi possibili di t=|A∩B∩C|. Non basta trovare un limite: dimostra che ogni valore ammesso si può realizzare.
Suggerimento
Ogni regione disgiunta, compresa quella esterna, deve avere cardinalità non negativa.
Soluzione con diagramma
1. Lasciamo t come parametro. Solo A vale 60−35−30+t=t−5; allo stesso modo solo B e solo C valgono t−5. Le regioni doppie valgono la rispettiva intersezione meno t.
|A∪B∪C|=165−90+t=75+t A soltanto = B soltanto = C soltanto = t−5 AB soltanto=35−t; AC soltanto=30−t; BC soltanto=25−t U ∖ (A∪B∪C): 25−t 5 ≤ t ≤ 25, t ∈ ℤ
2. Le regioni singole impongono t≥5. La regione BC senza A e quella esterna impongono t≤25; gli altri vincoli superiori sono più deboli.
3. Sufficienza. Per ogni intero fra 5 e 25, le otto quantità del diagramma sono non negative e sommano a 100. Prendiamo otto gruppi disgiunti con quelle dimensioni e definiamo A, B e C unendo i gruppi corrispondenti. Questa costruzione realizza tutti i dati. Dunque i valori possibili sono esattamente 5,6,…,25.
3. Le distanze simmetriche non raccontano tutto
Tre sottoinsiemi di U, con |U|=60, soddisfano |AΔB|=24, |AΔC|=30, |BΔC|=26, |A∩B∩C|=8 e |A|+|B|+|C|=92. Trova quanti elementi appartengono a esattamente uno, due o tre insiemi e quanti a nessuno. Questi dati determinano anche ogni singola regione?
Suggerimento
Un elemento presente in uno oppure due insiemi viene contato esattamente due volte nella somma delle tre differenze simmetriche.
Soluzione con diagramma
1. Indichiamo con n₁,n₂,n₃ le quantità in esattamente uno, due, tre insiemi. Gli elementi esterni e quelli comuni a tutti non compaiono in nessuna differenza simmetrica. Ogni altro elemento ne compare in due.
2(n₁+n₂)=24+30+26=80 n₃=8 n₁+2n₂+3·8=92 n₂=28; n₁=12 |A∪B∪C|=12+28+8=48
2. Esattamente uno: 12; esattamente due: 28; tutti e tre: 8; nessuno: 12.
3. Le singole regioni non sono determinate. Nel diagramma compare una configurazione valida. Un’altra è: solo A=5, solo B=1, solo C=6; AB senza C=10, AC senza B=9, BC senza A=9; tripla=8, esterna=12. Riproduce gli stessi cinque dati. Distinguere quantità determinate e configurazione completa è parte della soluzione.
4. Semplificare una differenza simmetrica annidata
Per insiemi arbitrari A,B,C, semplifica E=((A∪B)∖C) Δ ((A∖B)∪(C∖A)) in una forma senza differenza simmetrica, usando al massimo un’unione, un’intersezione tripla e una differenza. Dimostra l’identità per tutte le regioni.
Suggerimento
Per ciascun elemento registra tre bit: appartiene o no ad A, B e C? La differenza simmetrica richiede esattamente uno dei due membri.
Soluzione con diagramma
1. Nell’ordine delle regioni 000,100,010,001,110,101,011,111, il primo membro (A∪B)∖C vale 0,1,1,0,1,0,0,0; il secondo (A∖B)∪(C∖A) vale 0,1,0,1,0,1,1,0.
2. La differenza simmetrica vale quindi 0,0,1,1,1,1,1,0: seleziona tutti gli elementi di B∪C tranne quelli comuni ai tre.
E=((A∪B)∖C) Δ ((A∖B)∪(C∖A)) E=(B∪C)∖(A∩B∩C)
3. Le otto combinazioni sono esaustive: l’identità vale per qualsiasi insieme, anche infinito. Una regione vuota non invalida il ragionamento.
5. Un insieme incognito con vincoli e cardinalità
Siano U={1,…,12}, A={1,…,7}, B={1,…,10}, C={2,4,6,8,10,12}, D={2,6,8,10}. Determina tutti gli X⊆U tali che X∪A=B, X∩C=D e |X|=7. Quanti sono?
Suggerimento
Distingui elementi obbligatori, vietati e liberi.
Soluzione con diagramma
1. X∪A=B impone che 8,9,10 appartengano a X e che 11,12 ne restino fuori. Gli elementi di A sono ancora liberi.
2. X∩C=D impone 2 e 6, conferma 8 e 10, vieta 4 e 12. Restano liberi 1,3,5,7. Abbiamo già cinque elementi obbligatori.
B∖A={8,9,10}
D∩A={2,6}
A∖C={1,3,5,7}
X={2,6,8,9,10}∪Y
Y⊆{1,3,5,7}, |Y|=2
C(4,2)=63. Per arrivare a sette bisogna scegliere due dei quattro elementi liberi: 6 soluzioni. Le possibili Y sono {1,3}, {1,5}, {1,7}, {3,5}, {3,7}, {5,7}. Unire ognuna al gruppo obbligatorio descrive tutti e soli gli X. Verificare separatamente i due vincoli evita di accettare elementi vietati.
6. L’insieme delle parti non distribuisce sull’unione
A e B sono finiti, |A∩B|=2, |𝒫(A)|=2|𝒫(B)| e |𝒫(A)∪𝒫(B)|=44. Trova |A| e |B|. Quanti sottoinsiemi di A∪B non sono contenuti interamente né in A né in B? Infine dimostra quando 𝒫(A∪B)=𝒫(A)∪𝒫(B).
Suggerimento
𝒫(A)∩𝒫(B)=𝒫(A∩B), ma l’analoga identità con l’unione non vale sempre.
Soluzione con diagramma
1. Un insieme con a elementi ha 2ᵃ sottoinsiemi. L’intersezione dei due insiemi delle parti contiene i sottoinsiemi dei due elementi comuni, quindi ne ha quattro. Applichiamo inclusione-esclusione:
a=|A|, b=|B| 2ᵃ=2·2ᵇ 2ᵃ+2ᵇ−2²=44 3·2ᵇ=48 ⇒ b=4, a=5 |A∪B|=5+4−2=7 2⁷−44=84
2. |A|=5, |B|=4. Dei 128 sottoinsiemi dell’unione, 44 stanno interamente in almeno uno dei due: i rimanenti sono 84.
3. L’uguaglianza richiesta vale se A⊆B oppure B⊆A. Viceversa, se nessuno contiene l’altro, scegli a∈A∖B e b∈B∖A: {a,b} è un sottoinsieme dell’unione ma non di A né di B. È un controesempio che prova anche la necessità.
7. Quattro insiemi: un archivio impossibile
Un archivio dichiara 40 elementi totali. Quattro categorie A,B,C,D contengono 20 elementi ciascuna; ognuna delle sei intersezioni a coppie ne contiene 8; ognuna delle quattro intersezioni triple ne contiene 3; l’intersezione quadrupla ne contiene 1. È possibile? Qual è il minimo universo che rende realizzabili questi dati?
Suggerimento
Per quattro insiemi servono sedici regioni. Non tentare di disegnarle con quattro cerchi ordinari.
Soluzione con diagramma
1. Inclusione-esclusione a quattro termini produce un’unione di 43 elementi: l’archivio da 40 è impossibile.
2. Per dimostrare che 43 bastano, ricostruiamo le regioni esclusive. La quadrupla vale 1; ogni tripla esclusiva 3−1=2; ogni coppia esclusiva 8−3−3+1=3; ogni singola esclusiva 20−24+9−1=4.
|A∪B∪C∪D|=4·20−6·8+4·3−1=43 n₄=1 n₃=4(3−1)=8 n₂=6(8−3−3+1)=18 n₁=4(20−3·8+3·3−1)=16
3. I gruppi disgiunti sono: quattro da 4, sei da 3, quattro da 2 e uno da 1. Sommano a 43 e realizzano tutti i dati; la regione esterna può essere vuota. Non basta dire «l’unione supera 40»: la costruzione dimostra che 43 è davvero il minimo, non solo un limite inferiore.
8. Quando l’immagine conserva l’intersezione
Sia U={1,…,8}, V={p,q,r,s}. Una funzione f ha fibre f⁻¹({p})={1,2,3}, f⁻¹({q})={4,5}, f⁻¹({r})={6}, f⁻¹({s})={7,8}. Fissa A={1,4,6,7}. Quanti B⊆U soddisfano f(A∩B)=f(A)∩f(B)? Spiega perché l’uguaglianza non è automatica.
Suggerimento
Ragiona separatamente in ogni fibra, cioè tra gli elementi con la stessa immagine.
Soluzione con diagramma
1. A incontra ogni fibra, dunque f(A)=V. In ogni fibra, B deve essere vuoto oppure contenere almeno uno degli elementi di A presenti nella fibra. Altrimenti il valore compare in f(B), ma non in f(A∩B).
2. Se una fibra ha m elementi, di cui a in A, le scelte sono: una scelta vuota, oppure un sottoinsieme non vuoto degli a elementi di A e un sottoinsieme arbitrario dei restanti m−a.
N(m,a)=1+(2ᵃ−1)2ᵐ⁻ᵃ N(3,1)=5; N(2,1)=3; N(1,1)=2 5·3·2·3=90
3. Le scelte nelle fibre sono indipendenti in senso combinatorio: 90 insiemi B. Il controesempio B={2} dà f(A)∩f(B)={p}, mentre A∩B=∅ e la sua immagine è vuota. L’inclusione f(A∩B)⊆f(A)∩f(B) vale sempre, l’uguaglianza no.
9. Una famiglia enorme senza elemento comune
Sia U={1,2,3,4,5,6}. Cerca il massimo numero di sottoinsiemi distinti in una famiglia ℱ tale che ogni coppia di membri distinti abbia intersezione non vuota, ma l’intersezione di tutta la famiglia sia vuota. Dimostra il massimo e costruisci una famiglia che lo raggiunge.
Suggerimento
Abbina ogni sottoinsieme al suo complementare. Per costruire, usa insieme sottoinsiemi grandi e alcuni di taglia tre.
Soluzione con diagramma
1. Limite superiore. I 64 sottoinsiemi si dividono in 32 coppie complementari {S,U∖S}. I due membri della stessa coppia sono disgiunti: ℱ può sceglierne al massimo uno. Dunque |ℱ|≤32.
2. Costruzione. Prendi tutti i sottoinsiemi con almeno quattro elementi e tutti quelli con tre elementi che contengono 1.
|𝒫(U)|=2⁶=64
|ℱ|≤64/2=32
ℱ={S⊆U: |S|≥4} ∪ {S⊆U: |S|=3, 1∈S}
|ℱ|=C(6,4)+C(6,5)+C(6,6)+C(5,2)
=15+6+1+10=323. Verifica a coppie. Due insiemi di taglia almeno quattro si incontrano; uno di taglia quattro o più e uno di taglia tre hanno in totale almeno sette elementi contati con ripetizione, quindi si incontrano in un universo di sei. Due terne scelte condividono 1.
4. Intersezione globale. Per ogni elemento di U esiste un sottoinsieme di quattro elementi che lo esclude; quel sottoinsieme appartiene alla famiglia. Nessun elemento è comune a tutti. Il massimo è quindi 32, pur senza un elemento universale.
10. Appartenere infinite volte non significa restare per sempre
Per n≥1 definisci Aₙ=[0,2−1/n]∪{3} se n è pari, e Aₙ=[−1+1/n,1]∪{4} se n è dispari. Trova l’insieme degli x che appartengono ad Aₙ per tutti gli n sufficientemente grandi (lim inf) e quello degli x che vi appartengono per infiniti n (lim sup). Giustifica anche gli estremi −1,0,1,2 e i punti 3,4.
Suggerimento
Studia separatamente gli indici pari e dispari. Essere limite degli estremi non implica appartenere agli intervalli.
Soluzione con diagramma
1. Ogni x∈[0,1] appartiene a tutti gli Aₙ. Un x∈(−1,0) entra negli intervalli dispari per tutti gli indici dispari abbastanza grandi, ma mai in quelli pari. Un x∈(1,2) si comporta allo stesso modo sugli indici pari.
2. −1 e 2 non entrano mai. Il punto 3 compare soltanto negli indici pari, 4 soltanto nei dispari. Tutti gli altri punti esterni a (−1,2)∪{3,4} sono sempre esclusi.
lim inf Aₙ = ⋃ₘ₌₁∞ ⋂ₙ≥ₘ Aₙ = [0,1]
lim sup Aₙ = ⋂ₘ₌₁∞ ⋃ₙ≥ₘ Aₙ = (−1,2)∪{3,4}3. Il limite inferiore è [0,1]; il superiore è (−1,2)∪{3,4}. Le formule formalizzano due ordini diversi dei quantificatori: «esiste una soglia dopo cui sempre» contro «oltre ogni soglia, almeno una volta». La successione non ha un unico limite di appartenenza, perché lim inf e lim sup sono diversi.
