鄧雄雁，胡澤洪

（華南師范大學政治與行政學院，廣東廣州510631）

協(xié)調、一致與一階公理系統(tǒng)的強完全性

鄧雄雁，胡澤洪

（華南師范大學政治與行政學院，廣東廣州510631）

在公理系統(tǒng)中演繹定理是連接一致性和協(xié)調性的橋梁。對于帶演繹定理的公理系統(tǒng)，可以證明公式集的一致性和協(xié)調性是等價的。在不帶演繹定理的一階公理系統(tǒng)中，一致性和協(xié)調性的差異集中體現(xiàn)在強完全性證明過程中。基于一致性的證明不依賴演繹定理，但基于協(xié)調性的強完全性證明多處受演繹定理束縛。文中將給出一個松綁方案，基于協(xié)調性上證明一階公理系統(tǒng)QC1的強完全性。

一致；協(xié)調；演繹定理；強完全性

一致、協(xié)調和演繹定理

一致和協(xié)調有兩個層面：一是系統(tǒng)本身的一致與協(xié)調，令S是公理系統(tǒng)，稱S協(xié)調?①S⊥，稱S是一致系統(tǒng)?S的定理集Th（S）是S一致集；二是公式集的一致和協(xié)調，稱Φ是S一致集?對所有有窮集Ψ?Φ，S?∧Ψ，稱Φ是S協(xié)調集?ΦS⊥②。

按照直觀理解，一個“好”的推理要求不能推出矛盾“⊥”。由這個標準，公式集的一致性達不到這個要求。因為可能出現(xiàn)這種情況，Φ├⊥但Φ還是一致的。例如，在某些系統(tǒng)中，比如下文的QC1，公式集Φ＝｛A，?xA→?xB，?xA→?x?B｝├QC1⊥，但是不存在有窮集Ψ?Φ，使得QC1?∧Ψ。相對來說，一個協(xié)調集Φ肯定推不出矛盾“⊥”，所以，協(xié)調更符合直觀。然而，在形式系統(tǒng)中特別是基本模態(tài)系統(tǒng)的完全性證明中用得較多的卻是一致性。個中原因值得探討。

一致和協(xié)調性的邏輯性質跟系統(tǒng)是否有演繹定理密切相關。按照是否有一般性演繹定理（下文簡稱為演繹定理），公理系統(tǒng)可以分為兩類：一類是有演繹定理的系統(tǒng)，一類是沒有演繹定理的系統(tǒng)。鑒于本文主要考慮一階系統(tǒng)情況中協(xié)調性和演繹定理以及其完全性證明三者之間的關系，有必要把這些系統(tǒng)簡要的列出來。較為常見的QC1是由下列公理模式和推理規(guī)則構成的形式系統(tǒng)：

（一）公理模式：

1，A→B→A

2，（A→B→C）→（A→B）→A→C

3，?（A→?B）→（B→A）

4，?xA→A（t／x），其中t對x代入自由，

5，?x（A→B）→A→?xB，x在A中不自由

（二）推理規(guī)則：

1，分離規(guī)則（MP），從A和A→B可以推出B

2，全稱概括規(guī)則（UG），從A可以推出?xA

Φ├QC1A指A為公式集Φ的QC1語法后承，也可稱為從Φ到A的QC1推演（在本文里，除非特別說明，用Φ├A表示Φ├QC1A）。當Φ為空集時，A為QC1定理，記為├A，也稱A在QC1中可證。Φ?A指對一階語言L的任一解釋M＝＜D，H＞和Μ上的任一指派σ，M?Φ［σ］?M?A［σ］；當Φ為空集時，A為有效式，記為?A。其中D為非空個體域；H為一階語言L的非邏輯符號集到Dn的一個映射。若s是L的特征符號，也可用sM表示H（s）。

QC2的公理模式1－4與QC1的相同，模式5是：A→?xA，其中x在A中不自由；模式6：?x（A→B）→?xA→?xB；模式7：?x1…?xnA，A是前六類公理之一，x1…xn是任意變元符號且n≥1；推理規(guī)則只有MP。類似于QC2的系統(tǒng)有葉峰的系統(tǒng)［7］，李小五的P［4］。

