用户: 数学迷/从 Hindman 定理谈起

Hindman 定理是个组合学事实:

定理 1 (Hindman). 对正整数的每个有限分划 $Z_{+} = A_{1} \cup \dots \cup A_{n}$ , 都存在 $i \in {1, \dots, n}$ , 以及序列 $a_{1}, a_{2}, \dots$ , 使得对任意非空有限的 $S \subseteq Z_{+}$ , 都有 $j \in S \sum a_{j} \in A_{i} .$

它的原始证明似乎是初等的, 但我不会. 以下证明是我高中去 Ross 时所学. 其严重使用了选择公理, 但我觉得十分漂亮, 多年过去仍记忆犹新. 该定理实际上能推广成:

定理 2. 对半群 $G$ 的每个有限分划 $G = A_{1} \cup \dots \cup A_{n}$ , 都存在 $i \in {1, \dots, n}$ , 以及序列 $a_{1}, a_{2}, \dots$ , 使得对任意非空有限的 $S \subseteq Z_{+}$ , 都有 $j \in S \prod a_{j} \in A_{i} .$ 其中 $G$ 可以不交换, 此时按下标从小到大乘.

可能有读者看到这里便会问: “你怎么不要求 $G$ 无限?” 这是因为这里允许 $a_{1}, a_{2}, \dots$ 重复. 所以 $G$ 有限时, 由于有限半群必有幂等元, 定理显然. 事实上定理的一般情况也是一种找幂等元. 先来看个乍一看和定理 2 毫无关系的定理.

定理 3 (Ellis–Numakura). 设 $G$ 是左半连续的紧 Hausdorff 半群, 即 $G$ 是紧 Hausdorff 空间, 具有结合的乘法 $G \times G \to G$ , 其本身未必连续, 但对单个 $g \in G$ , 左乘 $g$ 的映射 $g \cdot : G \to G$ 连续. 则 $G$ 有幂等元.

证明. 由紧性及 Zorn 引理,

G

的非空闭子半群中有极小者, 设为

H

. 任取

h \in H

. 则显然

h H \subseteq H

还是非空闭子半群, 故由极小性

h H = H

. 于是

{k \in H ∣ h k = h}

非空; 它显然也是子半群; 由

h \cdot

的连续性, 它闭; 故由极小性

{k \in H ∣ h k = h} = H

, 特别地

h^{2} = h

.

$□$

再来用它证明定理 2. 为此需要引入超滤.

定义 4 (超滤). 集合 $X$ 上的超滤指其子集族 $F$ , 满足

$∙$	$\emptyset \in / F$ , $X \in F$ .
$∙$	如 $A \in F$ , $A \subseteq B$ , 则 $B \in F$ .
$∙$	如 $A, B \in F$ , 则 $A \cap B \in F$ .
$∙$	如 $A, B \subseteq X$ 满足 $A \cup B \in F$ , 则 $A \in F$ 或 $B \in F$ .

$X$ 上所有超滤的集合记作 $β X$ . 对 $x \in X$ , 显然 ${A \subseteq X ∣ x \in A}$ 是超滤, 我们滥用记号将此超滤也记作 $x$ , 并将 $X$ 视为 $β X$ 的子集.

对 $A \subseteq X$ , 定义 $U_{A} = {F \in β X ∣ A \in F}$ , 则 $U_{\emptyset} = \emptyset$ , $U_{X} = β X$ , $U_{A} \cap U_{B} = U_{A \cap B}$ , $U_{A} \cup U_{B} = U_{A \cup B}$ . 以这些 $U_{A}$ 为开集基, 可将 $β X$ 视为拓扑空间. $β X$ Hausdorff: 对不同的超滤 $F$ , $G$ , 取 $A \subseteq X$ 使得 $A \in F$ , $A \in / G$ , 则 $A$ 的补集 $A^{c} \in G$ , 于是开集 $U_{A}$ 与 $U_{A^{c}}$ 就分离 $F$ 与 $G$ .

注 5. 依定义容易发现, 超滤一一对应于 Boole 代数 $2^{X}$ 到 $2$ 的同态: 超滤 $F$ 对应于同态 $f (A) = [A \in F]$ (即 $A \in F$ 的真值), 反过来同态 $f$ 对应超滤 $f^{- 1} (1)$ . 由于这也对应于 Boole 环同态, 从而对应于 Boole 环 $2^{X}$ 的极大理想, 故 $β X = S p e c (2^{X})$ , 上面的拓扑显然是 Zariski 拓扑. 由此可得 $β X$ 紧. 当然也可以直接用滤子和超滤的理论证紧, 我这属于数学家救火.

对半群 $G$ , 其超滤集合 $β G$ 上有自然的左半连续半群结构.

命题 6. $G$ 是半群. 对 $F, G \in β G$ 定义 $F G = {A \subseteq G ∣ {a \in G ∣ A a^{- 1} \in F} \in G},$ 其中 $\cdot a^{- 1}$ 指 $(\cdot a)^{- 1}$ , 即沿右乘 $a$ 取映射原像. 则这使 $β G$ 成为左半连续半群, $G \subseteq β G$ 成为子半群.

