基本概念补漏

1 集合

对于任意两个集合 $A$ 、 $B$ ，可以组成一个新的集合。
注意无序对 $\{A,B\}=\{B,A\}$ ，而在 $A\neq B$ 时它恰好包含两个元素。

有序对（序偶）的集合称为直积（笛卡尔积）：

X \times Y := \bigl\{ (x,y) \bigm| x\in X,\ y\in Y \bigr\}

一般而言，

X \times Y \ \ne\ Y \times X

当 $X=Y$ 时，常记作 $X^2$ 。

设序偶 $z = (x_1, x_2)$ 是 $X_1 \times X_2$ 的元素，则 $x_1$ 、 $x_2$ 分别称为 $z$ 的第一投影和第二投影，记作：

\Pr_1(z),\quad \Pr_2(z) \quad \text{或有时写作}\quad \pi_1(z),\ \pi_2(z)

对于集合 $X$ 的任意子集 $A\subseteq X$ ，其特征函数（示性函数） $\chi_A : X \to \{0,1\}$ 定义为：

\chi_A(x) = \begin{cases} 1 & \text{若 } x \in A \\ 0 & \text{若 } x \notin A \end{cases}

若存在双射 $f:X\to Y$ ，则称 $X$ 与 $Y$ 等势，记作

X \sim Y \quad \text{或}\quad |X| = |Y|

等势关系是等价关系，它将所有集合划分为等势类，同一类中任意两个集合的基数（势、cardinality）相等，记作 $\operatorname{card} X$ 或 $|X|$ 。

由此可定义不大于关系：

\operatorname{card} X \leqslant \operatorname{card} Y \quad :\Longleftrightarrow\quad \exists Z\subseteq Y\ \text{使得}\ |X| = |Z|

若同时 $|X|\neq |Y|$ ，则称严格小于：

\operatorname{card} X < \operatorname{card} Y

对于任何集合 $X$ ，都有严格的不等式（康托尔定理）：

\operatorname{card} X < \operatorname{card} \mathcal{P}(X)

其中 $\mathcal{P}(X)$ 是 $X$ 的幂集（一切子集组成的集合）。这说明无穷集合的“大小”可以有无穷多种不同的级别。

通常将函数记为三元组 $(X, f, Y)$ ，其中：

$x\in X$ 对应的唯一元素 $f(x)$ 称为 $x$ 的像（image）。

常用术语：

g \circ f = \mathrm{id}_X \quad \Longrightarrow\quad \left\{ \begin{array}{l} f\ \text{是单射} \\ g\ \text{是满射} \end{array} \right.

（类似地， $f\circ g = \mathrm{id}_Y$ 则 $f$ 满射、 $g$ 单射）

任意序偶集合 $\mathcal{R}\subseteq X\times Y$ 都称为一个关系。

定义域： $\operatorname{dom}(\mathcal{R}) = \{x \mid \exists y,\ (x,y)\in\mathcal{R}\}$
值域（像集）： $\operatorname{ran}(\mathcal{R}) = \{y \mid \exists x,\ (x,y)\in\mathcal{R}\}$

若关系 $\mathcal{R}$ 满足单值性（函数性）：

(x,y_1)\in\mathcal{R} \ \wedge\ (x,y_2)\in\mathcal{R} \ \Longrightarrow\ y_1 = y_2

则称 $\mathcal{R}$ 是一个函数关系。

此时我们说 $\mathcal{R}$ 是从 $X$ 到 $Y$ 的函数，其图像就是集合 $\mathcal{R}$ 本身：

f\ :=\ \mathcal{R}\ \subseteq\ X \times Y

而 $X$ 常称为出发域， $Y$ 称为到达域（不必等于值域 $\operatorname{ran}(f)$ ）。

常用记号： $(x,y)\in f$ 写作 $x\ f\ y$ 或 $f(x)=y$ 。