残留格子

抽象代数において、残余格子は、格子x ≤ y であると同時にモノイドx • yでもある代数構造であり、 x • y をそれぞれ乗算または連言と見なすと、除算または含意に大まかに類似した演算x \ zおよびz / yを許容します。それぞれ右残余および左残余と呼ばれるこれらの演算は、モノイドが可換である場合に一致します。一般概念は、 1939 年にMorgan WardとRobert P. Dilworthによって導入されました。一般概念より前に存在していた例としては、ブール代数、Heyting 代数、残余ブール代数、関係代数、およびMV 代数などがあります。残余半格子は、 Kleene 代数や作用代数などの meet 演算 ∧ を省略します。

意味

数学において、残余格子は代数構造 $L = (L, \leq, •, I)$ であり、

(i) ( L ,≤)は格子である。

(ii)

(L, •, I)は

モノイドである。

(iii) すべてのzに対して、任意のxに対して最大のy が存在し、任意のyに対して最大のx が存在し、 x • y ≤ z を満たす（残差特性）。

(iii) では、 zとxの関数である「最大のy 」はx \ zで表され、xによるzの右残差と呼ばれます。これは、左側のzをxで「割った」後に右側のzが残るものと考えてください。同様に、「最大のx 」はz / yで表され、yによるzの左残差と呼ばれます。これらの演算を使用してこれらの最大値に名前を付ける (iii) の同等でより正式な記述は、次のとおりです。

(iii) L内のすべてのx、y、zについて、 y ≤ x \ z ≡ x • y ≤ z ≡ x ≤ z / y。

表記法からわかるように、残差は商の一種です。より正確には、L内の与えられたxに対して、単項演算x • とx \ はそれぞれL上のガロア接続の上下随伴関数であり、2 つの関数 • yと / yに対しても左右随伴関数です。ガロア接続に適用されるのと同じ理由から、残差の別の定義が存在します。

x •( x \ y ) ≤ y ≤ x \( x • y )、かつ

( y / x )• x ≤ y ≤ ( y • x )/ x、

