2

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.

Mariusz Popieluch
  • 682
Csci319
  • 779
  • Do you really mean $D\to 0$? Or is it $D\to{0,1}$? Or in your definition, are partly defined "functions" allowed? – André Nicolas Apr 21 '15 at 01:10
  • @AndréNicolas the question is as above – Csci319 Apr 21 '15 at 01:13
  • They already said $\lvert D \rvert = n$ so $\lvert D \rvert = 2$ can't be right. – user4894 Apr 21 '15 at 01:15
  • 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}$. – André Nicolas Apr 21 '15 at 01:22
  • 1
    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. – André Nicolas Apr 21 '15 at 01:47

2 Answers2

2

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.

Ross Millikan
  • 374,822
  • so would $n=4$? – Csci319 Apr 21 '15 at 01:09
  • No, you defined $n=|D|$, so it is $3$ here. There is one more choice to make for the function. – Ross Millikan Apr 21 '15 at 01:14
  • 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. – Mariusz Popieluch Apr 21 '15 at 01:20
  • @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$. – Ross Millikan Apr 21 '15 at 01:22
  • 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} ,$. – Mariusz Popieluch Apr 21 '15 at 01:24
  • I was thinking of $2^{|D|}$ that is why I said $4$ – Csci319 Apr 21 '15 at 01:41
  • for the second part it would just be (∅,{0},{1},{0,1}) right? – Csci319 Apr 21 '15 at 01:43
  • See my answer, below. – Mariusz Popieluch Apr 21 '15 at 01:46
  • 1
    @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. – Ross Millikan Apr 21 '15 at 05:02
1

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.

Mariusz Popieluch
  • 682
  • 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)}$? – Csci319 Apr 22 '15 at 20:41
  • 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,$. – Mariusz Popieluch Apr 22 '15 at 21:19
  • Ok so the answer is $4$ because $n=2$ – Csci319 Apr 22 '15 at 22:00
  • 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. – Mariusz Popieluch Apr 22 '15 at 22:30
  • ok so if we do not know what $D$ is then we can say the answer for part one is $2^{|D|}$ – Csci319 Apr 23 '15 at 14:55