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

Question

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$.

Answer 1

$|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$?

Your answer is correct.

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|$.