[Math] the cardinality of the set of functions having finite image

cardinalselementary-set-theory

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

Best Answer

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.

Related Question