Deje que$\mathcal F$ sea el conjunto de asignaciones$f:\Bbb N \to \Bbb N$ para las cuales$f(m) \ge f(n)$ para$m \le n$. Mostrar que$\mathcal F$ es contable

Question

Deje $\mathcal F$ el conjunto de asignaciones $f:\Bbb N \to \Bbb N$ para que $f(m) \ge f(n)$ para $m \le n$. Mostrar que $\mathcal F$ es contable.

---

Mi intento:

Para todos los $f\in \mathcal F$, $f$ será finalmente constante, es decir no existe $N\in \Bbb N$ tal que $f(n)=f(N)$ para todos los $n>N$. Deje $N_f$ ser el menor elemento de este tipo de $N$ por cada $f\in \mathcal F$.

Deje $\operatorname{Seq}(\Bbb N)$ ser el conjunto de todas las secuencias finitas de $\Bbb N$. Se define un mapeo $G:\mathcal F \to \operatorname{Seq}(\Bbb N)$ por $G(f)=f_{\restriction \{0,\cdots,N_f\}}$. A continuación, $G$ es claramente inyectiva. Por lo tanto $|\mathcal F| \le |\operatorname{Seq}(\Bbb N)|$. Ya sabemos que $\operatorname{Seq}(\Bbb N)$ es contable. De ello se desprende que $\mathcal F$ es contable.

---

Mis preguntas:

1. ¿Mi prueba de verse bien o contener huecos?

2. Siento que esta prueba depende del teorema de Si $A$ es contable, entonces el conjunto de secuencias finitas de $A$ es contable, que a su vez requiere de varias pesadas lemas. Me gustaría pedir una simple prueba.

Answer 1

Una prueba posiblemente más simple (dependiendo de su punto de vista) es construir una inyección explícita $\mathcal{F}\to\mathbb{N}$ por $$ f \ in \ mathcal {F} \ mapsto 2 ^ {f (0)} \ times 3 ^ {f (0 ) -f (1)} \ times 5 ^ {f (1) -f (2)} \ times \ cdots $$ El producto es finito por exactamente el mismo motivo que el de la existencia de $N_f$ . Tenga en cuenta que esto es solo una inyección, ya que no contiene números impares> 1, por ejemplo.

Answer 2

Tenga en cuenta que $f$ es un miembro de $\mathbb{N}^{N_f} \times \{c_f\}^\mathbb{N}$ (donde $c_f$ es la constante final), que es un conjunto contable para cualquier par de $(c_f, N_f)$ fijo. Solo hay $\mathbb{N}^2$ pares iguales. Una unión contable de conjuntos contables es contable.

Answer 3

Un enfoque alternativo escrito por diversión y/o claridad:

Esto produce una secuencia con un máximo de $f(1)$ que eventualmente se convierte en la constante (como se señaló en el OP). Vamos a considerar los casos en que $f(1) = 3$ para la concreción. Esto significa que todas las secuencias que son de una de las siguientes formas:

• todos los $3$s

• un número finito de $3$s, $2$s

• un número finito de $3$s, un número finito de $2$s, $1$s

Respectivamente, el número de estas secuencias es:

• uno

• countably infinito: uno para cada posible lugar en el que se cambia de $3$ a $2$, que tiene el tamaño de $|\mathbb{N}|$

• countably infinito: uno para cada posible lugar en el que se cambia de $3$ a $2$, y otro para cada posible lugar en el que se cambia de $2$ a $1$, que tiene el tamaño de $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$

En total, llegamos a la conclusión de que el número de secuencias con $f(1) = 3$ constituye un countably colección infinita: corresponde a una unión finita de conjuntos contables. Pero, en una línea similar de razonamiento funciona para $f(1) = n$ por cada $n \in \mathbb{N}$. Desde el contable de la unión de conjuntos contables es contable, la afirmación de la siguiente manera.