1. ## 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.

2. ## 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.

3. ## 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].

4. ## 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.

5. ## Re: Equivalence relations

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 $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 $\{1,2,3\}$ and count them.

6. ## Re: Equivalence relations

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

7. ## Re: Equivalence relations

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.

8. ## Re: Equivalence relations

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.

9. ## Re: Equivalence relations

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?

10. ## Re: Equivalence relations

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?

11. ## Re: Equivalence relations

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.

thank you!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

# no of equivalence relations using bell

Click on a term to search for related topics.