超フィルター

数学において、超フィルター（ちょうフィルター、英: ultrafilter）または極大フィルター（きょくだいフィルター、英: maximal filter）とは順序集合上で定義されたフィルターの中で極大なものをいう。特にブール代数上では超フィルターは素フィルター（英語版）に一致する。 超フィルターは位相空間論や集合論における最も基本的な概念の一つであり、また多くの分野に応用を持っている。 冪集合は包含関係で自然に順序集合となる。 集合 X の冪集合 P(X) 上の超フィルターは単に X 上の超フィルターとも呼ばれる。X 上の超フィルターは X 上ですべての集合に対して定義された非自明な二値有限加法的測度と同一視することが出来る。この時 X 上の集合は測度の意味で殆ど全体（測度が 1）か殆ど元を含まない（測度が 0）のいずれかに分けられる。 (P, ≤) を順序集合とし F を P の部分集合とする。 この時、以下の3つの条件を満たすとき F をフィルターという。 F ≠ ∅。 任意の x, y ∈ F に対し、ある z ∈ F が存在して、z ≤ x かつ z ≤ y が成り立つ。 任意の x ∈ F, y∈ P について「x ≤ y ならば y ∈ F」が成り立つ。 更にフィルター F が P の真部分集合のとき真のフィルターという。極大な真のフィルターを超フィルターという。つまり P 上の真のフィルター U が次を満たすとき超フィルターという。 U を部分集合に含む P 上の真のフィルター F は U 自身ただひとつ。 以下順序集合 P 上の超フィルター全体を Ult(P) と書く。 存在 L を最小元 0 を持った順序集合、F を L 上の有限交叉族とする。このとき F を含む超フィルターが存在する。 実際 F を L 上の有限交叉族としたとき、（L 上のフィルターが真のフィルターとなる必要十分条件は 0 を含まないことから、）F を含む真のフィルター全体は包含関係で帰納的順序集合となる。この集合族はツォルンの補題から極大元を持つ。この極大元は F を含む超フィルターである。 任意のブール代数上での（勝手な有限交叉族を含む）超フィルターの存在はブールの素イデアル定理（英語版）と呼ばれ、ZF集合論では証明できず、選択公理を弱めた原理であることが知られている。 B を最小元 0 を持った束、U を B 上の真のフィルターとする。このとき U が超フィルターとなることと次が同値。 x ∉ U ならば、ある y ∈ U が有って、x ∧ y = 0。 更に、B がブール代数のとき、以下ふたつの条件も超フィルターであることとそれぞれ同値である。 x ∨ y ∈ U ならば、x ∈ U または y ∈ U （素フィルター）。 x ∈ B ならば、x ∈ U または ¬x ∈ U。 A, B をブール代数、Φ: A → B をブール代数の準同型、U を B 上の超フィルターとする。U の Φ による逆像 Φ−1(U) = {x ∈ A : Φ(x) ∈ U}（≕ StΦ(U)）は A 上の超フィルターとなる。ブール代数 B に空間 Ult(B) を、準同型 Φ に写像 StΦ を対応させる対応はブール代数の圏から位相空間の圏への関手を与える（詳しくはストーンの表現定理を参照）。 逆にブール代数 B 上に超フィルター U が与えられたとき、μU: B → 2 ≔ {0, 1} を μ U ( x ) := { 1 x ∈ U 0 x ∉ U {\displaystyle \mu _{U}(x):={\begin{cases}1&x\in U\\0&x\notin U\end{cases}}} と定義すると、μU はブール代数間の準同型となる。このことから B の超フィルター全体 St(B) と 2 への準同型全体 Bool(B, 2) は自然に同一視出来る。 K を最小元を持った束 L の部分束とする。このとき K 上の超フィルターは L 上の超フィルターに拡張できる。さらに拡張した超フィルターの制限は元に一致する。つまり K 上の超フィルターは L 上の超フィルターの制限と見なせる。更に、L 上の超フィルターの K への制限は空集合であるか、全体か、超フィルターのいずれかになる。 B0, B1 をブール代数、L0, L1 をそれぞれの部分束、f: B0 → B1 をブール代数の準同型とする。このとき、f(L0) ⊆ L1 とすると、U ∈ Ult(L1) ならば f  −1 |L0 (U) ∈ Ult(L0) 。 全順序集合は超フィルターを持つのは最小元を持つときに限り、そのとき最小元を 0 とすると唯一の超フィルターは {x : 0 < x} と表せる。 最小元 0 を持った束 L の元 x が原子元（つまり L ∖ {0} の極小元）のとき x で生成される単項フィルター (x) ≔ {y ∈ F : x ≤ y} が超フィルターになる（束では単項フィルターが超フィルターになるのはこの時に限る）。 無限集合 X の補有限部分集合全体 Pfin(X) ≔ {A ⊆ X : |X ∖ A| ≤ ∞} は最小元を持たない分配束となる。U を Pfin(X) の超フィルターとするとある x ∈ X が存在して、U = {A : {x} ⊆ A} とかける。これは Pfin(X) 上の単項フィルターではない。 以下、集合 X の冪集合 P(X) 上のフィルターを単に X 上のフィルターといい、誤解の恐れがないとき X 上の超フィルター全体からなる集合族 Ult(P(X)) を 単にUlt(X) と書く。以下特に断りがない限りフィルターは集合族上のフィルターのみ考える。 U ∈ Ult(X) としたとき、以下のいずれか片方を満たす。 ある x ∈ X が有って U は x で生成される単項フィルター（U = {A ⊂ X : x ∈ A}）。 A が X の有限部分集合ならば Ac ∈ U。 二番目は自由な(英: free)超フィルター（または非単項(英: non-principal)超フィルター）と呼ばれる非常に重要な超フィルターのクラスである。 U ∈ Ult(X) のとき、前項で定義したブール代数間の準同型 μU: P(X) → {0, 1} は P(X) 全体で定義された X 上の非自明な（μU(X) ≠0）二値有限加法的測度となる。 集合 X, Y 間の写像 f: X → Y に対し、Φf: P(Y ) → P(X) を Φf(B) ≔ f−1(B)（B ∈ Y）とする。このとき、Φf はブール代数の間の準同型なので、U ∈ Ult(X) のとき、f[U] ≔ {B ⊆ Y : f−1(B) ∈ U}（= Φ −1 f (U)）は Y 上の超フィルターである。 このとき、βf: Ult(X) → Ult(Y) はストーンチェックコンパクト化による f の拡張である（ただし βf(U) ≔ f[U]）。 このとき (Ult, β) はコンパクトハウスドルフ空間の圏 Comhaus から集合の圏 Set への忘却関手の左随伴関手になっている（詳しくはコンパクト化を参照）。 基本性質 X が有限集合のとき U が自由な超フィルターだとすると ∅ = Xc ∈ U より矛盾するので、有限集合上には単項フィルターしか存在しない。 無限集合 X の補有限部分集合全体 Pfin(X) ≔ {A ⊆ X : |X ∖ A| ≤ ∞} は真のフィルターとなりフレシェ (仏: Fréchet) フィルターと呼ばれる。超フィルターが自由なこととフレシェフィルターを含むことが同値。 無限集合 X の超フィルター全体 Ult(X) の濃度は、X の冪集合 P(P(X )) の濃度と等しくなる（これはフィルター全体や自由な超フィルター全体の濃度とも等しい）。 無限集合 X 無限基数 κ < |X| にたいし、X 上の集合族 Pκ(X) ≔ {A ⊆ X : |X ∖ A| < κ} は真のフィルターとなり（特に κ = |X| のとき）一般化されたフレシェ (英: generalized Fréchet) フィルターと呼ばれる。X 上の超フィルターが κ-一様なことと、Pκ(X) を含むことが同値。 ノルム フィルター U に対し、‖ U ‖ ≔ min({|A| : A ∈ U}) をフィルター U のノルムという 。 前小項の記述から超フィルターのノルムは単項フィルターについては1、自由な超フィルターについては無限基数となることが分かる。 一様 無限基数 κ と U ∈ Ult(X) について、‖ U ‖ ≥ κ となるとき U は κ-一様 (κ-仏: uniform)な超フィルターだという、特に ‖ U ‖ = |X| のとき、単に U は一様な超フィルターだという。 完備 無限基数 κ とフィルター U について V ⊂ U , | V | < κ {\textstyle V\subset U,|V|<\kappa } ならば ⋂ V ∈ U {\textstyle \bigcap V\in U} 　が成立するとき、U は κ-完備(κ-英: complete)だという。ω1-完備のことを σ-完備ともよぶ。 U ∈ Ult(X ) について以下2つの条件は互いに同値（フィルターは常に ω-完備なことに注意）。 U は κ-完備。 V ⊆ P ( X ) , ⋃ V ∈ U , | V | < κ {\textstyle V\subseteq \mathbf {P} (X),\bigcup V\in U,|V|<\kappa } ならば V ∩ U ≠ ∅ {\textstyle V\cap U\neq \varnothing } ω1-完備のことを σ-完備または可算完備とも言う。 善良 性質 自由な超フィルター U が κ-完備ならば U は κ-一様になる。 自由な超フィルター U ∈ X が可算完備ならば |X| はウラム可測基数、|X|-完備ならば |X| は可測基数（英語版）となる。 U, V をそれぞれ X, Y 上の超フィルターとする。このとき X × Y 上のフィルター U × V, U ⋅ V を以下のように定義する。 U × V ≔ {C ⊆ X × Y : ある A ∈ U, B ∈ V が存在して、A × B ⊆ C} U ⋅ V ≔ {C ⊆ X × Y : {x ∈ X : {y ∈ Y : (x, y) ∈ C} ∈ V} ∈ U} U × V は U, V の各要素の直積からなるフィルター基から生成されたフィルターである。 以下、X と Y を集合、r: X × Y → Y × X を r(x, y) ≔ (y, x) で定義される成分の入れ替え写像だとする。 基本性質 U ⋅ V = lim x ∈ U ( lim y ∈ V ( x , y ) ) {\textstyle U\cdot V=\lim _{x\in U}(\lim _{y\in V}(x,y))} （ただし収束はストーン・チェックコンパクト化（X × Y ⊆）Ult(X × Y) 上での収束。） U × V ⊆ U ⋅ V. U, V が共に超フィルターならば U ⋅ V も超フィルター。 U または V が単項フィルターならば U ⋅ V = U × V. ‖ U × V ‖ = ‖ U ⋅ V ‖ = ‖ U ‖⋅‖ V ‖. U, V が共に自由な超フィルターで ‖ U ‖ = ‖ V ‖ なら U ⋅ V ≠ r[V ⋅ U] 。 U, V が共に κ-完備ならば U × V, U ⋅ V も κ-完備。 今、超フィルター間の前順序 ≤RK 及び同値関係 ≡RK を 超フィルター U, V が V ≤RK U ⇔ ある写像 f: X → Y（ただし X, Y は U, V の台集合）が存在して V = f[U] となる。 超フィルター U, V が V ≡RK U ⇔ ある A ∈ U, B ∈ V と、ある全単射 f: A → B が存在して V ∩ P(B) = f[U ∩ P(A )] となる。 と定義する。これを超フィルターに関するルディン・キースラー順序及びルディン・キースラー同値という。 じつはルディン・キースラー同値はルディン・キースラー順序によって定義される同値関係と一致する。言い換えると U ≡RK V ⇔ V ≤RK U かつ U ≤RK V となる。つまりルディン・キースラー順序は超フィルターのルディン・キースラー同値に関する同値類間の順序と思える。 基本性質 U ≤RK V ならば ‖ U ‖ ≤ ‖ V ‖。 κ-完備な超フィルターよりルディン・キースラー順序で小さい超フィルターは再び κ-完備。 単項超フィルター（からなるルディン・キースラー同値類）はルディン・キースラー順序に関する最小元と成っている。 U0 ≤RK U1 かつ V0 ≤RK V1 ならば U0 × V0 ≤RK U1 × V1 かつ U0 ⋅ V0 ≤RK U1 ⋅ V1。 位相空間 X 上のフィルター U が x ∈ X に収束するとは U が x の近傍系 Nx の拡張に成っていることをいう。 このとき x に収束する X 上の超フィルターの共通部分は Nx と一致する。 位相空間 X の閉集合全体からなる集合族 C(X) は空集合を最小元として持つ束である。よって有限交叉的な閉集合族が与えられたとき C(X) 上にその有限交叉族を含む超フィルターが存在する。 f: X → Y を位相空間 X, Y 間の連続写像、U を C(X) 上の超フィルターとしたとき、fc[U] ≔ {A ∈ C(Y) : f−1(A) ∈ U} は C(Y) 上の超フィルターとなる。 C(X) 上の超フィルター全体はウォールマンのコンパクト化と呼ばれるコンパクト化を与える。これ以外にも位相空間上の様々な集合族に各種の順序を与えるた順序集合上の超フィルターを考えることで各種のコンパクト化が構成できる。 基本性質 位相空間の間の写像 f: X → Y が連続 ⇔ 超フィルター U が x に収束するならば f[U] は f(x) に収束する。 位相空間がハウスドルフ ⇔ 各超フィルターの収束先は高々一つ。 位相空間がコンパクト ⇔ 超フィルターは必ず収束する ⇔ C(X) 上の超フィルターの共通部分は空でない。 一様空間が全有界 ⇔ 超フィルターは必ずコーシーフィルターとなる。 I を無限集合、U を I 上の自由な超フィルター、{Mi}i∈I をある構造に関する I で添字付けられたモデルの族とする。このとき、∏ i∈I Mi を同値関係 (ai)i∈I ∼ (bi)i∈I ⇔ {i ∈ I : ai = bi} ∈ U で割った商空間 ∏ i∈I Mi/U 上には自然に構造が入る。これを超積という。 これは U を I 上の測度と同一視して見たとき、殆どいたるところ一致する元を同一視した空間である。 特に Mi が常に一つのモデル M を取るとき、MI/U とかき M の超フィルター U による超冪とよばれる。このとき MI/U は M の初等拡大になっている。特に M がある構造に関する標準モデル（英: standard model）のとき、MI/U はその構造に関する超準モデル（英: non-standard model）となっている。例えば実数の超準モデルである超実数は実数と様々な性質を共有し実数上の関係や関数は超実数上の関係や関数として自然に拡張できるが完備性などの様々な重要な性質については異なっている。（超積、算術の超準モデル等を参照） I を無限集合、U を I 上の自由な超フィルター、(Xi , di , bi)i∈I を I で添字付けられた基点付き距離空間の族とする。このとき超積 ∏ i∈I Xi/U 上に同値関係 x ∼ y ⇔ st(d*(x, y)) = 0（ただし d* はもとの距離から定まる超積上の（超実数に値を持つ）距離、st は超実数の標準成分） を定義したとき lim U X i = { x ∈ ∏ i ∈ I X i / U : st ⁡ ( d ∗ ( x , b ∞ ) ) < ∞ } / ∼ {\displaystyle \lim _{U}X_{i}=\{x\in \prod _{i\in I}X_{i}/U:\operatorname {st} (d^{\ast }(x,b_{\infty }))<\infty \}/\sim } を (Xi, di, bi)i∈I の U による超極限（英語版）（英: ultralimit）という（ただし、b∞ = (bi)i∈I であり、st ∘ d* を距離とする）。 特に基点付き距離空間 (X, d, b) に対し、(Xn, dn, bn) = (X, d/n, b)（ただし添字集合 I を自然数全体 N とする）としたとき、 lim U X n {\textstyle \lim _{U}X_{n}} を (X, d, b) の漸近錐（英語版）（英: asymptotic cone）という。 基本性質 距離空間の超極限は完備距離空間 弧長距離空間（英: length metric space）の超極限は弧長距離空間 測地距離空間の超極限は測地距離空間 超実数を利用した微分方程式と差分方程式の対応は微分方程式論の研究やトロピカル幾何に応用されている。 それ以外にも超積を利用した方法は解析学の様々な分野に応用されている（超準解析参照）。 組合せ論の中で特に大きい分野の一つであるラムゼー理論の中心的定理、ラムゼーの定理 はある集合上に与えられた一件無秩序な構造にたいし、十分大きく等質な部分集合が取れることを表している。以下のラムゼーフィルターはこの大きさを表すものとみなすことが出来る。 以下 X を無限集合 U を X 上の自由な超フィルターとする。このとき U がラムゼーとは、X の二元集合上の関数 f: [X]2 → {0, 1} が与えられたとき、「ある A ∈ U が存在して、[A]2 ⊆ f−1({0}) または [A]2 ⊆ f−1{1})」となること。 U が κ-一様選抜的（英: uniformly selective）とは、X の任意の κ の分割 P が与えられたとき、「Q⊆ P が存在して |Q| < κ かつ ⋃ Q ∈ U {\textstyle \bigcup Q\in U} であるかさもなくば、ある A ∈ U が存在して、任意の B ∈ P に対し、|B ∩ A| = 1」となること。 U がP-点 とは、X の任意の可算分割 P が与えられたとき、「P ∩ U ≠ ∅ であるかさもなくば、ある A ∈ U が存在して、任意の B ∈ P に対し、|B ∩ A| < ∞」となること。 ただし、P ⊆ P(X) が互いに素な集合からなる集合族でその合併が X と一致するとき X の分割といい、[A]2 ≔ {B ⊆ A : |B| = 2} とする。 特に U が ω-一様選抜的なとき単に選抜的といい、|X|-一様選抜的なとき一様選抜的という。 無限グラフとその頂点集合上のラムゼーフィルター U を固定する。このとき有限色の辺彩色が任意に与えられれば、彩色に関する等質集合を U の元に取れる。これがラムゼーという呼び名の由来である。 このP-点の定義は β(X) ∖ X 上の位相的なP-点の定義と一致する。明らかに選抜的ならP-点である。 ウォルター・ルーディンは連続体仮説から可算集合上のラムゼーフィルターの存在を証明している。更にマーティンの公理を始めとする様々な仮定からラムゼーフィルターの存在は証明されている。逆にサハロン・シェラハはP-pointの存在がZFCから示せないことを証明した。以上からこれらの存在はZFCから独立であることが分かる。 このようなフィルターの性質は「無限の組合せ論」等と呼ばれる集合論の分野の一部をなし、集合論的な議論の基礎をなしている。 基本性質 自由な超フィルターがラムゼーであることと選抜的であることは同値。 自由な超フィルターが選抜的であることと、自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。 自由な超フィルターが κ-一様選抜的であることと、κ-一様で自由な超フィルター全体のルディン・キースラー順序に関する極小元であることが同値。 アローの不可能性定理 社会選択理論において、超フィルターは、無限人の選好を集計するための (社会厚生関数とよばれる) 集計ルールを構築するために用いられる。 具体的には構成員からなる無限集合を M、選択肢の集合を C とし、M 上のフィルター F を固定し、各人の選好 (≤m)m∈M としたとき、F による被約積によって構成された選好 (≤m)m∈M/F は半順序となる。特に F が超フィルターのときは全順序となる。この集計ルールが普遍性、全会一致性、独立性を満たすのは構成から直ちに従う。非独裁性が成り立つのは超フィルター F が自由になるちょうどその時である。 以上より、有限人ケースに対する有名なアローの不可能性定理の述べるところと異なり、そのような集計ルールは、アローが提示した条件 (公理) をすべて満たす。 しかしながら、そのような集計ルールを計算するようなアルゴリズムは存在しないため、それらの集計ルールの実用的な意味合いは乏しいことが指摘されており、アローの不可能性定理をかえって強化する結果となっている。