Let $\mathcal F$ be the set of mappings $f:\Bbb N \to \Bbb N$ for which $f(m) \ge f(n)$ for $m \le n$. Show that $\mathcal F$ is countable

Question

Let $\mathcal F$ be the set of mappings $f:\Bbb N \to \Bbb N$ for which $f(m) \ge f(n)$ for $m \le n$. Show that $\mathcal F$ is countable.

---

My attempt:

For all $f\in \mathcal F$, $f$ will be eventually constant, i.e. there exists $N\in \Bbb N$ such that $f(n)=f(N)$ for all $n>N$. Let $N_f$ be the least element of such $N$ for each $f\in \mathcal F$.

Let $\operatorname{Seq}(\Bbb N)$ be the set of all finite sequences from $\Bbb N$. We define a mapping $G:\mathcal F \to \operatorname{Seq}(\Bbb N)$ by $G(f)=f_{\restriction \{0,\cdots,N_f\}}$. Then $G$ is clearly injective. Hence $|\mathcal F| \le |\operatorname{Seq}(\Bbb N)|$. We already know that $\operatorname{Seq}(\Bbb N)$ is countable. It follows that $\mathcal F$ is countable.

---

My questions:

1. Does my proof look fine or contain gaps?

2. I feel that this proof depends on the theorem If $A$ is countable, then the set of finite sequences from $A$ is countable, which in turn requires several heavy lemmas. I would like to ask for a simpler proof.

Answer 1

Note that $f$ is a member of $\mathbb{N}^{N_f} \times \{c_f\}^\mathbb{N}$ (where $c_f$ is the final constant), which is a countable set for any fixed $(c_f, N_f)$ pair. There are only $\mathbb{N}^2$ such pairs. A countable union of countable sets is countable.

Answer 2

A possibly simpler proof (depending on your viewpoint) is to construct an explicit injection $\mathcal{F}\to\mathbb{N}$ by $$ f\in\mathcal{F}\mapsto 2^{f(0)}\times 3^{f(0)-f(1)}\times 5^{f(1)-f(2)}\times\cdots $$ The product is finite by exactly the same reason as that of the existence of $N_f$. Note this is only an injection, since it doesn't contain odd numbers >1, for example.

Answer 3

An alternative approach written for fun and/or clarity:

This produces a sequence with maximum $f(1)$ that eventually becomes constant (as pointed out in the OP). Let us just consider the cases where $f(1) = 3$ for concreteness. This means all sequences that are of one of the following forms:

• all $3$s

• finitely many $3$s, all $2$s

• finitely many $3$s, finitely many $2$s, all $1$s

Respectively, the number of these sequences is:

• one

• countably infinite: one for each possible place at which it switches from $3$ to $2$, which has size $|\mathbb{N}|$

• countably infinite: one for each possible place at which it switches from $3$ to $2$, and another for each possible place at which it switches from $2$ to $1$, which has size $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$

Altogether, we conclude that the number of sequences with $f(1) = 3$ constitutes a countably infinite collection: it corresponds to a a finite union of countable sets. But, a similar line of reasoning works for $f(1) = n$ for each $n \in \mathbb{N}$. Since the countable union of countable sets is countable, the assertion follows.