Contabilità

Si dice che un insieme infinito è contabile, o numerabile, se esiste una corrispondenza biunivoca tra esso e l’insieme di tutti i numeri naturali.

Lemma di Cantor
Sia f₀,f₁,f₂,… una successione contabile di funzioni tale che ogni f_i applica i numeri naturali in {0,1}. Esiste una funzione f che applica i numeri naturali in {0 1} ma non è uguale ad alcuna delle f_i.
Dimostrazione. Definendo f(i) come 1 -f_i allora f(i) sarà sicuramente diverso da f_i(i), dunque f è diversa da f_i per ogni i.

Dal lemma di Cantor segue che l’insieme di tutte le funzioni dai numeri naturali a {0,1} non è contabile.

Consideriamo adesso l’insieme S di tutte le successioni finitamente non nulle di 0 ed 1. Tale insieme è contabile e possiamo mostrarlo consideranto s₀s₁s₂… una successione di 0 ed 1 e definendo una funzione che prende in input quella sccuessione:

dove N è un numero coì garande che s_n=0 per ogni n>=N. f è una corrspondenza biunivoca tra S e i numeri naturali. Per esserne sicuri basta osservare che per ogni j, s₀=0 solo se il più grande intero tra le somme di s_i2ⁱ diviso per 2^j è pari.

Ogni sottoinsieme infinito di un insieme contabile è a sua volta contabile. Infatti, sia sia X un sottoinsieme di N={0,1,2,3,…}. Definiamo una funzione f che va da N ad X nel seguente modo:

• f(0) = min(X)
• f(n+1) è il più piccolo elemento di X maggiore di f(n)

f è invertibile e rappresenta una corrispondenza biunivoca tra N ed X. La sua inversa è una corrispondenza tra X ed N che dimostra la contabilità di X.

Possiamo dire anche che l’insieme F di tutte le successioni finite di numeri naturali è contabile. Sia n* una successione di n+1 uno. Per ogni successione di numeri naturali n₀n₁n₂… sia:

f è quinid una corrispondenza tra F e l’insieme S visto in precedenza. Ciò mostra che F è contabile.