3.10 Cardinalità[1YW]
[22B]Per comodità useremo il simbolo \(|A|\) per indicare la cardinalità dell’ insieme \(A\). Questo simbolo si usa come segue. Dati due insiemi \(A,B\), scriveremo \(|A|= |B|\) se gli insiemi sono equipotenti (o anche equinumerosi), cioè se esiste una funzione bigettiva fra \(A\) e \(B\); scriveremo \(|A|≤ |B|\) se esiste una funzione iniettiva da \(A\) a \(B\). Scriveremo anche \(|A|{\lt} |B|\) se esiste una funzione iniettiva da \(A\) a \(B\), ma non una bigezione. Se assumiamo vero l’assioma della scelta allora per ogni coppia di insiemi si ha sempre \(|A|≤ |B|\) oppure \(|B|≤ |A|\) (si veda 114).
[1Z9]Se ora fissiamo una famiglia \(\mathcal F\) di insiemi di interesse, definiamo innanzitutto la relazione \(A∼ B\iff |A|= |B|\); si mostra che questa è una relazione di equivalenza; dunque si ottiene che \(|A|≤ |B|\) è un ordinamento totale in \({\mathcal F}/∼\).
Questo deriva dalla Proposizione 82, in quanto la relazione
è riflessiva e transitiva, e per il Teorema di Cantor–Bernstein
Nel seguito, sia \(E_ 0=∅\) oppure \(E_ n=\{ 1, \ldots n\} \) se \(n ≥ 1 \).
[1B1]Per definizione 1 “un insieme \(A\) è finito e ha cardinalità \(n\)” se è equipotente a un’insieme \(E_ n\) (per una scelta di \(n∈ℕ\); vi è al più un \(n\) per cui questo può avvenire, per via del il Lemma precedente). Dunque quando l’insieme è finito, \(|A|\) si identifica con il numero (naturale) dei suoi elementi, scriveremo \(|A|=n\). Se un insieme non è finito, allora è infinito.
Notiamo che la mappa nulla \(f:∅→ ∅\) è una bigezione; e \(|A|=0 ⇔ A=∅\). Il risultato seguente è fondamentale.
[2GH]Dimostrate che \(ℕ\) è infinito, e che \(|ℕ|{\gt}n, ∀ n∈ ℕ\). Soluzione nascosta: [UNACCESSIBLE UUID ’2GJ’]
Ricordiamo il Teorema 1.12.2 degli appunti [ 3 ] , per comodità.
[02S] Se \(A\) è infinito, allora \(|A|\ge |{\mathbb {N}}|\). In particolare, \(|A|{\gt}n\) per ogni \(n\in {\mathbb {N}}\).
Insiemi finiti
- E112
[02T] Sia \(A\) un insieme finito, e \(B⊆ A\), mostrate che \(B\) è finito.
Soluzione nascosta: [UNACCESSIBLE UUID ’02V’]
- E112
[02W] Supponiamo di avere un numero finito \(m≥ 1\) di insiemi \(A_ 1,\ldots , A_ m\) tutti finiti. Mostrate che \(⋃_{j=1}^ m A_ j\) è un insieme finito. Soluzione nascosta: [UNACCESSIBLE UUID ’02X’]
- E112
[02Y] Ricordiamo che \(A^ B\) è l’insieme di tutte le funzioni \(f:B→ A\). Se \(A,B\) sono insiemi finiti nonvuoti mostrate che \(|A^ B|=|A|^{|B|}\). Cosa succede se uno, o entrambi, sono vuoti? Soluzione nascosta: [UNACCESSIBLE UUID ’02Z’]
- E112
[22K]Se \(A,B\) sono insiemi finiti nonvuoti, calcolate la cardinalità dell’insieme delle funzioni \(f:B\to A\) iniettive; e la cardinalità di quelle surgettive. Cosa succede se uno, o entrambi, dei due insiemi \(A,B\) sono vuoti?
Confronto
- E112
[030]Prerequisiti:13.Supponiamo che \(A\) non sia vuoto. Si ha \(|A|≤ |B|\) se e solo se esiste una funzione surgettiva \(f:B→ A\). (L’implicazione “se” necessita dell’assioma della scelta; si veda anche 2).
- E112
[031] Mostrate che se \(|A_ 1|\le |A_ 2| \) e \(|B_ 1|\le |B_ 2| \) allora \(|A_ 1\times {B_ 1}|\le |A_ 2\times {B_ 2}|\).
- E112
[032] Mostrate che se \(|A_ 1|≤ |A_ 2| \) e \(|B_ 1|≤ |B_ 2| \) allora \(|A_ 1^{B_ 1}|≤ |A_ 2^{B_ 2}|\) Soluzione nascosta: [UNACCESSIBLE UUID ’033’]
- E112
[034] (Svolto il 2022-10-27) Mostrate che \(|(A^ B)^ C|=|A^{(B \times C)}|\). Soluzione nascosta: [UNACCESSIBLE UUID ’035’]
- E112
[036] (Svolto il 2023-01-24) Sia \(I\) una famiglia di indici e \(B_ i,A_ i\) insiemi, per \(i∈ I\), con \(|A_ i|≤ |B_ i|\); supponiamo che gli insiemi \(B_ i\) siano a due a due disgiunti; si mostri allora che
\[ \left|⋃_{i∈ I} A_ i\right| ≤ \left|⋃_{i∈ I} B_ i\right|~ . \](Secondo voi è possibile dimostrare questo risultato senza usare l’assioma della scelta, almeno nel caso in cui \(I\) è numerabile?) Soluzione nascosta: [UNACCESSIBLE UUID ’037’]
- E112
[038] Sia \(C\) un insieme, \(I\) una famiglia di indici e siano \(B_ i\) insiemi per \(i\in I\); supponiamo che gli insiemi \(B_ i\) siano a due a due disgiunti; sia \({\mathcal B}=\bigcup _{i\in I} B_ i\) per comodità; si mostri allora che
\begin{eqnarray} \forall i, |B_ i|\le |C|& \Rightarrow & \left|{\mathcal B}\right| \le \left|I\times C\right| \label{eqn:B_ i_ cup_ le_ times_ C}\\ \forall i, |B_ i|\ge |C|& \Rightarrow & \left|{\mathcal B}\right| \ge \left|I\times C\right|~ ~ . \end{eqnarray}Soluzione nascosta: [UNACCESSIBLE UUID ’039’]
dove \({\mathcal B}=\prod _{i\in I} B_ i\). Soluzione nascosta: [UNACCESSIBLE UUID ’03D’] [03F] Prerequisiti:17.(Proposto il 2022-12) Mostrate che le cardinalità sono sempre confrontabili, cioè che dati due insiemi \(A,B\) si ha sempre o \(|A|\le |B|\) o \(|B|\le |A|\). (Usate il lemma di Zorn e la costruzione spiegata nell’esercizio 17). Soluzione nascosta: [UNACCESSIBLE UUID ’03G’]
(Presente come teorema 1.19 negli appunti)
Questo enunciato è equivalente all’ Assioma della Scelta, si veda [ 22 ] .
Cardinalità numerabile
[2DF]Ricordiamo che un insieme è “numerabile” se ha la stessa cardinalità di \(ℕ\).
Se \(A\) è numerabile, esiste \(a:ℕ→ A\) bigettiva; scrivendo \(a_ n\) invece di \(a(n)\), diremo dunque che \(A=\{ a_{0},a_{1},a_ 2\ldots \} \) è una enumerazione.
- E115
[03H] Trovato un polinomio \(p(x,y)\) che, visto come funzione \(p:ℕ^ 2→ ℕ\) sia bigettivo. Se ne ricava, iterando, che esiste un polinomio \(q_ k\) in \(k\) variabili bigettivo \(q_ k:ℕ^ k→ℕ\). Dunque \(ℕ^ k\) è numerabile. Soluzione nascosta: [UNACCESSIBLE UUID ’03J’][UNACCESSIBLE UUID ’03K’]
- E115
[03M]Mostrate che gli insiemi \( {\mathbb {Z}}, {\mathbb {Q}}\) sono numerabili.
Soluzione nascosta: [UNACCESSIBLE UUID ’03N’]
- E115
-
Siano \(A_ 0,A_ 1\ldots A_ n\ldots \) insiemi al più numerabili, per \(n\in {\mathbb {N}}\).
Si mostri che \(B=\bigcup _{k=0}^\infty A_ k\) è al più numerabile.
Notate che \(B\) è numerabile se ad esempio vi è almeno un \(n\) per cui \(A_ n\) è numerabile.
Soluzione nascosta: [UNACCESSIBLE UUID ’03Q’]
- E115
[03R] Indichiamo con \({\mathcal P}_{\mathfrak f}(A)\) l’insieme dei sottoinsiemi \(B⊆ A\) che sono insiemi finiti. Questo è detto colloquialmente l’insieme delle parti finite.
Si mostri che \({\mathcal P}_{\mathfrak f}(ℕ)\) è numerabile.
Soluzione nascosta: [UNACCESSIBLE UUID ’03S’]
Questo risultato vale in generale, si veda 2.
Cardinalità del continuo
[03V]Diremo che un insieme ha cardinalità del continuo se ha la stessa cardinalità di \(ℝ\).
[2F2] Cantor dimostrò che \(|ℕ|{\lt} |ℝ|\). Successivamente Cantor formulò (nel 1878) l’ipotesi del continuo CH: per ogni insieme infinito \(E⊆ ℝ\), si ha che \(|E|= |ℝ|\) oppure \(|E|= |ℕ|\). Per molti anni i matematici provarono a dimostrare CH (o la sua negazione). Ci vollero decenni per capire che questo non è possibile. Oggi sappiamo che, assumendo che la teoria ZF sia consistente, allora né CH né la negazione di CH possono essere dimostrati come teoremi in ZF (anche usando l’Assioma della scelta). La seconda parte dell’asserzione fu dimostrata da Gödel in 1939. La prima parte da Cohen nel 1963. Si veda nel Cap. 6 in [ 13 ] .
- E117
[03X](Proposto il 2022-12) Spiegate come potreste costruire esplicitamente una bigezione fra \([0,1)\) e \([0,1)^ 2\).
- E117
[03Y](Proposto il 2022-10-13) (Svolto il 2022-10-27) Mostrate con costruzioni esplicite che i seguenti insiemi hanno cardinalità del continuo:
\[ [0,1],\quad [0,1),\quad (0,1),\quad (0,∞)~ ~ . \]Soluzione nascosta: [UNACCESSIBLE UUID ’03Z’]
- E117
-
Mostrate che i seguenti insiemi hanno cardinalità del continuo.
\[ ℝ^ n,\quad \{ 0,1\} ^{ℕ},\quad ℕ^{ℕ},\quad ℝ^{ℕ}~ ~ . \]Soluzione nascosta: [UNACCESSIBLE UUID ’041’][UNACCESSIBLE UUID ’042’]
- E117
[043]Prerequisiti:5,3.Siano \(A_ t\) insiemi con cardinalità minore o uguale al continuo, per \(t∈ℝ\). Si mostri che \(⋃_{t∈ℝ} A_ t\) ha cardinalità del continuo. Soluzione nascosta: [UNACCESSIBLE UUID ’044’]
- E117
[045]Sia \({\mathcal A}\) l’insieme dei sottoinsiemi \(B⊆ ℝ\) che sono insiemi finiti o numerabili; si mostri che \({\mathcal A}\) ha cardinalità del continuo. Soluzione nascosta: [UNACCESSIBLE UUID ’046’]
In generale
Aggiungiamo alcuni esercizi di carattere più generale.
- E117
[048]Mostrate che \(|A|{\lt}|{\mathcal P}(A)|\). Soluzione nascosta: [UNACCESSIBLE UUID ’049’]
- E117
[04B]Considerate l’insieme \(ℕ ^ℕ\) delle funzioni \(f:ℕ→ℕ\); e il sottoinsieme \(\mathcal A\) delle \(f\) che possono essere definite usando un algoritmo, scritto in un linguaggio di programmazione a piacere, supponendo inoltre che il computer che lo esegue abbia una memoria potenzialmente illimitata, e tale che per ogni scelta \(n∈ℕ\) in input l’algoritmo deve terminare e restituire \(f(n)\). Confrontate le cardinalità di \(ℕ ^ℕ\) e di \(\mathcal A\).
[04D](Proposto il 2022-12) Calcolate la cardinalità dell’insieme \({\mathcal F}\) delle funzioni \(f:ℕ→ℕ\) debolmente descrescenti. Soluzione nascosta: [UNACCESSIBLE UUID ’04F’] [04G] Prerequisiti:134.
Un insieme \(A\) è detto Dedekind–infinito se è in bigezione con una sua parte propria cioè se esiste \(B⊂ A, B≠ A\) e \(h:A→ B\) bigezione. Mostrate che un insieme \(A\) è Dedekind–infinito se e solo se esiste una funzione iniettiva \(g:ℕ→ A\). (Questo risultato non necessita dell’assioma della scelta).
Soluzione nascosta: [UNACCESSIBLE UUID ’04H’] [04J] Prerequisiti:111.Se \(A\) è infinito e \(B\) è finito o numerabile mostrate che \(|A|=|A∪ B|\) usando l’esistenza di una funzione \(g:ℕ→ A\) iniettiva.
Soluzione nascosta: [UNACCESSIBLE UUID ’04K’] [22M]Prerequisiti:2,2.Similmente se \(A\) è infinito e \(B\) è finito mostrate che \(|A|=|A⧵ B|\) usando il fatto che per ogni insieme infinito \(X\) esiste una funzione \(g:ℕ→ X\) iniettiva. Soluzione nascosta: [UNACCESSIBLE UUID ’22N’] [04M] Prerequisiti:111, 2. Mostrate che un insieme \(A\) è Dedekind–infinito se e solo se è infinito (secondo la definizione vista all’inizio del capitolo).
Soluzione nascosta: [UNACCESSIBLE UUID ’04N’]
Nota: secondo [ 11 ] , la precedente equivalenza non può essere dimostrata usando solo gli assiomi di ZF (Zermelo–Fraenkel senza l’assioma della scelta) ; la precedente equivalenza può essere dimostrata usando gli assiomi di ZFC (Zermelo–Fraenkel con l’assioma della scelta); ma la sua validità in ZF è più debole dell’assioma della scelta.
[UNACCESSIBLE UUID ’1ZC’] [04P] Prerequisiti:2,17.Difficoltà:*.(Proposto il 2022-12)
Sia \(X\) infinito. Mostrate che \(X\) si partiziona in due insiemi \(X_ 1,X_ 2\) che hanno la stessa cardinalità di \(X\). (Sugg. considerate sottoinsiemi di \(X\) su cui la proprietà vale, usate Zorn) Soluzione nascosta: [UNACCESSIBLE UUID ’04Q’] [04R] Prerequisiti:2,1,3.Difficoltà:*.(Svolto il 2022-10-13
in parte)
Sia \(A\) infinito. Mostrate che \(|D× A|=|A|\) per ogni insieme nonvuoto \(D\) finito o numerabile. 3
(Una possibile soluzione usa 2) Soluzione nascosta: [UNACCESSIBLE UUID ’04S’]
(Un’altra possibile soluzione usa il teorema di Zermelo, 3 e 1; in questo caso 2 diviene un corollario di questo risultato.) Soluzione nascosta: [UNACCESSIBLE UUID ’04T’] [04V](Svolto il 2022-10-27) Siano \(A,B\) infiniti. Mostrate che \(|A∪ B|=\max \{ |A|,|B|\} \). Soluzione nascosta: [UNACCESSIBLE UUID ’04W’] [04X]Mostrate che se \(A\) è un insieme infinito, e si decompone nell’unione disgiunta di due insiemi \(A_ 1,A_ 2\) con \(|A_ 1|≤ |A_ 2|\) allora \(|A|=|A_ 2|\). Soluzione nascosta: [UNACCESSIBLE UUID ’04Y’] [04Z] Prerequisiti:17, 2.Difficoltà:**.(Proposto il 2022-10-13) (Svolto il 2022-11-15)
Siano \(A,B\) infiniti. Mostrate che \(|A^ 2|=|A|\).
Usate questo risultato per mostrare che se \(A,B\) sono nonvuoti e almeno uno è infinito allora \(|A× B|=\max \{ |A|,|B|\} \).
Soluzione nascosta: [UNACCESSIBLE UUID ’050’]
Si veda inoltre la nota 118.
[27H]Note storiche.
La proposizione “\(|A^ 2|=|A|\) vale per ogni insieme infinito” è equivalente all’assioma della scelta. Questo fu dimostrato da Tarski [ 24 ] nel 1928; l’articolo è online e scaricabile e contiene altre sorprendenti equivalenze. Si veda anche [ 22 ] Parte 1 Sezione 7 pagina 140 asserzione CN6.
Jan Mycielski [ 19 ] riporta: «Tarski told me the following story. He tried to publish his theorem (stated above) in the Comptes Rendus Acad. Sci. Paris but Fréchet and Lebesgue refused to present it. Fréchet wrote that an implication between two well known propositions is not a new result. Lebesgue wrote that an implication between two false propositions is of no interest. And Tarski said that after this misadventure he never tried to publish in the Comptes Rendus».
Questo aneddoto ci mostra quanto (prima dei lavori di Godel e Cohen [ 6 ] , anche i matematici più importanti non capissero l’importanza dell’assioma della scelta.
- E118
[051] Prerequisiti:2.Sia \(A\) infinito. Sia \(n∈ℕ\) con \(n≥ 1\). Mostrate che \(|A^ n|=|A|\). Soluzione nascosta: [UNACCESSIBLE UUID ’052’]
- E118
[053] Prerequisiti:5, 1, 2.(Proposto il 2022-12) (Svolto il 2023-01-24) Sia \(A\) infinito. Si mostri che l’insieme delle parti finite \({\mathcal P}_{\mathfrak f}(A)\) ha la stessa cardinalità di \(A\). Soluzione nascosta: [UNACCESSIBLE UUID ’054’]
- E118
[055] Prerequisiti: 6, 2.(Svolto il 2023-01-24) Sia \(X\) un insieme infinito, sia \(∼\) una relazione di equivalenza su \(X\), siano \(U=X/∼\) le classi di equivalenza.
Supponiamo che ogni classe sia finita, mostrate che \(|U|=|X|\).
Supponiamo che \(U\) sia infinito e ogni classe abbia cardinalità al più \(|U|\), allora \(|U|=|X|\).
Soluzione nascosta: [UNACCESSIBLE UUID ’056’]
- E118
[057]Prerequisiti:3,2,3.Difficoltà:**.
Sia \(V\) uno spazio vettoriale reale. Siano \(A,B\) due basi di Hamel (si veda 3). Si mostri che \(|A|=|B|\). (Questo risultato è noto come “Teorema della dimensione”)
Più in generale, siano \(L,G⊆ V\), dimostrate che, se i vettori in \(L\) sono linearmente indipendenti e se \(G\) genera \(V\), allora \(|L|≤ |G|\).
Soluzione nascosta: [UNACCESSIBLE UUID ’058’]
[UNACCESSIBLE UUID ’1ZB’] [UNACCESSIBLE UUID ’05B’] [UNACCESSIBLE UUID ’05C’][UNACCESSIBLE UUID ’05D’] [UNACCESSIBLE UUID ’05F’] [UNACCESSIBLE UUID ’05G’]
Potenza
Ricordiamo che \(A^ B\) è l’insieme di tutte le funzioni \(f:B→ A\). Scriveremo \(|2^ A|\) per indicare la cardinalità dell’insieme delle parti di \(A\).
- E118
[05J]Prerequisiti:2.(Proposto il 2022-12) Siano \(A,B\) insiemi non vuoti e tali che \(A\) è infinito e \(2≤ |B|≤ |A|\) allora \(|B^ A|=|2^ A|\). Soluzione nascosta: [UNACCESSIBLE UUID ’05K’]
- E118
[05M]Siano \(A,B\) insiemi non vuoti, supponiamo che esista un insieme \(C\) tale che \(|B|=|2^ C|\) allora \(|B^ A|=\max \{ |B|,|2^ A| \} \).
Soluzione nascosta: [UNACCESSIBLE UUID ’05N’]
In generale nel caso in cui \(|B|{\gt}|A|\) lo studio della cardinalità di \(|B^ A|\) è molto complesso (anche in casi apparentemente semplici come \(A=ℕ\)).