集合与映射

{/* label: chap:ch02 */}

\begin{figure}[htbp]

TikZ 图 4

\end{figure} 新高考选科后，学校需要精准统计学生选课情况，以便分班和安排教学资源.已知选物理、化学、地理的人数，以及同时选物理和化学、物理和地理、化学和地理的人数，甚至三科同时都选的人数.如何才能不重不漏地算出，至少选了理科三门中任意一科的学生总数？或者，只选了物理这一科的学生究竟有多少？这个问题看似复杂，其本质正是集合的运算，读完本章后，相信读者能够清晰地解决此类问题.

本章作为高中数学的起点，不仅为我们提供了描述所有数学对像（如数集、函数定义域、方程解集）的统一框架，也教会我们如何用最严谨的方式思考和表达.本章的主角是：

• 集合的基本概念、表示方法、关系与运算.
• 常用数集及其扩张历程，特别是实数系的完备性.
• 逻辑用语：四种命题与量词否定.
• 核心转化思想：充要条件与集合包含关系的等价性.

本章开头图示所展现的选科问题看似复杂，其本质正是集合的运算.掌握本章内容，将为后续所有数学内容的学习打下坚实的语言和思想基础.

集合论初步

{/* label: sec:ch02-s01 */}

集合的基本概念

在我们的日常思维与交流中，将事物归类与分组是一种基本的认知活动.例如，当我们参观动物园时，我们可能会谈论所有猫科动物的总体，或者所有来自非洲的动物的群体.类似地，我们可以考虑一支篮球队的所有队员，太阳系中的所有行星，或是更为抽象的，所有小于10的素数.

这些例子中的总体、群体或全体，尽管称谓不同，但都指向一个核心概念：将一些明确的对象作为一个整体来研究.为了精确、无歧义地描述这类整体，数学家们引入了一个基本而深刻的概念——集合.

集合

我们把一些确定的、可以互相区分的事物汇集成的整体称为集合.构成集合的每个事物称为该集合的元素.

此定义蕴含了三个作为集合论基石的特性： \begin{compactdesc} \item[确定性] 对于一个给定的集合，任何一个对象是否属于这个集合，其答案必须是明确的，非此即彼.例如，“所有大于$\pi$的实数”构成一个集合，但“世界上所有著名的数学家”则不能，因为“著名”的标准是模糊的. \item[互异性] 集合中的元素必须是互不相同的.在描述一个集合时，任何重复的对象只计入一次.例如，方程 $(x-1)^2=0$ 的解集是 $\{1\}$, 而非 $\{1, 1\}$. \item[无序性] 集合中的元素没有先后次序之分.元素的位置变化不改变集合本身.例如，集合 $\{1, 2, 3\}$ 与集合 $\{3, 1, 2\}$ 是完全相同的. \end{compactdesc}

我们通常用大写斜体字母 $A, B, C, ...$ 表示集合, 用小写斜体字母 $a, b, c, ...$ 表示元素.若 $a$ 是集合 $A$ 的元素, 记作 $a \in A$ (读作“$a$ 属于 $A$”).若 $a$ 不是集合 $A$ 的元素, 记作 $a \notin A$ (读作“$a$ 不属于 $A$”).

集合的表示方法

\paragraph{列举法} 当集合中的元素个数有限或呈现出明显的规律时，可将所有元素一一列举，并用花括号 \{\} 括起来.例如，所有正偶数的集合可表示为 $\{2, 4, 6, 8, ...\}$.

\paragraph{描述法} 这是数学中最常用且最强大的表示方法.它通过描述集合中所有元素共有的独特性质来定义集合，其标准形式为：$\{x \mid P(x)\}$.例如, 方程 $x^2 - 9 = 0$ 的解集可表示为 $\{x \in \mathbb{R} \mid x^2 - 9 = 0\}$.

\paragraph{Venn图法} 由英国数学家约翰·维恩发明，使用平面上的封闭曲线（通常是圆形）来直观地表示集合及其相互关系.

例

用列举法表示集合 $A = \{d \mid d = \frac{6}{5-a} \in \mathbb{N}^*, a \in \mathbb{Z}\}$.

解

解读此集合的描述法定义是解题的第一步. 集合 $A$ 的元素是 $d$, 而非参数 $a$. 这些元素 $d$ 必须满足两个核心条件：

1. $d$ 必须是一个正自然数 ($d \in \mathbb{N}^*$)，即正整数.
2. $d$ 的值由一个以整数 $a$ 为参数的表达式 $\frac{6}{5-a}$ 给出.

这两个条件之间存在着深刻的代数结构约束. 由于 $d$ 必须是整数, 表达式 $\frac{6}{5-a}$ 的分母 $(5-a)$ 必须是分子 $6$ 的一个整数因数. 不仅如此，由于 $d$ 必须为正数, 且分子 $6$ 为正, 分母 $(5-a)$ 也必须为正数.

因此，我们的问题被转化为一个更具体的问题：寻找整数 $6$ 的所有正因数. $6$ 的正因数集合为 $\{1, 2, 3, 6\}$. 这就为分母 $(5-a)$ 提供了所有可能的取值. 我们逐一考察这些可能值，以确定集合 $A$ 的所有元素:

• 若 $5-a = 1$, 则 $a=4$. 此时 $d = \frac{6}{1} = 6$.

• 若 $5-a = 2$, 则 $a=3$. 此时 $d = \frac{6}{2} = 3$.

• 若 $5-a = 3$, 则 $a=2$. 此时 $d = \frac{6}{3} = 2$.

• 若 $5-a = 6$, 则 $a=-1$. 此时 $d = \frac{6}{6} = 1$.

  这些计算产生的 $d$ 值 $\{1, 2, 3, 6\}$ 构成了集合 $A$ 的全部元素. 故，用列举法表示的集合 $A$ 为 $\{1, 2, 3, 6\}$.

参数与元素的辨析

一个常见的思维陷阱是将满足条件的参数 $a$ 的集合 $\{-1, 2, 3, 4\}$ 误认为是集合 $A$. 必须时刻牢记, 集合的元素由描述法中竖线 | 左侧的变量所定义. 在本例中, 这个变量是 $d$. 参数 $a$ 仅仅是用于生成这些元素的内部工具，其本身并非集合的成员.

例

用列举法表示集合 $S = \{y \mid y=x^2, -1 \< x \< 2, y \in \mathbb{Z}\}$.

解

此集合 $S$ 的元素是所有满足特定条件的整数 $y$. 条件是：这样的 $y$ 必须能表示为一个实数 $x$ 的平方, 且 $x$ 的取值范围被限制在开区间 $(-1, 2)$ 内.

解决这类问题的有效策略是分步进行：首先，忽略整数限制，确定由函数关系和自变量范围所决定的因变量 $y$ 的完整连续取值范围；然后，从这个范围中筛选出所有整数.

我们考察函数 $f(x)=x^2$ 在区间 $x \in (-1, 2)$ 上的值域. 这是一个开口向上、顶点在原点的二次函数. 当自变量 $x$ 从 $-1$ (不含) 变化到 $2$ (不含) 时, 函数值 $y=x^2$ 的变化轨迹如何？

• 当 $x$ 从 $-1$ 趋近于 $0$ 时, $y$ 从 $(-1)^2=1$ 减小到 $0$.

• 在 $x=0$ 处, $y$ 达到其最小值 $0^2=0$.

• 当 $x$ 从 $0$ 增大到 $2$ 时, $y$ 从 $0$ 增大到 $2^2=4$.

  综合来看，当 $x$ 遍历整个区间 $(-1, 2)$ 时, $y$ 的取值范围是 $[0, 4)$. 注意到 $y=0$ 是可以取到的, 而 $y=4$ 只是一个无法达到的上界.

  \begin{figure}[htbp]

TikZ 图 5

{y=x^2} 在定义域 \texorpdfstring{$x \in (-1, 2)$}{x in (-1, 2)} 上的图像（加粗曲线）. 其值域为 \texorpdfstring{$[0, 4)$}{[0, 4)}, 其中包含的整数点已在 \texorpdfstring{$y$}{y} 轴上标出.}

