Number of Possible Equivalence Relations on a Finite Set

Table of Contents#

1. What are Equivalence Relations?
2. Partitions and Equivalence Relations
3. Calculating the Number of Partitions (Bell Numbers)
4. Examples of Calculating the Number of Equivalence Relations
5. Common Practices and Best Practices
6. Conclusion
7. References

What are Equivalence Relations?#

Let (A) be a non - empty set. A binary relation (R) on (A), denoted as (R\subseteq A\times A), is called an equivalence relation if it satisfies the following three properties:

Reflexivity#

For every (a\in A), ((a, a)\in R). In other words, every element is related to itself. For example, if (A={1, 2, 3}), a reflexive relation (R) must contain ((1,1)), ((2,2)), and ((3,3)).

Symmetry#

If ((a, b)\in R), then ((b, a)\in R) for all (a,b\in A). That is, if (a) is related to (b), then (b) is related to (a). For instance, if ((1, 2)\in R), then ((2, 1)) must also be in (R).

Transitivity#

If ((a, b)\in R) and ((b, c)\in R), then ((a, c)\in R) for all (a,b,c\in A). For example, if ((1, 2)\in R) and ((2, 3)\in R), then ((1, 3)) must be in (R).

Partitions and Equivalence Relations#

A partition of a set (A) is a collection (\Pi={S_1,S_2,\cdots,S_k}) of non - empty subsets of (A) such that:

1. (S_i\cap S_j=\varnothing) for (i\neq j) (the subsets are pairwise disjoint).
2. (\bigcup_{i = 1}^{k}S_i=A) (the union of all subsets is the set (A)).

There is a one - to - one correspondence between the equivalence relations on a set (A) and the partitions of the set (A). Given an equivalence relation (R) on (A), the equivalence classes ([a]={b\in A:(a, b)\in R}) form a partition of (A). Conversely, given a partition (\Pi) of (A), we can define an equivalence relation (R) such that ((a, b)\in R) if and only if (a) and (b) belong to the same subset in the partition.

Calculating the Number of Partitions (Bell Numbers)#

The number of partitions of a set with (n) elements is given by the (n)th Bell number, denoted as (B_n). Bell numbers can be calculated using several methods:

Recursive Formula#

The Bell numbers satisfy the following recurrence relation: [B_{n + 1}=\sum_{k = 0}^{n}\binom{n}{k}B_{k}] where (\binom{n}{k}=\frac{n!}{k!(n - k)!}) is the binomial coefficient. The base case is (B_0 = 1).

Bell Triangle#

We can also calculate Bell numbers using the Bell triangle. The Bell triangle is constructed as follows:

• The first element of the first row is (B_0 = 1).
• The first element of each subsequent row is the last element of the previous row.
• Each other element in a row is the sum of the element to its left and the element above the element to its left.

For example, the first few rows of the Bell triangle are:

1
1  2
2  3  5
5  7  10 15

The first element of each row gives the corresponding Bell number ((B_0 = 1), (B_1 = 1), (B_2 = 2), (B_3 = 5), (B_4 = 15)).

Examples of Calculating the Number of Equivalence Relations#

Example 1: Set with (n = 1) element#

Let (A={a}). There is only one possible partition of (A), which is ({{a}}). So, the number of equivalence relations on (A) is (B_1=1).

Example 2: Set with (n = 2) elements#

Let (A = {a,b}). The possible partitions of (A) are:

• ({{a,b}}): All elements are in the same subset.
• ({{a},{b}}): Each element is in its own subset.

So, the number of equivalence relations on (A) is (B_2 = 2).

Example 3: Set with (n=3) elements#

Let (A={a,b,c}). The possible partitions of (A) are:

• ({{a,b,c}}) (one subset with all elements).
• ({{a},{b,c}}), ({{b},{a,c}}), ({{c},{a,b}}) (one single - element subset and one two - element subset).
• ({{a},{b},{c}}) (three single - element subsets).

The number of equivalence relations on (A) is (B_3=5).

Common Practices and Best Practices#

• Use Recursion with Memoization: When calculating Bell numbers using the recursive formula, it is a good practice to use memoization to avoid redundant calculations. This can significantly reduce the time complexity.
• Understand the Concept of Partitions: Since the number of equivalence relations is equal to the number of partitions, having a clear understanding of partitions and how to construct them is crucial.
• Visualize with Small Examples: For small sets, it is often helpful to visualize the partitions and equivalence relations. This can aid in understanding the concepts and validating the calculations.

Conclusion#

In conclusion, the number of possible equivalence relations on a finite set with (n) elements is given by the (n)th Bell number. The relationship between equivalence relations and partitions provides a powerful tool for solving problems related to counting and classification. By understanding the properties of equivalence relations, partitions, and the methods for calculating Bell numbers, we can handle various combinatorial problems with ease.

References#

• "Discrete Mathematics and Its Applications" by Kenneth H. Rosen.
• Wikipedia pages on "Equivalence relation" and "Bell number".