Argumento de diagonalización de Cantor

Na teoría de conxuntos, o argumento de diagonalización de Cantor, foi publicado en 1891 por Georg Cantor como unha proba matemática de que hai conxuntos infinitos que non se poden mapear nunha correspondencia un a un co conxunto de números naturais infinitos.^[1]^[2]^[3] Estes conxuntos coñécense agora como conxuntos incontábeis (ou non numerábeis), e o tamaño dos conxuntos infinitos agora tratase coa teoría dos números cardinais que iniciou Cantor.

O argumento da diagonalización non foi a primeira proba de Cantor da non numerabilidade dos números reais; en realidade publicouse moito máis tarde do que a súa primeira proba, que apareceu en 1874.^[4] No entanto, demostra unha técnica poderosa e xeral, que desde entón se utilizou nunha ampla gama de demostracións, tamén coñecidas como argumentos de diagonalización por analoxía co argumento usado nesta proba. Os exemplos máis famosos son o paradoxo de Russell, o primeiro dos teoremas de incompletitude de Gödel, e a resposta de Turing ao Entscheidungsproblem (problema da decisión).

Conxunto incontábel

No seu artigo de 1891, Cantor considerou o conxunto T de todas as secuencias infinitas de díxitos binarios (é dicir, que consta só de ceros e uns). Comeza cunha demostración construtiva do seguinte teorema:

Se s₁, s₂, ..., s_n, ... é calquera enumeración dos elementos de T, entón sempre hai un elemento s de T que non corresponde con ningún s_n na enumeración.

Para demostralo, dada unha enumeración dos elementos arbitrarios de T, por exemplo:

e constrúe a secuencia s escollendo o seu enésimo díxito como complemento do e-nésimo díxito de sn, para todo n. No exemplo, isto dá como resultado:

Por construción, s difire de todo s_n, xa que os seus enésimos díxitos difiren (resaltados no exemplo). Polo tanto, non pode aparecer s na enumeración.

Baseándose neste teorema, Cantor usa entón un argumento indirecto para demostrar que:

O conxunto T é incontábel (ou non numerábel).

Asume a contradición de que T era contábel. Entón (todos) os seus elementos pódense escribir como unha enumeración s₁, s₂, …, s_n, … . Aplicando o teorema anterior a esta enumeración produciríase unha secuencia s non pertencente á enumeración. No entanto, s era un elemento de T e, polo tanto, debe estar na enumeración. Isto contradí a suposición orixinal, polo que T debe ser incontábel.

Interpretación

A interpretación do resultado de Cantor depende do punto de vista matemático que se teña en conta. Para os construtivistas, o argumento non mostra mais que non hai bixección entre os números naturais e T. Non se exclúe a posibilidade de que estes últimos estean infravalorados. No contexto das matemáticas clásicas, isto é imposíbel, e o argumento da diagonalización estabelece que aínda que ambos os conxuntos son infinitos, en realidade hai máis secuencias infinitas de ceros e uns que números naturais.

Números reais

A incontabilidade dos números reais xa foi estabelecida pola primeira proba de non numerabilidade de Cantor, mais tamén se desprende do resultado anterior. Para ver isto, imos construír unha correspondencia un a un entre o conxunto T de cadeas binarias infinitas e un subconxunto de R (o conxunto de números reais). Dado que T é incontábel, este subconxunto de R debe ser incontábel. Polo tanto, R é incontábel.

Para construír esta correspondencia un a un (ou bixección), teña en conta que a secuencia t = 0111... aparece despois do punto flotante na correspondencia binaria 0.0111.... Isto suxire definir a función f(t) = 0.t, onde t é unha cadea de caracteres en T. Desafortunadamente, f(1000...) = 0.1000... = 1/2, e f (0111...) = 0.0111... = 1/4 + 1/8 1/16 + + … = 1/2. Así, esta función non é unha bixección xa que dúas cadeas corresponden a un número, un número con dúas correspondencias binarias.

