# 集合

定义
将满足特定条件的对象的全体称为 集合 (Set)「集合」，构成集合的每一个对象称为该集合的 元 (Element)「元」。

若 $a$ 是集合 $A$ 的元，记作 $a \in A$ ；若 $a$ 不是集合 $A$ 的元，记作 $a \not\in A$ 。
若两个集合 $A, B$ 由完全相同的元构成，则称它们相等，记作 $A = B$ 。

示例
常用的数集符号：

$\mathbb N$ ：全体自然数集合（注：今后取 $0 \not\in \mathbb N$ ）
$\mathbb Z$ ：全体整数集合
$\mathbb Q$ ：全体有理数集合
$\mathbb R$ ：全体实数集合
$\mathbb C$ ：全体复数集合

通常来说集合有两种表示方法

列举法：直接列举出集合的所有元，例如 $A = \{1, 2, 3\} \quad$
描述法：通过描述集合元所满足的性质来表示集合，例如 $B = \{x \mid x \text{ 是偶数且 } 1 \leq x \leq 10\}$

示例

$\mathbb R = \{x \mid x \text{ 是实数}\}$
$\mathbb N = \{x \mid x \in \mathbb Z \text{ 且 } x \geq 1\}$

令 $A, B$ 为集合。
若 $A$ 的所有元都属于 $B$ ，则称 $A$ 为 $B$ 的 子集 (Subset)「部分集合」，或称 $A$ 包含于 $B$ ，记作 $A \subset B$ 。

若 $A \subset B$ 且 $A \neq B$ ，则称 $A$ 为 $B$ 的 真子集 (Proper Subset)「真部分集合」，记作 $A \subsetneq B$ 。

显然，

$A = B \iff A \subset B \text{ 且 } A \supset B$

这一点在证明中非常重要且常见

不含任何元素的集合称为 空集 (Empty Set)「空集合」，记作 $\emptyset$ 。规定空集是任何集合的子集。

# 集合运算

主要有以下四种基础的，以集合为对象的运算

令 $A, B$ 为集合。给定一个集合 $U$ 作为全集（即包含所有讨论对象的集合）

并集 (Union)「和集合」： $A \cup B = \{x \mid x \in A \text{ 或 } x \in B\}$
交集 (Intersection)「共通部分」： $A \cap B = \{x \mid x \in A \text{ 且 } x \in B\}$
差集 (Set Difference)「差集合」： $A \setminus B = \{x \mid x \in A \text{ 且 } x \not\in B\}$
补集 (Complement)「補集合」： $A^c = U \setminus A = \{x \mid x \not\in A\} \quad$

定理 分配律
令 $A, B, C$ 为集合，则：

$(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
$(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$

证明

仅证明 (1)，(2) 同理可得。
$(\subset)$
令 $x \in (A \cup B) \cap C$ ，则 $x \in C$ 且 ( $x \in A$ 或 $x \in B$ )。
若 $x \in A$ ，则 $x \in A \cap C$ ；若 $x \in B$ ，则 $x \in B \cap C$ 。
故 $x \in (A \cap C) \cup (B \cap C)$ 。

$(\supset)$
令 $x \in (A \cap C) \cup (B \cap C)$ 。
若 $x \in A \cap C$ ，则 $x \in A \subset A \cup B$ 且 $x \in C$ ；
若 $x \in B \cap C$ ，则 $x \in B \subset A \cup B$ 且 $x \in C$ 。
故 $x \in (A \cup B) \cap C$ 。

定理 结合律
令 $A, B, C$ 为集合，则：

$(A \cup B) \cup C = A \cup (B \cup C)$
$(A \cap B) \cap C = A \cap (B \cap C)$

证明

容易验证，暂时省略

定理 De Morgan 定律
令 $A, B$ 为全集 $X$ 的子集，则：

$(A \cup B)^c = A^c \cap B^c$
$(A \cap B)^c = A^c \cup B^c$

证明

仅证明 (1)。

$\begin{aligned} x \in (A \cup B)^c &\iff x \not\in A \cup B \\ &\iff \neg (x \in A \text{ 或 } x \in B) \\ &\iff x \not\in A \text{ 且 } x \not\in B \\ &\iff x \in A^c \text{ 且 } x \in B^c \\ &\iff x \in A^c \cap B^c \end{aligned}$

另一个关于补集的计算性质
以下类似 $P \iff Q$ 格式的证明中，一般来说主要的证明结构为

假设 $P$ 成立，证明 $Q$ 成立
假设 $Q$ 成立，证明 $P$ 成立

定理
令 $A, B$ 为全集 $X$ 的子集，则：

$A \subset B \iff B^c \subset A^c$

证明

( $\Rightarrow$ )
假设 $A \subset B$ ，令 $x \in B^c$ ，则 $x \not\in B$ 。
由 $A \subset B$ 可知 $x \not\in A$ ，故 $x \in A^c$ 。
因此 $B^c \subset A^c$ 。
( $\Leftarrow$ )
假设 $B^c \subset A^c$ ，令 $x \in A$ ，则 $x \not\in A^c$ 。
由 $B^c \subset A^c$ 可知 $x \not\in B^c$ ，故 $x \in B$ 。
因此 $A \subset B$ 。
$\square$

# 直积

类似平面上的点的坐标 $(x, y)$
这样有顺序的组合（交换位置会改变意义）称为有序对

定义
令 $X, Y$ 为集合。
称

$X \times Y = \{(x, y) \mid x \in X, y \in Y\}$

为 $X$ 与 $Y$ 的 直积 (Direct Product)「直積」。

直积即为两个集合中元的所有可能有序组合所构成的集合。

一般地，对于 $n$ 个集合 $X_1, \dots, X_n$ ，其直积定义为：

$X_1 \times \cdots \times X_n = \{(x_1, \dots, x_n) \mid x_i \in X_i, i=1,\dots,n\}$

也常常用幂来简单的表示直积

$X^n = \underbrace{X \times X \times \cdots \times X}_{n \text{ times}}$

示例

$\{1, 2\} \times \{a, b, c\} = \{(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\} \quad$
$[a, b] \times [c, d] = \{(x, y) \mid a \leq x \leq b,\ c \leq y \leq d\}$ ，即平面上的矩形区域

直积运算可以保持包含关系，即

$A \subset X, B \subset Y \implies A \times B \subset X \times Y$

除了两个元素组成的有序对，一般对于 $3$ 个或更多元素，称 $(x_1, x_2, \ldots, x_n)$ 为有序 n 元组。

称有序组的第 $i$ 个元素为该有序组的第 i 个成分。
两个有序组必须在所有成分都相等的情况下，才相等。

# 集合

# 集合运算

# 直积

数学笔记目录

【集合论】映射