Posiblemente no sea una prueba aceptable para la incontabilidad del producto contable de conjuntos contables

Question

Este es un texto del libro Topología por Munkres:

Teorema 7.7. $ \ \ \ $ Dejemos que $X$ denotan el conjunto de dos elementos $\{0,1\}.$ Entonces el conjunto $X^\omega$ es incontable.

Prueba. $\ \ \ \ $ Demostramos que, dada cualquier función $$g:\mathbb{Z}_+\longrightarrow X^\omega,$$ $g$ no es sobreyectiva. A tal efecto, denotemos $g(n)$ de la siguiente manera: $$g(n)=(x_{n1},x_{n2},x_{n3},..,x_{nn},...),$$ donde cada $x_{ij}$ es $0$ o $1$ . Entonces definimos un elemento ${\bf y}=(y_1,y_2,...,y_n,...)$ de $X^\omega$ dejando $$y_n=\begin{cases}0 &\text{if }x_{nn}=1, \\ 1 &\text{if }x_{nn}=0. \end{cases}$$ (Si escribimos los números $x_{ni}$ en una matriz rectangular, los elementos particulares $x_{nn}$ aparecen como las entradas diagonales de esta matriz; elegimos $\bf y$ para que su $n$ coordenadas difiere de la entrada diagonal $x_{nn}$ .)

Ahora $\bf y$ es un elemento de $X^\omega$ y $\bf y$ no se encuentra en la imagen de $g$ ; dado $n$ el punto $g(n)$ y el punto $\bf y$ difieren en al menos una coordenada, a saber, la $n$ th. Así, $g$ no es sobreyectiva. $$\tag*{$ \N - Plaza negra $}$$

Entiendo el texto pero no creo que el argumento sea correcto para ser considerado como prueba. Después de elegir alguna secuencia arbitraria de $0$ y $1$ (digamos $\alpha$ ), lo arreglamos antes de definir $y$ es decir $y$ se define a partir de un elemento fijo de $g(n)$ es decir $\alpha$ Así que

$1$ - Cómo demostrar que si $y\ne \alpha$ entonces $y\notin g(n)$ ? [nota que $y$ no es una entidad única fija]

$2$ - (Aclaraciones sobre la prueba mencionada y/o) Se agradecería una prueba alternativa más sencilla y clara.

---

Ejemplo más fácil pero similar : Dejemos que $Y={\{1,2,3}\}$ y $Z={\{a_1,a_2,a_3}\}$ y supongamos que quiero demostrar que dada cualquier función $f: Y\rightarrow Z$ , $f$ no es sobreyectiva. Definamos $f(i)=a_i$ . Elija una de las siguientes opciones $a_i$ de forma arbitraria y definir $z=a_{i+1}$ (mod $\mathbb {Z_3}$ ). Dado que $y=a_{i+1}\ne a_i$ y $a_i$ se eligió arbitrariamente para que $y$ no es la imagen de $f$ así que $f$ no es sobreyectiva. El mismo absurdo se da en el mencionado texto del libro.

Answer 1

El argumento está bien y podría decirse que es el más sencillo posible; simplemente lo has malinterpretado. No tengo ni idea de cuál es su $\alpha$ es. El elemento $y$ de $X^\omega$ es no definida a partir de alguna secuencia particular de ceros y unos; sólo depende de la función $g$ y una vez $g$ se ha dado, $y$ es fijo.

La idea de la prueba es muy sencilla. Da un algoritmo para tomar cualquier función $g:\Bbb Z_+\to X^\omega$ y construyendo a partir de $g$ un elemento $y^{(g)}=\langle y_1^{(g)},y_2^{(g)},y_3^{(g)},\ldots\rangle$ de $X^\omega$ de tal manera que $y^{(g)}$ no está en el rango de $g$ . Esto demuestra que no hay ninguna suryección de $\Bbb Z_+$ a $X^\omega$ y por lo tanto ciertamente no hay biyección.

¿Cómo nos aseguramos de que $y^{(g)}\ne g(n)$ para cualquier $n\in\omega$ ? Simplemente nos aseguramos de definir $y^{(g)}$ para que se diferencie de $g(n)$ en el $n$ -a posición. Si $g(n)$ tiene un $0$ en el $n$ -(es decir, si $x_{nn}=0$ ), entonces nos aseguramos de que $y_n^{(g)}=1$ en su lugar, y si $g(n)$ tiene un $1$ en el $n$ -(es decir, si $x_{nn}=1$ ), entonces nos aseguramos de que $y_n^{(g)}=0$ en su lugar.

