映射

集合論中，映射（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）。