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

如果 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 对应的 l 为 l_x，设映射 g: x \mapsto f^{l_x-1}(x)，容易验证

fg = gf = e_X

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

来自 sjy 的证明

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