Suppose we have the following sets, and determine whether they are countably infinite or uncountable .
-
The set of all functions from $\mathbb{N}$ to $\mathbb{N}$.
-
The set of all non-increasing functions from $\mathbb{N}$ to
$\mathbb{N}$. -
The set of all non-decreasing functions from $\mathbb{N}$ to
$\mathbb{N}$. -
The set of all injective functions from $\mathbb{N}$ to
$\mathbb{N}$. -
The set of all surjective functions from from $\mathbb{N}$ to
$\mathbb{N}$. - The set of all bijection functions from from $\mathbb{N}$ to
$\mathbb{N}$.
My thoughts on this:
-
The first set is uncountable by using diagonalization argument.
-
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.
-
The article I read says this is uncountable but I couldn't follow the argument either.
-
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}$?
Best 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<b_2<\dots<b_n<b_{n+1}<\dots$ ), 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<b_1<\dots<b_n$. We put $f_A(x)=x$ for $x\in A$, $f_A(b_k)=b_{k+1}$ for $0\le k<n$ 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$.