离散数学-2

设 $a_1 < a_2 < \ldots < a_n$ 是 $n$ 个实数，$A = \{a_1, \ldots, a_n\}$，$\varphi$ 是 $A$ 到 $A$ 的可逆映射。如果 $a_1 + \varphi(a_1) < a_2 + \varphi(a_2) < \ldots < \varphi(a_n) + a_n$，试证：$\varphi = I_A$。

[证] 设 $\varphi(a_1) \neq a_1$，则由 $\varphi$ 是可逆的，故为一一对应，从而必有 $j, j > 1$，使 $\varphi(a_j) = a_1$。

于是，对任何正整数 $i < j$，有 $a_i + \varphi(a_i) < a_j + \varphi(a_j)$。但由于 $a_i \geq a_1$，$\varphi(a_j) = a_1$，所以

$$a_1 + \varphi(a_1) \leq a_i + \varphi(a_i) < \varphi(a_j) + a_j = a_j + a_1,$$

故 $\varphi(a_i) < a_j$，从而 $\varphi(a_i) = a_k, k < j$。这表明当 $\varphi(a_1) = a_p$ 时，$p < j$。于是，对任意的 $i, i < j$，$\varphi(a_i) \in \{a_1, a_2, \ldots, a_{j-1}\}$。

从而 $\varphi$ 限制在 $\{a_1, a_2, \ldots, a_{j-1}\}$ 上时，$\varphi$ 也是一个一一对应(若不是,则要么违反在整个定义域上的可逆性,要么违反上面的大小限制)，于是有 $i$，使 $\varphi(a_i) = a_1$，矛盾。故 $\varphi(a_1) = a_1$。

类似可证 $\varphi(a_2) = a_2, \ldots, \varphi(a_n) = a_n$，即 $\varphi = I_A$。[证毕]

注意：如 $A$ 为无穷集，则命题不真，例如 $A = \mathbb{N}$ 时，令 $\varphi(n) = n + 1$，则

$$1 + \varphi(1) = 3 < \varphi(2) + 2 = 5 < 3 + \varphi(3) = 7 \ldots,\varphi \neq I_A$$

设 $u_1, u_2, \cdots, u_{mn+1}$ 是一个两两不相交的整数构成的数列，则必有长至少为 $n+1$ 的递增子序列或有长至少为 $m+1$ 的递减子序列。

[证] 令 $A = \{u_1, u_2, \cdots, u_{mn+1}\}$，则 $|A| = mn + 1$。

设以 $u_i$ 为首项的最长递增子序列的长度为 $\ell^+_i$，

设以 $u_i$ 为首项的最长递减子序列的长度为 $\ell^-_i$。

反证法：假设题中结论不成立，则 $\ell^+_i \leq n, \ell^-_i \leq m, i=1,2,3,\cdots,mn+1$。

令 $\varphi: A \to \{1,2,\cdots,n\} \times \{1,2,\cdots,m\}, \forall u_i \in A, \varphi(u_i) = (\ell^+_i, \ell^-_i)$，则 $\varphi$ 是单射。

实际上，$\forall u_i, u_j \in A$ 且 $u_i \neq u_j (i < j)$，则

若 $u_i > u_j$，则 $\ell^-_i > \ell^-_j$，所以 $(\ell^+_i, \ell^-_i) \neq (\ell^+_j, \ell^-_j)$；

即 $\varphi(u_i) \neq \varphi(u_j)$。

若 $u_i < u_j$，则 $\ell^+_i > \ell^+_j$，所以 $(\ell^+_i, \ell^-_i) \neq (\ell^+_j, \ell^-_j)$；

即 $\varphi(u_i) \neq \varphi(u_j)$。

故 $\varphi$ 为单射，从而就有 $mn + 1 \leq mn$ 矛盾。

一些人组成的团体 $S$，试证可以把 $S$ 分为两组，使得每个人在其所在的组中的朋友数至多是他在团体 $S$ 中的朋友数的一半。

[证] 对 $S$ 的任一二划分 $\{A, A^c\}$，令

$$f(A, A^c) = \{(a, b) \mid (a, b) \in A \times A^c \text{ 且 } a \text{ 与 } b \text{ 互为朋友}\}$$

由于 $|S| < \infty$，所以 $S$ 的 2-划分为有限个。所以，存在 $S$ 的一个 2-划分 $\{B, B^c\}$，使 $f(B, B^c)$ 最大。我们断言 $B$ 与 $B^c$ 即为所求。

实际上，$\forall a \in S$，若 $a \in B$ 且 $a$ 在 $B$ 中的朋友数 $d > a$ 在 $B^c$ 中的朋友数 $d'$，则把 $a$ 调到 $B^c$ 中得分组 $B \setminus \{a\}$ 与 $B^c \cup \{a\}$，分别记为 $B', B'^c$。于是

