互模擬
——檢驗(yàn)集合相等的一個(gè)新工具

姚從軍

（湖南科技學(xué)院 思想政治理論課教學(xué)科研部，湖南 永州 425100）

互模擬
——檢驗(yàn)集合相等的一個(gè)新工具

姚從軍

（湖南科技學(xué)院 思想政治理論課教學(xué)科研部，湖南 永州 425100）

在ZFC-(AFA)系統(tǒng)中，外延公理不可強(qiáng)大得足以判斷兩個(gè)非良基集合是否相等。因此隨著研究范圍的擴(kuò)大，需要新的理論解決新問題。為解決非良基集合相等問題，文章介紹了四個(gè)方法：圖理論方法、互模擬方法、游戲方法和方程法，這幾種方法最后都可以歸結(jié)為互模擬方法。故互模擬是檢驗(yàn)集合相等強(qiáng)有力的工具。

外延公理；非良基集合；可及點(diǎn)圖；互模擬；游戲；解引理

在ZFA公理系統(tǒng)中，根據(jù)外延公理可知：兩個(gè)集合相等當(dāng)且僅當(dāng)它們有共同的元素。因此，要判斷兩個(gè)良基集合是否相同，只需通過觀察看看它們的元素是否相同即可。但是在ZFC-(AFA)系統(tǒng)中，對于兩個(gè)非良基集合而言，外延公理不可強(qiáng)大得足以判斷它們是否相等。例如 A=｛B｝，B=｛A｝，是否相等，根據(jù)外延公理，會(huì)得出 A=B當(dāng)且僅當(dāng)B=A這樣的循環(huán)定義，這就需要研究新的方法，從而可以判斷非良基集合是否相等。

一 圖理論法

（一）圖的裝飾判斷法

集合論中，最初人們?yōu)榱硕x良基集合的相等，使用了外延公理，但是由于非良基集合的存在，用已有的經(jīng)典外延公理無法斷定兩個(gè)非良基集合的相等性，為解決這一問題，集合的圖理論首先產(chǎn)生，用可及點(diǎn)圖刻畫集合。公理AFA假定每個(gè)圖有唯一裝飾。這里存在兩個(gè)重要事實(shí)，裝飾的存在性和唯一性。前一個(gè)事實(shí)告訴我們非良基集合存在，因?yàn)榉橇蓟鶊D的存在是一個(gè)不爭的事實(shí)，而依據(jù)AFA，非良基圖也應(yīng)該有一個(gè)裝飾，根據(jù)可及點(diǎn)圖理論這個(gè)裝飾不可能是良基集合，所以必然是非良基集合，這樣由非良基圖的存在，我們就得出非良基集合的存在性。后一個(gè)事實(shí)告訴我們什么樣的非良基集合是相等的，因?yàn)閾?jù)AFA，每個(gè)圖的裝飾是唯一的，所以如果兩個(gè)集合可有效地指派到同一個(gè)圖的同一個(gè)結(jié)點(diǎn)，則這兩個(gè)集合是相等的。AFA告訴我們每個(gè)圖只是一個(gè)唯一集合的圖，裝飾同一個(gè)圖的所有集合在此理論下都是相等的集合。[1]例如集合?={?}、A={B}和B={A}是相等的，因?yàn)橄聢D有一個(gè)裝飾，其中兩個(gè)結(jié)點(diǎn)都指派?，并且還有一個(gè)裝飾，其中左邊的結(jié)點(diǎn)指派A，右邊的結(jié)點(diǎn)指派B。

所以我們可得出集合相等的一個(gè)判斷方法：兩集合相等，如果它們是同一個(gè)集合的圖，或者可裝飾同一個(gè)圖的同一個(gè)結(jié)點(diǎn)。

（二）圖之間的互模擬關(guān)系判斷法

但是一個(gè)集合可用不同的可及點(diǎn)圖來刻畫，[2]例如，集合2能夠用下列圖刻畫：

我把這種刻畫同一個(gè)集合的各種圖稱為等價(jià)圖（模型等價(jià)），并將這種模型等價(jià)性稱之為裝飾等價(jià)性，因?yàn)樗鼈兪峭粋€(gè)集合的圖，或者說它們有相同的裝飾。

