映射

集合论中，映射（map）是函数概念的推广，它描述了两个集合之间的关系，如果这两个集合是同一个，那么映射也称作变换（transformation）。

概念

设两个非空集合$A$和$B$，若存在一个对应关系$f$，使得对每个$A$中的元素$x \in A$，在$B$中都有唯一一个元素$y \in B$和它对应，我们称$f$是$A$到$B$的一个映射，记作

$$\begin{align} f: A & \to B \\ x & \mapsto y = f(x) \end{align}$$

第一个式子表示该映射$f$是从$A$到$B$的，第二个表明了$f$的对应关系。

• 上式中$y=f(x)$称为$x$对应的像（image），$x$称为$y$的原像（inverse image）；
• $A$称为$f$的定义域（domain of f）或原像集，也记作$D(f)$;
• $B$称作$f$的值域、到达域（codomain of f）或变程，记作$R(f)$；
• $f(A) = \{ y | y = f(x), x \in A \}$称为$A$在$f$下的像集（image set），也记作$\operatorname{Im} f$；
• 给定一$y \in B$，符合等式$y=f(x)$的所有$x \in A$称作$y$在$f$下的完全原像，记作$f^{-1}(y)$。

一般来说，像集和值域并不相等，$f(A) \subseteq B$，如果$f$是满射时那这两者是相等的。某个特定的$y \in B$的完全原像可能并不是唯一的，甚至可能没有。

我们说两个映射$f: A \to B, g: A \to B$是相等的，是指$\forall x \in A, f(x) = g(x).$

将集合$A$中的元素映作自身的变换称作恒等变换（映射），记作$i, i_A.$

单射与满射

单射

若$\forall x_1, x_2 \in A, x_1 \ne x_2$均有$f(x_1) \ne f(x_2)$，则称$f$是一个单射（injection）或 1-1 的映射。

上述定义等价于：$\forall y \in B, |f^{-1} (y)| \leqslant 1.$该式中$f^{-1}(y)$是一个集合，$|f^{-1} (y)|$为该集合的元素，这表明对任意的$y \in B$的完全原像的元素数量不多于一个。

满射

若$\forall y \in B, \exists x \in A$，使得$y=f(x)$，则称$f$是一个满射（surjection）或到上的映射。

上述定义等价于$f(A) = B.$也等价于$\forall y \in B, |f^{-1}(b)| \leqslant 1.$

双射

若$f$既是单射又是满射，就称$f$是一个双射（bijection），或一一对应。

像与原像的子集

假设$f: X \to Y$且有两族集合$\{ A_i \}_{i \in I} \subset X, \{ B_j \}_{j \in J} \in Y$，那么有

1. $f\left( \bigcup_{i \in I} A_i \right) = \bigcup_{i \in I} f(A_i).$
2. $f\left( \bigcap_{i \in I} A_i \right) \subset \bigcap_{i \in I} f(A_i).$当$f$为单射时相等。
3. $f^{-1} \left( \bigcup_{j \in J} B_j \right) = \bigcup_{j \in J} f^{-1} (B_j).$
4. $f^{-1} \left( \bigcap_{j \in J} B_j \right) = \bigcap_{j \in J} f^{-1} (B_j).$
5. $f^{-1} (B^c) = (f^{-1}(B))^c.$
6. $f^{-1} (B_1 \setminus B_2) = f^{-1}(B_1) \setminus f^{-1}(B_2).$
7. $f(f^{-1}(B)) \subset B.$当$f$为满射时相等。
8. $f^{-1}(f(A)) \supset A.$当$f$为单射时相等。

映射的复合

设$f: A \to B, g: b \to C$，那么以下这个新映射

$$\begin{align} h: A & \to C \\ x & \mapsto z = g(f(x)) \end{align}$$

就称作$f$和$g$的复合，记作$h = g \circ f$。

该运算满足结合律，即$h\circ(g\circ f) = (h\circ g)\circ f$，但是一般不满足交换律，即一般$f \circ g \ne g \circ f.$

假设同上，若$h$是一单射，则$f$也是一单射；若$h$是一满射，则$g$也是一满射。

显然恒等映射$i$和任意映射$f:A \to B$可交换$f \circ i_A = i_B \circ f.$这种交换是不指定恒等映射的种类下的。

可逆映射

借助复合映射，我们可以得到如下单射和满射的等价命题

1. $f:A \to B$是单射，当且仅当存在$g:B \to A$，使得$g \circ f = i_A$，这时我们称$g$是$f$的右逆映射；
2. $f:A \to B$是满射，当且仅当存在$g:B \to A$，使得$f \circ g = i_B$，这是我们称$g$是$f$的左逆映射；
3. $f:A \to B$是双射，当且仅当存在$g:B \to A$，使得$g \circ f = i_A, f \circ g = i_B$，这是我们称$g$是$f$的逆映射。

由上述第三款定义的逆映射当且仅当$f$是双射时存在，且他和$f$可交换，我们也将逆映射记作$f^{-1}$。

以下这个定理揭示了复合映射的逆的结构问题：
设$f: A \to B, g: B \to A, h = g \circ f$，若$f, g$都是双射，那么$h$也是双射，且

$$h^{-1} = f^{-1} \circ g^{-1}.$$

变换

如果映射$f:A \to A$，那么映射$f$也称作$A$上的变换。

当$A = \{ x_1, x_2, \cdots \}$的元素有限（至多可列个）时，可以用下列数表来表示该映射的值

$$f = \begin{pmatrix} x_1 & x_2 & \cdots & x_n & \cdots \\ f(x_1) & f(x_2) & \cdots & f(x_n) & \cdots \\ \end{pmatrix}$$

例如，对于一个自然数集的子集$A = \{1,2,\cdots,n\}$的一个$n$级排列$i_1 i_2 \cdots i_n$（它是由$f:A \to A$定义的一个双射）可以表示为

$$f = \begin{pmatrix} 1 & 2 & \cdots & n \\ i_1 & i_2 & \cdots & i_n \\ \end{pmatrix}$$

这样的一个变换称为一个$n$次置换（permutation of degree n）。