Diagonalització de Cantor

De la Viquipèdia, l'enciclopèdia lliure
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.[1] 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, r₂, r₃…)
  • 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.

Es podria obtenir aleshores una seqüència com la del següent exemple:

r₁ = 0. 5 1 0 5 1 1 0...
r₂ = 0. 4 1 3 2 0 4 3...
r₃ = 0. 8 2 7 5 0 2 6...
r₄ = 0. 2 3 3 9 1 2 6...
r₅ = 0. 4 1 0 7 2 4 6...
r₆ = 0. 9 9 3 7 8 3 8...
r₇ = 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.

r₁ = 0. 5 1 0 5 1 1 0...
r₂ = 0. 4 1 3 2 0 4 3...
r₃ = 0. 8 2 7 5 0 2 6...
r₄ = 0. 2 3 3 9 1 2 6...
r₅ = 0. 4 1 0 7 2 4 6...
r₆ = 0. 9 9 3 7 8 3 8...
r₇ = 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 més 1 (si fóra un 9, se li assignaria el 0).

En l'exemple,rk = 0.5179235..., i per tant x = 0.6280346...

El nombre x és clarament un de real, però on és x? Si afirméssim que x es troba en el n-èssim lloc de la llista, no seria cert, puix que el n-èssim 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.

Referències[modifica]

  1. Gardner, Martin. «3. Aleph-cero y aleph-uno». A: Carnaval matemático (en castellà). Alianza Editorial, p. 53. ISBN 9788491811503 [Consulta: 26 gener 2022]. «[La prueba de la diagonal de Cantor] Prueba que el conjunto de los números reales (racionales más irracionales) tampoco es numerable.» 

Vegeu també[modifica]