# Different Number of Equivalence Relations

• MHB
• Yankel
In summary, there are a total of 15 different equivalence classes under the constraint that two elements must be in the same equivalence class.
Yankel
Hello all,

I have a few questions related to the different number of equivalence classes under some constraint. I don't know how to approach them, if you could guide me to it, maybe if I do a few I can do the others. Thank you.

Given the set A={1,2,3,4,5},

1) How many different equivalence relations are there on A, with two equivalence classes?

2) How many different equivalence relations are there on A, with no three equivalence classes (other number rather than 3)?

3) How many different equivalence relations are there on A, which includes the pair (1,3) ?

4) How many different equivalence relations are there on A, with three equivalence classes?

I do not know how to approach this kind of questions. Can you please assist and give me some guidance ?

Thank you in advance.

Yankel said:
1) How many different equivalence relations are there on A, with two equivalence classes?
As many as there are nonempty subsets of $A$ (the other class is the complement of the subset).

Yankel said:
4) How many different equivalence relations are there on A, with three equivalence classes?
The number 5 can be represented as a sum of three nonincreasing numbers (integer partitions of size 3) as follows.
\begin{align}
5&=3+1+1\\
5&=2+2+1
\end{align}
The first way corresponds to $\binom{5}{3}$ equivalence relations and the second one corresponds to $\binom{5}{2}\binom{3}{2}/2$ (please check).

Yankel said:
2) How many different equivalence relations are there on A, with no three equivalence classes (other number rather than 3)?
This can be done similarly by considering all integer partitions of 5. You can verify your answer because the total number of equivalence relations on a set with $n$ elements is given by the Bell numbers.

Yankel said:
3) How many different equivalence relations are there on A, which includes the pair (1,3) ?
So 1 and 3 must be in the same equivalence class. It may contain other elements; the total number of variants for this class is 8. If the class is just $\{1,3\}$, then we have to break $\{2,4,5\}$ into 1, 2 or 3 classes. If the class containing 1 and 3 has one extra element, then we have to break the two remaining elements into 1 or 2 classes: this makes 2 variants, and so on.

I am slightly confused. I'll try to clear things.

I figured out that the number of ways to construct 2 equivalence classes is 15. Two equivalence classes will happen when one has one element and the other 4, or 2 and 3, for example: {1} and {2,3,4,5} or {1,2} and {3,4,5}. 5C2 + 5C1 gives 10+5=15.

Now I am trying to do the same thing for 3 equivalence classes. This can happen either when I have, for example, {1}, {2} , {3,4,5}, or, {1,2}, {3,4}, {5}. I have tried figuring out how to calculate the number of possibilities for this happening. The final answer should be 15, I can't get it. There are 10 different triplets for the first case, and there are 6 doubles out of 4 in the second.

What I am saying is that I don't understand the calculation behind:

"The first way corresponds to (5C3) equivalence relations and the second one corresponds to (5C2)(3C2)/2 (please check)."

That you wrote.

One more thing that doesn't end up. In total there are 2^25 different equivalence relations. How come the total number of relations with n classes (n=1,...5) doesn't end up to this number ?

Last edited:
Yankel said:
I figured out that the number of ways to construct 2 equivalence classes is 15.
My response from post #2 should be corrected: the number of equivalence relations on $A$ with two classes equals half of the number of nontrivial subsets of $A$. A subset is nontrivial if it is nonempty and does not equal the whole $A$. We take half because pairs of classes $(C,A\setminus C)$ and $(A\setminus C,C)$ produce the same equivalence relation. This gives $(2^5-2)/2=15$, which agrees with your answer.

Yankel said:
What I am saying is that I don't understand the calculation behind:

"The first way corresponds to (5C3) equivalence relations and the second one corresponds to (5C2)(3C2)/2 (please check)."
By the first way I mean splitting $A$ into a subset of 3 elements and two subsets of 1 element. Once we select a three-element subset, the partition is fixed (the other two elements go to two different classes). Therefore, the integer partition $5=3+1+1$ corresponds to (5C3) equivalence relations.

The partition $5=2+2+1$ means that we have to select 2 elements out of 5 and then 2 out of the remaining 3. The remaining 1 element goes into a class by itself. But each such partition can be obtained in two ways: e.g., first choosing {1, 2}, then {3, 4} or by first choosing {3, 4} and then {1, 2}.

Yankel said:
One more thing that doesn't end up. In total there are 2^25 different equivalence relations.
I wrote that the total number of equivalence relations on a set with 5 elements is given by the Bell number $B_5=52$.

Thank you very much !

All clear now !

## 1. What is an equivalence relation?

An equivalence relation is a mathematical concept that defines a relationship between objects or elements in a set. It is a binary relation that must satisfy three properties: reflexivity, symmetry, and transitivity.

## 2. How many different equivalence relations can be defined for a given set?

The number of different equivalence relations that can be defined for a set depends on the cardinality (number of elements) of the set. For a set with n elements, there are 2^(n^2) possible equivalence relations that can be defined.

## 3. What is the difference between a partial equivalence relation and a total equivalence relation?

A partial equivalence relation is a binary relation that satisfies the properties of reflexivity, symmetry, and transitivity only for certain pairs of elements in a set. A total equivalence relation, on the other hand, satisfies these properties for all pairs of elements in a set.

## 4. Can a set have more than one equivalence relation?

Yes, a set can have multiple equivalence relations. In fact, there can be an infinite number of equivalence relations for a given set.

## 5. How are equivalence relations used in mathematics?

Equivalence relations are used in mathematics to partition a set into smaller subsets that share similar properties. They are also used to define equivalence classes, which are sets of elements that are equivalent to each other according to the defined relation.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
5K
• Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
4K