\end{figure} 图：函数 \texorpdfstring{$y=x^2$

最后一步是施加整数约束 $y \in \mathbb{Z}$. 我们需要在区间 $[0, 4)$ 中寻找所有的整数. 即求解 $y \in [0, 4) \cap \mathbb{Z}$. 这些整数显然是 $0, 1, 2, 3$.

因此，集合 $S$ 用列举法表示为 $\{0, 1, 2, 3\}$.

常用数集与数系的扩张

数学中一些基础数集被频繁使用，它们之间存在着深刻的包含关系，反映了数系为满足运算的封闭性而不断扩张的历程.封闭性是指集合内的元素经过某种运算后，其结果仍然在该集合内.

从自然数到整数（满足减法封闭性）

人类最早认识的数是用于计数的，譬如数羊：一只羊、二只羊等等，这便产生了自然数集 $\mathbb{N} = \{0, 1, 2, 3, ...\}$.在 $\mathbb{N}$ 中，加法和乘法是封闭的，但减法并非如此.考虑方程： <MathBlock raw={"x + 5 = 2"} /> 此方程在自然数集 $\mathbb{N}$ 中无解.为了使任意的减法运算都有意义, 数学家引入了负整数的概念.将正整数、0、负整数合并, 我们得到了整数集 $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$.记号 $\mathbb{Z}$ 源于德语单词 \textrm{Zahlen} (意为“数”).显然, $\mathbb{N} \subsetneq \mathbb{Z}$.

从整数到有理数（满足除法封闭性）

整数集解决了任意减法的问题，但除法又带来了新的挑战.考虑方程： <MathBlock raw={"3x = 1"} /> 此方程在整数集 $\mathbb{Z}$ 中无解.为了使除法运算(除数不为0时)具有封闭性, 我们必须引入分数.所有能表示为两个整数之比的数, 构成了有理数集 $\mathbb{Q}$. <MathBlock raw={"\mathbb{Q} = \left\{ x \mid x = \frac{p}{q}, p \in \mathbb{Z}, q \in \mathbb{Z} \text{ 且 } q \neq 0 \right\}"} /> 记号 $\mathbb{Q}$ 源于德语单词 \textrm{Quotient} (意为“商”).整数可以被看作分母为1的分数, 因此 $\mathbb{Z} \subsetneq \mathbb{Q}$.

从有理数到实数（补全数轴的完备性）

有理数集 $\mathbb{Q}$ 在数轴上已经非常稠密, 即任意两个不相等的有理数之间都存在无数个有理数.但这并不意味着有理数已能表示数轴上所有的点.古希腊的毕达哥拉斯学派发现, 边长为1的正方形其对角线长度 $\sqrt{2}$ 无法表示为两个整数之比.这类数被称为无理数.其他著名的无理数还包括圆周率 $\pi$ 和自然对数的底 $e$.

将有理数集与无理数集合并，我们得到了能够与数轴上的点一一对应的实数集 $\mathbb{R}$.这是一个直观但并不足够严谨的描述.我们不禁要问：我们如何能确信已经“填补”了所有的“缝隙”？实数集 $\mathbb{R}$ 的本质究竟是什么？有兴趣的同学可以阅读下面的思想实验.

让我们进行一个思想实验，来尝试捕捉数轴上一个“点”的精确位置.想像一把无比锋利的“刀”，我们用它在有理数构成的数轴上切下一刀.这一刀会将所有的有理数分割成两个非空的集合：一个在“刀口”左边的集合 $L$, 和一个在“刀口”右边的集合 $R$.这个分割 $(L, R)$ 必须满足一个自然的要求：集合 $L$ 中的每一个数都严格小于集合 $R$ 中的每一个数.

接着，让我们来考察“刀口”处的情况：

情况一：刀口落在有理数上 假设我们在有理数 $q=3$ 的位置切下这一刀.我们可以这样定义分割：

• 左集合 $L = \{x \in \mathbb{Q} \mid x \le 3\}$
• 右集合 $R = \{x \in \mathbb{Q} \mid x \> 3\}$

请注意一个关键特征：在这次分割中，左集合 $L$ 拥有一个最大元素, 即 $3$ 本身.这个最大元素精确地标记了分割的位置.(我们也可以定义 $L=\{x\<3\}, R=\{x \ge 3\}$, 此时右集合 $R$ 有一个最小元素.关键在于，总有一个集合能“抓住”这个理性的边界点.)

情况二：刀口落在“缝隙”中 接着，让我们尝试在 $\sqrt{2}$ 应该在的位置切下一刀.由于我们只能使用有理数来描述，我们必须根据有理数的性质来定义分割：

• 左集合 $L = \{x \in \mathbb{Q} \mid x \< 0 \text{ 或 } x^2 \< 2\}$
• 右集合 $R = \{x \in \mathbb{Q} \mid x \> 0 \text{ 且 } x^2 \> 2\}$

我们来考察这个新分割 $(L, R)$ 的边界.

• 左集合 $L$ 是否有最大元素？答案是没有.无论我们找到 $L$ 中多么接近 $\sqrt{2}$ 的一个有理数 $x_0$, 我们总能找到另一个有理数 $x_1$ 也在 $L$ 中, 且 $x_0 \< x_1$.
• 右集合 $R$ 是否有最小元素？答案同样是没有.无论我们找到 $R$ 中多么接近 $\sqrt{2}$ 的一个有理数 $y_0$, 我们总能找到另一个有理数 $y_1$ 也在 $R$ 中, 且 $y_1 \< y_0$.

在这种情况下，分割的“刀口”既不属于左集合（作为最大值），也不属于右集合（作为最小值）.它恰好落在了有理数集的一个“缝隙”之中.

\begin{figure}[htbp]

TikZ 图 6

{L}；右侧的空心点表示该边界点在有理数集 \texorpdfstring{$\mathbb{Q}$}{Q} 中“悬空”，不被任何一个集合捕获.} \end{figure} 图：左侧的实心点表示该点属于集合 \texorpdfstring{$L$

十九世纪德国数学家戴德金提出了一个革命性的思想：我们不必去“寻找”那些填补缝隙的数，我们可以直接用**“分割”本身来定义数**.

• 每一个对有理数集的分割 $(L, R)$ 就是一个实数.
• 如果分割中，集合 $L$ 有最大元素或集合 $R$ 有最小元素，那么这个分割就定义了一个有理数.
• 如果分割中，集合 $L$ 没有最大元素且集合 $R$ 没有最小元素，那么这个分割就定义了一个无理数.

这样一来，实数集 $\mathbb{R}$ 就被严谨地定义为有理数集 $\mathbb{Q}$ 上所有可能的这种分割的集合.这个构造性的定义从根本上保证了实数轴的连续性和完备性，即没有任何“缝隙”存在.

例

使用戴德金分割来定义有理数 $q = \frac{2}{3}$，并说明其与无理数分割的本质区别.

解

我们按照有理数分割的特征来构造集合 $L$ 和 $R$.一个标准的构造方式是： <MathBlock raw={"L = \left\{x \in \mathbb{Q} \mid x \le \frac{2}{3}\right\}, R = \left\{x \in \mathbb{Q} \mid x \> \frac{2}{3}\right\}"} />

这是一个合法的分割.接着我们来分析其边界属性.

左集合 $L$: 根据 $L$ 的定义, 有理数 $\frac{2}{3}$ 本身就属于集合 $L$. 对于 $L$ 中任意一个元素 $p$, 根据定义我们有 $p \le \frac{2}{3}$. 这表明，$\frac{2}{3}$ 大于或等于 $L$ 中的所有元素. 因此，$\frac{2}{3}$ 就是集合 $L$ 的最大元素.

右集合 $R$: $R$ 中是否存在最小元素？假设存在一个最小元素 $r_{min} \in R$. 那么 $r_{min} \> \frac{2}{3}$. 考虑 $r_{min}$ 与 $\frac{2}{3}$ 的算术平均值 $m = \frac{1}{2}\left(r_{min} + \frac{2}{3}\right)$. $m$ 显然是一个有理数. 由于 $r_{min} \> \frac{2}{3}$, 我们有 $m \> \frac{1}{2}\left(\frac{2}{3} + \frac{2}{3}\right) = \frac{2}{3}$, 所以 $m \in R$. 同时， $m \< \frac{1}{2}\left(r_{min} + r_{min}\right) = r_{min}$. 我们找到了一个比 $r_{min}$ 更小的元素 $m$ 也在 $R$ 中, 这与 $r_{min}$ 是最小元素矛盾. 所以 $R$ 没有最小元素.

为有理数 $\frac{2}{3}$ 构造的分割 $(L, R)$, 其左集合 $L$ 中存在一个最大元素 ($\frac{2}{3}$ 本身), 而右集合 $R$ 中没有最小元素.这与为 $\sqrt{2}$ 构造的分割形成了鲜明对比. 其本质区别在于：有理数分割的“刀口”被其中一个集合“捕获”了，没有产生缝隙；而无理数分割的“刀口”则悬于两个集合之间，定义了一个缝隙.

至此，我们完成了高中阶段主要讨论的数集的扩张之旅，其关系可总结为： <MathBlock raw={"\mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}"} />

集合间的基本关系

子集与真子集

对于两个集合 $A$ 和 $B$, 如果集合 $A$ 中的任意一个元素都是集合 $B$ 的元素, 我们就称集合 $A$ 是集合 $B$ 的子集, 记作 $A \subseteq B$. <MathBlock raw={"A \subseteq B \iff \forall x, (x \in A \implies x \in B)"} /> 如果 $A \subseteq B$, 且集合 $B$ 中至少存在一个元素不属于集合 $A$, 则称集合 $A$ 是集合 $B$ 的真子集, 记作 $A \subsetneq B$.

\begin{proposition}[空集与相等] 不含任何元素的集合称为空集，记作 $\emptyset$.

• 空集的性质: 空集是任何集合的子集.
• 集合相等: $A = B \iff A \subseteq B \text{ 且 } B \subseteq A$.

\end{proposition}

证明

根据子集的定义，$\emptyset \subseteq A$ 等价于逻辑命题“$\forall x, (x \in \emptyset \implies x \in A)$”为真. 该蕴含命题的前提“$x \in \emptyset$”恒为假, 因为空集中无任何元素.在逻辑推理中, 前提为假的蕴含命题恒为真（称为空虚的真）, 故 $\emptyset \subseteq A$ 对任意集合 $A$ 恒成立.

例

已知集合 $A = \{x \mid x^2 - 3x + 2 = 0\}$, 集合 $B = \{x \mid ax = 2\}$. 若 $A \cup B = A$, 求所有可能的实数 $a$ 组成的集合.

解

条件 $A \cup B = A$ 的内在含义是, 集合 $B$ 的所有元素并入集合 $A$ 后, $A$ 并未扩大.这当且仅当 $B$ 的所有元素原本就已经在 $A$ 中. 因此，该条件在逻辑上等价于 $B \subseteq A$.

首先，我们确定集合 $A$ 的具体元素. <MathBlock raw={"x^2 - 3x + 2 = 0 \implies (x-1)(x-2) = 0"} /> 解得 $x=1$ 或 $x=2$. 故 $A = \{1, 2\}$.

接着问题转化为，研究集合 $B = \{x \mid ax = 2\}$ 在何种条件下能成为 $A=\{1, 2\}$ 的子集.这需要对参数 $a$ 进行分类讨论.

情况一：$B$ 是空集. 空集是任何集合的子集，因此 $B = \emptyset$ 是满足 $B \subseteq A$ 的一种情形. 要使集合 $B$ 为空, 必须使方程 $ax=2$ 无解.这仅在 $a=0$ 时发生, 此时方程变为 $0 \cdot x = 2$, 此式对任何实数 $x$ 均不成立. 故 $a=0$ 是一个解.

情况二：$B$ 是非空子集. 若 $B$ 非空, 则 $a \neq 0$. 此时方程 $ax=2$ 有唯一解 $x = \frac{2}{a}$. 即 $B = \{\frac{2}{a}\}$. 要满足 $B \subseteq A$, 即 $\{\frac{2}{a}\} \subseteq \{1, 2\}$, 那么元素 $\frac{2}{a}$ 必须等于 $1$ 或 $2$.

• 若 $\frac{2}{a} = 1$, 则 $a=2$.

• 若 $\frac{2}{a} = 2$, 则 $a=1$.

  综上所述，所有可能的 $a$ 值构成的集合为 $\{0, 1, 2\}$.

例

设集合 $A = \{x \in \mathbb{R} \mid x^2 - 4x + 3 \le 0\}$, 集合 $B = \{x \in \mathbb{R} \mid 1-m \le x \le 3+m\}$. 若 $A \subsetneq B$, 求实数 $m$ 的取值范围.

解

首先解不等式确定集合 $A$： <MathBlock raw={"x^2 - 4x + 3 \le 0 \implies (x-1)(x-3) \le 0"} /> 解得 $1 \le x \le 3$. 所以 $A = [1, 3]$.

题目条件 $A \subsetneq B$ 包含两层独立的逻辑要求：其一是 $A \subseteq B$, 其二是 $A \neq B$.

我们先分析 $A \subseteq B$ 的条件. $[1, 3] \subseteq [1-m, 3+m]$ 意味着区间 $A$ 必须被区间 $B$ 完全覆盖. 这要求 $B$ 的左端点不大于 $A$ 的左端点, 且 $B$ 的右端点不小于 $A$ 的右端点.同时, 集合 $B$ 本身必须是一个有效的区间，即其左端点不大于右端点. 这可以表示为一个关于 $m$ 的不等式组： <MathBlock raw={"\begin{cases} 1-m \le 1 & (\text{左端点条件}) 3+m \ge 3 & (\text{右端点条件}) 1-m \le 3+m & (B\text{自身存在的条件}) \end{cases}"} /> 解这个不等式组： <MathBlock raw={"\begin{cases} m \ge 0 m \ge 0 -2 \le 2m \implies m \ge -1 \end{cases}"} /> 三个条件的交集为 $m \ge 0$.这是 $A \subseteq B$ 成立的充要条件.

接下来，我们处理真子集的条件 $A \neq B$. 这意味着必须排除使 $A=B$ 的情况. 若 $A=B$, 则区间的左右端点必须完全重合： <MathBlock raw={"\begin{cases} 1-m = 1 3+m = 3 \end{cases}"} /> 这两个方程都指向同一个解 $m=0$. 因此，为了保证 $A \neq B$, 我们必须有 $m \neq 0$.

综合以上两个要求：$A \subseteq B$ 要求 $m \ge 0$, $A \neq B$ 要求 $m \neq 0$. 两者的交集为 $m \> 0$. 故实数 $m$ 的取值范围是 $(0, +\infty)$.

例

已知集合 $A = \{0, 1, a\}$, $B = \{-1, a+1, a^2\}$. 若 $A=B$, 求实数 $a$ 的值.

解

集合相等的定义是两个集合的元素完全相同，与顺序无关.我们可以利用这一性质，通过分析特定元素的归属来确定参数 $a$ 的值.

我们观察到 $-1$ 是集合 $B$ 中一个确定的元素.根据 $A=B$, 可知 $-1$ 也必须是集合 $A$ 的元素. 在集合 $A=\{0, 1, a\}$ 中, 由于 $0 \neq -1$ 且 $1 \neq -1$，因此必然有： <MathBlock raw={"a = -1"} />

这是一个必要条件，但我们必须验证它是否充分.即需要检验当 $a=-1$ 时，两个集合是否确实完全相等. 我们将 $a=-1$ 代入原集合 $A$ 和 $B$ 中.

当 $a=-1$ 时, 集合 $A$ 为： <MathBlock raw={"A = \{0, 1, -1\}"} />

当 $a=-1$ 时, 集合 $B$ 为： <MathBlock raw={"B = \{-1, (-1)+1, (-1)^2\} = \{-1, 0, 1\}"} />

此时，$A=\{0, 1, -1\}$ 且 $B=\{-1, 0, 1\}$. 根据集合的无序性，这两个集合的元素完全相同. 因此，$A=B$ 成立.

故实数 $a$ 的值为 $-1$.

集合的基本运算

交集

由所有既属于集合 $A$ 又属于集合 $B$ 的元素构成的集合, 称为 $A$ 与 $B$ 的交集, 记作 $A \cap B$.其数学语言表述为： <MathBlock raw={"A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}"} /> 交集运算的本质是逻辑关系中的“且”，即寻找两个集合的公共部分.

例

已知集合 $A = \{x \in \mathbb{Z} \mid x^2 - 2x - 3 = 0\}$, 集合 $B = \{x \in \mathbb{R} \mid x \> 1\}$. 求 $A \cap B$.

解

在进行集合运算之前，首要任务是将用描述法给出的集合化为更直观、清晰的形式，通常是列举法或区间表示法.

对于集合 $A$, 其元素是满足二次方程 $x^2 - 2x - 3 = 0$ 的所有整数. 我们解这个方程： <MathBlock raw={"(x-3)(x+1) = 0"} /> 解得 $x=3$ 或 $x=-1$. 由于这两个解都是整数, 它们都符合集合 $A$ 的定义. 于是, 我们可以用列举法重写集合 $A$： <MathBlock raw={"A = \{-1, 3\}"} />

集合 $B$ 是由所有大于 $1$ 的实数构成的, 这是一个开区间 $(1, +\infty)$.

现在，我们来寻找 $A \cap B$ 的元素. 根据交集的定义, 一个元素必须同时属于 $A$ 和 $B$. 这意味着我们需要检验集合 $A$ 中的每一个元素是否也满足集合 $B$ 的条件.

• 对于元素 $-1 \in A$, 由于 $-1 \ngtr 1$, 所以 $-1 \notin B$.

• 对于元素 $3 \in A$, 由于 $3 \> 1$, 所以 $3 \in B$.

  因此，唯一同时属于两个集合的元素是 $3$. 故 $A \cap B = \{3\}$.

例

设集合 $A=\{x \in \mathbb{R} \mid -2 \le x \le 5\}$, 集合 $B=\{x \in \mathbb{R} \mid x^2 - x - 6 \> 0\}$. 求 $A \cap B$.

解

对于涉及不等式的集合运算，数轴是不可或缺的几何直观工具. 它可以将抽象的代数关系转化为清晰的几何位置关系.

首先，我们解析两个集合. 集合 $A$ 是一个闭区间 $A = [-2, 5]$.

对于集合 $B$, 我们需要解二次不等式 $x^2 - x - 6 \> 0$. <MathBlock raw={"(x-3)(x+2) \> 0"} /> 该不等式的解为 $x \< -2$ 或 $x \> 3$. 因此, 集合 $B$ 是两个不相交区间的并集： <MathBlock raw={"B = (-\infty, -2) \cup (3, +\infty)"} />

接下来，我们在数轴上同时表示出集合 $A$ 和 $B$，并寻找它们的公共部分.

\begin{figure}[htbp]

TikZ 图 7

{A} 和 \texorpdfstring{$B$}{B} 的交集.}

