2
$\begingroup$

Given the problem:

  • Please count how many functions $f : D → \{0, 1 \}$ can be defined if the domain D is a finite set with the cardinality $|D| = n$.
  • Is there a bijection between the set of all such functions and the powerset $\mathcal{P}(D)$?

For the first question would the answer just be $|D|=2$?

I was hoping someone can give me a hint for the second question because I am not sure how to go about solving it.

$\endgroup$
5
  • $\begingroup$ Do you really mean $D\to 0$? Or is it $D\to\{0,1\}$? Or in your definition, are partly defined "functions" allowed? $\endgroup$ Commented Apr 21, 2015 at 1:10
  • $\begingroup$ @AndréNicolas the question is as above $\endgroup$
    – Csci319
    Commented Apr 21, 2015 at 1:13
  • $\begingroup$ They already said $\lvert D \rvert = n$ so $\lvert D \rvert = 2$ can't be right. $\endgroup$
    – user4894
    Commented Apr 21, 2015 at 1:15
  • $\begingroup$ If $A$ is a subset of $D$, define $f_A:D\to \{0,1\}$ by $f_A(x)=1$ if $x\in A$ and $f_A(x)=0$ if $x\not\in A$. The mapping $\varphi$ that maps $A$ to $f_A$ is a bijection from the power set of $D$ to the set of all functions from $D$ to $\{0,1\}$. $\endgroup$ Commented Apr 21, 2015 at 1:22
  • 1
    $\begingroup$ Note that we do not need to mention the "natural" bijection given above. There are $2^n$ functions, and the power set has $2^n$ elements, so sure, there is a bijection. $\endgroup$ Commented Apr 21, 2015 at 1:47

2 Answers 2

2
$\begingroup$

No, let $D=\{a,b,c\}$, so $n=3$. How many choices do you have for $f(a)$? How many for $f(b)?$ How many functions does that make overall? If you list the functions it may help with the answer for 2.

$\endgroup$
9
  • $\begingroup$ so would $n=4$? $\endgroup$
    – Csci319
    Commented Apr 21, 2015 at 1:09
  • $\begingroup$ No, you defined $n=|D|$, so it is $3$ here. There is one more choice to make for the function. $\endgroup$ Commented Apr 21, 2015 at 1:14
  • $\begingroup$ I would have thought that there are $2^{|D|}$ such functions, i.e. $f_1=\{(a,0),(b,0),(c,0) \} \,$, $f_2=\{(a,1),(b,0),(c,0) \} \,$, $f_3=\{(a,0),(b,1),(c,0) \} \,$, $f_3=\{(a,0),(b,0),(c,1) \} \,$, $f_4=\{(a,1),(b,1),(c,0) \} \,$,... 8 in total here. $\endgroup$ Commented Apr 21, 2015 at 1:20
  • $\begingroup$ @prime4567: You are correct. That is where I was hoping to get OP to. $n$ is not the number of functions, it is the number of elements of $D$. $\endgroup$ Commented Apr 21, 2015 at 1:22
  • 1
    $\begingroup$ @Csci319: as I said $|D|=3,$ so $2^{|D|}=2^3=8$. prime4567 has given a listing of the eight functions. You are not looking for subsets of $\{0,1\}$. You have two choices for $f(a)$, two for $f(b)$, two for $f(c)$, so $2^3=8$ total. Much more generally, the number of functions from $A$ to $B$ is $|B|^{|A|}$. You need to understand this. The logic is the multiplication principle for choices. $\endgroup$ Commented Apr 21, 2015 at 5:02
1
$\begingroup$

There are $2^{|D|}$ such functions. Example, let $D=\{a,b,c\}\,$, so $|D|=3\,$, but there will be 8 functions from $D$ to $\{0,1\}\,$, i.e.

$\\f_1=\{(a,0),(b,0),(c,0)\}\, , f_2=\{(a,1),(b,0),(c,0)\}\,, f_3=\{(a,0),(b,1),(c,0)\}\,,\\ f_4=\{(a,0),(b,0),(c,1)\}\,, ...,\,f_8=\{(a,1),(b,1),(c,1)\}\,.$

And the bijection between $D \rightarrow \{ 0,1\}$ and $\mathcal{P}(A)$ would be the obvious one: between the elements of $\mathcal{P}(A)$ and their characteristic functions in $D \rightarrow \{ 0,1\} \,$. That is, from the example above, $f_1$ maps to $\emptyset \,$, $f_2$ maps to $\{a\}$, and $f_8$ maps to $\{a,b,c\}=D \,$. You get the idea.

$\endgroup$
5
  • $\begingroup$ Thanks. so here we said $|D|=3$ why can't I say $|D|=2$ and say $f1={(a,0),(b,0)}$,$f2={(a,1),(b,0)}$,$f3={(a,0),(b,1)}$,$f4={(a,1),(b,1)}$? $\endgroup$
    – Csci319
    Commented Apr 22, 2015 at 20:41
  • $\begingroup$ No, that's also fine. Similarly for all $n$ sizes of $D$. Above is just an example, to give you the idea how it looks in general. So for $|D|=2$ the number of functions is $4$ (as you correctly noticed), for $|D|=3$ the number of functions id $8$ (my example),..., and in general for $|D|=n$ the number of functions $D \rightarrow \{0,1\}$ is $2^n\,$. $\endgroup$ Commented Apr 22, 2015 at 21:19
  • $\begingroup$ Ok so the answer is $4$ because $n=2$ $\endgroup$
    – Csci319
    Commented Apr 22, 2015 at 22:00
  • $\begingroup$ The special case, when $|D|=2\,$, i.e. $n=2\,$ is 4, but that's not the answer. The question asks for $D$ of any size $n\,$. Don't confuse reading $D \rightarrow \{0,1\}$ as $D = \{0,1\}$, and so confusingly take $|D|=2\,$. $\{0,1\}$ is the stipulated range (co-domain) of all the functions from the domain $D$ that you're supposed to count. $\endgroup$ Commented Apr 22, 2015 at 22:30
  • $\begingroup$ ok so if we do not know what $D$ is then we can say the answer for part one is $2^{|D|}$ $\endgroup$
    – Csci319
    Commented Apr 23, 2015 at 14:55

You must log in to answer this question.

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