およびx • y がxおよびyに関して単調であるという要件。((iii) または (iii)' を使用して公理化されると、単調性は定理になり、したがって公理化では必須ではなくなります。) これらは、関数 $x •$ および $x \ が$ 互いの擬似逆または随伴関数であるという感覚を与え、 $• x$ および $/ x$ についても同様です。

この最後の定義は純粋に不等式に関するものであり、単調性は $x • y \leq (x \lor z) • y$ として公理化でき、他の演算とその引数についても同様であることに注意してください。さらに、任意の不等式x ≤ y は、 $x \land y = x$ または $x \lor y = y$ のいずれかの方程式として同等に表現できます。これは、格子とモノイドを公理化する方程式とともに、必要な演算がシグネチャ $(L 、\leq、•、 I)に付加され、それによって$ $( L、∧、∨、•、I、/、\)$ に拡張される限り、残余格子の純粋に方程式的な定義をもたらします。このように整理されると、残余格子は方程式クラスまたは方程式多様体を形成し、その準同型は格子およびモノイド演算と同様に残余を尊重分配法則 $x • (y \lor z) = (x • y) \lor (x • z)$ およびx •0 = 0 はこれらの公理の結果であるため、定義の一部にする必要がないことに注意してください。 • の $\lorに対する分配法則は、一般に$ $\landの$ $\lor$ に対する分配法則を伴いません。つまり、残余格子は分配格子である必要はありません。ただし、 • と $\landが同じ演算である場合、$ $\landの$ $\lor$ に対する分配法則が伴います。これは、 Heyting 代数と呼ばれる残余格子の特殊なケースです。

x • yの代替表記法には、x ◦ y、x ; y (関係代数)、x ⊗ y (線型論理)などがあります。 $I$ の代替表記法には、 eと 1' があります。残差の代替表記法は、x \ yの場合はx → y、y / xの場合はy ← xです。これは、論理における残差と含意の類似性から示唆されており、モノイドの乗法は、必ずしも可換である必要のない連言の形として理解されています。モノイドが可換の場合、2つの残差は一致します。可換でない場合、連言としてのモノイドと含意としての残差の直感的な意味は、時間的な性質を持つものとして理解できます。x • y はxの次にy を意味し、 x → y はx (過去)があった後にy (現在)を意味し、y ← x は、例の最後の自然言語の例で示されているように、常にx (将来)があった後にy (その時点) を意味します。

例

残余格子の研究の元々の動機の 1 つは、環の (2 辺)イデアルの格子でした。環Rが与えられたとき、 Rのイデアル $(Id($ $R$ $)$ と表記)は、集合交差がミート演算として機能し、「イデアル加算」がジョイン演算として機能する完全な格子を形成します。モノイド演算 • は「イデアル乗算」によって与えられ、 $Id($ $R$ $)$ の元R はこの演算の恒等式として機能します。 Id $($ $R$ $)$ の2 つのイデアルAとB が与えられたとき、残余は次のように与えられます。

A/B:=\{r\in R\mid rB\subseteq A\}

B\setminus A:=\{r\in R\mid Br\subseteq A\}

{0}/ BとB \{0} はそれぞれBの左消滅子と右消滅子であることに注目する価値があります。この残余は、可換代数の導体（またはトランスポーター）に関連しており、( A : B )= A / Bと記述されます。使用法の1つの違いは、 B がRのイデアルである必要はなく、単にサブセットである可能性があることです。

ブール代数とヘイティング代数は、 x • y = x ∧ y（したがって単位 $I$ は代数の最上位要素 1 です）であり、残差x \ yとy / x の両方が同じ演算、つまり含意x → yである、可換剰余格子です。2 番目の例は非常に一般的です。ヘイティング代数は、すべての有限分配格子だけでなく、すべての連鎖または全順序、たとえば実数直線上の単位区間 [0,1] や整数およびを含むためです。 $\pm \infty$

構造 ( Z、min、max、 +、 0、 −、 −) (両方の残差が減算された整数) は、モノイドの単位が最大元ではない (実際、最小または最大の整数は存在しない) ような可換残差格子であり、モノイドの乗算は格子の meet 演算ではない。この例では、不等式が等式であるのは、 − (減算) が + の単なる随伴または擬似逆ではなく、真の逆であるためである。この例の整数の代わりに、有理数や実数などの加算による全順序群を使用することができる。これらの例の非負部分はいずれも、minとmaxが交換され、 − がmonusに置き換えられた場合の例であり、この場合、 x ≤ yの場合はx - y = 0 となり、それ以外の場合は通常の減算となるように定義される。

より一般的な例のクラスは、集合X 、すなわちX ²の冪集合上のすべての二項関係のブール代数によって与えられ、これはモノイド乗法 • を関係の合成と見なし、モノイド単位を X 上のすべての対 ( x , x ) からなる X 上の恒等関係 I と見なすことによって剰余格子を作成します。 X上の2つの関係Rと S を考えると、 RによるSの右剰余R \ S は、Xのすべてのzに対してzRxがzSy を意味するときにのみx ( R \ S ) y が成立する二項関係です(含意との関連に注意)。左剰余はこれの鏡像で、X のすべてのzに対してxRz がySz を意味するときにのみy ( S / R ) xが成立します。

これは、{0,1} 上の 2 項関係 < および > で説明できます。この関係では、0 < 1 および 1 > 0 のみが成り立ちます。すると、x (>\<) y はx = 1の場合にのみ成り立ち、x (</>) y はy = 0の場合にのみ成り立ち、< による > の剰余は、右または左のどちらで剰余するかによって異なることがわかります。この違いは、<•> と >•< の違いによるもので、ここで成立する関係は 0(<•>)0 (0<1>0 であるため) と 1(>•<)1 (1>0<1 であるため) のみです。< と > の代わりに ≤ と ≥ を選択した場合、≥\≤ と ≤/≥ は同じになります。これは、≤•≥ = ≥•≤ であり、どちらも常にすべてのxとy の間で成立するためです( x ≤1≥ yおよびx ≥0≤ yであるため)。

アルファベット（集合）Σ上のすべての形式言語のブール代数2 ^Σ*は、モノイド乗算が言語連結LMであり、モノイド単位 $I$ が空文字列εのみからなる言語{ε}である剰余格子を形成します。右剰余M \ Lは、Mw ⊆ LとなるΣ上のすべての単語wで構成されます。左剰余L / Mは、 Mwの代わりにwMと同じになります。

X上のすべての二項関係の残余格子は、Xが有限であるときのみ有限であり、X が最大で 1 つの要素を持つときのみ可換です。Xが空の場合、代数は $0 = 1 = I$ となる退化したブール代数です。 Σ 上のすべての言語の残余格子は、 Σ が最大で 1 つの文字を持つときのみ可換です。 Σ が空で、2 つの言語 0 (空言語 {}) とモノイド単位 $I = {ε} = 1$ で構成されるときのみ有限です。

ブール代数を形成する例には、残余ブール代数に関する記事で扱われる特別な特性があります。

自然言語では、残余格子は「そして」の非可換な意味で使用される場合の「そして」の論理を形式化します。x = bet、y = win、z = richと設定すると、 x • y ≤ z は「賭けてから勝つと金持ちが必然的に生じる」と読むことができます。公理により、これは $y \leq x \to z の$ 「勝つと賭けてから金持ちが必然的に生じる」に相当し、また $x \leq z \leftarrow y$ の「賭けると、もしあれば勝つと金持ちが必然的に生じる」に相当します。人間は、「賭けると、もしあれば勝つと金持ちが必然的に生じる」や「勝つと、もしあれば賭けてから金持ちが必然的に生じる」などの不合理な表現が、どちらも「勝つと賭けると金持ちが必然的に生じる」という希望的観測に等しいことをすぐに察知します。^{[要出典]人間は、}パースの法則(( P → Q )→ P )→ Pが古典的なトートロジーであることを容易には検出しません。これは、人間が古典的な推論よりも非古典的な推論の方が熟達しているという興味深い状況です (たとえば、関連性論理では、パースの法則はトートロジーではありません)。^{[関連性あり? ]}

残余半格子

残余半格子は、残余格子とほぼ同じように定義されますが、ミート演算 ∧ だけが省略されます。したがって、これは、記号∧ の出現を含むものを除いて、上で指定されたすべての残余格子方程式を満たす代数構造 $L = (L, ∨, •, 1, /, \)です$ 。x ≤ y を $x \land y = x$ として定義するオプションは使用できず、他のオプション $x \lor y = y$ (またはそれと同等のもの) のみが残ります。

任意の残余格子は、単に∧ を省略するだけで残余半格子にすることができます。残余半格子は、作用代数に関連して生じます。作用代数は残余半格子であり、クリーネ代数でもありますが、この場合、∧ は通常は必要ありません。

参照

参考文献

Ward, MorganおよびRobert P. Dilworth (1939)「Residuated lattices」、Trans. Amer. Math. Soc. 45 : 335–54。Bogart, K.、Freese, R.、および Kung, J. 編 (1990) The Dilworth Theorems: Selected Papers of RP Dilworth Basel: Birkhäuserに再録。
Nikolaos Galatos、Peter Jipsen、Tomasz Kowalski、小野博明 (2007)、Residuated Lattices。「An Algebraic Glimpse at Substructural Logics」、エルゼビア、ISBN 978-0-444-52141-5。