\end{figure} 图：利用数轴求解集合 \texorpdfstring{$A$

从数轴上可以清晰地观察到，两个集合的公共区域位于 $3$ 和 $5$ 之间. 我们必须仔细分析端点处的取舍：

• 左端点 $3$：$3 \in A$ (因为 $-2 \le 3 \le 5$), 但 $3 \notin B$ (因为 $B$ 要求 $x\>3$). 故 $3$ 不在交集中.

• 右端点 $5$：$5 \in A$ (因为 $-2 \le 5 \le 5$), 且 $5 \in B$ (因为 $5\>3$). 故 $5$ 在交集中.

  综上所述，两个集合的交集是一个左开右闭的区间. <MathBlock raw={"A \cap B = (3, 5]"} />

\begin{figure}[htbp]

TikZ 图 8

{A intersect B} 的Venn图示意 (阴影部分)} \end{figure} 图：交集 \texorpdfstring{$A \cap B$

并集

由所有属于集合 $A$ 或属于集合 $B$ 的元素构成的集合, 称为 $A$ 与 $B$ 的并集, 记作 $A \cup B$.其数学语言表述为： <MathBlock raw={"A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}"} /> 并集运算的本质是逻辑关系中的“或”.此处的“或”是包容性的，包含了同时属于二者的情况.

\begin{figure}[htbp]

TikZ 图 9

{A union B} 的Venn图示意 (阴影部分)} \end{figure} 图：并集 \texorpdfstring{$A \cup B$

例

已知集合 $A = \{-1, 3\}$, 集合 $B = \{x \in \mathbb{R} \mid x \> 1\}$. 求 $A \cup B$.

解

并集 $A \cup B$ 包含了所有属于 $A$ 的元素, 以及所有属于 $B$ 的元素. 我们只需将两个集合中的元素“汇集”在一起，并遵循互异性原则.

集合 $A$ 包含两个离散的整数: $-1$ 和 $3$. 集合 $B$ 包含所有大于 $1$ 的实数, 即区间 $(1, +\infty)$.

我们将这些元素合并： <MathBlock raw={"A \cup B = \{-1, 3\} \cup (1, +\infty)"} />

我们注意到，元素 $3$ 既属于集合 $A$, 也满足 $3\>1$ 从而属于集合 $B$. 在并集中, 它自然被包含在区间 $(1, +\infty)$ 内. 因此, 我们无需再单独列出 $3$. 而元素 $-1$ 仅属于集合 $A$, 它不被区间 $(1, +\infty)$ 包含，因此必须被单独列出.

综上，该并集是一个孤立点与一个开区间的组合. <MathBlock raw={"A \cup B = \{-1\} \cup (1, +\infty)"} /> 这是一个混合类型的集合，无法表示为单一的区间.

例

设集合 $A=\{x \in \mathbb{R} \mid -2 \le x \le 5\}$, 集合 $B=\{x \in \mathbb{R} \mid x \< -2 \text{ 或 } x \> 3\}$. 求 $A \cup B$.

解

我们再次借助数轴来分析此问题. 并集运算在数轴上的几何意义是将两个集合所覆盖的区域“合并”起来.

集合 $A$ 是闭区间 $[-2, 5]$. 集合 $B$ 是两个不相交的开区间的并集 $(-\infty, -2) \cup (3, +\infty)$.

\begin{figure}[htbp]

TikZ 图 10

{A} 和 \texorpdfstring{$B$}{B} 的并集. 集合 \texorpdfstring{$A$}{A} 恰好“填补”了集合 \texorpdfstring{$B$}{B} 在 \texorpdfstring{$[-2, 3]$}{[-2, 3]} 之间的空隙.}

