Loading article…
数学において、分配束に関するバーコフの表現定理は、任意の有限分配束の要素は、束演算が集合の和集合と積集合に対応するような有限集合として表現できると述べています。ここで、束は「出会う」演算と「結合する」演算という2つの二項演算を持つ抽象的な構造であり、これらの演算は特定の公理に従わなければなりません。これらの2つの演算が分配法則に従う場合、それは分配的であると言えます。これらの演算に関して閉じている集合族における和集合と積集合演算は、自動的に分配束を形成し、バーコフの表現定理は、（同型を除いて）すべての有限分配束がこのように形成できると述べています。これは、1937年にその証明を発表したギャレット・バーコフにちなんで名付けられました。 [ 1 ]
この定理は、分配束と部分順序、準順序知識空間と前順序、または有限位相空間と前順序の間に一対一の対応関係を提供するものとして解釈できる。
「バーコフの表現定理」という名称は、バーコフの他の2つの結果にも適用されている。1つは1935年の、ブール代数を和集合、積集合、補集合に関して閉じた集合族（いわゆる集合の体であり、バーコフが分配束を表現するために使用した集合の環と密接に関連している）として表現することに関するもので、もう1つは、代数を既約代数の積として表現するバーコフのHSP定理である。バーコフの表現定理は、有限分配束の基本定理とも呼ばれている。[ 2 ]
多くの束は、束の要素が集合で表され、束の結合演算が集合の和集合で表され、束の交わり演算が集合の積集合で表されるように定義できます。例えば、有限集合のすべての部分集合の族から定義されるブール束はこの性質を持ちます。より一般的には、任意の有限位相空間は、開集合の族として集合の束を持ちます。集合の和集合と積集合は分配法則に従うため、このように定義された束はすべて分配束です。バーコフの定理は、実際にはすべての有限分配束がこのようにして得られることを述べており、バーコフの定理の後の一般化では、無限分配束についても同様のことが述べられています。
（図のように）120のような合成数の約数を、割り切れる順に部分的に並べたものを考えます。120の約数である12と20は、最大公約数12∧20 = 4 （両方を割り切る最大の数）と最小公倍数12∨20 = 60を持ち、どちらも120の約数です。これらの2つの演算∨と∧は、2つの同等の形式のいずれかで分配法則を満たします。( x∧y ) ∨z = ( x∨z ) ∧ ( y∨z )と( x∨y ) ∧z = ( x∧z ) ∨ ( y∧z )、すべてのx 、y、zについて。したがって、除数は有限分配束を形成する。
各約数を、それを割り切る素数の集合と関連付けることができます。例えば、12 は集合 {2,3,4} と関連付けられ、20 は集合 {2,4,5} と関連付けられます。すると、12 ∧ 20 = 4 は集合 {2,3,4} ∩ {2,4,5} = {2,4} と関連付けられ、12 ∨ 20 = 60 は集合 {2,3,4} ∪ {2,4,5} = {2,3,4,5} と関連付けられるため、格子の結合演算と交わり演算は、集合の和集合と積集合に対応します。
これらの集合の要素として現れる素数のべき乗 2、3、4、5、8 は、可除性によって部分的に順序付けられることがあります。このより小さな部分順序では、2 ≤ 4 ≤ 8 であり、他のペア間には順序関係はありません。120 の約数に関連付けられている 16 個の集合は、このより小さな部分順序の下位集合であり、 x ≤ yであり、 y が部分集合に属する場合、xも部分集合に属する必要があるような要素の部分集合です。任意の下位集合Lから、 L内の素数のべき乗の最小公倍数を計算することで、関連する約数を復元できます。したがって、5 つの素数のべき乗 2、3、4、5、8 に関する部分順序は、元の 16 要素の可除性格子全体を復元するのに十分な情報を持っています。
ビルコフの定理は、約数の束の演算∧と∨と、それに対応する素数のべき乗の集合の演算∩と∪との間のこの関係は偶然ではなく、素数と整除性の特定の性質にも依存しないことを述べている。つまり、任意の有限分配束の要素は、同様の方法で半順序の下位集合と関連付けることができる。
別の例として、 n個の要素からなる集合の部分集合の束を考えてみましょう。これは包含関係によって部分的に順序付けられています。バーコフの定理によれば、この束はn 個の生成元上の自由分配束の下位集合によって生成され、その要素数はデデキント数で与えられます。
束において、要素xが他の有限個の要素の結合でない場合、その要素は結合既約である。言い換えれば、 x が束の最下位要素 (0 個の要素の結合) でも、それより小さい 2 つの要素の結合でもない場合、x は結合既約である。例えば、120 の約数の束では、結合が 4 となる要素のペアは存在しないため、4 は結合既約である。要素xが結合素数であるとは、それが最下位要素と異なり、x ≤ y ∨ zの場合には、x ≤ yまたはx ≤ zのいずれかが成り立つ場合である。同じ束において、4 は結合素数である。すなわち、lcm( y , z ) が 4 で割り切れる場合には、yとzの少なくとも一方が 4 で割り切れる必要がある。
任意の束において、結合素元は結合既約でなければならない。言い換えれば、結合既約でない元は結合素元ではない。なぜなら、元xが結合既約でない場合、x = y ∨ zとなるような、より小さいyとzが存在するからである。しかし、この場合x ≤ y ∨ zとなり、x はyまたはzより小さくも等しくもないため、結合素元ではないことがわかる。
結合素元が結合既約元の真部分集合を形成する束が存在するが、分配束では2種類の要素が一致する。なぜなら、xが結合既約であり、x ≤ y ∨ zであると仮定するからである。この不等式は、 x = x ∧ ( y ∨ z )という記述と同値であり、分配法則によりx = ( x ∧ y ) ∨ ( x ∧ z )となる。しかし、xは結合既約であるため、この結合の2つの項のうち少なくとも1つはx自身でなければならず、x = x ∧ y (同値にx ≤ y )またはx = x ∧ z (同値にx ≤ z )のいずれかであることがわかる。
結合既約要素の部分集合上の格子順序は半順序を形成します。バーコフの定理によれば、この半順序の下位集合から格子自体を復元することができます。
任意の半順序において、下位集合は束を形成し、その束の半順序は集合の包含によって与えられ、結合操作は集合の和集合に対応し、交わり操作は集合の積集合に対応する。これは、和集合と積集合が下位集合であるという性質を保持するためである。集合の和集合と積集合は分配法則に従うため、これは分配束である。バーコフの定理によれば、任意の有限分配束はこのように構成できる。
つまり、 Lの要素と部分順序の下位集合の間には、順序を保持する 1 対 1 の対応関係が存在する。Lの要素xに対応する下位集合は、単にx以下のLの結合既約要素の集合であり、結合既約要素の下位集合Sに対応するLの要素は、Sの結合である。
結合既約要素の任意の下位集合Sに対して、 x をSの結合とし、Tをx以下の結合既約要素の下位集合とする。このとき、S = Tとなる。なぜなら、 Sのすべての要素は明らかにTに属し、 x以下の結合既約要素は(結合素数性により) S のいずれかの要素以下でなければならず、したがって ( Sが下位集合であるという仮定により) S 自体に属しなければならないからである。逆に、 Lの任意の要素xに対して、Sをx以下の結合既約要素とし、y をSの結合とする。このとき、 x = yとなる。なぜなら、y はx以下の要素の結合であるため、x 自身より大きくなることはないが、x が結合既約であればxはSに属し、x が 2 つ以上の結合既約要素の結合であれば、それらは再び S に属しなければならないので、y ≥ xとなるからである。したがって、対応関係は1対1であり、定理は証明された。
バーコフ (1937) は、集合の和集合と積集合の操作に関して閉じている集合の族を集合の環と定義しました。後に、数理心理学への応用に着想を得て、ドワニョンとファルマーニュ (1999)は同じ構造を準順序知識空間と呼びました。集合の環内の集合が包含関係によって順序付けられている場合、それらは分配束を形成します。集合の要素には、環内のいずれかの集合がx を含み、かつy を含まない場合にx ≤ yとなるような前順序を与えることができます。集合の環自体は、この前順序の下位集合の族であり、任意の前順序はこのようにして集合の環を生み出します。
前述の通り、バーコフの定理は個々の半順序と分配束との間の対応関係を示しています。しかし、この定理は、半順序の順序保存関数と、対応する分配束の有界準同型写像との間の対応関係にも拡張できます。この対応関係では、これらの写像の方向が反転します。
2 を2 要素集合 {0, 1} 上の順序関係 0 < 1 を持つ部分順序とし、(スタンレーに従って) J(P)を有限部分順序Pの下集合の分配束とする。このとき、 J(P)の要素は、Pから2への順序保存関数と 1 対 1 で対応する。[ 2 ]なぜなら、 ƒ がそのような関数である場合、 ƒ −1 (0) は下集合を形成し、逆にL が下集合である場合、 L を0 に写像し、 Pの残りの要素を 1 に写像する順序保存関数 ƒ Lを定義できるからである。gがQからPへの任意の順序保存関数である場合、関数の合成を使用してJ(P)の任意の要素Lを ƒ L ∘ gに写像する関数g * を J(P) からJ ( Q)に定義できる。この合成関数はQ を2に写像するため、 J(Q)の要素g *( L ) = (ƒ L ∘ g ) −1 (0) に対応します。さらに、J(P)の任意のxとyに対して、g *( x ∧ y ) = g *( x ) ∧ g *( y ) ( Qの要素が、xに写像される要素の集合とyに写像される要素の集合の両方に属する場合に限り、gによって下位集合x ∩ yに写像されます) であり、対称的にg *( x ∨ y ) = g *( x ) ∨ g *( y ) となります。加えて、 J(P)の下位要素( Pのすべての要素を 0 に写像する関数) はg * によってJ(Q)の下位要素に写像され、 J(P)の上位要素はg * によってJ(Q)の上位要素に写像されます。つまり、g * は有界格子の準同型写像である。
しかし、 Pの要素自体は、J(P)から2への有界格子準同型と 1 対 1 で対応します。なぜなら、x がPの任意の要素である場合、 x を含むすべての下位集合を1 に、他のすべての下位集合を 0 に写像する有界格子準同型j xを定義できるからです。また、 J(P)から2への任意の格子準同型に対して、1 に写像されるJ(P)の要素は、一意の最小要素x (1 に写像されるすべての要素の交わり) を持つ必要があり、これは結合既約でなければなりません (0 に写像される要素の集合の結合であってはなりません)。したがって、すべての格子準同型は、あるxに対してj x の形をとります。また、 J(P)からJ(Q)への任意の有界格子準同型hから、関数の合成を使用して、 QからPへの順序保存写像h *を定義できます。QからPへの任意の順序保存写像gに対してg ** = gが成り立ち、J(P)からJ(Q)への任意の有界格子準同型写像hに対してh ** = hが成り立つことが確認できる。
圏論の用語では、Jは反変ホム関手J = Hom(—, 2 )であり、一方では有限部分順序と順序保存写像の圏、他方では有限分配束と有界束準同型の圏との間の圏の双対性を定義します。
無限分配束では、結合既約要素の下位集合が束の要素と一対一に対応するとは限りません。実際、結合既約要素がまったく存在しない場合もあります。これは、例えば、通常の割り算の順序とは逆の順序で並べられたすべての自然数の束（つまり、 y がxを割り切るときにx ≤ yとなる）で起こります。任意の数x は、異なる素数pとqの数xpとxqの結合として表すことができます。ただし、無限分配束の要素は、ストーンの分配束表現定理によって集合として表現できます。これは、各束要素が特定の位相空間のコンパクトな開集合に対応するストーン双対性の一形態です。この一般化された表現定理は、分配束とスペクトル空間（コヒーレント空間と呼ばれることもあるが、線形論理のコヒーレント空間とは異なる）との間の圏論的双対性として表現できる。スペクトル空間とは、コンパクトな開集合が交差に関して閉じており、位相の基底を形成する位相空間である。 [ 3 ]ヒラリー・プリーストリーは、ストーンの表現定理は、ナッハビンの順序付き位相空間の考え方を用いて、半順序の下位集合によって束の要素を表現するという考え方を拡張したものとして解釈できることを示した。プリーストリー分離公理によって位相と結び付けられた追加の半順序を持つストーン空間は、有界分配束を表現するためにも使用できる。このような空間はプリーストリー空間として知られている。さらに、ペアワイズ・ストーン空間と呼ばれる特定の双位相空間は、集合上の2つの位相を利用して抽象的な分配束を表現することで、ストーンの元のアプローチを一般化している。このように、バーコフの表現定理は、少なくとも３つの異なる方法で無限（有界）分配束の場合に拡張され、分配束の双対性理論にまとめられています。
バーコフの表現定理は、分配束以外の有限構造にも一般化できる。分配束では、自己双対メディアン演算[ 4 ]
はメディアン代数を生成し、束の被覆関係はメディアングラフを形成します。有限メディアン代数とメディアングラフは、2-充足可能性インスタンスの解の集合として双対構造を持ちます。Barthélemy & Constantin (1993)は、この構造を混合グラフの初期安定集合の族として等価に定式化しています。[ 5 ]分配束の場合、対応する混合グラフには無向エッジがなく、初期安定集合はグラフの推移閉包の下位集合です。同様に、分配束の場合、 2-充足可能性インスタンスの含意グラフは、インスタンスの正の変数と負の変数の2つの連結成分に分割できます。正の成分の推移閉包は、分配束の基礎となる半順序です。
バーコフの表現定理に類似する別の結果で、より広いクラスの束に適用されるものとして、エデルマン（1980）の定理がある。この定理によれば、任意の有限結合分配束は、アンチマトロイドとして表現できる。アンチマトロイドとは、和集合に関して閉じているが、交差に関して閉じている性質が、各空でない集合が除去可能な要素を持つという性質に置き換えられた集合の族である。