QC3的公理模式和推理規(guī)則與QC1相同，但對UG進行限制，規(guī)定只允許對系統(tǒng)定理運用UG。類似系統(tǒng)有陳慕澤、余俊偉的Q系統(tǒng)［2］。

QC2和QC3、QC1對于UG規(guī)則的不同使用所導致的結果就是：QC2和QC3有演繹定理，而QC1沒有演繹定理。陳慕澤詳細論述了演繹定理與UG的關系［1］，這里不再贅述。

與一階系統(tǒng)情況類似，對于含有必然化規(guī)則（RN）的模態(tài)系統(tǒng)，如果RN只運用于定理集，則這個系統(tǒng)有演繹定理；如果RN運用于前提集，則沒有的演繹定理。

但QC1有受限制演繹定理：令A和B是任意L公式，Φ是L任公式集，若Φ∪｛A｝├B，并且演繹對涉及A中的自由變元沒有使用概括，那么Φ├A→B。證明從略。（下文中凡是出現(xiàn)類似的較為常識性的定理、引理或結論，這些定理、引理或結論的證明在數(shù)理邏輯著作中均可找到，此處就不再贅述）

推論：若Φ∪｛A｝├B，且A是閉公式，則Φ├A→B。

一致和協(xié)調的邏輯性質須從如下兩個方面加以探討。

一、系統(tǒng)本身的協(xié)調性和一致性：S一致?S協(xié)調。

證明：“?”設S一致。據(jù)系統(tǒng)一致定義，Th（S）是S一致的?！?是任何集合的有窮子集，∴據(jù)公式集一致定義，S?∧?③。 ∴S⊥，也就是S協(xié)調。

二、公式集的協(xié)調性和一致性：在有演繹定理的系統(tǒng)S中，Φ是S一致?Φ是S協(xié)調；在無演繹定理的系統(tǒng)S中，Φ是S－協(xié)調?Φ是S一致，反向不成立。

證明：“?”，設Φ是S一致，假如Φ不是S協(xié)調，則Φ├s⊥，∵推演的長度是有窮的，∴存在有窮集｛A1…An｝?Φ，使得｛A1…An｝├s⊥，運用演繹定理n次得，├sA1→…→An→⊥（無演繹定理的系統(tǒng)在此處通不過），即├s（A1∧…∧An）→⊥，∵├PCA→B?├PC?B→?A有├s?⊥→?（A1∧…An），再據(jù)├s⊥，∴├s?（A1∧…∧An），矛盾于題設。

“?”，設Φ是S協(xié)調但不S一致，則存在有窮集Ψ?Φ，使得├s?∧Ψ，易見Φ├s?∧Ψ且Φ├s∧Ψ，∵├PC?A→A→B，∴Φ├s⊥，矛盾。

上述結果表明，對于系統(tǒng)本身的協(xié)調性和一致性，我們可以等價地運用這兩個概念，無需顧忌系統(tǒng)是否有演繹定理。但對于公式集的協(xié)調性和一致性，必須分情況對待：對于有演繹定理的系統(tǒng)，比如QC2與QC3，公式集的一致性和協(xié)調性是等價的；但對于只有受限制的演繹定理的系統(tǒng)，比如QC1或基本模態(tài)系統(tǒng)，協(xié)調性強于一致性。造成這種差異的關鍵在于｛A1…An｝├⊥?├A1→…→An→⊥的推導過程中前者可以運用演繹定理而后者不能。

QC1或基本模態(tài)系統(tǒng)中的公式集的一致和協(xié)調的區(qū)別集中體現(xiàn)在這些系統(tǒng)的強完全性證明過程中。強完全性指：Φ?A?Φ├A；弱完全性指：?A?├A。

