Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If we are given two infinite sets $X$ and $Y$ we can consider the set $S$ of all functions from $X$ to $Y$, which has cardinality $|Y|^{|X|}$.

Also, we can consider the set $F$ of all functions from $X$ to $Y$ having finite image. Is it true that $|F|=|Y|\cdot 2^{|X|}$?

If not, what is the cardinality of $F$?

share|cite|improve this question
It seems wrong as it is written... Suppose $Y=\{a\}$ be a singleton. Then, no matter what is the cardinality of $X$, there is basically just one map from $X$ to $Y$, which is the one which sends everything to $a$. So the formula does not convince me.. Am I misinterpretating something? – uforoboa Sep 4 '12 at 8:52
Are we assuming the axiom of choice somehow? – Asaf Karagila Sep 4 '12 at 9:23
@ufo, the question starts by positing that $Y$ is infinite. – Gerry Myerson Sep 4 '12 at 9:23
@Gerry: Check the timestamps, the infinite was added after uforoboa's comment. – Asaf Karagila Sep 4 '12 at 9:24
up vote 3 down vote accepted

Yes, it is true (assuming appropriate Choice, at least).

To settle on some notation, given sets $A$ and $B$ by ${^A}B$ I will denote the family of all functions $A \to B$ (and so $S = {^X}Y$). Also, for any set $B$ by $[B]^{< \omega}$ I will denote the family of all finite subsets of $B$.

Note that given any finite set $B$ we have that $$ | {^X}B | = \begin{cases} 0, &\text{if }B = \emptyset\\ 1, &\text{if }|B| = 1\\ 2^{|X|}, &\text{if }|B| > 1 \end{cases}$$

As the set $F$ of all functions $X \to Y$ with finite image is just $\bigcup \left\{ {^X}B : B \in [Y]^{<\omega} \right\}$, it follows that $$|F| = \left| \bigcup \{ {^X}B : B \in [Y]^{<\omega} \} \right| \leq \sum \left\{ | {^X}B | : B \in [Y]^{<\omega} \right\}.$$ This sum can be split up into three parts: where $B = \emptyset$, where $|B| = 1$, and where $|B| > 1$.

  • Clearly, $| {^X}\emptyset | = 0$.
  • If $|B| = 1$, then $| {^X}B | = 1$, and there are clearly $|Y|$-many such subsets of $Y$.
  • If $|B| > 1$, then as above $|{^X}B| = 2^{|X|}$. It is easy to show that there are $|Y|$-many such subsets of $Y$. ($| [Y]^{<\omega} | = |Y|$, and we can easily find $|Y|$-many distinct 2-elements subsets of $Y$.)

Our sum from above then becomes $$0 \cdot 1 + 1 \cdot |Y| + 2^{|X|} \cdot |Y| = 2^{|X|} \cdot |Y|.$$

Remember that this is, so far, just an upper bound. To get this as a lower bound fix distinct $x_0, x_1 \in X$. Then for each pair $y,z$ of distinct elements of $Y$ and each $A \subseteq X \setminus \{ x_1 \}$ containing $x_0$ define a function $f_{y,z,A} : X \to Y$ by $$f_{y,z,A}(x) = \begin{cases} y, &\text{if }x \in A \\ z, &\text{if }x \notin A. \end{cases}$$ Clearly these functions are all distinct, and there are $2^{|X|} \cdot |Y|$ many of them.

share|cite|improve this answer

Even more simply, if $A\subseteq Y$ is finite, there are $|A|^{|X|}\le2^{|X|}$ maps from $X$ to $A$, and $Y$ has $|Y|$ finite subsets, so $|F|\le|Y|\cdot2^{|X|}$. On the other hand, the constant maps from $X$ to $Y$ show that $|F|\ge|Y|$, and there are $2^{|X|}$ maps from $X$ to any fixed two-element subset of $Y$, so $|F|\ge 2^{|X|}$. Thus, $$|Y|\cdot2^{|X|}=\max\left\{|Y|,2^{|X|}\right\}\le|F|\le|Y|\cdot2^{|X|}\;,$$ and we have the desired result, $|F|=|Y|\cdot2^{|X|}$.

share|cite|improve this answer

Your Answer


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.