= Solution
A <countable set> is one admitting an <injection> into $\mathbb N$; this includes finite sets and the empty set. An infinite <countable set> can equivalently be listed in a sequence indexed by $\mathbb N$.
For a <countable union of countable sets> $A=\bigcup_{i\geq1}A_i$, choose an <injection> $e_i:A_i\to\mathbb N$ for each nonempty $A_i$. Assign $x\in A$ the pair $(i,e_i(x))$, where $i$ is the least index with $x\in A_i$. This is an <injection> into $\mathbb N^2$. The pairs are countable by diagonal enumeration; explicitly, with natural numbers starting at one, the <Cantor pairing function>
$$
(i,j)\longmapsto\frac{(i+j-2)(i+j-1)}2+j
$$
maps them bijectively to $\mathbb N$. Composing the two maps proves that the union is countable. Empty members contribute no elements.
To prove uncountability of the <power set> $\mathcal P(\mathbb N)$, suppose all <subsets> could be listed as $A_1,A_2,\ldots$. Define
$$
D=\{n\in\mathbb N:n\notin A_n\}.
$$
For every $n$, $D$ differs from $A_n$ on whether it contains $n$. Thus $D$ is missing from the supposedly exhaustive list. This <Cantor diagonal argument> proves \b[$\mathcal P(\mathbb N)$ is uncountable].
For increasing functions in the question's non-strict sense, encode every <subset> $A\subseteq\mathbb N$ by
$$
f_A(n)=n+\sum_{k=1}^{n}\mathbf1_A(k),\qquad f_A(0)=0
$$
where the value at zero is only a convenient auxiliary convention. Then
$$
f_A(n)-f_A(n-1)=1+\mathbf1_A(n).
$$
Each $f_A$ is even strictly increasing, hence is a <nondecreasing function> as required, and its successive differences recover $A$ uniquely. This is an <injection> from the uncountable <power set> into the requested collection. Therefore \b[the increasing functions $\mathbb N\to\mathbb N$ form an <uncountable set>].
For a decreasing function in the question's sense, $f$ is a <nonincreasing function> with positive integer values. Each strict decrease lowers its value by at least one, so there can be at most $f(1)-1$ strict decreases. There is consequently a final drop, after which the function is constant. Every such function is determined by a finite initial list whose final value repeats forever. The set of all these lists is contained in
$$
\bigcup_{N=1}^{\infty}\mathbb N^N,
$$
a countable union of <countable sets>, hence countable by the result just proved. Thus \b[the decreasing functions $\mathbb N\to\mathbb N$ form a <countable set>]. These contrasting <cardinalities of monotone natural-number functions> come from the absence of an upper bound for increasing values and the finite number of drops available to decreasing natural-number values. If the natural numbers include zero, the same proof uses the bound $f(1)$ instead.
Back to article page
