# Counting number of relations, functions, injective functions, and surjective functions between sets $A$ and $B$

Set Theory Question... Are my injective and surjective numbers correct?

Consider sets $$A$$ and $$B$$, with $$|A| = 7$$ and $$|B| = 3$$.

Let $$\{a1, a2, a3, a4, a5, a6, a7\}$$ be the $$7$$ elements that are in $$|A|$$.

Let $$\{b1, b2, b3\}$$ be the $$3$$ elements in $$|B|$$.

Let $$\boldsymbol{U}$$ be the set of all functions from $$A \to B$$.

Let $$\boldsymbol{F}_1$$ be the set of functions which do not send any element of $$A$$ into $$b_1$$.

Let $$\boldsymbol{F}_2, \boldsymbol{F}_3$$ be similar set of functions which do not send any element of $$A$$ into $$b_2, b_3$$, etc.

(a) How many relations are there from $$A$$ to $$B$$?

$$\boldsymbol{R} \to \boldsymbol{R}$$: $$f: A \to B = A \times B = 7 \times 3 = 21$$ elements $$= 2^{21}$$

(b) How many functions are there from $$A$$ to $$B$$?

$$f: A \to B = |B|^{|A|} = 3 = 2187$$

(c) How many injective functions are there from $$A$$ to $$B$$?

Not possible since number of elements in $$|B| < |A|$$.

(d) How many surjective functions are there from $$A$$ to $$B$$?

From the Inclusion-Exclusion Principle: $$n(A1 \cup A2 \cup \ldots \cup A_n) = s_1 – s_2 + s_3… +(-1)^{r-1} s_r$$

Alternatively: $$n(A_1^C \cap A_2^C \cap \ldots \cap A_n)^C = |\mathbb{U}| - s_1 + s_2 - s_3 - \ldots +(-1)^{r-1} s_r$$

$$3^7 = 2187$$

$$2^7 = 128$$

$$1^7 = 1$$

$$2187 – 128 + 1 = 2160$$

Now repeat the above four questions, but with $$|A| = 3$$ and $$|B| = 7$$.

(a) How many relations are there from $$A$$ to $$B$$?

$$\boldsymbol{R} \to \boldsymbol{R}$$: $$f: A \to B = A \times B = 7 \times 3 = 21$$ elements $$= 2^{21}$$

(b) How many functions are there from $$A$$ to $$B$$?

$$f: A \to B = |B|^{|A|} = 7^3 = 343$$

(c) How many injective functions are there from $$A$$ to $$B$$?

$$7 \cdot 6 \cdot 5 = 210$$

(d) How many surjective functions are there from $$A$$ to $$B$$?

Not possible, since $$|A| = m$$ and $$|B| = n$$ where $$m \geq n$$.

