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
    Commented Feb 10, 2017 at 18:27

4 Answers 4

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$ Commented Sep 23, 2014 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$ Commented Sep 23, 2014 at 4:25
  • $\begingroup$ @DanielMcLaury Could you clarify what the difference is between arbitrary relation and partial function? $\endgroup$ Commented Sep 23, 2014 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$ Commented Sep 23, 2014 at 4:50

You must log in to answer this question.

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