$$f(B', B'^c) = f(B, B^c) + (d - d') > f(B, B^c)$$

这与 $f(B, B^c)$ 为最大值的假设相矛盾。

已知 $m$ 个整数 $a_1, a_2, \cdots, a_m$，试证：存在两个整数 $k, \ell$，$0 \leq k < \ell \leq m$，使得 $a_{k+1} + a_{k+2} + \cdots + a_\ell$ 能被 $m$ 整除。

【证】 考察下式：

$a_1$

$a_1 + a_2$

$a_1 + a_2 + a_3$

$\vdots$

$a_1 + a_2 + \cdots + a_m$

若第 $i$ 式能被 $m$ 整除，则显然成立，此时 $k = 0, \ell = i$；

若任一式都不能被 $m$ 整除，则考察各式被 $m$ 整除后的余数，如下式：

$a_1 = q_1 m + r_1$

$a_1 + a_2 = q_2 m + r_2$

$a_1 + a_2 + a_3 = q_3 m + r_3$

$\vdots$

$a_1 + a_2 + \cdots + a_m = q_m m + r_m$

由于每一个都不能被 $m$ 整除，故共有 $m$ 个余数—相当于 $m$ 个物体。而任意整数被 $m$ 除后的余数有 $m-1$ 种可能（即 $1, 2, \ldots, m-1$）—相当于 $m-1$ 个抽屉。

由抽屉原理，必有两个余数相等，设为 $r_i = r_j$，其中 $i < j$。

于是 $(a_1 + \cdots + a_j) - (a_1 + \cdots + a_i) = a_{i+1} + \cdots + a_j$ 能被 $m$ 整除。

此时 $k = i, \ell = j$，结论成立。

在一个半径为 16 的圆内任意放入 650 个点。给你一个形似垫圈的圆环，此圆环的外半径为 3, 内半径为 2。现在要求你用这个垫圈盖住这 650 个点中的至少 10 点，这可能吗？证明你的结论。

[证]:

每个点可接触区面积:

$$S=\pi (3^2-2^2)=5\pi$$

可接触区的实际面积:

$$S'=\pi (16+3)^2=361\pi$$

可能接触的总面积:

$$nS=650*5\pi=3250\pi$$

平均一个位置接触的可接触区个数:

$$\frac{3250\pi}{361\pi}\approx9.002 \gt 9$$

故至少存在一个点接触10个可接触区(反证:若不然,则上面不可能大于9)

设 $a_1 a_2 \cdots a_n$ 为 $1, 2, \cdots, n$ 的任一排列。如果 $n$ 是奇数且

$$(a_1 - 1)(a_1 - 2) \cdots (a_n - n) \neq 0,$$

则乘积为偶数

[证]

反证法：若 $(a_1 - 1)(a_2 - 2) \cdots (a_n - n)$ 为奇数，则 $(a_i - i)$ 中的 $a_i$ 与 $i$ 必是一个为奇数，一个为偶数。而 $n$ 为奇数，故奇数个数为 $\left\lfloor \frac{n}{2} \right\rfloor + 1$ 比偶数 $\left\lfloor \frac{n}{2} \right\rfloor$ 多一个，这是不可能的。

证法 2：当 $n$ 为奇数时，$1, 2, \ldots, n$ 中有 $\frac{n-1}{2}$ 个偶数，$\frac{n+1}{2}$ 个奇数，奇数的个数比偶数的个数多一个。于是，$a_1, a_2, \ldots, a_n$，$1, 2, \ldots, n$ 中恰有 $n+1$ 个奇数。然而只有 $n$ 个因子（$n$ 个盒子），先把 $a_1, a_2, \ldots, a_n$ 依次放入 $n$ 个盒中，然后把 $1, 2, \ldots, n$ 依次放入 $n$ 个盒中，这样就把 $n+1$ 个奇数放入了 $n$ 个盒中。因此，有一个盒子 $i$ 中的两个数均为奇数，对应的因子 $a_i - i$ 就是偶数。

珍珠 4 颗，有真有假。真珍珠重量相同且为 $p$，假珍珠重量相同且为 $q$，$p > q$。用秤（而不是天平）仅称量 3 次查出真假，应该怎么做？

【解】 先用 $<1>$、$<2>$、$<3>$、$<4>$ 为 4 个珍珠编号且代表其重量。$<1> + <2>$ 表示这两个珍珠放在一起称且代表其重量。其他类推。

称 $<1> + <2>$，$<1> + <3>$，$<2> + <3> + <4>$，得如下的方程组：

$$\begin{align*} <1> + <2> &= a_1 \\ <1> + <3> &= b_1 \\ <2> + <3> + <4> &= c_1 \end{align*}$$

其中 $a_1, b_1, c_1$ 是在称量后得到的常数。显然，$a_1$ 为 $2p$ 或 $2q$ 或 $p+q$。令

$$x = \frac{<1> - q}{p - q}, \quad y = \frac{<2> - q}{p - q}, \quad z = \frac{<3> - q}{p - q}, \quad \omega = \frac{<4> - q}{p - q},$$

$$a = \frac{a_1 - 2q}{p - q}, \quad b = \frac{b_1 - 2q}{p - q}, \quad c = \frac{c_1 - 2q}{p - q},$$

则我们有

$$\begin{align*} x + y &= a \\ x + z &= b \\ y + z + \omega &= c \end{align*}$$

其中 $x, y, z, \omega \in \{0, 1\}$，$a, b, c$ 为已知的常数。

由于

$$2(x + y + z) + \omega = a + b + c$$

所以如果 $a + b + c$ 为偶数，则 $\omega = 0$；如果 $a + b + c$ 为奇数，则 $\omega = 1$。于是，根据 $a + b + c$ 的奇偶性决定方程组的解。再由算得的结果 $x, y, z, \omega$ 中是 1 的代表相应的珍珠为真，为 0 的代表相同的珍珠为假珍珠。

设 $f: X \to Y$。证明：$f$ 是满的当且仅当 $\forall E \in 2^Y$ 有 $f(f^{-1}(E)) = E$

[证]

$\Leftarrow$ if $\forall E \in 2^Y$ 有 $f(f^{-1}(E)) = E$，往证 $f$ 是满的。假设 $f$ 不是满射，则 $\exists y_0 \in Y$ 使 $\forall x \in X, f(x) \neq y_0$。令 $E = \{y_0\}$，则 $f^{-1}(E) = \phi$，$\therefore \phi = f(f^{-1}(E)) = E = \{y_0\}$，矛盾。所以，$f$ 是满的

$\Rightarrow$ 显然，$f(f^{-1}(E)) \subseteq E$。设 $y \in E$，则由于 $f$ 是满的，所以 $\forall y \in E, \exists x \in X$ 使 $f(x) = y$，故 $x \in f^{-1}(E)$ 且 $y \in f(f^{-1}(E))$。因此，$E \subseteq f(f^{-1}(E))$，故 $f(f^{-1}(E)) = E$。

设 $f: X \to Y$。证明：$f$ 是单射当且仅当 $\forall F \in 2^X$ 有 $f^{-1}(f(F)) = F$

[证]

$\Leftarrow$ 若不然, $\exists x_1, x_2 \in X, x_1 \neq x_2$ 使 $f(x_1) = f(x_2)$。令 $F = \{x_1\}$ 则 $f(F) = f(\{x_1\}) = \{f(x_1)\}, f^{-1}(f(F)) = \{x_1, x_2\} \neq \{x_1\} = F$，矛盾。

$\Rightarrow$ 由单射的性质,显然。

设 $f: X \to Y, A \subseteq X$，则 $(f(A))^c \subseteq f(A^c)$ 成立吗？

提示:既不是满射,也不是单射

[解]

尝试举反例即可.

反例：设 $X = \{1, 2, 3\}, Y = \{a, b, c\}$。

$f: X \to Y, f(1) = a, f(2) = a, f(3) = b$。

令 $A = \{1, 2\}$，则 $A^c = \{3\}$。

$f(A) = \{a\}$，$(f((A))^c = \{b, c\}$，但 $f(A^c) = b$。

设 $X$ 是一个无穷集合，$f: X \to Y$。证明：存在 $X$ 的一个真子集 $E$ 使得 $f(E) \subseteq E$

[证] 取 $x_0 \in X$，

令 $x_1 = f(x_0), x_2 = f(x_1), \cdots, x_n = f(x_{n-1}), \cdots$。若到某一位与前面有重复项，设为第 $k$ 项，即 $f(x_k) = x_i (i < k)$。令 $E = \{x_0, x_1, x_2, \cdots, x_k\} \subset X$，则 $f(E) \subseteq E$ 且 $E \subset X$。

若 $x_i$ 互不相同，令 $E_1 = X \setminus \{x_0\} \subset X$，则 $f(E_1) \subseteq E_1$。

[不去掉 $x_0$ 有 $E_1 = X$]

设 $M$ 是一个非空集合，$\varphi: M \to M$，$N \subseteq M$。令 $\mathcal{A} = \{P | P \subseteq M \text{ 且 } N \subseteq P, \varphi(P) \subseteq P\}$，$G = \bigcap_{P \in \mathcal{A}} P$。

试证：

(1) $G \in \mathcal{A}$

(2) $N \cup \varphi(G) = G$

[证] (1) $\forall P \in \mathcal{A}$，$G = \bigcap_{P \in \mathcal{A}} P \subseteq P \subseteq M$；$\forall P \in \mathcal{A}$，$N \subseteq P$，所以 $N \subseteq G$；$\varphi(G) = \varphi(\bigcap_{P \in \mathcal{A}} P) \subseteq \bigcap_{P \in \mathcal{A}} \varphi(P) \subseteq \bigcap_{P \in \mathcal{A}} P = G$。因此 $G \in \mathcal{A}$。

(2) 显然有 $N \cup \varphi(G) \subseteq G$。$N \cup \varphi(G) \subseteq M$，$N \subseteq N \cup \varphi(G)$，只要证明 $\varphi(N \cup \varphi(G)) \subseteq N \cup \varphi(G)$ 即可知 $N \cup \varphi(G) \in \mathcal{A}$

从而有 $G \subseteq N \cup \varphi(G)$

$\forall y \in \varphi(N \cup \varphi(G))$，$\exists x \in N \cup \varphi(G)$，使得 $y = \varphi(x)$

因为 $x$ 是 $N \cup \varphi(G)$ 中元素，则可分以下二种情况讨论

• (1) $x$ 的像在 $N$ 中，则 $\varphi(x) \in N \cup \varphi(G)$；

• (2) $x$ 的像不在 $N$ 中，又分三种情况：

  • ① $\varphi(x) = x$
  • ② $\varphi(x) = y$ 时必有 $\varphi(y) = x$
  • ③ $\varphi(x) = y$ 且 $\varphi(y) = z$ 时必有 $\varphi(x) = z$（否则与 $\varphi(P) \subseteq P$ 矛盾）。
  • 这三种情况下均有 $\varphi(x) \in N \cup \varphi(G)$

设 $X, Y, Z$ 是三个非空集合，$|Z| \geq 2$。证明：$f: X \to Y$ 是满射当且仅当不存在从 $Y$ 到 $Z$ 的映射 $g_1$ 和 $g_2$，使得 $g_1 \neq g_2$，但$g_1 \circ f = g_2 \circ f$。

[证]

$\Rightarrow$ 因 $f: X \to Y$ 且 $f$ 为满射，故 $\forall y \in Y, \exists x \in X$ ，使得 $f(x) = y$。

假设存在 $g_1, g_2, g_1 \neq g_2$，但 $g_1 \circ f = g_2 \circ f$。因为 $g_1 \neq g_2$，所以 $\exists y_0 \in Y$，使得 $g_1(y_0) \neq g_2(y_0)$。对于上面的 $y_0$，$\exists x_0 \in X$（$f$ 是满射），使得 $g_1(f(x_0)) \neq g_2(f(x_0))$

[$g_1(y_0) \neq g_2(y_0)$]，即 $g_1f(x_0) \neq g_2f(x_0)$。故 $g_1 \circ f \neq g_2 \circ f$ 与 $g_1 \circ f = g_2 \circ f$，矛盾。所以假设不成立。

证法 2:

$f$ 满射 $\Leftrightarrow f$ 右可逆 $\Leftrightarrow \exists h: Y \to X$，使得 $f \circ h = I_Y \Leftrightarrow$ 假设 $g_1 \circ f = g_2 \circ f$ 得到 $g_1 = g_2$，命题得证。

$\Leftarrow$ $f: X \to Y$，假设 $f$ 不是满射，则 $\exists y_0 \in Y$，使得 $\forall x \in X, f(x) \neq y_0$。构造两个映射 $g_1, g_2: Y \to Z$，

当 $y = y_0$ 时，$g_1(y_0) \neq g_2(y_0)$；

当 $y \neq y_0$ 时，$g_1(y) = g_2(y)$。

因为 $|Z| \geq 2$，故此时 $g_1 \neq g_2$，但

$\forall x \in X, g_1 \circ f(x) = g_1(y \neq y_0) = g_2(y \neq y_0) = g_2 \circ f(x)$

即 $g_1 \circ f = g_2 \circ f$，与假设不存在 $g_1 \neq g_2$，但 $g_1 \circ f = g_2 \circ f$ 矛盾，故 $f$ 一定是满射。

设 $X, Y, Z$ 是三个非空的集合，$|X| \geq 2$，证明：$f: X \to Y$ 是单射当且仅当不存在从 $Z$ 到 $X$ 的映射 $g_1, g_2$，使得 $g_1 \neq g_2$，但 $f \circ g_1 = f \circ g_2$

[证]

$\Rightarrow$ $f$ 是单射，则 $\forall x_1, x_2, x_1 \neq x_2$，有 $f(x_1) \neq f(x_2)$。假设存在 $g_1$ 和 $g_2: Z \to X, g_1 \neq g_2$，因为 $|X| \geq 2$，于是 $\exists z_0 \in Z$，使得 $g_1(z_0) \neq g_2(z_0)$。

而由于 $f$ 为单射，故 $f(g_1(z_0)) \neq f(g_2(z_0))$，即 $f \circ g_1(z_0) \neq f \circ g_2(z_0)$，故 $f \circ g_1 \neq f \circ g_2$ 矛盾。

证法 2: $f$ 单射 $\Leftrightarrow f$ 左可逆的 $\Leftrightarrow \exists h$ 使得 $hf = I_X \Rightarrow$ 由 $f \circ g_1 = f \circ g_2 \Rightarrow g_1 = g_2$ 得证。

逆否命题：$g_1 \neq g_2 \Leftrightarrow fg_1 \neq fg_2$。

$\Leftarrow$ 假设 $f$ 不是单射，则 $\exists x_1, x_2 \in X, x_1 \neq x_2$，但 $f(x_1) = f(x_2)$。构造两个映射 $g_1$ 和 $g_2: Z \to X, \forall z \in Z$，令 $g_1(z) = x_1, g_2(z) = x_2$，由于 $|X| \geq 2$，故若 $x_1 \neq x_2$，则有 $g_1 \neq g_2$。但 $\forall z \in Z, f \circ g_1(z) = f(x_1) = f(x_2) = f \circ g_2(z)$，于是有 $f \circ g_1 = f \circ g_2$ 矛盾。

设 $f: X \to Y$, $g: Y \to Z$，则 $g \circ f$ 是 $X$ 到 $Z$ 的映射。我们知道由 $f$ 和 $g$ 分别诱导出从 $2^X$ 到 $2^Y$ 与 $2^Y$ 到 $2^Z$ 的映射也记为 $f$ 和 $g$。问诱导映射 $f$ 与 $g$ 的合成 $g \circ f$ 是否是映射 $g \circ f$ 的诱导映射呢？

[解]

不是.

举反例:

考虑$X=\{1,2,3\},Y=\{a,b,c\},Z=\{\alpha,\beta,\gamma\}$

现在令

$$f(1)=a,f(2)=a,f(3)=b\\ g(a)=\alpha,g(b)=\alpha,g(c)=\beta$$

记:$A=\{a,b\}\subset Y,B=\{\alpha,\beta\}\subset Z$

有诱导映射:$f:2^{X}\rightarrow 2^{Y},f(X)=A,g:2^{Y}\rightarrow 2^{Z},g(Y)=B,$

诱导映射$g \circ f(X)=\empty$,然而$g \circ f(1)=\alpha,g \circ f(2)=\alpha,g \circ f(3)=\alpha $,即$g \circ f(X)=\alpha$才是其真正的诱导映射.

设 $f: X \to Y$, $g: Y \to Z$, $A \subseteq Z$，证明：$(g \circ f)^{-1}(A) = f^{-1}(g^{-1}(A))$

[证]

$\forall x\in (g \circ f)^{-1}(A),g \circ f(x)\in A,f(x)\in g^{-1}(A),x \in f^{-1}(g^{-1}(A))$

即: $(g \circ f)^{-1}(A) \subseteq f^{-1}(g^{-1}(A))$

类似地:

$\forall x\in f^{-1}(g^{-1}(A)),f(x)\in g^{-1}(A),g \circ f(x)\in A, x\in (g \circ f)^{-1}(A)$

即: $(g \circ f)^{-1}(A) \supseteq f^{-1}(g^{-1}(A))$

为了简便,上面过程可以用$\iff$

令 $f$ 与 $g$ 都是从集合 $A$ 到 $A$ 的映射。试证：

$$|f\circ g(A)| \leq \min\{|f(A)|, |g(A)|\}$$

[证]

采用反证法.

假设$|f\circ g(A)|=\min\{|f(A)|, |g(A)|\}+1$,$|f(A)|=x,|g(A)|=y$

分情况讨论:

• $x \gt y$

  $|f\circ g(A)|=\min\{|f(A)|, |g(A)|\}+1=y+1$,这是不可能的,违反了映射的定义

• $x=y$

  $|f\circ g(A)|=\min\{|f(A)|, |g(A)|\}+1=x+1$,这是不可能的,违反了映射的定义

• $x \lt y$

  $|f\circ g(A)|=\min\{|f(A)|, |g(A)|\}+1=x+1$,这是不可能的,违反了映射的定义

设 $f$ 和 $g$ 都是从集合 $A$ 到 $A$ 的映射。试证：一般地

$$f \circ g(A) \not\subseteq f(A) \cap g(A)$$

注意本题在书上的表述有误,可以很容易举出一个反例.

本题笔者未完全理解. 若此处$f,g$全为恒等映射不能断定此命题错误吗?笔者猜测是某些文字中隐藏的条件未被使用.

下面贴出老师参考答案:

[证]

如果 $g$ 是单射，则 $g$ 是双射，此时，

$$fg(A) = f(g(A)) = f(A) = f(A) \cap g(A)$$

如果 $g$ 不是单射，则 $g$ 也不是满射，$\exists x \in A$ 使得 $\forall y \in A$ 均有 $g(y) \neq x$，此时

$$fg(A) = f(g(A)) \subseteq f(A) \setminus f(x)$$

$$f(A) \cap g(A) \subseteq f(A) \setminus \{x\}$$

一般情况下，$f(x) \neq x$，因此 $fg(A) \not\subseteq f(A) \cap g(A)$。

设 $f = u \circ g \circ v$，其中 $f, g, u, v$ 都是从集合 $A$ 到 $A$ 的映射。证明：

$$|f(A)| \leq |g(A)|$$

[证]

$f = u \circ g \circ v$，则 $f(A) = u(g(v(A)))$，则

$$|f(A)| \leq |g(v(A))| \leq |g(A)|$$

设 $N = \{1, 2, 3, \cdots\}$，试构造两个映射 $f$ 和 $g: N \to N$，使得

• (1) $fg = I_N$，但 $gf \neq I_N$；
• (2) $gf = I_N$，但 $fg \neq I_N$。

[解] (1) $fg = I_N$ 但 $gf \neq I_N$，故 $f$ 是满射，但 $f$ 不是单射。于是令：

$$f: N \to N, f(1) = 1, f(n) = n - 1, n \geq 2,$$

$$g: N \to N, \forall n \in N, g(n) = n + 1,$$

则 $fg = I_N$ 但 $gf \neq I_N$。事实上，当 $n = 1$ 时，$gf(1) = g(f(1)) = g(1) = 2$，故 $gf \neq I_N$。

(2) 和(1)有什么区别?

设 $f: X \to Y$ 则

• (1) 若存在唯一的一个映射 $g: Y \to X$，使得 $gf = I_X$，则 $f$ 是可逆的吗？
• (2) 若存在唯一的一个映射 $g: Y \to X$，使得 $fg = I_Y$，则 $f$ 是可逆的吗？

[解]

• (1) $f$ 不一定可逆。

  • 当 $|X| = 1$ 时，$f$ 不一定可逆。
  • 当 $|X| \geq 2$ 时，$f$ 可逆。

• (2) $f$ 一定可逆。

​ [证] 由 $fg = I_Y$，得 $f$ 是单射。假设 $f$ 不是满射，则 $g$ 不唯一，矛盾。

设 $f: X \to Y, |X| = m, |Y| = n$，则

• (1) 若 $f$ 是左可逆的，则 $f$ 有多少个左逆映射？
• (2) 若 $f$ 是右可逆的，则 $f$ 有多少个右逆映射？

[解] 令 $X = (x_1, x_2, \cdots, x_m), Y = (y_1, y_2, \cdots, y_n)$，则

• 有 $m^{n-m}$；

• 有 $\displaystyle \left| f^{-1}(y_1) \right| \times \left| f^{-1}(y_2) \right| \times \cdots \times \left| f^{-1}(y_n) \right|=\Pi_{\xi \in Y}|f^{-1}(\xi)|$

自行绘图结合定义即可.

证明：每个 $n$ 次置换 $\sigma$ 都可分解成这样的一些置换的乘积：每个置换或为 $(1 \ 2)$ 或为 $(2 \ 3 \ \cdots \ n)$。

[证] 只须证明，$\forall i \in \{2, 3, \ldots, n\}$ 有

$$(1 \ i) = \alpha^{x} \beta \alpha^{y}$$

其中 $\alpha = (2, 3, \ldots, n)$，$\beta = (1 \ 2)$，这是因为:

$$(i \ j) = (1 \ i)(1 \ j)(1 \ i)$$

此结论在教材中有证明

$$(1 \ i) = \alpha^{x} \beta \alpha^{y}=\begin{pmatrix} i & i+1 & \cdots \\ 2 & 3 & \cdots \end{pmatrix}(1,2)\begin{pmatrix} 2 & 3 &\cdots \\ i & i+1 & \cdots \end{pmatrix}$$

凑出$x,y$即可

观察发现:

$$\alpha^{x+y} =\begin{pmatrix} 2 & 3 &\cdots \\ i & i+1 & \cdots \end{pmatrix}\begin{pmatrix} i & i+1 & \cdots \\ 2 & 3 & \cdots \end{pmatrix}=\alpha \\ \Rightarrow x+y=n-1 \\$$

凑出$y=i-2$,进而有$x=n+1-i$

$$(1 \ i) = \alpha^{n+1-i} \beta \alpha^{i-2}$$

任一偶置换均可被分解成 $3-$ 循环置换 $(123)$，$(124) \ldots (12n)$ 中若干之乘积。

[证] 证法 1：$\forall i, j, s, t \in \{1, 2, \cdots, n\}, i \neq j, s \neq t$

$$(ij)(st) = (1i)(1j)(1i)(2s)(2t)(2s) = (1i)(1j)(2s)(1j)(2t)(2s)$$

$$= (1i)(2s)(1j)(2t)(1i)(2s)$$

$$= (1 \quad 2 \quad s)(1 \quad 2 \quad i)(1 \quad 2 \quad t)(1 \quad 2 \quad j)(1 \quad 2 \quad s)(1 \quad 2 \quad i)$$

因为 $(1 \quad 2 \quad s)(1 \quad 2 \quad i) = \begin{pmatrix} 1 & 2 & s \\ 2 & s & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & i \\ 2 & i & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & s & i \\ i & s & 2 & 1 \end{pmatrix} = (1i)(2s)$

$$(12t)(12j) = \begin{pmatrix} 1 & 2 & t \\ 2 & t & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & j \\ 2 & j & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & t & j \\ j & t & 2 & 1 \end{pmatrix} = (1j)(2t)$$

因此本题得证。

证法 2：由 $(1 \ i)(1 \ j) = (1 \ i \ j)$，$(1 \ i \ j) = (12j)(12i)(12j)^2$ 即得证。

6. 证明下列置换等式

(1) $(ac_1 \cdots c_h bd_1 \cdots d_k)(ab) = (ac_1 \cdots c_h)(bd_1 \cdots d_k)$

(2) $(ac_1 \cdots c_h)(bd_1 \cdots d_k)(ab) = (ac_1 \cdots c_h bd_1 \cdots d_k)$

[证]

(1)

$$(ac_1 \cdots c_h bd_1 \cdots d_k)(ab) = \begin{pmatrix} a & c_1 & c_2 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & c_3 & \cdots & b & d_1 & d_2 & \cdots & a \end{pmatrix}(ab)$$

$$= \begin{pmatrix} a & c_1 & c_2 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & c_3 & \cdots & a & d_1 & d_2 & \cdots & b \end{pmatrix}$$

$$= (ac_1 \cdots c_h)(bd_1 \cdots d_k)$$

(2)

$$(ac_1 \cdots c_h)(bd_1 \cdots d_k)(ab) = \begin{pmatrix} a & c_1 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & \cdots & a & d_1 & d_2 & \cdots & b \end{pmatrix}(ab)= \begin{pmatrix} a & c_1 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & \cdots & b & d_1 & d_2 & \cdots & a \end{pmatrix}= (ac_1 \cdots c_h bd_1 \cdots d_k)$$

设 $\sigma$ 是任一置换，试证：$\sigma^{-1}(i_1 i_2 \cdots i_r)\sigma = (i_1\sigma \ i_2\sigma \cdots i_r\sigma)$。

[证] 令 $\alpha = \sigma^{-1}(i_1 i_2 \cdots i_r)\sigma$，$\beta = (i_1\sigma \ i_2\sigma \cdots i_r\sigma)$，$\forall i \in S$，分两种情况，

(1) $i \notin \{i_1\sigma, i_2\sigma, \cdots, i_r\sigma\}$ 时，$i\alpha = i\beta = i$；

(2) $i \in \{i_1\sigma, i_2\sigma, \cdots, i_r\sigma\}$ 时，又分两种情况，

• ① $i = i_k\sigma, k < r$，$i\alpha = i_k\sigma\sigma^{-1}(i_1 i_2 \cdots i_r)\sigma = (i_k(i_1 i_2 \cdots i_r))\sigma = (i_{k+1})\sigma = i\beta$；

• ② $i = i_r\sigma$，$i\alpha = i_r\sigma\sigma^{-1}(i_1 i_2 \cdots i_r)\sigma = (i_r(i_1 i_2 \cdots i_r))\sigma = (i_1)\sigma = i\beta$。

在所有的 $n$ 次置换中，有多少个 $n-$ 循环置换？

提示:站在映射的角度看这个问题,绘图或许会给你一些帮助

[解]

$$(i_1, i_2, \cdots, i_n) = \begin{pmatrix} i_1 & i_2 & \cdots & i_n \\ i_2 & i_3 & \cdots & i_1 \end{pmatrix}$$

对 $i_1$，有 $n$ 种选择
对 $i_2$，有 $(n-1)$ 种选择
……
对 $i_n$ 有 $1$ 种选择

因此共有 $n!$ 种排列。
对每个 $n-$ 循环置换，均有 $n$ 种排列，因此 $n-$ 循环置换的个数为 $\frac{n!}{n} = (n-1)!$ 个。

设 $S(n, k)$ 表示 $S_n$ 中的恰有 $k$ 个循环（包括 $1-$ 循环）的置换个数。证明：

$$\sum_{k=1}^{n} S(n, k) x^k = x(x + 1)(x + 2)\cdots(x + n - 1)$$

提示:如无必要能力精力,不建议花费时间在此.

[证]

考察 $S(n,k)$ 与 $S(n-1,k)$的关系.

在 $n-1$ 个元素的基础上增加一个元素 $n$ 后的情况需要分类讨论:

• 增加的 $n$ 自成循环,总循环数$+1$,要求前 $n-1$ 个元素形成 $ k-1$ 个循环,此时前 $n-1$ 个元素中有$S(n-1,k-1)$ 个置换

• 增加的 $n$ 被加入前 $n-1$ 个元素形成的某个循环,要求前 $n-1$ 个元素形成 $ k$ 个循环,此时前 $n-1$ 个元素中有$S(n-1,k)$ 个置换, $n$ 可以被加入在 $n-1$ 个元素任何一个的前面,故有 $n-1$ 种加入方法

根据上面的分析,结合乘法法则有:

$$S(n,k)=S(n-1,k-1)+(n-1)S(n-1,k) \tag{1}$$

如果对这个结果感到困惑,请仔细阅读 $S(n,k)$ 的定义

由定义可以给出:

$$S(n,n)=1,S(n,0)=0$$

观察题设形式,联想到数学归纳法,施归纳于n:

• 当$n=1$,$S(1,1)x=x$

• 假设对 $n=i$ 时结论成立,此时有:

  $$\sum_{k=1}^{i} S(i, k) x^k = x(x + 1)(x + 2)\cdots(x + i - 1)=\prod ^{i-1}_{j=0}(x+j)$$

  则当 $n=i+1$时,使用(1)式:

  $$\begin{align} \sum_{k=1}^{i+1} S(i+1, k) x^k =& S(i+1, i+1) x^{i+1}+\sum_{k=1}^{i} S(i+1, k) x^k=\\ =& x^{i+1}+\sum_{k=1}^{i}[S(i,k-1)+iS(i,k) ]x^k \\ =& x^{i+1}+x\sum_{k=1}^{i}S(i,k-1)x^{k-1}+i\sum_{k=1}^{i}S(i,k) x^k\\ =& x^{i+1}+x\sum_{k=2}^{i}S(i,k-1)x^{k-1}+i\prod ^{i-1}_{j=0}(x+j)\\ =& x^{i+1}+x\sum_{k=1}^{i-1}S(i,k)x^{k}+i\prod ^{i-1}_{j=0}(x+j)\\ =& x^{i+1}+x[\prod ^{i-1}_{j=0}(x+j)-x^{i}]+i\prod ^{i-1}_{j=0}(x+j)\\ =& (x+i)\prod ^{i-1}_{j=0}(x+j)\\ =& \prod ^{i}_{j=0}(x+j) \end{align}$$

  证毕

令 $\{a_{n_k}\}_{k=1}^{\infty}$ 是 $\{a_n\}_{n=1}^{\infty}$ 的子序列，证明：$\forall k \in \mathbb{N}, n_k \geq k$。

[证]

采用反证法

假设 $\exist i \in \mathbb{N},n_i \lt i$,则 $n_i \le i-1$

根据子序列定义2.7.2: $n_{i-1}<n_i\le i -1$

施归纳于 $i$ ,可得 $n_1 \lt 1$,又因为 $n_k \in \mathbb{N}$ 这是不可能的.

设 $\{a_n\}_{n=1}^{\infty}$ 是一个序列。试证：$\{a_n\}_{n=1}^{\infty}$ 的子序列的子序还是 $\{a_n\}_{n=1}^{\infty}$ 的子序列。

[证]

取 $X$ 上一个序列 $\{a_n\}_{n=1}^{\infty}$ ,取 $s=\{n_i\}_{i=1}^{\infty}$ 作为自然数序列的一个子序列,取 $r=\{m_s\}_{s=1}^{\infty}$ 作为 $s$ 序列的一个子序列

此问题等价于证明: $r \circ s$ 是自然数序列的一个子序列

验证定义即可:

$$\forall i,j\in \mathbb{N},i \lt j,s(i)<s(j)\Rightarrow r(s(i))<r(s(j))$$

证毕

给出一个三元运算的例子。

提示:注意 $n$ 元运算定义

[解] 求三个正整数的最大公因数