對于這些系統(tǒng)的強完全性證明有兩種版本：一種是基于公式集的一致性，例如通行的模態(tài)邏輯的強完全性證明，如Hughe，G.E.and Cresswell，M.J或LI Xiao－wu的證明［8，10］，其特點是證明過程無需運用演繹定理；一種是基于公式集的協(xié)調性，漢密爾頓，劉壯虎基于協(xié)調性基礎上證明了QC1弱完全性［3，5］。筆者尚未看到基于協(xié)調性的基本模態(tài)系統(tǒng)的強完全性證明?；趨f(xié)調性的QC1強完全性證明也具有一定難度，本文嘗試用亨金方法［9］證明QC1強完全性。

基于協(xié)調性的QC1強完全性證明

基于協(xié)調性QC1強完全證明要解決如下問題，第一，ΦA?Φ∪｛?A｝協(xié)調，是否成立，下文命題1的證明過程展示這個結論是不成立的；第二，Φ協(xié)調?Φ可滿足，是否成立，這是證明完全性的核心問題。第二個問題又分為兩個方面：首先，任何一個協(xié)調集與亨金公式集的并是否還是協(xié)調集；其次，任何一個協(xié)調集與亨金公式集的并能否擴充為極大協(xié)調集。這三個問題的共同特點是均要牽涉演繹定理。但相對于一致性的證明，在這三種情形中均不需演繹定理。基于協(xié)調性QC1強完全性證明要依賴演繹定理，已經(jīng)知道QC1系統(tǒng)只有受限制的演繹定量。如何化解這個矛盾是解決第二、三個問題的關鍵。我們的策略是盡量避免使用演繹定理：或者弱化使用演繹定理情形，只用受限制的演繹定理；或者把關于協(xié)調性的討論轉化為關于一致性的討論。

下面開始證明Φ?A?Φ├?，從命題1到命題6分成六個步驟。

引理1：對任L協(xié)調集Φ和任意L公式A，它的自由變元是x1…xm，Φ├A?Φ├?x1…?xmA。

證明：“?”，對A的自由變元個數(shù)進行歸納，當m＝1，A只有一自由變元x，若Φ├A，UG，則Φ├?x1A；當m＞1，假設對于m－1成立，證對m成立，若Φ├A，由歸納假設有Φ├?x1…?xm－1A，再UG，有Φ├?x1…?xmA。

“?”，若，Φ├?x1…?xmA，對m作類似歸納，∵任一變元對自身作代入總是代入自由的，∴再與公理4，MP m次，易得Φ├A。

命題2，任何一個L協(xié)調集與L1亨金公式集的并是一致。⑤

引理2，等值置換定理：令B是A的子公式，A［B／C］是用C置換A中的B的某個出現(xiàn)得到的公式，則├B?C＆├A?├A［B／C］

引理3，設Φ是L一致，增加可數(shù)無窮個新常元來膨脹原有語言，Φ作為膨脹語言中L1的公式集仍是一致的。

枚舉膨脹語言中的每一公式和變元集中的每一變元構成的序對如下：

＜A1，x1＞，…，＜An，xn＞，…

定義亨金公式：B1＝??x1A1→?A1（c1／x1）。其中，c1是膨脹語言中第一個不在A1中出現(xiàn)的新常元。假設Bn已經(jīng)構造完畢，令Bn＋1＝??xn＋1An＋1→?An＋1（cn＋1／xn＋1）。其中cn＋1是L1中第一個不在｛A1，…，An＋1｝中出現(xiàn)的新常元，規(guī)定語言L1是可數(shù)的，上述構造是能完成的。令Ψ＝｛B1，…，Bn｝，則Ψ稱為L1亨金公式集。

引理4，Φ∪｛A｝不一致?存在有窮集Θ?Φ使得├∧Θ→?A。

現(xiàn)證命題2：設任一L協(xié)調集Φ，如前所證，由Φ是協(xié)調的，可知Φ是一致的，據(jù)引理3，Φ作為膨脹語言中L1的公式集仍是一致的，下證Φ與L1亨金公式集Ψ的并Φ∪Ψ還是一致的。

證明：假設不一致，則總存在n∈?，使得1≤n且Φ∪｛B1…Bn＋1…｝不一致。

