没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记344(2019)169-188www.elsevier.com/locate/entcs拟Nelson代数Umberto Rivieccio1,2Dep artamentodeInform'aticaeMatem'aticaAplicadaUniversidade Federal do Rio Grante do Norte巴西纳塔尔马修·斯宾克斯3Dipartimento di Pedagogia,Psicologia,FilosofiaUniversit`adiCagliari意大利卡利亚里摘要我们介绍了一个推广的纳尔逊代数有一个不一定对合否定,我们建议这类拟纳尔逊代数的类比拟德摩根格,这些是一个非对合推广的德摩根格。我们表明,类似于对合的情况下(也许sur-(1)拟Nelson剩余格,这些代数模型包括:(1)非对合扭结构,即Heyting代数的特殊积,它推广了Nelson构造性逻辑的强负代数模型的构造;(2)拟Nelson代数,即Heyting代数的特殊积,它推广了Nelson构造性逻辑的强负代数模型的构造非对合纳尔逊逻辑的模型被视为直觉主义逻辑的否定自由片段的保守这三种表示的等价性,特别是扭结构表示到非对合情形的扩展,是本文的主要技术结果。 然而,我们希望,主要影响可能是开辟新途径的可能性,(i)更深入地了解纳尔逊逻辑的特点代数对应;(ii)能够调查某些纯代数性质(如3-效力和(0,1)-同余有序性)在更一般的设置。关键词:纳尔逊逻辑,拟纳尔逊代数,拟纳尔逊剩余格,半德摩根代数,非对合扭结构,纳尔逊恒等式。1引言Nelson作为一个保守的扩展,否定自由片段的直觉主义逻辑的一个新的一元连接词的强否定(强否定),或,以内[1]第一作者要感谢梁飞对本文主题的几次初步讨论;特别是梁飞提供了命题2.4(x)的部分证明2电子邮件:urivieccio@dimap.ufrn.br3电子邮件:mspinksau@yahoo.com.auhttps://doi.org/10.1016/j.entcs.2019.07.0111571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。170联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169等价,作为FL ew的公理化扩展,具有交换和弱化的完全Lambek演算[4]4. 因此,N3的代数模型被称为Nelson代数或Nelson剩余格[20]。众所周知,FLew是所有交换积分剩余格的逻辑[4];加上双重否定公理(xx),得到满足对合恒等式(xx)的交换积分剩余格的逻辑NInFLew进一步补充Nelson公理:((x精确地得到了Nelson这些正是满足对合恒等式和纳尔逊公理的代数对应物(即纳尔逊恒等式)的交换积分剩余格:(x(xy))(y(y x))x y。(Nelson)纳 尔 逊公 理 / 恒 等 式是 一 个 强大 而 又 有 点神 秘 的 公理 。 当 我 们把 它 加 到NInFLew上时,我们很容易得到分配律(x<$(y<$z))<$((x<$y)<$(x<$z))以及(3, 2)-压缩(x(x(xy)(x(xy))而在NInFLew中两者都不成立。此外,N3的代数模型允许一个很好的表示作为Heyting代数的乘积(所谓的扭结构)[18,13],并且这个构造也关键地使用了Nelson公理。在最近的系列论文[10,11,19]中,我们一直在仔细研究Nelson家族中的逻辑和Nelson公理/恒等式,重点关注其在扩展FLew的逻辑中的含义和后果。具体地说,论文[10,11]研究了从N3中得到的逻辑和代数,通过丢弃尼尔森公理,同时保持双重否定和(3, 2)-收缩;而在[19]中,我们确定并研究了一些条件(代数,句法和序论),这些条件在NInFLew的上下文中与尼尔森公理/恒等式等价。如[19,问题8.2和8.3]中所述,尚未解决的主要问题之一是,上述特征中的哪些(如果有的话)可以在比NInFLew更一般的上下文中获得,即(首先)FLew,所有交换积分剩余格的逻辑换句话说,我们可能会问,一旦我们放弃双重否定律,纳尔逊公理的后果是什么?上述结果是否成立,例如,纳尔逊公理是否仍然允许我们证明(3,2)-收缩和分配性?对应逻辑的代数对应物是什么是[4](一个给定逻辑的)扩展,我们指的是比同一语言更强的逻辑;扩展,我们指的是通过增加新的连接词而获得的逻辑联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169171有“非对合Nelson剩余格”的合理概念也许令人惊讶的是,这些问题的答案大多是肯定的,本文是我们在不一定对合剩余格的背景下理解纳尔逊公理的第一个尝试。我们的策略如下。模仿的方法,证明成功的研究纳尔逊的建设性逻辑与强否定N3及其代数模型,我们将介绍和查看“非对合纳尔逊剩余格”在三个(1) 作为准Nelson剩余格,即FLew模型加上Nelson公理;(2) 作为非对合扭结构,即Heyting代数的特殊积,推广了N3的代数模型的构造;(3) 作为准纳尔逊代数,即非对合纳尔逊逻辑的模型,被视为直觉主义逻辑的否定自由片段的扩展本文的主要结果,推广了著名的等价N3模型,是上述三类都是项等价5。因此,我们将在第2节中引入拟纳尔逊剩余格作为另外满足纳尔逊恒等式(1)的交换积分剩余格;然后我们挑出所有拟纳尔逊剩余格满足的某些性质(命题2.5),我们将在后面将其作为我们定义拟纳尔逊代数(3)的基础。证明我们的命名,我们将指出(命题2.7),就像每个Nelson剩余格有一个De Morgan代数约简,每个拟Nelson剩余格有一个拟De Morgan代数约简[16]。在第三节中,我们引入了非对合扭结构(2),证明了每一个这样的结构都是拟Nelson剩余格(定理3.3)。可能值得指出的是,直到最近的论文[7,8],在文献中还没有已知的这种结构可以让人们表示携带非对合否定的代数。最后,在第4节中,我们关闭了我们的等价循环,引入了拟Nelson代数(3),并证明了每个这样的代数都可表示为非对合扭结构。 整体等价性总结在最终定理4.4中。我们想指出的是,我们的间接证明策略不仅是无法避免的,而且暂时(我们还没有直接证明,例如,命题2.7),而且很有见地,因为我们把拟Nelson剩余格表示为扭结构,这为构造这种代数的具体例子提供了一种简单的方法。最后,让我们强调,虽然在本文中我们只研究代数,但重要的是,有逻辑头脑的读者要记住,我们将代数视为逻辑的代数对应物;这种策略是合理的,因为我们处理的是可代数化的逻辑[1],所以我们可以直接将结果从代数转移到逻辑。[5]不严格地说,这意味着这三个定义可以被看作是“同一”类代数在不同代数语言中的不同表示172联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169“我的天,2-拟Nelson剩余格我们假设熟悉一般代数和模型论的基础知识,特别是一阶逻辑中被称为方程逻辑的部分。对于一般的代数背景,见[3,5,9]。定义2.1交换积分有界剩余格(CIBRL)是一个代数A=A;,0, 1,其类型为2,2, 2, 2, 0,0,使得:(i) 交换么半群,(Mon)(ii) <$A;<$,<$,0, 1<$是有界格(阶≤),(Lat)(iii) a<$b≤ci <$a≤b<$c,对所有a,b,c∈A。(RES)在CIBRLA上,常数0的存在允许我们定义一个否定运算(),由a:=a 0给出,对于所有a∈A。我们需要的另一个缩写是an:=a· · ·a(按照惯例,我们让a0:= 1和a1:=a)。正如我们将n次所有的准纳尔逊剩余格都满足恒等式x2<$x3。 这确实是理解这类代数的一个关键性质:它被称为3-幂性(或其他作者的2-幂性),是(3, 2)-压缩的代数对应。使用这些缩写,我们在下面的命题中列出了CIBRL的一些众所周知的性质,我们将在续集中使用(它们在[4,引理]中得到证明2.6 2.8.或者说,这是一个简单的过程。命题2.2设A是CIBRL,a,b,c,d∈A。 以下属性成立:(i) a≤biab = 1。(ii) (a b)c = a(b c)。(iii) a ≤ b ≤a。(iv) 如果a ≤ b且c ≤ d,则a<$c ≤ b<$d。(v) (a(vi) (a(vii) a(a b)≤ a b。(viii) a ≤ 100% a.(ix) a(b c)=(a b)(a c)。(x) a = 0.(xi) 如果a ≤b,则b ≤ a。(xii) ∼∼∼ a= ∼a.(xiii) ab = ab。(xiv) aCIBRLA的一个非空子集F是一个滤波器,如果对所有的a,b∈A,它有:(i)a≤b且a∈F蕴涵b∈F;(ii)a,b∈F蕴涵a∈b∈F联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169173(one很容易证明,这样的F必须是一个通常意义上的格过滤器,虽然反过来可能不成立,因为(ii)可能不成立)。 对于a∈A,set [a)={b∈A:ak≤b,for somepositive integerk}是一个滤波器,即由a生成的滤波器。此外,如果A是n+ 1-幂次的,则[a)={b∈A:an≤b}。对CIBRL滤波器的研究尤为重要,因为从逻辑角度来看, 的观点,他们对应的逻辑理论的FLew,代数,他们是在一对一的对应关系与同余。特别地,众所周知,用ΘA(x,1)表示由对(x,1)生成的主同余,有[a)<$[b)当且仅当ΘA(a,1)<$ΘA(b,1)。我们将在下面的命题2.4的证明中使用这个事实(更多细节见[19]定义2.3准纳尔逊剩余格是满足纳尔逊恒等式的CIBRL(x(xy))(y(yx))xy(Nelson)通过命题2.2(ii),我们可以用下面的方式等价地重新表述纳尔逊恒等式(这在后面会很有用(x2y)((y)2x)x y。(Nelson ')下面我们收集了一些有用的性质,这些性质在所有的拟纳尔逊剩余格上都成立命题2.4设A是拟Nelson剩余格,a,b,c∈A.以下属性成立:(i) 如果a2≤ b且(b)2≤ b a,则a ≤ b。(ii) a= a2a)。(iii) a2 = a3。(iv) a≤b我的 Θ A(b,1)<$Θ A(a,1)和Θ A(a,0)<$Θ A(b,0)。(v) A的格约简是分配的。(vi) ab = a b(a b)。(vii) ∼ ∼(a ∗ b)= ∼∼ a ∗ ∼ ∼ b.(viii) (a <$b)2=(a <$b)2。(ix) (ab))2 =(a ab)2。(x)(a b))2=(a b))2。(xi) ((a2 b))2。证据(i). 如果a2≤b,则a2<$b= 1,由命题2.2(i)。 类似地,我们得到(b)2<$a= 1。然后使用(Nelson),我们有ab=(a2b)<$((ab)2<$a)= 1< $1 = 1,这使得我们需要a≤b。(二).观察到a2a)≤a在所有CIBRL中成立,因为命题2.2(iii)证明a2≤a,而格的性质证明aa≤a因此,还需要证明a≤a2a)。我们将使用上述第(i)项,一方面检查174联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)1692A a aAa2≤a2a),这是平凡的,另一方面,(a)2≤你好我们有:(a2)(a2)(a 1)(a2)(a2)(a 1)(a 2)(a 1)(a 2)(a 1)(a 2)(a 2)(a 1)(a 2)(a 1)(a 2)(a 2)(a 1)(a 2)(a 1)(a 2)(a 1)(a 2)(a 2)(a 1)(a2)(a 1)(a 2)(a 1)(a 2)(a2.2(五)=((aa)(a a))2,按第2.2(vi)条计算根据Prop. 2.2(iv),≤(aa)(a a)(xy)≤xy。因此,证明(aa)(a a)≤a就足够了。使用(Res),我们有(aa)(aa)≤aia(a a)(a a)≤0 ia(aa)≤结果如下,因为命题2.2(vii)和(viii)我们有一个(aa)≤aa≤(aa)。(iii). 利用上面的第(ii)项,我们将证明(a2a)) 2≤a3。使用命题2.2(ix),我们有(a2<$(aa))<$(a 2 <$(a a))=(a 2<$(a 2 <$(aa))<$((a a)<$(a 2<$(a a)=a4<$(a 2<$(a a))<$((a a))<$(a a)2=a 4<$(a2<$(a a))<$(aa)2。根据命题2.2(x),我们有一个aa= 0,并且正如上面第(ii)项的证明所观察到的,(aa)2≤aa= 0。因此,a4(a2(aa))(a a)2=a4(a2(a a))。根据命题2.2(iii)a4≤a3,根据命题2.2(iv)a2a)≤a3因此,根据需要,a4a))=a2≤a3(iv). 设a≤b,且对A的任意同余θ,(a,1)∈θ. 然后(a<$b,1<$b)=(b,1)∈θ。这表明θA(b,1)<$ΘA(a,1)。类似地,(b,0)∈θ意味着(a<$b,a<$0)=(a,0)∈θ,这意味着ΘA(a,0)<$ΘA(b,0)。相反,假设ΘA(b,1)<$ΘA(a,1)和ΘA(a,0)<$ΘA(b,0)。如前所述,第一个假设包含[b]<$[a],即b∈[a]。 通过[19,引理2.5],我们有ΘA(a,1)= ΘA(a,0)和ΘA(b,1)= ΘA(b,0)。因此,第二个假设意味着[a]<$[b],即a∈[在项目中证明了3-效价(iii)上面,我们有[a)={c∈A:a2≤c}和[bb]={c∈A:(b)2≤c}。 因此,a2≤b且(b)2≤ba。在这一点上,我们将(Nelson因此,再根据命题2.2(i),我们有a≤b。(v). 考虑到一个矛盾,设A的格约简是非分配的.然后,根据格理论中的一个著名结果,A包含作为子格的在任何一种情况下,都存在三个不同的元素a,b,c∈A,使得a<$c=b<$c和a<$c=b<$c。我们将证明θ(a,1)= Θ(b,1)和Θ(a,0)= Θ(b,0),因此,通过上面的第(iv)项,我们将得出a=b与我们的假设相反的结论。设θ是A上的任意同余。设(a,1)∈θ。则(a<$c,1<$c)=(b<$c,c)∈θ和(a<$c,1<$c)=(b<$c,1)∈θ。 由前者(和传递律)我们有(b<$(b<$c),b<$c)=(b,b<$c)∈θ,因此由后者和θ的传递性我们有(b,1)∈θ。对称推理表明,(b,1)∈θ意味着(a,1)∈θ,因此ΘA(a,1)= ΘA(b,1)。 接下来,假设(a,0)∈θ。 然后 (a<$c,0<$c)=(b<$c,0)∈θ和 ( a<$c , 0<$c ) = ( b<$c , c ) ∈θ 。 如 前 所 述 , 通 过 吸 收 , 我 们 得 到(b<$(b<$c),b<$c)=(b,b<$c)∈θ,这使我们得到(b,0)∈θ,联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169175∈∈传递性对称推理表明,(b,0)θ意味着(a,0)θ,因此ΘA(a,0)= ΘA(b,0)。因此,根据上述第(iv)项,我们得出结论,a=b,与我们的假设相反。(vi). 不等式ab≤ab(ab)在任何CIBRL中都成立。事实上,通过(Res),我们有ab≤(ab)iab(ab)≤0。后一个不等式成立,因为应用命题2.2(iv),(viii)和(x),我们有ab(ab)=ba(a b)≤b(ab)≤bb= 0. 由于命题2.2(iii)给出了a b ≤ a b,我们利用的单调性得到了ab≤ab(ab).为了检验a b(ab)≤ a b,我们将使用上面的项(iv),并证明Θ A(ab,1)<$Θ A(ab(ab),1)和Θ A(a b(a b),0)<$Θ A(ab,0)。设θ是A的任意同余。设(a(ab),1)∈θ。然后,通过吸收,(a<$(a<$b <$$>(a <$$>b)),a<$1)=(a,1)∈θ,类似地(b,1)∈θ。则(a<$b,1<$1)=(a<$b,1)∈θ。现在假设(a∈b,0)∈θ。使用命题2.2(vi),我们有((ab),0))=((ab),0)∈θ。则(a(ab),a(ab),0)按要求∈θ(vii). 使用上面的第(iv)项,我们将检查θA(θA(ab),1)= ΘA(θA(ab),1)。θA(ab),0)= ΘA(aab,0)。我们还将使用以下内容:根据第2.2(vi)条,=根据第2.2(xii)条计算的=a按第2.2(xiii)条计算的平均值b=(a b),按第2.2(vi)条计算。设θ是A的任意同余。设(a<$b),1)∈θ。由于(ab)≤根据命题2.2的第(iii)项和第(Xi)项,我们有(a)(a)(b)(a)(xi)(a)(1)(xi)(a)(xi)(a)(xi)(xi)(a)(xi)(xi)(a)(xi)(xi(1)∈θ。类似地,我们得到(θb,1)∈θ,因此(θa)∼∼b,1∗ 1)=(∼∼a ∗ ∼ ∼b,1)∈θ.相反,假设(ab,1)∈θ。使用当θ(a<$b)=θ(a<$a<$$>b)时,我们立即得到(a <$b(a <$a<$$>b),1)=( a<$b ) , 1 ) ∈θ 。 现 在 假 设 ( a<$b ) , 0 ) ∈θ 。 如 前 所 述 推 理 , 我 们 有((ab),0)=((ab),0)∈θ。由于ab≤(ab)(根据命题2.2的第(viii)项),我们有((a b)(a b),0(ab))=(ab, 0)∈θ。最后,假设(aθ(0)∈θ。如前所述,我们有((ab),0)=((ab),0)∈θ按要求(viii). 根据命题2.2(iii),我们有ab≤ab,因此根据命题2.2(iv),(ab)2≤(ab) 2另一方面,根据命题2.2(iv),a<$b≤a和a<$b≤b,我们得到(a<$b)2≤a<$b,因此(a<$b)4≤(a<$b)2。现在应用3-效价(上面的第(iii)项),我们得到(a<$b)2=(a<$b)4≤(a<$b)2。(ix). 利用命题2.2(Xi)可以很容易地证明(ab)≤(aab),由此我们利用命题2.2(iv)得到(ab))2≤(a a b)2它仍然需要检查(ab)2≤((ab))2。根据上述第(viii)项,我们有(ab)2=(ab)2,根据上述第(vii)项,(ab)2=176联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169(a)(a)(b)(a)(b))根据命题2.2(iii),我们有ab≤ab,这意味着b(ab)≤通过命题2.2(Xi),可以得到(ab)2≤(ab)2把这些事实结合起来,我们有(ab)2=(ab)2=(ab))2≤(ab))2。(x). 请注意,((a b))2=(ab)2。这是因为,根据上面的第(ix)项,我们有(a b))2=(ab)2,根据命题2.2(xii),我们有(ab))2=(ab))2 。 因 此 , 检 查 ( ab ) 2= ( ( ab ) ) 2 就 足 够 了 。 让 我 们 从 ( ab ) ) 2≤((ab))2开始。观察到ab≤(ab)。这是因为,通过(Res),我们有∼∼a∗∼b≤∼(a⇒b) iff (a⇒b) ∗ ∼ ∼a∗∼b≤ 0 iff (a⇒b) ∗ ∼ ∼a≤∼ ∼b iffa⇒b≤∼∼a⇒ ∼ ∼b =a⇒ ∼ ∼b.最后一个等式由命题2.2(xiii)成立。 通过(Res),我们有ab≤abia(ab)≤b,后者成立,因为通过命题2.2(vii)和(viii),我们有a(ab)≤b≤b。在证明了ab≤(ab)之后,我们可以引用命题2.2(iv)来得到(ab)2≤((ab))2。我们已经在上面的第(viii)项中证明了(ab)2=(ab)2,因此我们得出结论(ab)2=(a b)2≤((ab))2。对于逆不等式,让我们从观察到a≤a<$b和b≤a<$b开始。后者是命题2.2(iii)的直接结果;至于前者,通过(Res)我们有a≤abi aa≤b,这是真的,因为aa= 0,通过命题2.2(x)。然后,通过单调性,我们有ab≤ab。通过命题2.2(Xi),我们得到了命题2.2(v)成立的最后一个等式:(ab)≤(ab)= a b然后我们可以再次使用命题2.2(iv)来得到(ab)2。(xi). 根 据 上 一 项 , 我 们 有 ( ( a2b ) ) 2 。 因 此 , 证 明 ( a2b ) ) 2=(a2b))2就足够了。使用项目(viii)和(iii)上面,我们有(a2b)2=(a2b)2=a4((b)2=(ab)2。因此,(a2b)2=(ab)2,并对两边应用双重否定,我们得到(a2b)2=(ab)2。现在注意到,(vii)上面,我们有x2=(x)2,因此(a2b)2=((a2b))2。类似地,我们有(ab)2=((ab))2,这就结束了我们的证明。Q让我们简要地评论一下在命题2.4中证明的最重要的性质。恒等式(ii)在[19,定理6.1]中被证明是等价的, 相容对合CIBRL的上下文中,身份(纳尔逊);我们不知道目前是否这样的等价也适用于任意CIBRL。第(iii)项,即3-幂性,是Nelson剩余格[19,推论4.3]的特征之一,并且极大地简化了这些结构的代数研究,因为它允许人们证明它们形成各种具有1-滤器保持运算的弱Brouwe半格:参见[19,引理2.4]以了解更多细节。条件(iv),我们在[19]中引入并称之为(0,1)-同余可序性,是著名的代数性质同余可序性的推广。事实上,[19,推论7.2]的主要结果之一是相容对合CIBRL是(0,1)-同余可序的当且仅当它满足恒等式(Nelson)。对于任意的CIBRL,也可以证明这种等价性,尽管我们在这里不讨论这个问题;我们请读者参考[19]以进一步了解。联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169177∗ ∧∈关于(0,1)-同余可序性的讨论最后,第(vi)项值得强调,因为它意味着有可能给出拟纳尔逊剩余格的定义,而从代数语言中省略幺半群运算,因为它可以通过项xy(xy)引入。 这概括了一个众所周知的 关于对合CIBRL的一个事实,其中可以定义xy:=(xy),它也解释了为什么我们在定义拟Nelson代数时(定义4.1)不需要引入作为下一个命题将是建立拟Nelson剩余格的等价刻画我们将写x→y作为x2y的简写(回想一下,在我们的上下文中,这也等价于x(xy))。如前所述,纳尔逊强否定逻辑N3的主要特征之一这种替代对应于以原始语言,,→,,0, 1或,0, 1表示N3和相应的代数。上面介绍的连接词→被称为弱蕴涵,与N3的无负片段上的直觉蕴涵一致;从FLew继承的剩余强蕴涵可以反过来从弱蕴涵恢复,令x<$y:=(x→y)<$(<$y→ <$x)。本文的主要结果之一是,这种内在的可定义性可以毫不费力地转移到非对合设置。命题2.5设A是拟Nelson剩余格。然后又道:(i) 约简<$A;<$,<$,0,1 <$是有界分配格(阶≤).(ii) 对于所有a,b∈A,通过a≤bi →a→b = 1定义的关系≤ on A是一个拟序(即自反且传递)。(iii)关系式<$:=≤ <$(≤)−1是约简<$A;<$,<$,→, 0,1 <$上而商代数A+=<$A;<$,<$,→,0,1 <$/<$是一个Heyting代数6。(iv) 对所有的a,b∈ A,成立(a b).(v) 对任意的a,b ∈ A,有a ≤ bi <$a ≤ b和<$b ≤ <$a.(vi) 对于所有的a,b∈A,它成立,(vi.1)(a→b)a→b(vi.2)(a)(b)(c)(d)(c(vi.3)(a、b)(vi.4)a ≤ a(vi.5)a≤a(vi.6)a≤ 0.证据(i).肯定地说,<$A;<$,<$, 0, 1<$<$是一个有界格;分配性由命题2.4(v)得出。第(二)项和第(三)项并不难直接证明,但一个6回想一下,海廷代数A可以定义为满足a的CIBRL。B= ab对于所有的a,bA。由于么半群和交运算重合,通常从代数签名中删除么半群178联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169依赖于这样一个事实,即,作为3-幂(命题2.4(iii)),拟Nelson剩余格形成各种具有1-滤器保持运算的弱Brouwerian半格[19,引理2.4]。则(ii)和(iii)分别对应于条件(WBSO2)和(WBSO3)。关于(iv),请注意,“y”的定义直接意味着xyix2 =y2。那么(iv)项就是命题2.4(Xi)。命题2.4(i)中证明了第(v)项的隐含意义。 对于二次多项式,若a≤b,则由命题2.2(Xi)得到二次多项式b≤二次多项式a 然后ab=ba= 1。 因此a→b=b→a= 1,因为在任何CIBRL中xy≤x2y 第(vi.1)项是命题2.2(xiv)的一个简单结果。命题2.2(v)蕴涵(vi.2)。第(vi.3)项正是提案2.4(ix)。命题2.2(xii)蕴涵(vi.4)。第(vi.5)项接自第((v) 与提案2.2(viii)一起。最后,关于(vi.6),注意,根据命题2.4(viii)和命题2.2(x),我们有(aa)2=(a a)2= 0。则(aa)→0 =(aa)20= 0 0 =1。 Q我们将在第4节中看到,上述条件不仅是必要的,而且足以提供Nelson剩余格类的等价表示。在形式上,我们称一个代数A=A;A,A,A,→,A, 0, 1,A为满足命题2.5的所有条件的n=2,2,2,1,0,0是一个拟Nelson代数(定义4.1)。使用这一术语,我们可以将上述命题重述如下。定理2.6对每一个拟Nelson剩余格A,有代数A;,<$,0,1 <$是一个拟Nelson代数。为了读者命题2.7根据[ 16,定义2.2]中引入的术语,任何拟Nelson剩余格A的n,n,0,1n-约化是一个下拟de Morgan代数。也就是说,对于所有a,b,c∈A,它成立:(i) 是有界分配格(阶≤),(ii)(a(iii)(a)(b)=(a)(b)(a)(b)(b)(a)(b)(a)(b)(b)(a)(b)(b)(c)(b)(b)(c)(b)(b)(c)(b)(c)(c)(b)(c)(b)(c)(c)(b)(c)(c)(b)(c)(c)(b)(c)(c)(iv) ∼∼∼a= ∼a,(v) a≤ 100%a.此外,委员会认为,(vi) aa ≤ b b。除了解释我们为Nelson代数的非对合推广所选择的名称外,命题2.7还推广了一个众所周知的事实:一个Nelson代数的一个约简是一个De Morgan代数(即一个拟De Morgan代数满足a),或者实际上是一个Kleene代数,即一个De Morgan代数满足命题[19,命题4.9]中的第(vi)联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)16917983非对合扭结构在这一节中,我们将介绍一个结构,它将使我们能够更好地了解我们的新代数类,以及证明等价之间替代介绍。我们的定义显然推广了/,其灵感来自于用于表示Nelson剩余格和相关代数的著名扭结构构造(参见例如[14])。然而,我们构造的关键部分依赖于[7,8]中引入的非对合扭结构,特别是使用两个由映射相关的Heyting代数而不是单个Heyting代数的思想。定义3.1设H+=H+,+,+,→+,0+,1+,H−=H−,−,−,→−,0−,1−b∈Heyting代数和n:H+→H−和p:H−→H+b∈映射满足下列性质:(i) ,故有“”之义,“”之义,“”之义。 一个有n(x+y)=n(x)−n(y),n(x+y)=n(x)−n(y),n(1+)=1−andn(0+)=0−),(ii) p保持满足,蕴涵和界限(即, 有p(x−y)=p(x)=p(x)→+p(y),p(x→−y)=p(x)→+p(y),p(1−)=1+且p(0−)=0+),(iii) n·p=IdH−且IdH+≤+p·n。代数H+da H−=<$H+× H−,<$,<$,→,<$,0,1 <$定义如下。为所有<$a+,a−<$,<$b+,b−<$∈H+×H−,1=1+,0−0= 0+, 1−0∼⟨a+,a−⟩=⟨p(a−),n(a+)⟩a+,a−a+,a−a+,a−H + da H −上的扭结构A是H+da H −的{<$,<$,→,<$,0,1}-子代数,其载体集A满足π1(A)=H+和a+<$+p(a−)=0+,其中a∈a+,a−<$∈A。使用我们的术语,人们很容易看到,对应于Nelson代数的标准扭结构(例如见[14])正是其中映射n和p是相互逆的Heyting代数同构的那些。[7]知情的读者可能记得,例如[2]中使用的预双格积构造也采用两个不同的代数;然而,没有否定运算符被定义在结果结构上。值得注意的是,[6]中引入的半德摩根代数的表示-这对我们也是一个启发-虽然不涉及类似乘积的结构,但也是基于这样的想法将半德摩根代数表示为由两个由映射相关的代数组成的四元组,满足与我们非常相似的要求[8]我们注意到,这些条件意味着对于所有的a+,a−∈A和π2[A] =H −,n(a +)<$− a − =0−。 首先,由于a+n+p(a−) =0+,我们可以将n应用于方程的两边,并且利用其性质,我们可以根据需要获得n(a+n+p(a−))=n(a+)n−n(p(a−))=n(a+)n−a−=0−=n(0+)。 从π1[A]= H + 开 始 , π 2 [ A ]=H−。事实上,对于所有的a−∈H−,我们知道a−=n(p(a−)),其中p(a−)∈H+。 nπ1[A]=H+证明存在b−∈H −,suc h证明了n πp(a−),b−n π ∈A,which表示nπp(a−),b−nπ=n πp(b−),n(p(a−)π=n πp(b−),a−nπ ∈A. Tu s a−∈π2[A]ar e uir e d.180联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169因为我们想赋予一个扭曲结构A一个准纳尔逊剩余格结构,我们需要在A上定义一对满足定义2.1中的(Res)的运算。我们让:xy:=(x→y)(y→ x)x y:= x y(xy)。请注意,“x”的定义与标准扭转结构的定义相同,而“x”的定义旨在考虑恒等式xy=x(x)的失效在一个非文本的文本中。 考虑<$a+,a−<$,<$b+,b−<$∈A。通过计算,我们立即得到:<$a+,a−<$$>b+,b−<$=<$(a+→+b+)<$+(p(b−)→+p(a−)),n(a+)<$−b−)<$。更复杂的是,检查是否将递归操作简化为以下表达式:a+,a−是的。直接计算告诉我们,a+,a−a−b+,b−b等于以下表达式:a+关于第一个组件,请注意,a+n+b+n+p(n(a+)n−n(b+))=a+n+b+因为使用Id H+ ≤+p·n和n保持n −的事实,我们得到a+n+b+≤+pn(a+n+b+)=p(n(a+)n−n(b+))。关于第二个复合物nt,首先观察到n(a+→+p(b−))=n(a+)→−b−和n((pn(b+)→+p(a−)=n(b+)→−a−。 后者可以很容易地证明,利用p与n·p = IdH−一起保持蕴涵,对于n((pn(b+)→+p(a−)=np(n(b+)→−a−)=n(b+)→−a−。 对于前者,不等式yn(a+→+p(b−))≤−n(a+)→−b−可以很容易地使用留数和n个前变量满足的事实:weh aven(a+→+p(b−))≤−n(a+)→−b−ib−≥−n ( a+ ) −n ( a+→+p ( b− ) ) =n ( a++ ( a+→+p ( b − ) ) = n(a++p(b−))=n(a+)−np(b−)=n(a+)−b−,再次回顾n·p=Id H−。 对于不等式yn( a+ )→−b−≤−n(a+→+p( b− )),我们从pn(a+ )→+p( b− )≤+a+→+p(b−)出发,由于Id ≤p·n,且p是蕴涵,我们有pn(a+)→+p(b−)=p(n(a+)→−b−)≤+a+→+p(b−).我们现在将n应用到b的两边(使用n的单调性y),以得到np(n(a+)→−b−) =n(a+)→−b−≤+n(a+→+p(b−)),其中第一个等式y成立,因为n·p=Id。把这些事实放在一起,a−n−b−n−(n(a+→+p(b−))n−n((pn(b+)→+p(a−)等于a−−b−−((n(a+)→−b−)−(n(b+)→−a−))。联合Rivieccio,M.Spinks/Electronic Notes in Theoretical Computer Science 344(2019)169181我们试图证明a−n−b −≤−(n(a+)→−b−)n−(n(b+)→−a−). Ob(byi ntegrali ty)weh aveb−≤−n(a+)→−b−,更可能是a−≤−n(a+)→−b−,因为后者是等价的,通过留数和a−−n(a+) =0−的要求,too0−=a−−n(a+)≤−b−。因 此 , a−n−b−≤−n ( a+ ) →−b−。 类 似 地 , 我 们 也 有 a−n−b−≤−n ( b+ )→−a−b , 因为一 方 面 a−≤−n ( b+ ) →−a−by是整数, 另 一方面 b−≤−n ( b+ )→−a−by是剩余,并且要求b −n−n(b+)=0−。THUSa−−b−−((n(a+)→−b−)−(n(b+)→−a−))等于(n(a+)→−b−)<$−(n(b+)→−a−)as必需的。Q我们继续检查,任何扭曲结构A可以被赋予一个准纳尔逊剩余晶格结构。命题3.2设A =<$A;<$,<$,→,<$,0,1 <$是H+,H−上的扭结构。然后又道:(i) A,(ii) A满足Nelson恒等式(x <$(x <$y))<$(<$y <$(<$y<$$> x))<$x<$y。(iii) 是一个下拟德摩根代数,并且满足Kleene恒等式x≤y。是的。(i). 你的交流是即时的。 设a+,a−,b+,b−∈H+×H−. 让我们证明,1+,0−是中性元素。Wehave1+,0−a+,a−=a+,a− 为 a+ →−0−)−(n(1+) →−a−) 为a+,(n(a+)→−0−)最后一段是由a−≤−n(a+)→−0−保持(by剩余)i ∈a−n−(a+)≤−0−这一事实证明的,其中h是t
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功