超滤是指极大的滤子, 即一个滤子 U 使包含 U 的真滤子只有 U 本身. 超滤也可看成二值有限可加测度, 在超滤里的子集测度为 1, 其余集合测度为 0. 给定拓扑空间上的超滤构成一拓扑空间, 称为该空间的 Stone–Čech 紧化. 超滤在 Ramsey 理论中亦是一强力工具.
定义
集合 X 上的超滤是指其上的一个真滤子 U, 使包含 U 的真滤子只有 U 本身. 展开滤子的定义, 这就是说 U 是 X 的子集族, 满足
• | 若 A,B∈U, 则 A∩B∈U; |
• | 若 A∈U, B⊇A, 则 B∈U; |
• | ∅∈/U; |
且如子集族 V⊇U 也满足以上条件, 则 V=U.
以下引理给出超滤的一个等价定义.
集合 X 上的滤子 F 是超滤当且仅当对于任何子集 A⊆X, A 和 X∖A 中恰一个属于 F.
证明. 若 F 是超滤, 那么对 A⊆X, 不能有 A 和 X∖A 都在 F 中, 否则它们的交集 ∅ 也在 F 中, 这与 F 是真滤子矛盾. 下面假设 A 和 X∖A 都不在 F 中. 那么考虑由 F 和 A 生成的滤子F′={B∣∃F∈F,B⊇F∩A}.容易验证 F′ 是滤子, 且 A∈F′. 如果 ∅∈F′, 则存在 F∈F 使 F∩A=∅, 于是 F⊆X∖A, 这与 X∖A∈/F 矛盾. 所以 F′ 是严格包含 F 的真滤子, 这与假设矛盾. 于是 A 和 X∖A 中恰一个属于 F.
现在假设
F 是真滤子, 满足对任意子集
A⊆X,
A 和
X∖A 中恰一个属于
F, 则若真滤子
F′ 是
F 的加细,
F′=F, 设
A∈F′∖F, 于是由假设
X∖A∈F⊆F′,
∅=A∩(X∖A)∈F′. 这与
F′ 是真滤子矛盾. 于是
F 是超滤.
集合 X 上的超滤 U 给出二值有限可加测度 μ:P(X)→{0,1}, 其中 μ(A)=1 当且仅当 A∈U.
例子
对 a∈X, 包含 a 的 X 的全体子集构成一超滤, 称为 a 处的主超滤, 记作 Ua.
不用选择公理, 这些就是我们能构造的所有超滤. 以下用选择公理证明每个真滤子都有超滤包含之, 从而构造非主超滤.
设 F 是集合 X 上的真滤子. 则存在 X 上超滤 U⊇F.
证明. 对集合
{G∣G 是 X 上的真滤子,G⊇F}的包含偏序用
Zorn 引理, 取出极大元, 此即所求的
U.
证明. 对余有限滤子
F={A⊆X∣X∖A 有限}用超滤定理, 取超滤
U⊇F. 如
a∈X 使得
U 为
a 处主超滤, 则
{a}∈U,
X∖{a}∈F⊆U, 故二者之交
∅∈U 矛盾! 故
U 不是主超滤.
在 Ramsey 理论中的应用
对集合 X 上超滤 U, 记 ∀Ux:P 表示 {x∈X:P}∈U.
这样定义的全称量词满足∀Ux:(P∧Q)∀Ux:(P∨Q)∀Ux:¬P⟺(∀Ux:P)∧(∀Ux:Q),⟺(∀Ux:P)∨(∀Ux:Q),⟺¬∀Ux:P.作为代价, 它会失去交换律: ∀Ux∀Uy 和 ∀Uy∀Ux 并不等价.
对无穷多个顶点上的图 G 的边 k-染色, 一定有无穷大的同色完全子图.
证明. 选取
G 的顶点集上的非主超滤
U. 考虑
k 个逻辑命题
Pi:=∀Ux∀Uy:(x,y) 边染为第 i 种颜色.由上面的逻辑法则,
Pi 中恰一个为真 (这里用到
U 非主). 设
Pi 是真的. 归纳地找一列顶点
x1,x2,… 使它们之间边均为第
i 中颜色. 假设
x1,x2,…,xn 已经找到. 找
xn+1 满足
∀Uy:(xn+1,y)(x1,xn+1)(x2,xn+1)(xn,xn+1) 边染为第 i 种颜色 边染为第 i 种颜色 边染为第 i 种颜色⋮ 边染为第 i 种颜色每个约束均被一个
U 中集合的每个元素满足, 所以总是存在一个
xn+1 同时满足它们 (由
U 对交封闭).