Diagonalització de Cantor

De Viquipèdia
Salta a la navegació Salta a la 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]

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:

  • Suposi's que l'interval [0,1] és infinit numerable.
  • Es podria elaborar una seqüència dels nombres, (r1, r2, r3,...)
  • Se sap que els reals entre 0 i 1 poden ser representats solament escrivint els seus decimals.
  • Es col·loquen 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í hi ha tots els nombres reals entre 0 i 1. Ara es construeix un nombre x que hauria d'estar en la llista. Per a això es fa 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, se li assignaria el zero).

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

Si x es troba en el n-èsim lloc de la llista, no seria cert, puix que el n-èsim dígit de l'element 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 s'ha 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çò es pot dir que hi ha tants nombres reals com reals entre 0 i 1.

Vegeu també[modifica]