No entanto, modificando esta función prodúcese unha bixección de T no intervalo (0, 1), é dicir, os números reais maiores que 0 e inferiores a 1. A idea é eliminar os elementos "problemáticos" de T e (0, 1) e tratalos por separado. De (0, 1), elimina os números que teñen dúas correspondencias binarias. Pomos estes números nunha secuencia: a = (1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, ...). Eliminamos as cadeas de T que aparecen despois da coma binaria nas correspondencias binarias de 0, 1, e os números da secuencia de a. Colocamos estas cadeas nunha secuencia: b = ( 000 …, 111 …, 1 000 …, 0 111 …, 01 000 …, 11 000 …, 00 111 …, 10 111 …,…). Unha bixección g(t) de T a (0, 1) defínese por: Se t é unha cadea n na secuencia b, sexa g (t) o número de orde n na secuencia a ; en caso contrario, g(t) = 0.t.

Para construír unha bixección de T en R: comezamos coa función tanxente tan(x), que nos dá unha bixección de (-π / 2, π / 2) en R; ver imaxe. Entón observe que a función linear h(x) = πx - π/2 dá como resultado a bixección de (0, 1) en (-π/2, π /2); ver imaxe. A función composta tan(h(x)) = tan (πx - π/2) dá unha bixección de (0, 1) en R. Compomos con esta función g(t) para obter tan (h(g(t))) = tan (πg(t) - π/2), que é unha bixección de T en R. Isto significa que T e R teñen a mesma cardinalidade - esta cardinalidade chámase "cardinalidade do contínuo".

Conxuntos xerais

Cantor utilizou a forma xeneralizada do argumento da diagonalización para demostrar o seu teorema: para cada conxunto S o conxunto de partes de S, é dicir, o conxunto de todos os subconxuntos de S (aquí escritos como P (S)), ten unha cardinalidade maior que S en si. Esta proba dáse do seguinte xeito:

Sexa f unha función de S a P (S). Basta demostrar que f non pode ser sobrexectiva. Isto significa que algún membro T de P (S), é dicir, un subconxunto de S, non é a imaxe de f. Como exemplo, considere o seguinte conxunto:

T = { s ∈ S: s ∉ f (s) }.

Para todo s en S, ou s está en T ou non. Se s está en T, entón por definición de T, s non está en f(s), polo que T non é igual a f(s). Por outra banda, se s non está en T, entón por definición de T, s está en f(s), polo que de novo T non é igual a f(s). Para unha descrición máis completa desta demostración, consulte o teorema de Cantor.

Consecuencias

Este resultado implica que a noción do conxunto de todos os conxuntos é unha noción inconsistente. Se S fose o conxunto de todos os conxuntos, entón P (S) sería maior que S e un subconxunto de S.

O paradoxo de Russell demostrounos que a inxenua teoría de conxuntos, baseada nun esquema de comprensión sen restricións, é contraditoria. Teña en conta que existe unha semellanza entre a construción de T e o conxunto do paradoxo de Russell. Polo tanto, dependendo de como modifiquemos o esquema axiomático da comprensión para evitar o paradoxo de Russell, argumentos como a inexistencia dun conxunto de todos os conxuntos poden seguir sendo válidos ou non.

O argumento da diagonalización mostra que o conxunto de números reais é "maior" que o conxunto de números naturais (e polo tanto tamén o conxunto de números enteiros e racionais). Polo tanto, podemos preguntarnos se existe un conxunto cuxa cardinalidade estea "entre" a dos números enteiros e os números reais. Esta pregunta leva á hipótese do continuo. Do mesmo xeito, a cuestión de se existe un conxunto cuxa cardinalidade estea entre |S| e |P (S)| para algún infinito S leva á hipótese do continuo xeneralizada.

Notas

↑ Georg Cantor (1892). "Ueber eine elementare Frage der Mannigfaltigkeitslehre" (PDF). Jahresbericht der Deutschen Mathematiker-Vereinigung 1890–1891 1: 75–78 (84–87 in pdf file). Arquivado dende o orixinal (PDF) o 2016-05-28. Consultado o 2019-06-01. (in german)
↑ Keith Simmons (30 de julho de 1993). Universality and the Liar: An Essay on Truth and the Diagonal Argument. pp. 20–. ISBN 978-0-521-43069-2.
↑ Walter (1976). Principles of Mathematical Analysis. New York. p. 30. ISBN 0070856133.
↑ Ethan D. (2011). The Real Numbers and Real Analysis. New York. p. 429. ISBN 978-0-387-72176-7.

Véxase tamén