映射
自17世纪起，近代数学产生以来，函数概念一直是处于数学思想的真正核心位置。函数关系这一概念的重要意义远远超出了数学领域。数学和自然科学的绝大部分都受到函数关系的支配，这是不足奇怪的。研究自然现象与技术过程的辩证法告诉我们，对于一个过程或系统中出现的量或事物，不能孤立地来研究它们，而要研究它们之间的相互联系，从事物之间的联系中找出事物之运动规律。这种量与量、事物与事物间的相互联系的数学表现，在最简单的情形下，就是那种单值依赖关系，即函数关系。
在数学分析中，把函数的定义域与值域限制为数集是没有必要的。如果用随便什么属性的集代替数集，我们就得到了函数的最一般概念——我们采用几何术语“映射”来代替它。
本篇讨论映射的概念及几种重要的特殊类型的映射、映射的最一般性质、映射的合成运算、逆映射。我们还讨论了映射的应用，介绍了抽屉原理及其应用。
函数的一般概念——映射
在数学分析中，函数概念是这样引入的。设 $X$ 和 $Y$ 是两个数集, 如果依据某一法则 $f$ ，使对于 $X$ 中的每一数 $x$ 总有 $Y$ 中的唯一确定的数 $y$ 与之对应，则称 $f$ 为定义在 $X$ 上取值于 $Y$ 中的函数。$X$ 称为函数 $f$ 的定义域,而值域包含在 $Y$ 中。函数 $f$ 给 $x$ 规定的对应值 $y$ 常记为 $f(x)$ 。实际上，函数概念的实质在于它建立了量与量间的单值对应关系。
然而，不仅量与量间有单值依赖关系，事物与事物间也可有单值的对应关系。所以，如果把 $x$ 和 $y$ 了解为具有不同属性的集合，我们就得到了函数的一般概念——映射。这样，映射就是函数概念的推广，它既能描述量与量间的单值联系，又能描述具有任何属性的事物间的单值联系。
映射的定义
仿函数概念的定义,我们有
定义1： 设 $X$ 和 $Y$ 是两个非空集合。一个从 $X$ 到 $Y$ 的映射 $f$ 是一个法则，根据 $f$ ，对 $X$ 中的每个元素 $x$ 都有 $Y$ 中唯一确定的元素 $y$ 与之对应。$f$ 给 $x$ 规定的对应元素 $y$ 称为 $x$ 在 $f$ 下的象，而 $x$ 称为 $y$ 的原象。$X$ 称为 $f$ 的定义域。
“f是 $X$ 到 $Y$ 的映射”这句话常记为
$x$ 在 $f$ 下的象 $y$ 常记为 $f(x)$ 。集合
$$\begin{aligned} \set{f(x) | x \in X} \tag{2}\end{aligned}$$称为 $f$ 的值域或象，记为 $I_m(f)$ 。
映射的这个定义，在许多方面，直观上是令人满意的。但是，其中所用的“法则”概念是含混不清的。因此，定义1给出的映射并不是一个精确地定义了的对象。19世纪后叶，Cantor创立了集合论，数学家们把函数定义为Cartesian乘积的子集，即把函数与它的图象等同，这是严格的，其中不再含有含糊的概念。这就引导我们用图象的定义代替用规则定义的映射。
定义2：设 $X$ 和 $Y$ 是两个非空集合。一个从 $X$ 到 $Y$ 的映射是一个满足以下两个条件的 $X \times Y$ 的子集 $f$ ：
(1) 对 $X$ 的每一个元素 $x$ ，存在一个 $y \in Y$ ，使得 $(x,y) \in f$ ；
(2) 若 $(x,y)、(x,y') \in f$ ，则 $y = y'$ 。
在这个定义中，性质(2)称为“单值性”。条件（1）和（2）合起来说明每个 $x \in X$ 有唯一的 $y$ 使 $(x,y) \in f$ 。$y$ 仍记为 $f(x)$ ，叫做 $x$ 在 $f$ 下的象。另一种可能的记号是用 $(x)f$ 或就写成 $xf$ 来表示 $x$ 在 $f$ 下的象。实际上，这后一记法读起更顺，处理映射的合成时更方便。然而，大家显然一致偏爱前一种记法。
如果我们认为“规则”只能用集加以抽象，那么定义1与定义2是一样的。不过，即使大多数学家也更偏爱用规则来定义映射。因为它生动并便于应用，在自然科学和技术过程中大都使用规则来定义映射（函数）。
特殊映射
限制与部分映射
定义3：设 $f: X \to Y, A \sube X$ ，当把 $f$ 的定义域限制在 $A$ 上时，就得到了一个 $\varphi : A \to Y, \forall x \in A, \varphi(x)=f(x)$ 。$\varphi$ 被称为 $f$ 在 $A$ 上的限制，并且常用 $f | A$ 来代替 $\varphi$ 。反过来，我们说 $f$ 是 $\varphi$ 在 $X$ 上的扩张。
定义4：设 $f:A \to Y,A \sube X$ ，则称 $f$ 是 $X$ 上的一个部分映射。在这里，我们假定空集到 $Y$ 有一个唯一的映射，它也是 $X$ 到 $Y$ 的部分映射。
相等
定义5：两个映射 $f$ 和 $g$ 称为是相等的当且仅当 $f$ 和 $g$ 都是 $X$ 到 $Y$ 的映射，并且 $\forall x \in X$ 总有 $f(x)=g(x)$ 。
单射、满射与双射
定义6：设 $f: X \to Y$ ，如果 $\forall x,x' \in X$ ，只要 $x \ne x'$ ，就有 $f(x) \ne f(x')$ ，则称 $f$ 为从 $X$ 到 $Y$ 的单射(injection)。
定义7：设 $f: X \to Y$ ，如果 $\forall y \in Y$ ，$\exist x \in X$ 使得 $f(x) = y$ ，则称 $f$ 为从 $X$ 到 $Y$ 上的映射，或称 $f$ 为满射(surjection)。
定义8：设 $f: X \to Y$ ，若 $f$ 即是满射又是单射，则称 $f$ 为双射(bijection)，或一一对应。这时也称 $X$ 与 $Y$ 对等，记为 $X \sim Y$ 。
恒等映射
定义9：设 $f: X \to X$ ，如果 $\forall x \in X,f(x)=x$ ，则称 $f$ 为 $X$ 上的恒等映射。$X$ 上的恒等映射常记为 $I_X$ 或 $1_X$ 。
在具体应用中有时不写出映射的符号，而写出其元素 $x$ 与对应 $y$ 并用符号“ $\mapsto$ ”联接成 $x \mapsto y$ 。由上下文便知对应规则。有限集 $X$ 到 $Y$ 的映射 $f$ 也可用图示方法给出：先列出 $X$ 和 $Y$ 的元素，在图上用点表示，如果 $f(x)=y$ ，则在代表 $x$ 的点画一条带箭头的线指向代表 $y$ 的点。
映射与有穷集合的基数
定理1：设 $A$ 和 $B$ 是有限集，$f: A \to B$ 。如果 $f$ 是满射，则 $|A| \ge |B|$ ；如果 $f$ 是单射，则 $|A| \le |B|$ 。
〔证明(定理1)〕由于 $A$ 和 $B$ 都是有限集，我们不妨设 $A = \set{a_1,a_2,\cdots,a_m},B = \set{b_1,b_2,\cdots,b_n}$ ，则由定义17可知 $|A| = m, |B| = n$ 。如果 $f$ 是满射，则由定义7，$\forall b \in B$ ，$\exist a \in A$ 使得 $f(a)=b$ 。但是由定义2的条件2，$b_1,b_2,\cdots,b_n$ 的原象必须是互不相等的 $n$ 个 $A$ 的元素，因此 $m$ 必须要大于等于 $n$ ，即 $|A| \ge |B|$ 。如果 $f$ 是单射，由定义6，$\forall a,a' \in A$ ，只要 $a \ne a'$ ，就有 $f(a) \ne f(a')$ 。因此 $a_1,a_2,\cdots,a_m$ 的象必须是 $m$ 个互不相同的 $B$ 的元素，因此 $n$ 必须要大于等于 $m$ ，即 $|B| \ge |A|$ 。
证毕
定理2：设 $A$ 和 $B$ 是有限集且 $|A|=|B|$ ，则 $f: A \to B$ 是单射当且仅当 $f$ 是满射。
〔证明(定理2)〕由于 $|A|=|B|$ 且 $A,B$ 均是有限集，不妨设 $|A|=|B|=n$ ，则根据定义17可设 $A = \set{a_1,a_2,\cdots,a_n},B=\set{b_1,b_2,\cdots,b_n}$ 。先证明单射 $\Rightarrow$ 满射。如果 $f$ 是单射，根据定义6，$\forall a,a' \in A$ ，只要 $a \ne a'$ ，就有 $f(a) \ne f(a')$ 。则 $a_1,a_2,\cdots,a_n$ 映射到 $n$ 个互不相等的 $B$ 的元素。但是 $B$ 中只有 $n$ 个元素，因此 $B$ 中每一个元素都与一个 $A$ 中的元素构成映射关系。根据定义7，这符合满射的定义。因此 $f$ 是满射。再证明满射 $\Rightarrow$ 单射。根据定义7可知 $\forall b \in B$ ，$\exist a \in A$ 使得 $f(a)=b$ 。假如 $f$ 不是单射，则根据定义6，$\exist a,a' \in A$ ，$a \ne a'$ ，但是 $f(a)=f(a')$ 。那么除去 $a,a'$ ，还剩下 $n-2$ 个 $A$ 的元素至多映射到 $n-2$ 个 $B$ 的元素。再加上 $f(a)=f(a')$ ，则所有 $A$ 的元素至多映射到 $n-1$ 个 $B$ 的元素。但是 $|B|=n$ ，则至少有一个 $B$ 的元素是不存在一个 $a'' \in A$ 满足 $f(a'')=b$ 的，这与满射的定义相矛盾。因此 $f$ 是单射。
证毕
从X到Y的所有映射之集
从 $X$ 到 $Y$ 的所有映射之集记为 $Y^X$ ，即
$$\begin{aligned} Y^X=\set{f|f:X \to Y} \tag{3}\end{aligned}$$抽屉原理
直观上，映射可以解释为事物的一种安排方法。如果 $X=\set{a_1,a_2,\cdots,a_m},Y = \set{1,2,\cdots,n}$ ，则当把 $X$ 视为 $m$ 个事物之集，而 $1,2,\cdots,n$ 为 $n$ 个盒子时，则一个 $f:X \to Y$ 就是把 $m$ 个东西放到 $n$ 个盒子里的一种放法。在这里，若 $f(a_i)=j$ ，则把 $a_i$ 放到盒子 $j$ 中。如果 $m > n$ ，则必有一个盒子至少装两物体。用数学的术语来说，当 $m > n$ ，从 $X$ 到 $Y$ 的每个映射都不是单射，即至少有两个元素的象相同。这就是有名的Dirichlet原理，但数学家们总是用直观的方式叙述这个原理，并称之为鸽巢原理、抽屉原理。
抽屉原理
原理1（抽屉原理）：如果把 $n+1$ 个物体放到几个抽屉里，则必有一个抽屉里至少放了两个物体。
〔证明(抽屉原理)〕实际上，如果结论不成立，则每个抽屉至多放一个物体，从而 $n$ 个抽屉里总共有不多于 $n$ 个物体，这与假设矛盾。所以，抽屉原理成立。
证毕
抽屉原理十分简单,就是数学家也都喜欢用物体-抽屉、物体-盒子、鸽子-鸽巢的生动形象的方式来叙述。这种叙述形式并未假定这些物体是不可区分的，也未假定这些抽屉是可区分的。这只是一个存在性定理，它并未告诉我们怎样实地找到至少放两个物体的抽屉。
抽屉原理的强形式
原理2（抽屉原理的强形式）：设 $q_1,q_2,\cdots,q_n$ 为 $n$ 个正整数，如果把 $q_1+q_2+\cdots+q_n-n+1$ 个物体放到 $n$ 个盒子中，则或者第一个盒中至少含有 $q_1$ 个物体，或者第二个盒子中至少含有 $q_2$ 个物体，···，或者第 $n$ 个盒子中至少含有 $q_n$ 个物体。
〔证明(抽屉原理的强形式)〕实际上，如果抽屉原理的强形式不成立，则每个盒子 $i$ 中至多含有 $q_i-1$ 个物体。于是 $n$ 个盒子中总共至多含有 $\displaystyle\sum_{i=1}^{n}(q_i-1)=\sum_{i=1}^{n}q_i-n$ 个物体。但已把 $\displaystyle\sum_{i=1}^{n}q_i-n+1$ 个物体全放入 $n$ 个盒子中了。而 $\displaystyle\sum_{i=1}^{n}q_i-n < \sum_{i=1}^{n}q_i-n+1$ ，这就引出矛盾。
证毕
当 $q_1=q_2=\cdots=q_n=2$ 时，$\displaystyle\sum_{i=1}^{n}q_i-n+1=n+1$ 。于是，抽屉原理是抽屉原理强形式的一个特殊情况。
推论1：若把 $n(r-1)+1$ 个物体放入 $n$ 个盒子中，则至少有一个盒中含有不少于 $r$ 个物体。
〔证明(推论1)〕抽屉原理的强形式中取 $q_1=q_2=\cdots=q_n=r$ ，则 $\displaystyle\sum_{i=1}^{n}q_i-n+1=nr-n+1=n(r-1)+1$ 。于是推论成立。
证毕
推论2：如果 $n$ 个正整数 $m_1,m_2,\cdots,m_n$ 的平均值 $\displaystyle\frac{m_1+m_2+\cdots+m_n}{n}>r-1$ ，则 $m_1,m_2,\cdots,m_n$ 中至少有一个正整数不小于 $r$ 。
〔证明(推论2)〕相当于将 $m_1+m_2+\cdots,+m_n$ 个物品放入 $n$ 个盒子中，每个盒子的物品数量就是 $m_i$ 的值。$\displaystyle\frac{m_1+m_2+\cdots+m_n}{n}>r-1$ 也就是 $m_1+m_2+\cdots+m_n > n(r-1)$ ，即 $m_1+m_2+\cdots+m_n \ge n(r-1)+1$ 。因此由推论1，至少有一个盒子中的物品数量不少于 $r$ ，即 $m_1,m_2,\cdots,m_n$ 中至少有一个正整数不小于 $r$ 。
证毕
映射的一般性质
诱导映射
设 $f:X \to Y$ 。由 $f$ 产生的，或诱导出的一些映射是有用的。若 $A \sube X$ ，那么由 $f$ 和 $A$ 就唯一地确定了 $Y$ 的一个子集，记为 $f(A)$ ：
$$\begin{aligned} f(A) = \set{f(x) | x \in A} \tag{4}\end{aligned}$$$f(A)$ 称为 $A$ 在 $f$ 下的象。利用这种方法，由 $f$ 就确定了一个从 $2^X$ 到 $2^Y$ 的映射，习惯上将这个映射仍记为 $f$ 。根据上下文，不会混淆的。显然，$f(\varnothing) = \varnothing,f(X) = I_m(f)$ ，并且
$$\begin{aligned} f是X到Y的满射，当且仅当f(X)=Y。 \tag{5}\end{aligned}$$又若
$$\begin{aligned} A \sube B \sube X，则f(A) \sube f(B)。 \tag{6}\end{aligned}$$其次，若 $B \sube Y$ ，则由 $f$ 和 $B$ 唯一确定了 $X$ 的一个子集 $\set{x | f(x) \in B, x \in X}$ ，这个子集习惯上用 $f^{-1}(B)$ 表示。即
$$\begin{aligned} f^{-1}(B) = \set{x | f(x) \in B, x \in X} \tag{7}\end{aligned}$$$f^{-1}(B)$ 是 $X$ 中在 $f$ 下象落在 $B$ 里的那些元素组成的，$f^{-1}(B)$ 叫做在 $f$ 下 $B$ 的原象。于是，利用这种方法，由 $f$ 就导出了一个从幂集 $2^Y$ 到 $2^X$ 的一个映射，数学文献中总是把这个导出映射记为 $f^{-1}$ 。不幸的是，这个记号与以后要讲的逆映射的记号相同。这是两个不同的概念，但根据上下文是可区分的。因此，我们仍遵循数学文献中的习惯。显然
$$\begin{aligned} f^{-1}(Y)=X \tag{8}\end{aligned}$$一定成立。
诱导映射的性质
逆向
定理3：设 $f:X \to Y,C \sube Y,D \sube Y$ ，则
(1)
$$\begin{aligned} f^{-1}(C \cup D) = f^{-1}(C) \cup f^{-1}(D) \tag{9}\end{aligned}$$(2)
$$\begin{aligned} f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D) \tag{10}\end{aligned}$$(3)
$$\begin{aligned} f^{-1}(C \backslash D) = f^{-1}(C) \backslash f^{-1}(D) \tag{11}\end{aligned}$$(4)
$$\begin{aligned} f^{-1}(C \triangle D) = f^{-1}(C) \triangle f^{-1}(D) \tag{12}\end{aligned}$$(5)
$$\begin{aligned} f^{-1}(C^c) = (f^{-1}(C))^c \tag{13}\end{aligned}$$注： $X$ 上集合的余集是对 $X$ 求的，而 $Y$ 上集合的余集是对 $Y$ 求的。
〔证明(定理3)〕
(1) 设 $x \in f^{-1}(C \backslash D)$ ，则由(7)可得 $f(x) \in C \backslash D$ 。于是，$f(x) \in C$ 或 $f(x) \in D$ 。因此再由(7)可得 $x \in f^{-1}(C)$ 或 $x \in f^{-1}(D)$ ，所以 $x \in f^{-1}(C) \backslash f^{-1}(D)$ 。故 $f^{-1}(C \backslash D) \sube f^{-1}(C) \backslash f^{-1}(D)$ 。其次，设 $x \in f^{-1}(C) \backslash f^{-1}(D)$ ，则 $x \in f^{-1}(C)$ 或 $x \in f^{-1}(D)$ 。从而根据(7)可得 $f(x) \in C$ 或 $f(x) \in D$ 。因此，$f(x) \in C \backslash D$ ，故由(7)可得 $x \in f^{-1}(C \backslash D)$ 。所以 $f^{-1}(C) \backslash f^{-1}(D) \sube f^{-1}(C \backslash D)$ 。因此，(9)成立。
(2) 设 $x \in f^{-1}(C \cap D)$ ，则由(7)可得 $f(x) \in C \cap D$ 。于是，$f(x) \in C$ 且 $f(x) \in D$ 。因此再由(7)可得 $x \in f^{-1}(C)$ 且 $x \in f^{-1}(D)$ ，所以 $x \in f^{-1}(C) \cap f^{-1}(D)$ 。故 $f^{-1}(C \cap D) \sube f^{-1}(C) \cap f^{-1}(D)$ 。其次，设 $x \in f^{-1}(C) \cap f^{-1}(D)$ ，则 $x \in f^{-1}(C)$ 且 $x \in f^{-1}(D)$ 。从而根据(7)可得 $f(x) \in C$ 且 $f(x) \in D$ 。因此，$f(x) \in C \cap D$ ，故由(7)可得 $x \in f^{-1}(C \cap D)$ 。所以 $f^{-1}(C) \cap f^{-1}(D) \sube f^{-1}(C \cap D)$ 。因此，(9)成立。
(3) 设 $x \in f^{-1}(C \backslash D)$ ，则由(7)可得 $f(x) \in C \backslash D$ 。于是，$f(x) \in C$ 且 $f(x) \notin D$ 。因此再由(7)可得 $x \in f^{-1}(C)$ 且 $x \notin f^{-1}(D)$ （实际上如果 $x \in f^{-1}(D)$ ，则一定有 $f(x) \in D$ ，与条件相矛盾），所以 $x \in f^{-1}(C) \backslash f^{-1}(D)$ 。故 $f^{-1}(C \backslash D) \sube f^{-1}(C) \backslash f^{-1}(D)$ 。其次，设 $x \in f^{-1}(C) \backslash f^{-1}(D)$ ，则 $x \in f^{-1}(C)$ 且 $x \notin f^{-1}(D)$ 。从而根据(7)可得 $f(x) \in C$ 且 $f(x) \notin D$ （实际上如果 $f(x) \in D$ ，则一定有 $x \in f^{-1}(D)$ ，与条件相矛盾）。因此，$f(x) \in C \backslash D$ ，故由(7)可得 $x \in f^{-1}(C \backslash D)$ 。所以 $f^{-1}(C) \backslash f^{-1}(D) \sube f^{-1}(C \backslash D)$ 。因此，(9)成立。
(4) 由定义10、(9)和(11)可得
证毕
正向
定理4：设 $f:X \to Y,A \sube X,B \sube X$ ，则
(1)
$$\begin{aligned} f(A \cup B) = f(A) \cup f(B) \tag{16}\end{aligned}$$(2)
$$\begin{aligned} f(A \cap B) \sube f(A) \cap f(B) \tag{17}\end{aligned}$$(3)
$$\begin{aligned} f(A \backslash B) \supe f(A) \backslash f(B) \tag{18}\end{aligned}$$(4)
$$\begin{aligned} f(A \triangle B) \supe f(A) \triangle f(B) \tag{19}\end{aligned}$$注： $f(A^c)$ 和 $(f(A))^c$ 没有必然联系。
〔证明(定理4)〕
(1) 设 $y \in f(A \cup B)$ ，则 $\exist x \in A \cup B$ 使得 $y = f(x)$ ，于是 $x \in A$ 或 $x \in B$ 。因此 $y \in f(A)$ 或 $y \in f(B)$ 。所以 $y \in f(A) \cup f(B)$ 。故 $f(A \cup B) \sube f(A) \cup f(B)$ 。
反之，设 $y \in f(A) \cup f(B)$ ，则 $y \in f(A)$ 或 $y \in f(B)$ 。于是 $\exist x_1 \in A$ 使 $f(x_1)=y$ ，或 $\exist x_2 \in B$ 使 $f(x_2)=y$ 。不管是哪种情况，均有 $x_1 \in A \cup B, x_2 \in A \cup B$ 。因此一定 $\exist x \in A \cup B$ 使得 $f(x)=y$ 。因此，$y \in f(A \cup B)$ 。所以，又有 $f(A) \cup f(B) \sube f(A \cup B)$ 。
综上所述，$f(A \cup B) = f(A) \cup f(B)$ 。
(2) 设 $y \in f(A \cap B)$ ，则 $\exist x \in A \cap B$ 使得 $y = f(x)$ 。于是，$x \in A$ 且 $x \in B$ 。因此 $y \in f(A)$ 且 $y \in f(B)$ 。所以 $y \in f(A) \cap f(B)$ ，故 $f(A \cap B) \sube f(A) \cap f(B)$ 。
注意 $f(A) \cap f(B) \nsubseteq f(A \cap B)$ ，因为如果设 $y \in f(A) \cap f(B)$ ，则 $y \in f(A)$ 且 $y \in f(B)$ 。于是，$\exist x_1 \in A$ 使 $f(x_1)=y$ ，并且 $\exist x_2 \in B$ 使 $f(x_2)=y$ 。但是，这并不能推出 $\exist x \in A \cap B$ 使 $f(x)=y$ 。因为由 $x_1 \in A$ 并不能推出 $x_1 \in A \cap B$ ，同理 $x_2 \in B$ 也不能推出 $x_2 \in A \cap B$ 。所以，$f(A) \cap f(B) \nsubseteq f(A \cap B)$ 。
(3) 设 $y \in f(A) \backslash f(B)$ ，有 $y \in f(A)$ 并且 $y \notin f(B)$ 。于是，$\exist x_1 \in A$ 使 $f(x_1)=y$ ，并且 $\nexists x_2 \in B$ 使 $f(x_2) = y$ 。这两个条件同时满足的话，注意 $x_1$ 也不能属于 $B$ ，因为如果 $x_1 \in B$ ，则 $f(x_1)=y$ 会和 $\nexists x_2 \in B$ 使 $f(x_2) = y$ 相矛盾。因此可以推出 $\exists x_1 \in A \backslash B$ 使 $f(x_1)=y$ ，即 $\exists x \in A \backslash B$ 使 $f(x)=y$ 。因此，$y \in f(A \backslash B)$ 。即 $f(A) \backslash f(B) \sube f(A \backslash B)$ 。
注意 $f(A \backslash B) \nsubseteq f(A) \backslash f(B)$ 。因为如果设 $y \in f(A \backslash B)$ ，则 $\exists x \in A \backslash B$ 使 $y=f(x)$ 。但是 $\exists x \in A \backslash B$ 使 $y=f(x)$ 并不能推导出 $\exists x \in A$ 使 $y=f(x)$ 并且 $\nexists x \in B$ 使 $y=f(x)$ 。因为 $\exists x \in A \backslash B$ 使 $y=f(x)$ 不能说明 $\exists x \in A$ 使 $y=f(x)$ ，也不能说明 $\nexists x \in B$ 使 $y=f(x)$ 。所以 $f(A \backslash B) \nsubseteq f(A) \backslash f(B)$ 。
(4) 由定义10、(16)、(18)和命题1可得
证毕
逆向与正向
定理5：设 $f:X \to Y, A \sube X, C \sube Y$ ，则
(1)
$$\begin{aligned} f(f^{-1}(C)) \sube C，当 f 为满射时相等 \tag{21}\end{aligned}$$(2)
$$\begin{aligned} f^{-1}(f(A)) \supe A，当 f 为单射时相等 \tag{22}\end{aligned}$$ 〔证明(定理5)〕
(1) 设 $y \in f(f^{-1}(C))$ ，则 $\exists x \in f^{-1}(C)$ 使 $f(x)=y$ 。由 $x \in f^{-1}(C)$ 又可推导出 $\exists y' \in C$ ，有 $f(x) = y'$ 。由定义2可知此时 $y=y'$ ，故 $y \in C$ 。因此 $f(f^{-1}(C)) \sube C$ 。
反过来，设 $y \in C$ 。若 $f$ 是满射，则由定义7可知，$\exists x \in X$ 使 $f(x)=y$ 。注意 $y \in C$ ，因此 $x \in f^{-1}(C)$ 。再利用 $f(x)=y$ 可得 $y \in f(f^{-1}(C))$ 。因此 $C \sube f(f^{-1}(C))$ 。综上，$f(f^{-1}(C)) = C$ 。如果 $f$ 不是满射，则可能存在一个 $y \in C$ ，$\nexists x \in X$ 使得 $f(x)=y$ 。如果 $y \in f(f^{-1}(C))$ ，则 $\exists x \in f^{-1}(C)$ ，使 $f(x)=y$ 。这与 $\nexists x \in X$ 使得 $f(x)=y$ 相矛盾。因此 $y \notin f(f^{-1}(C))$ 。即 $C \nsubseteq f(f^{-1}(C))$ 。
(2) 设 $x \in A$ ，则 $\exists y \in f(A)$ 使 $f(x)=y$ 。由 $y \in f(A), f(x)=y$ 和(7)又可推导出 $x \in f^{-1}(f(A))$ 。因此 $A \sube f^{-1}(f(A))$ 。
反过来，设 $x \in f^{-1}(f(A))$ 。则 $\exists y \in f(A)$ 使得 $y = f(x)$ 。采用反证法，假设 $x \notin A$ 。如果 $f$ 是单射，根据定义6，这意味着 $\nexists x' \in A$ ，使得 $f(x')=y$ 。这与 $y \in f(A)$ 相矛盾。因此，必须有 $x \in A$ 。即 $f^{-1}(f(A)) \sube A$ 。综上可得 $f^{-1}(f(A)) = A$ 。如果 $f$ 不是单射，则有可能存在一个 $x' \in A$ ，使得 $f(x') = y$ 。此时 $y \in f(A)$ 仍成立，推不出矛盾。因此 $f^{-1}(f(A)) \nsubseteq A$ 。
证毕
映射的合成
映射是函数概念的推广，映射的合成运算是复合函数概念的推广。在数学分析中，复合函数的连续性定理、复合函数的微分法、积分的换元积分法是最重要的计算方法。其实，换元法不仅在积分中使用，在求解微分方程及其他科学中经常使用，其动机或者由所讨论的问题中，这种变量及其函数特别值得采用，或者这种变换的引入使表达式得以简化。其次，利用函数的复合能用已知的函数产生新的函数，这种产生机制对计算机科学和程序设计语言是十分有用的。
合成的定义
定义10：设 $f: X \to Y,g: Y \to Z$ ，一个从 $X$ 到 $Z$ 的映射 $h$ 称为 $f$ 与 $g$ 的合成，如果 $\forall x \in X,h(x)=g(f(x))$ 。“映射 $f$ 与 $g$ 的合成” $h$ 记为 $g \circ f$ ，且常省去其中的“ $\circ$ ”，而写成 $gf$ 。
按定义，$\forall x \in X$ ，我们有
$$\begin{aligned} g \circ f(x) = gf(x) = g(f(x)) \tag{23}\end{aligned}$$注意“ $f$ 与 $g$ 的合成”在书写时写成 $gf$ ，顺序正好相反。这是由于我们采用记号 $f(x)$ 来表示 $x$ 在 $f$ 下的象。如果用 $(x)f$ 表示 $x$ 在 $f$ 下的象，则“ $f$ 与 $g$ 的合成”就可以记成 $fg$ ，这显然是方便的。
合成的性质
结合律
定理6：设 $f:X \to Y, g: Y \to Z,h:Z \to W$ ，则
$$\begin{aligned} h(gf) = (hg)f \tag{24}\end{aligned}$$即映射的合成运算满足结合律。
〔证明(定理6)〕注意 $h(gf)$ 与 $(hg)f$ 都是 $X$ 到 $W$ 的映射。而且 $\forall x \in X$ ，我们有 $h(gf)(x)=h(gf(x))=h(g(f(x)))$ ，$(hg)f(x)=hg(f(x))=h(g(f(x)))$ 。因此 $\forall x \in X$ ，总有 $h(gf)(x)=(hg)f(x)$ 。所以，根据映射相等的定义便得到 $h(gf) = (hg)f$ 。
证毕
映射的合成运算满足结合律是合成运算的基本性质。据此，$h(gf)$ 和 $(hg)f$ 就可简记为 $hgf$ 。于是，如果 $f_1:A_1 \to A_2,f_2:A_2 \to A_3,\cdots,f_n:A_n \to A_{n+1}$ ，则 $f_1,f_2,\cdots,f_n$ 的合成就可记为 $f_n \circ f_{n-1} \circ \cdots \circ f_1$ 或 $f_nf_{n-1}\cdots f_1$ ，并且，$\forall x \in A_1$
$$\begin{aligned} f_nf_{n-1}\cdots f_1(x) = f_n(f_{n-1}\cdots (f_2(f_1(x))) \cdots ) \tag{25}\end{aligned}$$与恒等映射相关
定理7：设 $f:X \to Y$ ，则 $f \circ I_X = I_Y \circ f$ 。
〔证明(定理7)〕 $\forall x \in X$ ，由定义9可得 $f \circ I_X (x) = f(x),I_Y \circ f(x) = f(x)$ 。因此 $f \circ I_X = I_Y \circ f$ 。
证毕
与单射、双射和满射相关
定理8：设 $f:X \to Y,g: Y \to Z$ ，则
(1) 如果 $f$ 和 $g$ 都是单射，则 $g \circ f$ 也是单射。
(2) 如果 $f$ 和 $g$ 都是满射，则 $g \circ f$ 也是满射。
(3) 如果 $f$ 和 $g$ 都是双射，则 $g \circ f$ 也是双射。
〔证明(定理8)〕
(1) $\forall x \in X$ ，则由于 $f$ 是单射，所以当 $x_1 \ne x_2$ 时有 $f(x_1) \ne f(x_2)$ 。再由 $g$ 是单射，便有 $g(f(x_1)) \ne g(f(x_2))$ ，故 $g \circ f$ 是单射。
(2) 由于 $g$ 是满射，所以 $\forall z \in Z, \exists y \in Y$ 使 $g(y)=z$ 。又因为 $f$ 是满射，所以对上述的 $y$ 有一个 $x \in X$ ，使得 $f(x)=y$ 。于是，$g \circ f(x) = g(f(x)) = g(y) = z$ 。这表明 $g \circ f$ 是满射。
(3) 由定义8，$f$ 和 $g$ 既是满射又是单射。因此由(1)(2)可得，$g \circ f$ 也既是满射又是单射，因此 $g \circ f$ 是双射。
证毕
定理9：设 $f: X \to Y, g: Y \to Z$ ，则
(1) 如果 $g \circ f$ 是单射，则 $f$ 是单射。
(2) 如果 $g \circ f$ 是满射，则 $g$ 是满射。
(3) 如果 $g \circ f$ 是双射，则 $f$ 是单射且 $g$ 是满射。
〔证明(定理9)〕
(1) 因为 $g \circ f$ 是单射，所以 $\forall x_1,x_2 \in X$ ，若 $x_1 \ne x_2$ ，则 $g(f(x_1)) \ne g(f(x_2))$ 。假设 $f(x_1) = f(x_2)$ ，由于 $g$ 是映射，这与定义2的条件(2)矛盾，因此 $f(x_1) \ne f(x_2)$ 。所以 $f$ 是单射。
(2) 如果 $g$ 不是满射，则 $\exists z_0 \in Z$ 使得 $\forall y \in Y$ 有 $g(y) \ne z_0$ 。于是，$\forall x \in X,g \circ f(x) = g(f(x)) \ne z_0$ ，这与 $g \circ f$ 是满射相矛盾。因此，$g$ 是满射。
(3) 若 $g \circ f$ 是双射，由定义8可知 $g \circ f$ 既是单射又是满射。由(1)(2)可知 $f$ 是单射 $g$ 是满射。
证毕
与到自身的映射相关
定理10：设 $f$ 与 $g$ 都是 $X$ 到 $X$ 的映射，则 $I_m(f) \sube I_m(g)$ 的充分必要条件是存在一个映射 $h: X \to X$ 使得 $f = g \circ h$ 。
〔证明(定理10)〕先证必要性。设 $I_m(f) \sube I_m(g)$ 。则 $f(X) \sube g(X)$ ，即 $\forall x \in X, f(x) \in g(X)$ 。所以，对每个 $x \in X$ ，存在一个 $y$ 使 $g(y)=f(x)$ 。令 $h:X \to X$ ，$h$ 定义为 $\forall x \in X$ ，$h(x)=y$ ，$y$ 为 $g^{-1}(f(x))$ 中某个元素。于是，$g \circ h(x) = g(h(x)) = g(y) = f(x)$ 。所以，$f = g \circ h$ 。
再证充分性。设 $h:X \to X, f = g \circ h$ 。由于一定有 $h(X) \sube X$ ，所以，$\forall x \in h(X)$ ，有 $x \in X$ 。又由(4)可知 $g(x) \in g(X)$ 。因此 $\forall x \in h(X)$ 有 $g(x) \in g(X)$ 。因此再由(4)的定义可知 $g(h(X)) \sube g(X)$ 。即 $g \circ h(X) \sube g(X)$ 。即 $I_m(f) \sube I_m(g)$ 。
证毕
交换图
在一个问题中往往涉及到若干个集合，在集合间存在一个集到另一个集的映射。这些映射刻划了这个系统中事物之间的联系。为了直观和清楚，人们往往在纸上写出这些集合的名字，如果两个集合间有一个映射，则就在这两个集间画一条带箭头的线，线上标明映射的名字。这样就得到了一个“图”，叫做映射图。这些集合叫做图的顶点。如果 $A$ 和 $B$ 是两个顶点，从 $A$ 开始沿矢线方向走可达到点 $B$ ，则说从 $A$ 到 $B$ 有一条有向路径。如果一个映射图的任两顶点间的每一有向路径上出现的映射合成后均相等，则称此图是一个交换图。例如，说图1中的三角形是交换图，意即 $h = g \circ f$ 。我们说图2是交换图，意即 $\alpha = g \circ f, \beta = h \circ g, \beta \circ f = h \circ \alpha$ 。而结合律成立，相当于说：如果三角形 $XYW$ 与 $YZW$ 是可交换的，则整个图是交换图。实际上如果 $XYW$ 和 $YZW$ 可交换，则 $\alpha = g \circ f, \beta = h \circ g$ ，通过结合律可推出 $XYZW$ 可交换，即可推出 $\beta \circ f = h \circ \alpha$ ，因为 $h \circ g \circ f = (h \circ g) \circ f = \beta \circ f = h \circ (g \circ f) = h \circ \alpha$ 。
图1
图2
逆映射
逆映射的定义
逆映射是反函数概念的推广。设 $V$ 是一个 $n$ 维线性空间。我们知道，$V$ 上的一个线性变换 $A$ 可以用一个 $n$ 阶矩阵 $A$ 表示。当选定了 $V$ 中的基后，矩阵 $A$ 代表了一个线性变换。在线性代数中定义了逆矩阵： $n$ 阶方阵 $A$ 称为是可逆的，如果存在一个 $n$ 阶方阵 $B$ 使得
$$\begin{aligned} AB=I且BA=I \tag{26}\end{aligned}$$ 其中 $I$ 是 $n$ 阶单位矩阵。$B$ 称为 $A$ 的逆矩阵，记为 $A^{-1}$ 。
仿此，我们有
定义11：设 $f: X \to Y$ 。如果存在一个映射 $g:Y \to X$ 使得
$$\begin{aligned} f \circ g = I_Y且g \circ f = I_X \tag{27}\end{aligned}$$则称映射 $f$ 是可逆的，而 $g$ 称为 $f$ 的逆映射。
按定义，$f$ 可逆当且仅当 $g \circ f = I_X$ 与 $f \circ g = I_Y$ 同时成立，缺一不可。仅保留其中一个条件时，我们便有
定义12：设 $f:X \to Y$ ，如果存在一个映射 $g:Y \to X$ 使得 $g \circ f = I_X$ ，则称 $f$ 是左可逆的，$g$ 称为 $f$ 的左逆映射。而如果存在一个映射 $h:Y \to X$ 使得 $f \circ h = I_Y$ ，则称 $f$ 是右可逆的，而 $h$ 称为 $f$ 的右映射。
逆映射的性质
映射可逆的充要条件是映射是双射
定理11：设 $f:X \to Y$ ，则 $f$ 可逆的充分必要条件是 $f$ 为双射（一一对应）。
〔证明(定理11)〕先证必要性。设 $f$ 是可逆的，按定义11，存在一个映射 $g:Y \to X$ ，使得 $g \circ f = I_X$ 且 $f \circ g = I_Y$ 。由于恒等映射 $I_X,I_Y$ 既是单射又是满射，所以由定理9便得到 $f$ 既是满射又是单射，因此，$f$ 是双射。
再证充分性。设 $f$ 是双射。则 $\forall y \in Y$ 有且仅有一个 $x \in X$ 使得 $f(x)=y$ 。于是，令 $g: Y \to X$ ，对任一 $y \in Y$ ，$g(y)=x$ 当且仅当 $f(x)=y$ 。显然，$g$ 是映射。而且 $\forall x \in X$，$g \circ f(x) = g(f(x)) = x = I_X(x)$ ，所以 $g \circ f = I_X$ 。又 $\forall y \in Y$ ，$f \circ g(y) = f(g(y)) = f(x) = y = I_Y(y)$ ，所以又有 $f \circ g = I_Y$ 。因此，$f$ 是可逆的，并且 $g$ 就是 $f$ 的逆映射。
证毕
映射可逆则其逆映射唯一
定理12：设 $f:X \to Y$ ，则如果 $f$ 是可逆的，那么 $f$ 的逆映射是唯一的。$f$ 的逆记为 $f^{-1}$ 。
〔证明(定理12)〕因为 $f$ 是可逆的，所以有 $g: Y \to X$ ，使得 $f \circ g = I_Y$ 且 $g \circ f = I_X$ 。若还有 $h:Y \to X$ 使得 $h \circ f = I_X$ 且 $f \circ h = I_Y$ ，则
$$\begin{aligned} g = I_X \circ g = (h \circ f) \circ g = h \circ (f \circ g) = h \circ I_Y = h \tag{28}\end{aligned}$$故 $f$ 有唯一的逆。
证毕
穿脱原则
定理13：设 $f:X \to Y, g: Y \to Z$ 都是可逆的，则 $gf$ 也可逆且
$$\begin{aligned} (gf)^{-1}=f^{-1}g^{-1} \tag{29}\end{aligned}$$ $$\begin{aligned} (f^{-1})^{-1} = f \tag{30}\end{aligned}$$公式 $(gf)^{-1} = f^{-1}g^{-1}$ 称为“穿脱原则”，脱的次序正好与穿的次序相反。
〔证明(定理13)〕由于 $f$ 和 $g$ 均可逆，而且由定理12知 $f$ 和 $g$ 的逆映射 $f^{-1}$ 和 $g^{-1}$ 都是唯一的，并且 $f^{-1}: Y \to X, g^{-1}: Z \to Y$ 。因此，$g^{-1}$ 与 $f^{-1}$ 可以合成且 $f^{-1}g^{-1}$ 是 $Z$ 到 $X$ 的映射。其次，
$$\begin{aligned} (gf)(f^{-1}g^{-1})=g(ff^{-1})g^{-1}=gg^{-1}=I_Z \tag{31}\end{aligned}$$ $$\begin{aligned} (f^{-1}g^{-1})(gf)=f^{-1}(g^{-1}g)f=f^{-1}f=I_X \tag{32}\end{aligned}$$ 所以 $f^{-1}g^{-1}$ 是 $gf$ 的逆，故 $(gf)^{-1}=f^{-1}g^{-1}$ 。
由于 $f \circ f^{-1} = I_Y$ 且 $f^{-1}f=I_X$ ，所以，$f$ 与 $f^{-1}$ 是互为逆映射。因此，$f$ 是 $f^{-1}$ 的逆，就应记成 $(f^{-1})^{-1}$ 。故 $(f^{-1})^{-1}=f$ 。
证毕
与诱导映射的区别
定理11给出了逆映射存在的条件，只有一一对应才有逆映射。定理12给出了逆映射的唯一性，因此才可用 $f^{-1}$ 表示 $f$ 的唯一逆。应该注意的是，对任何的 $f: X \to Y$ ，在诱导映射一节中引出了 $2^Y \to 2^X$ 的诱导映射，这个诱导映射也用 $f^{-1}$ 表示，这个诱导映射也用 $f^{-1}$ 表示，这时 $f^{-1}$ 是作用 $Y$ 的子集上的。而当 $f$ 可逆时，符号 $f^{-1}$ 又代表 $f$ 的逆，其定义域为 $Y$ 。这是两个不同的概念。根据上下文，便知其定义域，从而区分出 $f^{-1}$ 是逆映射，还是 $f$ 诱导出的 $2^Y$ 到 $2^X$ 的映射。
其次,按定义11，如果 $f:X \to Y$ 可逆，则 $f$ 的逆是从 $Y$ 到 $X$ 的映射，即 $f^{-1}$ 的定义域必须是 $Y$ ，在 $Y$ 中 $f^{-1}$ 处处有定义。当 $f$ 是 $X$ 到 $Y$ 的单射时，若 $I_m(f) \sub Y$ 则 $f$ 可视为 $X$ 到 $I_m(f)$ 的一一对应, 从而有逆，其逆是从 $I_m(f)$ 到 $X$ 的映射，在 $Y \backslash I_m(f)$ 中没有定义，因此不是 $f:X \to Y$ 的逆。
左可逆与右可逆的充分必要条件
定理14：设 $f:X \to Y$ ，则
(1) $f$ 左可逆的充分必要条件是 $f$ 为单射。
(2) $f$ 右可逆的充分必要条件是 $f$ 为满射。
〔证明(定理14)〕
(1) 先证必要性。设 $f$ 是左可逆的。由定义12和定理9的(1)便得到 $f$ 是单射。再证充分性。设 $f$ 是单射。则 $f$ 可视为 $X$ 到 $I_m(f)$ 的一一对应。于是，有 $g:I_m(f) \to X$ 使得 $g \circ f = I_X$ 。扩充 $g$ 到 $Y$ 上： $\forall y \in Y$ ，若 $y \in I_m(f)$ ，则 $g(y)$ 不变，而当 $y \in Y \backslash I_m(f)$ 时，规定 $g(y)$ 为 $X$ 中一固定元 $x_0$ ，则 $g$ 就是 $Y$ 到 $X$ 的映射，且由于 $\forall x \in X,f(x) \in I_m(f)$ 可知 $g(f(x))=x$ ，因此 $g \circ f = I_X$ 。所以，$f$ 是左可逆的。
(2)先证必要性。设 $f$ 是右可逆的。由定义12和定理9的(2)便得到 $f$ 是满射。再证充分性。设 $f$ 是满射，则 $\forall y \in Y,f^{-1}(\set{y}) \ne \varnothing$ （这里的 $f^{-1}$ 是诱导映射）。令 $g:Y \to X$ ，其定义为，对 $Y$ 的每个元素 $y$ ，$g(y)=x$ ，其中 $x$ 为 $f^{-1}(\set{y})$ 中俄一个特定元素。于是，$f(x)=y$ 。且 $(fg)(y)=f(g(y))=f(x)=y$ ，因此 $f \circ g = I_Y$ 。所以，$f$ 是右可逆的。
证毕
由定理14的证明可知，若 $f$ 左可逆，则 $f$ 的左逆映射未必唯一，甚至可以有无穷多个。若 $f$ 右可逆，则 $f$ 的右逆映射也未必唯一，也可以有无穷多个。
置换
本节讨论有限集合s上的一一对应。
置换的定义
定义13：有限集合 $S$ 到自身的一一对应称为 $S$ 上的一个置换(permutation)。如果 $|S|=n$ ，则 $S$ 上的置换就说成是 $n$ 次置换。
实际上，一个 $n$ 次置换就是 $S$ 的 $n$ 个元素的一个全排列。
置换在数学里和其他方面有着各种各样的应用。在组合数学、近世代数、几何、物理学、理论化学、量子力学以及工程技术中的应用是人们共知的。因此，在有数学修养的任何人的知识宝库中，必须吸收这个简明而自然的概念。虽然有些问题，不用置换概念也能解决，但这时要引人一些不自然的或没有意义的设计。
置换的表示
由于我们对集合中元素的属性并不感兴趣，所以用什么符号表示集合中的元素是没有什么关系的。因此，我们用 $1,2,\cdots,n$ 表示 $n$ 元集 $S$ 的各元素。
设 $S=\set{1,2,\cdots,n}$ ，$\sigma$ 是 $S$ 上的一个置换，即 $\sigma$ 是 $S$ 到 $S$ 的一个一一对应。于是，对 $S$ 中每个元素 $i$ ，在 $S$ 中有唯一的一个元素 $k_i$ 与之对应，即 $\sigma(i)=k_i$ 。由于 $S$ 只有 $n$ 个元素，所以可把 $S$ 的 $n$ 个元素写在一行上，而把每个元素在 $\sigma$ 下的像写在这个元素的下面，那么就得到如下的一个表
显然，已知(33)与已知 $\sigma$ 是等价的。所以，(33)是置换的一个方便的表示。因此，我们可得
$$\begin{aligned} \sigma = \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\[5pt] k_1 & k_2 & k_3 & \cdots & k_n \end{pmatrix} \tag{34}\end{aligned}$$由于 $\sigma$ 是一一对应，所以(33)的下一行 $k_1k_2 \cdots k_n$ 就是 $S$ 中的全部元素的一个排列。而(33)的上一行的 $1,2,\cdots,n$ 是通常所说的 $n$ 个位置的标号。因此，一个 $n$ 次置换就是 $1,2,\cdots,n$ 的一个全排列。
(33)只是置换的一种表示法。其实置换 $\sigma$ 的表示(33)中，上一行不一定必须按 $1,2,\cdots,n$ 的顺序写，而可按任何次序写出，只是必须保证 $i$ 在 $\sigma$ 下的像 $k_i$ 一定要写在 $i$ 的正下方即可。由映射的定义，这并未改变 $\sigma$ 的定义。不过，通常习惯于用(33)表示 $\sigma$ 。
置换的这种表示法是十分方便的，特别是对置换的合成更为方便。两个 $n$ 次置换 $\alpha$ 与 $\beta$ 的合成 $\beta\alpha$ 称为乘积。当 $i$ 在 $\alpha$ 下的像用 $(i)\alpha$ 表示时，$\alpha$ 与 $\beta$ 的乘积（合成）就可记为 $\alpha\beta$ ，并且 $(i)\alpha\beta=((i)\alpha)\beta$ ，或简记为切 $i\alpha\beta$ 。
本节用 $(i)\alpha$ 表示 $i$ 在 $\alpha$ 下的像。这样，$\alpha$ 与 $\beta$ 的乘积的计算正好符合通常的从左到右的计算习惯。
置换的逆
由于 $n$ 次置换是一个一一对应，由定理11可知必有逆置换，其逆置换也是一个 $n$ 次置换。若
$$\begin{aligned} \sigma = \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\[5pt] k_1 & k_2 & k_3 & \cdots & k_n \end{pmatrix} \tag{35}\end{aligned}$$则
$$\begin{aligned} \sigma^{-1} = \begin{pmatrix} k_1 & k_2 & k_3 & \cdots & k_n \\[5pt] 1 & 2 & 3 & \cdots & n \end{pmatrix} \tag{36}\end{aligned}$$根据置换的表示可以看出 $\sigma \sigma^{-1} = \sigma^{-1} \sigma = I_X$ 。即 $\sigma$ 的逆 $\sigma^{-1}$ 就是 $\sigma$ 表示式的上下两行交换后所得到的表达式。
所有n次置换之集
令 $S_n$ 为所有 $n$ 次置换之集，则 $S_n=n!$ 。因为 $1,2,\cdots,n$ 的全排列个数为 $n!$ 。
k—循环置换、对换
k—循环置换、对换的定义
定义14：设 $\sigma$ 是 $S$ 上的一个 $n$ 次置换，若 $i_1\sigma=i_2,i_2\sigma=i_3,\cdots,i_{k-1}\sigma=i_k,i_k\sigma=i_1$ ，而 $\forall i \in S \backslash \set{i_1,i_2,\cdots,i_k},i\sigma=i$ ，则称 $\sigma$ 是一个k—循环置换，记为 $(i_1i_2\cdots i_k)$ 。2—循环置换称为对换。
于是，
$$\begin{aligned} (i_1i_2\cdots i_k)= \begin{pmatrix} i_1 & i_2 & \cdots & i_{k-1} & i_k & i_{k+1} & \cdots & i_n \\[5pt] i_2 & i_3 & \cdots & i_k & i_1 & i_{k+1} & \cdots & i_n \end{pmatrix} \tag{37}\end{aligned}$$而对换 $(i \quad j)$ 是
$$\begin{aligned} (i \quad j)= \begin{pmatrix} 1 & 2 & \cdots & i-1 & i & i+1 & \cdots & \cdots & j-1 & j & j+1 & \cdots & n \\[5pt] 1 & 2 & \cdots & i-1 & j & i+1 & \cdots & \cdots & j-1 & i & j+1 & \cdots & n \end{pmatrix} \tag{38}\end{aligned}$$的简写。
k—循环置换、对换的性质
定理15：设 $(i_1i_2\cdots i_k)$ 为 $S$ 上的一个 $n$ 次k—循环置换。则
$$\begin{aligned} (i_1i_2\cdots i_k) =& (i_2i_3\cdots i_ki_1) = (i_3i_4\cdots i_ki_1i_2) \\[5pt] =& \cdots = (i_ki_1i_2\cdots i_{k-1}) \\[5pt] =& (i_1i_2)(i_1i_3)\cdots(i_1i_k) \tag{39}\end{aligned}$$〔证明(定理15)〕 $\displaystyle (i_1i_2\cdots i_k)=\begin{pmatrix} i_1 & i_2 & \cdots & i_{k-1} & i_k & i_{k+1} & \cdots & i_n \\[5pt] i_2 & i_3 & \cdots & i_k & i_1 & i_{k+1} & \cdots & i_n \end{pmatrix}$ ，而
$$\begin{aligned} (i_2i_3\cdots i_ki_1)=\begin{pmatrix} i_2 & \cdots & i_{k-1} & i_k & i_1 & i_{k+1} & \cdots & i_n \\[5pt] i_3 & \cdots & i_k & i_1 & i_2 & i_{k+1} & \cdots & i_n \end{pmatrix}=\begin{pmatrix} i_1 & i_2 & \cdots & i_{k-1} & i_k & i_{k+1} & \cdots & i_n \\[5pt] i_2 & i_3 & \cdots & i_k & i_1 & i_{k+1} & \cdots & i_n \end{pmatrix} \tag{40}\end{aligned}$$因此 $(i_1i_2\cdots i_k) = (i_2i_3\cdots i_ki_1)$ 。同理可证 $(i_1i_2\cdots i_k) = (i_2i_3\cdots i_ki_1) = (i_3i_4\cdots i_ki_1i_2) = \cdots = (i_ki_1i_2\cdots i_{k-1})$ 。而
$$\begin{aligned} (i_1i_2)(i_1i_3)\cdots(i_1i_k) =& \begin{pmatrix} i_1 & i_2 & \cdots \\[5pt] i_2 & i_1 & \cdots \end{pmatrix} \begin{pmatrix} i_1 & i_2 & i_3 & \cdots \\[5pt] i_3 & i_2 & i_1 & \cdots \end{pmatrix} \cdots(i_1i_k) \\[25pt] =& \begin{pmatrix} i_1 & i_2 & i_3 & \cdots \\[5pt] i_2 & i_3 & i_1 & \cdots \end{pmatrix}\cdots(i_1i_k)\\[25pt] =& \cdots = \begin{pmatrix} i_1 & i_2 & i_3 & \cdots & i_k\\[5pt] i_2 & i_3 & i_4 & \cdots & i_1 \end{pmatrix} = (i_1i_2\cdots i_k) \tag{41}\end{aligned}$$证毕
定理16： $(i \quad j)^{-1}=(i \quad j)$ 且 $(i_1i_2\cdots i_k)^{-1}=(i_ki_{k-1}\cdots i_2 i_1)$ 。
$$\begin{aligned} (i \quad j)^{-1} = \begin{pmatrix} \cdots & i & \cdots & j & \cdots \\[5pt] \cdots & j & \cdots & i & \cdots \end{pmatrix}^{-1} = \begin{pmatrix} \cdots & j & \cdots & i & \cdots \\[5pt] \cdots & i & \cdots & j & \cdots \end{pmatrix} = \begin{pmatrix} \cdots & i & \cdots & j & \cdots \\[5pt] \cdots & j & \cdots & i & \cdots \end{pmatrix} =(i \quad j) \tag{42}\end{aligned}$$且
$$\begin{aligned} (i_1i_2\cdots i_k)^{-1}=& \begin{pmatrix} i_1 & i_2 & \cdots & i_{k-1} & i_k & \cdots \\[5pt] i_2 & i_3 & \cdots & i_k & i_1 & \cdots \end{pmatrix}^{-1} \\[25pt] =& \begin{pmatrix} i_2 & i_3 & \cdots & i_k & i_1 & \cdots \\[5pt] i_1 & i_2 & \cdots & i_{k-1} & i_k & \cdots \end{pmatrix} \\[25pt] =& \begin{pmatrix} i_k & i_{k-1} & \cdots & i_2 & i_1 & \cdots \\[5pt] i_{k-1} & i_{k-2} & \cdots & i_1 & i_k & \cdots \end{pmatrix} \\[25pt] =& (i_ki_{k-1}\cdots i_2 i_1) \tag{43}\end{aligned}$$证毕
恒等置换
约定恒等置换 $I = \begin{pmatrix} 1 & 2 & 3 & \cdots & n \\[5pt] 1 & 2 & 3 & \cdots & n \end{pmatrix}$ 简记为 $(1)$ 或 $(2)$ ，···，$(n)$ ，并把 $(i)$ 称为1—循环置换。
不相交的循环置换
对 $k = 1,2,\cdots,n$ ，k—循环置换统称为循环置换。设 $(i_1i_2\cdots i_k)$ 与 $j_1j_2 \cdots j_r$ 是两个循环置换，如果 $\set{i_1,i_2,\cdots,i_k} \cap \set{j_1,j_2,\cdots,j_r}=\varnothing$ ，则称这两个循环置换是没有共同数字的循环置换（不相交）。
定理17：设 $\sigma = (i_1i_2\cdots i_k)$ 与 $\tau=\set{j_1j_2\cdots j_r}$ 是两个没有共同数字的循环置换，则 $\alpha$ 和 $\beta$ 可交换，即 $\alpha\beta=\beta\alpha$ 。
〔证明(定理17)〕 $\forall i \in \set{1,2,\cdots,n}$ ，①如果 $i\alpha \ne i$ ，则由 $\alpha,\beta$ 不相交可得 $i\beta = i$ ，所以 $i \beta \alpha = i \alpha$ 。由于 $\alpha$是循环置换，此时也必定有 $(i\alpha)\alpha \ne i \alpha$ ，则由 $\alpha,\beta$ 不相交可得 $i\alpha\beta=i\alpha$ 。因此 $i \beta \alpha = i \alpha = i \alpha \beta$ 。②如果 $i\beta \ne i$ ，类似可得 $i \alpha \beta = i \beta = i \beta \alpha$ 。③如果 $i \alpha = i = i \beta$ ，则 $i \alpha \beta = i \beta = i$ ，$i \beta \alpha = i \alpha = i$ ，即 $i \alpha \beta = i \beta \alpha$ 。注意不存在 $i\alpha\ne i$ 且 $i \beta \ne i$ 的情况，因为 $\alpha,\beta$ 不相交。因此，无论无论是那种情况都有 $i \alpha \beta = i \beta \alpha$ ，即 $\alpha \beta = \beta \alpha$ 。
证毕
循环置换的幂
设 $\alpha$ 为一个 $n$ 次置换，令 $\alpha^0=I,\alpha^1=\alpha,\alpha^2=\alpha \circ \alpha,\cdots, \alpha^k = \alpha^{k-1}\circ\alpha$ 。
定理18：设 $\gamma = (i_1i_2\cdots i_r)$ ，则 $\gamma^r=I$ 且 $1 \le k < r$ 时 $\gamma^k \ne I$ 。
〔证明(定理18)〕对 $1 \le k \le r$ 来说，由(37)可得当 $j+k \le r$ 时，$i_j \gamma^k = i_{j+1} \gamma^{k-1} = i_{j+2} \gamma^{k-2} = \cdots = i_{j+k}$ ；当 $j+k > r$ 时，$i_j \gamma^k = i_{j+1} \gamma^{k-1} = \cdots = i_r \gamma^{j+k-r} = i_1 \gamma^{j+k-r-1} = i_2 \gamma^{j+k-r-2} = \cdots = i_{j+k-r}$ 。取 $k=r$ ，得 $i_j \gamma^r = i_{j+k-r} = i_{j+r-r} = i_j$ ，即 $\gamma^r = I$ 。当 $1 \le k < r$ 时，若 $j+k \le r$ ，则 $i_j \ne i_{j+k}$ ；若 $j+k > r$ ，因为 $r-k > 0$ ，得 $i_j \ne i_{j+k-r}$ 。所以当 $1 \le k < r$ 时 $\gamma^k \ne I$ 。
证毕
置换的分解
置换的循环分解
定理19（置换的循环分解定理）：每个置换都能被分解成若干个没有共同数字的循环置换的乘积。如果不计这些循环置换的顺序，这个分解是唯一的。
〔证明(置换的循环分解定理)〕设 $\sigma$ 是任一 $n$ 次置换，在 $\sigma$ 下变动了 $\set{1,2,\cdots,n}$ 的 $r$ 个符号，即 $1,2,\cdots,n$ 中有 $r$ 个元素使之在 $\sigma$ 下的象不是该元素本身。显然，当 $\sigma=I$ 时定理成立。今假设 $\sigma \ne I$ ，则 $2 \le r \le n$ 。
我们首先证明存在性。对 $r$ 施行归纳证明：首先，当 $r=2$ 时，$\sigma$ 是一个对换，因此分解存在。假设 $r \le k \le 2$ 时分解存在，往证 $r=k+1 \le n$ 时分解存在。取一个被 $\sigma$ 变动的元素，记为 $i_1$ （即 $i_1\sigma\ne i_1$ ）。设 $i_1\sigma=i_2,i_2\sigma=i_3,\cdots$ ，这样就得到了 $i_1,i_2,i_3,\cdots$ 。于是，必有一个最小下标 $l$ ，使得 $i_l \sigma$ 不再是一个新的不同元素了，而是 $i_1,i_2,\cdots,i_{l-1}$ 中的某个 $i_j$ ，即 $i_l \sigma = i_j,1 \le j < l$ 。但 $i_{j-1}\sigma = i_j$ ，而 $\sigma$ 是一一对应，所以 $i_j$ 就只能是 $i_1$ ，即 $i_l \sigma = i_1$ 。于是，得到了一个循环置换 $i_1i_2\cdots i_l,l \le k+1$ 。若 $l=k+1$ ，则 $\sigma$ 就是一个k+1—循环置换，从而结论成立。否则，若 $l \le k$ 。于是
其中
$$\begin{aligned} \tau = \begin{pmatrix} i_1 & \cdots & i_l & i_{l+1} & \cdots & i_n \\[5pt] i_1 & \cdots & i_l & i'_{l+1} & \cdots & i'_n \end{pmatrix} \tag{45}\end{aligned}$$ $\tau$ 只变动了 $k+1-l \le k$ 个符号。由归纳假设，$\tau$ 能被分解成若干个没有共同数字的循环置换的乘积，所以 $\sigma=(i_1i_2\cdots i_l)\tau$ 能被分解成若干个没有共同数字的乘积。
这样，我们就用归纳法证明了分解的存在性。由上证明可知，经若干步后，$\tau$ 必为恒等置换。于是，把那些不在已出现的循环置换中出现的数字分别用1—循环表示，则分解式中每个数字只出现一次。不过，这些1—循环置换代表恒等置换，通常略去不写。
再证明其唯一性。当略去1—循环因子后,这个分解式除了因子顺序外，分解式是唯一的。实际上，若有两个本质不同的分解，则必存在某 $i,j,i\ne j$ ，使得在一个分解中 $i$ 紧跟在 $j$ 后，而在另一分解中不是这样，那么第一 种分解表明 $j \alpha = i$ ，而第二个分解却指出 $j \alpha \ne i$ ，这个矛盾就证明了分解的唯一性。
证毕
置换的循环分解定理的证明过程，具体地给出了实际分解的方法：先找出一个实际变动的符号，在它的后面写上置换中这个符号的象，继续进行，直到不能得出新的符号为止。在这一循环置换闭合后，假如还有实际被变动的符号，就再任取一个被变动的符号，重复上述过程，就得到了第二个循环置换。依次类推。
置换的对换分解
定理20：每个置换都能被分解成若干个对换的乘积。
〔证明(定理20)〕由定理15可知每个循环置换都能被分解成若干个对换的乘积，再由置换的循环分解定理可得每个置换都能被分解成若干个对换的乘积。
证毕
定理21：如果把置换分解成若干个对换乘积，则对换的个数的奇偶性是不变的。
〔证明(定理21)〕假如置换 $\sigma$ 能被分解为 $s$ 个对换之积，又能被分解成 $t$ 个对换之积，我们来证明 $s$ 与 $t$ 的奇偶性相同。为此，考虑 $n$ 个变量 $x_1,x_2,\cdots,x_n$ 的Vandermonde行列式
$$\begin{aligned} D = \begin{vmatrix} 1 & 1 & \cdots & 1 \\[5pt] x_1 & x_2 & \cdots & x_n \\[5pt] x_1^2 & x_2^2 & \cdots & x_n^2 \\[5pt] \vdots & \vdots & & \vdots \\[5pt] x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1} \end{vmatrix} \tag{46}\end{aligned}$$如将 $\sigma$ 的每个对换因子 $(i,j)$ 看着是使 $D$ 中的第 $i、j$ 两列互换，则从 $\sigma$ 的第一种的 $s$ 个对换之积表示，可知连续施行这 $s$ 个对换于 $D$ 上，就使得 $D$ 变为 $(-1)^sD$ ，而从 $\sigma$ 的第二种 $t$ 个对换之积表示，又使 $D$ 变成 $(-1)^tD$ 。但这二个结果都是将置换 $\sigma$ 施行在 $D$ 上而得的，故应相同。所以，$(-1)^sD=(-1)^tD$ 。由于 $D$ 不恒等于零，故有 $(-1)^s=(-1)^t$ ，即 $s$ 和 $t$ 有相同的奇偶性。
证毕
奇置换与偶置换
定义15：—个置换称为偶置换，如果这个置换能被分解为偶数个对换的乘积；如果一个置换能被分解为奇数个对换的乘积，则这个置换便叫做奇置换。
显然，一个奇置换与一个偶置换的乘积是一个奇置换；任意有限个偶置换的乘积是偶置换；任意奇数个奇置换之积是奇置换；任意偶数个奇置换之积是偶置换。
定理22： $n$ 次奇置换的个数与 $n$ 次偶置换的个数相等，都等于 $\displaystyle\frac{n!}{2}$ 。
〔证明(定理22)〕令所有的 $n$ 次奇置换所构成的集合为 $A$ ，$B$ 为所有的偶置换构成的集合，$S_n$ 为所有的 $n$ 次置换构成的集合，则 $S_n=A \cup B$ 且 $A \cap B = \varnothing$ 。所以 $|S_n|=|A|+|B|=n!$ 。
令 $\sigma \in A$ ，则 $\sigma A = \set{\sigma\tau | \tau \in A} \sube B$ ，所以 $|\sigma A| \le |B|$ ；又 $\sigma B = \set{\sigma\gamma | \gamma \in B} \sube A$ ，所以 $|\sigma B| \le |A|$ 。令 $\varphi: A \to \sigma A, \forall \tau \in A,\varphi(\tau) = \sigma\tau$ ，则可证 $\varphi$ 为一一对应。实际上，若 $\tau_1,\tau_2 \in A$ 且 $\tau_1 \ne \tau_2$ ，但 $\sigma \tau_1 = \sigma \tau_2$ ，两边左乘以 $\sigma^{-1}$ 得到 $\tau_1=\tau_2$ ，矛盾。因此，$\varphi$ 是单射。由于 $\sigma A$ 是直接由 $A$ 的元素生成的，因此 $\varphi$ 是满射。由定义8可知 $\varphi$ 为一一对应。因此由定理1知 $|A|=|\sigma A|$ 。类似地，$|B|=|\sigma B|$ 。所以，$|A| \le |B|, |B| \le |A|$ ，故 $|A|=|B|=\cfrac{n!}{2}$ 。
证毕
二元和n元运算
前面讨论了映射、映射的合成、逆映射等概念，它们分别是函数、 复合函数、反函数概念的推广。函数概念的重要意义远远超出数学领域。数学和自然科学的绝大部分都受着函数关系的支配，一些重要的概念大都与函数（映射）有关。本节从数学的角度，来看数学上几个重要概念与映射的关系。特别是对“运算”这个概念给出了严格的抽象定义。
序列
无穷序列
“序列”是数学中的一个重要概念。序列分为有穷序列和无穷序列，有穷序列在计算机科学中有各种表现形式，而无穷序列是数学分析的重要研究对象之一。序列这个概念不仅涉及对象的集合，还涉及到顺序概念：第1个,第2个,···等等。我们假定已知道了自然数的顺序为1,2,3,···。
定义16：一个从自然数集 $N$ 到集合 $X$ 的映射称为X上的一个无穷序列。而从 $\set{1,2,\cdots,n}$ 到 $X$ 的一个映射称为 $X$ 上的一个长为 $n$ 的（有限）序列。
如果 $a:N \to X, \forall i \in N$ ，令 $a(i)=a_i$ ，则序列 $a$ 就可以直观地借助自然顺序写成
$$\begin{aligned} a_1,a_2,a_3,\cdots \tag{47}\end{aligned}$$并简写成 $\set{a_i}_{i=1}^{\infin}$ ，$a_i$ 称为这个序列的第 $i$ 项。对长为 $n$ 的有穷序列，$a_1,a_2,\cdots,a_n$ 也常记为
$$\begin{aligned} (a_1,a_2,\cdots,a_n)或a_1a_2\cdots a_n \tag{48}\end{aligned}$$实际上，$(a_1,a_2,\cdots,a_n)$ 就是一个 $n$ 元组，在程序设计语言中叫做一个有 $n$ 个元素的一维数组。而记成 $a_1a_2\cdots a_n$ 时，在计算机科学中常把它叫做 $X$ 上的一个长为 $n$ 的符号行或字符串或字。其实，本质上就是 $\set{1,2,\cdots,n}$ 到 $X$ 的一个映射。
子序列
“子序列”就复杂一些了。(47)的子序列，直观上是序列(47)的那些项中选出一些项并按原次序写出的序列。在这里，每一项至多被选一次。而这些选出的下标形成自然数的子序列，后一项大于前一项。于是，我们有
定义17：一个从 $N$ 到 $N$ 的映射 $s$ ，如果 $\forall i,j \in N$ ，$i < j$ 时就有 $s(i) < s(j)$ ，则称 $s$ 为 $N$ 的一个子序列。如果令 $s(i)=n_i$ ，则这个子序列就记为 $n_1,n_2,n_3,\cdots$ ，其中 $n_1 < n_2 < n_3 < \cdots$ 。
定义18：设 $a=\set{a_i}_{i=1}^\infin$ 是 $X$ 上的一个序列，$s=\set{n_i}_{i=1}^\infin$ 是自然数序列的一个子序列，则 $s$ 与 $a$ 的合成 $a \circ s$ 称为 $a$ 的一个子序列。
二元运算的定义和表示
其次，矩阵是数学中的一个重要的数学对象，也是程序设计语言中提供的重要的复合数据类型，即二维数组。一个 $m$ 行 $n$ 列的实矩阵 $A$ ，在程序设计语言C中用一个二维数组表示，并用float a[m][n]说明。在数学上，一个 $m$ 行 $n$ 列的实矩阵 $A$ 是一个从 $\set{1,2,\cdots,m} \times \set{1,2,\cdots,n}$ 到实数集 $R$ 的映射。$\forall (i,j) \in \set{1,2,\cdots,m}$ ，$A(i,j)$ 常记为 $a_{ij}$ ，称为 $A$ 的第 $i$ 行第 $j$ 列的元素。在C语言的说明float a[m][n]中指出了它有 $m$ 行 $n$ 列，而类型说明符float则规定了 $a$ 的元素为实数值。在程序设计语言中，总是用一片连续的存储单元存放 $a$ 的元素。在C中，按行存放；在Fortran语言中，按列存放数组的元素。因此，在概念上，不能把二维数组说成是内存中的一片连续的存储单元，这只是一种存储方式。
在我们的数学教育中，我们遇到过许多运算：数的加法和减法、向量的加法、方阵的加法和乘法、多项式的加法和乘法、函数的微分和积分运算等等。分析这些运算各不相同，运算对象、运算方法不同，有的运算要求参加运算的对象是两个，有的要求运算对象是一个，但都要得出一个“新的”结果。运算是从已知对象产生新对象的方法。抽去运算对象的属性及具体的运算方法，我们便有
二元运算的定义
定义19：设 $X,Y,Z$ 为任意三个非空集合。一个从 $X \times Y$ 到 $Z$ 的映射 $\varphi$ 称为 $X$ 与 $Y$ 到 $Z$ 的一个二元运算或二元代数运算。当 $X=Y=Z$ 时，则称 $\varphi$ 为 $X$ 上的二元运算。
在此定义中，$\varphi$ 称为运算符号，它表示的是运算法则。$X$ 和 $Y$ 是运算对象的集合，$Z$ 是运算结果所在的集合。$\forall (x,y) \in X \times Y$ ，如果 $\varphi(x,y)=z$ ，习惯上记为 $x \varphi y = z$ 。由定义可知，二元运算 $\varphi$ 对 $X \times Y$ 中任一元素对 $(x,y)$ ，必须规定一个唯一的结果元素。当 $\varphi$ 为 $X$ 上的二元代数运算时，$\varphi(x,y) \in X$ ，并且说 $\varphi$ 在 $X$ 上封闭。其次，一般说来，$x\varphi y \ne y \varphi x$ 。
在数学上，习惯把二元运算 $\varphi$ 记成“ $\cdot$ ”“ $\circ$ ”“ $*$ ”等。于是，$\varphi(x,y)$ 或 $x \varphi y$ 就写成 $x \cdot y$ 或 $x \circ y$ 等，甚至记为 $xy$ 。
二元运算的表示
当运算对象集 $A=\set{a_1,a_2,\cdots,a_m},B=\set{b_1,b_2,\cdots,b_m}$ 结果集为 $C$ 时，$A$ 与 $B$ 到 $C$ 的二元代数运算“ $\circ$ ”常用一个二维表来定义，称为“乘法”表，见图3。表中的第 $i$ 行与第 $j$ 列交叉处写上 $c_{ij}$ ，表示 $a_i \circ b_j = c_{ij}$ 。
图3 乘法表
例1：设 $K=\set{0,1}$ ，在 $K$ 上定义加法和乘法，并分别用“ $+$ ”与“ $\circ$ ”表示加法运算符和乘法运算符。“ $+$ ”和“ $\circ$ ”用图4的两表给出。
图4 加法表和乘法表
易见，“ $+$ ”和“ $\circ$ ”是 $K$ 上的两个不同的二元代数运算。
一元运算与n元运算
除了二元运算外，还有一元运算。例如，求复数的共轭复数，求矩阵的转置矩阵、求函数的导函数、定积分等都是一元运算。抽象地，一元运算就是映射。我们也有三元、四元，乃至n元运算。例如，求n个正整数的最大公因数和最小公倍数，都是n元运算。
定义20：从集合 $X$ 到集合 $Y$ 的任一映射都称为 $X$ 到 $Y$ 的一元运算。若 $X=Y$ ，则 $X$ 到 $X$ 的一元运算称为 $X$ 上的一元运算，也叫做 $X$ 的一个变换。
定义21：设 $A_1,A_2,\cdots,A_n,D$ 为非空集合。一个从 $A_1 \times A_2 \times \cdots \times A_n$ 到 $D$ 的映射 $\varphi$ 称为 $A_1,A_2,\cdots,A_n$ 到 $D$ 的一个n元（代数）运算。如果 $A_1=A_2=\cdots=A_n=D=A$ ，则称 $\varphi$ 为 $A$ 上的n元运算。
最常用的是一元运算和二元运算。在近世代数中更常用的是集合 $X$ 上的一元运算和二元运算。从定义可以看出，代数运算可以相当任意地规定，运算对象和运算方法都可任意规定。但是，如此任意规定的代数运算，很难希望由此能算出什么好的结果。在数学、物理学及其他科学中，在所研究的对象间引入的运算，其目的在于使推理清晰以达到简化科学的逻辑结构的目的。回忆一下，物理学、力学中所使用的一些运算，它大都满足一定的规律，利用它们把已发现的物理规律表述得十分简洁和完美。当然，这些物理规律的发现是通过艰苦和巧妙的实验以及深刻的思考得到的。但是，表述得那么简洁和完美也与选择合适的运算有关。
二元运算的特性
交换律与结合律
定义22：设“ $\circ$ ”是集合 $X$ 上的一个二元代数运算。如果 $\forall a,b,c \in X$ ，恒有 $a \circ b \ne b \circ a$ ，则称二元代数运算“ $\circ$ ”满足交换律。如果 $\forall a,b,c \in X$ ，总有
$$\begin{aligned} (a \circ b) \circ c = a \circ (b \circ c) \tag{49}\end{aligned}$$则称二元代数运算“ $\circ$ ”满足结合律。
结合律是我们熟知的，已往所遇到的那些有用的运算大都适合结合律。但也有不适合结合律的，例如，数的减法就不满足结合律。二元代数运算只告诉我们对两个有次序的元素，在运算下能得到唯一的一个结果元素。但当给定了有次序的三个元素时，在不改变这三个元素的次序下，适当地加以结合才能得出（算出）一个结果。在不改变 $a,b,c$ 的次序下，只有两种组合方法，即 $(a \circ b) \circ c$ 与 $a \circ (b \circ c)$ 。一般说来，$(a \circ b) \circ c = a \circ (b \circ c)$ 。而结合律成立，告诉我们 $(a \circ b) \circ c = a \circ (b \circ c)$ ，所以可简记为 $a \circ b \circ c$ ，而无须加括号注明计算次序。
结合律是二元代数运算的一条重要规律，我们经常引用它而不自觉。但在近世代数中，对所讨论的代数运算往往假定代数运算满足结合律，并且以公理的形式规定下来。可以证明：如果代数运算满足结合律，则对 $X$ 中 $n$ 个有次序的元素 $a_1,a_2,\cdots,a_n$ ，$a_1 \circ a_2 \circ \cdots \circ a_n$ 有意义且由 $a_1,a_2,\cdots,a_n$ 的次序唯一确定。
交换律是说代数运算的结果仅与两个运算对象有关，而与它们的次序无关。可以证明：如果 $X$ 上的二元代数运算“ $\circ$ ”既满足结合律又满足交换律，则 $\forall a_1,a_2,\cdots,a_n \in X$ ，$a_1 \circ a_2 \circ \cdots \circ a_n$ 只与 $a_1,a_2,\cdots,a_n$ 有关，而与它们的次序无关。
分配律
在一个问题中往往有几个运算，这些运算并不是彼此无关的。分配律是刻划两个运算之间的联系的一种运算律。
定义23：设“ $+$ ”与" $\circ$ ”是集合 $X$ 上的两个二元代数运算。如果 $\forall a,b,c \in X$ 恒有
$$\begin{aligned} a \circ (b + c) = (a \circ b) + (a \circ c) \tag{50}\end{aligned}$$则称二元代数运算 $\circ$ 对 $+$ 满足左分配律。如果总有
$$\begin{aligned} (b + c) \circ a = (b \circ a) + (c \circ a) \tag{51}\end{aligned}$$则称 $\circ$ 对 $+$ 满足右分配律。
我们之所以引入左分律与右分配律，是因为二元代数运算“ $\circ$ ”未必满足交换律。如果交换律成立，则左、右分配律重合。
代数系
一个集合不过是一组元素而已，无所谓结构。但引进了代数运算，我们就说有了代数结构，$X$ 与其上的代数运算" $\circ$ “组成了一个代数系或代数结构。一般的，在几个集合之间定义了若干个代数运算后，这个集合及其间的代数运算就形成一个代数系。
在近世代数中，主要研究一个集合 $X$ 上的二元代数运算的代数系 $(X,\circ)$ 以及 $X$ 上的两个代数运算 $\circ$ 与 $+$ 组成的代数系 $X,+,\circ$ 。根据施加于运算上的公理，这些代数系将称为半群、幺半群、群、环、域、布尔代数等等。
单位元素与逆元素
在用公理定义一些代数系时，往往涉及二元代数运算的单位元素，以及由此引出的元素的逆元素的概念。
定义24：设“ $\circ$ ”是 $X$ 上的一个二元代数运算。如果存在一个元素 $e \in X$ 使得 $\forall x \in X$ 恒有 $e \circ x=x \circ e=x$ ，则称 $e$ 为 $\circ$ 的单位元素。如果在代数系 $(X,\circ)$ 中，$\circ$ 有单位元素 $e$ ，$a$ 为 $X$ 中某个元素，当 $\exists b \in X$ 使得 $a \circ b = b \circ a = e$ ，则称 $b$ 为 $a$ 的逆元素。
若 $b,c$ 都是 $a$ 的逆元素，则 $a \circ b = b \circ a = e,a \circ c = c \circ a = e$ 。于是，$b = e \circ b = (c \circ a) \circ b$ 。所以当结合律成立时，$(c \circ a) \circ b = c \circ (a \circ b) = c \circ e = c$ ，即 $b=c$ 。
例2：在例1中，定义了 $\set{0,1}$ 上的两个二元运算：加法 $+$ ，乘法 $\circ$ 。容易验证，$0$ 是加法 $+$ 的单位元素，$1$ 是乘法的单位元素；加法和乘法满足结合律和交换律；乘法对加法满足分配律； $0$ 对加法的逆元是 $0$ ，$1$ 对加法的逆元是 $1$ 。$1$ 对乘法的逆元为 $1$ ，$0$ 对乘法的逆元不存在。以后，我们把这个代数系称为域，或域 $\text{K}$ 。
同构
当抽象地研究代数系时，其中的运算对象是什么是不管的，运算的法则是什么也是不管的。只知道这些运算对象与运算满足公理中规定的性质。因此，如何比较两个抽象代数系在本质上是否一样就十分重要。但本质一样指的什么呢？
定义25：设 $(S,+,\circ)$ 与 $(T,\oplus,*)$ 为两个代数系。如果存在一个一一对应 $\varphi:S \to T$ ，使得 $\forall x,y \in S$ ，有
$$\begin{aligned} \varphi(x+y)=\varphi(x) \oplus \varphi(y) \tag{52}\end{aligned}$$ $$\begin{aligned} \varphi(x \circ y) = \varphi(x) * \varphi(y) \tag{53}\end{aligned}$$
则称代数系 $(S,+,\circ)$ 与 $(T,\oplus,*)$ 同构，并记为 $S \cong T$ ，而 $\varphi$ 称为这两个代数系间的一个同构。
由此可知，同构的代数系本质上是一样的，区别的仅是运算对象的命名不同，代数运算的命名不同而已。如果重新命名，则它们是同一结构。$\varphi$ 就是这个命名法则。
代数系同构可推广到其他情况。
集合的特征函数
集合是一个比较直观的对象。在实际应用中，出现的集合往往都是某个全集 $X$ 的子集。若 $E \sube X$ ，对 $X$ 的每个元素 $x,x \in E$ 或 $x \notin E$ ，即 $x$ 是 $E$ 的元素，或 $x$ 不是 $E$ 的元素。于是，给定了 $E$ ，就确定了 $X$ 的元素与“是”或“否”间的一个对应关系。对应于“是”的元素表明该元素在 $E$ 中，对应于“否”的元素，表明了它不在 $E$ 中。这个对应关系实质上就刻划了 $E$ 。
特征函数的定义
定义26：设 $X$ 是一个集合，$E \sube X$ 。从 $X$ 到 $\set{0,1}$ 的如下的一个映射 $\chi_E$ 称为 $E$ 的特征函数： $\forall x \in X$ ，
$$\begin{aligned} \chi_E = \begin{cases} 1,如果x \in E \\[5pt] 0,如果 x\notin E \end{cases} \tag{54}\end{aligned}$$于是，集合 $E$ 的特征函数 $\chi_E$ 由 $E$ 唯一确定。显然，若 $E$ 与 $F \sube X$ ，且 $E \ne F$ ，则 $\chi_E \ne \chi_F$ 。而且若 $E \sube F$ ，则 $\forall x \in X,\chi_E(x) \le \chi_F(x)$ 。$\chi_\varnothing \equiv 0$ ，即 $\forall x \in X, \chi_\varnothing(x)=0$ ； $\chi_X \equiv 1$ ，即 $\forall x \in X, \chi_X(x)=1$ 。
特征函数的代数系统
令 $Ch(X)=\set{\chi | \chi: X \to \set{0,1}}$ 。
在例1中我们定义了 $\set{0,1}=K$ 上的加法和乘法，形成了一个代数系 $(\set{0,1},+,\cdot)$ （这里为了方便用“ $\cdot$ ”代替了“ $\circ$ ”）。在例2中讨论了它们的性质，并说以后称之为域，简称域 $\mathbf{K}$ 。由于 $Ch(X)$ 中元 $\chi$ 的值域包含在 $K$ 中，所以可以借助 $\mathbf{K}$ 中加法、乘法定义 $Ch(X)$ 中的加法和乘法，分别用“ $\lor$ ”与“ $\land$ ”表示。
$\forall \chi,\chi' \in Ch(X)$ 及 $x \in X$
$$\begin{aligned} (\chi \lor \chi')(x)=\chi(x)+\chi'(x)+\chi(x)\cdot\chi'(x) \tag{55}\end{aligned}$$ $$\begin{aligned} (\chi \land \chi')(x)=\chi(x)\cdot \chi'(x) \tag{56}\end{aligned}$$
其次，在 $Ch(X)$ 中定义 $\chi$ 的补 $\chi^c$ 为
$$\begin{aligned} \chi^c(x)=1-\chi(x) \tag{57}\end{aligned}$$ 其中减号为 $\mathrm{K}$ 中加法的逆运算（在这里，$0-0=0,0-1=1,1-0=1,1-1=0$ ）。
于是，$(Ch(X),\lor,\land,^c)$ 就是一个代数系统。
集合运算的代数系统和特征函数的代数系统同构
定理23：设 $X$ 是一个集合，则代数系 $(2^X,\cup,\cap,^c)$ 与 $(Ch(X),\lor,\land,^c)$ 同构。
〔证明(定理23)〕令 $\Phi:2^X\to Ch(X)$ ，其定义为 $\forall E \in 2^X,\Phi(E)=\chi_E$ 。由定义26可知，$\Phi$ 为单射。而且 $\forall \chi \in Ch(X)$ ，令 $F=\set{x | \chi(x)=1,x \in X}$ ，则 $\Phi(F)=\chi=\chi_F$ 。所以 $\Phi$ 为满射，故 $\Phi$ 为一一对应，即 $2^X$ 与 $Ch(X)$ 对等。
设 $E、F \sube X$ ，往证 $\Phi(E \cap F) = \chi_E \cdot \chi_F$ 。由定义可知 $\Phi(E \cap F)=\chi_{E \cap F}$ ，所以只需证明 $\chi_{E\cap F}=\chi_E \cdot \chi_F$ 即可。为此，设 $x \in X$ ，则当 $x \in E \cap F$ 时，$x \in E$ 且 $x \in F$ ，从而 $\chi_{E \cap F}(x)=1=1 \cdot 1 = \chi_E(x) \cdot \chi_F(x)$ 。如果 $x \notin E \cap F$ ，则 $x \notin E$ 或 $x \notin F$ ，从而 $\chi_E(x)=0$ 或 $\chi_F(x)=0$ 。于是
总之也有 $\chi_{E \cap F}(x)=\chi_E(x) \cdot \chi_F(x)$ ，故 $\chi_{E \cap F}=\chi_E \cdot \chi_F = \chi_E \land \chi_F$ 。
设 $E、F \sube X$ ，往证 $\Phi(E \cup F) = \chi_E + \chi_F+\chi_E \cdot \chi_F$ 。由定义可知 $\Phi(E \cup F)=\chi_{E \cup F}$ ，所以只需证明 $\chi_{E\cap F}=\chi_E \cdot \chi_F$ 即可。为此，设 $x \in X$ ，则当 $x \in E \cup F$ 时，$x \in E, x \notin F$ 或 $x \notin E,x \in F$ 或 $x \in E, x \in F$ ，从而
如果 $x \notin E \cup F$ ，则 $x \notin E$ 且 $x \notin F$ ，从而 $\chi_E(x)=0$ 且 $\chi_F(x)=0$ 。于是 $\chi_{E \cup F}(x) = 0 = 0 + 0 = \chi_E(x) + \chi_F(x) + \chi_E(x) \cdot \chi_F(x)$ 。总之也有 $\chi_{E \cup F}(x)=\chi_E(x) + \chi_F(x) + \chi_E(x)\cdot\chi_F(x)$ ，故 $\chi_{E \cap F}=\chi_E + \chi_F + \chi_E \cdot \chi_F = \chi_E \lor \chi_F$ 。
下面证明 $\Phi(E^c)=\chi_E^c$ 。为此，只需证明 $\chi_{E^c}=\chi_E^c$ 。设 $x \in X$ ，若 $x \in E$ ，则 $x \notin E^c$ ，从而 $\chi_E(x)=1,\chi_{E^c}(x)=0$ 。于是，$\chi_E^c(x)=0=1-1=1-\chi_E(x)=\chi_E^c(x)$ ，故 $\chi_{E^c}(x)=\chi_E^c(x)$ ；若 $x \notin E$ ，则 $x \in E^c$ ，所以 $\chi_E(x)=0,\chi_{E^c}(x)=1$ ，因此
故 $\chi_{E^c}(x)=\chi_E^c(x)$ 。总之，$\forall x \in X$ ，$\chi_{E^c}(x)=\chi_E^c(x)$ .因此，$\chi_{E^c}=\chi_E^c$ 。即 $\Phi(E^c)=\chi_E^c$ 。
综上，由定义25可知，代数系 $(2^X,\cup,\cap,^c)$ 与 $(Ch(X),\lor,\land,^c)$ 同构。
证毕
设 $E、F \in 2^X$ ，由集合及其运算-(94)得 $E \backslash F = E \cap F^c$ ，所以
$$\begin{aligned} \chi_{E \backslash F}=\chi_{E \cap F^c} = \chi_E \land \chi_{F^c} = \chi_E \land X_F^c \tag{61}\end{aligned}$$ $$\begin{aligned} \chi_{E \triangle F} = (\chi_E \land \chi_F^c) \lor (\chi_F \land \chi_E^c) \tag{62}\end{aligned}$$
可见，$(2^X,\cup,\cap,^c)$ 同构于 $(Ch(X),\lor,\land,^c)$ 。尽管对象不同、运算不同，但它们的元素一一对应，并在同构 $\Phi$ 下，其运算也相互对应，运算的性质和规律也一样。因此，本质是一样的。于是，$2^X$ 与 $Ch(X)$ 可视为一样，只是表现形式不同而已。因此，$\chi_E$ 就是 $E$ 的另一表示方式。集合比较直观，而特征函数较抽象，但有启发性，易于推
广。L.A.Zadeh正是抓住了这一点，把特征函数的概念加以推广，得到了模糊集合（fuzzy set）的概念。
在计算机科学中，经常需要对集合实行各种各样的操作。把在一个集合上实行的几种不同操作结合起来考虑，得到一些重要的以集合为基础的抽象数据类型，这些抽象的数据类型具有专门的名称，并且有高效的实现方法。如何有效地实现一个以集合为基础的抽象数类型，依赖于该集合的大小，以及对这个集合所实行的操作。
当我们所讨论的集合都是全集 $X=\set{1,2,\cdots,M}$ 的一个子集，而 $M$ 是一个不太大的固定整数时，可以用位向量（布尔数组）来实现。位向量是这样来表示集合的，位向量的第 $i$ 位为true（真，在计算机中常用1表示）当且仅当 $i$ 是这个集合的元素。用这种方法表示 $X$ 的子集合，实际上就是用特征函数来表示集合。用这种方法表示集的优点是“插入”操作、“删除”操作、“成员资格”操作都可在常数时间内完成。而“并”、“交差”操作所需的时间正比于全集 $X$ 的大小。由于C语言有位操作，所以用C语言实现是方便的。
无论如何，在写程序时，只要面临的集合能处理成全集 $\set{1,2,\cdots,M}$ 的子集，就可以考虑用位向量表示它而不必顾及它的大小。当全集是一个有限集，但不是一个连续整数组成的集时，仍然可以用位向量来表示这个全集的子集，这时只需要建立全集的成员与整数 $\set{1,2,\cdots,M}$ 之间的一个一一对应即可。
知识可以传授，但智慧不能。― Hermann Hesse, 《悉达多》