Solución:
Primero, déjame darte una prueba de lo siguiente:
Sea $ mathbb {N} $ los números naturales, $ mathbb {N} = {1,2,3,4,5, ldots } $, y sea $ 2 ^ { mathbb {N}} $ ser el conjunto de todos secuencias binarias (funciones desde $ mathbb {N} $ a $ {0,1 } $, que pueden verse como “tuplas infinitas” donde cada entrada es $ 0 $ o $ 1 $).
Si $ f colon mathbb {N} to 2 ^ { mathbb {N}} $ es una función, entonces $ f $ no es sobreyectiva. Es decir, existe una secuencia binaria $ s_f $, que depende de $ f $, tal que $ f (n) neq s_f $ para todos los números naturales $ n $.
Lo que denoto $ 2 ^ { mathbb {N}} $ es lo que Wikipedia llama $ T $.
Representaré elementos de $ 2 ^ { mathbb {N}} $ como tuplas, $$ (a_1, a_2, a_3, ldots, a_n, ldots) $$ donde cada $ a_i $ es $ 0 $ o $ 1 $; estas tuplas son infinito; pensamos que la tupla define una función cuyo valor en $ n $ es $ a_n $, por lo que realmente corresponde a una función $ mathbb {N} to {0,1 } $. Dos tuplas son iguales si y solo si son idénticas: es decir, $$ (a_1, a_2, a_3, ldots, a_n, ldots) = (b_1, b_2, b_3, ldots, b_n, ldots) text {si y solo si} a_k = b_k text {para todos} k. $$
Ahora, suponga que $ f colon mathbb {N} to 2 ^ { mathbb {N}} $ es una función dada. Para cada número natural $ n $, $ f (n) $ es una tupla. Denote esta tupla por $$ f (n) = (a_ {1n}, a_ {2n}, a_ {3n}, ldots, a_ {kn}, ldots). $$ Es decir, $ a_ {ij} $ es la entrada $ i $ ésima en $ f (j) $.
Quiero mostrar que esta función no es sobreyectiva. Con ese fin, construiré un elemento de $ 2 ^ { mathbb {N}} $ que no está en la imagen de $ f $. Llame a esta tupla $ s_f = (s_1, s_2, s_3, ldots, s_n, ldots) $. Ahora diré qué es $ s_k $. Defina $$ s_k = left { begin {array} {ll} 1 & mbox {if $ a_ {nn} = 0 $;} \ 0 & mbox {if $ a_ {nn} = 1 $. } end {matriz} right. $$
Esto define un elemento de $ 2 ^ { mathbb {N}} $, porque define una tupla infinita de $ 0 $ sy $ 1 $ s; este elemento depende del $ f $ con el que comenzamos: si cambiamos el $ f $, el $ s_f $ resultante puede cambiar; esta bien. (Este es el “elemento diagonal”).
Ahora, la pregunta es si $ s_f = f (n) $ por unos $ n $. La respuesta es no.” Para ver esto, sea $ n in mathbb {N} $ cualquier número natural. Entonces $$ f (n) = (a_ {1n}, a_ {2n}, a_ {3n}, ldots, a_ {nn}, ldots) $$ entonces la $ n $ ésima entrada de $ f (n) $ es $ a_ {nn} $. Si la $ n $ ésima entrada de $ f (n) $ es $ 0 $, entonces por construcción la $ n $ ésima entrada de $ s_f $, $ s_n $ es $ 1 $, entonces $ f (n) neq s_f $. Si la entrada $ n $ ésima de $ f (n) $ es $ 1 $, entonces, por construcción, la entrada $ n $ ésima de $ s_f $, $ s_n $, es $ 0 $. Luego $ f (n) neq s_f $ nuevamente, porque no están de acuerdo con la entrada $ n $ ésima.
Esto significa que por cada $ n in mathbb {N} $, $ s_f $ no puede ser igual a $ f (n) $, porque difieren en la entrada $ n $ ésima. Entonces $ s_f $ es no en la imagen de $ f $.
Lo que hemos mostrado es que dada una función $ f colon mathbb {N} to 2 ^ { mathbb {N}} $, hay algún elemento de $ 2 ^ { mathbb {N}} $ que no está en la imagen de $ f $. El elemento depende de lo que sea $ f $, por supuesto; diferentes funciones tendrán posiblemente diferentes “testigos” del hecho de que no son sobreyectivos.
Piense en la función $ f $ que se lleva ante un juzgado y acusado de ser superviviente; para probar su inocencia, $ f $ presenta un testigo para verificar su coartada de que no es sobreyectiva; este testigo es $ s_f $, que puede jurar que $ f $ no es sobreyectiva porque $ s_f $ demuestra que $ f $ no es sobreyectiva: $ s_f $ no está en $ mathrm {Im} (f) $; si la policía arrastra en algún otro función $ g $ y acusar ese En función de ser sobreyectiva, $ g $ también tendrá que presentar un testigo para verificar su coartada de que no es sobreyectiva; pero ese testigo no tiene que ser el mismo testigo que presentó $ f $. El “testigo” que produzcamos dependerá de quién sea el “acusado”.
La razón por la que esto se llama el “argumento diagonal” o la secuencia $ s_f $ el “elemento diagonal” es que al igual que uno puede representar una función $ mathbb {N} a {0,1 } $ como un infinito ” tupla “, por lo que se puede representar una función $ mathbb {N} to 2 ^ { mathbb {N}} $ como una” lista infinita “, enumerando la imagen de $ 1 $, luego la imagen de $ 2 $, luego la imagen de $ 3 $, etc: $$ begin {align *} f (1) & = (a_ {11}, a_ {21}, a_ {31}, ldots, a_ {k1}, ldots) f (2) & = (a_ {12}, a_ {22}, a_ {32}, ldots, a_ {k2}, ldots) \ & vdots \ f (m) & = (a_ { 1m}, a_ {2m}, a_ {3m}, ldots, a_ {km}, ldots) end {align *} $$ y si uno imagina la función de esta manera, entonces la forma en que construimos $ s_f $ es “bajando por la diagonal principal”, mirando $ a_ {11} $, $ a_ {22} $, $ a_ {33} $, etc.
Ahora, recuerde la definición de “contable”:
Definición. Se dice que un conjunto $ X $ es contable si y solo si existe una función $ f colon mathbb {N} to X $ que es sobreyectiva. Si no existe tal función, se dice que $ X $ es incontable.
Eso significa que el teorema que probamos anteriormente muestra que:
Teorema. El conjunto de todas las secuencias binarias, $ 2 ^ { mathbb {N}} $, es no contable.
¿Por qué? Porque mostramos que no hay funciones sobreyectivas $ mathbb {N} to 2 ^ { mathbb {N}} $, por lo que no es contable.
¿Cómo se relaciona esto con los números reales? Los números reales son biyectable con el conjunto $ 2 ^ { mathbb {N}} $. Es decir, hay una función $ H colon 2 ^ { mathbb {N}} $ a $ mathbb {R} $ que es tanto uno a uno como sobre. Si tuviéramos una sobreyección $ mathbb {N} to mathbb {R} $, entonces componiendo esta sobreyección con $ H $ obtendríamos una sobreyección de $ mathbb {N} $ a $ 2 ^ { mathbb {N} } $, y no existe tal sospecha. Por lo tanto, no puede haber una sobreyección de $ mathbb {N} $ a $ mathbb {R} $, por lo que $ mathbb {R} $ no es contable (es decir, no es contable).
Biyectar $ mathbb {R} $ con $ 2 ^ { mathbb {N}} $ es un poco complicado; primero puedes biject $ mathbb {R} $ con $[0,1]PS entonces querrás usar la representación binaria (como en el artículo de wikipedia), de modo que cada secuencia corresponda a una expansión binaria, y cada número en $[0,1]$ corresponde a una secuencia binaria (sus dígitos cuando se escriben en binario); el problema es que al igual que algunos números en decimal tienen dos representaciones ($ 1 $ y $ 0.999 ldots $ son iguales), algunos números tienen dos representaciones en binario (por ejemplo, $ 0.01 $ y $ 0.0011111 ldots $ son iguales). Hay una forma de solucionar este problema, pero es un poco técnico y puede ocultar el problema, por lo que prefiero no entrar en él.
En su lugar, permítame señalar que el conjunto $ 2 ^ { mathbb {N}} $ se puede asignar de una manera uno a uno dentro $ (0,1) $: simplemente toma una secuencia binaria $$ (a_1, a_2, a_3, ldots, a_n, ldots) $$ y mapea al número decimal que tiene $ 5 $ en el $ k $ th posición decimal si $ a_k = 0 $, y tiene $ 6 $ en la posición decimal $ k $ ésima si $ a_k = 1 $. El uso de $ 5 $ y $ 6 $ garantiza que cada número tenga solo una representación decimal, por lo que el mapa es uno a uno. Llame a este mapa $ h $. Defina $ H colon mathbb {R} to 2 ^ { mathbb {N}} $ de la siguiente manera: dado un número real $ x $, si $ x $ está en la imagen de $ h $, defina $ H (x) $ sea la secuencia única $ s $ tal que $ h (s) = x $. Si $ x $ es no en la imagen de $ h $, luego defina $ H (x) $ como la secuencia $ (0,0,0, ldots, 0, ldots) $. Observe que $ H $ es sobreyectiva, porque $ h $ se define en todo $ 2 ^ { mathbb {N}} $.
Esto es suficiente para demostrar que no puede haber sobreyección de $ mathbb {N} $ a $ mathbb {R} $: suponga que $ f colon mathbb {N} to mathbb {R} $ es cualquier función . Entonces la función $ H circ f colon mathbb {N} stackrel {f} { to} mathbb {R} stackrel {H} { to} 2 ^ { mathbb {N}} $ es una función desde $ mathbb {N} $ a $ 2 ^ { mathbb {N}} $. Dado que cualquier función desde $ mathbb {N} $ a $ 2 ^ { mathbb {N}} $ no es sobreyectiva, hay algunos $ s en 2 ^ { mathbb {N}} $ que no están en la imagen de $ H circ f $. Desde $ s $ es en la imagen de $ H $, existen algunos $ x in mathbb {R} $ tales que $ H (x) = s $. Eso significa que $ f (n) neq x $ para todos $ n $ (desde $ H circ f (n) neq s $).
Dado que no puede haber sobreyección de $ mathbb {N} $ a $ mathbb {R} $, eso significa que $ mathbb {R} $ es incontable.
Entonces, en cuanto a sus preguntas. Primero, debe comprender que el argumento diagonal se aplica a una lista dada. usted ya tener todo $ s_1 $, $ s_2 $, $ s_3 $, etc., frente a ti. Nadie puede cambiarlos. Construye el “número diagonal” (mi $ s_f $ arriba) sobre la base de esa lista. Sí, si cambia la lista, puede poner el número diagonal $ s_f $ en la nueva lista; pero $ s_f $ es solo un testimonio del hecho de que el original list no era una lista de todas las secuencias. Si cambia a una lista diferente, tendré que presentar un testigo diferente. Los testigos dependen de la lista dada. usted saber que $ s_4 $ no es igual a $ s_f $ porque $ s_f $ está construido precisamente de modo que no está de acuerdo con $ s_4 $ en la posición $ 4 $ ésima, y un desacuerdo es suficiente para garantizar la desigualdad.
La presentación de Wikipedia parece argumentar por contradicción; No me gusta introducir eso en estas discusiones porque el argumento es lo suficientemente difícil de “asimilar” sin la complicación adicional. (La parte “De lo contrario …” es un argumento por contradicción, argumentando que si podría ‘enumerar’ los elementos de $ T $, luego aplicaría el argumento para mostrar que esta ‘lista completa’ no está ‘completa’, etc.). No hay necesidad. Simplemente, no hay sobreyección de $ mathbb {N} $ a $ T $, como se discutió anteriormente.
Ahora, hay una “primera reacción” común de que este argumento se aplicaría “igual de bien” a los números naturales: tome una lista de números naturales enumerados en binario y diseñe un argumento como el argumento diagonal (por ejemplo, “reflejándolos sobre el punto decimal “, por lo que salen con una cola de ceros a la derecha; o escribiéndolos de izquierda a derecha, con el dígito menos significativo primero, en lugar del último) para producir un” número “que no está en la lista. Puedes hacer eso, pero el problema es que los números naturales solo corresponden a secuencias que terminan con una cola de $ 0 $ s, y tratar de hacer el argumento diagonal necesariamente producirá un número que sí no tiene una cola de $ 0 $ s, por lo que no puede representar un número natural. La razón por la que el argumento diagonal funciona con secuencias binarias es que $ s_f $ es ciertamente una secuencia binaria, ya que no existen restricciones sobre las secuencias binarias que estamos considerando.
Espero que esto ayude.
La idea, en pocas palabras, es asumir por contradicción que los reales son contables. Debido a eso, puede escribirlos como $ a_i $ por $ i in mathbb N $. Esta lista contiene todos los números reales.
Al tomar el número producido por el argumento diagonal, se asegura en el $ n $ -ésimo paso de que no es uno de los $ a_1, ldots, a_n $. Cuando la inducción “termina”, ha producido un número real que no es ninguno de los $ a_i, i in mathbb N $.
Esto solo podía significar una cosa: la enumeración no capturó todos los números reales como lo asumiste.
Dado que la enumeración no fue específica, sino arbitraria, deducimos que cualquier enumeración contable de los reales no cubrirá todos los números reales. Esto, por definición, significa que los números reales son incontables.
Apéndice:
Después de leer más detenidamente la mayor parte de este hilo (en sus comentarios, etc.), creo que debería agregar algunas palabras sobre la prueba por contradicción, que es un método muy común en matemáticas.
“Las matemáticas son una ciencia de deducciones”, dijo mi prof de álgebra lineal. el primer día de mi B.Sc.
“Suponemos A, B, C y deducimos D, E, F “, continuó.
Lo importante de la capacidad de deducir cosas es mantener la coherencia. En palabras simples, significa no poder probar tanto algo como su negación. ¿Porque es esto importante? Porque es simple de probar cualquier cosa de la contradicción, de hecho, de acuerdo con este xkcd, incluso es posible derivar números de teléfono (aunque nunca logré hacerlo yo mismo).
La prueba por contradicción explota la suposición de que usamos un sistema axiomático consistente. Si asumimos una cosa y derivamos de ella una contradicción, entonces nuestra suposición era falsa.
Dado que algo es verdadero o falso, si es falso, entonces su negación es verdadera.
Entonces, ¿qué hice en la prueba anterior? Comencé asumiendo que las matemáticas tal como las conocemos son consistentes, luego agregué la suposición “Los reales son contables”. Si son contables, entonces, por definición, podemos enumerarlos como se indicó anteriormente.
El argumento diagonal muestra que, independientemente de cómo vaya a enumerarlos, muchos índices contables no son suficientes, y para cada lista podemos fabricar fácilmente un número real que no esté presente en ella. De esto deducimos que no hay listas contables que contengan todos los números reales. Es decir, los reales no son contables, lo que contradice nuestra suposición de que son contables.
Debo agregar que algunas de las pruebas por contradiccin no Realmente requieren el supuesto contrapositivo. En este caso, por ejemplo, podría haber dicho “dada una lista contable arbitraria de números reales, podemos obtener un número real que no está en la lista” y deducir de eso que los números reales son incontables. A veces, sin embargo, la contradicción es un poco más esencial para la prueba.
El argumento diagonal se comprende mejor examinando primero los casos finitos. Suponga que $ rm : M _ {: ! I : j} : $ es una matriz $ rm n times n $ cuyas entradas se encuentran en un conjunto $ rm : T : $ con en al menos dos elementos. Entonces uno puede construir un $ rm 1 times n $ fila $ rm : R : $ diferente de cualquier fila $ rm : M _ {: ! I} : $ de $ rm : M : $ tomando la diagonal $ rm : M _ {: ! I : i} : $ y cambiando cada una de sus entradas, a saber. $ rm : R _ {: ! i}: = neg : A _ {: ! i : i}, : $ donde $ : neg : $ es cualquier función de “cambio” en $ rm : T, : $ es decir $ rm : neg : t ne t : $ $ rm : forall : t in T. : $ Tenga en cuenta que $ rm : R : $ no es igual a ninguna fila $ rm : M _ {: ! I} : $ ya que su entrada $ rm : i $ ‘es diferente, es decir, $ rm : R _ { : ! i} = : neg : M _ {: ! i : i} ne M _ {: ! i : i} :. : $
Ver cada fila $ rm : M _ {: ! I} : $ como una función $ rm : j mapsto M _ {: ! I : j} : $ desde $ rm : n = {0 1 : cdots : n-1 } : $ a $ rm : T, : $ la prueba muestra que hay más de $ rm : n : $ tales funciones, es decir, $ rm : | T ^ {: ! n} | > n : $ if $ rm : | T | ge 2 :. : $ Obviamente, la prueba se generaliza desde $ rm : n : $ a cualquier conjunto $ rm : S, : $ dando que $ rm : | T ^ S | > | S | :. : $ Esto ilustra la esencia simple de la diagonalización, que no se debe a Cantor, sino a du Bois-Reymond (quien la usó para diagonalizar las tasas de crecimiento de funciones, es decir, “órdenes de infinito”) .