Diagonalització de Cantor

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

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, (r₁, 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 x_k li correspon el k-èssim dígit de r_k més 1 (si fóra un 9, se li assignaria el 0).

En l'exemple, r_k = 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 r_n é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:

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

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

Vegeu també

• Teorema de Cantor
• Conjunt numerable
• Funció bijectiva
• Nombre cardinal