Question

求离散数学高手，等价类的问题

设A=｛1,2,3,4｝,P(A)(A的幂集) 上规定二元关系如下 R=｛<s,t>|s,t∈P(A)∧(|s|=|t|)｝,求P(A)/R，求详细解答，

Answer 1

记 s∈P(A) 在P(A)/R 中的等价类为 sR.
设 s0 = 空集，s(i) = {1,2, ..,i}, i = 1,2,...,4. 则 P(A)/R = {s(i)R| i = 0, 1, ...,4}.
证明：注意到：　｜s（i）｜＝i，　i＝0，1，．．．，4.
1.　任意给　t∈P(A)，　0＜＝｜t｜＜＝4，　所以：tR＝s（｜t｜）R
于是，　{s(i)R| i = 0, 1, ...,4}　包含P(A)/R中的所有元素。
2.　任意给　0＜＝i，j＜＝4，i不等于j，　则因为
｜s（i）｜＝i不等于j＝｜s（j）｜，
所以：　s（i）R不等于s（j）R．　
于是结论成立。

追问

没看懂，答案是什么？用集合表示出来行吗

追答

P(A)/R = {s(i)R| i = 0, 1, ...,4}. 这正是集合表示的。
s0 = 空集
s1 = {1}
s2 = {1,2}
s3 = {1,2,3}
s4 = {1,2,3,4}
P(A)/R = {s0R, s1R, s2R, s3R, s4R}

追问

首先P(A)是A的幂集，则P(A)=｛空集,{1},{2},{3},{4}……,{1,2,3,4}｝，共2的四次方 16个元素，而P(A)/R是P(A)的一个划分，而根据划分的定义 S1,S2……之间不能有交集。怎么解释呢？

追答

无交集 正是 我前面证明中 2 所说明的。不是A的子集间无交，而是一个子集不能同属于两个等价类。
P(A) 有16个元素， 安等价类分 如下：
含0个A的元素的子集： {空集} -------- s0R
含1个A的元素的子集： {{1},{2}, {3},{4}} ---- s1R
含2个A的元素的子集： {{1,2},{1,3},... {3,4}} ---- s2R
含3个A的元素的子集： {{1,2,3},{1,2,4}, ..., {2,3,4}} ---- s3R
含4个A的元素的子集： {{1,2,3,4}} ---- s4R