证明有限集合到自身的一个满变换也是双射

如果 X 是有限集,且变换 f: X \to X 是满射,则 f 是双射.

证明[\text{BAI}] 第 1 章 §5 的定理 2,只需要证明 f 是可逆的.

定理 2 映射 f: X \to Y 有逆,当且仅当 f 是双射.

定义

f^k(x) = \begin{cases}
x&k = 0 \
f(f^{k-1}(x))&k = 1,2,3,\cdots
\end{cases}

因为 f 是满射,所以

\forall x \in X, \exists x^{(1)} \in X, f(x^{(1)}) = x

于是也

\exists x^{(2)} \in X, f(x^{(2)}) = x^{(1)}

如此下去可以得到一个序列

x^{(0)}, x^{(1)}, x^{(2)}, \dots, x^{(n)}, \dots

其中 x^{(0)} 就是 x.

这里有一个显然的观察

引理 1 \forall n > m \ge 0, f^m(x^{(n)}) = x^{(n – m)}

由于 X 有限,上述序列中必然存在相等的两项,即

\exists n > m \ge 0, x^{(n)} = x^{(m)}

对等式两边施以 f^{m},由引理 1可得

x^{(n – m)} = x^{(0)} = x

综上,也就是说

\forall x \in X, \exists l > 0, x^{(l)} = x

也即是

f^l(x) = f^l(x^{(l)}) = x^{(l-l)} = x^{(0)} = x

由于映射的合成满足结合律,可得

(f \circ f^{l-1})(x) = (f^{l-1} \circ f)(x) = x

记每个 x 对应的 ll_x,设映射 g: x \mapsto f^{l_x-1}(x),容易验证

fg = gf = e_X

所以 g = f^{-1},映射 f 可逆,所以 f 是双射. 证毕.


来自 sjy 的证明

如果不单,那么可以取真子集,使得映射在它上面的限制为单射,并且保持映满,于是这个限制为双射,从而得这有限集合与它的真子集对等,矛盾。

作者:
孑枵 Abreto版权所有,转载时必须以链接形式注明作者和原始出处及本声明,本站有权追究其法律责任。

“证明有限集合到自身的一个满变换也是双射”的3个回复

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据