离散数学题目：关于集合的等价关系

Question

问：在4个元素的集合上可定义的等价关系有（）个？

答案是15个，我认为错误，想找人核实
我觉得是12个，想请人对照答案

Answer 1

含有4个元素的集合, 可以构成15个等价关系.

对zhangzhuxueli的回答修改补充如下:

4个元素互不等价, 有C(0,4)=1种情形; [C(m,n)表示n中取m的组合数]
4个元素分为3个等价类 (分别含元素1,1,2个), 共有C(2,4)=6种情形;
4个元素分为2个等价类 (分别含元素1,3个或2,2个), 共有C(3,4)+C(2,4)/2=4+3=7种情形;
4个元素属于同一等价类, 只有1种情形.
以上情形之和为 1+6+7+1=15.

具体15种不同等价关系的列举请见参考链接.

参考资料：http://zhidao.baidu.com/question/78905236.html

Answer 2

我认为你的回答正确，理由是：
4个元素互不等价，有C(0,4)=1种情形；[C(m,n)表示n中取m的组合数]
4个元素分为3个等价类（分别含元素1，1，2个），共有C(2,4)=6种情形；
4个元素分为两个等价类（分别含元素1，3个），共有C(3,4)=4种情形；
4个元素属于同一等价类，只有1种情形。
以上情形之和为 1+6+4+1=12。

我曾经推导过一般结论：
1个元素的集合上可以定义的等价关系有1个；
2个元素的集合上可以定义的等价关系有3个；
n(n是大于1的奇数)个元素的集合上可以定义的等价关系有
1+2^(n-1)个；
n(n是大于2的偶数)个元素的集合上可以定义的等价关系有
1+2^(n-1)+(1/2)C(n/2,n)个.

Answer 3

证明
只需验证如下3个条件，即知
s
也是一个等价关系。设
r
是
a
上的关系，
1）自反性：对任意
a∈a，因
∈r，
∈r，故
∈s；
2）传递性：设
,
∈s，则有
d,
e∈a，使
∈r，
∈r，
∈r，
∈r，
而
r
具传递性，得
∈r，
∈r，
由
s
的定义，得
∈s，传递性得证。
3）对称性：设
∈s，则有
c∈a，使
∈r，
∈r，
而
r
具传递对称性，得
∈r，
∈r，
由
s
的定义，得
∈s，对称性得证。