In my previous note here, I mentioned that a combination is an arrangement of things with no order. To further discuss combinations let us begin with the following example.

Example. How many different ways are there to permute three letters from $A=\{a,b,c,d\}$?

Solution. $P(4.3)=\frac{4!}{(4-3)!}=4!=24$.

Example. How many ways can we select three letters from $A=\{a,b,c,d\}$?

Solution. Note that with this question we are not interested in the order of arranging three letters but are only interested in selecting three letters. For each choice of a group of three letters, there are $3!$ permutations among the letters we won’t distinguish. Hence, the answer is $$\frac{P(4,3)}{3!}=\frac{4!}{3!(4-3)!}=4$$ Those four selections are \begin{array}{c}abc\\abd\\acd\\bcd\end{array}

The number of selecting $r$ elements from a set of $n$ elements, $0\leq r\leq n$ is denoted by $\begin{pmatrix}n\\r\end{pmatrix}$, $C(n,r)$ or ${}_nC_r$ and by using a similar argument to the one we made in the above example, we obtain \begin{equation}\label{eq:comb}\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}\end{equation} $\begin{pmatrix}n\\r\end{pmatrix}$ is called binomial coefficient for a good reason which will be mentioned later. The sage command for calculating $\begin{pmatrix}n\\r\end{pmatrix}$ is binomial(n,r).

Note that the formula \eqref{eq:comb} is symmetrical, meaning the number of selecting $r$ elements from $n$ elements or the number of selecting $n-r$ elements from $n$ elements are the same: $$\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}=\frac{n!}{(n-r)!r!}=\frac{n!}{(n-r)!(n-(n-r))!}=\begin{pmatrix}n\\n-r\end{pmatrix}$$ This can be easily understood without working through the algebra above: the number of selecting $r$ elements from $n$ elements is the same as the number of not selecting $n-r$ elements from $n$ elements.

Example. A committee of 3 is to be formed from a club of 20 people. How many different committees are possible?

Solution. $\begin{pmatrix}20\\3\end{pmatrix}=\frac{20!}{3!17!}=\frac{20\cdot 19\cdot 18}{3\cdot 2\cdot 1}=1140$.

Example. In the above example, if the treasurer must be on the committee, the answer changes to $\begin{pmatrix}19\\2\end{pmatrix}=171$. If we further require that a chairperson other than the treasurer be selected, then there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 2=342$ different committees. If the treasure can be a chairperson, there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 3=513$ different committees.

Example. Assume that a coin is tossed 5 times. In how many ways can three heads be obtained?

Solution. $\begin{pmatrix}5\\3\end{pmatrix}=\frac{5!}{2!3!}=10$.

Example. When a fair coin is tossed 5 times, how many ways can we possibly observe?

Solution. There are 6 different cases: when we observe 5 heads, 4 heads, 3 heads, 2 heads, 1 head, or 0 head (i.e. all 5 tails). Hence there are $$\begin{pmatrix}5\\5\end{pmatrix}+\begin{pmatrix}5\\4\end{pmatrix}+\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}5\\2\end{pmatrix}+\begin{pmatrix}5\\1\end{pmatrix}+\begin{pmatrix}5\\0\end{pmatrix}=1+5+10+10+5+1=32$$ Or more simply, for each coin toss, there are two possible outcomes (head or tail). So by the basic principle of counting there are $2^5=32$ possible outcomes from 5 coin tosses.

Example. From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refused to serve on the committee together?

Solution. There can be $\begin{pmatrix}5\\2\end{pmatrix}\begin{pmatrix}7\\3\end{pmatrix}=350$ different committees consisting of 2 women and 3 men. If two men refuse to serve on the committee together, we can either include only one of the two men in the committee or neither of the two men in the committee. Hence, in this case we have $\begin{pmatrix}2\\0\end{pmatrix}\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}2\\1\end{pmatrix}\begin{pmatrix}5\\2\end{pmatrix}=30$ different groups of men not containing both of the two feuding men. Since there are $\begin{pmatrix}5\\2\end{pmatrix}$ different ways to choose the two women, it follows that there are $30\begin{pmatrix}5\\2\end{pmatrix}=300$ possible committees.

