Question

离散数学之等价关系

设集合A={a,b,c,d},问在集合A上可以定义多少个等价关系？

Answer 1

集合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合的一个等价关系,不同的等价关系对应于集合的划分也不同,因此集合有多少不同划分,就有多少不同等价关系,三个元素的集合共有5种不同划分,(含有1块和3块各有1种,含有2块有3种),故含有三个元素的集合，可以确定5种等价关系。
如A={1，2，3}，则5种不同划分为 ：
{{1}，{2}，{3}}；{{1}，{2,3}}；{{1,3}，{2}}；{{1,2}，{3}}；{1, 2, 3}}；
对应的等价关系为：
R1={(1,1),(2,2),(3,3)};
R2={(1,1),(2,2),(2,3),(3,2),(3,3)};
R3={(1,1),(1,3),(3,1),(2,2),(3,3)};
R4={(1,1),(1,2),(2,1),(2,2),(3,3)};
R5={(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1)};
一般地,对有n个元素的集合有Bn种不同的划分(等价关系),Bn称为Catalan数，Bn=2n!/((n+1)n!n!),如4个元素的集合，可以确定14种等价关系。

Answer 2

共有15种：

具体等价关系的划分类型：

1+1+1+1型共1种
{{a},{b},{c},{d}}
2+1+1型共6种
{{a,b},{c},{d}}
{{a,c},{b},{d}}
{{a,d},{b},{c}}
{{c,b},{a},{d}}
{{d,c},{b},{a}}
{{b,d},{a},{c}}

2+2型共3种
{{a,b},{c,d}}
{{a,c},{b,d}}
{{a,d},{b,c}}
3+1型共4种
{{a,b,c},{d}}
{{a,c,d},{b}}
{{a,b,d},{d}}
{{b,c,d},{a}}

4型共1种
{{a,b,c,d}}

追问

你好，“关系”不是应该为这种形式的吗？等价关系需要满足自反性、对称性、传递性，那定义的关系至少都应该包含{,,,,}这些序偶吧？

追答

我写的是等价关系的划分A/R，不是直接写的等价关系R，请看清楚回答。

追问

你好，不好意思还是不太明白，若是划分应该用[x]来表示吧？能不能请你任举一个例子，比如“2+1+1型”中的{{a,b},{c},{d}}所代表的关系R是什么？谢谢，已多追加10分:-)

追答

“2+1+1型”中的{{a,b},{c},{d}}

具体来讲就是
,,,,,