Argumento de la diagonal de Cantor

El primer argumento diagonal de Cantor

El ejemplo siguiente utiliza dos de los conjuntos infinitos más sencillos, el de los números naturales y el de las fracciones positivas. La idea es demostrar que ambos conjuntos, N {\displaystyle \mathbb {N} } y Q + {\displaystyle \mathbb {Q^{+}} } tienen la misma cardinalidad.

En primer lugar, las fracciones se alinean en una matriz, como se indica a continuación:

1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 4 2 5 ⋯ 3 1 3 2 3 3 3 3 5 ⋯ 4 1 4 2 4 3 4 4 5 ⋯ 5 1 5 2 5 3 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccc}{tfrac {1}{1}&&{tfrac {1}{2}&&{tfrac {1}{3}&{tfrac {1}{4}&&{tfrac {1}{5}}&&{cdots \\\&&&&&&&&&\\\ {tfrac {2}{1}&&{tfrac {2}{2}&&{\tfrac {2}{3}&&{\tfrac {2}{4}&&{\tfrac {2}{5}&\cdots \&&&&&&&&&{\tfrac {3}{1}&{tfrac {3}{2}&&{tfrac {3}{3}&{tfrac {3}{4}&{tfrac {3}{5}&{cdots \&&&&&&&&&\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \&&&&&&&&&\ {\tfrac {5}{1}&&{tfrac {5}{2}&&{tfrac {5}{3}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

A continuación, se cuentan los números, como se indica. Las fracciones que se pueden simplificar se omiten:

1 1 ( 1 ) → 1 2 ( 2 ) 1 3 ( 5 ) → 1 4 ( 6 ) 1 5 ( 11 ) → ↙ ↙ 2 1 ( 3 ) 2 2 ( ⋅ ) 2 3 ( 7 ) 2 4 ( ⋅ ) 2 5 ⋯ ↓ ↙ 3 1 ( 4 ) 3 2 ( 8 ) 3 3 ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 ⋯ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclc}{tfrac {1}{1}{{color azul noche}} y {{tfrac}{1}{2}{año}} {{color azul}(2)} y {{tfrac}{1}{3}{año}{año}(5)}{...y el color azul (6) y el color azul (11)...{{color azul noche}} {{flecha derecha}} {{color azul noche}} {{flecha verde}} {{color azul noche}} {{flecha verde}} {{color azul noche}} {{flecha verde}}}{y el color azul de medianoche...{{tfrac {2}} {{color Azul}}(\cdot )}&{tfrac {2}3} {{color Azul}(7)}&{tfrac {2}4} {{color Azul}(\cdot )}&&{tfrac {2}{5}&{cdots} {{color azul noche}{downarrow }&{color azul noche}{nearrow }&{{color azul noche}} {{flecha}} y {{color azul noche}} {{flecha}} &&&& {{tfrac {3}{1}} {{color azul}(4)}&&{{tfrac {3}{2} {{color azul}(8)}&{tfrac {3}{3}{color azul}(\cdot )}&{tfrac {3}{4}&&{{tfrac}{3}{5}&{cdots}&{color azul noche}{flecha}&{color azul noche}{flecha}}&&&&&&\\{{tfrac}} {4}{1} {{color azul}}(9)}&{tfrac} {4}{2}{{color azul}(\cdot )}&&{tfrac} {4}{3}&&{{tfrac {4}}&&{tfrac {4}{5}}&{cdots} {{color azul noche}}&{color azul noche}}&&&&&&&& {{tfrac {5}} {{color azul}(10)}&&{tfrac {5}{2}&&{tfrac {5}{3}&&{tfrac {5}{4}&&{\tfrac {5}{5}}&\cdots \\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\end{array}}}

Así se cuentan las fracciones:

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccc}{color {Azul}1}&{color {Azul}2}& {color {Azul}3}& {color {Azul}4}& {color {Azul}5}&{color {Azul}6}& {color {Azul}7}& {color {Azul}8}& {color {Azul}9}& {color {Azul}10}& {color {Azul}11}&{{color azul}} {puntos} {{color azul noche}} {flecha descendente}} {{color azul noche} {flecha descendente}} {{color azul noche} {flecha descendente}} {{color azul noche} {flecha descendente}}}{{color azul noche}} flecha abajo {{color azul noche}} flecha abajo {{color azul noche}} flecha abajo {{color azul noche}} flecha abajo {{color azul noche}}.{{color azul medianoche}} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha arriba.[3pt]1&{tfrac}{2}&2&3&{{tfrac {1}{3}}&{tfrac {1}{4}}&{tfrac {2}{3}&{tfrac {3}{2}}&4&5&{tfrac {1}{5}}&{cdots}{punto final}}

Al omitir las fracciones que aún se pueden simplificar, existe una biyección que asocia cada elemento de los números naturales, a un elemento de las fracciones:

Para demostrar que todos los números naturales y las fracciones tienen la misma cardinalidad, hay que añadir el elemento 0; después de cada fracción se añade su negativo;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccc}{color {Azul}1}&{color {Azul}2}& {color {Azul}3}& {color {Azul}4}& {color {Azul}5}& {color {Azul}6}& {color {Azul}7}&{color {Azul}8} {color {Azul}9} {color {Azul}10} {color {Azul}11} {color {Azul}12} {color {Azul}13} {color {Azul}14} {color {Azul}15}{\color {Blue}\cdots }\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{{color azul medianoche}} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha abajo}{color azul medianoche} flecha arriba.{color {azul de medianoche}descenso} y {color {azul de medianoche}descenso} y {color {azul de medianoche}descenso} y {color {azul de medianoche}descenso} y {color {azul de medianoche}descenso}[3pt]0&1&-1&{tfrac {1}{2}}-{tfrac {1}{2}}2&-2&3&-3&{tfrac {1}{3}}&-{tfrac {1}{3}}&{tfrac {1}{4}}&-{tfrac {1}{4}}&{tfrac {2}{3}}&-{tfrac {2}{3}}&{cdots \\\\\}end{array}}

De este modo, existe una biyección completa, que asocia una fracción a cada número natural. En otras palabras: ambos conjuntos tienen la misma cardinalidad. Actualmente, los conjuntos que tienen el mismo número de elementos que el conjunto de los números naturales se llaman contables. Los conjuntos que tienen menos elementos que los números naturales se llaman como máximo contables. Con esta definición, el conjunto de los números racionales / fracciones es contable.

Los conjuntos infinitos suelen tener propiedades que van en contra de la intuición: David Hilbert lo demostró en un experimento que se llama la paradoja de Hilbert del Gran Hotel.

Números reales

El conjunto de los números reales no tiene la misma cardinalidad que el de los números naturales; hay más números reales que naturales. La idea expuesta anteriormente influyó en su demostración. En su artículo de 1891, Cantor consideró el conjunto T de todas las secuencias infinitas de dígitos binarios (es decir, cada dígito es cero o uno).

Comienza con una demostración constructiva del siguiente teorema:

Si s₁ , s₂ , ... , s_n , ... es cualquier enumeración de elementos de T, entonces siempre hay un elemento s de T que no corresponde a ningún s _nen la enumeración.

Para demostrarlo, dada una enumeración de elementos de T, como por ejemplo

La secuencia s se construye eligiendo el 1er dígito como complementario del 1er dígito de s ₁(intercambiando 0s por 1s y viceversa), el 2do dígito como complementario del 2do dígito de s ₂, el 3er dígito como complementario del 3er dígito de s ₃, y generalmente para cada n, el n ^thdígito como complementario del n ^thdígito de s _n. En el ejemplo, esto da como resultado:

Por construcción, s difiere de cada s _n, ya que sus n^th dígitos difieren (resaltados en el ejemplo). Por lo tanto, s no puede aparecer en la enumeración.

A partir de este teorema, Cantor utiliza una prueba por contradicción para demostrar que:

El conjunto T es incontable.

Supone por contradicción que T era contable. En ese caso, todos sus elementos podrían escribirse como una enumeración s ₁, s₂ , ... , s_n , ... . Aplicando el teorema anterior a esta enumeración se obtendría una secuencia s que no pertenece a la enumeración. Sin embargo, s era un elemento de T y, por tanto, debería estar en la enumeración. Esto contradice la suposición original, por lo que T debe ser incontable.