自由格子

数学の秩序理論の分野において、自由格子は格子に対応する自由対象である。自由対象として、それらは普遍的性質を持つ。

格子の概念は、2 つの演算と特定の恒等式を満たすことで公理化できるため、すべての格子のカテゴリは多様体 (普遍代数)を構成し、したがって (普遍代数の一般原理により)このカテゴリ内には自由オブジェクト、つまり一般公理から導かれる関係 のみが成り立つ格子が存在します。${\displaystyle \wedge}$${\displaystyle \vee}$

これらの自由格子は、関連する普遍的性質を用いて特徴付けることができる。具体的には、自由格子は、 各集合に、それぞれに対応する要素を割り当てる集合写像を備えた自由格子を割り当てる、集合から格子への関数である。これらの普遍的性質は、から任意の格子への任意の写像に対して、を満たす一意の格子準同型が存在すること、または可換図として が存在することである。 関数は、格子からその基礎となる集合への忘却関数の左随伴である。 ${\displaystyle F}$ ${\displaystyle X}$${\displaystyle F(X)}$${\displaystyle \eta \colon X\longrightarrow F(X)}$${\displaystyle x\in X}$${\displaystyle \eta (x)\in F(X)}$${\displaystyle f\colon X\longrightarrow L}$${\displaystyle X}$${\displaystyle L}$ ${\displaystyle {\tilde {f}}\colon F(X)\longrightarrow L}$${\displaystyle f={\tilde {f}}\circ \eta }$$${\displaystyle {\begin{array}{cccc}X&{\stackrel {\eta }{\longrightarrow }}&F(X)\\&\!\forall f\searrow &{\Bigg \downarrow }\exists _{1}{\tilde {f}}\!\!\!\!\!\!\!\!\!\!&\quad \\&&L\end{array}}}$$${\displaystyle F}$

自由格子に関する事柄は普遍的性質を使って直接証明できることが多いですが、そのような議論はむしろ抽象的になりがちなので、具体的な構成は貴重な代替表現となります。

半格子の場合、自由半格子 の明示的な構成は簡単に与えられます。これは、普遍的性質という形で定義のいくつかの特徴を説明するのに役立ちます。具体的には、自由半格子 は、のすべての有限の空でない部分集合の集合として実現され、通常の集合の和は結合演算 として用いられます。写像 は、の要素を単集合に写像します。つまり、すべての に対して となります。任意の半格子および任意の集合写像に対して、対応する普遍射はによって与えられます 。 ここで はにおける半格子演算を表します。 ${\displaystyle F_{\vee}(X)}$${\displaystyle F_{\vee}(X)}$${\displaystyle X}$${\displaystyle \vee}$${\displaystyle \eta \colon X\longrightarrow F_{\vee }(X)}$${\displaystyle X}$${\displaystyle \eta (x)=\{x\}}$${\displaystyle x\in X}$${\displaystyle L}$${\displaystyle f\colon X\longrightarrow L}$ ${\displaystyle {\tilde {f}}\colon F_{\vee }(X)\longrightarrow L}$$${\displaystyle {\tilde {f}}(S)=\bigvee _{x\in S}f(x)\qquad {\text{すべての}}S\in F_{\vee }(X)に対して}$$${\displaystyle \bigvee}$${\displaystyle L}$

のこの形式は、普遍的性質によって強制されます。つまり、任意の は、いくつかのに対しての形式上の元の有限和として表すことができ、普遍的性質 における等式は を言い、最後に の準同型性状態は、すべての に対してを意味します。ただし、 の無限部分集合への任意の拡張(存在する場合) は、これらの条件によって一意に決定される必要はないため、の無限部分集合に対応する の元は存在できません。 ${\displaystyle {\tilde {f}}}$${\displaystyle S\in F_{\vee }(X)}$${\displaystyle \eta (x)}$${\displaystyle x\in X}$${\displaystyle {\tilde {f}}{\bigl (}\eta (x){\bigr )}=f(x)}$${\displaystyle {\tilde {f}}}$${\displaystyle {\チルダ {f}}(S_{1}\cup S_{2})={\チルダ {f}}(S_{1})\vee {\チルダ {f}}(S_{2} )}$${\displaystyle S_{1},S_{2}\in F_{\vee }(X)}$${\displaystyle {\tilde {f}}}$${\displaystyle X}$${\displaystyle F_{\vee}(X)}$${\displaystyle X}$

同様に、下側の半格子に対して自由関数を定義することも可能だが、 は単なる集合として 扱うため、その組み合わせではいくつかの点で自由格子を生成できない。${\displaystyle F_{\wedge}}$${\displaystyle F_{\wedge}(F_{\vee}(X))}$${\displaystyle F(X)}$${\displaystyle F_{\wedge}}$${\displaystyle F_{\vee}(X)}$

• 結合操作はの新しい要素には拡張されません。${\displaystyle \vee}$${\displaystyle F_{\wedge}(F_{\vee}(X))}$
• 上の既存の部分順序は尊重されません。ビューとを無関係なものとして理解せずに、 を作成する必要があります。${\displaystyle F_{\vee}(X)}$${\displaystyle F_{\wedge}}$${\displaystyle a}$${\displaystyle a\vee b}$${\displaystyle a\wedge (a\vee b)=a}$

自由格子の実際の構造は、自由半格子の構造よりもかなり複雑です。 ${\displaystyle F(X)}$

