Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  John Moeller Dec 2 '11 at 0:53
    
@John: The set of all finite binary strings most certainly is countable. –  Brian M. Scott Dec 2 '11 at 1:04
    
Doh, you're right. It's contained in the rational numbers. My bad. Perhaps I was thinking of infinite strings. –  John Moeller Dec 2 '11 at 1:19

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.