¿Por qué no es contable$\{-1,1\}^{\mathbb{Z}^2}$?

Question

La gente de mi clase actuó como si fuera obvio, pero no estoy seguro:

¿Por qué este conjunto no es contable? PS

Entonces, este conjunto contiene todas las funciones de $$\{-1,1\}^{\mathbb{Z}^2}$ $

donde $$\mathbb{Z}^2\to\{-1,1\}$ es el conjunto de enteros.

¡Gracias por todas las buenas respuestas!

Answer 1

Hay un bijection de $\Bbb Z^2$ a $\Bbb N$, induciendo un bijection de $\{-1,1\}^{\Bbb Z^2}$ a $\{-1,1\}^{\Bbb N}$. Y $\{-1,1\}^{\Bbb N}$ es famosa por su incontable por Cantor de la diagonal argumento:

Supongamos por contradicción que es contable. Entonces es posible enumerar todas las funciones en $\{-1,1\}^{\Bbb N}$ como $f_1,f_2,f_3,\ldots$. Ahora considere la función $g\in \{ -1,1 \} ^{\Bbb N}$ dada por $$ g(n)=-f_n(n) $$ Esta función no puede ser igual a cualquiera de las funciones de $f_1,f_2,\ldots$, por lo que no está en la lista, contradiciendo que nuestra lista de contenidos de todas las funciones de $\{-1,1\}^{\Bbb N}$.

Answer 2

Considere la opción $\{-1, 1\}^{\mathbb{Z}^2}$ a $P(\mathbb{Z}^2)$ enviando una función $f$ al conjunto $\{x \in \mathbb{Z}^2 : f(x) = 1\}$ . El inverso es $S \rightarrow f$ donde $f(x) = \begin{cases} 1 \text{ if x $ \ en S$} \\ -1 \text{ otherwise} \end{cases}$

El conjunto de potencias de cualquier conjunto infinito es incontable por el teorema de Cantor.

Answer 3

Insinuación. Supongamos que $\{f_n\}_{n\in\mathbb{N}}$ es una lista contable de TODAS estas funciones de $\mathbb{Z}^2\to \{-1,1\}$ . Ahora defina una nueva función $g:\mathbb{Z}^2\to \{-1,1\}$ tal que para cualquier $(n,m)\in \mathbb{Z}^2$ , $g(n,m):=-f_{|n|}(n,m)$ . ¿La función $g$ pertenece a la lista?

Answer 4

Considere la más sencilla y que, ingenuamente, conjunto más pequeño $\{0, 1\} ^ \mathbb{N}$. Hay un claro cerca de bijection para el intervalo de $[0, 1]$ por escrito los reales en binario. Así, esto podría hacer que sea más claro que este juego es incontable y la tuya también.

Me dicen que cerca de bijection porque es necesario para considerar que la representación binaria no es siempre única. E. g. $0.011111... = 0.1000000...$. Usted puede ignorar esto si lo que deseas es una intuición de que el tamaño del conjunto. Para solucionar el problema, mira Schröder–Bernstein teorema.