Problem 2

Question

Let $A, B$ be finite sets with $\operatorname{card}(A)=n$ and $\operatorname{card}(B)=m .$ Prove that \- The number of functions from $A$ to $B$ is $m^{n}$. \- If $n \leq m$, the number of injective functions from $A$ to $B$ is $m(m-1)(m-2) \cdots(m-n+1) .$ If $n>m$ there are no injective functions from $A$ to $B$.

Step-by-Step Solution

Verified

Answer

Total functions: $m^n$. Injective functions: $m(m-1) \cdots (m-n+1)$ for $n \leq m$, zero for $n > m$.

1Step 1: Understanding the Problem

We have two finite sets, $A$ and $B$, with $\operatorname{card}(A) = n$ and $\operatorname{card}(B) = m$. We need to calculate the total number of functions from $A$ to $B$, and specifically calculate the number of injective functions from $A$ to $B$, considering two scenarios: $n \leq m$ and $n > m$.

2Step 2: Calculating Total Number of Functions from A to B

Every element of set $A$, which has $n$ elements, can be mapped to any of the $m$ elements in set $B$. So, for each element in $A$, there are $m$ choices. Therefore, the total number of functions from $A$ to $B$ is $m^n$.

3Step 3: Understanding Injective Functions

An injective function (or one-to-one function) means that different elements in $A$ are mapped to different elements in $B$. This requires that the number of elements in $B$ must be at least as large as in $A$ (i.e., $m \geq n$).

4Step 4: Counting Injective Functions for n \leq m

For $n \leq m$, calculate injective functions as follows: map the first element of $A$ to any of the $m$ elements in $B$. For the second element of $A$, map it to any of the remaining $m-1$ elements in $B$, and so on. Finally, map the $n$-th element of $A$ to one of the remaining $m-n+1$ elements in $B$. The total number of injective functions is given by $m(m-1)(m-2) \cdots (m-n+1)$.

5Step 5: No Injective Functions for n > m

If $n > m$, it is impossible to have injective functions since there are not enough elements in $B$ to provide unique mappings for all elements in $A$. Thus, there are zero injective functions in this case.

Key Concepts

Finite SetsInjective FunctionsCardinalityMapping

Finite Sets

Finite sets are simply collections of distinct elements where the number of elements is countable and ends. In simpler terms, you can list all elements without going on forever. For example, the set {1, 2, 3, 4, 5} is finite because it has 5 elements which we can easily count.

When dealing with problems involving finite sets, it's essential to understand the size or the number of elements. We often use the term "cardinality" to refer to this number, denoted as $ \operatorname{card}(S) $, where $ S $ is the set.

Knowing the cardinality helps in defining possible relations or mappings between two sets. This includes understanding the possible number of functions that can exist from set $ A $ to set $ B $, as well as defining injective functions, which will be discussed in the following sections.

Injective Functions

Injective functions, also known as one-to-one functions, are functions where each element of the set $ A $ is mapped to a unique element of set $ B $. In simpler terms, no two different elements in set $ A $ share the same image in set $ B $.

To determine if a function is injective, check that:

Each element of the domain (set $ A $) maps to a unique element of the codomain (set $ B $).
Cardinality of $ B $ must be greater than or equal to the cardinality of $ A $ ($ m \geq n $).

In mathematical problems like ours, if you have two sets $ A $ and $ B $, and you want the mappings to be injective, the set $ B $ needs enough elements to have a unique pair for each from $ A $. This is why the conditions $ n \leq m $ (justify why not \

Cardinality

Cardinality is a term that refers to the number of elements in a set. In mathematics, we often denote the cardinality of a set $ A $ with $ \operatorname{card}(A) $.

Understanding cardinality is crucial because it defines the potential ways elements of one set can relate to those in another. For example, if set $ A $ has $ n $ elements ($ \operatorname{card}(A) = n$) and set $ B $ has $ m $ elements ($ \operatorname{card}(B) = m$), then we can begin to explore how functions can be defined from $ A $ to $ B $, including understanding injective, surjective, and bijective functions.

In our specific problem, the cardinality directly dictates the number of possible functions and injective mappings between sets $ A $ and $ B $. When learning about functions between finite sets, keep in mind the role of cardinality in these relationships to grasp how complex mappings can become.

Mapping

Mapping is the process of associating each element of one set with an element of another set. In mathematics, functions are mappings from one set (known as the domain) to another set (known as the codomain).

When mapping from finite set $ A $ to finite set $ B $, there are different types of functions one can consider:

General Mappings: Every element from $ A $ has a corresponding element in $ B $.
Injective (One-to-One): Each element of $ A $ is mapped to a unique element in $ B $.
Surjective (Onto): Every element in $ B $ is the image of at least one element from $ A $.
Bijective (One-to-One Correspondence): The mapping is both injective and surjective; every element in $ A $ is uniquely paired with an element in $ B $, and each element of $ B $ is mapped from some element in $ A $.

Understanding the type of mappings possible is essential for solving problems related to functions and helps in visualizing how different sets are interrelated.

Problem 2

Other exercises in this chapter

Problem 2

Let $t \geq 0 .$ Prove that $|x| \geq t \Longleftrightarrow(x \geq t)$ or $\quad(x \leq-t) .$

View solution

Problem 2

Given that 1002004008016032 has a prime factor $\boldsymbol{p}>250000$, find it.

View solution

Problem 2

Prove the following properties of the empty set: $$ A \cap \emptyset=\varnothing, \quad A \cup \varnothing=A $$

View solution

Problem 3

Let $\boldsymbol{n} \geq 2$ be an integer. Prove that $$ \max _{0 \leq x_{1} \leq x_{2} \leq \cdots \leq x_{n} \leq 1}\left(\sum_{1 \leq i

View solution