Mostrar el conjunto de todas las funciones de $\mathbb{N}$ à $\{0, 1\}$ es incontable mediante una contradicción.

Question

Esto es lo que he escrito:

Por contradicción, supongamos que es contable. Escribe $S=\{\text{all functions } \mathbb{N} \rightarrow \{0,1\} \}$ . Entonces, podemos encontrar una biyección $\mathcal{H}: S \rightarrow \mathbb{N}$ . Ahora, me gustaría comprobar cómo incorporar el método de Cantor para encontrar la contradicción. ¿Sería correcto pensar en cada función como una representación binaria (porque mapean a cualquiera de los dos $0$ o $1$ )? Entonces, escribiré

$f(1) \mapsto a_{11}a_{12}a_{13}...$

$f(2) \mapsto a_{21}a_{22}a_{23}...$

$f(3) \mapsto a_{31}a_{32}a_{33}...$

donde $a_{ij} \in \{0,1\}$ .

y así sucesivamente. Así, por ejemplo, $f(1)$ ha introducido cualquier número natural, por lo que escupirá un $0$ o un $1$ y he escrito todas las posibilidades en una lista.

A continuación, defino una función en $S$ es decir $0$ si un valor de cadena es $1$ y $1$ si el valor de la cadena es $0$ .

Tengo una pregunta más: ¿qué significa la notación $\{0,1\}^{\mathbb{N}}$ ?

Gracias.

Answer 1

Se puede conseguir la contradicción definiendo otra $f(x)$ que nunca puede estar en la lista como sigue:

$f(x)=b_{11}b_{22}\cdots, \hspace{2 mm} b_{ii}\neq a_{ii}$

Tenga en cuenta que $f(x)$ no puede estar en la lista de todos modos porque si hay un $j$ tal que $f(j)=f(x)$ entonces $b_{jj}=a_{jj}$ una contradicción. Así que no $1-1$ es posible el mapeo.

$\{0,1\}^{\mathbb{N}}$ es el conjunto de todas las funciones que mapean $\mathbb{N}$ à $\{0,1\}$ .

Answer 2

Tu idea es correcta, el uso de la representación binaria facilita mucho la explicación. Siempre se puede obtener un número binario que no esté en la lista y obtener una contradicción utilizando el método de la diagonal de Cantor

Answer 3

Esta es una aplicación clásica del argumento de Cantor, primero en lugar de pensar en funciones vamos a pensar en secuencias de 0's y 1's. Es decir, si $f: \mathbb{N} \to \{0,1\}$ y $f(1)=0, f(2)=1,f(3)=1, \ldots$ Me limitaré a escribir la secuencia $011\ldots$ . Supongamos que el conjunto es contable y enumeramos los elementos $$a_{1}=a_{11}a_{12}a_{13} \ldots\\ a_{2}=a_{21}a_{22}a_{23} \ldots\\ a_{3}=a_{31}a_{32}a_{33} \ldots\\ \vdots $$ Ahora construimos un elemento $b$ que no hemos enumerado tomando $$b_{n}=1 \text{ if }a_{nn}=0 \text{ or }b_{n}=1 \text{ if }a_{nn}=0$$ $b_{n}$ no está en la lista porque difiere de $a_{n}$ en el $n$ posición para todos los $n$ .