\end{figure} 图：利用数轴求解集合 \texorpdfstring{$A$

我们将两个集合在数轴上覆盖的区域合并.

• 集合 $B$ 覆盖了 $(-\infty, -2)$ 区域.

• 关键点 $x=-2$：虽然 $-2 \notin B$, 但是 $-2 \in A$. 根据并集的“或”逻辑, 只要元素属于其中一个集合即可, 故 $-2 \in A \cup B$. 集合 $A$ 恰好“连接”了 $B$ 在 $-2$ 处的断点.

• 集合 $A$ 覆盖了 $[-2, 5]$ 区域.

• 集合 $B$ 覆盖了 $(3, +\infty)$ 区域.

  将这些区域全部合并，我们发现： <MathBlock raw={"A \cup B = (-\infty, -2) \cup [-2, 5] \cup (3, +\infty)"} />

  我们来化简这个表达式. $(-\infty, -2) \cup [-2, 5]$ 可以无缝连接成 $(-\infty, 5]$. 接着计算 $(-\infty, 5] \cup (3, +\infty)$. 由于区间 $(3, 5]$ 已经被前者包含, 这个并集的结果是 $(-\infty, +\infty)$.

  因此，这两个集合的并集覆盖了整个实数轴. <MathBlock raw={"A \cup B = \mathbb{R}"} />

补集

如果我们研究的集合都是某个给定的大集合 $U$ 的子集, 我们称 $U$ 为全集.对于 $U$ 的一个子集 $A$, 由 $U$ 中所有不属于 $A$ 的元素构成的集合, 称为 $A$ 在 $U$ 中的补集, 记作 $\complement_U A$.其数学语言表述为： <MathBlock raw={"\complement_U A = \{x \mid x \in U \text{ 且 } x \notin A\}"} /> 补集运算的本质是逻辑关系中的“非”，即从全集中排除特定集合的元素.

\begin{figure}[htbp]

TikZ 图 11

{complement A} 的Venn图示意 (阴影部分)} \end{figure} 图：补集 \texorpdfstring{$\complement_U A$

例

设全集 $U=\mathbb{R}$, 集合 $A = \{x \mid -1 \< x \le 3\}$. 求 $\complement_U A$.

解

补集 $\complement_U A$ 由所有属于全集 $U$ 但不属于集合 $A$ 的元素构成. 在本例中, 即为所有不满足条件 $-1 \< x \le 3$ 的实数 $x$.

一个实数 $x$ 不在区间 $(-1, 3]$ 内, 逻辑上意味着 $x$ 或者小于等于 $-1$, 或者大于 $3$. <MathBlock raw={"x \notin (-1, 3] \iff x \le -1 \text{ 或 } x \> 3"} />

这个逻辑转换是求解补集问题的核心. 它将对一个区间的否定，转化为两个独立区间条件的析取.

• 原条件中 $x \> -1$ 的否定是 $x \le -1$. 注意到开边界变成了闭边界.

• 原条件中 $x \le 3$ 的否定是 $x \> 3$. 注意到闭边界变成了开边界.

  我们将此结果用数轴直观地表示出来. \begin{figure}[htbp]

TikZ 图 12

{A} 与其在 \texorpdfstring{$\mathbb{R}$}{R} 中的补集的数轴表示. 补集恰好是 \texorpdfstring{$A$}{A} 在数轴上“挖掉”后剩下的部分，且端点的开闭性完全相反.}