Example. Consider a set of $n$ antennas of which $m$ are defective and $n-m$ are functional. Assume that the functional and the defective antennas are not distinguishable. How many linear orderings are there in which no two defectives are consecutive?

Solution. Imagine that the $n-m$ functional antennas are lined up. Since no two defective antennas are consecutive, the spaces between functional antennas must contains at most one defective antennas. There are $n-m+1$ possible positions for defective antennas. Hence, there are $\begin{pmatrix}n-m+1\\m\end{pmatrix}$ possible linear orderings.

Lemma. \begin{equation}\label{eq:combidentity}\begin{pmatrix}n\\r\end{pmatrix}=\begin{pmatrix}n-1\\r-1\end{pmatrix}+\begin{pmatrix}n-1\\r\end{pmatrix}\end{equation} where $1\leq r\leq n$.

Proof. Consider a group of $n$ objects and fix attention on a particular object. Let us call it object 1. There are then $\begin{pmatrix}n-1\\r-1\end{pmatrix}$ groups of size $r$ that contain object 1. There are also $\begin{pmatrix}n-1\\r\end{pmatrix}$ groups of size $r$ that do not contain object 1. Hence we obtain the identity in \eqref{eq:combidentity}.

Theorem. (The Binomial Theorem) \begin{equation}\label{eq:binomthm}(x+y)^n=\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}x^ry^{n-r}\end{equation}

The binomial theorem \eqref{eq:binomthm} can be proved by mathematical induction along with the identity in \eqref{eq:combidentity}. I will leave details of proof for readers.

Example. Expand $(x+y)^3$.

Solution. \begin{align*}(x+y)^3&=\begin{pmatrix}3\\0\end{pmatrix}x^0y^3+\begin{pmatrix}3\\1\end{pmatrix}x^1y^2+\begin{pmatrix}3\\2\end{pmatrix}x^2y^1+\begin{pmatrix}3\\3\end{pmatrix}x^3y^0\\&=y^3+3xy^2+3x^2y+x^3\end{align*}

The example below gives an alternative proof to Power Set Cardinality Theorem we discussed here.

Example. How many subsets are there of a set consisting of $n$ elements?

Solution. There are $\begin{pmatrix}n\\r\end{pmatrix}$ subsets of size $r$, so the answer is \begin{equation}\label{eq:binom}\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}=(1+1)^n=2^n\end{equation}

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

[3] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

There are two particular types of counting of interest in combinatorics. One is a permutation and the other is a combination. A permutation is ordering things without repeats. A combination is arranging things without order. In this note, we study permutations and we will discuss combinations in the following note. Let us begin with an example.

Example. How many different ways can we order the three different elements of $A=\{a,b,c\}$?

Solution. We have three choices for position 1. We have two choices for position 2. And we have 1 choice for position 3. Hence, by the basic principle of counting there are $3\cdot 2\cdot 1=6$ different ways of ordering the three letters. In fact, they are \begin{array}{cc}abc & acb\\bca & bac\\cab & cba\end{array}

The above example can be generalized to ordering elements from a set of $n$ elements. By a similar account, there are $n$ choices for position 1, there are $n-1$ choices for position 2, there are $n-2$ choices for position 3, …, there is one choice for position $n$. Hence, there are $$n!:=n(n-1)(n-2)\cdots3\cdot 2\cdot 1$$ different permutations on the set of $n$ elements. The symbol $n!$ is called $n$ factorial. We define $0!=1$ for an obvious reason which will be mentioned later. Note that $n!$ is also the number of bijective (one-to-one and onto) maps from $\{1,2,\cdots,n\}$ to itself. The sage command for calculating $n!$ is factorial(n).

Example. A class in probability theory consists of 6 men and 4 women. An exam is given and students are ranked according to their performance. Assume that no students received the same score.

1. How many different rankings are possible?
2. If the men are ranked just among themselves and the women among themselves, how many different rankings are possible?

Solution.

1. $10!=3,628,800$.
2. $6!4!=(720)(24)=17280$.

Example. Mark has 10 books that he is going to put on his bookshelf. Of these, 4 are math books, 3 are physics books, 2 are computer science books, and 1 is a language book. Mark wants to arrange his books so that all the books dealing with the same subject are placed together on the shelf. How many different arrangements are possible?

