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
    Be careful declaring $G$ countable. * Is $\mathbb{S}$ given as part of the definition of $G$? Is it a particular set? Then yes, $G$ is countable. Let $n=|\mathbb{S}|$, then $G$ is just the set of all ordered pairs of integers of length $n$. This is countable. * Does $G$ include any function whose domain is *any* finite set? Then $G$ is really the set of all finite strings of integers. If we consider the set of all finite strings of just $\{0,1\}$, then we know this is uncountable. The set of strings of integers is at least as large as this set. – 2011-12-02
  • 0
    @John: The set of all finite binary strings most certainly *is* countable. – 2011-12-02
  • 0
    Doh, you're right. It's contained in the rational numbers. 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.