閉包作用素

テンプレート:Pathnav 閉包作用素（へいほうさようそ、テンプレート:Lang-en-short）とは、半順序集合あるいは集合の冪集合上に定義される、拡大的・単調・冪等的な自己写像である。ある対象を、それを含む最小の「閉じた」対象へ移す作用として理解でき、位相空間における閉包、群・環・ベクトル空間における生成作用素、凸包、順序集合におけるイデアル生成など、多くの数学的構成を統一的に記述する。順序論・束論では基本概念の一つであり、閉集合系（ムーア族）、ガロア接続、完備束、形式概念分析、Horn 論理、frame の nucleus などと密接に関係する。

概要

閉包作用素の本質は、各対象に対し「それを含む最小の閉対象」を対応させる点にある。閉包作用素の不動点は閉元あるいは閉集合を与え、それらは通常、任意交叉に関して閉じた族をなす。したがって、閉包作用素の理論は閉集合系の理論と本質的に同値である。

位相空間の閉包作用素は代表的な例であるが、順序論においては閉包作用素を位相から独立な一般概念として扱う。とくに完備束上では、閉包作用素の像は閉元全体からなる完備部分束となり、逆に適切な完備部分束から閉包作用素を復元できる。さらに閉包作用素全体も自然な順序のもとで完備束をなす。

定義

半順序集合上の定義

半順序集合 $(P,\le )$ 上の自己写像

$c:P\to P$

が、任意の $x,y\in P$ に対して次の三条件を満たすとき、$c$ を 閉包作用素 という。

1. 拡大的（extensive, inflationary）: $x\le c(x)$
2. 単調（monotone, isotone）: $x\le y\Rightarrow c(x)\le c(y)$
3. 冪等的（idempotent）: $c(c(x))=c(x)$

$c(x)=x$ を満たす元 $x$ を $c$ に関する 閉元（closed element）という。冪等性により、閉包作用素の像と不動点集合は一致する。

冪集合上の定義

集合 $X$ の冪集合 $𝒫(X)$ 上の写像

$\mathrm{cl}:𝒫(X)\to 𝒫(X)$

が、任意の部分集合 $A,B\subseteq X$ に対して

1. $A\subseteq \mathrm{cl}(A)$
2. $A\subseteq B\Rightarrow \mathrm{cl}(A)\subseteq \mathrm{cl}(B)$
3. $\mathrm{cl}(\mathrm{cl}(A))=\mathrm{cl}(A)$

を満たすとき、これを $X$ 上の閉包作用素という。$\mathrm{cl}(A)$ を $A$ の 閉包 と呼ぶ。

前閉包作用素

冪等性を課さず、拡大的かつ単調な自己写像だけを考えることもあり、これは 前閉包作用素（preclosure operator）と呼ばれる。通常の閉包作用素はその特別な場合である。

閉集合系との対応

集合 $X$ の部分集合族 $𝒞\subseteq 𝒫(X)$ が任意交叉で閉じているとき、$𝒞$ を 閉集合系（closure system）または ムーア族（Moore family）という。

閉包作用素 $\mathrm{cl}$ が与えられると、その閉集合全体

${𝒞}_{\mathrm{cl}}=\{F\subseteq X\mid \mathrm{cl}(F)=F\}$

はムーア族をなす。逆に、ムーア族 $𝒞$ が与えられると、

${\mathrm{cl}}_{𝒞}(A)=\bigcap \{F\in 𝒞\mid A\subseteq F\}$

によって閉包作用素が定まる。

したがって、閉包作用素とムーア族は一対一に対応する。とくに、任意の部分集合 $A$ の閉包は、$A$ を含むすべての閉集合の交叉として与えられる。

基本性質

閉包作用素 $c$ に対して次が成り立つ。

• $c(x)$ は $x$ を上から支配する閉元のうち最小のものである。
• 閉元全体は、存在する任意の交わりについて閉じる。
• 完備束上では閉元全体は完備束をなし、その結びは元の結びを取ったあと閉包を施すことで与えられる。
• 2つの閉包作用素 $c,d$ に対し、$c\le d$ を「任意の $x$ について $c(x)\le d(x)$」で定めると、これは対応する閉元集合についての逆包含関係に対応する。

例

位相空間における閉包

位相空間 $X$ において、各部分集合 $A\subseteq X$ にその位相的閉包 $\bar{A}$ を対応させる写像

$A\mapsto \bar{A}$

は閉包作用素である。 さらに

