Diagonalització de Cantor

De Viquipèdia
Dreceres ràpides: navegació, cerca

La diagonalització de Cantor, també coneguda com a mètode diagonal, és una prova matemàtica albirada per Georg Cantor per a demostrar que el conjunt dels nombres reals no és numerable.

Aquesta demostració de la impossibilitat de comptar els nombres reals no va ser la primera, però sí que és més senzilla i elegant que aquesta. Posteriorment aquesta prova va inspirar altres demostracions, conegudes com a argument diagonal per l'analogia amb aquesta demostració.

Nombres reals[modifica | modifica el codi]

La prova original de Cantor mostra que l'interval [0,1] no és numerable. S'estén a tots els reals, ja que és possible equipotenciar aquests a l'interval.

La demostració és per reducció a l'absurd.

  • Suposem que l'interval [0,1] és infinit numerable.
  • Podríem elaborar una seqüència dels nombres, (r1, r2, r3,...)
  • Sabem que els reals entre 0 i 1 poden ser representats solament escrivint els seus decimals.
  • Col·loquem els nombres en la llista (no necessàriament en ordre). Considerant els decimals periòdics, com 0.499... = 0.500..., com els que tenen infinits nous.

La seqüència q

r4 = 0. 2 3 3 0 1 2 6...
r5 = 0. 4 1 0 7 2 4 6...
r6 = 0. 9 9 3 7 8 3 8...
r7 = 0. 0 1 0 5 1 3 5...
...

Ací tenim tots els nombres reals entre 0 i 1. Ara construirem un nombre x que hauria d'estar en la llista. Per a això fem servir els nombres de la diagonal.

r1 = 0. 5 1 0 5 1 1 0...
r2 = 0. 4 1 3 2 0 4 3...
r3 = 0. 8 2 4 5 0 2 6...
r4 = 0. 2 3 3 0 1 2 6...
r5 = 0. 4 1 0 7 2 4 6...
r6 = 0. 9 9 3 7 8 3 8...
r7 = 0. 0 1 0 5 1 3 5...
...
  • El nombre x està definit així: al dígit xk li correspon el k-èssim dígit de rk + 1 (si fóra un nou, li assignem el zero).

Llavors x= 0.6251346.... El nombre x és clarament un de real. Però... on està x ?

Si jo volguera dir que x està en el n-èssim lloc de la meua llista, no seria cert, puix que l'element n-èssim dígit de rn és distint al de x.

  • Llavors, aquesta no és una llista completa dels reals en l'interval [0,1].
  • Existeix una contradicció, per suposar que aquests nombres són infinits numerables.

Per a estendre aquest resultat a R hem d'establir una relació bijectiva entre aquest interval i els reals. Açò és possible gràcies a una funció com aquesta:

f: (0,1)\rightarrow\mathbb{R} definida per f\left(x\right)=\tan\left(\pi\left(x-\frac{1}{2}\right)\right).

Amb açò podem dir que hi ha tants nombres reals com reals entre 0 i 1.

Vegeu també[modifica | modifica el codi]