跳至內容

剩餘格

維基百科,自由的百科全書

抽象代數中,剩餘格是既為又為幺半群代數結構,使得幺半群乘法的每個自變量都是關於這個格次序的伽羅瓦連接的一極。它的一般概念是Ward和Dilworth在1939年介入的。某些例子先於一般概念而存在,包括布爾代數Heyting代數剩餘布爾代數關係代數MV-代數。剩餘半格省略了交運算∧,比如克萊尼代數作用代數

定義

數學中,剩餘格代數結構L = (L, ∧, ∨, ·, I, /, \)使得

(i) (L, ∧, ∨)是
(ii) (L, ·, I)是幺半群
(iii)對於所有L 中的x, y, z,有yx\zx·yzxz/y(剩餘公理)。

條件(iii)的效果是,對每個L中的xzx\z成為最大的y使得x·yz,對偶的對於每個L中的yzz/y成為最大x使得x·yz

運算x\yy/x分別叫做yx的「右剩餘」和「左剩餘」。如符號所暗示的那樣它們是某種形式的商。更加精確地說,對於一個給定的L中的x,一元運算x·和x\是在L和它的序對偶之間的伽羅瓦連接的兩極,並且對偶於兩個函數·y和 /y。通過同樣適用於伽羅瓦連接的推理,我們有了另一個剩餘的定義,就是:

x·(x\y) ≤ yx\(x·y),
(y/xxy ≤ (y·x)/x

並且要求這些函數必須在L上是單調的(或反單調的,在被看作從L到它的序對偶的函數的時候,這是在格理論中表示伽羅瓦連接的更標準的方式)。其意義在於使函數x·和x\相互之間是偽逆(pseudoinverse)或伴隨,·x和 /x也類似。

最後這個定義純粹依據不等式,注意單調性可以公理化為x·y ≤ (xzy,其他運算和它們的自變量也類似。而且任何不等式xy可以等價的表示為等式,要麼xy = x要麼xy = y。這與格和幺半群的等式公理化一起生成剩餘格的純等式定義,而它們形成了一個等式類或。注意分配律x·(yz) = (x·y) ∨ (x·z)是這些公理的結論所以不需要是定義的一部分。在幺半群乘法是∧的時候,剩餘格變成為Heyting代數,這種格是分配性的,但是一般的說格不需要是分配性的,而它的·分配在∨之上。

x\y的可供替代的符號是xyy/x的可供替代的符號是yx,這是在剩餘和邏輯蘊涵之間的類似性所暗示的,而幺半群的乘法可以被理解為不需要是交換性的某種形式的合取。當幺半群是交換性的時候這兩種剩餘是一致的。

x·y的可供替代的符號包括xy, x;y關係代數),和xy線性邏輯)。I的可供替代的符號包括e和1'。

例子

布爾代數Heyting代數是交換剩餘格,在其中x·y = xy(而單位元I是代數的頂元素1)而兩個剩餘x\yy/x是同一個運算,就是蘊涵xy。第二個例子非常一般性,因為Heyting代數包換所有有限分配格,和形成完全格的所有鏈或全序,例如實數軸上的單位區間[0,1],或者整數和±

結構(Z, min, max, +, 0, −, −)(整數帶有兩個剩餘都是減法)是交換剩餘格,使得幺半群的單位元不是最大元素(實際上這裡沒有最小或最大元素),而幺半群的乘法不是這個格的交運算。在這個例子中,不等式就是等式,因為−(減法)不只是+的伴隨或偽逆運算而真就是它的逆運算。任何在加法下的全序群比如有理數或實數都可替代這個例子中的整數。任何這些例子的非負部分都假定了minmax被互換並且−被替代為「monus」(定義為在xyx-y = 0其他時候為正常減法)的例子。

更一般性的一類例子是在給定集合X的所有二元關係也就是X2冪集的布爾代數,通過選取幺半群乘法·為關係複合,選取幺半群單位元為由在所有Xx的有序對(x,x)構成的恆等關係I而成為剩餘格。給定在X上的兩個關係RSSR的右剩餘R\S是二元關係使得x(R\S)y只在對於所有X中的zzRx蘊涵zSy的時候成立(注意與蘊涵的聯繫)。左剩餘是它的鏡像:y(S/R)x在對於所有X中的zxRz蘊涵ySz的時候成立。

可用在{0,1}上的二元關係<和>來展示,在其中0 < 1和1 > 0是唯一成立的關聯。那麼x(>\<)y只在x = 1的時候成立,而x(</>)y只在y = 0的時候成立,顯示出<對>的剩餘是不同的,依賴於我們剩餘在右側還是在左側。這種不同是在<;>和>;<和之間的不同的推論,這裡唯一成立的關聯是0(<;>)0(因為0<1>0)和1(>;<)1 (since 1>0<1)。如果我們轉而選擇≤和≥,≥\≤和≤/≥是同樣的,因為≤;≥ = ≥;≤,二者在所有xy之間總是成立(因為x≤1≥y並且x≥0≤y)。

字母表(集合)Σ上的所有形式語言的布爾代數2Σ*形成了剩餘格,它的幺半群乘法是語言串接LM而它的幺半群單位元I是由空字符串ε足成的語言{ε}。右剩餘M\L構成自所有在Σ上的字w是的MwL。左剩餘L/MwM替代了左剩餘中的Mw

只在X為有限的時候X上的所有二元關係的剩餘格是有限的,並且只在X有最多一個元素的時候是交換的。當X為空的時候代數是退化的布爾代數其中0 = 1 = I。只在Σ有最多一個字母的時候Σ上的所有語言的剩餘格是交換的。只在Σ為空的時候它是有限的,這時它由兩個語言0(空語言{})和幺半群單位元I = {ε} = 1構成。

形成有特殊性質的布爾代數的例子請參見剩餘布爾代數

剩餘半格

剩餘半格除了省略了交運算∧之外同一於剩餘格。它是代數結構L = (L, ∨, ·, 1, /, \)滿足上面規定的所有剩餘格等式,除了包含符號∧的之外。定義xyxy = x的選項就不可用了,只留下了另一個選項xy = y(或任何等價者)。

通過簡單的省略∧用任何剩餘格製作出剩餘半格。剩餘半格起因於與作用代數的聯繫,它是也是克萊尼代數的剩餘半格,它通常不需要∧。

引用

  • Ward, Morgan, and Robert P. Dilworth (1939) "Residuated lattices," Trans. Amer. Math. Soc. 45: 335-54. Reprinted in Bogart, K, Freese, R., and Kung, J., eds. (1990) The Dilworth Theorems: Selected Papers of R.P. Dilworth Basel: Birkhäuser.