Pagina iniziale | Navigazione |
Google

Insieme numerabile

Un insieme infinito si dice numerabile quando ha la stessa cardinalit√† di N, ossia quando Ť possibile stabilire una corrispondenza biunivoca (biiezione) con l'insieme dei numeri naturali.

Esempi di insiemi numerabili sono i numeri interi e i numeri razionali. L'insieme dei numeri reali, al contrario, non Ť numerabile.

Per esempio, l'insieme dei numeri pari Ť numerabile; infatti possiamo associare ad ogni numero il suo doppio stabilendo la corrispondenza voluta:

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, ...

Per dimostrare che l'insieme dei numeri razionali Ť numerabile (ci limitiamo ai razionali positivi, sebbene la generalizzazione sia banale), osserviamo che tutti i razionali positivi si possono scrivere nella forma con a e b interi positivi. Possiamo creare la seguente tabella delle frazioni a/b:

1/1, 2/1, 3/1, 4/1, 5/1, ...

1/2, 2/2, 3/2, 4/2, 5/2, ...

1/3, 2/3, 3/3, 4/3, 5/3, ...

1/4, 2/4, 3/4, 4/4, 5/4, ...

1/5, 2/5, 3/5, 4/5, 5/5, ...

E così via. Tramite un processo di diagonalizzazione si può quindi ottenere la seguente lista:

1/1, 2/1, 1/2, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 2/4, 3/3, 4/2, 5/1, ... ecc. Se da questa lista cancelliamo le frazioni che non sono ridotte ai minimi termini ci rimane la seguente successione:

1, 2, 1/2, 3, 4, 3/2, 2/3, 1/4, 1/5, 5, ...

che contiene esattamente tutti i numeri razionali. Non Ť superfluo osservare che questa sequenza non Ť ordinata e, anzi, Ť impossibile costruire una lista ordinata dei numeri razionali.

Dimostriamo adesso la non-numerabilit√† dell'insieme dei numeri reali. Ragioniamo per assurdo. Supponiamo cioŤ che esista una biiezione tra i reali ed i numeri naturali. Allora Ť possibile costruire una lista di tutti i numeri reali:

  • N1,a1a2a3a4a5
  • N2,b1b2b3b4b5
  • N3,c1c2c3c4c5
  • ...

Ora scegliamo un numero a diverso da a1 e compresa tra 1 e 8 (includere 0 e 9 potrebbe provocare casi di ambiguit√† dovuti a rappresentazioni come 0,99999... = 1), una cifra b diversa da b2, c diversa da c3 e cos√¨ via. Costruiamo quindi il numero reale 0,abcd... Questo numero Ť per costruzione diverso da ogni numero presente nella lista, e di conseguenza non fa parte di essa. Ci√≤ costituisce un assurdo, perch√© avevamo supposto che la lista contenesse tutti i numeri reali. La sola supposizione di esistenza ci ha condotto a conseguenze in contrasto con le ipotesi, pertanto la lista non esiste e i reali non sono numerabili.


GNU Fdl - it.Wikipedia.org




Google | 

Enciclopedia |  La Divina Commedia di Dante |  Mappa | : A |  B |  C |  D |  E |  F |  G |  H |  I |  J |  K |  L |  M |  N |  O |  P |  Q |  R |  S |  T |  U |  V |  W |  X |  Y |  Z |