Solution. There are $4!3!2!1!$ different arrangements in the order of math, physics, computer science and language. There are then $4!$ different ways to arranging the 4 subjects. Therefore, the final answer is $4!4!3!2!1!=6912$.

Example. How many different letter arrangements can be formed using the letters PEPPER?

Solution. Suppose that the 3 P’s and 2 E’s are distinguished as $P_1E_1P_2P_3E_2R$. Then there would be $6!$ permutations. Now there are $3!$ permutations among the 3P’s and $2!$ permutations among the 2 E’s. Hence, there are all $3!2!$ permutations of the form PPEPER. Therefore, there are $\frac{6!}{3!2!}=60$ possible letter arrangements of the letters PEPPER.

By a similar account, we see that there are $$\frac{n!}{n_1!n_2!\cdots n_r!}$$ different permutations of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, …, $n_r$ are alike.

Example. A chess tournament has 10 competitors of which 4 are Russians, 3 are from the United States, 2 from Great Britain, and 1 from Brazil. If the tournament result lists just the nationalities of the prayers in the order in which they are placed, how may outcomes are possible?

Solution. $\frac{10!}{4!3!2!1!}=12,600$.

What if we want to arrange not all elements but only some elements from a set? Here is an example.

Example. A club of 25 members is holding an election for president, secretary and treasurer in that order. Assume that a person can hold only one position. How many different ways of choosing these officers are there?

Solution. $25\cdot 24\cdot 23$ by the basic principle of counting.

Definition. An ordered arrangement of $r$ elements selected from $n$ elements, $0\leq r\leq n$, where no two elements of the arrangement are the same, is called a permutation of $n$ objects taken $r$ at a time.The total number of such permutations is denoted by $P(n,r)$ or ${}_nP_r$.

By the basic principle of counting we find that \begin{equation}\label{eq:perm}P(n,r)=\prod_{j=0}^{r-1}(n-j)=n(n-1)(n-2)\cdots(n-r+1)\end{equation}

The expression in \eqref{eq:perm} can be written as \begin{equation}\label{eq:perm2}P(n,r)=\frac{n!}{(n-r)!}\end{equation} The sage command for calculating $P(n,r)$ is falling_factorial(n,r). Obviously, $P(n,n)=n!$. On the other hand, we have $P(n,n)=\frac{n!}{0!}$ from \eqref{eq:perm2}. Therefore, it is defined that $0!=1$.

Using the formula \eqref{eq:perm2} the answer to the question in the above example is simply $$P(25,3)=\frac{25!}{(5-3)!}=25\cdot 24\cdot 23$$

Example. Consider the digits 1, 2, 3, 4, 5.

1. How many three-digit numbers can be formed if no repetition of digits can occur?
2. How many three-digit numbers can be formed if repetition is allowed?
3. How many three-digit numbers can be formed if only non-consecutive repetition of digits are allowed?

Solution.

1. $P(5,3)=\frac{5!}{(5-3)!}=5\cdot 4\cdot 3=60$.
2. $5\cdot 5\cdot 5=125$.
3. $5\cdot 4\cdot 4=80$.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

What is combinatorics? It can be simply characterized as:

Combinatorics = The Art of counting

Combinatorics begins with

The Basic Principle of Counting: Suppose that two operations are to be performed. If operation 1 results in any one of $m$ possible outcomes and if for each outcome of operation 1 there are $n$ possible outcomes of operation 2, then together there are $mn$ possible outcomes of the two operations.

The Basic Principle of Counting is also called the Rule of Products. The principle assumes that the choice for operation 2 does not depend on the choice of operation 1.

Example. A lunch bar serves 5 different sandwiches and 3 different drinks. How many different lunches can a person order?

Solution. For each choice of a sandwich, there are three different choices of a drink. Hence there are $5\cdot 3=15$ possible orders.

Example. Let $A$ and $B$ be finite sets. Prove that $|A\times B|=|A|\cdot|B|$ where $|A|$ denotes the cardinality (i.e. the number of elements) of the set $A$.

Proof. Let $|A|=m$ and $|B|=n$. For each choice of elements in $A$ there are $n$ possible choices for the elements in $B$ to pair with. Since there are $m$ possible choices for the elements in $A$, the total number of all possible ordered pairs is $mn$, i.e. $|A\times B|=mn=|A|\cdot|B|$.

