分配格子

数学において、分配格子とは、結合と会合の演算が互いに分配される格子のことである。このような構造の典型的な例は、集合の集合であり、それらの格子演算は集合の和集合と積集合によって与えられる。実際、これらの集合の格子は風景を完全に記述する。つまり、すべての分配格子は、同型性を除き、そのような集合の格子として与えられる。

任意の格子の場合と同様に、分配格子L を順序理論の構造として考えるか、普遍代数の構造として考えるかを選択できます。両方の見解とそれらの相互対応については、格子に関する記事で説明されています。現在の状況では、代数的記述の方が便利であると思われます。

格子 ( L ,∨,∧) が分配的であるとは、 L内のすべてのx、y、zに対して次の追加の恒等式が成り立つ場合です。

x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) です。

格子を半順序集合として見ると、meet操作は空でない有限結合を保存することがわかります。上記の条件がその双対と同等であることは格子理論の基本的な事実です。^[1]

L内のすべてのx、y、zについて、 x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) です。

すべての格子において、順序関係p ≤ q を通常通りp ∧ q = pと定義すると、不等式x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ) とその双対x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ) は常に真となります。逆不等式の 1 つも成立する場合、格子は分配的です。この条件と順序理論の他の分配条件との関係の詳細については、記事「分配性 (順序理論)」を参照してください。

分配格子の射は、格子に関する記事で述べられているように、格子準同型、つまり 2 つの格子演算と互換性のある関数です。このような格子の射は格子構造を保存するため、結果的に分配性も保存されます (したがって、分配格子の射になります)。

分配格子はどこにでもあるが、かなり特殊な構造でもある。すでに述べたように、分配格子の主な例は集合の格子であり、結合と会合は通常の集合論的演算によって与えられる。その他の例としては、次のものがある。

• 論理積と論理和をサポートするほとんどの論理のリンデンバウム代数は分配格子です。つまり、「and」は「or」に分配され、逆もまた同様です。
• すべてのブール代数は分配格子です。
• すべてのHeyting 代数は分配格子です。特に、これにはすべての局所と、したがって位相空間のすべての開集合格子が含まれます。また、Heyting 代数は直観主義論理の Lindenbaum 代数として見ることができるため、最初の例の特別なケースになります。
• すべての完全に順序付けられた集合は、最大値が結合し、最小値が会合する分配格子です。
• 自然数は、最大公約数を meet とし、最小公倍数を join として、 (条件付きで完全な) 分配格子を形成します。この格子には最小元、つまり 1 もあり、これは join の単位元として機能します。
• 正の整数nが与えられると、 nのすべての正の約数の集合は分配格子を形成し、ここでも最大公約数は meet 、最小公倍数は join となります。これは、nが平方でない場合に限り、ブール代数です。
• 格子順序ベクトル空間は分配格子です。
• 整数分割を表すヤング図の包含順序によって与えられるヤングの格子は分配格子である。
• 分配多面体（座標最小値と座標最大値の演算によって閉じた凸多面体）の点。この2つの演算は格子の結合演算と会合演算となる。^[2]

格子理論の発展の初期に、チャールズ・S・パースは、すべての格子は分配的である、つまり分配性は格子公理の残りから従うと信じていました。^{[3] [4]} しかし、独立性の証明はシュレーダー、フォークト、^（デ） リューロート、コルセルト、^[5]デデキントによって与えられました。^[3]

上記の定義には、様々な同等の定式化が存在する。例えば、Lが分配的であるためには、L内のすべての要素x、y、zに対して次の式が成り立つ必要がある。 同様に、Lが分配的であるためには、次の式が成り立つ必要がある。 $${\displaystyle (x\wedge y)\vee (y\wedge z)\vee (z\wedge x)=(x\vee y)\wedge (y\vee z)\wedge (z\vee x).}$$

${\displaystyle x\wedge z=y\wedge z}$そして常に暗示する${\displaystyle x\vee z=y\vee z}$${\displaystyle x=y.}$

最も単純な非分配的格子は、 M ₃（「ダイヤモンド格子」）とN ₅（「五角形格子」）です。格子が分配的であるのは、その部分格子のいずれもM ₃または N ₅と同型ではない場合のみです。部分格子は、元の格子の meet および join 操作の下で閉じている部分集合です。これは、元の順序の下で格子である部分集合と同じではないことに注意してください（ただし、join および meet 操作は異なる可能性があります）。次のセクションの表現理論から、さらに特徴づけが導き出されます。

同じ事実を別の方法で述べると、すべての分配格子は2元鎖のコピーの部分直積である、または分配格子のクラスの部分直約不可能な唯一の要素は2元鎖である、ということになります。結果として、すべてのブール格子もこの性質を持ちます。^[6]

最後に、分配法則は他のいくつかの好ましい性質を伴う。例えば、分配格子の元がmeet-primeであるのは、それがmeet-irreducibleである場合のみであるが、後者は一般に弱い性質である。双対性により、 join-prime元とjoin-irreducible元についても同じことが言える。 ^[7]格子が分配法則である場合、その被覆関係は中央値グラフを形成する。^[8]

さらに、すべての分配格子もモジュラーです。

