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