elementary set theory - Problems about Countability related to Function Spaces

Suppose we have the following sets, and determine whether they are countably infinite or uncountable .

1. The set of all functions from $\mathbb{N}$ to $\mathbb{N}$.





2. The set of all non-increasing functions from $\mathbb{N}$ to
   $\mathbb{N}$.




3. The set of all non-decreasing functions from $\mathbb{N}$ to
   $\mathbb{N}$.




4. The set of all injective functions from $\mathbb{N}$ to
   $\mathbb{N}$.




5. The set of all surjective functions from from $\mathbb{N}$ to
   $\mathbb{N}$.



6. The set of all bijection functions from from $\mathbb{N}$ to
   $\mathbb{N}$.

---

My thoughts on this:

1. The first set is uncountable by using diagonalization argument.




2. I have read something about it saying this is countable since we can see this as a set of finite sequences of natural numbers. But I have hard time following the argument.




3. The article I read says this is uncountable but I couldn't follow the argument either.





4. For (4),(5) and (6), I am not even sure how to approach problems like these.

Could someone please explain how to approach this kind of problems in general?

And does it matter when I change all the $\mathbb{N}$ to $\mathbb{R}$?

Answer

Another approach to the 6th part.

Let us denote the set of all bijections from $\mathbb N$ to $\mathbb N$ by $\operatorname{Bij}(\mathbb N,\mathbb N)$.

Clearly
$$|\operatorname{Bij}(\mathbb N,\mathbb N)| \le \aleph_0^{\aleph_0} = 2^{\aleph_0} = \mathfrak c.$$

Let us try to show the opposite inequality.

For arbitrary function $f\in\operatorname{Bij}(\mathbb N,\mathbb N)$ we define $$\operatorname{Fix}(f)=\{n\in\mathbb N; f(n)=n\}.$$ (That is, $\operatorname{Fix}(f)$ is the set of all fixed points of the map $f$.)
Let us try to answer the question, whether for any
$A\subseteq\mathbb N$ it is possible to find a bijection ${f_A}:{\mathbb N}\to {\mathbb N}$ such $\operatorname{Fix}(f_A)=A$. Let us consider two cases.

If the complement of the set $A$ is infinite, i.e. $\mathbb N\setminus A=\{b_n; n\in\mathbb N\}$ (and we can assume that the elements $\mathbb N\setminus A$ are written in the increasing order, i.e. $b_1 ), then we can define a function $f_A$ as follows:
$$f_A(x)= \begin{cases} x, & \text{if }x\in A, \\\ b_{2k+1}, &\text{if $x=b_{2k}$ for some $k\in\mathbb N$},\\\ b_{2k}, &\text{if $x=b_{2k+1}$ for some $k\in\mathbb N$}. \end{cases}$$
In the other words, we did not move the elements of $A$ and the elements from the complement were paired and we interchanged it pair.
Such map is a bijection from $\mathbb N$ to $\mathbb N$ such that $\operatorname{Fix}(f_A)=A$.

Next we consider the case that $\mathbb N\setminus A$ is finite.

If $\mathbb N\setminus A=\emptyset$, then $f=id_{\mathbb N}$ is a function fulfilling $\operatorname{Fix}(f_A)=\mathbb N=A$.

If the set $\mathbb N\setminus A$ is a singleton $\{a\}$, then is is impossible to find a bijection $f$ such that $\operatorname{Fix}(f)=A=\mathbb N\setminus\{a\}$. No element of $A$ can be mapped on $a$ (since all such elements are fixed). But $a$ cannot be mapped on $a$ since this would mean that $a$ is a fixed point.

But if the set $\mathbb N\setminus A$ has at least two elements, then it is possible to construct such a map. We again assume that the elements $b_k$ are written in the increasing order, i.e. $\mathbb N\setminus A=\{b_0,\dots, b_n\}$ and $b_0.
We put $f_A(x)=x$ for $x\in A$, $f_A(b_k)=b_{k+1}$ for $0\le k and $f_A(b_n)=b_0$. (I.e. we made a cycle consisting of elements of $\mathbb N\setminus A$.)

This defines a bijection ${f_A}:{\mathbb N}\to{\mathbb N}$ such that $\operatorname{Fix}(f_A)=A$.

The assignment $A\mapsto f_A$ that we described above is a map from the set $\mathcal P({\mathbb N})\setminus\{\mathbb N\setminus\{a\}\in\mathbb N\}$ consisting of all subsets of $\mathbb N$, whose complement is not a singleton, to the set $\operatorname{Bij}(\mathbb N,\mathbb N)$. This map is injective; since from $f_A=f_B$ we get $A=\operatorname{Fix}(f_A)=\operatorname{Fix}(f_B)=B$.

From the set $\mathcal P({\mathbb N})$ with the cardinality $\mathfrak c$ we have omitted a countable set $\{\mathbb N\setminus\{a\}\in\mathbb N\}$. Therefore the cardinality of this difference $\mathcal P({\mathbb N})\setminus\{\mathbb N\setminus\{a\}\in\mathbb N\}$ is again $\mathfrak c$.

So we found an injection from a set of cardinality $\mathfrak c$ to the set $\operatorname{Bij}(\mathbb N,\mathbb N)$. This yields the opposite inequality
$$\mathfrak c\le|{\operatorname{Bij}(\mathbb N,\mathbb N)}|$$
and by Cantor-Bernstein theorem we get $|{\operatorname{Bij}(\mathbb N,\mathbb N)}|=\mathfrak c$.