有限集合和鸽子洞原理

有限集

我们称一个集合是有限的如果其等势于某个集合 $[n]$ , 其中 $[n]:=\{1,\cdots, n\}$

鸽笼原理 pigeonhole principle

自然数集合 [n] 不等势与任何一个真子集

caveat

对于函数 $f: A \to B$ 我们有

• 如果 $A = \emptyset$ 那么对于任意函数 $f :\emptyset \to B$ 是单射的
• 如果 $B = \emptyset$ 则 $f$ 是一个空映射，从 $\emptyset \to \emptyset$ 这也是满射的，因此这也是一个双射

推论

1. 没有有限集能等势于其真子集
2. $\mathbb N$ 是无限集
3. 任意有限集合等势于一个唯一的自然数
4. 任意有限集的子集是有限集
5. 对于非空有限集合 $A,B$, 如果存在单射 $f: A\to B$, 那么 $|A| \le |B|$
6. 如果 $f : A\to [n]$ 是一个单射那么 $A$ 是一个有限集合且 $|A| \le n$
7. 对于一个有限集合 A 且有一个满射函数 $f: A\to B$ 则 $|B| \le |A|$
8. 对于一个有限集合 A 和一个映射 $f:A\to B$ 有 $|f(A)| \le |A|$

高阶鸽笼原理

令 $r,s\in \mathbb N - \{0\}$, 如果有一个集合包含了至少 $rs + 1$ 的元素且被分割到 r 个子集中，那么有一些子集包含了至少 s+ 1 个元素

应用

1. $S\subset [200], |S| = 101$, 则 $S$ 一定包含了两个相邻的整数
2. 假设 $S\subset [200], |S| = 101$, 那么 $S$ 包含了两个整数，一个整除另一个

埃尔德什-塞克雷斯定理 Erdos-Szekeres Theorem

给定任意 $n$ 和 $m$（都是正整数），存在一个最小的整数 $N$，使得任意长度为 $N$ 的序列，必包含一个长度至少为 $n$ 的单调递增子序列或一个长度至少为 m 的单调递减子序列。这个最小整数 N 满足：

$N \geq (n - 1)(m - 1) + 1$