極限情況：Φ∪｛B1｝不一致，由引理4，存在有窮集Ξ?Φ使得├?Ξ→?B1。據(jù)B1的構造和├PCA→B∧C?├PCA→B＆├PCA→C有├∧Ξ→??x1A1⑴＆├∧Ξ→A1（c1／x1）⑵，令y1是第一個不在Φ，A1，和∧Ξ→A1（c1／x1）中出現(xiàn)的變元，用y1替換每個c1的出現(xiàn)，則├（∧Ξ→A1（c1／x1））（y1／c1），∵據(jù)B1規(guī)定，c1不在Φ中出現(xiàn)，則c1肯定不在∧Ξ中出現(xiàn)，∴├∧Ξ→A1（c1／x1）（y1／c1）⑶，據(jù)亨金公式構造規(guī)定，c1也不在A1中出現(xiàn)，∴A1（c1／x1）（y1／c1）＝A1（y1／x1），再由⑶和引理2有├∧Ξ→A1（y1／x1），UG，得├?y1（∧Ξ→A1（y1／x1））⑷，∵y1不在∧Ξ中出現(xiàn)，∴再據(jù)公理5與⑷，MP，得├∧Ξ→?y1A1（y1／x1）⑸，∵由約束變元易字定理?y1A1（y1／x1）??x1A1，∴由⑸和引理2得├∧Ξ→?x1A1⑹，由⑴⑹和├PCA→B＆├PCA→C?├PCA→B∧C得├∧Ξ→??x1A1?x1A1，再由├PCA→⊥?├PC?A，有├?∧Ξ矛盾于Φ一致。

一般情況：∵Φ∪｛B1｝一致的，∴總存在某個最小n使得Φ∪｛B1…Bn…｝是一致，現(xiàn)在Φ∪｛B1…Bn＋1…｝不一致，據(jù)引理4，存在有窮集Ξ?Φ∪｛B1…Bn…｝使得├∧Ξ→?Bn＋1，據(jù)Bn＋1構造規(guī)則，得├? Ξ→??xn＋1An＋1⑴和├∧Ξ→An＋1（cn＋1／xn＋1），令yn＋1是第一個不在Φ，An＋1和∧Ξ→An＋1（cn＋1／xn＋1）中出現(xiàn)的變元，用yn＋1替換每個cn＋1的出現(xiàn)。據(jù)語言L1是可數(shù)語言和集合論知識，這是可以做到的，則├（∧Ξ→An＋1（cn＋1／xn＋1））（yn＋1／cn＋1）。類似于上述根據(jù)情況證明過程，有├∧Ξ→An＋1（yn＋1／xn＋1）。由UG，得├?yn＋1（∧Ξ→An＋1（yn＋1／xn＋1）），再由yn＋1不在∧Ξ中出現(xiàn)和公理5，MP，有├∧Ξ→?yn＋1An＋1（yn＋1／xn＋1）；由易字定理和引理2得├∧Ξ→?xn＋1An＋1⑵；由⑴⑵易得├?∧Ξ，矛盾于Φ∪｛B1…Bn…｝一致。

命題3，任何一個協(xié)調集與亨金公式集的并能擴充為亨金集。

引理5，緊致性定理：Φ是一致的?Φ的所有有窮子集是一致的。

引理6，林登保姆引理：任何一致集都可以擴充為極大一致集。

先證：⑴Ψn是一致的。

據(jù)設定條件，已知Φ＝Ψ0是一致的。對任意n＞0，歸納設定Ψn是一致的。下證Ψn＋1是一致的。為此考慮Ψn∪｛An｝的一致性。

情況1 Ψn∪｛An｝是一致的：此時Ψn＋1＝Ψn∪｛An｝，∴Ψn＋1是一致的。

情況2 Ψn∪｛An｝不是一致的：此時Ψn＋1＝Ψn∪｛?An｝。假設Ψn＋1不是一致的，則據(jù)本情況的設定條件和剛才的假設，Ψn∪｛An｝不是一致的，Ψn∪｛?An｝不是一致的，∴據(jù)引理4，存在有窮子集Θ，Ξ?Ψn使得├∧Θ→?An，├∧Ξ→An。易得，├?（∧Θ∧∧Ξ），∵Θ∪Ξ是Ψn的有窮子集，∴Ψn不是一致的，與歸納設定矛盾。