$\mathrm{cl}(\varnothing )=\varnothing ,\mathrm{cl}(A\cup B)=\mathrm{cl}(A)\cup \mathrm{cl}(B)$

が成り立つ。この2条件を加えたものがクラトフスキーの閉包公理であり、位相的閉包作用素を特徴づける。

線型包・生成部分代数

ベクトル空間 $V$ の部分集合 $A$ に対して、その線型包

$A\mapsto \mathrm{Span}(A)$

を対応させる写像は閉包作用素である。同様に、群における生成部分群、環における生成部分環、普遍代数における生成部分代数を与える作用素も閉包作用素である。

正規閉包

群 $G$ の部分集合 $A$ に対し、$A$ を含む最小の正規部分群

$A\mapsto ⟨A{⟩}^G$

を対応させる写像は閉包作用素である。

凸包

実ベクトル空間の部分集合にその凸包を対応させる作用素

$A\mapsto \mathrm{conv}(A)$

も閉包作用素である。

順序イデアル生成

順序集合 $P$ の部分集合 $A$ に対し、それが生成する順序イデアル

$\downarrow A=\{x\in P\mid \mathrm{\exists }a\in A,x\le a\}$

を対応させる作用素も閉包作用素である。

有限型閉包作用素

閉包作用素 $\mathrm{cl}$ が

$\mathrm{cl}(A)=\bigcup \{\mathrm{cl}(F)\mid F\subseteq A,F\text{ は有限}\}$

を満たすとき、有限型（finitary）または 代数的（algebraic）であるという。 有限型閉包作用素では、閉包が有限部分集合の情報によって決まる。群・環・ベクトル空間・普遍代数における生成作用素、順序イデアル生成作用素は典型的に有限型である。

有限閉包系

有限集合 $X$ 上の閉包作用素、あるいはそれと同値な閉集合系は、有限閉包系（finite closure system）として組合せ論的・計算論的に詳しく研究される。有限の場合、閉包作用素の理論は束論に加えて、形式概念分析、データベース理論、論理プログラミング、Horn 論理などと強く結び付く。

有限閉包系では、閉集合全体を列挙する問題、閉包作用素を短い規則系で表す問題、標準的な含意基底を構成する問題などが重要となる。

含意系による記述

有限集合 $X$ 上の 含意（implication）とは、通常

$A\to B$

の形の規則であり、$A,B\subseteq X$ である。部分集合 $S\subseteq X$ がこの含意を満たすとは、

$A\subseteq S\Rightarrow B\subseteq S$

が成り立つことをいう。

含意族 $\mathrm{\Sigma }$ が与えられると、それを満たすすべての部分集合の族は閉集合系をなす。逆に、任意の有限閉包系は適当な含意族によって記述できる。したがって有限閉包系、有限集合上の閉包作用素、含意系は本質的に同値な記述である。

この対応により、閉包作用素は「規則の反復適用による推論装置」とみなされる。実際、含意族 $\mathrm{\Sigma }$ と部分集合 $A\subseteq X$ に対し、$A$ から出発して、前件が満たされる含意の後件を順次追加していくことで、$A$ の閉包が得られる。

形式概念分析との関係

形式概念分析（Formal Concept Analysis, FCA）では、対象集合 $G$、属性集合 $M$、両者の二項関係 $I\subseteq G\times M$ からなる 形式文脈（formal context）

$⟨G,M,I⟩$

を考える。対象の部分集合 $A\subseteq G$ に対し、$A$ のすべての対象に共通する属性全体 $A^{\uparrow }$ を、属性の部分集合 $B\subseteq M$ に対し、$B$ のすべての属性を共有する対象全体 $B^{\downarrow }$ を対応させると、これらはガロア接続をなす。

このとき

$A\mapsto A^{\uparrow \downarrow }$

は $G$ 上の閉包作用素であり、

$B\mapsto B^{\downarrow \uparrow }$

は $M$ 上の閉包作用素である。

FCA における 形式概念 は、$A^{\uparrow }=B$ かつ $B^{\downarrow }=A$ を満たす組 $(A,B)$ として定義される。これらの全体は包含順序のもとで概念束（concept lattice）をなす。

FCA において閉包作用素は、概念を定義するだけでなく、属性間の依存関係を含意として抽出する役割も担う。Ganter による Next Closure は、閉属性集合を辞書式に列挙する標準的手法であり、概念束の計算および含意基底の構成に広く用いられる。

Horn 論理との関係

