超滤

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

1定义

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

•	若 $A,B\in \mathcal{U}$, 则 $A\cap B\in \mathcal{U}$;
•	若 $A\in \mathcal{U}$, $B\supseteq A$, 则 $B\in \mathcal{U}$;
•	$\varnothing \notin \mathcal{U}$;

且如子集族 $\mathcal{V}\supseteq \mathcal{U}$ 也满足以上条件, 则 $\mathcal{V}=\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\mid \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$ 的全体子集构成一超滤, 称为 $a$ 处的主超滤, 记作 ${\mathcal{U}}_a$.

不用选择公理, 这些就是我们能构造的所有超滤. 以下用选择公理证明每个真滤子都有超滤包含之, 从而构造非主超滤.

定理 2.2 (超滤定理). 设 $\mathcal{F}$ 是集合 $X$ 上的真滤子. 则存在 $X$ 上超滤 $\mathcal{U}\supseteq \mathcal{F}$.

证明. 对集合$$\{\mathcal{G}\mid \mathcal{G}是X上的真滤子,\mathcal{G}\supseteq \mathcal{F}\}$$的包含偏序用 Zorn 引理, 取出极大元, 此即所求的 $\mathcal{U}$.

$\square$

推论 2.3. 若集合 $X$ 无限, 则其上有非主超滤.

证明. 对余有限滤子$$\mathcal{F}=\{A\subseteq X\mid X\setminus A有限\}$$用超滤定理, 取超滤 $\mathcal{U}\supseteq F$. 如 $a\in X$ 使得 $\mathcal{U}$ 为 $a$ 处主超滤, 则 $\{a\}\in \mathcal{U}$, $X\setminus \{a\}\in \mathcal{F}\subseteq \mathcal{U}$, 故二者之交 $\varnothing \in \mathcal{U}$ 矛盾! 故 $\mathcal{U}$ 不是主超滤.

$\square$

3在 Ramsey 理论中的应用

定义 3.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$ 并不等价.

定理 3.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$

术语翻译

超滤 • 英文 ultrafilter