模态逻辑的诸后承关系之比较.doc

此文发表在电子期刊逻辑与认知，2004年第1期。模态逻辑的诸后承关系之比较李小五中山大学逻辑与认知研究所，中山大学哲学系，广州，510275摘要：本文定义模态语言的两种语义（邻域语义和关系语义）的若干个语义后承和4个具有代表性的模态系统的语法后承，然后比较它们之间的关系。关键词：语义后承；语法后承；后承关系之比较中图分类号：B81 文献标识码： A令L是模态句子语言，At是L的全体原子公式的集合，FL是L的全体公式的集合。我们总用p，q和r表示At的前3个句符，用A和B表示任意公式，用和表示任意公式集。1 语义后承之间的比较我们先来考虑语义后承关系。任给集合X，我们用P(X)表示X的幂集。本文我们总用*表示R或N，其中R和N分别指称关系语义和邻域语义。1.1定义(1) 称FW，*是*-框架，记作F*F， 下列条件满足： W是非空集，其中的元素称为可能世界，且 若*是R，则R是W上的二元关系。 若*是N，则N是从W到P(P(W)中的映射。(2) 称MW，*， 是*-模型，记作M*M，下列条件满足： W，*是*-框架，且 是从At到P(W)中的映射。(3) 复合公式在M中的真值集定义如下： AWA， ABAB， 若*是R，则AwW：R(w)A，其中R(x)表示yW：xRy。 若*是N，则AwW：AN(w)。(4) 设MW，*， ，FW，*。我们称M是F的模型，F是M的框架。表示定义、定理(的证明)等的结束符。若*是R，则称*-框架(模型)为关系框架(模型)；若*是N，则称*-框架(模型)为邻域框架(模型)。1.2 约定 (1) wM表示w属于M的可能世界集。(2) 令MW，*， ， wA表示：wA。 w或w表示：对每一A，wA。1.3 定义 任给MW，*， 。(1) 称A在M中有效，记作MA，AW。(2) 称在M中有效，记作M， 对每一A，MA。(3) 称逐*-点衍推A，记作*A， 对每一M*M和wM (w wA)。(4) 称逐*-模型衍推A，记作*M A， 对每一M*M (M MA)。(3)和(4)中定义的关系和下面我们要定义的同类关系都称为后承关系，它们都是定义在P(FL)FL上的二元关系。以后我们也集合论地看待后承关系，即考虑它们之间的（真）包含关系和等于关系（互为包含关系）。1.4 定义(1) 称A在*-框架F中有效，记作FA， 对F的任意模型M，MA。(2) 称在*-框架F中有效，记作F， 对每一A，FA。(3) 称逐*-框架衍推A，记作*F A， 对每一框架F*F (F FA)。1.5 定义 令C是*-模型的类或*-框架的类。(1) 称A在C中有效，记作CA， 对所有XCF，XA。(2) 称在C中有效，记作C， 对所有A，CA。(3) 称相对C衍推A，记作CA， (C CA)。1.6 定义 (1) 称逐*-模型类衍推A ，记作* CM A， (对所有*-模型的类C，C CA)。(2) 称逐*-框架类衍推A ，记作*CF A， (对所有*-框架的类C，C CA)。说明：在1.3(3)，我们定义了逐点衍推，在1.3(4)和1.4(3)，我们定义了逐个衍推，在1.5(3)，我们定义了全类衍推。这里我们又定义了逐类衍推。以后我们将研究它们之间的关系。上面我们已经定义了多个语义后承关系。类似地，我们还可以定义其他语义后承关系。例如，称相对*-模型的类CM逐点衍推A，记作CM，P A， 对每一MCM和wM (w wA)。称相对CM逐模型衍推A，记作CM，M A， 对每一MCM (M MA)。称相对*-框架的类CF逐模型衍推A，记作CF，M A， 对每一FCF和F的模型M (M MA)。称相对CF逐框架衍推A，记作CF，F A， 对每一FCF (F FA)。称相对CF逐点衍推A，记作CF，P A， 对每一FCF和F的模型M和wM (w wA)。易见这些衍推关系是前面的衍推关系的概括。易证：1.7 推论 其中每一命题中的*指称同一个符号。(1) * *M，P *F，P。(2) *M *M，M *F，M。(3) *F *F，F。(4) *M *F。下面我们着重考虑具有代表性的3个后承关系：*，*M，*F。1.8定义(1) 称是一个代入映射 是从At到FL中的映射。(2) 任给公式A，定义A的代入特例A如下： p(p)， 对所有pAt， (A) (A)， (AB)(A)(B)， (A)(A)。1.9 定理 (1) R RM。 (2) RM RM。(3) RF RF。(4) RM RF。(5) RCM RM。(6) RCF RF。证明：(1) “”显然。下证：“”。为此只须证： p RM p。 p R p。证：为此我们证明一个更强的命题： A RM A，对每一公式A。任给关系模型MW，R， 和A使得MA，则AW。任给wW，易见R(w)A，所以wA。据w的任意性，MA。证：考虑关系模型Ww，u，Rw，u，pw。易见wp但w p（因为R(w) u 不是p的子集），所以成立。(2) “”显然。下证：“”。为此只须证： p RM q。 p R M q。因为p不在所有的关系模型中有效，所以空洞地成立。另一方面，容易构造一个模型使得p在其中有效且q不有效，所以不成立。(3) “”显然。下证：“”。为此只须证： p RF p。 p R F p。因为p不在所有的框架中有效，所以空洞地成立。另一方面，构造死点关系框架Fw，。则Fp但F p，所以不成立。(4) 先证“”：设RM A。则() M MA， 对每一MRM。任给框架FRF使得F。要证FA。任给F的任意模型M，只须证MA。因为F，所以对每一B，FB，所以MB。据B的任意性，M，所以据()，MA。下证：“”。据Hughes和Cresswell的1996(p.40)， ARF A， 对每一公式A和代入映射。下证：存在公式A和代入映射使得 A RM A。构造M如下：Ww，u， Rw，u， pw，u， qw。则wpp，upp，uqq。所以Mpp而Mqq。(5) “”：设RCM A。则逐任意模型类衍推A，当然逐单元模型类衍推A，所以RM A。具体说，任给MRM使得M。则M。据设定，MA，所以MA。所以RM A。“”：设RM A。任给关系模型类C使得C。则对每一MC，M。据设定，MA。据M的任意性，我们有CA。所以RCM A。(6) 证明类似(5)。1.10 定理 (1) N NM。 (2) NM NM。(3) NF NF。 (4) NM NF。(5) NCM NM。(6) NCF NF。证明：(1)(4)中的“”如上易证。下证(1)(4)中的“”。(1) 只须证： pq NM pq。 pq N pq。证：据Chellas的1980(p.209)，我们有一个更强的命题： AB NM AB，对每一公式A。下证：定义邻域模型Mw，u，N， 使得：pw， qw，u， N(w)w。pN(w)且qN(w)，wpq。另一方面，我们有wpq。(2)(3)的“”的证明类似上一定理的(2)(3)的“”的证明。注意，那里的死点关系框架也是死点邻域框架。(4) 先证： ANF A， 对每一公式A和代入映射。假设不成立，则存在邻域框架FW，N，公式A和代入特例A使得 FA， FA。据，存在邻域模型MW，N， 和wW使得 wA。我们用M构造新模型W，N， 1使得 1恰如 ，除了 (pi)pi1， 对A中所有句符pi。下证： AA1。施归纳于A的结构。若A是某个pi，则据易得要证结果。若A形如B或BC，则据归纳假设易得要证结果。设AB。任给uW，据归纳假设，易证：BN(w) B1N(w),即：u(B) uB1。据u的任意性，我们证明了。据和，wA1，所以W，N， 1A，所以FA，矛盾于，所以成立。最后证：存在公式A和代入特例A使得 A NM A。构造邻域模型M如下：Ww，u， N(w)u， pw，u， qw。则wpp， upp， uqq。所以Mpp而Mqq。(5)(6)的证明类似1.9的(5)(6)的证明。1.11 定义(1) 称RM逐点蕴涵NM，记作RMwNM， 对每一MW，R， RM存在M1W，N， NM使得对每一AFL和wW（wAM wAM1）。(2) 称RM蕴涵NM，记作RMNM， 对每一MRM存在NNM使得对每一AFL（MA NA）。(3) 称RF蕴涵NF，记作RFNF， 对每一FRF存在GNF使得对每一AFL（FA GA）。1.12 引理(1) RMwNM。(2) RMNM。(3) RFNF。证明：(1) 任给MW，R， RM。定义M1W，N， NM如下： N(w)XW：R(w) X，对每一wW。任给公式A，下证： wAM wAM1，对每一wW。 其中两个下标表示它们提到的指派是哪个模型的指派。若A是原子公式p。则因为上述两个模型的指派（相对At）相同，所以 wpM wpM1，对每一wW。若A形如B或BC，则据归纳假设易得要证结果。令AB。则wBM R(w)BM 据关系模型的真值集定义BM1N(w) 据归纳假设和 wBM1 据邻域模型的真值集定义。类似(1)的证明，我们易得(2)和(3)。1.13 定理(1) NR。(2) NMRM。(3) NFRF。 (4) RF NF。(5) NF RF。证明：(1) 先证“”。设NA。任给NW，R， RM和wW使得wN。据上一引理(1)，存在MW，N， NM使得 wBM wBN，对每一公式B和wW。因为NA，所以 wM wAM，对每一MW，N， NM和wM。因为wN，所以据，wM。据，wAM，再据，wAN。这就意味wN wAN ，即RA。下证：“”。易见p q R (pq)，所以只须证： p q N(pq)。构造M如下：Ww，u， N(w)w，u， pw， qu。易见M是邻域模型，且wp q但w(pq)。(2) 证“”。设NMA。任给NRM使得N。据上一引理(2)，存在MNM使得 MB NB，对每一公式B。因为NMA，所以 M MA，对每一MNM。因为N，所以据，M。据，MA，再据，NA。下证：“”。据1.9(1)，p RM p，所以只须证： p NMp。构造邻域模型M为：Ww，N(w)，pW。易见Mp但M p。(3) 据上一引理(3)且类似上面(2)所证，易得“”。下证：“”。易见T RF T，所以只须证： T NFT。构造邻域框架F为：Ww，N(w)。易见FT，而F T。(4) 据(3)易见T RF T且T NFT。(5) 令A是K的公理K，且令B不是K的内定理。则A和B都不是E的内定理，所以A NF B且A RF B。最后我们来定义经典命题语义，以后我们要用：1.14 定义(1) 称V是经典指派 V是从AtA：AFL到0，1中的映射。(2) 称MV是经典模型 MV是从FL到0，1中的映射，使得对FL中的每一公式A，若AAtA：AFL，则MV (A)= V(A)；若AB，则MV (A)=1-MV (B)；若ABC，则MV (A)= MV (B) MV (C)。(3) 称在MV中有效，记作MV ()=1， 对每一B，MV(B)=1。(4) 称经典逐点衍推A，记作0A， 对每一经典模型MV（MV ()=1 MV (A)=1）。2 语法后承之间的比较本文我们考虑4个具有代表性的系统PC，E，K和Kb的语法后承之间的关系。2.1定义 对每一nw nw表示n是任意自然数。，定义0AA，n1AnA。2.2定义(1) 经典系统PC是由下列公理和推理规则构成的系统： pqp， (pqr)(pq)pr， (pq)(pq)p， (MP) A，ABB，(US) AA，其中是任一代入映射。(2) 模态系统E是在PC中加入下列推理规则构成的系统： (RE) ABAB。(3) 模态系统K是在PC中加入下列公理和推理规则构成的系统： (K) (pq)pq， (RN) AA。(4) 模态系统Kb是由下列公理和推理规则构成的系统： nA， 其中A是PC中的任一公理且nw， n (pq)pq)，其中nw。 (MP) A，ABB， (US) AA，其中是任一代入映射。以后我们用S来表示上述任一系统。2.3定义(1) 称S中有从到A的推演，记作SA， 存在公式序列A1，AnA使得对每一1in，下列条件之一成立： Ai是S的公理的代入特例， Ai， 存在j，ki使得Ai是从Aj和Ak据MP得到的， 若S是K或E，则存在ji使得Ai是从Aj据S中的RN或RE得到的。(2) 若，则我们把S A记作S A，并称A是S的内定理。注意：我们可以证明US可以用于S的所有内定理。2.4定义(1) 若是有穷集，则我们用和分别指称的所有元素的合取和析取。当A时，和皆记为A。(2) 若，则定义为T使得T为某个重言式，定义为使得T。2.5定义称S中有从到A的强推演，记作S A， 存在有穷子集使得SA。易见上面定义的推演和强推演实际上定义了P(FL)FL上的两种语法后承关系。2.6定理(1) S S。 (2) PC PC。(3) K K。 (4) E E。证明：(1) 设S A。据强推演定义，存在有穷子集使得SA，因为S，所以据MP，易得S A，因此据推演定义，S A。(2) 据(1)，只须证“”：设PC A，则据定义，存在有穷集使得PC A，据PC的演绎定理，PCA，PC A。(3) 据（1），只须证“”。据RN，pK p。假设pK p。则存在有穷子集p使得Kp。情况1：Kp。则K Tp，所以K pp。情况2：Kpp。则K pp。这两种情况都矛盾于K没有内定理pp(参见Hughes和Cresswell的1996)。(4) 据(1)，只须证“”。据RE，pqEpq。假设pqE pq。则存在有穷子集pq使得E pq。情况1：Epq。则E Tpq，所以E pqpq。情况2：Epqpq。则E pqpq。下证E没有内定理pqpq。定义W，N， 使得Ww，u，N(w)w，pw，qW。则易见wpq，wp，但wq。所以W，N (pq)(pq)，矛盾于E的内定理在所有邻域框架中有效(参见Chellas的1980)。据上面提到的两种文献，我们还可以证明：2.7 定理(1) PC E K。 (2) PC E K。 (3) E K。 2.8 引理(1) 对上述任意系统S，若S AB且S A，则S B。(2)(Kb的演绎定理) ，AKb B Kb AB。(3) K A Kb A。证明：（1）设S AB且S A。则据定义，存在有穷子集1，2使得S 1AB， S2A。令12。则易得SAB和SA。所以易得SB，因此S B。(2) 显然。(3) “”：显然。下证“”：先证 若Kb A，则Kb A。设Kb A，则在Kb存在从空集到A的推演A1，AnA。对每一1in。若Ai是Kb的公理的代入特例，则Ai也是Kb的公理的代入特例，所以Kb Ai。若存在j，ki使得Ai是从Aj和AkAjAi据MP得到的，则据归纳假设，Kb (AjAi)，Kb Aj，据公理K的代入特例和MP，我们有Kb Ai。至此成立。最后证： 若K A，则Kb A。设K A，则在K存在从空集到A的推演A1，AnA。对每一1in。若Ai是K的公理的代入特例，则易见Ai也是Kb的公理的代入特例，所以Kb Ai。若存在j，ki使得Ai是从Aj和AkAjAi据MP得到的，则据归纳假设，Kb AjAi，Kb Aj，据MP，我们有Kb Ai。若存在ji使得Ai是从Aj据RN得到的，则据归纳假设，Kb Aj，据，Kb Ai。2.9 定理(1) Kb Kb。(2) Kb K。 (3) Kb K。证明：(1) “”：据2.6(1)。“”：设Kb A，则存在从到A的推演A1，AnA。对每一1in。若Ai是Kb的公理的代入特例，则Kb Ai，所以KbAi，因此Kb Ai。若Ai，则KbAiAi，所以Kb Ai。若存在j，ki使得Ai是从Aj和Ak据MP得到，则据归纳假设和上面引理(1)，Kb Ai。(2) 显然。(3) “”：设Kb A。据（1），有Kb A。所以存在有穷子集使得Kb A。据上面引理(2)，易得KbA，据(2)，KA，所以据定义，K A。“”：设K A，存在有穷子集使得KA，据上面引理(3)，KbA，所以KbA。另一方面，Kb，所以据MP，KbA，因此Kb A。3 语法后承和语义后承之间的比较3.1 定理(1) K=RM 。(2) E =NM 。证明：(1) 据S. Popkon的1994(p.127)。类似S. Popkon在其1994(p.127)对 (1)的证明，我们有(2)。3.2 定理 (1) RK。(2) NE。证明：(1) “”：设K A。则可证A是K-一致的。据Lindenbaum-引理，存在K-极大一致集w使得Aw。据K的典范关系模型的基本定理，w但wA，所以RA。“”：先证： K的内定理在每一关系模型的每一可能世界中真。任给K的内定理A，则在K中存在从空集到A的推演A1，AnA。任给1in，下证： Ai在每一关系模型的每一可能世界中真。设Ai是K的公理的代入特例。不妨令Ai(AB)AB。任给关系模型MW，R， 和wW使得w(AB)和wA。则R(w)ABA，所以R(w) B，所以wB，所以wAi，因此成立。设存在j，ki使得Ai是从Aj和AkAjAi据MP得到的，则据归纳假设， Aj和AjAi在每一关系模型的每一可能世界中真。任给关系模型MW，R， 和wW。据，wAj和wAjAi，所以wAi，因此成立。设存在ji使得Ai是从Aj据RN得到的，则据归纳假设， Aj在每一关系模型的每一可能世界中真。任给关系模型MW，R， 和wW。据，MAj，所以据1.9(1)，MAi，所以wAi，因此成立。至此我们证明了成立。设K A，则存在有穷子集使得KA。任给关系模型M和wM 使得w。则w，再据，wA ，因此wA。所以RA。(2) 证明类似(1)。3.3 定理0PC。证明：“”：设PC A。则A是PC-一致的。据Lindenbaum-引理，存在PC-极大一致集w使得Aw。据经典逻辑的基本结果，存在经典模型MV使得MV()=1，但MV(A)=0，所以0A。“”：设PC A，则PC中存在从到A的推演A1，AnA。对每一1in。若Ai是公理的代入特例或Ai，则易证0Ai。若存在j，ki使得Ai是从Aj和AkAjAi据MP得到，则据归纳假设，0Aj且0AjAi。据经典命题逻辑的基本事实，0Ai。4 结论现在我们把上面陆续得到的结果结合起来，其中RR1表示R R1，RR1表示RR1，下标表示得到这些关系的根据。0 3.3 PC 2.6(2) PC 2.7(1) N 3.2(2) E NCMNCF2.6(4) 1.10(5)1.10(6)E 3.1(2) NM1.10(4) NF 1.10(3) NF 1.7(4) NM 2.7(3) 1.13(2) 1.13(3) R 3.2(1) Kb 2.9(1) Kb2.9(3) K2.6(3) K3.1(1) RM1.9(4) RF 1.9(3) RF 1.7(4) RM 1.9(5)1.9(6) RCMRCF 这样的比较后承关系的工作还可以继续下去，也就是说可以丰富上述图表。至少有以下方向可以考虑：模态逻辑方向：一是在PC中只增加RN得到系统N作为代表系统。讨论由此得到的语法后承与加标关系语义的何种衍推关系对应。二是修改推演定义使得US可以用在假设集上，这样的语法后承应该与逐框架衍推对应。一阶逻辑方向：我们已有两类一阶系统，其中一类（全称概括规则像US那样只能用于公理（内定理）的语