再證：⑵Σ是極大一致集。

任給A∈L1，總存在n∈?使得A＝An。據(jù)Ψn＋1的構造，An或?An總有一屬于Ψn＋1?Σ，∴Σ是極大的。假設Σ不是一致的，則據(jù)引理5，存在有窮子集Θ?Σ使得Θ不是一致的。但Σ的每一有窮子集顯然是某個Ψn?Σ的子集，∴再據(jù)定理5，易見Ψn不是一致的，矛盾于⑴。［10］124－125

令

可以看到，協(xié)調集的一致擴充過程中始終未曾用到演繹定理，這也是把關于協(xié)調性的討論轉化為關于一致性的討論根據(jù)所在。

命題4，亨金集Σ有典范解釋。

定義一致集Σ的解釋和指派σ如下：⑴定義D是膨脹一階語言L1的所有項的集合；⑵對每一常元c，定義c＝c；⑶對n元函數(shù)F，F(xiàn)t1…tn＝Ft1…tn；⑷對n元謂詞符號P，〈t1….tn〉∈P?Pt1…tn∈Σ；⑸對任意變元，σ（x）＝x

引理7，M?A［σ］?A∈Σ，對于所有A∈L1，所以有M?Σ［σ］。驗證從略。

引理8：令L1是L的膨脹語言，令解釋M是相對于原語言L的規(guī)約，使得⑴DL＝DL1，⑵HL（s）＝HL1（s），對每一特征符號s。則對每一L公式A和每一指派σ，M1?A［σ］?M?A［σ］。

命題5，在亨金集里，Φ∪｛??x1…?xmA｝可滿足?Φ∪｛?A｝可滿足。⑥

引理9：對任極大一致集Σ，｛A，A→B｝∈Σ?B∈Σ。

引理10，代入自由引理，令t對A中的x自由，任給解釋M和σ，使得σ（a／x）（x）＝tM則M?A（t／x）［σ］?M?A［σ（a／x）］。其中σ是任一解釋M的指派，σ（a／x）使得對任一變元y，若y≠x，則σ（a／x）（y）＝σ（y）；若y＝x，則σ（a／x）（y）＝a。

現(xiàn)證命題5：設Φ∪｛??x1…?xmA｝可滿足，往證Φ∪｛?A｝是可滿足的。

一方面：由??x1…?xmA∈Σ⑴，且具有??xA的形式，據(jù)亨金公式集的構造，總可以找到一亨金公式??xnAn→?An（cn／xn）與??x1…?xmA對應。令x1＝xn，則?x2…?xmA＝An，顯然??x1…?xmA→??x2…?xmA（c1／x1）∈Σ⑵。由⑴⑵和引理9，可得??x2…?xmA（c1／x1）∈Σ⑶。??x2…?xmA（c1／x1）又具有??xA形式，不難找到一亨金公式與之對應，使得??x2…?xmA（c1／x1）→??x3…?xmA（c1／x1）（c2／x2）∈Σ⑷。再據(jù)引理9，⑶⑷，有??x3…?xmA（c1／x1）（c2／x2）∈Σ。重復上述步驟m次，最終可得?A（c1／x1）…（cm／xm）∈Σ。據(jù)引理7，? A（c1／x1）…（cm／xm）是可滿足的⑸。

命題6，Φ?A?Φ├A。

如本文所述，一致和協(xié)調的區(qū)別主要是指公式集層面上的，且只有在不帶演繹定理的系統(tǒng)中討論二者的區(qū)別才是有意義的。對于有演繹定理的公理系統(tǒng)，公式集的協(xié)調性和一致性通過演繹定理過渡，從而二者是等價的。在不帶演繹定理的系統(tǒng)中，二者的區(qū)別主要是體現(xiàn)在強完全性證明過程當中?；趨f(xié)調性的強完全性證明對演繹定理依賴性比較強，基于一致性的強完全性證明不依賴于演繹定理。還可以看到，協(xié)調集不一定能擴充為極大協(xié)調集。因為在極大擴充的過程中要受到演繹定理的束縛。只有對于有演繹定理的系統(tǒng)，協(xié)調集可以擴充為極大協(xié)調集。值得提出的是，任一協(xié)調閉式集可以擴充為極大協(xié)調閉式集，不論系統(tǒng)是否帶演繹定理。原因是在擴充過程中可以運用受限制的演繹定理。但是，本文只是給出了一種基于協(xié)調性的QC1強完全性證明，基于協(xié)調性的基本模態(tài)系統(tǒng)強完全性證明尚待解決。

