cardinalidad del conjunto de $ \varphi: \mathbb N \to \mathbb N$ tal que $\varphi$ es una secuencia de creciente

Question

Sé que el conjunto de funciones $ f:\mathbb N \to \mathbb N$ es incontable, pero ¿qué pasa si consideramos sólo el $f$ tal que $f$ va en aumento? Quiero saber si este sistema es contable D: y también el caso de biyectiva y aumentando (claramente si la firstone sostiene entonces esto también). Creo que podría ser posible que sea contable

Answer 1

Esto esencialmente está invirtiendo argumento inicial de Brian M. Scott...

Que $\mathbb{N}^{\mathbb{N}\uparrow}$ denotan la familia estrictamente creciente funciones $\mathbb{N} \to \mathbb{N}$. Dada cualquier función $f : \mathbb{N} \to \mathbb{N}$ $\Phi ( f ) : \mathbb{N} \to \mathbb{N}$ por $$\Phi ( f ) ( n ) = \sum_{i=0}^n ( f(i) + 1 )$$ Then $\Phi (f) $ is strictly increasing, and the mapping $f # \mapsto \Phi (f) de definir $ es uno a uno.

Por lo tanto, $| \mathbb{N}^\mathbb{N} | \leq | \mathbb{N}^{\mathbb{N}\uparrow} |$. Una rápida aplicación del teorema de Cantor-Bernstein-Schröder luego rendimientos $| \mathbb{N}^{\mathbb{N}\uparrow} | = | \mathbb{N}^\mathbb{N} | = 2^{\aleph_0}$.

Answer 2

Que $e_1,e_2,e_3,\dots$ ser cualquier secuencia de %#% de #% o $0$'s. Que $1$ y $a_1=1$.

Esto demuestra que hay al menos $a_{i+1}=a_i+e_i+1$ secuencias cada vez más. Así que hay exactamente $c$.

Answer 3

Es incontable. Supongamos que $f_n$ es una secuencia estrictamente creciente secuencias, que $g(0)=f_0(0)+1$; y $g(n+1)=\max\{g(n)+1, f_{n+1}(n+1)+1\}$. Claramente $g$ no es uno de lo $f_n$'s.

Answer 4

Deje $\mathscr{F}$ el conjunto de los estrictamente creciente de las funciones de la $\Bbb N$$\Bbb N$: a continuación,$|\mathscr{F}|=2^\omega=|\wp(\Bbb N)|$, lo $\mathscr{F}$ es, sin duda innumerables. Una forma de ver esto es la construcción de un bijection entre el$\mathscr{F}$${}^{\Bbb N}\Bbb N$, el conjunto de todas las funciones de$\Bbb N$$\Bbb N$. Esto no es demasiado difícil.

Definir una función $\mathscr{F}\to{}^{\Bbb N}\Bbb N:f\mapsto\hat f$ como sigue: vaya a $f\in\mathscr{F}$, y definir $\hat f$ mediante el establecimiento $\hat f(0)=0$$\hat f(k)=f(k)-f(k-1)-1$$k>0$. Es fácil comprobar que este mapa es un bijection, por lo $|\mathscr{F}|=\left|{}^{\Bbb N}\Bbb N\right|$, que usted probablemente ya sabe es $2^\omega=|\wp(\Bbb N)|$.

Añadido: la inversa de La mapa es bastante fácil escribir así: si $f\in{}^{\Bbb N}\Bbb N$, vamos

$$g:\Bbb N\to\Bbb N:n\mapsto n+\sum_{k\le n}f(k)\;.$$

a continuación, $$\hat g(n)=\left(n+\sum_{k\le n}f(k)\right)-\left((n-1)+\sum_{k\le n-1}f(k)\right)-1=f(n)\;,$$

es decir, $\hat g=f$.

Answer 5

Una buena idea de cómo probar esto fue dado en esta respuesta por Srivatsan. Estoy exponer aquí ya la otra pregunta se refiere a varios puntos, así que esto podría ser fácilmente olvidada entre las soluciones de otras partes de que se trate.

---

Considerar sólo los mapas de $\varphi \colon \mathbb N\to\mathbb N$ tal que $k$ se asigna a $2k$ o a $2k+1$.

Cada mapa está aumentando.

Tenemos dos posibilidades de elegir $\varphi(k)$ por cada $k$, por lo que no es $2^{\aleph_0}=\mathfrak c$ tales funciones. (Para hacer este argumento más riguroso, se puede mostrar que usted puede obtener para cada elemento de la $\{0,1\}^{\mathbb N}$ una función diferente de este formulario.)