0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$). $\endgroup$ Oct 13, 2014 at 18:11

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .