几个关于集合的有趣证明

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert} 在离散数学的第一堂课就被介绍了Set和Proper Class的区别。

与高中内容不同，现代数学中并不是任取一些元素都能组成一个Set，某些东西归在一起只能形成Proper Class（因为这个东西不满足集合的一些性质）

根据ZFC公理系统，我们可以知道关于集合的若干条公理，也就是说满足这些的才是集合，而推断某个东西不是集合常用反证的方法，下面来看几个栗子

1. Prove that the set of all sets is a proper class. 这个比较简单。假设这东西是一个集合，记为 $S$，那么根据Cantor’s Theorem我们有 $|S|<|2^S|$。 而根据幂集公理(Axiom of power set)可知，$2^S$ 也是一个集合，于是有 $2^S\subset S$，也就是 $|2^S|\le |S|$，矛盾

2. Prove that the set of all cardinals is a proper class. 这周的作业，想了很久。。 首先要知道任意多个集合的并、一个集合的幂集都是集合，并且任意集合都唯一对应着一个cardinal，知道这些就比较好做了。 和上面的方法类似，假设这是一个集合 $S$，那么根据并集公理(Axiom of union)我们有 $T=\cup S$ 也是一个集合，于是 $|T|\in S$。 因为 $\forall x\in S$ 都有 $x\subset T$，于是得到 $\forall x\in S\ \ \ |x|\le |T|$ 然而 $|T|<|2^T|\in S$，这就推出了一个矛盾。 关于the set of all ordinals是一个 proper class的证明和这个类似

3. Prove that for cardinals $A$ and $B$，$A+B=\max(A,B)$ where at least one of them is infinite 网上有很多证明，然而我都看不太懂，希望有别的做法的朋友可以交流交流;-P 不妨设$A\ge B$，那么显然有$A\le A+B\le A+A$，我们只需要证明$A=A+A$即可，注意这里的A是cardinal 由于A是一个cardinal，那么它同时也是一个ordinal。对于任意ordinal $x$，$\exist \alpha,\beta\ \ s.t.\ \ x=\alpha+\beta$，其中$\alpha$是一个limit ordinal，$\beta\in\mathbb N$ 考虑这样一个映射$f(\alpha+\beta)=\left{\begin{aligned}\left(0,\alpha+\beta\right)&,&\beta &=2k\\left(1,\alpha+\beta\right)&,&\beta&=2k+1\end{aligned}\right. \left(k\in\mathbb Z\right)$

不难发现$f:A\mapsto\left(\left{0\right}\times A\right)\cup\left(\left{1\right}\times A\right)$是一个双射，于是就证明完了。