子节 A.2 映射
集合可以帮我们划定讨论问题的范围，即哪些元素是我们需要关心的。划定讨论问题的范围后，这些我们关心的元素之间的关系则可以用映射来进行描述。
定义 A.2.12.
设\(S\)、\(T\)是非空集合, 用\(\phi\)表示一个\(S\)中元素与\(T\)中元素的对应关系（也称对应法则）。若对\(\forall s\in S\)，有且只有\(T\)中唯一元素\(t\)与之对应，则称\(\phi\)是\(S\)到\(T\)的映射，记为
\begin{equation*}
\phi: S\to T.
\end{equation*}
用 \(t= \phi(s)\)或\(\phi: s\mapsto t\)表示在映射\(\phi\)下\(t\)与\(s\)相对应。称\(t\)为\(s\)在\(\phi\)下的像 ，\(s\)称为\(t\)的一个原像。当取遍\(S\)中所有\(s\)时，所有像的集合记为
\begin{equation*}
{\rm Im}(\phi)=\phi(S)=\{\phi(s)| s\in S\}.
\end{equation*}
元素\(t\)的所有原像的集合记为
\begin{equation*}
\phi^{-1}(t)=\{s\in S|\phi(s)= t\}.
\end{equation*}
映射是由它的三个要素\(S\)、\(T\)和映射法则\(\phi\)共同决定的。有时为了简便，我们通常用映射法则\(\phi\)作为整个映射的代表。假设现在有两个映射\(\phi: S\to T\)和\(\psi: U\to V\)。当且仅当\(S=U\)、\(T=V\)，且\(\forall s\in S\)、\(\phi(s) =\psi(s)\)时我们才认为这两个映射是一样的，并将其简记为\(\phi=\psi\)。
下面的几种映射有特殊重要的意义。
定义 A.2.13.
设\(\phi: S\to T\)。若\(\forall s_1\)、\(s_2\in S\)，\(s_1\ne s_2\)必有\(\phi(s_1)\ne \phi(s_2)\)，则称\(\phi\)是单射 。
由定义可知：若\(\phi\)是单射，则\(\phi(s_1)=\phi(s_2)\)等价于\(s_1=s_2\)。
定义 A.2.14.
若对\(\forall t\in T\)，存在\(s\in S\)，使得\(\phi(s)=t\)，则称\(\phi\)是满射。
\(\phi\)是满射等价于\(\phi(S)=T\)。
定义 A.2.15.
既单又满的映射称为双射，也称一一映射。
映射\(\phi\)是双射可以等价于：\(\forall t\in T\)，存在唯一\(s\in S\)，使得\(\phi(s)=t\)。其中存在性保证了\(\phi\)是满射，唯一性保证了\(\phi\)是单射。
对于有限集来说，两集合之间存在双射的充要条件是它们所含元素的个数相同。
对于集合\(S\)及\(T\subsetneq S\)，（即\(T\) 为\(S\) 的真子集），若\(S\)是有限集，则 \(S\)、\(T\) 之间不可能存在双射；但若\(S\)是无限集，则可能存在。如取\(S=\Z\)，\(T=2\Z =\{2n|n\in \Z\} \)为所有偶数集，对应法则\(\phi: n\mapsto 2n\)，容易验证\(\phi: S\to T\)是一个双射。是否存在到真子集的双射是有限集和无限集的本质差别之一。
一个映射建立了两个集合元素之间的联系，通过多个映射，我们也可以把这种联系链接起来。
定义 A.2.16.
设\(\phi: S\to T\)、\(\psi: T\to U\)。\(\phi\)与\(\psi\)的合成（也称复合）定义为
\begin{equation*}
\psi\phi: S\to U, s\mapsto \psi(\phi(s)).
\end{equation*}
注意在上述合成过程中，集合\(T\)起到了中间桥梁的作用。由于映射是一个单向的概念，这种合成通常也是单向的，即多数情况下，\(\psi\phi{\ne} \phi \psi\)。这里的不相等有3层含义：
\(\phi \psi\)不一定存在。当\(U{\ne} S\)时，\(\psi\)与\(\phi\)不能合成，相应地\(\phi\psi\)就不存在。
即便\(U=S\)，此时\(\phi\psi\)和\(\psi\phi\)都有意义，但也可能不相等。如\(T\ne S\)时，\(\phi \psi\)和\(\psi\phi\)就不可能相等。
即便\(S=T=U\)，\(\phi \psi\)和\(\psi\phi\)都是相同集合上的映射，此时仍有可能\(\phi \psi\ne \psi\phi\)。
例 A.2.17.
取\(S=T=U=\{1,2\}\)，\(\phi\)和\(\psi\)的对应法则如下表所示：
\begin{equation*}
\begin{array}{c|c|c}
s & 1 & 2\\
\hline
\phi(s) & 1 & 1
\end{array},\qquad \begin{array}{c|c|c}
s & 1 & 2\\
\hline
\psi(s) & 2 & 2
\end{array}.
\end{equation*}
则\((\phi\psi)(1)=\phi(\psi(1))=1\)，\((\psi\phi)(1)=\psi(\phi(1))=2\)，于是\(\phi\psi\ne \psi\phi\)。
容易验证映射的合成运算满足结合律：设 \(\phi: S\to {T}\)、\(\psi: {T}\to {U}\)、 \(\rho: {U}\to V\)，则
\begin{equation*}
\rho(\psi\phi)= (\rho\psi)\phi.
\end{equation*}
下面两种映射在合成运算的研讨中有重要作用。
定义 A.2.18.
映射\({\rm id}_S: S\to S, s\mapsto s\)称为集合\(S\)上的恒等映射或单位映射。
单位映射有复合不变性，类似于数字乘法中数字1的性质：设\(\phi: S\to T\)，则
\begin{equation*}
{\rm id}_T\phi=\phi{\rm id}_S=\phi.
\end{equation*}
定义 A.2.19.
设\(\phi: S\to T\)是映射，若存在映射\(\psi: T\to S\)，使得\(\psi\phi={\rm id}_S \)，且\(\phi\psi={\rm id}_T\)，则称\(\phi\)是可逆映射，并称\(\psi\)为\(\phi\)的逆映射。
定理 A.2.20.
映射\(\phi: S\to T\)是可逆映射的充分必要条件是映射\(\phi\)是双射。
可以验证：可逆映射的逆映射唯一，记\(\phi\)唯一的逆映射为\(\phi^{-1}\)。
同样可以验证：若\(\phi: S\to T\)、\(\psi: T\to U\)均为可逆映射， 则\(\psi\phi\)可逆，且\((\psi\phi)^{-1}=\phi^{-1}\psi^{-1}\)。
命题 A.2.22.
设\(\phi: S\to T\)、\(\psi: T\to U\)，则
若\(\phi\)、\(\psi\)是满的， 则\(\psi\phi\)也是满的；
若\(\phi\)、\(\psi\)是单的， 则\(\psi\phi\)也是单的；
若\(\phi\)、\(\psi\)是双射， 则\(\psi\phi\)也是双射。