Imagina que organizas las secuencias $g(1),g(2),g(3),\ldots$ en una columna, así:

$$\begin{array}{ccc} \color{red}{x_{11}}&x_{12}&x_{13}&x_{14}&x_{15}&\ldots\\ x_{21}&\color{red}{x_{22}}&x_{23}&x_{24}&x_{25}&\ldots\\ x_{31}&x_{32}&\color{red}{x_{33}}&x_{34}&x_{35}&\ldots\\ x_{41}&x_{42}&x_{43}&\color{red}{x_{44}}&x_{45}&\ldots\\ x_{51}&x_{52}&x_{53}&x_{54}&\color{red}{x_{55}}&\ldots\\ \vdots&\vdots&\vdots&\vdots&\vdots& \end{array}$$

Esta matriz está completamente determinada por la función $g$ que nos han dado. Ahora miramos la secuencia diagonal de ceros y unos, que he marcado en rojo:

$$x_{11},x_{22},x_{33},x_{44},x_{55},\ldots\tag{1}$$

Se trata de una secuencia de ceros y unos que viene determinada por la función $g$ . Creamos una nueva secuencia $y^{(g)}$ (Munkres' $y$ pero hago hincapié en su dependencia de $g$ ) cambiando cada $0$ en la secuencia $(1)$ a un $1$ y cada $1$ a un $0$ . ¿Puede esta secuencia

$$y_1^{(g)},y_2^{(g)},y_3^{(g)},y_4^{(g)},y_5^{(g)},\ldots$$

sea igual a cualquier fila de la matriz? No: difiere de la fila $3$ , por ejemplo, que es la secuencia $g(3)$ en el $3$ - la tercera posición: $g(3)$ tiene $x_{33}$ allí, y $y_3^{(g)}$ es cualquiera de $0$ y $1$ es no $x_{33}$ . Lo mismo ocurre con cada fila de la matriz, es decir, con cada una de las secuencias $g(n)$ , por lo que la secuencia $y^{(g)}$ no es igual a $g(n)$ para cualquier $n\in\Bbb Z_+$ . Es un elemento de $X^\omega$ que no está en el rango de $g$ Así que $g$ no puede ser sobreyectiva. Y como este algoritmo funciona sin importar la función $g$ empezamos, ninguna función $g:\Bbb Z_+\to X\to\omega$ puede ser sobreyectiva.

Answer 2

Para su referencia, esta es la prueba clásica del teorema. El argumento se llama Argumento de Diagonalización de Cantor.

$y$ no se basa en un elemento fijo de $g(n)$ se hace a partir de todos los valores $g$ puede tomar.

A continuación se explica cómo se construye con más detalle. Elegimos una función arbitraria, pero fija $g:\mathbb{Z}^+ \to X^\omega$ . Para nuestro ejemplo dejaremos que $g(1)=\{1,1,0,1,...\}$ , $g(2)=\{1,0,1,0,...\}$ , $g(3)=\{0,0,0,0,...\}.$

Ahora construimos $y$ . Dado que el primer elemento de la secuencia de $g(1)$ es $1$ , hacemos $y_1$ lo contrario, es decir $y_1=0$ . Ahora el segundo elemento de $g(2)$ es $0$ Así que $y_2=1$ . Ahora el tercer elemento de $g(3)$ es $0$ Así que $y_3=1$ . El proceso continúa para definir todos los elementos de $y$ .

Ahora comparamos $y = \{0,1,1,...\}$ con $g(n)$ . Por la forma en que se construyó vemos que $y\neq g(1)$ , $y\neq g(2)$ , $y \neq g(3)$ y así sucesivamente.

Así, $g$ pierde una secuencia contenida en $X^\omega$ . Dicha secuencia puede construirse para cualquier función de este tipo $g$ . Si $g$ no se perdió una secuencia, entonces $g$ sería suryente y $X^\omega$ sería contable. Por el contrario, si $X^\omega$ era contable, debe haber alguna función $g : \mathbb{Z}^+ \to X^\omega$ tal que $g$ es suryente.

Acabamos de demostrar que cualquier función de este tipo $g$ no puede ser sobreyectiva, por lo que $X^\omega$ no es contable.