\end{figure} 图：集合 \texorpdfstring{$A$

因此，集合 $A$ 的补集是两个不相交区间的并集. <MathBlock raw={"\complement_U A = (-\infty, -1] \cup (3, +\infty)"} />

例

设全集 $U=\mathbb{Z}$, 集合 $A = \{x \in \mathbb{Z} \mid x^2 \le 9\}$. 求 $\complement_U A$.

解

此题的一个关键点在于，全集不再是连续的实数集 $\mathbb{R}$, 而是离散的整数集 $\mathbb{Z}$. 这要求我们的最终答案必须由整数构成.

首先，我们明确集合 $A$ 的具体元素. 条件 $x^2 \le 9$ 在实数范围内等价于 $-3 \le x \le 3$. 由于集合 $A$ 的元素必须是整数 ($x \in \mathbb{Z}$), 我们需要从闭区间 $[-3, 3]$ 中筛选出所有的整数. <MathBlock raw={"A = \{-3, -2, -1, 0, 1, 2, 3\}"} />

接下来，我们寻找 $\complement_U A$. 它的元素是所有属于全集 $\mathbb{Z}$ 但不属于集合 $A$ 的整数. 这意味着，我们要寻找所有不在这七个元素之列的整数.

这些整数可以分为两部分：

• 所有小于 $-3$ 的整数.

• 所有大于 $3$ 的整数.

  因此，该补集可以用描述法表示为 $\{x \in \mathbb{Z} \mid x \< -3 \text{ 或 } x \> 3\}$. 用列举法（结合省略号）则可以更直观地展示为： <MathBlock raw={"\complement_U A = \{..., -5, -4\} \cup \{4, 5, ...\}"} />

全集的重要性

此题凸显了全集在补集运算中的决定性作用. 若此题的全集是 $\mathbb{R}$, 那么 $\complement_{\mathbb{R}} A$ 将是 $(-\infty, -3) \cup (3, +\infty)$, 一个由无穷多个实数构成的连续区间集合. 但由于全集是 $\mathbb{Z}$，其补集也必须是离散的整数集合.

集合的运算律

集合运算满足交换律、结合律、分配律等.其中，德摩根定律尤为重要.

德摩根定律

对于任意集合 $A, B$ 和全集 $U$，有： <MathBlock raw={"\begin{aligned} \complement_U(A \cup B) &= (\complement_U A) \cap (\complement_U B) \complement_U(A \cap B) &= (\complement_U A) \cup (\complement_U B) \end{aligned}"} />

备注

证明（以 $\complement_U(A \cup B) = (\complement_U A) \cap (\complement_U B)$ 为例）

我们通过逻辑等价推导来证明.对于任意元素 $x$： <MathBlock raw={"\begin{aligned} x \in \complement_U(A \cup B) &\iff x \notin (A \cup B) &&\text{(补集定义)} &\iff \neg (x \in A \text{ 或 } x \in B) &&\text{(并集定义)} &\iff (x \notin A) \text{ 且 } (x \notin B) &&\text{(逻辑德摩根律)} &\iff (x \in \complement_U A) \text{ 且 } (x \in \complement_U B) &&\text{(补集定义)} &\iff x \in (\complement_U A) \cap (\complement_U B) &&\text{(交集定义)} \end{aligned}"} /> 由于上述逻辑等价关系对任意 $x$ 恒成立，故原式得证.

导出容斥原理相关恒等式

设 $A, B, C$ 为有限集.试证明, 仅属于集合 $A$ 的元素个数为 <MathBlock raw={"\mathrm{card}(A) - \mathrm{card}(A \cap B) - \mathrm{card}(A \cap C) + \mathrm{card}(A \cap B \cap C)"} />

解

我们首先需要用集合运算的语言来精确描述“仅属于集合 $A$”的集合. 一个元素 $x$ 仅属于 $A$, 意味着 $x \in A$, 同时 $x \notin B$ 且 $x \notin C$. 这可以表示为集合 $A \cap (\complement_U B) \cap (\complement_U C)$.

注意到后两项的交集 $(\complement_U B) \cap (\complement_U C)$, 根据德摩根定律, 它等价于 $(B \cup C)$ 的补集. <MathBlock raw={"(\complement_U B) \cap (\complement_U C) = \complement_U(B \cup C)"} /> 因此，我们所求的集合可以写作 $A \cap \complement_U(B \cup C)$.

这个表达式的几何意义是从集合 $A$ 中“挖去”所有属于 $B$ 或 $C$ 的部分, 即从 $A$ 中除去 $A$ 与 $(B \cup C)$ 的交集. 因此，该集合的基数可以表示为 <MathBlock raw={"\mathrm{card}(A) - \mathrm{card}(A \cap (B \cup C))"} />

接着，我们处理 $A \cap (B \cup C)$ 这一项.根据集合的分配律，我们有 <MathBlock raw={"A \cap (B \cup C) = (A \cap B) \cup (A \cap C)"} />

利用两集合的容斥原理，我们得到 <MathBlock raw={"\mathrm{card}((A \cap B) \cup (A \cap C)) = \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}((A \cap B) \cap (A \cap C))"} />

注意到 $(A \cap B) \cap (A \cap C)$ 就是 $A \cap B \cap C$. 因此， <MathBlock raw={"\mathrm{card}(A \cap (B \cup C)) = \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}(A \cap B \cap C)"} />

将此结果代回我们之前的表达式，即可得到所求的元素个数： <MathBlock raw={"\begin{aligned} \mathrm{card}(A \cap \complement_U(B \cup C)) &= \mathrm{card}(A) - \mathrm{card}(A \cap (B \cup C)) &= \mathrm{card}(A) - \left( \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}(A \cap B \cap C) \right) &= \mathrm{card}(A) - \mathrm{card}(A \cap B) - \mathrm{card}(A \cap C) + \mathrm{card}(A \cap B \cap C) \end{aligned}"} /> 此即为所证.这个结果是构造完整的三集合容斥原理公式的一个重要组成部分.

例

设全集 $U = \mathbb{R}$, 已知集合 $A = \{x \mid x^2 - 2x - 8 \> 0\}$ 和 $B = \{x \mid -1 \le x \le 5\}$.求集合 $\complement_U(A \cup B)$.

解

若直接计算并集 $A \cup B$ 再求其补集, 则需要先求解二次不等式确定集合 $A$，然后将两个较为复杂的区间集合在数轴上合并，最后再寻找合并后集合的外部区域，过程较为繁琐. 德摩根定律为此提供了一个更为清晰的途径. <MathBlock raw={"\complement_U(A \cup B) = (\complement_U A) \cap (\complement_U B)"} /> 这个等式将一个复杂运算（先并后补）转化为两个简单运算（先分别求补）与一个交集运算的组合.

首先，我们确定集合 $A$ 的补集 $\complement_U A$. $\complement_U A$ 中的元素 $x$ 满足 $A$ 中条件的否定，即 <MathBlock raw={"x^2 - 2x - 8 \le 0 \implies (x-4)(x+2) \le 0"} /> 解得 $-2 \le x \le 4$. 因此, $\complement_U A = [-2, 4]$. 注意到，原集合 $A$ 是两个分离区间的并集, 而其补集 $\complement_U A$ 是一个单一的闭区间，形式上更为简洁.

接着，我们确定集合 $B$ 的补集 $\complement_U B$. <MathBlock raw={"\complement_U B = \{x \mid x \< -1 \text{ 或 } x \> 5\} = (-\infty, -1) \cup (5, +\infty)"} />

最后，我们计算这两个补集的交集. <MathBlock raw={"(\complement_U A) \cap (\complement_U B) = [-2, 4] \cap \left( (-\infty, -1) \cup (5, +\infty) \right)"} /> 通过数轴可以清晰地观察到，区间 $[-2, 4]$ 与区间 $(-\infty, -1)$ 的公共部分是 $[-2, -1)$, 与区间 $(5, +\infty)$ 的公共部分为空集.

因此，所求的集合为 $[-2, -1)$.

例

某班级共 50 名学生，一次考试中有两道压轴题.答对第一题的有 30 人，答对第二题的有 28 人，两题都答对的有 15 人.问两题都未答对的学生有多少人？

解

设全集 $U$ 为该班级全体学生, 集合 $A$ 为答对第一题的学生构成的集合, 集合 $B$ 为答对第二题的学生构成的集合. 根据题意，我们有 <MathBlock raw={"\mathrm{card}(U) = 50, \mathrm{card}(A) = 30, \mathrm{card}(B) = 28, \mathrm{card}(A \cap B) = 15"} />

问题所求的是“两题都未答对”的学生人数. 一个学生两题都未答对，意味着该学生既不属于集合 $A$, 也不属于集合 $B$. 这在集合语言中表示为该学生属于 $(\complement_U A) \cap (\complement_U B)$. 因此，我们的目标是计算 $\mathrm{card}((\complement_U A) \cap (\complement_U B))$.

直接处理未答对的情况需要额外的信息，但我们可以通过德摩根定律转化视角. <MathBlock raw={"(\complement_U A) \cap (\complement_U B) = \complement_U(A \cup B)"} /> 此式表明，两题都未答对的学生集合，等价于“至少答对一题”的学生集合的补集.

因此，所求人数为 <MathBlock raw={"\mathrm{card}(\complement_U(A \cup B)) = \mathrm{card}(U) - \mathrm{card}(A \cup B)"} />

利用容斥原理，我们可以计算出至少答对一题的学生人数： <MathBlock raw={"\begin{aligned} \mathrm{card}(A \cup B) &= \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B) &= 30 + 28 - 15 &= 43 \end{aligned}"} />

最后，两题都未答对的学生人数为 <MathBlock raw={"50 - 43 = 7"} />

故共有 7 名学生两题都未答对.

例

设全集 $U=\mathbb{R}$, 集合 $A = \{x \mid x^2-9 \> 0\}$, $B = \{x \mid x^2-5x+4 \le 0\}$. 求集合 $(\complement_U A) \cup (\complement_U B)$.

解

该问题为我们提供了两种求解路径，我们可以根据集合的特点选择其一.

路径一：直接计算 首先分别计算两个集合的补集. 对于集合 $A$, 其补集 $\complement_U A$ 的元素满足 $x^2-9 \le 0$, 即 $-3 \le x \le 3$. 故 $\complement_U A = [-3, 3]$.

对于集合 $B$, 其补集 $\complement_U B$ 的元素满足 $x^2-5x+4 \> 0$. 即 $(x-1)(x-4) \> 0$, 解得 $x\<1$ 或 $x\>4$. 故 $\complement_U B = (-\infty, 1) \cup (4, +\infty)$.

然后计算它们的并集: <MathBlock raw={"(\complement_U A) \cup (\complement_U B) = [-3, 3] \cup (-\infty, 1) \cup (4, +\infty) = (-\infty, 3] \cup (4, +\infty)"} />

路径二：应用德摩根定律 德摩根定律指出，$(\complement_U A) \cup (\complement_U B) = \complement_U(A \cap B)$. 我们可以先计算交集 $A \cap B$, 然后再求其补集.

首先确定集合 $A$ 和 $B$. $A = \{x \mid x^2-9 \> 0\} = \{x \mid x \< -3 \text{ 或 } x \> 3\} = (-\infty, -3) \cup (3, +\infty)$. $B = \{x \mid x^2-5x+4 \le 0\} = \{x \mid (x-1)(x-4) \le 0\} = [1, 4]$.

接着计算它们的交集 $A \cap B$: <MathBlock raw={"A \cap B = \left( (-\infty, -3) \cup (3, +\infty) \right) \cap [1, 4] = (3, 4]"} />

最后，求此交集的补集: <MathBlock raw={"\complement_U(A \cap B) = \complement_U((3, 4]) = (-\infty, 3] \cup (4, +\infty)"} />

两种路径得到的结果完全一致.在实际解题中，我们可以根据 $A, B$ 与其补集的形式复杂程度，灵活选择使计算过程最为简便的路径.

有限集的计数

集合的基数

一个有限集合的元素个数称为该集合的基数，记为 $\mathrm{card}(A)$.

定理

若 $\mathrm{card}(A)=n$, 则 $A$ 的子集个数是 $2^n$.

证明

本定理可通过两种基本方法证明：组合论证与数学归纳法.我们在此呈现更具构造性的组合论证.

设有限集 $A = \{a_1, a_2, ..., a_n\}$.构造 $A$ 的一个任意子集 $S$ 的过程, 可以视为对 $A$ 中的每一个元素 $a_i$ 进行一次独立的决策.对于每一个元素 $a_i \in A$ ($i=1, 2, ..., n$)，仅存在两种互斥的可能性： <MathBlock raw={"a_i \in S \text{或} a_i \notin S"} /> 因此，一个特定的子集 $S$ 完全由这一系列共 $n$ 次的二元选择所唯一确定.我们可以将这一系列选择编码为一个长度为 $n$ 的二进制序列 $(b_1, b_2, ..., b_n)$，其中 <MathBlock raw={"b_i = \begin{cases} 1, & \text{若 } a_i \in S 0, & \text{若 } a_i \notin S \end{cases}"} /> 此构造建立了一个从 $A$ 的所有子集构成的集合 (即 $A$ 的幂集 $\mathcal{P}(A)$) 到所有长度为 $n$ 的二进制序列构成的集合之间的双射.

由于每一次选择都有 2 种可能，且这 $n$ 次选择是相互独立的，根据基本计数中的乘法原理，所有可能的选择序列的总数，即所有不同子集的总数，为 <MathBlock raw={"\underbrace{2 \times 2 \times ... \times 2}_{n \text{个}} = 2^n"} /> 故集合 $A$ 的子集个数为 $2^n$.

容斥原理

对于任意有限集合 $A, B, C$：

• $\mathrm{card}(A \cup B) = \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B)$.
• $\mathrm{card}(A \cup B \cup C) = (\mathrm{card}(A)+\mathrm{card}(B)+\mathrm{card}(C)) - (\mathrm{card}(A \cap B)+\mathrm{card}(A \cap C)+\mathrm{card}(B \cap C)) + \mathrm{card}(A \cap B \cap C)$.

