# What is the cardinality of the set of functions having finite image?

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$?

-
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

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.

-

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|}$.

-