那么刻畫同一個(gè)集合的不同圖之間有什么必然聯(lián)系呢？結(jié)論是兩個(gè)圖等價(jià)當(dāng)且僅當(dāng)它們具有互模擬關(guān)系。Aczel給出了可及點(diǎn)圖理論中的互模擬具體表現(xiàn)形式，他說，系統(tǒng)M上的一個(gè)二元關(guān)系R是M上的一個(gè)互模擬，如果R?R+，這里對于a，b∈M（aM 和bM 分別指結(jié)點(diǎn)a、b的子結(jié)點(diǎn)集）

aR+b??x∈aM?y∈bMxRy∧?y∈bM?x∈aMxRy[3]

既然具有互模擬關(guān)系的圖刻畫同一集合，那么所有具有互模擬關(guān)系的可及點(diǎn)圖所刻畫的集合都是相等的集合。例如，已知一個(gè)集合s={s}，我們用下圖來描述這個(gè)集合，這里用s裝飾結(jié)點(diǎn)n。

再給予一個(gè)結(jié)合t={t}，我們想判斷s和t是否相等。如果僅僅根據(jù)外延公理，我們無能為力，因?yàn)橥庋庸頂喽▋蓚€(gè)集合相等僅當(dāng)它們有相同的元素，而集合s和t只有自身是自己的唯一元素，無法斷定它們的相等性。未解決這一問題，我們必須另辟蹊徑，我們畫出集合t的可及點(diǎn)圖如下，這里用t裝飾n′。

現(xiàn)在我們來檢驗(yàn)集合s和t的圖是否具有互模擬關(guān)系，很顯然兩個(gè)圖之間存在一個(gè)互模擬關(guān)系R={(n，n′)。最后根據(jù)圖理論可知，在非良基集合論中，集合s和t就是相等的集合。

實(shí)際上這是一種間接互模擬判斷法。這樣就找到了刻畫集合相等的強(qiáng)外延公理：兩個(gè)集合相等，當(dāng)且僅當(dāng)它們的可及點(diǎn)圖是互模擬的。這也說明了過去的外延公理，即兩集合相等，當(dāng)且僅當(dāng)它們有相同的元素只是判斷兩集合相等的充分條件。也就是說，如果兩集合有相同的元素，那么它們必然相等；但是兩集合相等不蘊(yùn)涵它們有相同的元素。因此外延公理不是判斷兩集合相等的必要條件。

二 直接互模擬法

一個(gè)關(guān)系 R是集合上的一個(gè)互模擬關(guān)系當(dāng)且僅當(dāng)對所有的集合s和t，如果（s，t）∈R那么

·對?s′∈s，?t′∈t使得（s′，t′）∈R，并且

·對?t′∈t，?s′∈s使得（s′，t′）∈R

兩個(gè)集合s與t是互模擬的當(dāng)且僅當(dāng)存在一個(gè)互模擬關(guān)系R使得（s，t）∈R。

兩個(gè)集合s與t相等當(dāng)且僅當(dāng)它們是互模擬關(guān)系的。[2]

三 游戲法

運(yùn)用兩個(gè)集合S和T玩游戲，你是正方，即認(rèn)為S和T相等，對方稱反方，認(rèn)為S和T不相等，對方先從兩集合中任一集合（比如 S）中找出一個(gè)元素 X，斷言 X不是 T的元素，即不與 T的任一元素相等。你表示反對，并從 T中找出一元素Y，聲稱Y=X?，F(xiàn)在你們再用XY玩游戲，如此進(jìn)行下去。如果在某一點(diǎn)（如 Xˊ、Yˊ），反方找到一個(gè)Xˊ的元素X〞，而你從Yˊ中找不出元素與之相匹配，這時(shí)就表明反方贏了，因此S與T不相等，在其他兩種情況下：

（1）反方不能再前進(jìn)一步，即反方每動(dòng)一步，你均能找到匹配步，最后反方不可再動(dòng)。（2）雙方可以無限地玩下去，無窮無盡。

表明你贏了，即S與T相等。

在游戲中，可得出結(jié)論：S與T相等當(dāng)且僅當(dāng)你有贏的戰(zhàn)略。這種方法其實(shí)是互模擬的間接運(yùn)用，因?yàn)槟阌汹A的戰(zhàn)略，當(dāng)且僅當(dāng)S和T是互模擬的，再根據(jù)方法2，當(dāng)且僅當(dāng)S與T相等。[4]

四 方程解引理法

