鸽巢原理

Written by: algebnaly

Date: 2025-04-28T11:24:22.000Z

导言

基本上,有两个版本的鸽巢原理:

1. 如果n个自然数之和大于n,则这些自然数中有一个自然数大于1。
2. $A,B$都是有限集,且有$|A|=|B|$,即$A$与$B$等势, 则函数$f:A \Rightarrow B$是单射当且仅当$f$是满射。

我想证明第二个版本。

证明命题

准备工具

在证明鸽巢原理之前, 我们需要两个引理。

引理1 有限集$A$的子集$B$是有限集, 且有$|B| \le |A|$, 若$B$是$A$的真子集, 则$|B| < |A|$

证明: 我们对$A$的势使用数学归纳法,令$n:=|A|$。 首先是基础情形, $n=0$时$A$是空集, 则唯一的子集也是空集, 命题成立。

现在假定$n=n_0$时命题也成立, 需要证明$n=n_0+1$时命题也成立。

如果$B=A$, 则$|A|=|B|$命题成立，现在考虑B是A的真子集的情况。既然$B$是$A$的真子集,则存在$a_0 \in A, a_0 \notin B$, 令$A_1 := A\backslash\{a_0\}$, 于是$A_1$的势为$n_0$, 且有$B$是$A_1$的子集,根据归纳假设$|B| \le |A_1| < |A|$命题成立。

引理2 $A,B$是有限集，如果$|A| < |B|$, 则不存在从$A$到$B$的满射。

证明: 我们对$A$的势使用强归纳法,令$n:=|A|$。

首先是基础情形, $n=0$时,$A$为空集,$|A| < |B|$, 则$B$不为空集,则唯一的从$A$到$B$的函数是空函数,该空函数不是满射, 于是基础情形成立。

接着假定$n=n_0$时命题也成立。现在需要证明$n=n_0+1$时命题也成立。

不妨假定存在从$A$到$B$的满射$f$,

任取$B$中一元素$b_0$, 由于$f$是满射, 则$f^{-1}(\{b_0\})$非空, 不妨令 $A_{b_0} := f^{-1}(\{ b_0 \})$。$A_{b_0}$是$A$的子集,令$A_1:=A\backslash A_{b_0}$, $B_1 := B\backslash\{ b_0 \}$,将f限制在$A_1$上得到函数$f_1$, $f_1$仍然是从$A_1$到$B_1$的满射。由引理1得到$A_1$是有限集且其势小于$|A|$。于是$|A_1| \le |A| - 1 < |B| -1 = |B_1|$于是$|A_1| < |B_1|$, 由于$A_1$的势小于等于$n_0$由归纳假设可知$f_1$不是满射, 这与假设相矛盾, 于是命题得证。

开始证明

现在我们可以证明鸽巢原理了。

单射 $\Rightarrow$ 满射

我们先证明单射蕴含着满射。

我们对$A$的势使用数学归纳法，用$n$表示$A$的势。

首先证明基础情形。$n=0$时, $A$与$B$的势为零则$A,B$都是空集, 则从$A$到$B$的唯一的函数就是空函数，空函数既是单射也是满射，基础情形成立。

接着假定$n=n_0$时，命题也成立，现在需要证明$n=n_0+1$时命题也成立。

取$A$中一元素$a_0$，那么有$f(a_0) \in B$, 不妨令$f(a_0)=b_0$。 既然f是单射, 那么如果$a \neq a_0$,则$f(a) \neq b_0$,于是我们有$f(A\backslash\{a_0\}) \subset B\backslash\{b_0\}$。

令$A_1 := A\backslash \{a_0\}$,$B_1 := B\backslash \{b_0\}$。 我们定义函数$f_1: A_1 \Rightarrow B_1, f_1: a \mapsto f(a)$, 从上文可知, 若$a \in A_1$, 则$f(a) \in B_1$,于是$f_1$是良定义的。

由于$f$是单射, 则$f_1$也是单射。且$|A_1|=|B_1|=n_0$, 于是由归纳假设, $f_1$是满射，接着得到$f$也是满射。

满射 $\Rightarrow$ 单射

现在证明满射蕴含着单射。

我们使用反证法，不妨假定存在一个函数$f: A \Rightarrow B$它是满射但不是单射。 既然$f$不是单射, 那么$A$的势大于1,否则$f$一定是单射。 既然$f$不是单射, 那么$B$中存在一元素$b_0$使得有多个$A$中的元素被映射到$b_0$。 模仿上文中的做法,拿掉$B$中的$b_0$和$A$中的$f^{-1}(\{b_0\})$和$f^{-1}(\{b_0\})$,得到$f_1: A_1 \Rightarrow B_1$,既然$f$是满射,拿掉$b_0$后仍然是满射, 由引理1,$A_1, B_1$仍然是有限集,且$|A_1| < n_0 = |B_1|$，由引理2，$f_1$不是满射这是一个矛盾。于是命题得证。