1
$\begingroup$

Let $F = \{f: \mathbb{S}\rightarrow\mathbb{R}\}$ where $\mathbb{S}$ is a finite set.

Is the set of $F$ countable?


How about $G = \{f:\mathbb{S}\rightarrow\mathbb{Z}\}$ where $\mathbb{S}$ is also a finite set.

Is the set of $G$ countable?


My thought on this

Since we know that $\{f:\{0,1\}\rightarrow\mathbb{N}\}$ is countable. Then the set of $G$ is a variant of that. So $G$ is countable. But I am not sure how to approach the first one.

And also, is there a general way to prove that some set of functions that map a set to another set is countable or not?

  • 0
    Doh, you're right. It's contained in the rational num$b$ers. My bad. Perhaps I was thinking of infinite strings.2011-12-02

1 Answers 1

5

Your set $F$ is not countable unless $\mathbb{S}=\varnothing$. Suppose that $s\in\mathbb{S}$. For each $x\in\mathbb{R}$ define the function $f_x:\mathbb{S}\to\mathbb{R}$ by $f_x(t)=\begin{cases}0,&t\ne s\\x,&t=s\;.\end{cases}$ Clearly $f_x\ne f_y$ whenever $x\ne y$, so we have at least as many functions in $F$ as there are real numbers.

The general principle is that the number of functions from $A$ to $B$ is $|B|^{|A|}$, where $|X|$ is the cardinality of the set $X$. If $A$ and $B$ are both finite sets, this is just ordinary exponentiation. When at least one of $A$ and $B$ is infinite, however, as in your setting, it’s exponentiation of (possibly) infinite cardinal numbers, which is discussed here.

In your case $|F|=|\mathbb{R}|^{|\mathbb{S}|}$, and $|G|=|\mathbb{Z}|^{|\mathbb{S}|}$. Now $|\mathbb{Z}|=\aleph_0$, and $\mathbb{R}=2^{\aleph_0}$, so if $|\mathbb{S}|=n$, then $|G|= \aleph_0^n$, and $|F|=(2^{\aleph_0})^n$. If $\kappa$ is any infinite cardinal number, $\kappa^n=\kappa$ for every positive integer $n$, so $|G|=\aleph_0$, and $|F|=2^{\aleph_0}$. In particular, $G$ is countable, but $F$ is not.

More generally, if $\kappa>1$ and $\lambda$ is infinite, then $\kappa^\lambda\ge 2^{\aleph_0}>\aleph_0$, and if $\kappa>\aleph_0$ and $\lambda>0$, then $\kappa^\lambda\ge\kappa>\aleph_0$. Thus, the only way to get $\kappa^\lambda$ to be countable is to have $\lambda$ finite and $\kappa$ countable (including finite), or to have $\kappa\in\{0,1\}$ and $\lambda$ arbitrary. In other words, the set of functions from $A$ to $B$ is countable (including finite) if and only if either $B$ has at most one element, or $B$ is countable (including finite) and $A$ is finite.