Una extraña prueba del uncountability de los reales

Question

Así, en la comprobación de que los reales son innumerables usted asume lo contrario y tratar de hacer una lista de ellos. Trabajo en binario esta lista es de la forma $a_1,a_2,\ldots$ donde $a_i = x_{i,1}x_{i,2},\ldots$ representa el binario de expansión. Dado que cualquier índice $j$ algún número real (en realidad, un número infinito de ellos) tiene su $j$th dígitos $1$. Si $x_{j,j} \neq 1$ podemos intercambiar $a_j$ $a_k$ tal que $k > j$$x_{k,k} = 1$; por el comentario, por $a_k$ existe. Debido a $k > j$ no deshacer cualquier trabajo anterior. Por lo tanto podemos asumir que $x_{j,j} = 1$ todos los $j$. A continuación, $0$ no está en nuestra enumeración.

Este es, por supuesto, la diagonal argumento, pero es un poco inquietante para mí que la especificación de cualquier decimal de expansión de antemano, se podría haber hecho exactamente el mismo argumento para demostrar que ${\it any}$ número real no está en nuestra enumeración. Hay algo mal con este método es uncountability sólo este extraño?

Answer 1

Esto no prueba que $\mathbb R$ es incontable, a ver, ¿por qué considerar la siguiente "prueba" de que el $\mathbb N$ es incontable.

Suponga $\mathbb N$ es contable y tenemos un bijection $f\colon\mathbb N \to \mathbb N$ (por ejemplo, la identidad!). Quiero mostrar que hay un bijection que no contenga $0$, una contradicción. Bueno, si $f(0) = 0$, a continuación, intercambiar $f(0)$$f(1)$, de modo que obtenemos un bijection $f\colon \mathbb{N \to N}$ tal que $f(0) \neq 0$.

Por inducción si $f(x) \neq 0$ todos los $x < n$ pero $f(n) = 0$, a continuación, intercambiar $f(n)$$f(n + 1)$, de modo que podemos suponer $f(n) \neq 0$.

Cuando hacemos un intercambio, no modificamos los valores por debajo de $n$, por lo que "después de que" todos estos swaps, tenemos perfectamente bien definida la función $f\colon\mathbb{N \to N}$ con la propiedad de que $0$ no está en la imagen. Contradicción!

Excepto que no es una contradicción! No hay ninguna razón por la que resulta de la función de $f$ debería haber sido un bijection. De hecho, la función que se obtiene de este procedimiento es, simplemente,$f(n) = n + 1$. Este no es un bijection, pero eso no significa que no existe algún otro bijection $\mathbb{N \to N}$, al igual que la identidad de la función que empezamos!

Answer 2

Aunque el argumento se presenta a menudo como una prueba por contradicción, en realidad no lo es. En su lugar, muestra cómo, dada cualquier función de $f:\Bbb N\to\Bbb R$, en realidad se puede construir un determinado número real $r_f$ que no está en el rango de $f$. Por lo tanto, ninguna función de $\Bbb N$ $\Bbb R$puede ser surjective, y, por definición, $\Bbb R$ debe ser incontables. Cuando modifique su original $f$ por el intercambio de dos valores, usted es simplemente la sustitución de $f$ por una función diferente a $g:\Bbb N\to\Bbb R$, y el mismo argumento muestra que el rango de $g$ no $\Bbb R$. Desde $g$ $f$ no son la misma función, no debería extrañar que $r_g\ne r_f$.

Answer 3

Así que le dan una función $f:\ \Bbb N\to[0,1]$ que es sobreyectiva. Proceso involucrado y de ninguna manera "finitary", entonces construir una nueva función $g:\ \Bbb N\to[0,1]$ que no contiene $0$ en su imagen. No veo cómo esto prueba nada sobre el % dado $f$.