導入部で、分配束の最も重要な特徴付けについてすでに触れました。つまり、束が分配的であるためには、それが集合の束と同型である必要があります (集合の和集合と積集合に関して閉じている)。(後者の構造は、この文脈では集合の環と呼ばれることもあります。) 集合の和集合と積集合が上記の意味で分配的であることは、基本的な事実です。もう一方の方向はそれほど簡単ではなく、以下に述べる表現定理を必要とします。この特徴付けから得られる重要な洞察は、すべての分配束で成り立つ恒等式 (方程式) は、上記の意味ですべての集合の束で成り立つものとまったく同じであるということです。

バーコフの分配束の表現定理は、すべての有限分配束は、その結合素数（つまり結合既約）元のposetの下側集合の束に同型であると述べている。これにより、すべての有限 poset のクラスとすべての有限分配束のクラスの間に、 （同型性を除いて）一対一の関係が確立される。この一対一の関係は、有限分配束の準同型と有限 poset の単調関数の間のカテゴリの双対性に拡張できる。ただし、この結果を無限束に一般化するには、さらに構造を追加する必要がある。

もう一つの初期の表現定理は、分配格子に対するストーンの表現定理として知られています（この名前は、最初に証明したマーシャル・ハーヴェイ・ストーンにちなんで付けられました）。これは、分配格子を、特定の位相空間のコンパクトな 開集合の格子として特徴付けます。この結果は、ブール代数に対するストーンの有名な表現定理の一般化と、ストーン双対性の一般的な設定の特殊化の両方として見ることができます。

さらに重要な表現は、ヒラリー・プリーストリーが分配格子の表現定理で確立した。この定式化では、分配格子を使用して、その点に追加の部分順序を持つ位相空間を構築し、（完全に順序が分離された）順序付きストーン空間（またはプリーストリー空間）を生成する。元の格子は、この空間の閉開下集合のコレクションとして復元される。

ストーンの定理とプリーストリーの定理の結果として、任意の分配格子は集合の格子と同型であることが容易に分かります。しかし、両方の命題の証明には、選択公理の弱い形であるブール素イデアル定理が必要です。

生成子の集合G上の自由分配格子は、一般の自由格子よりもはるかに簡単に構築できます。最初の観察結果は、分配法則を使用すると、生成子の集合上の二項演算とによって形成されるすべての項を、次の同等の正規形に変換できることです。 ${\displaystyle \lor}$${\displaystyle \land}$

${\displaystyle M_{1}\lor M_{2}\lor \cdots \lor M_{n},}$

ここで、 はGの要素の有限の meets です。さらに、 meet と join は両方とも結合法則、可換法則、およびべき等法則を持っているため、重複と順序を無視して、上記のような meets の join を集合の集合として表すことができます。 ${\displaystyle M_{i}}$

${\displaystyle \{N_{1},N_{2},\ldots ,N_{n}\},}$

ここで はGの有限部分集合です。しかし、そのような 2 つの項が分配格子の同じ要素を表す可能性はまだあります。これは、が の部分集合であるような添え字jとk がある場合に起こります。この場合、 の交わりはの交わりよりも下になるため、項全体の解釈を変えずに冗長な集合を安全に削除できます。したがって、 Gの有限部分集合の集合は、そのすべての要素が相互に比較不可能な場合 (部分集合の順序に関して)、つまり有限集合の反連鎖を形成する場合は常に冗長でないと呼ばれます。 ${\displaystyle N_{i}}$${\displaystyle N_{j}}$${\displaystyle N_{k}.}$${\displaystyle N_{k}}$${\displaystyle N_{j},}$${\displaystyle N_{k}}$${\displaystyle N_{i}}$

ここで、生成子集合G上の自由分配格子は、 Gの有限部分集合のすべての有限非冗長集合の集合上で定義されます。2 つの有限非冗長集合の結合は、すべての冗長集合を削除することでそれらの和集合から得られます。同様に、2 つの集合SとTの交わりは、の非冗長バージョンです。この構造が、必要な普遍的特性を持つ分配格子であることの検証は、日常的に行われます。 ${\displaystyle \{N\cup M\mid N\in S,M\in T\}.}$

n個の生成元を持つ自由分配格子の要素の数はデデキント数で与えられる。これらの数は急速に増加し、n  ≤ 9の場合にのみ知られている。

2、3、6、20、168、7581、7828354、2414682040998、56130437228687557907788、286386577668298411128469151667598498812366（OEISの配列A000372）。

上記の数字は、空集合を含む有限集合の結合と会合である自由分配格子内の要素の数を数える。空結合と空会合が禁止されている場合、結果として得られる自由分配格子の要素数は2つ少なくなり、その要素数は次の数列を形成する。

0、1、4、18、166、7579、7828352、2414682040996、56130437228687557907786、286386577668298411128469151667598498812364（OEISの配列A007153）。

• 完全分配格子- 無限の結合が無限の会合に分配される格子
• 分配格子の双対性理論
• スペクトル空間

• Burris, Stanley N.; Sankappanavar, HP (1981)。普遍代数の講座。Springer- Verlag。ISBN 3-540-90578-2。
• OEISシーケンス A006982 (n 個の要素を持つラベルなし分配格子の数)