证明

证明二元情形. 为精确计数并集 $A \cup B$ 中的元素, 我们可将其分解为互不相交的部分.集合 $A \cup B$ 可以被划分为三个不相交的集合的并： <MathBlock raw={"A \cup B = (A \setminus B) \cup (B \setminus A) \cup (A \cap B)"} /> 其中 $A \setminus B$ 表示仅属于 $A$ 而不属于 $B$ 的元素集合.由于这三个集合两两不交，并集的基数等于它们各自基数之和： <MathBlock raw={"\mathrm{card}(A \cup B) = \mathrm{card}(A \setminus B) + \mathrm{card}(B \setminus A) + \mathrm{card}(A \cap B)"} /> 同时，集合 $A$ 也可以被分解为两个不相交的部分：$A = (A \setminus B) \cup (A \cap B)$.由此可得 $\mathrm{card}(A) = \mathrm{card}(A \setminus B) + \mathrm{card}(A \cap B)$，这意味着 <MathBlock raw={"\mathrm{card}(A \setminus B) = \mathrm{card}(A) - \mathrm{card}(A \cap B)"} /> 同理，对于集合 $B$ 我们有 <MathBlock raw={"\mathrm{card}(B \setminus A) = \mathrm{card}(B) - \mathrm{card}(A \cap B)"} /> 将这两个表达式代入 $\mathrm{card}(A \cup B)$ 的分解式中，我们得到 <MathBlock raw={"\begin{aligned} \mathrm{card}(A \cup B) &= \left( \mathrm{card}(A) - \mathrm{card}(A \cap B) \right) + \left( \mathrm{card}(B) - \mathrm{card}(A \cap B) \right) + \mathrm{card}(A \cap B) &= \mathrm{card}(A) + \mathrm{card}(B) - \mathrm{card}(A \cap B) \end{aligned}"} /> 二元情形证毕.