Example. A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?

Solution. There are $10\times 3=30$ possible choices.

If more than two operations are to be performed, the basic principle can be generalized as follows.

The Generalized Basic Principle of Counting

If $r$ operations are to be performed in such a way that operation 1 results in $n_1$ possible outcomes, operation 2 results in $n_2$ possible outcomes, …, operation $r$ results in $n_r$ possible outcomes, then there is a total of $n_1\cdot n_2\cdots n_r$ possible outcomes of the $r$ operations.

Example. A person is to complete a true-false questionnaire. How many different ways are there to answer the questionnaire?

Solution. $\stackrel{10\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^{10}=1024$.

Example. A questionnaire contains 4 questions that have 2 possible answers and three questions with 5 possible answers. How many different answers are possible?

Solution. $2\cdot 2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 5=2^4\cdot 5^3=2000$ different ways to answer the questionnaire.

Example. How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers?

Solution. $26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10\cdot 10=175,760,000$.

Example. In the above example, how many license plates would be possible if repetition among letters or numbers were prohibited?

Solution. $26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7=78,624,000$.

Theorem. (Power Set Cardinality Theorem) If $A$ is a finite set, then $|\wp(A)|=2^{|A|}$.

Proof. The proof boils down to counting how many different ways there are to determine subsets of $A$. Let $B$ be a subset of $A$. For each $x\in A$, there are two possibilities: either $x\in B$ or $x\not\in B$. Since $A$ has $n$ elements, there are $\stackrel{n\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^n$ different ways to determine subsets of $A$.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

Recall the equivalence relation $\equiv\ \mathrm{mod}\ n$ on $\mathbb{Z}$ (we discussed it here) $$p\equiv q\ \mathrm{mod}\ n\ \Longleftrightarrow\ n|(p-q)$$ Let us denote by $p\ \mathrm{mod}\ n$ the remainder when $p$ is divided by $n$. The definition of the equivalence relation implies that $$p\equiv q\ \mathrm{mod}\ n\ \Longleftrightarrow\ p\ \mathrm{mod}\ n=q\ \mathrm{mod}\ n$$ (The proof is left as an exercise.) When an integer $p$ is divided by $n$, the remainder $p\ \mathrm{mod}\ n$ is an integer satisfying the inequality $0\leq p\ \mathrm{mod}\ n\leq n-1$. Therefore, the equivalence class $[p]$ is one of $[0],[1],\cdots,[n-1]$, i.e. the quotient set $\mathbb{Z}_n=\mathbb{Z}/\equiv\mathrm{mod}\ n$ is $$\mathbb{Z}_n=\{[0],[1],[2],\cdots,[n-1]\}$$ Also recall that in here we defined $+$ and $\cdot$ on $\mathbb{Z}_n$ by \begin{align*}[a]+[b]&=[a+b]\\ [a]\cdot[b]&=[a\cdot b]\end{align*} These operations are well-defined due to the following properties (see Problem Set 12 #7): if $a\equiv b\ \mathrm{mod}\ n$ and $c\equiv d\ \mathrm{mod}\ n$, then \begin{equation}\begin{aligned}a+c&\equiv b+d\ \mathrm{mod}\ n\\a\cdot c&\equiv b\cdot d\ \mathrm{mod}\ n\end{aligned}\label{eq:congrel}\end{equation} The following is another useful property: if $a\equiv b\ \mathrm{mod}\ n$ and $c$ is an integer then \begin{equation}\label{eq:congrel2}c\cdot a\equiv c\cdot b\ \mathrm{mod}\ n\end{equation} Its proof is straightforward so it is left as an exercise. The properties \eqref{eq:congrel} and \eqref{eq:congrel2} can be used to calculate the remainder when a significantly large integer is divided by an integer $n$.

Example. What is $N\ \mathrm{mod}\ 21$ where $$N=113\times (167+484)+192\times 145?$$

Solution. $N=113\times (167+484)+192\times 145=101403$, which is not really a large number. One can simply divide 101403 by 21 and find the remainder 15. Let us now try a different way. Note that $113\equiv 8\ \mathrm{mod}\ 21$, $167\equiv 20\ \mathrm{mod}\ 21$, $484\equiv\ 1\mathrm{mod}\ 21$, $192\equiv 3\ \mathrm{mod}\ 21$, and $145\equiv 19\ \mathrm{mod}\ 21$. Hence by using \eqref{eq:congrel} we have $$N\equiv 8\times (20+1)+3\times 19=225\ \mathrm{mod}\ 21$$ 225 is a much smaller number and one can easily divide it by 21 and obtain the remainder 15. On the other hand, $21\equiv 0\ \mathrm{mod}\ 21$ and $19\equiv -2\ \mathrm{mod}\ 21$ since $19=21-2$. So by using the properties \eqref{eq:congrel} and \eqref{eq:congrel2}, we have $$N\equiv 8\times 0+3\times (-2)=-6\equiv 15\ \mathrm{mod}\ 21$$ since $-6=21(-1)+15$.

Example. What is $10^3\ \mathrm{mod}\ 7$?

Solution. $1000$ is not a large number and one can easily divide it by 7 to obtain $1000=142\cdot 7+6$ and so $10^3\equiv 6\ \mathrm{mod}\ 7$. There is a smarter way to do this though. Note that $10=7\cdot 1+3$, so $10\equiv 3\ \mathrm{mod}\ 7$. Using \eqref{eq:congrel}, we obtain $$10^3\equiv 3\cdot 3\cdot 3=27\equiv 6\ \mathrm{mod}\ 7$$

The remainder when a large number is divided by an integer sometimes can be calculated using repeated squaring as seen in the following example.

Example. Find $3^{25}\ \mathrm{mod}\ 7$.

Solution. \begin{align*}3^{25}&=(3^{12})^2\cdot 3\\&=((3^6)^2)^2\cdot 3\\&=(((3^3)^2)^2)^2\cdot 3\\&=(((3^2\cdot 3)^2)^2)^2\cdot 3\\&\equiv (((2\cdot 3)^2)^2)^2\cdot 3\\&=((36)^2)^2\cdot 3\\&\equiv 3\ \mathrm{mod}\ 7\end{align*} where we use the fact $36\equiv 1\ \mathrm{mod}\ 7$.

Definition. $[y]$ is said to be a multiplicative inverse of $[x]$ in $\mathbb{Z}_n$ if $x\cdot y\equiv 1\ \mathrm{mod}\ n$.

It is not necessarily that every non-zero element of $\mathbb{Z}_n$ has a multiplicative inverse. For example, let us consider the multiplication table of $\mathbb{Z}_4$. Here, we denoted $[a]$ by simply $a$. $$\begin{array}{|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3\\\hline 0 & 0 & 0 & 0 &0\\\hline1 & 0 & 1 & 2 & 3\\\hline2 & 0 & 2 & 1 & 2\\\hline3 & 0 &3 & 0 &3\\\hline\end{array}$$ As clearly seen in the table, 3 does not have a multiplicative inverse. On the other hand, in $\mathbb{Z}_5$ all non-zero elements have multiplicative inverses as shown in the following table. $$\begin{array}{|c|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3 & 4\\\hline 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 0 & 1 & 2 & 3 & 4\\\hline 2 & 0 & 2 & 4 & 1 & 3\\\hline 3 & 0 &3 & 1 & 4 & 2\\\hline 4 & 0 & 4 & 3 & 2 & 1\\\hline\end{array}$$ Notice that 5 is a prime number. In fact, we have the following cool theorem.

Theorem. If $p$ is prime, then every non-zero element of $\mathbb{Z}_p$ has a multiplicative inverse. Therefore, $\mathbb{Z}_p$ is a finite field.

Proof. Let $a$ be an integer such that $1\leq a\leq p-1$. Then clearly $$\mathbb{Z}_p[a]=\{[0],[1\cdot a],\cdots,[(p-1)\cdot a]\}\subseteq\mathbb{Z}_p$$ If $[0],[1\cdot a],\cdots,[(p-1)\cdot a]$ are mutually distinct, $\mathbb{Z}_p[a]=\mathbb{Z}$ and therefore, $[i]\cdot[a]=[i\cdot a]=1$ for some $1\leq i\leq p-1$. That is, $[a]$ has a multiplicative inverse. So the proof of this theorem boils down to showing that $\mathbb{Z}_p[a]$ has $p$ distinct elements for any $1\leq a\leq p-1$. This is a consequence of the lemma below.

Lemma. If $p$ is a prime number such that $p\not| a$ and $i\cdot a\equiv j\cdot a\ \mathrm{mod}\ p$ then $i\equiv j\ \mathrm{mod}\ p$.

Proof. If $i\cdot a\equiv j\cdot a\ \mathrm{mod}\ p$ then $p|a(i-j)$. Since $p\not| a$, $p|i-j$ i.e. $i\equiv j\ \mathrm{mod}\ p$.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

[2] A Short Course in Discrete Mathematics, Edward A. Bender and S. Gil Williamson, Dover Publications, 2012

Definition. Let $A$ be a nonempty set. Then $R\subseteq A\times A$ is called a binary relation on $A$. A binary relation $R$ on $A$ is said to be an equivalence relation if

1. $R$ is reflexive: $\forall x\in A$, $(x,x)\in R$
2. $R$ is symmetric: $(x,y)\in R\Longrightarrow (y,x)\in R$
3. $R$ is transitive: $(x,y)\in R\ \mathrm{and}\ (y,z)\in R\Longrightarrow (x,z)\in R$

Definition. Let $R$ be an equivalence relation on a set $A$. For each $x\in A$, let $$[x]=\{y\in A: (y,x)\in R\}$$ Then $[x]$ is called the ($R$-)equivalence class of $x\in A$.

Theorem 1. Let $R$ be an equivalence relation on a set $A$. Then

1. $\forall x,y\in A$, $[x]\cap [y]=\emptyset$ or $[x]=[y]$.
2. $A=\bigcup_{x\in A}[x]$.

Proof.

1. Let $x,y\in A$. If $[x]\cap [y]=\emptyset$, then we are done. Now suppose that $[x]\cap [y]\ne\emptyset$. Then $\exists z\in[x]\cap [y]$ so that \begin{align*}(z,x)\in R\ \mathrm{and}\ (z,y)\in R&\Longrightarrow (x,z)\in R\ \mathrm{and}\ (z,y)\in R\\&\Longrightarrow (x,y)\in R\end{align*} This implies that $[x]=[y]$.
2. Left as an exercise.

Definition. Let $A$ be a set. By a partition of $A$ we mean a family $\{A_i\}_{i\in I}$of nonempty subsets of $A$ such that

1. $\forall i,j\in I$, $A_i\cap A_j=\emptyset$ or $A_i=A_j$.
2. $A=\bigcup_{i\in I}A_i$

Theorem 1 says that given an equivalence relation $R$ on $A$, the $R$-equivalence classes form a partition of $A$. Conversely, given a partition $\{A_i\}_{i\in I}$, one can define an equivalence relation $R$ whose equivalence classes coincide with the $A_i$´s.

Theorem 2. Let $\{A_i\}_{i\in I}$ be a partition of a set $A$. Define a relation $R$ on $A$ as follows: $$\forall x,y\in A,\ (x,y)\in R\Longleftrightarrow x,y\in A_i\ \mbox{for some}\ i\in I$$ Then $R$ is an equivalence relation on $A$ and the $R$-equivalence classes coincide with the $A_i$´s.

Proof. Left as an exercise.

Given an equivalence relation $R$ on a set $A$, the set of all equivalence classes is called the quotient set of $A$ modulo (or mod in short) $R$ and is denoted by $A/R$ i.e. $$A/R=\{[x]: x\in A\}$$

There is a map $\gamma: A\longrightarrow A/R$ defined by $$\forall x\in A,\ \gamma(x)=[x]$$ $\gamma$ is called the canonical map from $A$ to $A/R$.

Example 1. (The Vector Space $\mathbb{R}^3$) Let $V$ be the set of all directed arrows in 3-space $\mathbb{R}^3$. Define a relation $\equiv$ on $V$ as follows: $$\forall \overrightarrow{AB},\overrightarrow{CD}\in V,\ \overrightarrow{AB}\equiv\overrightarrow{CD}\Longleftrightarrow\ \overrightarrow{AB}\ \mathrm{and}\ \overrightarrow{CD}\ \mbox{have the same direction and magnitude}$$ Then clearly $\equiv$ is an equivalence relation on $V$. Denote by $\mathcal{V}$ the quotient set $V/\equiv$ and each equivalence class $[\overrightarrow{AB}]\in\mathcal{V}$ is called a vector. Each directed arrow $\overrightarrow{AB}$ whose starting point is $A$ and terminal point is $B$ is $\equiv$-related to a directed arrow $\vec{a}$ whose starting point is the origin $O=(0,0,0)$ and terminal point is $B-A$. $\vec{a}$ can be identified with its terminal point $B-A$ which is an ordered triple $(a_1,a_2,a_3)$. Hence from here on, without loss of generality, we may assume that each equivalence class is represented by such a vector. Define the vector addition $+:\mathcal{V}\times\mathcal{V}\longrightarrow\mathcal{V}$ by $$\forall [\vec{a}],[\vec{b}]\in\mathcal{V},\ [\vec{a}]+[\vec{b}]:=[\vec{a}+\vec{b}]$$ Here, $$\vec{a}+\vec{b}=(a_1,a_2,a_3)+(b_1,b_2,b_3)=(a_1+b_1,a_2+b_2,a_3+b_3)$$ Also define the scalar multiplication $\cdot :\mathbb{R}\times\mathcal{V}\longrightarrow\mathcal{V}$ by $$\forall c\in\mathbb{R},\ \forall [\vec{a}]\in\mathbb{V},\ c[\vec{a}]:=[c\vec{a}]$$ Here, $$c\vec{a}=(ca_1,ca_2,ca_3)$$ Let $[\vec{a}]=[\vec{a}’]$ and $[\vec{b}]=[\vec{b}’]$. Then $\vec{a}=\vec{a}’$ and $\vec{b}=\vec{b}’$ i.e. $a_i=a’_i$ and $b_i=b’_i$, $i=1,2,3$. Thus $$\vec{a}+\vec{b}=\vec{a}’+\vec{b}’\Longrightarrow [\vec{a}]+[\vec{b}]=[\vec{a}+\vec{b}]=[\vec{a}’+\vec{b}’]=[\vec{a}’]+[\vec{b}’]$$ Hence, the vector addition is well-defined. It can be shown similarly that the scalar multiplication is also well-defined. We will see in the next example that there is a bijective from $\mathcal{V}$ to $\mathbb{R}^3$.

Example 2. (The Kernel of a Function) Let $f: A\longrightarrow B$ be a function. The kernel of $f$, $\ker f$ is defined by $$\ker f=\{(x,y)\in A\times A: f(x)=f(y)\}$$ It is easy to see that $\ker f$ is an equivalence relation on $A$. It turns out that the quotient set $A/\ker f$ coincides with the partition of $A$ by the pre-images $f^{-1}(z)$, $\forall z\in A$. (See Problem Set 12 #5 (b).) Now we suppose that $f: A\longrightarrow B$ is surjective (onto). Define a map $\psi: A/\ker f\longrightarrow B$ by $$\forall [x]\in A/R,\ \psi([x])=f(x)$$ Then $\psi$ is a bijective and $\gamma=\psi\circ f$, where $\gamma: A\longrightarrow A/\ker f$ is the canonical map. (Its proof is left as an exercise.)

In Example 1, we have seen that given a directed arrow $\overrightarrow{AB}$ there is a $\equiv$-related directed arrow whose starting point the origin $O$ and terminal point $B-A$ and that such a directed arrow can be identified with its terminal point $\vec{a}:=B-A=(a_1,a_2,a_3)\in\mathbb{R}^3$. This defines a surjective map $f: V\longrightarrow\mathbb{R}^3$ and $\ker f=\equiv$. Therefore, we see that there is a bijective $\psi$ from $V/\ker f=V/\equiv$ to $\mathbb{R}^3$ defined by $$\forall [\vec{a}]\in V/\equiv,\ \psi([\vec{a}])=(a_1,a_2,a_3)$$ Furthermore, this bijective is a vector space homomorphism i.e. it preserves the vector addition and the scalar multiplication: \begin{align*}\psi([\vec{a}]+[\vec{b}])&=\psi([\vec{a}])+\psi([\vec{b}])\\\psi(c[\vec{a}])&=c\psi([\vec{a}])\end{align*} Therefore $V/\equiv$ is isomorphic to $\mathbb{R}^3$ as a vector space.

Example 3. (The Construction of Rational Numbers From Integers) Let $\mathbb{Z}$ be the set of all integers. Define a relation $\sim$ on $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ by $$\forall (a,b),(c,d)\in \mathbb{Z}\times(\mathbb{Z}\setminus\{0\}),\ (a,b)\sim (c,d)\Longleftrightarrow ad=bc$$ Then $\sim$ is an equivalence relation. (Its proof is left as an exercise.) The equivalence class of $(a,b)$ is denoted by $\frac{a}{b}$. For example, $(1,2)\sim (2,4)$ thus $\frac{1}{2}=\frac{2}{4}$. We see that the quotient set $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})/\sim$ can be identified with $\mathbb{Q}$, the set of all rational numbers.

Example 4. (Residue Classes Modulo $n$) Let $\mathbb{Z}$ be the set of all integers. Define a relation $\equiv\ \mathrm{mod}\ n$ on $\mathbb{Z}$ by $$\forall p,q\in\mathbb{Z},\ p\equiv q\ \mathrm{mod}\ n\Longleftrightarrow n|(p-q)$$ Then $\equiv\ \mathrm{mod}\ n$ is an equivalence relation. (Its proof is left as an exercise.) An integer $m$ can be written as $m=nk+r$ where $k$ is the quotient and $0\leq r<n$ is the remainder when $m$ is divided by $n$. Thus $m\equiv\ \mathrm{mod}\ n r$. This means that there are exactly $n-1$ equivalence classes $$[0],[1],\cdots,[n-1]$$ These equivalence classes are called the residue classes modulo $n$. The quotient set $\mathbb{Z}/\equiv\ \mathrm{mod}\ n$ is usually denoted by $\mathbb{Z}_n$. We can define addition and multiplication on $\mathbb{Z}_n$ as follows: $\forall [a],[b]\in\mathbb{Z}_n$, \begin{align*}[a]+[b]&=[a+b]\\ [a]\cdot [b]&=[ab]\end{align*} These operations are well-defined because the equivalence relation $\equiv\ \mathrm{mod}\ n$ preserves the operations, namely if $a\equiv b\ \mathrm{mod}\ n$ and $c\equiv d \mathrm{mod}\ n$ then \begin{align*}a+c&\equiv b+d\ \mathrm{mod}\ n\\ ac&\equiv bd\ \mathrm{mod}\ n\end{align*} An equivalence which preserves operations are called a congruence relation. Congruence relations play a crucial role in constructing quotient algebras. For more details about congruence relations, see for example the reference [3]. Note that the equivalence relations in Examples 1 and 3 are also congruence relations. $(\mathbb{Z}_n,+)$ is an abelian group and $(\mathbb{Z}_n,+,\cdot)$ is a commutative ring with unity. $(\mathbb{Z},+,\cdot)$ is a field if $n$ is a prime.

Example. (Digraphs) Let $G=(V,A)$ be a digraph. Let $\sim$ be mutual reachability relation on $V$, i.e. $\forall x,y\in V$, $x\sim y$ if and only if $x$ and $y$ are mutually reachable. It can be easily seen that mutual reachability relation is an equivalence relation. The equivalence classes are called the strongly connected components or simply strong components of the digraph $G$ and they are subgraphs of $G$.

Theorem. Let $G=(V,A)$ be a digraph and let $T$ be the partition of $V$ into the strong components of $G$. Construct a new digraph $G’=(T,A’)$, where $\forall X,Y\in T$, $X\to Y\in A’$ if and only if $X\ne Y$ and $x\to y\in A$ for some $x\in X$ and $y\in Y$. Then $G’$ is a DAG.

Proof. Suppose that there is a cycle in $G’$, $x_0\to x_1\to\cdots x_k\to x_0$ for some $x_0,\cdots,x_k$ belonging to different strong components of $G$. But all theses vertices are mutually reachable in $G$ so this is a contradiction. Therefore $G’$ is acyclic.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

[2] Set Theory, Charles C. Pinter, Addison Wesley Publishing Company, 1971

[3] A Course in Universal Algebra, Stanley N. Burris and H. P. Sankappanavar, Graduate Texts in Mathematics, Springer-Verlag, 1981. The book is available online for free at the first named author’s web page here.