Primo teorema di Cantor (teorema fondamentale sul numerabile)

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.
Questa sezione è un contenitore temporaneo per i topic speciali a pagamento (One-Shot)

Se hai acquistato uno o più Topic speciali, puoi pubblicarli qui cliccando su "Apri un Topic".

Il registro completo dei Topic risolti e in corso è disponibile sul proprio profilo.

Primo teorema di Cantor (teorema fondamentale sul numerabile) #95706

avt
Pm97
Punto
Volevo chiedervi l'enunciato e la dimostrazione del primo teorema di Cantor, o teorema fondamentale sul numerabile.

In pratica il primo teorema di Cantor che afferma che l'unione disgiunta di una famiglia numerabile di insiemi numerabili è a sua volta numerabile.

Grazie in anticipo.
 
 

Re: Primo teorema di Cantor (teorema fondamentale sul numerabile) #95714

avt
Omega
Amministratore
Ciao Pm97,

partiamo dall'enunciato del primo teorema di Canto e poi passiamo alla dimostrazione, che a conti fatti non è così difficile ed è piuttosto carina.

Primo teorema di Cantor (teorema fondamentale sul numerabile)

L'unione di un numero finito o di una infinità numerabile di insiemi numerabili è un insieme numerabile.

Commento sull'enunciato: nota che la proposizione che ho riportato è quella più generale possibile perché non menziona l'ipotesi di disgiunzione degli insiemi.

Dimostrazione del primo teorema di Cantor

Per dimostrare l'asserto possiamo limitarci al caso di un'unione numerabile di insiemi numerabili a due a due disgiunti, da cui segue banalmente il caso non disgiunto e il caso finito.

Partiamo dalle notazioni: consideriamo una generica famiglia numerabile di insiemi, che chiameremo

F=\{A_i\mbox{ t.c. }i\in\mathbb{N}\}

dove \mathbb{N} denota l'insieme dei numeri naturali. In pratica F è un insieme numerabile i cui elementi sono insiemi.

Ognuno degli insiemi A_i è a sua volta un insieme numerabile. Il modo più furbo per indicarne gli elementi consiste nell'utilizzare una notazione con doppio indice

A_{i}=\{a_{ij}\mbox{ t.c. }j\in\mathbb{N}\}

dove l'indice i è fisso e al variare dell'indice j vengono individuati tutti gli elementi dell'insieme A_i.

Non è immediato comprendere che l'unione degli insiemi della famiglia F sia un insieme numerabile:

\bigcup_{i\in\mathbb{N}}A_i=\\ \\ =\{a_{00},a_{01},a_{02},...a_{0n},...\\ \\ a_{10},a_{11},a_{12},...a_{1n},...\\ \\ a_{20},a_{21},a_{22},...a_{2n},... \\ \\ ...\\ \\ a_{n0},a_{n1},a_{n2},...a_{nn},...\\ \\ ...\}

Per dimostrarlo dobbiamo provare che esiste una corrispondenza biunivoca tra l'insieme dei numeri naturali e l'insieme \bigcup_{i\in\mathbb{N}}A_i.

In altri termini dobbiamo dimostrare che ogni elemento dell'unione può essere associato ad uno ed un solo numero naturale (suriettività e iniettività).

Un'interpretazione geometrica del problema può esserci di grande aiuto. Disponiamo gli elementi dell'unione ordinatamente in una matrice

\left[\begin{matrix}a_{00} & a_{01} & a_{02} & a_{03} & ... & ... & a_{0i} & ... \\ a_{10} & a_{11} & a_{12} & ... & ... & a_{1(i-1)} & ... & ... \\ a_{20} & a_{21} & ... & ... & ... & ... & ... & ... \\ a_{30} & ... & ... & ... & ... & ... & ... & ... \\ ... & ... & ... & ... & ... & ... & ... & ... \\ ... & a_{(i-1)1} & ... & ... & ... & ... & ... & ... \\ a_{i0} & ... & ... & ... & ... & ... & ... & ... \\ ... & ... & ... &  ... & ... & ... & ... & ... \end{matrix}\right]

dove il primo indice corrisponde al numero di riga e il secondo indice corrisponde al numero di colonna.

Se leggiamo gli elementi procedendo lungo le antidiagonali (da sinistra verso destra, dal basso verso l'alto) possiamo enumerare gli elementi dell'unione nel modo seguente

\bigcup_{i\in\mathbb{N}}A_i=\\ \\ =\{a_{00},\\ \\ a_{10},a_{01},\\ \\ a_{20},a_{11},a_{02},\\ \\ a_{30},a_{21},a_{12},a_{03}, \\ \\ ...\\ \\ a_{i0},a_{(i-1)1},a_{(i-2)(2)},...,a_{2(i-2)},a_{1(i-1)},a_{0i}\\ \\ ...\}

A questo punto dobbiamo individuare una legge che associ biunivocamente gli elementi dell'unione agli elementi di \mathbb{N}. In modo del tutto equivalente (e più semplicemente) possiamo scrivere una corrispondenza inversa che associ biunivocamente i numeri naturali agli elementi dell'unione.

La seguente corrispondenza fa al caso nostro:

f:\bigcup_{i\in\mathbb{N}}A_i\to\mathbb{N} \\ \\ \\ f(a_{ij})=\begin{cases}0\ \ \ \mbox{se }(i,j)=(0,0)\\ \left(\sum_{k=1}^{i+j}k\right)+j\ \ \mbox{se }(i,j)\neq(0,0)\end{cases}

Forse scrivendone la legge per esteso è di più semplice lettura

f(a_{ij})=\begin{cases}0\ \ \ \mbox{se }(i,j)=(0,0)\\ [1+2+...+(i+j)]+j\ \ \mbox{se }(i,j)\neq(0,0)\end{cases}

La corrispondenza così definita è biunivoca per costruzione, essendo sia iniettiva che suriettiva. Avendo provato che l'unione può essere messa in corrispondenza biunivoca con l'insieme dei numeri naturali, dalla definizione segue che essa è un insieme numerabile.

Nota finale: la costruzione è resa possibile dalla disgiunzione degli insiemi A_i della famiglia.
Ringraziano: CarFaby, Pm97

Re: Primo teorema di Cantor (teorema fondamentale sul numerabile) #95718

avt
Pm97
Punto
Ho capito grazie, ma ho una domanda.

Hai dimostrato l'enunciato per insiemi a due a due disgiunti, dicendo che il caso non disgiunto segue da tale dimostrazione.

Alla fine però dici che la rappresentazione grazie alla quale hai fatto la dimostrazione è resa possibile dal fatto che gli insiemi siano disgiunti, come faccio quindi a dimostrarlo nel caso generale (dove non ho l'ipotesi di insiemi disgiunti)?

Re: Primo teorema di Cantor (teorema fondamentale sul numerabile) #95719

avt
Omega
Amministratore
Se gli insiemi non fossero disgiunti, ci sarebbe almeno un elemento in comune tra almeno due insiemi.

Tale elemento comparirebbe una sola volta nell'unione (per definizione di unione).

In conclusione il ragionamento non cambierebbe, sarebbe solo (inutilmente) più difficile scrivere la rappresentazione matriciale degli elementi dell'unione.

L'enunciato con l'ipotesi di disgiunzione è più forte ma il ragionamento che permette di dimostrarlo è valido anche nel caso più generale, ossia per l'enunciato più debole.
Ringraziano: Pm97
  • Pagina:
  • 1
Os