前置知识

1. 集合的基本运算

设 $A, B$ 是全集 $X$ 的子集。

$$A\cup B=\{x:x\in A\text{ 或 }x\in B\},$$

$$A\cap B=\{x:x\in A\text{ 且 }x\in B\},$$

$$A\setminus B=\{x:x\in A\text{ 且 }x\notin B\},$$

$$A^c=X\setminus A.$$

两个集合相等的含义是它们包含完全相同的元素：

$$A=B \iff \forall x,\quad (x\in A\iff x\in B).$$

因此，证明两个集合相等通常分为两步：

$$A\subseteq B, \qquad B\subseteq A.$$

1.1 德摩根律

$$(A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c.$$

2. 映射

设

$$f:A\to B$$

要求每个 $x\in A$ 都有唯一确定的 $f(x)\in B$ 与之对应。

• $A$ 称为定义域。
• $B$ 称为陪域。
• $f(x)$ 称为 $x$ 的像。
• 若 $f(x)=y$，则 $x$ 称为 $y$ 的一个原像。

「唯一确定」意味着一个输入不能同时对应两个不同输出。但不同输入可以得到同一个输出。

2.1 单射

如果

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2,$$

则称 $f$ 为单射。

等价地，

$$x_1\ne x_2\Longrightarrow f(x_1)\ne f(x_2).$$

例如

$$f:\mathbb Z^+\to\mathbb Z^+,\qquad f(n)=2n$$

是单射，但不是满射，因为奇数没有原像。

2.2 满射

如果

$$\forall y\in B,\quad \exists x\in A,\quad f(x)=y,$$

则称 $f$ 为满射。

2.3 双射

既是单射又是满射的映射称为双射。此时：

• 每个输入恰好对应一个输出，
• 每个输出也恰好对应一个输入。

因此，双射建立了两个集合之间真正的「一一配对」。只有双射才存在逆映射。

3. 笛卡尔积

设 $A$、$B$ 是两个集合，它们的笛卡尔积定义为

$$A\times B=\{(a,b):a\in A,\ b\in B\}.$$

这里的 $\times$ 不是普通乘法，而表示「从每个集合中各选一个元素，并按顺序组合起来」。

例如，

$$A=\{1,2\},\qquad B=\{a,b\},$$

则

$$A\times B=\{(1,a),(1,b),(2,a),(2,b)\}.$$

顺序是有意义的，一般来说

$$(a,b)\ne(b,a).$$