Uncountability de aumentar las funciones de N

Question

Creo que he hecho un intento razonable para responder a la siguiente pregunta. Me gustaría una confirmación de mi prueba, para ser correcta, o ayuda en cuanto a por qué es incorrecto.

Pregunta: Deje $f : \mathbb{N} \to \mathbb{N}$ ser el aumento de la si $f(n+1) \ge f(n)$ todos los $n$. Es el conjunto $A$ funciones $f$ contables o incontables?

Para cada una de las $f$$A$, hay una función de $g: \mathbb{N}\cup \{0\} \to \mathbb{N} \cup\{0\}$ definido por $g(0)=f(1)$$g(n)=f(n+1)-f(n)$$n>0$. Por el contrario, para cada una de las $g: \mathbb{N}\cup \{0\} \to \mathbb{N}\cup\{0\}$$g(0)>0$, hay un aumento de la función de $f$ definida recursivamente por $f(1)=g(0)$$f(n+1)=f(n)+g(n)$$n>0$. En consecuencia, hay un bijection entre el $A$ y el conjunto de $B$, de $g: \mathbb{N}\cup\{0\} \to \mathbb{N}\cup\{0\}$, $g(0)>0$. Si $B$ es incontable, a continuación, $A$ debe ser incontables.

El conjunto $C$ $h: \mathbb{N}\cup\{0\} \to \{0,1,2,3,4,5,6,7,8,9\}$ $h(0)=1 $es un subconjunto de a $B$. Para cada real de a $x \in [1,2)$, no hay un único decimal de expansión con 1 antes del punto decimal, que NO finalice en trailing 9. Por definir por $n>0$, $h(n)=$ (n-esima dígitos de x después del punto decimal), tenemos una inyección de $[1,2)$ para el conjunto de $C$ (diferentes $x$ => diferentes expansiones decimales => x mapas a diferentes h). Desde el conjunto de reales en $[1,2]$ es incontable, el conjunto C es incontable, => el conjunto B es incontable, => el conjunto a es incontable.

Answer 1

Esta prueba funciona, pero parece innecesariamente detallado. Es más fácil probar que estrictamente creciente funciones forman una multitud innumerable (lo que implica que la monotonía creciente son innumerables así). Esto es debido a que es evidente que existe una correspondencia 1-1 entre estrictamente creciente funciones e infinitos subconjuntos de N (cada función está determinada únicamente por su rango). Se trata de un estándar resultado de que hay una cantidad no numerable de subconjuntos de N, de los cuales sólo countably muchos son finitos. Por lo tanto, hay una cantidad no numerable de infinitos subconjuntos.

Answer 2

Es bastante fácil de aplicar directamente el argumento de diagonalización. Que $\langle f_n\rangle$ sea una secuencia de funciones cada vez más de los naturales a sí mismo. Definir una función $f$ recursivamente por $f(1)=1$ y $$f(n+1)=f(n)+f_n(n+1)-f_n(n)+1.$ $ el % resultante de la función $f$es claramente diferente de cada función en la secuencia $\langle f_n\rangle$.

Answer 3

La prueba se ve bien para mí. Es un poco más largo de lo necesario, aunque.

A la derecha después de definir su conjunto $A$, lo que si nos restringimos a un subconjunto de a $A$ dado por el subconjunto de funciones monótonas $t: \mathbb{N} \to \mathbb{N}$ tal que $t(n+1)-t(n) \in \{0,1\}$$t(0)=k$.

A continuación, en su espíritu, podemos identificar cada una de las $t$ con la infinita secuencia binaria de su step-wise diferencias. Por otra parte, claramente para cualquier infinita secuencia binaria se puede construir la única $t$ de los que obtienen relacionados con ella. Entonces por Cantor de la diagonalización argumento sabemos $\{0,1\}^\mathbb{N}$ es incontable y hemos terminado.

Answer 4

Otra forma de mostrar que $A$ es incontable: Mostrar eso si $B=\{f_n: n\in N\}\subset A$ y $B\ne A$ como sigue:

Que $g(n)=\max \{1+f_j(n): j\leq n\}.$

Tenemos $g(n)> f_n(n)$ por cada $n. $ % que $g\ne f_n$para cada $n.$ % que $g \not \in B.$

Para cada $ n $ tenemos $g(n)=1+f_{j_n}(n)$ $j_n\leq n . $ % que $g(n+1)=\max \{1+f_j(n+1):j\leq n+1\}\geq 1+f_{j_n}(n+1)\geq 1+f_{j_n}(n)=g(n). $lo $ g\in A. $