Funciones decrecientes $f:\mathbb{N} \rightarrow \mathbb{N}$

Question

Dejemos que $P=\{f:\mathbb{N} \rightarrow \mathbb{N}; f(i+1)\leq f(i) \ \forall \ i \in \mathbb{N}\}.$

Necesito mostrar 2 elementos de $P$ y demostrar que $P$ es contable (o no).

Creo que $P$ sólo tienen funciones constantes, y si esto es correcto, puedo demostrar que $P$ es contable. ¿Hay algún contraejemplo para esto?

Answer 1

Esta respuesta se basa en un bonito principio esbozado en un post de @Riemann'sPointyNose que ha sido borrado por una laguna argumental, que creo que se cierra en lo siguiente.

La idea es asignar a cualquier función $f: \mathbb{N}\to\mathbb{N}$ un número real de tal manera que cada $f\in P$ se asigna a un número racional.

Por ejemplo $f(1) = 245$ , $f(2) = 123$ , $f(3) = 10$ , $f(4) = 4$ , $f(5) = 4$ , ...

Luego concatena las representaciones decimales para obtener una cadena infinita $$\color{red}{2451231044\ldots}$$ Sin embargo, no podemos reconstruir de forma única la función $f$ de esta cadena porque no sabemos dónde están los límites de los números. Para solucionarlo, la intercalamos con otra secuencia formada por 0's y 1's, donde ponemos un 1 cada vez que "empieza un nuevo número". Es decir: $$\color{red}{2}\color{blue}{0}\color{red}{4}\color{blue}{0}\color{red}{5}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{2}\color{blue}{0}\color{red}{3}\color{blue}{1}\color{red}{1}\color{blue}{0}\color{red}{0}\color{blue}{1}\color{red}{4}\color{blue}{1}\color{red}{4}\color{blue}{1}\ldots$$ Esto nos permite reconstruir de forma única la función $f$ .

Ahora bien, tenga en cuenta que si $f$ se hace constante eventualmente, la cadena resultante será periódica eventualmente. Por lo tanto, si la consideramos como una expansión decimal de un número en $[0,1]$ el número será racional.

Dado que cada función en $P$ se vuelve constante eventualmente, esto nos da una inyectiva cartografía $$P \to \mathbb{Q}$$ y $P$ debe ser, por tanto, contable.

Answer 2

No es cierto que todos los $f\in P$ es constante. Tomemos, por ejemplo, $$f(n)=\begin{cases}2&\text{ if }n=1\\1&\text{ otherwise.}\end{cases}$$ Sin embargo, es cierto que, si $f\in P$ entonces hay algo de $N\in\Bbb N$ tal que $n\geqslant N\implies f(n)=f(N)$ . Y no es difícil deducir de esto que $P$ es efectivamente contable.

Answer 3

Te dejaré las formulaciones rigurosas, aquí están las ideas principales: (Tenga en cuenta también que utilizo $0\not\in\mathbb N$ Todos mis argumentos tienen que ser ligeramente adaptados si se quiere utilizar $0\in\mathbb N$ pero las ideas son exactamente las mismas)

---

Primero demostramos que cada $f\in P$ es eventualmente constante por contradicción. La intuición es que cualquier constante no eventual $f\in P$ tiene que bajar al menos $1$ infinitamente a menudo, pero $f$ no puede bajar por $1$ más de $f(1)$ tiempos.

Expresado con rigor: Si existe un $f\in P$ que no es eventualmente constante, entonces existen infinitas $n_1<n_2<n_3<\dots$ en $\mathbb N$ tal que $f(n_i+1)\le f(n_i)-1$ por cada $i\in\mathbb N$ .

Así que \begin {split} &f(n_{f(1)}+1)& \le &f(n_{f(1)})-1 \\ \le &f(n_{f(1)-1}+1)-1 & \le &f(n_{f(1)-1})-2 \\ \le &f(n_{f(1)-2}+1)-2 & \le &f(n_{f(1)-2})-3 \\ \le & \dots & \le & \dots \\ \le &f(n_{f(1)-(f(1)-1)}+1)-(f(1)-1)& \le & f(n_{f(1)-(f(1)-1)})-f(1), \\ \end {split} pero $f(n_{f(1)-(f(1)-1)})-f(1)=f(n_1)-f(1)\le 0$ lo que significa que $f(n_{f(1)}+1)\le0$ que es una contradicción con $f(n_{f(1)}+1)\in\mathbb N$ .

---

Ahora para demostrar que $P$ es contable, se podría utilizar que el conjunto de todas las funciones eventualmente constantes $f:\mathbb N\to\mathbb N$ es biyectiva a $\bigcup_{k\in\mathbb N} \mathbb N^k$ .