I'm trying to grasp countability concepts with regards to set theory and came across this question. I'm trying to prove in some way that certain sets are countable, uncountable, or finite.
If I have two sets, $\mathbb{N}$ and $\{1, 2, 3, …, i\}$, how can I prove whether the below are countable or uncountable or finite? $A, B, C$ are sets of functions.
$$\begin{align}
A &: \mathbb{N} \to \{1, 2, 3, …, i\} \\
B &: \{1, 2, 3, …, i\} \to \mathbb{N} \\
C &: \{1, 2, 3, …, i\} \to \{1, 2, 3, …, i\}
\end{align}$$
It can be assumed $i\geq1$ and $|\mathbb{N}| \gt |\{1, 2, 3, …, i\}|$.
I believe $C$ is finite as it is bijective between two finite sets. What about the other two?
Up to this point I've been using Cantor's Diagonalization and proofs by contradiction. I'm just not so versed in bijection, surjection, injection, etc I think which is relevant for this question.
Best Answer
Instead of $\{1,2,...,i\}$, we will instead work with the set $\{0,1,...,i-1\}$ (at least to analyze $A$). For $A$, note that for any $S\in A$, we have
$$S(\mathbb{N})=(S(1),S(2),...)$$
where $S(n)\in\{0,1,...,i-1\}$. To find the cardinality of $A$, note that there is a bijection between these types of ordered sets and the interval $[0,1]$. Simply note that every real number $x=[0,1]$ can be written as
$$x=\sum_{k=1}^\infty \frac{a_k}{i^k}$$
where $a_i\in\{0,1,...,i-1\}$. For example, if $i=2$, then one such $S$ is
$$S(\mathbb{N})=(S(1),S(2),...)=(1,0,0,1,1,0,...)$$
which corresponds to the number
$$\frac{1}{2}+\frac{0}{4}+\frac{0}{8}+\frac{1}{16}+\frac{1}{32}+\frac{0}{64}+...$$
We conclude $|A|=|\mathbb{R}|$. We will now go back to $\{1,2,...,i\}$. For $B$, note that any $S\in B$ can be written as
$$S(\{1,2,...,i\})=(S(1),S(2),...,S(i))$$
where $S(n)\in \mathbb{N}$. To find the cardinality of this set, note that there is a bijection between $B$ and natural numbers whose prime factorization includes the first $i$ primes. This bijection can be written as
$$S(\{1,2,...,i\})=(S(1),S(2),...,S(i))\leftrightarrow 2^{S(1)}3^{S(2)}...p_i^{S(i)}$$
Since this set is countable, we conclude $|B|=|\mathbb{N}|$. Finally, for $C$ it is easy to see that there are $i^i$ different functions from $\{1,2,...,i\}$ onto itself. For every element in the set you pick, there are $i$ choices for it to map to. We conclude $|C|=i^i$.