集合、关系与函数：练习题及分步解答

1集合与集合运算

集合是由互不相同的元素组成的整体：A = {1, 2, 3}。顺序和重复无关紧要。|A| 是元素个数，U 是包含所讨论的一切对象的全集。

• A ∪ B（并集）：属于 A 或 B 或两者的元素。
• A ∩ B（交集）：同时属于两者的元素。
• A − B（差集）：属于 A 但不属于 B 的元素。
• A′（补集）：属于 U 但不属于 A 的元素。

在维恩图中，两个圆把 U 分成四个区域：只属于 A、两者都属于、只属于 B，以及都不属于。每个集合表达式都是其中若干区域的并集，所以总可以逐个区域地计数。

这里 |A| = 12 + 5 = 17，|A ∩ B| = 5，|A ∪ B| = 12 + 5 + 8 = 25，|(A ∪ B)′| = 15。

2用容斥原理计数

把 |A| 和 |B| 相加会把重叠部分计两次，所以要减去一次：

对于三个集合，要减去两两的重叠部分，但这样中心部分被减去了三次，所以要加回来：

在应用题中，通常更稳妥的做法是从中心向外填写维恩图：先填同时属于三个集合的元素，再填每两个集合的部分（减去中心），然后填每个单独集合（减去已经填入的部分）。

另外两个常见的计数：有 n 个元素的集合有 2ⁿ 个子集（即它的幂集 𝒫(A)），以及 |A × B| = |A|·|B| 个有序对。

3例题讲解

跟着每一步走。打开下一步之前，先试着预测它。

4关系

集合 X 上的关系 R 是由有序对 (x, y) 组成的集合，其中 x 和 y 属于 X。画成有向图时，每个序对是一条箭头，(x, x) 是一个环。

• 自反：对每个 x 都有 (x, x) ∈ R：每个顶点上都有一个环。
• 对称：(x, y) ∈ R 时总有 (y, x) ∈ R。
• 反对称：(x, y) 和 (y, x) 同时属于 R 仅当 x = y。
• 传递：(x, y) 和 (y, z) 属于 R 时必有 (x, z) ∈ R。

既自反、又对称、又传递的关系是等价关系。它把 X 分成互不相交的类，例如“x ≡ y (mod 3)”的余数类 0、1 和 2。含 s 个元素的类贡献 s² 个有序对。

要否定一个性质，一个反例就够了；要证明它，则要检验每一对。

5函数

函数 f: A → B 使 A 中每个元素在 B 中恰有一个像。

• 单射（一一映射）：不同元素有不同的像；B 中没有元素收到两条箭头。
• 满射（映上）：B 中每个元素至少收到一条箭头。
• 双射：两者兼具。只有这时 f 才有逆函数 f⁻¹。

图中的函数是单射但不是满射：d 没有收到箭头。单射需要 |A| ≤ |B|，满射需要 |A| ≥ |B|。

当 |A| = m，|B| = n 时，共有 nᵐ 个函数和 n!/(n − m)! 个单射。复合 (g ∘ f)(x) = g(f(x)) 先作用 f。

6常见错误

• 把 |A| + |B| 相加却没有减去重叠部分。
• 在三个集合的容斥原理中忘记把中心部分加回来。
• 把从 m 个元素到 n 个元素的函数个数写成 mⁿ，而不是 nᵐ。
• 以为关系不可能同时是对称和反对称的：关系 {(1, 1)} 两者兼具。
• 把 g ∘ f 的顺序弄错：先作用的是 f。

7考试题是什么样的

• 简单：维恩图与子集。你要根据维恩图数出集合表达式的元素个数，点选某个表达式对应的区域，或求出幂集、笛卡儿积或子集族的大小。
• 中等：容斥原理与关系。你要解两个集合和三个集合的计数问题，根据各区域的总数计算表达式，判断一个关系具有哪种性质，或数出求闭包所需添加的序对个数。
• 困难：函数与计数。你要把函数分类为单射、满射或双射，数出函数、单射和满射的个数，计算复合函数和逆函数，并数出等价关系中的序对个数。