证明三元情形. 我们可以巧妙地将三元问题转化为二元问题的迭代应用.令 $D = B \cup C$, 于是 $A \cup B \cup C$ 可以视作 $A \cup D$.应用已证的二元容斥原理，我们有 <MathBlock raw={"\mathrm{card}(A \cup B \cup C) = \mathrm{card}(A \cup D) = \mathrm{card}(A) + \mathrm{card}(D) - \mathrm{card}(A \cap D)"} /> 现在，我们分别处理 $\mathrm{card}(D)$ 和 $\mathrm{card}(A \cap D)$.

对于 $\mathrm{card}(D)$，我们再次应用二元容斥原理： <MathBlock raw={"\mathrm{card}(D) = \mathrm{card}(B \cup C) = \mathrm{card}(B) + \mathrm{card}(C) - \mathrm{card}(B \cap C)"} />

对于 $\mathrm{card}(A \cap D)$，我们首先利用集合的分配律： <MathBlock raw={"A \cap D = A \cap (B \cup C) = (A \cap B) \cup (A \cap C)"} /> 对其基数应用二元容斥原理，得到 <MathBlock raw={"\begin{aligned} \mathrm{card}(A \cap D) &= \mathrm{card}((A \cap B) \cup (A \cap C)) &= \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}((A \cap B) \cap (A \cap C)) &= \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}(A \cap B \cap C) \end{aligned}"} />

最后，将 $\mathrm{card}(D)$ 和 $\mathrm{card}(A \cap D)$ 的展开式代回最初的表达式中： <MathBlock raw={"\begin{aligned} \mathrm{card}(A \cup B \cup C) &= \mathrm{card}(A) + \left( \mathrm{card}(B) + \mathrm{card}(C) - \mathrm{card}(B \cap C) \right) & - \left( \mathrm{card}(A \cap B) + \mathrm{card}(A \cap C) - \mathrm{card}(A \cap B \cap C) \right) \end{aligned}"} /> 整理各项，即可得到三元容斥原理的最终形式： <MathBlock raw={"\mathrm{card}(A \cup B \cup C) = \sum_{\text{cyc}} \mathrm{card}(A) - \sum_{\text{cyc}} \mathrm{card}(A \cap B) + \mathrm{card}(A \cap B \cap C)"} /> 此即为所证.

映射

{/* label: sec:ch02-s02 */}

映射的概念

我们已经熟悉了函数，它建立了数集之间的一种对应关系. 例如，$f(x) = x^2$ 将每个实数 $x$ 与其平方 $x^2$ 对应起来. 几何变换，如平面上的旋转，将每个点与旋转后的新点对应起来. 这些多样化的“对应关系”背后，蕴含着一个更为深刻和普适的数学结构，即映射.

映射

设 $A, B$ 是两个非空集合. 如果存在一个法则 $f$, 使得对 $A$ 中的每一个元素 $x$, 在 $B$ 中都有唯一确定的元素 $y$ 与之对应, 则称 $f$ 为从 $A$ 到 $B$ 的一个映射，记作 <MathBlock raw={"f: A \to B"} /> 其中，集合 $A$ 称为映射 $f$ 的定义域. 集合 $B$ 称为映射 $f$ 的陪域.

这个定义包含了三个核心要素：定义域 $A$、陪域 $B$ 以及对应法则 $f$. 它同时对法则 $f$ 施加了两个根本性的约束：

• 全域性: 定义域 $A$ 中的每一个元素都必须有像，不允许有“遗漏”.
• 单值性: 任意一个元素的像必须是唯一的，不允许“一对多”.

对于 $x \in A$, 我们称其在 $B$ 中对应的元素 $y$ 为 $x$ 在映射 $f$ 下的像, 记作 $y=f(x)$. 反之, 称 $x$ 为 $y$ 的一个原像. 定义域 $A$ 中所有元素的像所构成的集合称为映射 $f$ 的像集或值域, 记作 $f(A)$: <MathBlock raw={"f(A) = \{f(x) \mid x \in A\}"} /> 务必注意到，像集 $f(A)$ 是陪域 $B$ 的一个子集, 即 $f(A) \subseteq B$. 陪域是像的“目标靶”，而像集是实际上“射中”的区域.

\begin{figure}[htbp]

TikZ 图 13

