# 集合

定义
将满足特定条件的对象的全体称为 集合 (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 \in \mathbb N \mid x \text{ is even and } 1 \leq x \leq 10\}$

示例

$\mathbb R = \{x \mid x \text{ is Real}\}$
$\mathbb N = \{x \mid x \in \mathbb Z \text{ and } 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$ 。
集合 $X$ 的所有子集所构成的集合称为 $X$ 的 幂集 (Power Set)「冪集合」，记作 $\mathcal{P}(X)$ 或 $\mathfrak{P}(X)$ 。这是一个非常常见的二级集合结构

示例

\mathcal{P}(\emptyset) = \
$\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

显然，

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

这一点在证明中非常重要且常见
类似 $P \iff Q$ 格式的证明中，一般来说主要的证明结构为

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

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

# 集合运算

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

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

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

示例

\{1, 2\} \cup \{2, 3, 4\} = \
\{1, 2\} \cap \{2, 3, 4\} = \
$\{1, 2\} \cap \{3, 4\} = \emptyset$
\{1, 2, 3, 4\} \setminus \{2, 4\} = \

命题 分配律
令 $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)
$(\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$ 。

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

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

命题 结合律
令 $A, B, C$ 为集合，则：

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

证明

(1)
$(\subset)$
令 $x \in (A \cup B) \cup C$ ，则 $x \in A \cup B$ 或 $x \in C$ 。
若 $x \in A \cup B$ ，则 $x \in A$ 或 $x \in B$ ，故 $x \in A \cup (B \cup C)$ ；
若 $x \in C$ ，则 $x \in B \cup C$ ，故 $x \in A \cup (B \cup C)$ 。

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

(2)
$(\subset)$
令 $x \in (A \cap B) \cap C$ ，则 $x \in A \cap B$ 且 $x \in C$ 。
由 $x \in A \cap B$ 可知 $x \in A$ 且 $x \in B$ ，故 $x \in A \cap (B \cap C)$ 。

$(\supset)$
令 $x \in A \cap (B \cap C)$ ，则 $x \in A$ 且 $x \in B \cap C$ 。
由 $x \in B \cap C$ 可知 $x \in B$ 且 $x \in C$ ，故 $x \in (A \cap B) \cap C$ 。
$\square$

定理 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{ or } x \in B) \\ &\iff x \not\in A \text{ and } x \not\in B \\ &\iff x \in A^c \text{ and } x \in B^c \\ &\iff x \in A^c \cap B^c \end{aligned}$

(2)

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

$\square$

命题 补集包含关系
令 $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)$
这样有顺序的组合（交换位置会改变意义）称为 有序对 (Ordered Pair)「順序対」。

定义
令 $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}}$

空集在直积运算中具有吸收律

$X \times \emptyset = \emptyset \times X = \emptyset$

示例

$\{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 个成分。
两个有序组必须在所有成分都相等的情况下，才相等。

示例

称 $\mathbb R^n$ 为 n 维实数空间
称 $\mathbb C^n$ 为 n 维复数空间

通常来说，对于类似 $\mathbb R^n$ 或 $\mathbb C^n$ 这样的空间中的元，有序组的表示方式依据定义应该是横向，但是从线性代数中矩阵乘法的角度考虑时，由于让行列从左侧乘以该元会更容易分析，所以一般写为

$\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in \mathbb R^n$

这在同构意义下是等价的，但在运算层面上存在列向量与行向量的区别

内容已经过 Gemini 3.0 Pro 审查

# 集合

# 集合运算

# 直积

LaTex 符号对照

【线性代数】2-简化阶梯形