跳转到内容

剩余格

维基百科,自由的百科全书

抽象代数中,剩余格是既为又为幺半群代数结构,使得幺半群乘法的每个自变量都是关于这个格次序的伽罗瓦连接的一极。它的一般概念是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.