{A} 中每个元素都有唯一一个箭头指出, 指向其在陪域 \texorpdfstring{$B$}{B} 中的像. 陪域 \texorpdfstring{$B$}{B} 中并非所有元素都是像 (如 \texorpdfstring{$b_2, b_4$}{b2, b4}). 一个元素可以有多个原像 (如 \texorpdfstring{$b_3$}{b3} 的 原像 是 \texorpdfstring{$a_2$}{a2} 和 \texorpdfstring{$a_3$}{a3}).} \end{figure} 图：映射的图示. 定义域 \texorpdfstring{$A$

例

考察函数 $f(x)=x^2$. 将其视为映射，分析其定义域、陪域和像集对映射性质的影响.

解

映射的性质不仅取决于对应法则，更由其定义域与陪域共同决定.

1. 考虑 $f_1: \mathbb{R} \to \mathbb{R}$, 其中 $f_1(x)=x^2$. 这是从实数集到其自身的映射. 定义域为 $\mathbb{R}$, 陪域也为 $\mathbb{R}$. 像集为 $f_1(\mathbb{R}) = [0, +\infty)$. 注意到，像集是陪域的一个真子集.
2. 考虑 $f_2: \mathbb{R} \to [0, +\infty)$, 其中 $f_2(x)=x^2$. 此映射的对应法则与 $f_1$ 相同，但陪域被显式地限制为所有非负实数. 定义域为 $\mathbb{R}$, 陪域为 $[0, +\infty)$. 像集为 $f_2(\mathbb{R}) = [0, +\infty)$. 在此情形下，像集与陪域恰好相等.
3. 考虑 $f_3: [0, +\infty) \to [0, +\infty)$, 其中 $f_3(x)=x^2$. 此映射将定义域也限制为非负实数. 定义域为 $[0, +\infty)$, 陪域为 $[0, +\infty)$. 像集为 $f_3([0, +\infty)) = [0, +\infty)$.
4. 考虑 $f_4: \mathbb{R} \to (-\infty, -1)$, 其中 $f_4(x)=x^2$. 这个定义是不合法的. 因为对于任意 $x \in \mathbb{R}$, 其像 $x^2 \ge 0$, 并不属于陪域 $(-\infty, -1)$.

这个例子清晰地表明，一个映射由其定义域、陪域和对应法则三者共同唯一确定. 任何一个要素的改变，都将产生一个本质上不同的新映射.

特殊映射：单射、满射与双射

根据像与原像的对应关系，我们可以将映射作进一步的精细分类.

单射、满射、双射

设 $f: A \to B$ 为一个映射.

• 如果对于定义域 $A$ 中任意两个不同的元素，它们的像也互不相同，即 <MathBlock raw={"\forall x_1, x_2 \in A, x_1 \neq x_2 \implies f(x_1) \neq f(x_2)"} /> 则称 $f$ 为单射或一对一映射.
• 如果陪域 $B$ 中的每一个元素都至少有一个原像, 即像集等于陪域 ($f(A)=B$)，即 <MathBlock raw={"\forall y \in B, \exists x \in A, \text{使得 } f(x)=y"} /> 则称 $f$ 为满射或映上映射.
• 如果映射 $f$ 既是单射又是满射, 则称 $f$ 为双射或一一对应.

单射保证了信息的无损压缩，因为不同的输入必有不同的输出. 满射保证了陪域中没有“冗余”的元素，每个目标都被“击中”. 双射则在两个集合之间建立了一个完美的、可逆的对应关系，它意味着两个集合在某种意义下具有相同的“大小”或“结构”.

例

回到 $f(x)=x^2$ 的例子, 判断 $f_1, f_2, f_3$ 分别是何种映射.

解

1. $f_1: \mathbb{R} \to \mathbb{R}$. 它不是单射，因为存在反例，如 $f_1(-2) = 4 = f_1(2)$, 但 $-2 \neq 2$. 它不是满射，因为像集 $[0, +\infty) \neq \mathbb{R}$, 例如陪域中的元素 $-1$ 没有任何原像.

2. $f_2: \mathbb{R} \to [0, +\infty)$. 它依然不是单射 (理由同上). 但它是满射，因为陪域中的任意元素 $y \in [0, +\infty)$ 都有原像 (即 $\sqrt{y}$ 和 $-\sqrt{y}$).

3. $f_3: [0, +\infty) \to [0, +\infty)$. 它是单射. 我们可以用其等价的逆否命题来证明：若 $f_3(x_1) = f_3(x_2)$, 即 $x_1^2 = x_2^2$, 由于 $x_1, x_2$ 均非负, 必然有 $x_1 = x_2$. 它也是满射，因为陪域中的任意元素 $y \in [0, +\infty)$ 都有唯一的原像 $\sqrt{y}$ 在定义域中.

   因此，$f_3$ 是一个双射. 这也解释了为何平方根函数 $\sqrt{x}$ 通常只定义在非负实数域上.

逻辑用语初步

{/* label: sec:ch02-s03 */}

数学的宏伟大厦建立在严密推理的基石之上. 为了保证推理的无懈可击，我们必须使用一种精确的、无歧义的语言——这就是逻辑用语.

命题及其真值

命题

在数学中，我们把能判断真假的陈述句称为命题.

一个命题的判断结果称为其真值，真值只有“真”和“假”两种.

例如，“$3 \> 2$”是一个真命题, “所有素数都是奇数”是一个假命题 (因为2是偶素数). 而“$x \> 5$”则不是一个命题, 因为在 $x$ 的值未确定前，我们无法判断其真假. 这种含有变量的陈述句称为谓词或开命题.

逻辑联结词与集合运算

简单的命题可以通过逻辑联结词组合成更复杂的复合命题. 逻辑联结词与集合运算之间存在深刻的对偶关系.

基本逻辑联结词

设 $p, q$ 为两个命题.

• 否定 ($\neg p$, 读作“非 $p$”): 若 $p$ 为真, 则 $\neg p$ 为假；若 $p$ 为假, 则 $\neg p$ 为真. 这对应于集合的补集运算. 如果 $P$ 是使 $p$ 为真的所有情况构成的集合, 则 $\complement_U P$ 就是使 $\neg p$ 为真的情况构成的集合.
• 合取 ($p \land q$, 读作“$p$ 且 $q$”): 仅当 $p$ 和 $q$ 同时为真时, $p \land q$ 才为真. 这对应于集合的交集运算 $P \cap Q$.
• 析取 ($p \lor q$, 读作“$p$ 或 $q$”): 仅当 $p$ 和 $q$ 同时为假时, $p \lor q$ 才为假. 这是包容性的或. 这对应于集合的并集运算 $P \cup Q$.

\begin{figure}[htbp]

TikZ 图 14

\end{figure} 图：逻辑联结词与集合运算的直观对应关系

蕴含关系与充要条件

数学推理的核心是条件命题.

蕴含命题

形如“若 $p$, 则 $q$”的命题称为蕴含命题, 记作 $p \implies q$. $p$ 称为命题的前提或条件, $q$ 称为命题的结论. 蕴含命题 $p \implies q$ 的真值规定为：仅在 $p$ 为真且 $q$ 为假时为假，其余情况均为真.

蕴含关系在集合论中的对应是子集关系. 命题 $p \implies q$ 为真, 等价于使 $p$ 为真的情况集合 $P$ 是使 $q$ 为真的情况集合 $Q$ 的子集, 即 $P \subseteq Q$. 这个观点对于理解蕴含关系至关重要.

• 若前提 $p$ 为假 (即 $x \notin P$), 则 $x$ 是否在 $Q$ 中与蕴含关系 $P \subseteq Q$ 的真假无关. 这就是为何前提为假时，蕴含命题恒为真（称为空虚的真）.

对于一个蕴含命题 $p \implies q$，我们还可以构造出它的三个关联命题：

• 逆命题: $q \implies p$.
• 否命题: $\neg p \implies \neg q$.
• 逆否命题: $\neg q \implies \neg p$.

定理

一个蕴含命题与其逆否命题是逻辑等价的，即它们具有相同的真值. <MathBlock raw={"(p \implies q) \iff (\neg q \implies \neg p)"} /> 其逆命题与否命题逻辑等价.

证明

我们从集合论的观点来证明. $p \implies q$ 为真, 等价于 $P \subseteq Q$. $\neg q \implies \neg p$ 为真, 等价于 $\complement_U Q \subseteq \complement_U P$. 在集合论中，$P \subseteq Q$ 与 $\complement_U Q \subseteq \complement_U P$ 是完全等价的两个论断. 从Venn图上可以直观地看出, 若区域 $P$ 完全被区域 $Q$ 包含, 那么 $Q$ 之外的区域也必然完全被 $P$ 之外的区域包含.

此定理是反证法的逻辑基础. 要证明 $p \implies q$, 有时直接从 $p$ 出发很困难, 我们可以转而证明其逆否命题：从 $\neg q$ 出发, 推导出 $\neg p$.

当 $p \implies q$ 成立时, 我们称 $p$ 是 $q$ 的充分条件, $q$ 是 $p$ 的必要条件.

• $p$ 的发生足以保证 $q$ 的发生.
• $q$ 的发生是 $p$ 发生的必要前提.

如果 $p \implies q$ 与 $q \implies p$ 同时成立 (记作 $p \iff q$), 则称 $p$ 是 $q$ 的充分必要条件 (或充要条件). 这在集合论中对应于 $P=Q$.

量词及其否定

为了将谓词转化为命题，我们需要引入量词.

量词

• 全称量词 $\forall$，读作“对任意”或“所有”. 命题 $\forall x \in M, p(x)$ 为真, 当且仅当对于集合 $M$ 中的每一个元素 $x$, $p(x)$ 都成立.
• 存在量词 $\exists$，读作“存在”或“有些”. 命题 $\exists x \in M, p(x)$ 为真, 当且仅当在集合 $M$ 中至少存在一个元素 $x_0$, 使得 $p(x_0)$ 成立.

在进行数学证明和反驳时，对量词命题进行正确的否定至关重要.

量词的否定

<MathBlock raw={"\begin{aligned} \neg (\forall x \in M, p(x)) &\iff \exists x \in M, \neg p(x) \neg (\exists x \in M, p(x)) &\iff \forall x \in M, \neg p(x) \end{aligned}"} />

证明

其逻辑是直观的. 要否定“所有 $x$ 都满足 $p(x)$”, 我们只需要找到一个反例, 即“存在一个 $x$ 不满足 $p(x)$”. 要否定“存在一个 $x$ 满足 $p(x)$”, 我们必须证明没有任何一个 $x$ 满足 $p(x)$, 即“所有 $x$ 都不满足 $p(x)$”.

例

写出命题“所有正方形的对角线都互相垂直”的否定.

解

设 $S$ 为所有正方形的集合, $p(x)$ 表示命题“$x$ 的对角线互相垂直”. 原命题可符号化为： $\forall x \in S, p(x)$.

根据量词的否定规则，其否定为 $\exists x \in S, \neg p(x)$. 翻译回自然语言即：“存在一个正方形，它的对角线不互相垂直”.

由于原命题为真，其否定命题必为假.