证明. 依定义

(F \cdot)^{- 1} (U_{A}) = U_{{a \in G ∣ A a^{- 1} \in F}}

, 故它左半连续. 结合律也是展开定义而得, 繁而不难, 我在这做一遍也没有好处, 故留给读者自证. 当

G = g \in G

时,

F G = {A \subseteq G ∣ g \in {a \in G ∣ A a^{- 1} \in F}} = {A \subseteq G ∣ A g^{- 1} \in F};

此时如再有

F = f \in G

, 则

F G = {A \subseteq G ∣ f \in A g^{- 1}} = {A \subseteq G ∣ f g \in A} = f g,

故

G \subseteq β G

成为子半群.

$□$

注 7. 有的读者可能知道 $β G$ 是 $G$ 作为离散空间的 Stone–Čech 紧化. 那么上述乘法可以解释如下: 对每个 $g \in G$ , 将右乘映射 $\cdot g : G \to G$ 作 Stone–Čech 紧化, 得映射 $\cdot g : β G \to β G$ ; 让 $g$ 变动, 即得乘法 $β G \times G \to β G$ ; 现在对每个 $F \in β G$ , 将左乘映射 $F \cdot : G \to β G$ 再作 Stone–Čech 紧化, 得映射 $F \cdot : β G \to β G$ ; 再让 $F$ 变动, 即得乘法 $β G \times β G \to β G$ . 这样也解释了为什么只能得到半连续.

懒于验证结合律的读者可能可以由 $G \subseteq β G$ 稠密以及 $G$ 上的结合律推出 $β G$ 上的结合律.

警告. 即便 $G$ 本身交换, $β G$ 也不太会交换.

现在终于能够证明定理 2. 下面证出的定理 2 中乘法是按下标从大到小乘的; 这显然无关紧要, 把半群取反即可.

证明. 由定理 3, 存在

F \in β G

使得

F^{2} = F

. 把定义写开, 这相当于对

A \subseteq G

,

A \in F ⟺ {a \in G ∣ A a^{- 1} \in F} \in F .

考虑定理陈述中的分划

G = A_{1} \cup \dots \cup A_{n}

. 由

F

是超滤, 存在

i \in {1, \dots, n}

使得

A_{i} \in F

. 接下来我们用

F

幂等, 在其中选出符合要求的序列. 记

A = A_{i}

. 由于

A \in F

, 有

{a \in G ∣ A a^{- 1} \in F} \in F

, 于是

A \cap {a \in G ∣ A a^{- 1} \in F} \in F,

从而该交集非空. 取交集中的元素

a_{1}

, 那么

a_{1} \in A

且

A a_{1}^{- 1} \in F

. 令

A^{'} = A \cap A a_{1}^{- 1}

, 则

A^{'} \in F

, 于是类似地

A^{'} \cap {a \in G ∣ A^{'} a^{- 1} \in F} \in F .

再取该交集中的元素

a_{2}

, 那么

a_{2} \in A^{'} = A \cap A a_{1}^{- 1}

, 从而

a_{2}, a_{2} a_{1} \in A

; 且

A^{'} a_{2}^{- 1} \in F

. 再令

A^{''} = A^{'} \cap A^{'} a_{2}^{- 1} \in F

, 类似地

A^{''} \cap {a \in G ∣ A^{''} a^{- 1} \in F} \in F .

再取该交集中的元素

a_{3}

, 那么

a_{3}, a_{3} a_{2} \in A^{'}

, 从而

a_{3}, a_{3} a_{1}, a_{3} a_{2}, a_{3} a_{2} a_{1} \in A

. 事不过三, 我想聪明的读者已经完全明白了.

$□$

区区一个正整数组合学事实, 证明过程中我用了三次选择公理, 这也许并不令人满意. 我实际上能证明这并不用到选择公理. 不过定理 1 目前的陈述本身就含有可数选择, 要先把它写成有限形式. (这些是我最近明白的, 并非高中所学.)

定理 8 (Hindman 有限形式). 对任意 $n, k \in Z_{+}$ , 存在 $N \in Z_{+}$ , 使得对每个分划 ${1, \dots, N} = A_{1} \cup \dots \cup A_{n}$ , 都存在 $i \in {1, \dots, n}$ 以及 $a_{1}, \dots, a_{k} \in A_{i}$ , 使得对任意非空的 $S \subseteq {1, \dots, k}$ , 都有 $j \in S \sum a_{j} \in A_{i} .$

证明. 这个由定理 1 不难得到. 这大概是组合学的一般道理. 我之后再详细写.

$□$

我们来证明定理 8 不需要选择公理.

定理 9. ZF 能推出定理 8.

证明. 这是数理逻辑的一般道理. 大概就是说, 如果 ZF 不能推出定理 8, 相当于 ZF 和其否定相容. 把该否定写出来, 把反例中的一些数､集合作为常数加到 ZF 中, 再加入该否定作为公理. 然后在这里面做 Gödel 可构造宇宙, 就得到 ZFC 和该否定相容, 就矛盾了.

$□$

名字空间

视图

用户: 数学迷/从 Hindman 定理谈起