• Please edit the question and use mathjax for all places where formulas or mathematical objects are used. math.meta.stackexchange.com/questions/5020/… - For instance, it is better to use $A$ instead of A. To get the union use $\cup$, to get indices use underscore, e.g. $A_1$ - so $A_1\cup A_2$ delivers $A_1\cup A_2$. (You need a space after \cup here, since else \cupA would be the token, and there is no such macro.) Is some index is "longer", e.g. $A_{11}$ use A_{11} - to get { in math modus use \{ Commented Oct 14, 2021 at 22:40
• You meant to write $3^{\color{red}{7}} = 2187$ in part (b). You can express $3^7$ by writing $3^7$`. This tutorial explains how to typeset mathematics on this site. Commented Oct 15, 2021 at 8:10

$$|A| = 7$$, $$|B| = 3$$

How many relations are there from $$A$$ to $$B$$?

Your answer is correct, but you were careless in your use of equal signs. You cannot equate the functions from $$A$$ to $$B$$ with its cross product or the cross product with the number of elements in the cross product.

A relation is a subset of the cross product, so the number of relations from $$A \to B$$ is the number of subsets of the cross product $$A \times B$$. Since $$|A| = 7$$ and $$B = 3$$, $$|A \times B| = 7 \cdot 3 = 21$$. Since a set with $$n$$ elements has $$2^n$$ subsets, there are $$2^{21}$$ subsets of $$|A \times B|$$, so there are $$2^{21}$$ relations from $$A$$ to $$B$$.

How many functions are there from $$A$$ to $$B$$?

Again, your answer is correct, but you were careless in your use of equal signs and omitted the exponent $$7$$ from your calculation. You cannot equate the functions from $$A$$ to $$B$$ with the number of functions from $$A$$ to $$B$$.

The number of functions $$f: A \to B$$ is $$|B|^{|A|} = 3^7 = 2187$$.

How many injective functions are there from $$A$$ to $$B$$?

You are correct since $$A$$ and $$B$$ are finite sets with $$|A| > |B|$$.

How many surjective functions are there from $$A$$ to $$B$$?

Applying the Inclusion-Exclusion Principle is the right strategy, but you did not implement it correctly.

By the Inclusion-Exclusion Principle, the number of surjective functions $$f: A \to B$$ is $$|\boldsymbol{U}| - |\boldsymbol{F_1}| - |\boldsymbol{F_2}| - |\boldsymbol{F_3}| + |\boldsymbol{F_1} \cap \boldsymbol{F_2}| + |\boldsymbol{F_1} \cap \boldsymbol{F_3}| + |\boldsymbol{F_2} \cap \boldsymbol{F_3}| - |\boldsymbol{F_1} \cap \boldsymbol{F_2} \cap \boldsymbol{F_3}|$$ where $$|\boldsymbol{U}|$$ is the number of functions $$f: A \to B$$ and $$|\boldsymbol{F}_i|$$, $$1 \leq i \leq 3$$, is the number of functions $$f: A \to B$$ which exclude the element $$b_i$$ from the range.

$$|\boldsymbol{U}|$$: As you stated, $$|\boldsymbol{U}| = 3^7$$.

$$|\boldsymbol{F_1}|$$: If the element $$b_1$$ is excluded from the range, each of the seven elements in the domain must be mapped to one of the remaining two elements in the codomain. Hence, $$|\boldsymbol{F_1}| = 2^7$$.

By symmetry, $$|\boldsymbol{F_1}| = |\boldsymbol{F_2}| = |\boldsymbol{F_3}|$$.

$$|\boldsymbol{F_1} \cap \boldsymbol{F_2}|$$: If the elements $$b_1$$ and $$b_2$$ are excluded from the range, all seven elements in the domain must be mapped to $$b_3$$. Hence, $$|\boldsymbol{F_1} \cap \boldsymbol{F_2}| = 1^7$$.

By symmetry, $$|\boldsymbol{F_1} \cap \boldsymbol{F_2}| = |\boldsymbol{F_1} \cap \boldsymbol{F_3}| = |\boldsymbol{F_2} \cap \boldsymbol{F_3}|$$.

$$|\boldsymbol{F_1} \cap \boldsymbol{F_2} \cap \boldsymbol{F_3}|$$: There are no functions that exclude all three elements of the codomain from the range.

Hence, by the Inclusion-Exclusion Principle, the number of surjective functions $$f: A \to B$$ is $$3^7 - 3 \cdot 2^7 + 3 \cdot 1^7 - 0^7 = 2187 - 3 \cdot 128 + 3 \cdot 1 = 1806$$

$$|A| = 3$$, $$|B| = 7$$

How many relations are there from $$A$$ to $$B$$?

Same observations as above.

How many functions are there from $$A$$ to $$B$$?

Your answer is correct, but you were careless in your use of equal signs. Again, you cannot equate the functions from $$A$$ to $$B$$ with the number of functions from $$A$$ to $$B$$.

How many injective functions are there from $$A$$ to $$B$$?

How many surjective functions are there from $$A$$ to $$B$$?
You are correct that there are no surjective functions. However, it is because $$A$$ and $$B$$ are finite sets with $$|A| < |B|$$.