Note: Content of multiple lectures
A relation $R$ from a set $A$ to another set $B$ is defined as a subset of $A \times B$. When $B = A$, $R$ is said to be a relation on $A$.
A relation $R$ on a set $A$ is said to be
Informally, most equivalence relations can be connected to elements having some property in common.
Given an equivalence relation $R$ on a set $A$, the equivalence class of an arbitrary $a \in A$ (denoted by $[a]$, $cl(a)$ or $\bar{a}$) is defined as the set of all elements related to $a$ in $A$, i.e.,
The set of all equivalence classes of $A$ with respect to $R$ form a partition of $A$. A partition of a set $A$ is a collection of disjoint subsets $A_{i}$ (called parts) of $A$ whose union is $A$, i.e., mutually exclusive and exhaustive.
Also, given a partition $P = {A_{1}, A_{2},…,A_{k}}$ of $A$, an equivalence relation can be defined on A as
Thus, defining an equivalence relation on a set is precisely the same as partitioning it, since the equivalence classes form a partition, and any partition gives rise to an equivalence relation.
Since defining an equivalence relation is equivalent to partitioning a set, the number of equivalence relations on a set is equal to the possible number of partitions of it. The number of ways to partition a set of cardinality $n$ is called $B_{n}$. These numbers are called Bell numbers.
The number of ways to partition a set of cardinality $n$ into $r$ (unlabelled) parts is called $S(n,r)$. These numbers are called Stirling numbers of the second kind.
In order to evaluate $S(n,r)$, we find a way to relate it to the previous Stirling numbers, i.e., we identify a recursion.
Consider a set $A_{n} = {x_{1},x_{2},…,x_{n}}$ that we wish to partition into $r$ parts.
We can say that $A_{n} = A_{n-1} \cup {x_{n}}$, where $A_{n-1} = {x_{1},x_{2},…,x_{n-1}}$ Here, we identify two cases with respect to $x_{n}$:
Case 1. $x_{n}$ is in a partition by itself. Now, $A_{n-1}$ has to be partitioned into only $(r-1)$ parts – hence there are $S(n-1,r-1)$ ways for this case to happen.
Case 2. $x_{n}$ shares a partition with some other $x_{i} \in A_{n-1}$. Now, $A_{n-1}$ will have to be partitioned into $r$ parts, and $x_{n}$ can be added to any of them – hence there are $rS(n-1,r)$ ways for this case to happen.
Both these cases are mutually exclusive and the possibilities can therefore be directly added, giving us the required recursion, i.e.
The initial value $S(1,1)$ is simply the number of ways to leave a singleton set alone; hence $S(1,1) = 1$. Further, a set cannot have more parts than its cardinality (since all parts must be nonempty); hence $n < r \Rightarrow S(n,r) = 0$.
Since $B_{n}$ is simply the number of ways to partition $A_{n}$ into any number of parts, we obtain it by summing up the Stirling numbers, i.e.,
Another recursion in terms of Bell numbers alone can be identified. Let $A_{i} = {x_{1}, x_{2},…,x_{i} }$ as above. Now consider $x_{n+1} \in A_{n+1}$. We will look at the number of elements in the part containing $x_{n+1}$ for an arbitrary partition of $A_{n+1}$.
Let $x_{n+1}$ be in a subset containing $k$ other elements for some partition. These $k$ elements have to be chosen from the $n$ elements of $A_{n}$, which can be done in $n \choose k$ ways. Now, the remaining $(n-k)$ elements need to be partitioned; this can be done in $B_{n-k}$ ways.
Since $k$ ranges from 0 to $n$, we obtain the following recursion:
Relations can be extended in order to have a certain property (reflexivity, symmetry or transitivity). This operation is called closure.
Let $P(R)$ indicate that $R$ has a certain property $P$. Then, the closure of $R$ with respect to $P$ is the set $R_{P}$, for which the following hold:
The reflexive closure of a relation over a set $A$ is obtained by taking its union with the set $\Delta = {(a,a)\, \vert \, a \in A}$i.e.,
The symmetric closure of a relation is obtained by taking its union with its inverse, i.e.,
The transitive closure of a relation has no such simple representation. It is denoted by $t(R)$.