用户: 不萌/Erdös-Dushnik-Miller 分划定理及一个应用

我们先来看一个经典的组合定理:

定理 0.1 (Erdös–Szekeres). 对于任意长为 $(mn+1)$ 的序列, 要么可以找到一个长为 $(m+1)$ 的增链, 要么可以找到长为 (n+1) 的降链.(增减视为可以取等)

证明. 可以用反证法, 假设前者不成立的前提下, 考虑每个元所后导的最长增链长度均不长于 $m$, 必有至少 $(n+1)$ 个元素的后导增链等长, 可知它们必为递减的.

$\square$

下面这个定理我认为可以看作是 Erdös-Szekeres 定理的一个无限版本的推广.

定理 0.2 (Erdös–Dushnik–Miller). 假设 $\kappa \le {\omega }_1$ 是正则基数, 那么对于任何一个 $\kappa$ 上的简单图, 都可以要么能找到 $\kappa$ 个点互相连边, 要么能找到序型为 $\omega +1$ 的集合, 其中两两互相不连边.

证明. 需要用到比较多的集合论, 可以参见《集合论导引 (第一卷: 基本理论) 》, 冯琦, 第 212 页.

$♠$

$\square$

下面希望阐述这与 Erdös-Szekeres 定理之间的联系:

命题 0.3. 对于一个基数为 $\kappa$ 的集合 $X$ 上, 若有两个良序关系 ${<}_1$ 与 ${<}_2$ , 则可以找到一个基数为 $\kappa$ 的子集 Y, ${<}_1{|}_Y={<}_2{|}_Y$.

证明. 假设对于 ${<}_1$ 的序型是 ${\kappa }_1\ge \kappa$, ${<}_2$ 的序型是 ${\kappa }_2\ge \kappa$, 我们做这样的简化: 先取出在 ${<}_1$ 关系下的前 $\kappa$ 个元素, 集合记为 $A_1$, $A_1$ 在 ${<}_2$ 关系下还是构成良序, 并且由于 $\kappa$ 是个基数, 所以其序型要大于等于 $\kappa$. 再次取出 $A_1$ 在 ${<}_2$ 关系下的前 $\kappa$ 个元素, 这些元素在 ${<}_1$ 关系下的序型不大于 $\kappa$ (因为是序型为 $\kappa$ 的子集) , 另一方面则是因为元素个数的原因, 序型至少要是 $\kappa$. 从而简化得到: > 对于一个双射 $f:\kappa \to \kappa$ , 可以找到长为 $\kappa$ 的单调增链.

这个形式就和 Erdös-Szekeres 很像了.

首先, 我们考虑 $\kappa$ 是正则基数的情况. 此时, 我们在 $\kappa$ 上, 以所有两个元素的 ${<}_1,{<}_2$ 关系一致的二元组连边. 在这一图上, 根据此前的 Erdös-Dushnik-Miller 定理, 我们可以得到, 要么有 $\kappa$ 个元素是递增的, 要么有一个序型为 $\omega +1$ 的集合, 是递减的. 但是需要注意的是, 这给出了一个长为 $\omega +1$ 的序数递减列, 但序数的递减列都是有限长的, 不得不说这导出了矛盾. 从而我们证明了 $\kappa$ 是正则基数的情况.

当 $\kappa$ 是奇异基数的时候, 假设 $\mathrm{cf}\kappa =\beta <\kappa$, 可以有一列正则基数 $⟨{\alpha }_{\gamma }|\gamma <\beta ⟩$ 单调递增趋近于 $\kappa$. (若 $⟨{\alpha }_{\gamma }|\gamma <\beta ⟩$ 趋近 $\kappa$ , 那么 $⟨{\alpha }_{\gamma }^{+}|\gamma <\beta ⟩$ 也趋近 $\kappa$ , 而后继基数都是正则的.) 在 $⟨{\alpha }_{\gamma }⟩$ 中, 我们先是可以找到一个 ${\alpha }_{{\gamma }_1}>\beta$. 考虑 $f[{\alpha }_{{\gamma }_1}]$, 这个像集合中的每个元素都被某个 ${\alpha }_{\lambda }$ 管住 (bounded by ${\alpha }_{\lambda }$) . 数列总长 $\beta$ , 根据 ${\alpha }_{{\gamma }_1}$ 的正则性, 我们一定有其中某个 ${\alpha }_{\lambda }(\lambda \ge {\gamma }_1)$ 管住了其中 ${\alpha }_{{\gamma }_1}$ 个 $f[{\alpha }_{{\gamma }_1}]$ 中的元素. 记该 $\lambda$ 为 ${\lambda }_1$. 在这其中, 可以找到长为 ${\alpha }_{{\gamma }_1}$ 的升链, 并且大小都小于 ${\alpha }_{{\lambda }_1}$.

几乎是照抄这部分证明, 我们就可以得到对于后继序数的情形:

在 $⟨{\alpha }_{\gamma }⟩$ 中, 我们先是可以找到一个 ${\alpha }_{{\gamma }_{n+1}}>{\alpha }_{{\lambda }_n}$. 考虑 $f[{\alpha }_{{\gamma }_{n+1}}-{\alpha }_{{\gamma }_n}]$, 这个像集合中的每个元素都被某个 ${\alpha }_{\lambda }$ 管住. 数列总长 $\beta$ , 根据 ${\alpha }_{{\gamma }_{n+1}}$ 的正则性, 我们一定有其中某个 ${\alpha }_{\lambda }(\lambda \ge {\gamma }_{n+1})$ 管住了其中 ${\alpha }_{{\gamma }_{n+1}}$ 个 $f[{\alpha }_{{\gamma }_{n+1}}-{\alpha }_{{\gamma }_n}]$ 中的元素. 记该 $\lambda$ 为 ${\lambda }_{n+1}$. 在这其中, 可以找到长为 ${\alpha }_{{\gamma }_{n+1}}$ 的升链, 并且大小都小于 ${\alpha }_{{\lambda }_{n+1}}$. 可以将这些升链全都衔接起来, 还是构成一条升链.

对于极限序数的情况, 实际上我们就令 ${\alpha }_{{\gamma }_{\tau }}={\sup }_{\theta <\tau }{\alpha }_{{\gamma }_{\theta }}$, ${\alpha }_{{\lambda }_{\tau }}={\sup }_{\theta <\tau }{\alpha }_{{\lambda }_{\theta }}$ 就可以了. 怎么保证这个 ${\lambda }_{\tau }$ 不是 $\kappa$? 要用到 $\beta$ 的正则性. 比较短的链的并是不能达到 $\kappa$ 的, 而不短于的 $\beta$ 的链, 并起来一定得到 $\kappa$.

通过取并, 可以做到延长升链的效果. 我们将每个部分的所取出的升链全都并起来, 就得到一条长为 $\kappa$ 的升链了.

$\square$