注 釋：

① 為了簡潔，本文用“?”表示元語言意義上的“…當且僅當…”，用“?”表示“若…，則…”，用“∵”表示“因為…”，用“∴”表示“所以…”，用“＆”表示“并且”。

② 在不引起混淆情況下S和下標s均可省略。

③ 定義：∧?＝⊥?！摩担健统闪⒌臈l件是：如果∧Φ所有的合取枝都為真，那么∧Φ為真。顯然當合取枝數(shù)目為零時，條件句前件為假，條件句空洞成立。

④ 這個定理和下文中將出現(xiàn)的├PC?A→A→B以及導出規(guī)則├PC?B→?A?├PCA→B或├PCA→B?├PC?B→?A等是命題邏輯中定理，用├PC標示，以示區(qū)別。在一階邏輯中或模態(tài)邏輯可以使用命題邏輯中的定理或導出規(guī)則，而不用考慮演繹定理的束縛，因為命題邏輯中的定理都是一階邏輯或模態(tài)邏輯的定理，而命題邏輯的導出規(guī)則是依據(jù)定理轉化而來的。依據(jù)前面的討論，對定理集作推演不會受到演繹定理的束縛。

⑤ 從這里開始，我們把關于協(xié)調集的討論轉化為一致集的討論，由命題6，再從一致性返回到協(xié)調性。

⑥ Φ∪｛??x1…?xmA｝可滿足?Φ∪｛?A｝是可滿足，在一般情況下不成立。

⑦ 設σ是任一解釋M的指派，定義σ（a／x）使得對任一變元y，若y≠x，則σ（a／x）（y）＝σ（y）；若y＝x，則σ（a／x）（y）＝a。

［1］ 陳慕澤.全稱概括規(guī)則和受限制的演繹定理——國內數(shù)理邏輯教材中的一個問題.浙江社會科學，2002（2）：99－101.

［2］ 陳慕澤，余俊偉.數(shù)理邏輯基礎.北京：中國人民大學出版社，2003.

［3］ 漢密爾頓.數(shù)理邏輯.朱水林，譯.上海：華東師范大學出版社，1986.

［4］ 李小五.數(shù)理邏輯.廣州：中山大學出版社，2005.

［5］ 劉壯虎.邏輯演算.北京：中國社會科學出版社，1993.

［6］ 余俊偉.形式系統(tǒng)的可靠性和完全性問題.湖南科技大學學報：社會科學版，2005，1：25－29.

［7］ 葉峰.一階邏輯與一階理論.北京：中國社會科學出版社，1994.

［8］ 胡澤洪.蘊涵芻議.華南師范大學學報：社會科學版，2006（5）：1－6.

［9］ 王健平.實質蘊涵與自然語言中的相關蘊涵命題分析.華南師范大學學報：社會科學版，2005（3）：11－18.

［10］ HUGHE G E，CRESSWELL M J.A New Introduction to Modal Logic.London：Routedge，1996.

［11］ HENKIN L.The Completeness of The First－order Functional Calculus.The Journal of Symbolic Logic，1949，14：159－166.

［12］ LI XIAO－WU.A Course in Modal Logic（Electronic version）.Guangzhou：Institute of Logic and Cognition of Sun Yat－sen University，2008.

【責任編輯：趙小華】

B812.23

A

1000－5455（2010）03－0112－05

2009－11－20

鄧雄雁（1979—），男，湖南衡南人，華南師范大學政行學院博士研究生；胡澤洪（1964—），男，湖南雙峰人，華南師范大學政行學院教授、博士生導師。