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.

Printable View

- Oct 16th 2011, 07:34 AMmathproblemsEquivalence 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 AMemakarovRe: 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 AMmathproblemsRe: 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 AMemakarovRe: 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 AMPlatoRe: Equivalence relations
**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 AMmathproblemsRe: Equivalence relations
[1]=[2]=[3]= {1,2,3}

3 correct? - Oct 16th 2011, 09:06 AMPlatoRe: Equivalence relations
- Oct 16th 2011, 09:08 AMemakarovRe: Equivalence relations
Yes, as I said in post #2,Also, as I said in post #4,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 AMmathproblemsRe: Equivalence relations
- Oct 16th 2011, 02:48 PMmathproblemsRe: Equivalence relations
- Oct 16th 2011, 02:53 PMPlatoRe: Equivalence relations
- Oct 16th 2011, 02:53 PMmathproblemsRe: Equivalence relations
thank you!