cardinality of specific sets without using cardinal arithmetic

Question

Find the cardinality of the following sets without using cardinal arithmetic.

1. $S,$ the set of all functions $f:\mathbb{N}\to \mathbb{N}$
2. $T,$ the set of all nonincreasing functions $f:\mathbb{N}\to\mathbb{N}.$
3. $U$, the set of all nondecreasing functions $f:\mathbb{N}\to\mathbb{N}.$

I think $1$'s cardinality is the same as that of the real numbers, which can be verified using cardinal arithmetic. Without using cardinal arithmetic, I could define a bijection between $S := \{f :\mathbb{N}\to \mathbb{N}\}$ to $2^\mathbb{N}$, the set of all functions from $\mathbb{N}$ to $\{0,1\}.$ The identity function is an injective function from $2^\mathbb{N}$ to $S$ as $2^\mathbb{N}\subseteq S.$ Thus I just need to find a surjective function from $2^\mathbb{N}$ to $S$ or an injective function from $S$ to $2^\mathbb{N}.$ I was thinking of the function $F: S\to2^\mathbb{N}, F(f)(n) = n\mod 2,$ which is well-defined. But I'm not sure if it's injective.

I think $2$'s cardinality is countable. The map that maps each natural number to its corresponding constant function is clearly injective and well-defined (constant functions are nonincreasing). Now let $g \in T$ and $m := \min \{g(n)\in\mathbb{N} : n\in\mathbb{N}\},$ which is well-defined by the well-ordering property of $\mathbb{N}.$ Let $n_0$ be the first index for which $g(n) = m.$ Then since $g$ is nonincreasing, $g(n) = m$ for all $n\geq n_0$ (if $g(n) < m$ for some $n$, this would contradict the minimality of $m$). Thus we can map $g$ to the tuple $(g(1), g(2),\cdots, g(n_0)) \in \mathbb{N}^{n_0}.$ This defines an injective map from $T$ to $\cup_{n=1}^\infty \mathbb{N}^n,$ which is a countable union of countable sets and hence countable.

Finally, I think $3$'s cardinality is not countable. I think the following is an injection from $2^\mathbb{N}$ to $U$:

for $f \in 2^\mathbb{N},$ map it to the function $g : \mathbb{N}\to \mathbb{N}, g(n) = \sum_{i=1}^n f(i)2^i.$ $g$ is clearly nondecreasing, so this map is well defined. Injectivity follows from the unique binary expansion of numbers. Thus $|2^\mathbb{N}|\leq |U|.$ Also, $U\subseteq S$ so $|U|\leq |S| = |2^\mathbb{N}|.$ Thus $|U| = |2^\mathbb{N}|.$

I'm most unsure about the justification for $1$; the justifications of the other two cardinalities seem reasonable, but are there simpler approaches?

Answer 1

Your guesses are all correct: $S$ and $U$ have the same cardinality as $\mathbb{R}$, while $T$ is countable. Your arguments in each case are also right, except your guess for showing in (1) that $\vert S\vert\le \vert 2^\mathbb{N}\vert$. Your $F$ is not injective (given $f$, consider $g: x\mapsto f(x)+2$).

Instead, we can use a neat trick. Given a function $f:\mathbb{N}\rightarrow\mathbb{N}$, consider the set $G_f=\{(a,b)\in\mathbb{N}^2: f(a)=b\}$ (this is sometimes called the graph of $f$). The map $f\mapsto G_f$ is injective, and so we get $\vert S\vert\le\vert 2^{\mathbb{N}^2}\vert$. Do you see how to finish?

Use the fact that $\vert\mathbb{N}\vert=\vert\mathbb{N}^2\vert$.