Diagonalització de Cantor

De Viquipèdia
Dreceres ràpides: navegació, cerca
Il·lustració de l'argument de la diagonal de Cantor (en base 2) per a l'existència de conjunts no numerables. La successió de la part inferior no pot aparèixer enlloc de l'enumeració de successions de la part superior.

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-èsim 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-èsim lloc de la meua llista, no seria cert, puix que l'element n-èsim dígit de rn és diferent del 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:

definida per

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

Vegeu també[modifica | modifica el codi]