数分技巧小记

设 \(\mathbb{F}, A\) 为两个集合，\(\forall x \in \mathbb F, \operatorname{card}(f(x)) = \operatorname{card}(A)\)，那么有 \(\operatorname{card}(\mathbb F \times A) = \operatorname{card}(\bigcup_{x \in \mathbb F} f(x))\)。

对角线技巧

证明：对于任意集合 \(X\)，都有 \(\operatorname{card}(X) < \operatorname{card}(\mathcal P(X))\)。

显然 \(\operatorname{card}(X) \leq \operatorname{card}(\mathcal P(X))\)。

假设 \(\exist f: X \to \mathcal P(X)\) 为满射，那么构造 \(T = \{x | x \notin f(x)\}\)，则 \(T \in \mathcal P(x)\)。

\(\forall x \in X\)，如果 \(x \in f(x)\) 则 \(x \notin T\)，即 \(f(x) \neq T\)；如果 \(x \notin f(x)\) 则 \(x \in T\)，也有 \(f(x) \neq T\)。

于是 \(f(X) \neq \mathcal P(X)\)，得证。