定理已证明

康托尔-施罗德-伯恩斯坦定理

命题陈述

若存在单射 $f:A\to B$ 与单射 $g:B\to A$ (在集合 $A$ 与 $B$ 之间),则存在双射 $h:A\to B$ 。等价地说: $|A|\le|B|$ 且 $|B|\le|A|$ 就意味着 $|A|=|B|$ 。

为什么成立?

只要两个集合彼此都能单射地嵌入对方,就足以保证它们的基数真正相等——不需要直接给出双射,只需要两个能够拼合起来的单向嵌入即可。

证明思路

对 $A$ 中每个元素,交替使用 $g^{-1}$ 与 $f^{-1}$ (在有定义处)向前追溯;每条轨迹要么停在 $A\setminus g(B)$ ,要么停在 $g(B\setminus f(A))$ ,要么永不停止。定义 $h=f$ ,适用于轨迹停于 $A$ 或永不停止的元素;定义 $h=g^{-1}$ ,适用于轨迹停于 $B$ 的元素。逐一验证可知 $h$ 是良定义的双射 $A\to B$ 。

提出者

1887 年提出格奥尔格·康托尔

用到此定理的主题

映射与基数

参考文献

Kenneth Kunen (1980). Set Theory: An Introduction to Independence Proofs
Paul R. Halmos (1974). Naive Set Theory