Thread: 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.

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.

I am not sure if we need to add [2] and [3] since they are both have {1,2,3} the same as [1].

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.

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 .
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 and count them.

[1]=[2]=[3]= {1,2,3}
3 correct?

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.

Yes, as I said in post #2,

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,

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.

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?

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?

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.
So the answer is 5.

thank you!