Es el conjunto de funciones suryentes de $\mathbb{N}$ a $\mathbb{N}$ ¿incontable?

Question

Quiero utilizar el argumento de la diagonalización de Cantor para demostrar que el conjunto S de funciones sobreyectivas de la forma $\Bbb{N} \to \Bbb{N}$ es incontable. El procedimiento normal es crear una matriz y llenarla con elementos de S e introducir una nueva función suryectiva $p$ El problema que tengo es que no sé cómo cambiar los elementos diagonales para que $p$ debería, pero no puede estar en la matriz.

¿Puede alguien ayudarme, o al menos darme algunos consejos?

Answer 1

Entre las proyecciones $\mathbb N\to\mathbb N$ tienes los mapas $$f(n)=\begin{cases}k&\text{if }n=2k\\g(k)&\text{if }n=2k-1\end{cases}$$ donde $g\colon\mathbb N\to\mathbb N$ es uno de los incontables arbitrario mapas $\mathbb N\to\mathbb N$ .

Answer 2

Lo que sigue es esencialmente la construcción de Asaf, excepto que creo que está un poco más cerca del método "diagonal" estándar. Asumo que, como en la imagen habitual del método diagonal, se nos da una matriz infinita y que queremos una nueva secuencia que difiera de cada fila de esa matriz, pero que también queremos que nuestra nueva secuencia contenga cada número natural al menos una vez. Empezaré produciendo cada segundo término de mi nueva secuencia; más tarde completaré los términos omitidos. La idea clave es utilizar una "diagonal" ligeramente diferente. En lugar de la "diagonal principal", que consiste en la $n$ -a entrada de la $n$ -en la fila de todos $n$ Utilizaré una "diagonal" de la mitad de la "pendiente". Es decir, en la $n$ -en la fila, me concentraré en el $2n$ -en la entrada, y me aseguraré de que mi nueva secuencia difiera de todas estas. Para ser más específico, definiré el $2n$ -enésima entrada de mi nueva secuencia que será $1$ más el $2n$ -ésima entrada en el $n$ - la cuarta fila. (Así que estoy definiendo los términos pares de mi nueva secuencia aquí; los Impares se definirán más tarde). Observe que, al hacer esto para cada $n$ Ya me he asegurado de que mi nueva secuencia difiera de cada fila de la matriz dada; concretamente, difiere de la fila $n$ en posición $2n$ Y esta diferencia está garantizada independientemente de lo que haga con las posiciones numeradas de impar en mi nueva secuencia. Pero ahora es fácil terminar el trabajo y ocuparse del requisito de surjetividad; basta con poner $k$ en el $k$ -a la posición de impar (es decir, a la posición $2k+1$ ) para cada $k$ .