0
$\begingroup$

I am trying to count how many functions there are from a set $A$ to a set $B$. The answer to this (and many textbook explanations) are readily available and accessible; I am not looking for the answer to that question and please do not post it. Instead I want to know what fundamental mistake(s) I am making in counting the number of these functions. My reasoning is below, which I know is wrong after checking this question: How many functions there is from 3 element set to 2 element set?.


For an example case, I consider counting how many functions there are from set $A = \{0,1\}$ to set $B = \{a,b\}$. My understanding of the term function is that it is any possible mapping between elements of set $A$ to elements of set $B$. Thus, a possible function $F: A \times B$ is the function that maps each element of $A$ to no element of $B$, i.e. $f_0(0) = \emptyset, f_0(1) = \emptyset$. Another possible function is $f_1(0) = a, f_1(1) = \{a, b\}$.

I notice a pattern here: for each element of the set $A$, there are $|\mathcal P (B)|$ unique combinations of elements that it can map to. In this case, $\mathcal P(B) = \{\{a,b\}, \{a\}, \{b\}, \emptyset\}$. To count these functions, then, we can use the product rule, since the choice of what each element of $A$ maps to does not affect what another element of $A$ can map to (since we consider all functions).

There are $4$ choices for $0$ and $4$ choices for $1$. Therefore there are $16$ unique functions $F: A \times B$. For a sanity check, I've listed out all 16 possible functions.

$f_0(0) = \emptyset, f_0(1) = \emptyset$

$f_1(0) = \emptyset, f_1(1) = \{a\}$

$f_2(0) = \emptyset, f_2(1) = \{b\}$

$f_3(0) = \emptyset, f_3(1) = \{a, b\}$

$f_4(0) = \{a\}, f_4(1) = \emptyset$

$f_5(0) = \{a\}, f_5(1) = \{a\}$

$f_6(0) = \{a\}, f_6(1) = \{b\}$

$f_7(0) = \{a\}, f_7(1) = \{a, b\}$

$f_8(0) = \{b\}, f_8(1) = \emptyset$

$f_9(0) = \{b\}, f_9(1) = \{a\}$

$f_{10}(0) = \{b\}, f_{10}(1) = \{b\}$

$f_{11}(0) = \{b\}, f_{11}(1) = \{a, b\}$

$f_{12}(0) = \{a,b\}, f_{12}(1) = \emptyset$

$f_{13}(0) = \{a,b\}, f_{13}(1) = \{a\}$

$f_{14}(0) = \{a,b\}, f_{14}(1) = \{b\}$

$f_{15}(0) = \{a,b\}, f_{15}(1) = \{a, b\}$

The generalization: The number of functions $F: A \times B$ is $|\mathcal P(B)|^{|A|}$.


Now I know my reasoning is completely wrong, but why? Am I double counting? Do I misunderstand the definition of a function?

$\endgroup$
1
  • $\begingroup$ "My understanding of the term function is that it is any possible mapping between elements of set A to elements of set B." <-- your understanding is correct. Why did you map to subsets of set B instead? :) $\endgroup$ – Džuris Feb 10 '17 at 18:27
4
$\begingroup$

Technically, what you've done in your example is defined all possible functions $f:A \to \mathcal{P}(B)$. That is, you're sending elements of $A$ to elements of $\mathcal{P}(B)$. If you want to count functions $f:A \to B$, then the outputs must be elements of $B$, not subsets of $B$.

Another way to say this is that a function from $A$ to $B$ is a subset of $A\times B$. The things you list are really subsets of $A \times \mathcal{P}(B)$, since you have pairs of elements of $A$ with subsets of $B$.

$\endgroup$
1
  • 1
    $\begingroup$ This answer is probably a bit misleading to someone who's not familiar with the material. The things he's listed are relations, which do correspond to arbitrary subsets of $A \times B$, or to partial functions $A \to \mathcal{P}(B)$. Of course a function is a type of relation, but an arbitrary subset of $A \times B$ is not a function. $\endgroup$ – Daniel McLaury Sep 23 '14 at 23:41
2
$\begingroup$

A function $f : A \to B$ sends each element of $A$ to exactly one element of $B$.

$\endgroup$
1
$\begingroup$

A function $f:A\rightarrow B$ is a rule that assigns to an element of $A$ an $unique$ element of $B$. So, first of all, given $a\in A$, you can't say that it maps to nothing or to a subset of two or more elements. That won't be a function at all from $A$ to $B$, but since with each element of $A$ you are associating a subset of $B$, it will be a function from $A$ to the power set of $B$. And in that case, what you've computed is correct.

$\endgroup$
0
$\begingroup$

A function requires assignment so you cannot just not return anything. What you're calling a function is, in fact, a partial function.

$\endgroup$
3
  • 1
    $\begingroup$ Actually, he's counting arbitrary relations. $\endgroup$ – Daniel McLaury Sep 23 '14 at 4:25
  • $\begingroup$ @DanielMcLaury Could you clarify what the difference is between arbitrary relation and partial function? $\endgroup$ – user3898238 Sep 23 '14 at 4:48
  • 3
    $\begingroup$ A relation is any subset of $A \times B$. A partial function is one where each element of $A$ is paired with at most one element of $B$. A function is one where each element of $A$ is paired with exactly one element of $B$. $\endgroup$ – Daniel McLaury Sep 23 '14 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.