運(yùn)用圖描述集合的一個(gè)擇換方法是運(yùn)用方程描述集合，比如?是滿足x={x}的唯一集合x，這說明可用x={x}來定義集合?。由于方程涉及到未定元，所以我們在集合中引進(jìn)本元與之對應(yīng)，令x是任一未定元，x的一個(gè)方程系統(tǒng)是滿足如下條件方程類：

對每個(gè)x∈X，恰有一個(gè)形如x={x1，x2，-------}的方程，其中{x1，x2，-------}是 x的子集。我們用（x=Sx）x∈X表示X方程系統(tǒng)，如 x={x，y}，y=?是{x，y}方程系統(tǒng)。一個(gè)方程系統(tǒng)的解是一個(gè)函數(shù)δ，它對每個(gè) x∈X指派一個(gè)集合使得δx={δy|y∈Sx}。集合{δx|x∈X}稱為該方程系統(tǒng)的解集。

圖與方程系統(tǒng)緊密相關(guān)，已知一個(gè)圖，我們把圖中結(jié)點(diǎn)看做未定元，并且對任一結(jié)點(diǎn)x，令x=Sx是一方程，其中S是以結(jié)點(diǎn) x的后繼為元素的集合，這樣就得到一個(gè)方程系統(tǒng)；相反，已知一個(gè)X方程系統(tǒng)，我們把X中的未定元看做結(jié)點(diǎn)，并且令x，y∈X，x→y當(dāng)且僅當(dāng)y∈Sx，這樣我們就得到一個(gè)圖。我們設(shè)該方程的解為δ，與之對應(yīng)的圖的裝飾是{δx|x∈X}。在每一個(gè)方向，一個(gè)給定方程系統(tǒng)的解δ指派給X中任一未定元x的集合δx，與對應(yīng)的圖裝飾d指派給結(jié)點(diǎn)x的集合dx相同，兩個(gè)不同類模型建立了對應(yīng)性，并且圖與對應(yīng)的方程系統(tǒng)都是同一集合的模型。由于每個(gè)圖有唯一裝飾，則相應(yīng)可得到每個(gè)方程系統(tǒng)有唯一解。故 X方程系統(tǒng)與 Y方程系統(tǒng)等價(jià)，當(dāng)且僅當(dāng)它們的解集相同。而解集是集合，兩個(gè)集合相同當(dāng)且僅當(dāng)它們是互模擬的，所以兩個(gè)解集相同當(dāng)且僅當(dāng)它們是互模擬的。由方程系統(tǒng)與圖的對應(yīng)性和每個(gè)圖都是一個(gè)集合的圖理論可知，這兩個(gè)方程系統(tǒng)也是分別刻畫某個(gè)集合的方程系統(tǒng)，故兩個(gè)集合相等當(dāng)且僅當(dāng)刻畫它們的方程系統(tǒng)有相同的解集，當(dāng)且僅當(dāng)對應(yīng)的方程系統(tǒng)的解集是互模擬的。[5]

刻畫集合相等還有其它的方法，這里不一一列舉。上面四種方法有一個(gè)共同點(diǎn)，那就是均直接或間接用到互模擬，也就是這四種判斷集合相等性方法最后都?xì)w結(jié)為判斷不同類對象間的互模擬性，這從另一個(gè)方面反應(yīng)了互模擬在理論上的應(yīng)用價(jià)值，它是判斷集合相等性的強(qiáng)有力的工具。

[1]Davide Sangiorgi.On the origins of Bisimulation,Coinduction,and Fixed Points[J].Tcchnical Report UBLCS-2007-24,October 2007.

[2]Jelle Gerbrand. Bisimulations on Planet. Kripke[D].PhD thesis ,insititute for logic,Language and Computation.University of Amsterdam,1998:5-6.

[3]P.Aczel.Non-Well-Founded Sets[M].Stanford: CSLI,1988:20-26.

[4]Van Benthem Modal logic for open minds[M].Stanford:CSLI Publications, 2005:30-34.

[5]J. Barwise, L. Moss. Vicious Circles: On the Mathematics of Non - Well –Founded Phenomena[M]. Stanford: CSLI,1996:77-83.

B815.1

A

1673-2219（2011）03-0088-02

2010―10―08

姚從軍（1971－），男，湖北隨州人，哲學(xué)博士，講師，研究方向?yàn)楝F(xiàn)代邏輯。

(責(zé)任編校：周 欣)