超滤

超滤是指极大的滤子, 即一个滤子 $\mathcal{U}$ 使包含 $\mathcal{U}$ 的真滤子只有 $\mathcal{U}$ 本身. 超滤也可看成二值有限可加测度, 在超滤里的子集测度为 $1$, 其余集合测度为 $0$. 给定拓扑空间上的超滤构成一拓扑空间, 称为该空间的 Stone–Čech 紧化. 超滤在 Ramsey 理论中亦是一强力工具.

1定义

定义 1.1. 集合 $X$ 上的超滤是指其上的一个真滤子 $\mathcal{U}$, 使包含 $\mathcal{U}$ 的真滤子只有 $\mathcal{U}$ 本身.

以下引理给出超滤的一个等价定义.

引理 1.2. 集合 $X$ 上的滤子 $\mathcal{F}$ 是超滤当且仅当对于任何子集 $A\subseteq X$, $A$ 和 $X\setminus A$ 中恰一个属于 $\mathcal{F}$.

证明. 若 $\mathcal{F}$ 是超滤, 那么对 $A\subseteq X$, 不能有 $A$ 和 $X\setminus A$ 都在 $\mathcal{F}$ 中, 否则它们的交集 $\varnothing$ 也在 $\mathcal{F}$ 中, 这与 $\mathcal{F}$ 是真滤子矛盾. 下面假设 $A$ 和 $X\setminus A$ 都不在 $\mathcal{F}$ 中. 那么考虑由 $\mathcal{F}$ 和 $A$ 生成的滤子$${\mathcal{F}}^{\prime }=\{B:\exists F\in \mathcal{F},B\supseteq F\cap A\}.$$容易验证 ${\mathcal{F}}^{\prime }$ 是滤子, 且 $A\in {\mathcal{F}}^{\prime }$. 如果 $\varnothing \in {\mathcal{F}}^{\prime }$, 则存在 $F\in \mathcal{F}$ 使 $F\cap A=\varnothing$, 于是 $F\subseteq X\setminus A$, 这与 $X\setminus A\notin \mathcal{F}$ 矛盾. 所以 ${\mathcal{F}}^{\prime }$ 是严格包含 $\mathcal{F}$ 的真滤子, 这与假设矛盾. 于是 $A$ 和 $X\setminus A$ 中恰一个属于 $\mathcal{F}$.

现在假设 $\mathcal{F}$ 是真滤子, 满足对任意子集 $A\subseteq X$, $A$ 和 $X\setminus A$ 中恰一个属于 $\mathcal{F}$, 则若真滤子 ${\mathcal{F}}^{\prime }$ 是 $\mathcal{F}$ 的加细, ${\mathcal{F}}^{\prime }\ne \mathcal{F}$, 设 $A\in {\mathcal{F}}^{\prime }\setminus \mathcal{F}$, 于是由假设 $X\setminus A\in \mathcal{F}\subseteq {\mathcal{F}}^{\prime }$, $\varnothing =A\cap (X\setminus A)\in {\mathcal{F}}^{\prime }$. 这与 ${\mathcal{F}}^{\prime }$ 是真滤子矛盾. 于是 $\mathcal{F}$ 是超滤.

$\square$

推论 1.3. 集合 $X$ 上的超滤 $\mathcal{U}$ 给出二值有限可加测度 $\mu :\mathcal{P}(X)\to \{0,1\}$, 其中 $\mu (A)=1$ 当且仅当 $A\in \mathcal{U}$.

2例子

例 2.1 (主超滤). 对 $a\in X$, 包含 $a$ 的 $X$ 的全体子集构成一超滤 (容易验证其是滤子, 然后用引理 1.2). 这个超滤称为 $a$ 处的主超滤.

不用选择公理, 这些就是我们能构造出来的所有超滤. 因此非主超滤在某种意义下是 “病态”(但非常有用) 的.

3非主超滤的存在性

定理 3.1. 若集合 $X$ 无限, 则其上有非主超滤.

证明. 取余有限滤子$$\mathcal{F}=\{A:A\subseteq X,|X\setminus A|<\omega \}.$$用 Zorn 引理, 不难证明每个真滤子都有超滤加细之. 由 $X$ 无限, $\mathcal{F}$ 真, 设其被 $\mathcal{U}$ 加细. 假设其为 $a$ 处主超滤, 则 $\{a\}\in \mathcal{U}$, $X\setminus \{a\}\in \mathcal{F}\subseteq \mathcal{U}$, 故二者之交 $\varnothing \in \mathcal{U}$, 与 $\mathcal{U}$ 是超滤矛盾.

$\square$

4在 Ramsey 理论中的应用

定义 4.1. 对集合 $X$ 上超滤 $\mathcal{U}$, 记 ${\forall }_{U}x:P$ 表示 $\{x\in X:P\}\in U$.

这样定义的全称量词满足$$\begin{array}{rl}{\forall }_{U}x:(P\wedge Q)& ⟺({\forall }_{U}x:P)\wedge ({\forall }_{U}x:Q),\\ {\forall }_{U}x:(P\vee Q)& ⟺({\forall }_{U}x:P)\vee ({\forall }_{U}x:Q),\\ {\forall }_{U}x:\neg P& ⟺\neg {\forall }_{U}x:P.\end{array}$$作为代价, 它会失去交换律: ${\forall }_{U}x{\forall }_{U}y$ 和 ${\forall }_{U}y{\forall }_{U}x$ 并不等价.

定理 4.2 (Ramsey 定理). 对无穷多个顶点上的图 $G$ 的边 $k$-染色, 一定有无穷大的同色完全子图.

证明. 选取 $G$ 的顶点集上的非主超滤 $\mathcal{U}$. 考虑 $k$ 个逻辑命题$$P_i:={\forall }_{U}x{\forall }_{U}y:(x,y)\text{ 边染为第 }i\text{ 种颜色}.$$由上面的逻辑法则, $P_i$ 中恰一个为真 (这里用到 $\mathcal{U}$ 非主). 设 $P_i$ 是真的. 归纳地找一列顶点 $x_1,x_2,\dots$ 使它们之间边均为第 $i$ 中颜色. 假设 $x_1,x_2,\dots ,x_n$ 已经找到. 找 $x_{n+1}$ 满足$$\begin{array}{rl}{\forall }_{U}y:(x_{n+1},y)& \text{ 边染为第 }i\text{ 种颜色}\\ (x_1,x_{n+1})& \text{ 边染为第 }i\text{ 种颜色}\\ (x_2,x_{n+1})& \text{ 边染为第 }i\text{ 种颜色}\\ & ⋮\\ (x_n,x_{n+1})& \text{ 边染为第 }i\text{ 种颜色}\end{array}$$每个约束均被一个 $U$ 中集合的每个元素满足, 所以总是存在一个 $x_{n+1}$ 同时满足它们 (由 $U$ 对交封闭).

$\square$