余代数与模态逻辑，本文主要内容关键词为：代数论文,逻辑论文,模态论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号：B815 文献标识码：A 文章编号：1673-9841(2011)04-0087-07
近年来，余代数(Co-algebra)成为国际逻辑学界研究的热点之一。“余代数”这个术语与“代数”相对应。一个代数结构是由给定的集合和该集合上的一些运算组成的，我们最熟悉的代数结构是自然数上的加法、乘法等运算。除此以外，还有数学中的各种抽象代数结构，比如群、环、域等等。而更一般的代数结构是抽象代数中的格、序、(加算子的)布尔代数。代数结构的特点是在某个集合上进行某种代数运算的结果仍然在该集合中，即该集合在这种代数运算下是封闭的。余代数则不同，它以范畴论为基础，在一个范畴中，对象和箭头的转换(运算)所得到的结果往往超出原来的对象本身。
从广义上说，余代数处理基于状态的动态系统，比如理论计算机科学、数学和逻辑中的各种结构都可以表示为余代数。余代数是基于状态的动态系统的抽象模型。最早研究余代数的逻辑学家是阿克采尔(P.Aczel，1988)，他把加标转换系统和非良基集合(Non-well founded set)表示为余代数结构。在阿克采尔的理论基础上，莫斯和巴维斯(Barwise & Moss，1996)详细讨论了与非良基集合有关的循环现象，特别是莫斯(Moss，1999)还专门提出了“余代数逻辑”，为逻辑研究开创了新的方向。
一、什么是动态系统？
一个动态系统是由内部结构和外部环境组成的。内部结构是系统本身的运行机制；外部环境则在系统运行时与之相互交流。系统有自身的特点：首先，系统与计算算法不同，正确的算法要求在输入信息之后必须在有穷步骤之内停止而输出结果；系统则是持续运行的，它假定不断运行下去而没有终结。比如：社会经济体系就是一个系统，生产、分配、交换、消费等现象在良好的经济系统中都被假定是连续不断地运行着的。此外，一台计算机也可被看做一个系统，计算机与人之间的互动过程就是一个系统与外部环境交流的过程。
其次，一个系统与环境之间的交流渠道称为“接口”。系统外部环境中的观察者，只有通过“接口”才能观察到系统的行为。比如人与计算机之间的交流，通过输入一些信息，使用者观察到一些系统输出的信息，从而继续进行交流。再比如，图书馆的借书系统也是如此，读者通过系统的借阅规则借出图书和归还图书，通过借还书的接口，读者观察到整个系统的行为。
接着，一个系统的外部观察者对系统的看法属于一种外部的观点，它看不到系统内部的结构，这种外部观点是由可以观察到的系统行为形成的。对于任何系统来说，外部观察者所关心的东西不是系统本身的结构，而是系统的行为。这就好比计算机软件的设计者和使用者之间的关系，使用者并不关心一个软件是如何制作的，而只关心使用软件能够达到的效果是怎样的。如果两个系统的行为一致，外部观察者是无法区分的。比如两台计算机的“芯片”不同，但它们都能很好地运行。对于计算机的外部使用者来说，这两台计算机的系统的区别在使用过程中是无法被观察到的。
从理论上说，要描述一个动态系统，首先要给出一个状态集合和在状态之间进行转换的运算，转换运算用于描述在每个状态上进行转换之后得到的结果。在现实生活中，比如一个申报程序是由一系列“阶段”组成的，从提交申请开始，每经过一个阶段就达到一个新的状态，这就是一个系统。事实上，存在各种不同类型的系统，我们举三个例子。
首先考虑这样一个系统，在某一个状态上进行一次转换，即输入某个集合中的一个元素。这样的系统在一次使用过程中仅仅发生一次转换。在生活中这类典型的系统是自动售货机和银行的自动取款机。第二类系统是只有转换没有输出的系统。比如闹钟就是这样的系统，指针只是不断往前走，每一次转换不产生任何结果。第三类系统是经过一次转换达到一个新的状态，并且同时输出一个结果。比如使用计算机编写一个文档时，每当输入一些信息(二进制代码)就输出一些信息，而且计算机本身的读写头达到一个新的状态。
我们知道，一个系统的行为对于外部环境来说是最重要的信息，那么如何从理论上描述一个系统的行为呢？从任何给定的状态
出发，系统进行的每一个转换都达到一个新的状态
并且同时输出一个结果
，由此不断转换下去从而得到一个无穷长的由状态和输出结果组成的链。我们把一个系统从状态出发产生的输出结果(，
，…)称为一个系统在状态上的行为。如果两个系统在任何状态上输出的结果相同，那么称这两个系统是行为等价的。比如两个软件在两台计算机上同时运行，对任何输入来说，输出的结果都相同，那么这两个系统就称为行为等价的。
在一些关于系统的基本理论中，除了研究个别系统的性质，还要研究不同系统之间的关系，或者一族系统的结构性质，这就好比单台计算机与计算机联网的区别。要研究不同系统之间的关系，最基本的概念是系统之间的同态。首先要明确，在一个系统中，给定一个状态就会得到一个输出结果(，,…)，其中称为该输出结果的起始信息，其他部分称为它的剩余信息。任给两个系统A和B，它们之间的一个同态就是从A的状态集到B的状态集之间的一个映射f，使得A中任何状态的输出结果的起始信息，在映射f下得到B中状态f(x)的输出结果的起始信息，而剩余信息经过映射得到的结果是f(x)的剩余信息。因此，任给两个系统A和B，如果它们之间存在一个同态，那么它们的行为就是等价的。
在理论计算机科学中，我们经常用的另一个概念是互模拟。两个系统之间的互模拟关系是这样一种关系R，如果两个状态x和y之间存在关系R，那么它们的起始信息和剩余信息都是相同的。由此可见，两个系统是互模拟的当且仅当它们是行为等价的。
二、余代数的基本概念
在上面，我们给出了一些动态系统的例子，并对动态系统的理论进行了刻画，下面介绍余代数的基本概念，明确余代数如何成为动态系统的抽象模型。动态系统的基本结构是：首先给定一集对象A(状态集合)，然后给出这些状态上的转换运算，这样就可以明确一个状态经过转换之后达到什么样的新状态。在这个关于动态系统的说明中，我们还假定了一点，即系统的种类，它是由转换的种类决定的。简单地说，这些关于动态系统的一般特征的理论称为余代数理论。
余代数理论以范畴论为基础，关于范畴论的一些基本概念，有学者进行了比较系统的研究。[1-3]一个范畴是由一些对象和这些对象之间的箭头组成的，同时必须满足以下条件：(1)对任何从对象A到B的箭头，对象A称为该箭头的域，对象B称为它的反域；(2)令f是从A到B的箭头，g是从B到C的箭头，那么存在一个从A到C的箭头，称为f和g的复合箭头。一个范畴的箭头必须在复合下封闭；(3)箭头的复合运算要满足结合律，即g与f和h的复合的复合箭头，等于g和f的复合与h的复合箭头；(4)对每个从对象A到B的箭头f，存在两个恒等箭头
和
使得f与的复合箭头等于f自身，并且与f的复合箭头也等于f自身。例如，由全部集合所组成的类SET可被看做一个范畴：它的对象是集合，而对象之间的箭头就是函数。对每个从A到B的函数f，A是该箭头的域，B是该箭头的反域。函数还满足结合律和幂等律。但是，范畴中的对象是任意的，对象之间的箭头也可以是任意的。
在任何一个范畴中，我们可以建立动态系统的抽象模型。任取从一个范畴到它自身的同态映射，这个映射称为一个函子T，它决定把每个对象映射到哪些对象，把每个箭头映射到哪些箭头。因此，对范畴中的任何对象A，经过T映射到某个对象TA，每个箭头f经过T映射到某个箭头Tf。然后，任给一个对象A，一个T-余代数就是从A到TA的一个转换映射。如果我们取所有集合和集合之间的函数组成的范畴，则可看出我们在第一部分中所举的系统的例子都是余代数的具体实例。一个动态系统是由一个状态集合、转换函数和转换之后的状态集合组成的。
在第一部分，我们谈到了动态系统的一般理论，同样在余代数这种抽象的结构中，我们也可以研究单个余代数的性质、余代数之间的关系以及一族余代数的结构。对于单个余代数的研究，主要集中于研究新的余代数种类。给定一个范畴和该范畴的两个函子
和
，我们可以考虑从T构造新的函子，比如“+”这个函子把任何一个对象A映射到新的对象，这个新对象是从两个函子映射的结果构造出来的，称为它们的“余积”(相当于“不相交并”)。
关于余代数之间的关系的研究，同样可以像动态系统之间的同态一样，定义余代数同态。任给两个余代数X和Y之间的映射f，从X中任何状态x出发，如果x在X中经过转换后再通过f映射的结果，等于首先x经过f映射再进行转换的结果，那么f就称为一个余代数同态。这个概念把一个系统的转换结果与另一个系统的转换结果等同起来，这与动态系统的同态是一样的。同样，有了余代数同态，也可以定义“行为等价”的概念。任给两个余代数X和Y以及其中的两个状态x和y，称这两个状态在余代数中是行为等价的，则需要找到一个中间的余代数Z，以及分别从X和Y到Z的同态f和g使得f(x)和g(y)是同一个状态。这个概念类似于平面几何中的一条定理：如果两条直线分别与第三条直线平行，那么这两条直线平行。
从理论上看，余代数结构的“抽象程度”体现在两个方面：第一，它不限于集合上的动态系统；第二，它不限于在一个集合内部的转换。第一个方面是由于在任何范畴上都可以定义余代数结构，比如在由群和群同态组成的范畴上，就可以定义余代数结构。第二个方面反映了动态系统的本质，动态系统并不局限于集合内部，进行转换的结果可以到达原来的对象之外。由于这两个特点，余代数理论广泛应用于数学、理论计算机科学和逻辑之中。下面我们具体地看一看非良基集合的模型以及余代数理论在模态逻辑中的作用。
三、非良基集合的模型
在数学和理论计算机科学中，许多结构都可以看作余代数，使用余代数作为它们的抽象模型。这一点最初是由阿克采尔在他的著作《非良基集合》[4]中发现的，他把非良基集合论的每个满模型都看作一个系统，也就是余代数。在巴维斯和莫斯的著作《恶性循环》[5]中，讨论了大量关于循环和自指称的现象，使用非良基集合可以为循环现象构建模型，而且可用它来处理模态逻辑。在这一部分，我们介绍非良基集合论与余代数的联系：余代数可被用作非良基集合的一般模型。
非良基集合的引入有两种方式：一是阿克采尔所采用的方法，通过图与集合之间的联系引入非良基集合。在一个非良基图中由所有结点的装饰组成的集合就是非良基集合；二是巴维斯和莫斯从方程组的解引入非良基集合。比如方程x=｛x｝的解唯一，即属于自身的非良基集合。[6]我们采用前一种方式。在经典集合论ZFC中，著名的莫斯托夫斯基坍塌定理说明：每个良基图都有唯一的装饰。所谓良基图是指没有无穷下降的关系链的图。对于非良基图，比如一个单点自返图(｛x｝，(x，x))，它的结点x的装饰d(x)属于自身，因此它是非良基集合。对于加标图也是如此，一个加标图(G，R，l)是由图(G，R)和加标函数l：G→A组成的，其中A是标签集合。加标图中结点的装饰是该结点在图中的装饰与它的标签的并集。由于A中的元素可能不是集合，所以在非良基集合中引入本元作为构成集合的元素，但是本元自身不是集合也不是类。
非良基集合可用于模拟循环现象，它反映了循环现象的本质。关于非良基集合的逻辑研究，需要构造一种逻辑语言来表达非良基集合的性质，并且对这些性质进行推理。巴塔格、巴维斯和莫斯等人采用(无穷)模态语言来谈论非良基集合，他们的基本思想是在集合上解释模态语言。[5][7]无穷模态语言是由命题变元集Φ和一元模态词◇、否定词
、任意合取∧和析取∨组成，它的公式由如下规则形成：任意命题变元p是公式；如果φ是公式，那么φ和◇φ是公式；如果T是公式集，那么∧T和∨T是公式。任给(可含命题变元的)集合a，任给无穷模态公式φ，可以递归定义φ在a上真如下：p在集合a上真当且仅当p属于a；φ在集合a上真当且仅当φ在a上假；∧T在a上真当且仅当T中的每个公式φ在a上真；∨T在a上真当且仅当T中存在某个公式φ在a上真；◇φ在a上真当且仅当存在集合b属于a使得φ在b上真。
非良基集合域(使用命题变元作为本元形成的非良基集合论的论域[6]上的一个互模拟关系是一个二元关系R，使得如果a和b有关系R，那么，(1)a与b含有相同的命题变元；(2)如果集合c属于a，那么存在集合d属于b使得c与d有关系R；(3)如果集合d属于b，那么存在集合c属于a使得c与d有关系R。
四、余代数模态逻辑
从目前模态逻辑的研究看，模态逻辑在计算机科学及相关领域有着广泛的应用，比如描述逻辑(知识表示的逻辑)、混合逻辑以及其他各种不同的形式系统，包括概率分布系统、移动网络、新语义网络等等。除此之外，模态逻辑还在多主体系统、博弈、经济主体的概率信息等领域中有许多应用，比如道义逻辑，即在关于权利和义务的哲学研究中发展起来的逻辑，它用于研究多个主体之间的契约问题。以博弈为例，一种简单的逆向归纳程序经常用于判定理性的主体在特定情形中进行博弈的结果。在博弈过程中主体的策略选择涉及它关于对手信息的认知，还涉及一些概率猜测、时间、信念、偏好等等问题，而模态逻辑为这些问题的研究提供了很好的研究工具。然而，经过多年的研究发现，在这些模态模型和语义背后有一种共同的因素，即可以把模型看作动态系统，从理论上说，这些动态系统就是我们前面讲过的余代数。下面我们给出一些例子说明为什么各种模态语言的模型都可以看作余代数。
经典模态逻辑的语义是关系语义学，也称为克里普克语义学[9]。一个关系框架是一个有序对(W，R)，其中W是非空集合，R是W上的二元关系。对于任何状态w来说，如果w和u有R关系(Rwu)，那么称u是w的可及状态。对于二元关系的不同解释使得关系框架可以应用于各个领域。比如在认知逻辑中，关系R被解释为主体不能区分两个不同的认知状态；再比如在纸牌游戏中，关系R被解释为一个主体不知道其他主体是否有某一张纸牌。在时态逻辑中，二元关系被解释为时间的次序，比如过去、现在和将来，而状态就是时间单位，比如时刻或者时间区间。在知识表示中，状态是各个不同的对象，而二元关系则是这些对象之间的关系，比如我们关于一个人的知识包括这个人与其他一些人和物之间的关系。在一个关系框架中，一个状态w满足一个形如“[]α”的公式(α这个命题是必然的)当且仅当F这个命题在w的任何可及状态上都是真的。
显然每个关系框架可以转换为一个余代数结构：任给框架F=(W，R)，可以定义从W到幂集P(W)的映射
，使得y属于R[x]当且仅当Rxy，即对每个状态x指派一个后继状态集合。这就是一个余代数，它以集合范畴上的幂集映射为函子，是集合W和幂集P(W)之间的转换映射。每个关系模型也可以看作一个余代数：它以W为状态集合，转换映射是从W到幂集P(W)与命题状态集合的幂集的笛卡尔乘积的函数，也就是说，对每个状态w指派W的子集作为可及状态，还指派命题变元的集合作为在w上真的命题变元。
从余代数的角度看模态逻辑的框架和模型：第一，框架(模型)上的运算或构造在余代数中都有相应的运算或构造；第二，等式逻辑是代数的逻辑，模态逻辑则成为余代数的逻辑，与代数的变种一样，也可以得到余代数的余变种。这些结果表明，余代数与模态逻辑的联系十分密切，而且也适合作为研究模态逻辑的工具。
对于幂集函子的余代数来说，余代数同态的概念相当于框架之间有界态射的概念[9]。考虑两个余代数F=(W，)和G=(U，S[.])，一个从W到U的同态要满足如下两个条件：对W中的每个状态x，(1)(S[.])(f)(x)是(Pf)()(x)的子集；(2)(Pf)()(x)是(S[.])(f)(x)的子集。条件(1)表示：对G中f(x)的每个S-后继状态z，存在F中x的R-后继状态使得f(x)等于z，这就是有界态射定义中的后退条件。条件(2)表示：对F中x的每个R-后继状态y，f(y)都是f(x)在G中的S-后继状态，这就是有界态射定义中的前进条件。
模态逻辑中有许多有用的模型构造，比如不相交并、生成子结构、有界态射、互模拟等等，都可以在余代数中定义相应的一般性概念[10]：不相交并相当于余代数的和，生成子结构相当于子代数，有界态射就是前面讲到的余代数同态，互模拟也就是前面讲过的行为等价的概念。对于模态逻辑的理论研究来说，可以定义一个重要概念：余代数变种。这个概念与代数中的变种概念相对应。一个代数变种是一个在取代数同态象、子代数和代数乘积下封闭的代数类。给定一个代数类K，包含K的最小代数类称为由K生成的变种。在泛代数中有这样一个结果：由K生成的代数变种等于对K依次取乘积、子代数、同态象得到的代数类。对于余代数来说有同样的结果。一个Ω-余代数类T称为一个余代数变种，如果它在取余代数同态象、余代数和、以及子余代数下封闭。令Covar(T)表示包含Ω-余代数类T的最小余代数变种。那么可以证明任何Covar(T)等于对T依次取余代数和、子余代数和余代数同态象而得到的余代数类。在泛代数中，一个重要的可定义性定理就是Birkhoff定理：一个代数类是等式可定义的当且仅当它是代数变种。对于余代数来说，如何定义余等式逻辑从而刻画余代数变种，这还是一个没有完全解决的问题[10-11]。此外，关于余代数模态逻辑的证明系统、模型论等等尚存在大量问题需要研究。
第二个例子是概率转换系统[12]。最简单的加标转换系统就是一个关系框架，而最简单的概率转换系统如下：任给一个关系框架(W，R)，对于该框架中的任何状态w和它的任何可及状态u，指派实数区间[0，1]中的某个概率p，使得对w的所有可及状态指派的概率之和小于等于1。由此对每个概率p引入一个模态算子[p]，因此一个公式[p]F在某个状态w上真当且仅当指派给w的可及状态的概率之和至少是p。这样的概率转换系统也可以表示为余代数，所需要的转换映射就是从状态集合到W上离散概率分布的集合。
第三个例子是条件句逻辑[12]。关于条件句逻辑的研究是哲学逻辑的一个重要分支[13]。它研究“条件”：一个命题F在另一个命题G成立的条件下是真的(表示为：G
F)。这个语言在所谓的“条件框架”下进行解释，即一个有序对(W，f)，其中W是可能世界集合，f是从一个可能世界和一个可能世界集合到另一个状态集合的映射，也就是说，对任何可能世界w和可能世界集合A，指派一个可能世界集合B，其中A相当于条件，B相当于在该条件下成立的命题。这样的条件框架很容易转换为余代数结构，只需把转换映射定义为从可能世界集合W到幂集P(W)上所有映射的集合的函数，即对每个可能世界w，转换后的结果是一个函数，对W的每个子集A，指派另一个子集B。
对模态逻辑的余代数研究是近年来兴起的方法。余代数是基于状态的动态系统的抽象数学模型，由于模态逻辑的广泛应用，余代数也有广泛的应用领域。余代数理论为研究动态系统上的不变性提供了一种新工具，它对于处理比如(加标)转换系统的计算等价性质起到了十分重要的作用。关于模态逻辑研究，上面模态逻辑与余代数的论述表明，余代数理论是研究模态模型论的一般方法，模态逻辑的框架和模型的构造在余代数中均有定义，这为研究模态逻辑提供了更有力的工具。
最后要强调的是，余代数理论是一种处理以状态为基础的动态系统的一般性工具。因此，原则上，任何这样的系统都可以使用余代数作为抽象的数学模型，从余代数理论能够直接得出这些系统的一些性质，比如由互模拟得到行为等价。余代数理论尚有待于进一步发展，模态逻辑与余代数的联系还未得到彻底研究。如果模态逻辑是描述余代数的性质和使用余代数推理的逻辑，那么怎样的模态逻辑适用全体余代数的类，这一点还不清楚。
标签：代数论文; 代数基本定理论文; 关系代数论文; 关系模型论文; 逻辑运算论文; 命题逻辑论文; 逻辑结构论文; 集合运算论文; 逻辑模型论文; 逻辑框架论文; 关系逻辑论文; 动态模型论文; 数学论文;