有限閉包系の含意系による記述は、Horn 論理と自然に対応する。有限集合 $X$ の各元を命題変数とみなすと、含意

$A\to B$

は definite Horn clause の合取として表現できる。したがって、含意系で定義された閉集合は Horn 理論のモデルとみなすことができる。

closure query は definite Horn formula の学習と閉包計算を直接結び付ける概念であり、Arias・Balcázar・Tîrnăucă は closure query と canonical Guigues–Duquenne basis との関係も論じている。

基底と正準基底

有限閉包系を表す含意族のうち、同じ閉包作用素を定めるものは一般に一意ではない。そのため、閉包系をできるだけ短く、かつ標準的に表す基底を求める問題が生じる。形式概念分析ではとくに Guigues–Duquenne 基底（Duquenne–Guigues basis, canonical basis）が重要であり、これは有限閉包系を表す代表的な正準基底として広く用いられる。

直接基底、ordered direct basis、正準基底の比較は、有限閉包系の計算理論における中心問題であり、前向き連鎖の効率や知識圧縮とも関係する。

アルゴリズム的側面

有限閉包系では、与えられた集合の閉包を計算する問題、すべての閉集合を列挙する問題、閉包系を表す含意基底を構成する問題、基底の形を最適化する問題が基本となる。

Ganter の Next Closure は、任意の閉包系の閉集合を漏れなく重複なく列挙する基本アルゴリズムである。また、Duquenne–Guigues 基底の計算でも閉集合の生成が主要な部分問題となる。

ガロア接続との関係

半順序集合 $P,Q$ の間のガロア接続

$f:P\to Q,g:Q\to P$

に対して、

$g\circ f:P\to P$

は $P$ 上の閉包作用素となる。集合間の二項関係から得られる古典的なガロア接続は、閉包作用素の主要な起源の一つである。

Everett は、束上の閉包作用素とガロア理論の関係を系統的に論じ、閉包概念の順序論的定式化を与えた。

完備束・代数的束との関係

完備束 $L$ 上の閉包作用素 $c$ に対し、閉元全体

$L_c=\{x\in L\mid c(x)=x\}$

は完備束をなす。任意族 $(x_i)$ の閉元に対し、その交わりは $L$ における交わりと一致し、結びは

$\underset{L_c}{\bigvee }{x}_i=c\left(\underset{L}{\bigvee }{x}_i\right)$

で与えられる。

逆に、適切な完備部分束から閉包作用素を構成できる。さらに代数的完備束は、有限型閉包作用素の閉集合束として現れることが多い。

閉包作用素全体の束

完備束 $L$ 上の全ての閉包作用素の集合を $\mathrm{Cl}(L)$ とし、

$c\le d⟺\mathrm{\forall }x\in L,c(x)\le d(x)$

で順序づけると、$\mathrm{Cl}(L)$ は完備束をなす。これは Ward の古典的結果である。

理論計算機科学では、この束は抽象解釈における抽象領域の空間として解釈される。Ranzato は Ward の定理を CPO に拡張し、CPO 上の閉包作用素全体も完備束をなすことを示した。

nucleus

frame（無限分配束） $L$ 上の閉包作用素 $j$ がさらに有限交わりを保存する、すなわち

$j(x\wedge y)=j(x)\wedge j(y)$

を満たすとき、$j$ を nucleus という。nucleus の不動点全体は再び frame をなし、locale 論では部分 locale に対応する。

nucleus 全体は点wise順序のもとで frame をなし、その結びは一般に単純な点wise結びでは記述できない。

内部作用素との双対

閉包作用素の双対概念は内部作用素（interior operator）であり、半順序集合上の自己写像

$i:P\to P$

であって、

1. $i(x)\le x$
2. $x\le y\Rightarrow i(x)\le i(y)$
3. $i(i(x))=i(x)$

を満たすものである。冪集合上では補集合演算により閉包作用素と内部作用素は相互に移り合う。

歴史

閉包作用素の思想は一般位相の初期に現れ、のちに順序論的に一般化された。1940年代には Ward が閉包作用素全体の束構造を論じ、Everett がガロア接続との関係を明確化した。20世紀後半以降、閉包作用素は束論・普遍代数・形式概念分析・ドメイン理論・抽象解釈・locale 論へと応用範囲を広げた。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• 閉包 (位相空間論)
• 閉集合
• 内部 (位相空間論)
• ガロア接続
• 束 (束論)
• 完備束
• 順序集合
• 完備半順序
• 随伴関手
• 凸包
• 推移閉包