得分
一、（20 分）对于任意集合 A 和 B， （1）证明：P(A)P(B) = P(AB)； （14 分）
对任意的 xP(A)P(B)，有 xP(A)且 xP(B)。即 xA 并且 xB，
则 xAB。所以 xP(AB)。故 P(A)P(B)P(AB)。 （7 分）
对任意的 xP(AB)，有 xAB，即 xA 并且 xB，所以 xP(A)
满射：3!*{4,3} + 4*3! =60 （4 分） 单射: 4*3! + C(4,2)*3*2 + C(4,1)*3 +1 =73 （4 分） 双射： 4*3！=24 （4 分）
得分
四、（20 分）用数学归纳法证明：
任意一个自然数的真子集都和某一个自然数等势。
S={n|nN x( x n m(mN mn))} (6 分)
(2) card P(N) = card N2 （5 分） 证一：同书上证明，子集合的特征函数。 证二：card P(N)= 2^\aleph_0=\aleph_1，card N2=2^\aleph_0=\aleph_1。
(3) 证明 < （5 分） 利用\aleph_0 < \aleph_1。
card NN =card 2N < card P(N) = card N2 （5 分，四者两两之间 6 种 关系每错 1 个扣 1 分）
证明：(1) card NN =card 2N （5 分） 证一：定义双射 H: (NN) (2N)，H(<a,b>)=f，f: 2N，f(0)=a, f(1)=b。 证二：card NN=\aleph_0，card 2N=\aleph_0。
1）S （4 分）
2）nS n+S (2 分 )
n+ = n{n}, x n+ 分三种 情况讨论 ：(2 分 )
a) x n, mx
(2 分 )
b) x=n, xn
(2 分 )
3) nx, x-{n} n, x -{n} m，则 xm+ (2 分 )
得分
五、（20 分）设 N 是自然数集，试比较以下四个集合的基数大小，并 给出证明. （1）NN （2）P(N) （3）N2 （4）2N
因为(f, a)RS，则存在 gA，使得(f, g)R，(g, a)S；因为 R 是传递的，
由(c, f)R，(f, g)R，则(c, g)R；因为(c, g)R，(g, a)S，所以(c, a)RS。 因为已经证明，RS 是对称的，所以(a, c)RS
得分
三、（20 分）试回答下列问题，并说明理由. （1）集合 A={a,b,c,d}, B={1,2,3}, 求 A 到 B 的所有偏函数、 全函数分别有多少个？ (8 分)
所有偏函数： 3^4 + C(4,3)*3^3 + C(4,2)*3^2 + C(4,1)*3^1+1=256 （4 分）
全函数：3^4 =81 （4 分）
（2）把所有偏函数 f : AB 通过 f : dom(f)B 转换成全函数，问这些全函数中 包含多少个单射函数？多少个满射函数？和多少个双射函数？ （12 分）
ቤተ መጻሕፍቲ ባይዱ
且 xP(B)。因此 P(AB)P(A)P(B)。
（7 分）
综上所述，P(A)P(B)=P(AB)
（2）举例说明 P(A)P(B) P(AB). （6 分）
A={1}, B={2}, AB={1, 2}; P(A)={, {1}}, P(B)={, {2}},
P(A)P(B)= {, {1}, {2}},
P(AB)= {, {1}, {2}, {1, 2}}; 所以 P(A)P(B)P(AB)
得分
二、（20 分）设 R, S 是 A 上的等价关系且 RS=SR，证明： RS 是 A 上的等价关系.
自反性和对称性容易证明，略。（5 分） 传递性证明： 对任意 a, b, cA，如果(a, b)RS, (b, c)RS，要证明(a, c)RS。 因为 RS=SR，则有(b, c)SR，即存在 e, fA，使(a, e)R，(e, b)S，(b, f)S， (f, c)R。 因为 S 是传递的，(e, b)S，(b, f)S，所以(e, f)S；因为(a, e)R，所以(a, f)RS；RS 是对称的，则(f, a)RS；因为 R 是对称的，(f, c)R，则(c, f)R。