（逻辑学专业论文）非良基集与模态逻辑.pdf

， 一、 j 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的e i jj 昂l j 本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版：在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 珈7 年占月y o e t 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 砌7 年亏月力日 摘要 摘要 在策梅洛弗兰克尔的集合论公理系统z f 中，基础公理把集合的论域限制 到良基集合。因此，不存在属于关系的无穷降链，也不存在属于自身的集合。 1 9 8 9 年阿克采尔创立了非良基集合理论，引入反基础公理a f a 替换z f 中的基 础公理f a ，从而得到非良基集合论系统z f a 。由于非良基集合可以用来构造循 环现象的模型，而这些循环现象都不能用经典集合论来描述，因此，它们在哲 学、经济学、模态逻辑、语言学以及理论计算机科学中具有十分广阔的应用前 景。接受非良基集合并发展非良基集理论具有重要的理论意义和应用价值。 本文研究非良基集合与模态逻辑的关系，在模态逻辑的集合论语义下探讨 了一些重要的语义概念，进而研究了集合( 模型) 的构造、可定义性等等模型 论问题。概括说来，本文的主要工作包括以下三个方面： 第一，梳理了非良基集合论的理论背景、发展历史和研究现状，介绍了非 良基集合在众多研究领域的广泛应用。 第二，根据阿克采尔和巴威斯等人的观点，阐述了非良基集合的基本理论， 从集合与图的关系和方程组的解两个方面引入反基础公理，保证非良基集合的 存在性。接着，引入两个重要的概念。一个概念是本元，它既不是集合也不是 类，但可以作为集合的元素。把本元引入图的装饰，便得到加标图。另一个概 念是集合上的互模拟关系，它用于判定两个非良基集合相等。 第三，在集合论语义下重新研究模态逻辑。本文探讨了框架、模型和集合 之间的联系，然后研究集合的构造以及模态可定义性问题，并且将基本模态语 言翻译到经典( 一阶或二阶) 集合论语言。本文还引入了集合之间的互模拟关 系和方程组之间的互模拟，进而研究加标图上的互模拟与模态等价之间的关系。 最后，在集合论语义下重新研究模态逻辑的一些元逻辑性质。 本文的主要创造性工作在于： 第一，在模态逻辑的集合论语义下，定义了集合之间的一些非标准运算， 包括不交并、生成子集合、p 态射、树展开等，并证明了模态公式在这些运算下 的保持或不变结果。 第二，把基本模态语言翻译到经典集合论语言，并且证明了语义上的对应 结果，初步探讨了范本特姆类型的刻画定理。 i 摘要 第三，在模态逻辑的集合论语义下，研究可定义性理论。本文重点研究了 如何使用集合类对模态公式进行分类，从模态逻辑t 的特征公式出发，把分类 结果推广到其它模态逻辑的特征公式，包括模态逻辑k d 、k 4 、k b 、k 5 和g l 的特征公式等等。 第四，使用图和加标图等语义结构，初步研究了模态逻辑系统的元逻辑性 质，主要包括正规模态逻辑的完全性、有穷加标图性质和可判定性质。本文还 尝试使用纯集合和含有本元的集合直接研究这些元逻辑性质。 目前，我国逻辑学界对非良基集合论及其应用的研究几乎还是一片空白， 尚处起步阶段。在这方面，本文研究工作的意义是，在借鉴和吸纳国外研究成 果的基础上，把非良基集合与模态逻辑相结合的研究成果引进、介绍到国内。 更重要的是，本文在非良基集合论语义下重新研究了模态逻辑，解决了一些模 型论问题，这有利于促进各个逻辑分支的共同发展，更大程度地发挥逻辑学的 工具性作用。我认为，模态逻辑与非良基集合论的结合是一个具有深厚理论意 义和应用价值的研究方向。 关键词：非良基集合模态逻辑可定义性互模拟元逻辑性质 a b s n a c t a b s t r a c t i nt h ez e r m e l o - f r a e n k e ls y s t e mz fo fs e tt h e o r y , t h ef o u n d a t i o na x i o mr e s t r i c t s t h ed o m a i no fs e tt h e o r yt ow e l l - f o u n d e ds e t s t h u st h e r ea r en oi n f i n i t e l yd e s c e n d i n g - c h a i n s ，a n dn os e tb e l o n g i n gt oi t s e l f i n19 8 9 ，a c z e le s t a b l i s h e dn o n w e l l f o u n d e d s y s t e mz f ao f s e tt h e o r yb yr e p l a c i n gt h ef o u n d a t i o na x i o mi nc l a s s i c a ls y s t e mz fq t s e tt h e o r yb yt h ea n t i f o u n d a t i o na x i o ma f a s i n c en o n - w e l l f o u n d e ds e t sc a nb e u s e dt om o d e lc i r c u l a rp h e n o m e n at h a tc a n n o tb ed e s c r i b e di nc l a s s i c a ls e tt h e o r y , l e yh a v ev a s ta p p l i c a t i o n si np h i l o s o p h y , e c o n o m i c s ，m o d a ll o g i c ，l i n g u i s t i c sa n d t h e o r e t i c a lc o m p u t e rs c i e n c e s i th a sv e r yi m p o r t a n tt h e o r e t i c a li m p l i c a t i o n sa n dv a l u e f o ra p p l i c a t i o n t i l i sd i s s e r t a t i o ns t u d i e st h er e l a t i o n s h i pb e t w e e nn o n w e l l f o u n d e ds e t sa n d m o d a ll o g i c i ti n v e s t i g a t e ss o m ei m p o r t a n ts e m a n t i cn o t i o n s ，a n dt h e ni n v e s t i g a t e s t h em o d e l t h e o r e t i cp r o b l e m so fs e t ( m o d e l ) c o n s t r u c t i o na n dd e f i n a b i l i t y i ng e n e r a l ， t h ew o r ki nm yd i s s e r t a t i o nc o n t a i n st h ef o l l o w i n gt h r e ep o i n t s f i r s t ，i ts k e t c h e st h et h e o r e t i c a lb a c k g r o u n d ，h i s t o r y , a n dr e c e n tr e s e a r c ho f n o n - w e l l f o u n d e ds e tt h e o r y a n di ta l s od i s c u s s e sv a s ta p p l i c a t i o n so fn o n w e l l f o u n d e d s e t s s e c o n d ，i te x p l a i n st h eb a s i ct h e o r yo fn o n - w e l l - f o u n d e ds e t sa c c o r d i n gt oa c z e l a n db a r w i s ee t c a n di ti n t r o d u c e sa n t i - f o u n d a t i o na x i o mf i o mt w op e r s p e c t i v e s ：t h e r e l a t i o nb e t w e e ns e ta n dg r a p h ,a n dt h es o l u t i o no fa ne q u a t i o ns y s t e m t h u s n o n w e l l f o u n d e ds e t se x i s t t h e nt w oi m p o r t a n tn o t i o n sa r ei n t r o d u c e d o n ei st h e n o t i o no fu r e l e m e n t u r e l e m e n t sa r en e i t h e rs e t sn o tc l a s s e s ，b u tc a nb ee l e m e n t so f s e t s b ya d d i n gu r e l c m e n t si n t og r a p hw e c a no b t a i nl a b e l e dg r a p h s t h eo t h e rn o t i o n i st h eb i s i m u l a t i o nr e l a t i o no ns e t sw h i c hi su s e dt od e c i d ew h e t h e rt w o n o n w e l l f o u n d e ds e t sa r et h es a m eo rn o t t h i r d ，t h ed i s s e r t a t i o ni n v e s t i g a t e sm o d a ll o g i cu n d e rs e t - t h e o r e t i cs e m a n t i c s i t e x p l o r e st h er e l a t i o nb e t w e e nf r a m e ，m o d e la n ds e t t h e ni ts t u d i e ss e tc o n s t r u c t i o n s a n dt h ep r o b l e mo fm o d a ld e f i n a b i l i t ya n di ta l s ot r a n s l a t e sb a s i cm o d a ll a n g u a g ei n t o c l a s s i c a l ( f i r s t o r d e ro rs e c o n d - o r d e r ) s e tt h e o r e t i cl a n g u a g e s i ta l s oi n t r o d u c e st h e n o t i o no fb i s i m u l a t i o no ns e t sa n do ne q u a t i o ns y s t e m s a n dt h e ni ti n v e s t i g a t e st h e i i i a b s t r a c t r e l a t i o nb e t w e e nb i s i m u l a t i o na n dm o d a le q u i v a l e n c eb e t w e e nl a b e l e dg r a p h s f i n a l l y , i te x p l o r e ss o m em e t a - l o g i c a lp r o p e r t i e so fm o d a ll o g i c r n l em a i nc r e a t i v ep o i n t so ft h i sd i s s e r t a t i o na r et h ef o l l o w i n g f i r s t , i td e f i n e su n d e rt h e s e t - t h e o r e t i cs e m a n t i c so fm o d a l l o g i c s o m e n o n - s t a n d a r do p e r a t i o n sb e t w e e ns e t s ，i n c l u d i n gd i s j o i n tu n i o n , g e n e r a t e ds u b s e t , p - m o r p h i s m ，t r e eu n r a v e l i n ge t c ，a n dp r o v e sp r e s e r v a t i o no ri n v a r i a n c er e s u l t su n d e r t h o s eo p e r a t i o n s s e c o n d ，i tt r a n s l a t e sb a s i cm o d a ll a n g u a g ei n t oc l a s s i c a ls e t t h e o r e t i cl a n g u a g e s ， a n dp r o v e ss o m es e m a n t i c a l l yc o r r e s p o n d i n gr e s u l t s i ta l s ot o u c h e sv a nb e n t h e m t y p ec h a r a c t e r i z a t i o nt h e o r e m s t h i r d ，i ti n v e s t i g a t e sd e f i n a b i l i t yt h e o r yu n d e rs e t t h e o r e t i cs e m a n t i c sf o rm o d a l l o g i c i tm a i n l yi n v e s t i g a t e sh o wt ou s em o d a lf o r m u l a st oc h a r a c t e r i z es e t so rc l a s s e s o fs e t s i te x t e n d sd e f i n a b i l i t yr e s u l t st oo t h e rc h a r a c t e r i s t i cf o r m u l a so fm o d a ll o g i c s f r o mt h ec h a r a c t e r i s t i cf o r m u l ao fm o d a ll o g i ct ，i n c l u d i n gm o d a ll o g i c sk d ，k b ，k 4 ， k 5 ，g la n ds oo n f o r t h ，s o m em c t a - l o g i c a lp r o p e r t i e so fm o d a ll o g i c ，i n c l u d i n gc o m p l e t e n e s s ，f i n i t e l a b e l e dg r a p hp r o p e r t ya n dd e c i d a b i l i t y , a r ei n v e s t i g a t e du n d e rs e t - t h e o r e t i cs e m a n t i c s i ta l s ot r i e st os t u d yt h o s ep r o p e r t i e sb yu s i n gp u r es e t sa n ds e t sw i t hu r e l e m e n t s i nr e c e n ty e a r s ，a l m o s t1 1 0l o g i c i a ni nc h i n ah a ss t u d i e dn o n - w e l l f o u n d e ds e t s a n dt l l e i ra p p l i c a t i o n s i ts t a y si nt h ei n i t i a ls t a g e i nt h i ss e n s e ，t h em e a n i n go ft h e d i s s e r t a t i o ni st oi n t r o d u c er e s u l t so b t a i n e df r o mc o m b i n a t i o nn o n w e l l f o u n d e ds e t s a n dm o d a ll o g i ci n t oc h i n ab ys t u d y i n ga b r o a di n v e s t i g a t i o n s w h a tm o r ei m p o r t a n t i st h ef o l l o w i n g i tg i v e san e wr e s e a r c hf o rm o d a ll o g i cu n d e rn o n w e l l - f o u n d e d s e t - t h e o r e t i cs e m a n t i c s ，a n ds o l v e ss o m em o d e l t h e o r e t i cp r o b l e m s t h i si sh e l p f u lf o r t h ed e v e l o p m e n to fv a r i o u sl o g i c a ld i r e c t i o n sa n dm a k i n gt h er o l eo fl o g i ca st o o l m o r ei m p o r t a n t it h i n kt h a tt h ec o m b i n a t i o no fn o n - w e l l - f o u n d e ds e t sa n dm o d a l l o g i ci s ar e s e a r c hd i r e c t i o nw i mp r o f o u n dt h e o r e t i c a lm e a n i n g sa n dv a l u eo f a p p l i c a t i o n s k e y w o r d s ：n o n - w e l l - f o u n d e d s e t , m o d a ll o g i c ，d e f i n a b i l i t y , b i s i m u l a t i o n , m e t a - l o g i c a lp r o p e r t i e s i v 目录 目录 引言1 第一章非良基集合概述5 第一节良基集合和非良基集合5 1 1 1 集合论悖论5 1 1 2 公理集合论z f c 6 1 1 3 良基集与非良基集7 第二节非良基集的研究历史和现状8 1 2 1 第一个时期：观念的萌芽( 1 9 0 0 1 9 2 4 ) 9 1 2 2 第二个时期：公理集合论( 1 9 2 5 1 9 4 9 ) 9 1 2 3 第三个时期：非良基集的存在性( 1 9 5 0 1 9 7 4 ) 1 0 1 2 4 第四个时期：非良基集合论的引入及其应用( 1 9 7 5 ) 1 1 第三节非良基集与循环现象1 4 1 3 1 哲学中的循环现象。1 4 1 3 2 经济学中的循环现象。1 6 1 3 3 模态逻辑中的循环现象1 6 1 3 4 情境语义学中的循环现象。1 7 1 3 4 理论计算机科学中的循环现象。l8 第二章非良基集合的基本理论2 0 第一节本元与非良基集合2 0 2 1 1 本元2 0 2 1 2 非良基集2 2 第二节集合与图2 3 2 2 1m o s t o w s k i 坍塌定理2 3 2 2 2 集合与图。2 4 2 2 3 集合与加标图2 9 第三节集合与方程组的解3 2 2 3 1 集合相等的判定3 2 n 目录 2 3 2 反基础公理的解引理表述3 3 2 3 3 反基础公理的两种等价表述3 5 第四节互模拟3 6 2 4 1 集合上的互模拟关系一3 6 2 4 2 加标图之间的互模拟关系3 7 2 4 3 方程组之间的互模拟关系。3 8 2 4 4 强外延性一4 1 三章模态逻辑的集合论语义4 3 第一节模态语言的句法和语义4 4 3 1 1 基本模态语言和无穷模态语言。4 4 3 1 2 模态逻辑的关系语义学。4 6 3 1 3 正规模态逻辑。4 7 第二节框架、模型与集合5 0 3 2 1 模态模型与加标图。5 0 3 2 2 模态逻辑的集合论语义5 2 第三节模态语言与集合论语言5 8 第四节集合运算和保持结果6 2 3 4 1 不交并“ 3 4 2 生成子集合6 6 3 4 3p - 态射6 7 3 4 4 树展开。6 9 第五节互模拟与模态等价7 0 3 5 1 加标图之间的运算7 0 3 5 2h e n n e s s y - m i l n c r 性质7 4 3 5 3v a nb e n t h e m 刻画定理7 7 第四章模态可定义性7 9 第一节使用模态公式刻画集合7 9 第二节有穷模态语言与单个集合的刻画8 4 第三节使用集合类对模态公式分类8 7 4 3 1 对应理论8 7 v i 目录 4 3 2 使用集合类对模态公式分类9 2 第四节一些刻画结果9 6 4 4 1 持续性公理t 9 6 4 4 2 传递性公理口p 啼d d p 9 7 4 4 3 对称性公理p 一口p 9 7 4 4 4 欧性公理劬_ 口劬9 8 4 4 5l 6 b 公理口( 口p 一计一口p 9 8 第五章模态逻辑的元逻辑性质1 0 0 第一节完全性10 0 5 1 1l 加标图1 0 0 5 1 2 强完全性1 0 3 第二节有穷加标图性和可判定性1 0 7 第三节集合论语义与元逻辑性质。10 9 参考文献l13 致j 谢1 17 个人简历1 18 v 引言 引言 在康托尔的集合论中，把满足特定性质的所有元素收集起来，就可以形成 一个集合。但是事实上并非所有性质都能确定一个集合，也就是说，如下概括 原理不成立： ( 概括原理) 如果p 是一种性质，那么缸：p ) 是集合。 考虑性质p = xg 工，假设y = 伽：xgx ) 是集合。那么y y 是否成立? 如果y y ，那么根据y 的定义，ygj ，；如果ygy ，那么p ) ，所以y y 。因此，y y 当且仅当yq y ，这样就得到矛盾。因此，性质x 叠x 无法确定一个集合。这里的 矛盾就是罗素发现的集合悖论。为了避免悖论，集合论研究者提出了如下分离 公理： ( 分离公理) 对任何集合x 和性质p ，存在集合y 使得y = 仁x ：p ( z ) ) 。 这条公理表明，可以从一个集合x 中分离出具有某种性质p 的元素组成的集合。 给定集合“，那么y = 缸u ：x 昼x ) 是一个集合，由y y 可得yg y ，但是由yg y 无法得到y y ，由此避免了悖论。 为了有效地避免悖论，人们创立了集合论的公理系统z f ( 以及带选择公理 的z 陀) ，它常常被看做数学的基础，断言所有数学对象都是集合，而且所有数 学性质都能从集合论公理得出。在z f c 公理系统中，有一条公理称为基础公理： ( 基础公理) 每个非空集合有极小元。 这条公理形式化表示为：v x ( x 历_ 砂秒xa xn y = 历) ) 。根据基础公理，不 存在属于自身的集合，也不存在无穷下降的序列x o x i x 2 弓和循环加x i x o 。这样的集合也称为良基集合。因此，在集合论z f c 的论域中，只 包括良基集合。 一般地，任给一个类p 上的二元关系e ，如果对每个工p ，e x t e ( x ) = 沙p ： l 引言 e y x 是集合，并且p 的每个非空子集都有b 极小元，那么称e 是p 上的良基关 系。一个类尸和尸上的良基关系e 恰好组成一个良基图( 只目。在集合论z f c 中，m o s t o w s k i 坍塌定理表明了良基图与集合之间的联系：对每个良基图以习， 存在一个传递类m 使得) 和( p ，目之间存在同构映射，也就是说，每个良基 图都有惟一的装饰。 由于集合与良基图之间存在这种联系，彼特阿克采尔( a c z e l ，e ) 进一步 把这种联系推广到集合和图，提出了反基础公理：每个图都有惟一的装饰。这 里的图包含了非良基图，而非良基图对应的集合必然是非良基的。非良基集合 论允许非良基集合存在，从而扩大了集合论的论域。因此，使用非良基集合论 能够处理所有的图，而不仅限于良基图。 在这样的背景下，可以把非良基集合论应用到模态逻辑，使用非良基集合 论重新研究模态逻辑。克里普克( k r i p k e ，s ) 的关系语义学表明，模态语言实 际上是谈论关系结构的语言。基本模态语言所谈论的框架是一个二元组( 形r ) ， 其中形是非空集，r 是形上的二元关系。因此，一个关系结构恰恰可以看作一 个图，这样就可以把( 非良基) 集合与图联系起来。基本模态语言中的模态词 “ 和“口 可以通过关系结构上的二元关系r 来解释，然而在集合论中，集 合之间的逆属于关系恰恰可以作为二元关系来解释模态词。此外，模态逻辑的 应用领域十分广泛，它在认知逻辑、信念逻辑、道义逻辑、时态逻辑等等领域， 特别是在理论计算机科学研究和人工智能研究中有着十分广泛的作用。同样， 非良基集合论在这些领域中也发挥着重要的作用。 使用集合论研究模态逻辑这种思想，基于集合与图之间的联系，对模态逻 辑提出了一种全新的研究视角。巴威斯( b a r w i s e ，j ) 、莫斯( m o s s ，l ) 、巴塔格 ( b f l t a g ，a ) 等等逻辑学家在这个领域做出了开创性的工作。巴威斯和莫斯在 恶性循环这本著作中，提出了使用集合研究模态逻辑的基本思路。巴塔 格在他的论文中也详细研究了使用模态公式刻画集合的问题。沿着这些开创性 的工作，本文首先在集合论语义下研究模态逻辑的一些模型论问题，包括构造 一些非标准的集合运算以及相应的模态公式保持或不变结果。然后，根据巴威 斯等人提出的研究思路，沿着巴塔格的工作，推进了使用集合类对模态公式分 类的研究。最后，本文还探讨了如何在集合论语义下研究模态逻辑的一些元逻 辑性质。 回b a r w i ，j 锄dm o s s ，l v i n o u sc i r c l 岱：o nt h em a t h e m a t i 岱o fn o n w e l l f o u n d e dp h 舶o m e n a c s ui 触嘴 n o t 鹤，n u m b e r6 0 s t a n f o r d ：c s l ip u b l i c a t i o n s ，l9 9 1 6 。b a l t a g , s i r s ：as t r u c t u r a lt h e o r yo f s e t s p k d d i s s e r t a t i o n , h & a n au m v e r s i q , 1 9 9 8 2； 统 论 第二章介绍非良基集合的基本理论。首先引入本元的概念。本元不是集合， 也不是类，引入本元是为了便于应用非良基集合刻画循环现象。第二，从集合 与图的关系和方程组的解两个角度论述反基础公理。根据彼特阿克采尔的思 想，把经典集合论的m o s t o w s k i 坍塌引理从良基图推广到任意图，从而引入反基 础公理：每个图都有惟一的装饰。根据巴威斯和莫斯等人的观点，每个集合都 可以看作某个含有未知元的方程组的解。为了保证方程组的解的惟一性，引入 解引理：每个方程组都有惟一的解。因此，比如方程组x = 缸) 的良基解是不存 在的，如果它有解，这个解一定是非良基的。第三，给出集合之间互模拟的概 念，用来判定两个非良基集合相等。此外，还给出了加标图之间的互模拟关系。 第三章讨论模态逻辑的集合论语义。第一，给出基本模态逻辑和无穷模态 逻辑的句法和语义。第二，讨论框架、模型和集合的关系，主要目的是引入模 态逻辑的集合论语义。第三，把基本模态语言的公式翻译为经典集合论语言的 公式，然后证明一些语义上的对应结果，即模态逻辑的集合论语义的满足关系 和经典逻辑的满足关系有某种对应。第四，在集合论语义下定义一些非标准的 集合运算，包括集合族的不交并、生成子集合、p 态射象、树展开等等。使用模 型论的研究方法，给出模态公式在这些运算下保持或不变的结果。第五，探讨 互模拟与模态等价的关系。在模态模型论中，模态等价与互模拟之间的相互联 系是一个重要问题。一般地，互模拟关系蕴涵模态等价；但是，反过来不一定 成立。对于基本模态语言来说，存在模态等价但并非互模拟的加标图；但是对 于无穷模态语言来说，任何两个模态等价的加标图都是互模拟的。 第四章研究模态可定义性的问题，它包括两个方面：第一，使用模态公式 刻画集合或集合类：第二，使用集合类对模态公式进行分类。首先阐述b a l t a g 定理，即使用由有穷命题变号集构造的模态语言刻画特定集合的条件。然后在 集合论语义下引入研究模态可定义性理论的方法，探讨如何使用集合类对模态 公式进行分类。最后把使用集合类对模态公式分类的结果从简单的模态逻辑t 的特征公式p 一p 推广到其它经典模态逻辑系统的特征公式。 3 引言 第五章研究了模态逻辑的一些重要元逻辑性质，包括正规模态逻辑的完全 性、有穷加标图性质、可判定性质等等。首先，在图和加标图语义下研究模态 逻辑的完全性问题，然后研究模态逻辑的有穷加标图性质和可判定性质。从图 和加标图的观点看，关于模态逻辑的完全性、有穷加标图性质和可判定性的讨 论，与克里普克语义下对模态逻辑的讨论是十分类似的。最后，本文还尝试使 用纯集合的概念来讨论图，使用带本元的集合来讨论加标图，并且在这两种集 合之间建立一种联系，这种联系相当于图和加标图的联系，或者相当于框架和 模型之间的联系。 4 第一章非良基集合概述 第一章非良基集合概述 本章引入非良基集的基本概念，我的主要工作是综述它的研究历史和现状， 并且介绍非良基集合在哲学、语言学、计算机科学、经济学等众多领域中的应 用。本章主要参考阿克采尔( a c z e l ，p ) 的著作非良基集合，集合论的基 本概念参考耶赫( j e c h ，t ) 的著作集合论。 第一节良基集合和非良基集合 1 1 1 集合论悖论 在引言中我们已经谈到康托尔的概括原则和罗素发现的悖论。概括原则断 言：任给一个性质p ，那么存在一个集合s ，s 的元素恰好是具有性质尸的对象。 罗素利用满足性质xgx 的元素x 组成集合缸：xgx ) 推出了矛盾，这个矛盾后来 被人们称为“罗素悖论 。罗素还曾以“理发师悖论 作比喻来说明这一悖论。 另一个悖论是“布拉里一福蒂悖论”。布拉里福蒂悖论是说，假设存在所有序数 的集合，序数上的序“ 将是这个集合的良序，并且它的序型将是最大的序数。 但是，当时人们已经知道不存在最大的序数。康托尔自己也已经发现集合论中 存在一些悖论。 为了避免悖论，当时的逻辑学家采取了公理化的方法。由于那时皮亚诺算 术公理系统已经建立，特别是1 8 9 9 年希尔伯特在几何基础中具体解决了公 理方法的一些基本逻辑问题，纠正了欧几里德公理的错误，建立了一个严格的 几何公理系统，这使公理化方法有了系统和广泛的应用。因此，在集合论中， 人们使用公理化方法对集合的存在性作一些必要的限制，从而建立它的形式公 理系统。1 9 0 8 年，策梅罗( z e r m e l o ，e ) 使用回避真类的方法建立了集合论的公 理系统z 。除此之外，他还严格陈述了使用条件确定集合的假设。弗兰克尔 ( f r a e n k e l ，a ) 和其他人对策梅罗的系统进行了补充，从而得到系统z f 。在z f 上增加选择公理得到z f c 系统。z f c 的展开是形式化的，它以带等词( = ) 的一 阶谓词演算为基础，加上关于集合基本性质的非逻辑公理，从而组成演绎体系。 近一个世纪以来，z f ( 或z 粥) 系统一直被广泛使用着。 a c z e l ，p n o n w e l l f o u n d e ds e t s s t a n f o r dc s l ip u b l i c a t i o n s ，19 8 8 。j e c h t s e tt h e o r y s p f i n g 盯, 2 0 0 3 。李娜论超穷数理论的发展南开哲学第二辑2 0 0 6 8 5 8 6 5 第一章非良基集合概述 1 1 2 公理集合论z 彤 集合论的公理系统z f 的非逻辑公理包括：配对公理、并集公理、幂集公理 和无穷公理。这些公理都是用来刻画集合存在性的。此外，z f 的非逻辑公理还 包括：外延公理、分离公理模式、替换公理模式和基础公理。这些公理用来刻 画集合的性质。在z f 的基础上增加选择公理得到z f c 系统。z f c 的九条非逻 辑公理可以详细表述如下： ( 1 ) 外延公理：坛( 比g 石hz 力_ x = j ，) 。如果x 和y 有相同的元 素，另b 么z = j ，。 ( 2 ) 配对公理：坛砂j zv w ( w z hw = x vw = 力。对任何集合x 和y ， 存在集合k y ) 恰好包含x 和y 。 ( 3 ) 分离公理模式：如果是性质，那么坛砂坛( z yh z xa ) ) 。 如果砧) 是性质，那么对任意集合工都存在集合y = z x ：妒) ，它包含x 中具 有性质潲所有元素z 。 ( 4 ) 并集公理：坛砂比( z yhj “x ( z “) ) 。对任意集合x ，取x 中每 个元素的所有元素构成一个集合y ，称为x 的并集合，记为：恤。 ( 5 ) 幂集公理：坛砂比( z yhz 曲。对任意集合x ，由x 的所有子集 构成一个集合y ，称为x 的幂集，记为：。 ( 6 ) 无穷公理：女( 乃xav y 工u 钞) 功) 。这条公理说明，存在一 个无穷集合。 ( 7 ) 替换公理模式：如果一个类f 是一个函数，那么对每个集合工，月l 是一个集合。对每个公式妒伍力，如下公式是替换公理： v x v y v z ( 9 l ( x , 力a 毗z ) 一y = z ) 一v u 3 v v t ( t ，h 玉u ，力) 。 ( 8 ) 基础公理：v x ( x j 2 f _ 砂t ynx = 彩) ) 。这条公理表明，任意非空 集合都有极小元。 ( 9 ) 选择公理：蝴o 工a y 乃_ 3 f ( f u n ( f ) av y e x ( f 0 9 力) ) ，其中 f u n ( f ) 表示7 是函数”，l i p v x ( x 厂h 狲= t y , z ) av u ( t y , “) 厂_ “= z ) ) ) 。对于 任意由非空集组成的集族x ，都存在选择函数厂使得对于任意y 工都有八力e y 。 在z f c 公理系统中，外延公理是判定两个集合是否相等的标准。配对公理、 并集公理、幂集公理、无穷公理断言某些集合的存在性。分离公理的陈述使用 6 第一章非良基集合概述 了集合论语言的公式，它是一条公理模式，使得我们可以从给定的集合中分离 出由具有特定性质的所有元素组成的集合。替换公理模式是使用类函数，取给 定集合在类函数下的象，从而构成一个集合。基础公理也称为良基公理或正则 公理，它说明不存在属于自身的集合，也不存在无穷下降的序列。选择公理说 明，对任意由非空集组成的集族，可以从该集族的每个集合中“选取 一个元 素。集合论的z f c 公理系统的建立，不仅消除了康托尔集合论中的罗素悖论， 还保留了康托尔集合论中的超穷序数理论。 1 1 3 良基集与非良基集 在z f c 公理系统中，基础公理把集合论的论域限制到良基集合。使用基础 公理，我们可以证明如下的结论。 1 1 定理对于任意的集合x ，都有x 叠x 成立。 证明：