# Equivalence relations

• Oct 16th 2011, 07:34 AM
mathproblems
Equivalence relations
How many equivalence relations are there on the set {1,2,3}?

I got just [1] = {1,2,3}

because (1,1) (2,2) (3,3) (1,2) (2,1) (1,3) (3,1) (2,3) (3,2).
[1] = {1,2.3}
[2] = {1,3}
[3] = {3,2}

is this correct?
Thank you.
• Oct 16th 2011, 07:47 AM
emakarov
Re: Equivalence relations
I am not sure what your answer is. The question "how many" requires a number as an answer. You write, "I got just [1] = {1,2,3}." Usually, [x] denotes the equivalence class of x, i.e., the set of elements that are equivalent to x. So, [x] is a set, not a number. It could be that you mean "I got just one" equivalence relation, but then what is it?

Also, if R = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}, then [1] is indeed {1, 2, 3}, but [2] = [3] = {1, 2, 3} as well with respect to R.

Each equivalence relation generates its own partition of {1, 2, 3}, so one way to find the answer is to count the number of partitions.
• Oct 16th 2011, 07:58 AM
mathproblems
Re: Equivalence relations
I am not sure if we need to add [2] and [3] since they are both have {1,2,3} the same as [1].
• Oct 16th 2011, 08:08 AM
emakarov
Re: Equivalence relations
In any case, so far you have found just one equivalence relation, which is the total relation on {1, 2, 3}. There are several others. Again, my advice is to enumerate all possible partitions.
• Oct 16th 2011, 08:34 AM
Plato
Re: Equivalence relations
Quote:

Originally Posted by mathproblems
How many equivalence relations are there on the set {1,2,3}?

There is a one-to-one correspondence between the number of partitions of a set and the number of equivalence relations on that set.
That number is known as the Bell Number of the set.
Bell numbers are sums of Stirling numbers of the second kind.
For example on a set of ten the Bell number is \$\displaystyle 115975\$.
So there are that many equivalence relations for a set of ten.

In this case the number is small. It is less that 10.
All you have to do is list all possible partitions of \$\displaystyle \{1,2,3\}\$ and count them.
• Oct 16th 2011, 09:02 AM
mathproblems
Re: Equivalence relations
[1]=[2]=[3]= {1,2,3}
3 correct?
• Oct 16th 2011, 09:06 AM
Plato
Re: Equivalence relations
Quote:

Originally Posted by mathproblems
[1]=[2]=[3]= {1,2,3}
3 correct?

No. That as nothing to do with any of this.
Do you know what a partition of that set is?
If so, show us four of them.
If you don't know, then you are not ready to do this question.
• Oct 16th 2011, 09:08 AM
emakarov
Re: Equivalence relations
Yes, as I said in post #2,
Quote:

Originally Posted by emakarov
If R = {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)}, then [1] is indeed {1, 2, 3}, but [2] = [3] = {1, 2, 3} as well with respect to R.

Also, as I said in post #4,
Quote:

Originally Posted by emakarov
In any case, so far you have found just one equivalence relation, which is the total relation on {1, 2, 3}. There are several others. Again, my advice is to enumerate all possible partitions.

Imagine that there are three regions on the map and that there are 1, 2, or 3 kings are fighting with each other for these regions. How can they split them between themselves? Start with 3 kings, then consider 2 kings, and finally just 1. Each splitting would be a partition.
• Oct 16th 2011, 09:11 AM
mathproblems
Re: Equivalence relations
Quote:

Originally Posted by Plato
No. That as nothing to do with any of this.
Do you know what a partition of that set is?
If so, show us four of them.
If you don't know, then you are not ready to do this question.

no I guess I dont know, so I cannot really show four of them. Would you please?
• Oct 16th 2011, 02:48 PM
mathproblems
Re: Equivalence relations
Quote:

Originally Posted by Plato
No. That as nothing to do with any of this.
Do you know what a partition of that set is?
If so, show us four of them.
If you don't know, then you are not ready to do this question.

{ {1}, {2}, {3} }, or 1/2/3.
{ {1, 2}, {3} }, or 12/3.
{ {1, 3}, {2} }, or 13/2.
{ {1}, {2, 3} }, or 1/23.
{ {1, 2, 3} }, or 123
is this correct?
• Oct 16th 2011, 02:53 PM
Plato
Re: Equivalence relations
Quote:

Originally Posted by mathproblems
{ {1}, {2}, {3} }, or 1/2/3.
{ {1, 2}, {3} }, or 12/3.
{ {1, 3}, {2} }, or 13/2.
{ {1}, {2, 3} }, or 1/23.
{ {1, 2, 3} }, or 123
is this correct?

BINGO By George you have it.