# Cardinality of the set of all indicator functions

Let's say we have two sets $$X=\{A,B,C\}$$ and $$Y=\{0,1\}$$. We are trying to find the cardinality of the set of all functions from $$X$$ to $$Y$$. From my understanding, this is supposed to be equal to the size of the power set. So I list out the power set of $$X = \{\{0\},\{A\},\{B\},\{C\},\{A,B\},\{A,C\},\{B,C\},\{A,B,C\}\}$$. If i list out all functions $$i$$ seem to get $$16$$ NOT $$8(|Y|^{|X|} = 2^3)$$:

$$f(x) = 0$$ when $$x = \{0\}$$ and $$1$$ otherwise.

$$f(x) = 1$$ when $$x = \{0\}$$ and $$0$$ otherwise.

$$f(x) = 0$$ when $$x = \{A\}$$ and $$1$$ otherwise.

$$f(x) = 1$$ when $$x = \{A\}$$ and $$0$$ otherwise.

And you can go on and list two functions for each set in the power set. So I know I'm not understanding something but if someone could maybe list all such functions and clarify what I'm doing wrong here that would be great.

• You are listing functions from the Power set of $X$ to $Y$, not functions from $X$ to $Y$. You got $16$ but there are in fact many more ($2^8=256$). Oct 13, 2014 at 18:11

Your problem is that you’re not actually looking at functions from $X$ to $Y$: $\{0\}$ and $\{A\}$ are not elements of $X$, so $x$ can’t be either one of them when you consider $f(x)$. The $x$ in $f(x)$ can only be $A,B$, or $C$. Thus, one of the functions has $$f(A)=f(B)=f(C)=0\;.$$ Another has $f(A)=1$ and $f(B)=f(C)=0$. Yet another has $f(A)=f(C)=1$ and $f(B)=0$. If you list all of the possibilities systematically, you’ll find that there are indeed $8$ such functions.
Or you can notice that if $S$ is any subset of $X$, there is exactly one of these functions — I’ll call it $f_S$ — such that $f_S(x)=1$ if $x\in S$, and $f(x)=0$ if $x\in X\setminus S$. The correspondence between subsets of $X$ and these functions is a bijection: there’s one function for each subset, and each function determines a subset. Thus, there must be the same number of each.