自由束の単語問題には、いくつか興味深い側面があります。有界束、つまり 2 つの二項演算 ∨ と ∧ および 2 つの定数 (零項演算) 0 と 1 を持つ代数構造の場合を考えてみましょう。与えられた生成元集合Xの要素に対してこれらの演算を使用して定式化できるすべての整形式の式の集合をW ( X )と呼びます。この単語集合には、すべての束で等しい値を表すことになる多くの式が含まれています。たとえば、a がXの何らかの要素である場合、a  ∨ 1 = 1 かつa  ∧ 1 = aです。自由有界束の単語問題は、 W ( X ) のこれらの要素のうちどれが自由有界束FX内の同じ要素を表し、したがってすべての有界束内で 同じ要素を表すかを決定する問題です。

単語問題は次のように解決できる。W ( X )上の関係≤ _~は、以下のいずれ かが成り立つ場合にのみ、w≤ _~ vと設定することで帰納的に定義できる。

1.   w = v （これはwとvがXの要素である場合に限定される）、
2.   0 ,
3.   v = 1,
4.   w = w ₁ ∨ w ₂かつw ₁ ≤ _~ vとw ₂ ≤ _~ v が成立する、
5.   w = w ₁ ∧ w ₂かつw ₁ ≤ _~ vまたはw ₂ ≤ _~ vのいずれかが成立する、
6.   v = v ₁ ∨ v ₂かつw ≤ _~ v ₁またはw ≤ _~ v ₂が成立する、
7.   v = v ₁ ∧ v _{2であり、} w ≤ _~ v ₁とw ≤ _~ v _{2 の}両方が成立します。

これはW ( X )上の前順序≤ _~を定義するので、w ≤ _~ vかつv ≤ _~ wのとき、w ~ vによって同値関係を定義できます。次に、部分的に順序付けられた商空間W ( X )/~ が自由有界格子FXであることを示します。^{[1] [2]} W ( X )/~の同値類は、 w ≤ _~ vかつv ≤ _~ wであるすべての単語 w および v の集合です。 W ( X ) 内の 2 つの整形式の単語 vおよびwがすべての有界格子で同じ値を表すのは、 w ≤ _~ vかつv ≤ _~ w の場合のみです。後者の条件は、上記の帰納的定義を使用して効果的に決定できます。表は、単語x ∧ zおよびx ∧ z ∧( x ∨ y ) がすべての有界格子で同じ値を表すことを示す計算例を示しています。境界のない格子の場合も同様に扱われますが、上記の構成では規則 2 と 3 は省略されます。

自由格子上の単語問題の解決には、いくつかの興味深い帰結があります。1つは、3要素の生成元セットの自由格子が無限であるということです。実際、3つの生成元上のすべての自由格子には、4つの生成元セットに対して自由である部分格子が含まれていることを示すこともできます。帰納法によって、これは最終的に可算な数の生成元に対して自由な部分格子をもたらします。^{[3]この特性は、}グループにおけるSQ普遍性を彷彿とさせます。

3つの生成元における自由格子が無限であることの証明は、帰納的に定義することによって進む。

p _{n +1} = x ∨ ( y ∧ ( z ∨ ( x ∧ ( y ∨ ( z ∧ p _n ))))

ここで、x、y、z は3つの生成元であり、p ₀ = xです。単語問題の帰納的関係を使用して、p _{n +1 は}p _n よりも厳密に大きい^[4]ため、無限個の単語p _{n は}すべて自由格子FXで異なる値に評価されることがわかります。

もう 1 つの帰結は、完全な自由束(3 つ以上の生成元上)は、適切なクラスであるという意味で「存在しない」ということです。この証明は、単語問題からも得られます。関係の観点から完全な束を定義するには、 meet と joinの有限関係を使用するだけでは不十分です。無限の部分集合の meet と join を定義する無限関係も必要です。たとえば、「join」に対応する無限関係は次のように定義できます。

${\displaystyle \operatorname {sup} _{N}:(f:N\to FX)}$

ここで、f は基数 Nの要素からFXへの写像です。演算子は、 fの像をその結合に取るという点で、最大値を表します。これは、もちろん、Nが有限数の場合の「結合」と同じです。この定義のポイントは、 N が無限基数の場合であっても、結合を関係として定義することです。 ${\displaystyle \operatorname {sup} _{N}}$

単語問題の順序付けの公理は、meetとjoinに対応する2つの無限演算子によって接続される。その後、定義を次のように 順序付けされたインデックスに拡張する。${\displaystyle p_{n}}$${\displaystyle p_{\alpha}}$

${\displaystyle p_{\alpha }=\operatorname {sup} \{p_{\beta }\mid \beta <\alpha \}}$

が極限順序数のとき、 となります。すると、前と同様に、が より確実に大きいことが示されます。したがって、完全自由格子には順序数と同じ数以上の要素が存在するため、完全自由格子は集合として存在できず、したがって適切なクラスでなければなりません。 ${\displaystyle \alpha}$${\displaystyle p_{\alpha +1}}$${\displaystyle p_{\alpha}}$

• Peter T. Johnstone, Stone Spaces , Cambridge Studies in Advanced Mathematics 3, Cambridge University Press, Cambridge, 1982. ( ISBN  0-521-23893-5 ) (第 1 章を参照)