第3章 CHAPTER 3 集合论初步 第2章中引入了谓词逻辑形式系统K2，并指出K2中的定理是逻辑上的定理。由于这些定理都是永真式，所以它们不依赖于具体的解释，当然也就不与具体的数学领域相关了。从这一章开始，介绍可以用谓词逻辑形式系统进行描述的公理集合论。本章介绍公理集合论的前5个公理，这5个公理所对应的初级形式是高中集合论中所接触的，这里无非使用形式化的公理描述，使得整体上更加严格一些罢了。在开始介绍之前，首先引入与数学领域相关的一般化的数学形式系统。 3.1数学形式系统 第2章介绍了谓词逻辑形式系统K2，然而，该形式系统不是与数学领域相关的形式系统，因为它是纯粹“逻辑意义上”的形式系统，它的公理和定理也都是逻辑意义上的公理和定理。它可以看作是一个采用谓词逻辑进行推理证明的“框架”或者“平台”。即使对形式系统K2赋予数学上的解释，形式系统中的定理在此数学解释下虽然有了数学上的含义，然而其为真的本质还是来源于该定理本身所具有的逻辑样式，而非数学解释本身。因为，这些定理是永真的，它们的真值不依赖于具体解释，所以，当然也就不是来源于数学知识本身了。换句话说，即使不采用数学意义上的解释，这些定理也会在其他解释下为真。举个简单的例子。比如，考虑形式系统K2中的一个谓词公式 x(F(x)→F(x)) 它是一个永真式。如果解释I中论域为整数集，F(x)表示“x可以被4整除”，则该谓词公式也就有了数学含义“对于任意的整数x，如果x可以被4整除，则x可以被4整除”。这当然是一个真值为真的数学命题，其为真是由于其逻辑本身导致的，所以在数学上也不会有什么意义和价值。如果对该谓词公式赋予其他的解释，它的真值一定还是为真的。 我们考虑另一个谓词公式 x(F(x)→G(x)) 考虑解释I中论域依然为整数集，F(x)依然表示“x可以被4整除”，G(x)表示“x可以被2整除”，则该谓词公式在解释I下的数学含义为“对于任意的整数x，如果x可以被4整除，则x可以被2整除”。这当然也是一个真值为真的数学命题，然而，这次的命题为真除了含有“任意”“如果……，则……”这样的逻辑样式外，还因为谓词F、G在解释下所具有的数学含义。当然，这个谓词公式也不是永真式，所以其真值依赖于所赋予的解释。比如，把谓词F、G的解释互换之后，这个谓词公式在解释下的命题就是一个假的命题了。 既然作为逻辑上的“框架”或者“平台”的谓词逻辑形式系统K2本身没有数学意义上的价值，那我们就在这个平台上加入一些具有数学意义的谓词公式作为公理集。我们把这种加入了数学意义的形式系统K2的扩张称为数学形式系统(mathematical formal system)。由于这种数学意义上的扩张加入的公理不是永真式，而是在某一数学领域内为真的谓词公式，因而，这些公理可能在其他的数学领域内为假。换句话说，这些谓词公式的真假依赖于所赋予它们的数学意义上的解释，在不同数学含义上的解释，其真值可能不同。 当然，我们在数学中使用形式系统的概念是为了对数学中的推理证明进行整体上的分析，以获得关于数学中推理证明的一般性结论，比如，无矛盾性、完备性。这种情况主要发生在涉及数学中相对基础的部分，比如算术、集合论。因为在涉及数学相对基础的部分时，我们所关注的是： 数学是在哪些公理基础之上，并以何种方式建立起来。需要指出，数学内部知识的分析发现过程中，还是采用我们一直以来所采取的自然语言的方式进行，以求简练和便于理解。我们在用自然语言进行推理证明时，会无意识地遵循和使用逻辑规则，并且这些逻辑规则与形式逻辑的规则是相一致的。 现在，我们把目光聚焦在数学形式系统上，也就是在“逻辑平台”K2上，增加了数学意义上的公理。在数学领域中，两个数学对象的同一是一个非常重要的基本概念，它是由相等关系来定义的。相等关系形式化之后是一个二元谓词，比如，自然语言中的“a=b”，形式化为E(a,b)，其中的谓词E是使用了英文Equality的第一个字母。我们希望可以把自然语言中涉及相等概念的真命题，在形式化之后可以成为数学形式系统中的定理。比如命题“对于任意的数学对象x,y，如果x=y，则有y=x”，其形式化之后的谓词公式表示为xy(E(x,y)→E(y,x))。由于这些真命题是在相等这个解释的基础上才为真，它们所对应的形式化之后谓词公式并不是形式系统K2的定理，所以需要加入关于相等的公理之后才能证明出它们。在对K2增加关于相等的形式化公理之前，我们先分析相等所具有的最基本性质，当然是用自然语言所描述的关于相等的直觉上的最基本事实。关于相等，它有如下最基本事实： (1) 对于任意的数学对象x，有x=x； (2) 对于任意的数学对象x、y，如果x=y，则有y=x； (3) 对于任意的数学对象x、y、z，如果x=y并且y=z，则有x=z； (4) 对于任意的数学对象x、y，如果x=y，则对于任意的函数f，有f(x)=f(y)，对于任意的性质P(·)，有P(x)和P(y)的真值相同。 其中，前3条是关于对象相等的直接属性，第4条则说明了对象相等具有对任意函数和任意性质的可替换性。 对于上面的4条最基本事实，将(1)和(4)的形式化结果作为公理添加到形式系统K2的公理集中，称它们为“等词公理”。 (1) E(x,x)； (2) E(tk,s)→E(f(t1,…,tk,…，tn),f(t1,…,s,…，tn))； (3) E(tk,s)→(F(t1,…,tk,…，tn)→F(t1,…,s,…，tn))。 其中，t1,t2，…,tn，s是K2中任意的项； f是K2中任意的n元函数； F是K2中任意的n元谓词。 可以看出，等词公理中的第1条对应于相等最基本事实中的(1)； 等词公理中的第2、3条对应于相等最基本事实中的(4)，只是将其中的一元函数f扩展为n元函数，将性质P(·)用n元谓词F表示。 对于相等最基本事实中的(2)、(3)，它们形式化之后的结果分别为 xy(E(x,y)→E(y,x))(3.1.1) xyz(E(x,y)→(E(y,z)→E(x,z)))(3.1.2) 注意： 如果可以使用连接词∧，最基本事实（3）的形式化结果为 xyz((E(x,y)∧E(y,z))→E(x,z))(3.1.3) 然而，由于形式系统K2中的连接词只有瘙綈、→，所以，利用命题逻辑中的重言等价式 p∧q→rp→(q→r) 易知，式(3.1.3)与式(3.1.2)是等价的。 下面以例题的形式给出式(3.1.1)与式(3.1.2)在形式系统K2中的证明。 【例3.1.1】在形式系统K2中证明式(3.1.1)和式(3.1.2)。 解： 对于式(3.1.1)，有如下证明： (1) E(x,y)→(E(x,x)→E(y,x))应用等词公理(3) (2) (E(x,y)→(E(x,x)→E(y,x)))→ ((E(x,y)→E(x,x))→(E(x,y)→E(y,x)))应用K2中公理(2) (3) ((E(x,y)→E(x,x))→(E(x,y)→E(y,x)))对(1)和(3)应用假言推理规则 (4) E(x,x)应用等词公理(1) (5) E(x,x)→(E(x,y)→E(x,x))应用K2中公理(1) (6) E(x,y)→E(x,x)对(4)和(5)应用假言推理规则 (7) E(x,y)→E(y,x)对(3)和(6)应用假言推理规则 (8) xy(E(x,y)→E(y,x))对(7)应用两次推广规则 对于式(3.1.2)，有如下证明： (1) E(y,x)→(E(y,z)→E(x,z))应用等词公理(3) (2) E(x,y)→E(y,x)应用刚刚证明过的式(3.1.1)的结果 (3) E(x,y)→(E(y,z)→E(x,z))对(4)和(5)应用例2.4.2中结果的代入实例 (4) xyz(E(x,y)→(E(y,z)→E(x,z)))对(3)应用三次推广规则 ▇ 在形式系统K2中证明式(3.1.1)和式(3.1.2)，相当于使用自然语言，利用相等最基本事实中的(1)和(4)去证明(2)和(3)，很容易得出具体的证明过程如下。 对于最基本事实（2）： 已知x=y； 此时，将最基本事实(1)中的x=x看作关于x的命题P(x)，其中P(·)表示“……等于x”； 然后利用最基本事实(4)，P(y)也成立，即“y等于x”也成立，也就是y=x； 再由x,y的任意性，可得最基本事实(2)成立。 对于最基本事实(3)： 已知x=y并且y=z； 根据已得出的最基本事实(2)的结果，有y=x； 此时，将y=z看作关于y的命题P(y)，即P(·)表示“……等于z”； 由于y=x，因而利用最基本事实(4)，P(x)也成立，即“x等于z”也成立，也就是x=z； 再由x、y、z的任意性，可得最基本事实(3)成立。 如果读者将例3.1.1中形式化证明中把E解释为相等的话，再对比使用自然语言去证明(2)和(3)的过程，就会发现： 它们的实质是完全相同的。可以看出，使用自然语言进行证明要比形式化证明简单，且容易理解。我们需要清楚： 采用形式系统的概念并非是为了人们在系统内对某个命题进行证明，而是为了从整体上研究推理证明。在数学的发展历史上，集合论建立之后，人们起初认为已经在数学中建立了“绝对的”基础和真理。然而，后来出现的关于集合理论的悖论，使人们思索如何避免悖论的发生，而这又涉及形式系统的无矛盾性、完备性等这些整体上的概念。使用形式系统的概念，可以把某个领域的数学知识是建立在何种基础之上以及采用何种方法进行推理证明，清晰明白地表现出来，进而才可以分析这个数学领域中是否有悖论以及是否有无法判断真假的命题。当然，形式化的证明虽然烦琐，然而却适合计算机来完成，所以出现了关于机器证明数学定理、人工智能中的机器推理等方面的研究工作。 细心的读者或许会发现，前面关于等词的三条公理都不是封闭的谓词公式，而根据命题2.4.8，应该加入不是定理的封闭的谓词公式作为新的公理，才可以得到形式系统K2的无矛盾扩张。事实上，根据推广规则，多次利用该规则，即可得到这些谓词公式所对应的封闭形式，这在例3.1.1的证明中也可以看出。之所以没有采用等词公理封闭的形式，是为了表示含义时更加清楚明了，也为了证明时使用起来更加方便。 【定义3.1.1】将包含等词公理的K2的扩张称为含等词的数学形式系统。 以后我们谈到数学形式系统，默认是这种含等词的数学形式系统。 3.2外延公理 有了前面关于形式逻辑的一些基础知识，现在开始集合论的介绍。我们所介绍的集合论是一种公理化的集合理论(axiomatic set theory)，它是含等词的数学形式系统，也就是说它在逻辑公理、等词公理的基础上再添加了若干条新的公理。当然，所添加的新的公理是来源于集合的事实和性质的形式化。我们把这种关于集合的数学形式系统称为集合理论形式系统(formal system of set theory)。 我们所介绍的集合理论形式系统是一个简称为ZF的形式系统，“ZF”是由德国数学家策梅洛(E.Zermelo)和以色列数学家弗兰克尔(A.A.Fraenkel)两人姓氏的首字母命名的，因为他们对ZF的建立和完善做出了重大贡献。作为一个集合理论形式系统，ZF中的公理描述起来相对简单明了，现已被数学界接受，是迄今为止最常用的集合理论形式系统。 在ZF的字母表中，没有个体词常元，没有函数词，谓词仅有两个： 除了等词E之外，还有一个谓词F。所以，在ZF中，项的形式只有个体词变元一种，进而原子谓词公式只有E(x,y)和F(x,y)这两种。对于ZF，存在“标准的”解释： 论域解释为“所有集合之全体”，称为“集合宇宙”(universe of sets)； 谓词E解释为“等于”，谓词F解释为“属于”。我们用符号=和∈分别表示等于和属于，因而，原子谓词公式E(x,y)和F(x,y)就可以表示为x=y 和x∈y。进而，对于瘙綈E(x,y)和瘙綈F(x,y)表示为x≠y和xy。 作为K2的扩张，ZF的字母表中没有使用符号、∧、∨、，然而，使用这些符号可以避免仅使用、→所带来的谓词公式的冗长，而且也会使逻辑含义更加清晰，所以，ZF的谓词公式中，也会使用这些符号。当然，这些符号的使用并不是对ZF的字母表添加了新符号，而是由ZF的字母表中的、→“定义”出来的，或者可以理解为是某种关于、→的简写。比如，xA理解为瘙綈x(瘙綈A)，A∨B理解为瘙綈A→B，A∧B理解为瘙綈(A→瘙綈B)，AB理解为瘙綈((A→B)→瘙綈(B→A))，其中A、B表示K2中任意的谓词公式。 对于ZF中的公理，除了采用形式化的谓词公式表示外，还会给出其在标准解释下的自然语言描述。对于由公理所得出的定理及其证明，只给出它们在标准解释下的自然语言描述。 在ZF中，个体词变元也就是英文小写字母x,y,z，…，在标准解释下当然是集合，而且集合在ZF内只能采用字母表中的个体词变元表示。然而，当我们用自然语言描述标准解释下的定理及其证明时，尽管大多数时候也采用英文小写字母表示集合，然而，有时为了更方便地表示特定的含义，也采用英文大写字母或者大写花体字母表示集合。 对于任何解释，其中的论域默认都是非空的，否则形式系统在该解释下就没有任何意义。为了突出ZF标准解释中的论域是非空的，有如下公理： ZF0存在公理： x(x=x) 这条公理在标准解释下的意思是： 存在一个集合。事实上，存在公理可以从等词公理（1），即x=x，以形式化的方式证明得出，也就是说，它事实上是一个定理。把它单独列成一条公理就是为了强调集合宇宙中至少存在一个对象。 下面给出两个集合相等的含义。直观上，集合仅由其元素决定，所以，集合的相等也应该仅由其元素来决定。 ZF1外延公理(axiom of extensionality)： z(z∈xz∈y)→(x=y) 这条公理在标准解释下的意思是： 对于任意的集合x、y，如果集合x的所有元素也是集合y的元素，并且集合y的所有元素也是集合x的元素，那么，集合x等于集合y。 注意： 如果x=y，那么z∈x和z∈y就是一回事，即z∈xz∈y，因而就有 (x=y)→z(z∈xz∈y)(3.2.1) 联立上式和ZF1，可以将ZF1写为 z(z∈xz∈y)(x=y)(3.2.2) 再次指出，我们是采用标准解释下的自然语言得到式(3.2.1)的。当然，也可以采用形式化语言，在ZF的内部一步步得到式(3.2.1)的证明，只是这样做会非常烦琐，反而会把本质的东西变模糊，因而我们不打算给出形式化的证明，但是给出一个大致思路： 利用等词公理（3），得到 x=y→(z∈x→z∈y)(3.2.3) y=x→(z∈y→z∈x)(3.2.4) 利用式(3.1.1)的结果，有 (x=y)→(y=x)(3.2.5) 对式(3.2.4)和式(3.2.5)应用假言推理规则可得 x=y→(z∈y→z∈x)(3.2.6) 联立式(3.2.3)和式(3.2.6)可得 x=y→(z∈yz∈x)(3.2.7) 对上式中个体词变元z应用推广规则，并利用逻辑公理中(6)，可得式(3.2.1)。 类似于等词公理，外延公理也没有采用封闭的形式写出，也是为了理解和使用上的方便。外延公理实质上是定义了两个集合的相等，即只要这两个集合所含有的元素相同，它们就是同一个对象——集合，而与其他因素无关。通过外延公理，我们可以用谓词∈来表示谓词=，从这个角度看，ZF仅使用一个谓词∈即可完成所有谓词公式的表达。 采用形式系统的方法，确实可以清楚明白地显示出关于集合的命题到底是基于哪几条公理得出的。读者也不用对“在标准解释下，ZF中的每一个定理都可以在ZF内部由公理出发得到它们的形式化证明”产生任何的怀疑。然而，为了便于理解，我们仅给出这些定理在标准解释下采用自然语言所表述的非形式化证明。细心的读者或许会有这样的疑问： 既然ZF中的定理都可以由公理出发得到它们的形式化证明，也就是说，无论对ZF中的定理及它们的证明做何种解释，都不影响定理和证明本身，这不就意味着我们可以对ZF中的定理及其证明做任意的解释吗？没错，我们确实可以对ZF做任意的解释，除了形式系统中6条逻辑公理是永真的，其真值与解释没有关系外，只要保证3条等词公理以及即将新添加的关于集合的公理在该解释下的真值为真，即可使得ZF中的定理在该解释下皆为真。与以往我们反复强调的一样，我们建立形式系统（包括ZF）的初衷，是为了从整体上对某一数学领域（包括集合理论）讨论无矛盾性和完备性。在集合理论的初期，集合论是以朴素集合论(naive set theory)的形式产生的，随后出现的关于集合的悖论迫使人们重新思考集合理论的建立方法，并由此产生了ZF。ZF除了可以避免已知的关于集合的悖论，还可以对一些关于集合重要命题的研究起到推动作用，比如著名的选择公理(axiom of choice)和连续统假设(continuum hypothesis)。在形式系统内部进行纯粹的形式化推导证明没有任何实际意义，只有与一定的解释相结合才会使得形式系统具体化，也就是与具体的数学领域相结合，才可以焕发出强大的生命力。对ZF做关于集合的解释是一种标准的解释，这种解释是建立ZF的源头，所以，我们当然选择这种标准的解释。在这种解释下，ZF中的每一个谓词公式都可以解释为关于集合的一个表述，特别地，每一条公理和定理在该解释下都是真的。对于非标准的解释，也具有一定的意义，由于它们涉及模型理论(model theory)和非标准分析(nonstandard analysis)，所以不在本书的讨论范围。 3.3分离公理 现代集合理论是由德国数学家康托(G.Cantor)建立的，其表述采用了非形式化的朴素方法。其中，在定义一个集合时，使用的是所谓的概括原理(comprehension principle)： 若P(x)表示关于x的一个性质，则{x|P(x)}为一个集合。我们可以把x看作个体词变元，P(x)就表示含自由的个体词变元的谓词公式。如果P(x)为xx，则按照概括原理，{x|P(x)}是一个集合，将其记为a。那么，a是否属于a呢？如果a属于a，则a就应该具有P(x)所表示的性质，所以a就不属于a； 如果a不属于a，则a就满足P(x)所表示的性质，就有a属于集合a。可以看出，无论a是否属于a，都会导致矛盾的结果。这个悖论就是著名的罗素悖论(Russell’s paradox)，由于其在表述上简单明了，在当时引起了整个数学界的震动，因为当时人们认为整个数学可以牢固地建立在集合理论的基础之上。 上述悖论的出现促进了集合理论的形式化发展。为了解决罗素悖论，我们应该弱化概括原理，这就引出了下一条公理——分离公理。 ZF2分离公理(axiom schema of separation)： yz(z∈yz∈x∧A(z))，其中A(z)表示不含个体词y的谓词公式。 公理中之所以采用了A(z)而非A这种写法，是为了突出个体词变元z，说明我们当前对z感兴趣，并不表示z在A中一定是自由的，虽然在大多数情况下z在A中是自由的。分离公理的意思是，给定一个集合x以及一个性质A(z)，就可以肯定一个集合y的存在，或者等价地，集合y是存在的，其元素是集合x中满足性质A(z)，或者等价地，使得谓词公式A(z)为真的那些元素z。也就是说，要想确定一个集合y的存在，首先必须有一个集合x，然后利用性质A(z)，从集合x中“分离出”符合性质A(z)的元素，去构成集合y。 我们还将由分离公理所确定的那个集合y，按照通常的习惯写为y={z|z∈x∧A(z)}，这相当于引入新的符号“{”和“}”来表示一个对象的存在。可以看出，分离公理确实是概括原理的弱化形式，因为根据分离公理，虽然集合y也可以写成y={z|B(z)}的形式，其中B(z)为z∈x∧A(z)，然而B(z)是包含z∈x的谓词公式； 如果B(z)不含有z是属于某个集合的含义，那么，{z|B(z)}就不是一个集合。从而，罗素悖论中所出现的{x|xx}就不再是集合了，也就避免了悖论。需要指出，B(z)含有z是属于某个集合的含义是指： B(z)蕴含了z∈u，其中u为某个集合，也就是B(z)→(z∈u)，在此条件下，对B(z)和B(z)→(z∈u)应用假言推理规则可以得到z∈u，进而再对B(z)和z∈u应用合取律即可得到B(z)∧z∈u，这说明B(z)和B(z)∧z∈u是等价的，进而{z|B(z)}就是集合了。 为了方便起见，我们定义xy是指z(z∈x→z∈y)，这相当于定义了新的谓词，并称xy为x是y的子集(subset)。对于分离公理中的y={z|z∈x∧A(z)}，由于z∈y蕴含了z∈x，所以y是x的子集，因此分离公理有时也称为子集公理。为了方便，也把y写作y={z∈x|A(z)}。 分离公理中，在给定集合x的情况下，每给定一个谓词公式A(z)就可以确定一个集合y，所以ZF2是一个公理模式(axiom schema)，类似于谓词逻辑中一个重言式会有很多个代换实例的情形。 联合ZF2和ZF1，还可以进一步得出： 由ZF2所确定的集合y是唯一存在的。假设y～也是由ZF2确定的集合，即y～={z|z∈x∧A(z)}，则有 t(t∈yt∈y～) 再根据ZF1可得y=y～。 罗素悖论中的{x|xx}不是集合，那它是什么呢？虽然我们的论域是集合宇宙，也就是说讨论的对象都是集合，然而，为了后面讨论的方便，需要引入类(class)的概念。 【定义3.3.1】对于任意的谓词公式A(x)，称对象{x|A(x)}为类。 从该定义可以看出： 集合一定是类，因为根据ZF2，可以把集合{z|z∈x∧A(z)}表示成{z|B(z)}，其中谓词公式B(z)为z∈x∧A(z)； 类的元素是集合，因为在类的定义中，其元素是满足性质A(x)的个体词变元x，当然也就是集合了。 对于不是集合的类，我们称之为“真类”(proper class)。可以看出，真类相对于集合而言，它们显得“太大”了，大到不能从某一个集合中分离出来。 我们知道，ZF中的原子谓词公式只有x=x和x∈x两个，它们的否定式为x≠x和xx。根据ZF中的等词公理，x=x是为真的，x≠x是为假的。因而，对于类{x|x=x}而言，集合宇宙中的所有集合都使得x=x为真，所以类{x|x=x}就是集合宇宙，把它记为 V={x|x=x}(3.3.1) 集合宇宙非常大，其是一个真类，不是集合。因为如果集合宇宙V是集合，那么根据ZF2，就可以构造集合u={x|x∈V∧xx}，而这是不可能的，因为无论u∈u还是uu，都会导致矛盾的产生。 对于类{x|x≠x}，由于x≠x一定为假，所以x≠x→x∈u就一定为真，其中u为任意一个集合。u的存在性可以由ZF0保证，也就是说x≠x蕴含了x∈u，所以可以将{x|x≠x}写作{x|x∈u∧x≠x}。当然，上述说明也可以理解为： 由于x≠x一定为假，所以x≠x就等价于x∈u∧x≠x，其中u为任意一个集合。不管哪种理解，类{x|x≠x}都可以写作{x|x∈u∧x≠x}，再根据ZF2可知，它为一个集合，称其为空集(empty set)，记为 ={x|x≠x}(3.3.2) 结合ZF1，可以得出空集是唯一的，因而才可以用符号表示空集。空集是不含任何元素的，因为如果空集含有任意的元素x，就会具有性质x≠x，这是与等词公理矛盾的。由于空集不含任意元素，所以对任意的集合y，z∈→z∈y一定为真，所以y，即空集是任意集合的子集。事实上，对于空集的定义和性质，相信读者应该是很熟悉的，因为在高中时已经学习过了关于集合的基本知识，无非那里是以朴素集合论的视角进行介绍的，这里采用形式化公理的方法使得集合理论的介绍更加严谨。 关于x∈x和xx，目前的公理还没有给出关于它们的任何信息，我们只是知道类{x|xx}不是一个集合，它是一个真类，称为罗素类(Russell class)； 对于类{x|x∈x}是集合还是真类，根据目前的ZF0~ZF2还不能确定。 再次强调，ZF的论域是集合宇宙，即我们所考察的对象仅仅只有集合这一种对象，因而ZF中所有的谓词公式在标准解释下不会涉及任何其他对象，引入类这种对象是为了后面论述的方便。比如，当我们谈到集合宇宙时知道它是一个真类。 3.4对集公理 在ZF中，所考察的对象只有集合，因而，集合的元素还是集合，集合元素的元素还是集合，直到碰到某个集合为空集为止。可以想象，空集是ZF的基础构成模块。然而，如何利用空集去构成集合，前面的公理并没有告诉我们，需要一些新的公理来完成这项工作。由于集合由元素构成，而元素也是集合，所以，首先想到的是，给定一个集合，比如空集，以它为元素的对象{}也应该是集合。这可以由如下的对集公理保证： ZF3对集公理(axiom of pairing)： yz(z∈y(z=u∨z=v)) 对集公理的意思是： 存在集合y，其元素是集合u和集合v。直接根据ZF3，可将y写作y={z|z=u∨z=v}，再结合ZF1可知，这样以集合u和v为元素的集合是唯一的，因此可以用一个符号去表示集合y，我们采用{u,v}来表示这个集合y。 现在我们来看看利用ZF3和目前仅有的一个具体的集合能构造出哪些集合。根据ZF3，{,}是集合，再根据ZF1，有{,}={}； 有了{}之后，根据ZF3，可以进一步构造集合{,{}}、{{},}和{{},{}}，然后再根据ZF1，可以得到{{},{}}={{}}，{{},}={,{}}，一直这样下去，可以构造许多新的集合。在上述构造新集合的过程中我们发现，集合{u,v}和集合{v,u}是相等的，这是由ZF1保证的； 同时，ZF3并没有说集合u和v不能相等，当它们u=v时，根据ZF1，{u,v}={u}。我们将{u}这样只有一个元素的集合称为单元集(singleton)。 由于{u,v}={v,u}，所以集合{u,v}是无序对(unordered pair)。然而，我们希望通过集合u和v去构造一种带有次序的对象，这个新的对象除了含有u和v之外，还应该表示出u是该对象的第一个元素，v是该对象的第二个元素。我们将该对象记为〈u,v〉，希望它具有性质： 〈u,v〉=〈s,t〉当且仅当u=s并且v=t。显然，如果〈u,v〉具有了此性质，则当u≠v时，就有〈u,v〉≠〈v,u〉，可见此时u和v就具有了次序。当然，对象〈u,v〉得是一个集合。如果仅采用集合u和v去构造，而不需要别的集合时，可以采用如下的集合形式： 〈u,v〉={{u},{u,v}}(3.4.1) 应用ZF3，〈u,v〉是由集合{u}和集合{u,v}两个元素构成的，所以〈u,v〉是集合。下面我们来验证，式(3.4.1)确实具有我们所期望的性质： 〈u,v〉=〈s,t〉，当且仅当u=s并且v=t。 当u=s并且v=t时，根据式(3.4.1)的定义，显然〈u,v〉=〈s,t〉。反之，如果〈u,v〉=〈s,t〉，即{{u},{u,v}}={{s},{s,t}}； 如果u≠v，则{u,v}含有两个元素，进而一定有{u,v}={s,t}，s≠t，且{u}={s}，这样就得到了u=s并且v=t了； 如果u=v，则{{u},{u,v}}={{u}}为单元集，所以{{s},{s,t}}也一定为单元集，因而有s=t，即{{s},{s,t}}={{s}}，进而又有u=s，所以，u=v=s=t。综上所述，无论哪种情况，总有u=s并且v=t。 我们把对象〈u,v〉称为有序对(ordered pair)，并称u为有序对的第一元素，v为有序对的第二元素。当u=v时，有序对〈u,v〉=〈u,u〉={{u}}为一个单元集。在有序对的基础上，我们还可以进一步地对多个集合，构造出由这些集合所形成的有序多元组(ordered ntuples)： 〈u,v,w〉=〈〈u,v〉,w〉，〈u,v,w,s〉=〈〈u,v,w〉,s〉，…。 3.5并集公理 给定两个集合x、y，我们可以利用ZF3得到集合{x，y}，这是将集合x、y作为整体去构造新的集合。由于ZF中只有集合一种对象，所以，集合x、y的元素还是集合。自然地，应该也可以利用集合x、y的元素而非x、y本身去构造新的集合，而这是由并集公理保证的。 ZF4 并集公理(axiom of union)： yz(z∈yu(u∈x∧z∈u)) 并集公理的意思是： 对于集合x，存在集合y，其元素是集合x的元素的元素。直接根据ZF4，可将y写作y={z|u(u∈x∧z∈u)}，再根据ZF1可知，集合y是唯一的。我们引入符号∪x来表示集合y，即y=∪x，这相当于在ZF中引入了函数词“∪”。将集合∪x称为集合x的并集(union)。 应用对集公理，最多只能获得含有两个元素的集合，而应用并集公理，可以获得多于两个元素的集合。比如，∪{{{},},{{{}}}}={,{},{{}}}。 对于由x和y构成的集合{x,y}，如果对其应用ZF4，可知∪{x,y}是一个集合，而且该集合的元素是由集合x和y的元素构成。我们定义x∪y=∪{x,y}，并称x∪y为“x并y”，此时，根据ZF4可得x∪y={z|z∈x∨z∈y}。可以看出，高中所学的两个集合的并运算可以从应用ZF3和ZF4中直接得到。类似地，也可以定义x∪y∪z=∪{x,y,z}等。有些读者可能会问： 集合{x,y,z}怎么得到？对于{x,y,z}，可以通过应用ZF3和ZF4得到，即首先应用ZF3可以得到{x,y}和{z}={z,z}，然后再次应用ZF3得到{{x,y},{z}}，进而应用ZF4得到∪{{x,y},{z}}={x,y,z}。可以看出，形式化的公理方法使得我们对集合操作的每一步都很严谨，严格依赖于所给定的公理，虽然有时结果是简单直观的。 我们把x∪y看作关于集合x和y的一种“运算”。下面给出“交运算”和“差运算”的定义。 对于集合x，如果x≠，称集合x为非空集。对于非空集x，我们定义 ∩x={z|u(u∈x→z∈u)}(3.5.1) 注意： 在给定集合x的情况下，谓词公式u(u∈x→z∈u)中只有个体词变元z是自由的，即谓词公式u(u∈x→z∈u)可以看作关于个体词变元z的性质A(z)。根据上式，首先∩x是一个类； 其次，我们说∩x还是一个集合。因为x≠，所以u1∈x为真； 而u(u∈x→z∈u)为真，蕴含了u1∈x→z∈u1为真，再利用假言推理规则可得z∈u1为真，也就是说，u(u∈x→z∈u)为真蕴含了z∈u1为真。所以，应用ZF2分离公理，可得∩x是一个集合，我们称之为集合x的交集(intersection)。当集合x为空集时，由于蕴含式u∈x→z∈u的前件总是为真，所以个体词变元z可以取论域中的任意对象，也就是说，此时∩x为集合宇宙，这是没有什么意义的，因而，当x=时，我们说∩x没有定义。 直接根据式(3.5.1)，∩x的元素就是属于集合x的每一个元素的那些对象所组成，也就是集合x的所有元素的公共元素，比如，∩{{},{{},},{,{{}}}}={}。类似地，也可以直接定义两个集合或者多个集合的公共元素，即定义x∩y=∩{x,y}，并称x∩y为“x交y”，此时，根据式(3.5.1)可得x∩y={z∈x|z∈y}； 定义x∩y∩z=∩{x,y,z}； 等等。 至于两个集合的差运算，定义为 x－y={z∈x|zy}(3.5.2) 并称x－y为x与y的差集(difference)。 可以看出，集合的交和差由于都是原集合的子集，所以仅靠ZF2就可以定义出来。之所以放在这一节是为了将我们在高中所学的关于集合的交、并、差这三种运算放在一起引出。对于符号“∩”和“－”也可以认为是在ZF中引入了函数词，其中“－”可认为是二元函数词。 3.6幂集公理 直观地看，给定一个集合x，其部分元素所构成的对象是集合，也就是x的子集； 那么不同的部分元素会构成x的不同子集，所有这些不同子集也应该可以作为元素去构成一个集合。这种对于集合x，既不采用对集公理构成集合{x}，也不采用并集公理构成集合∪x，而是采用x的所有部分——子集去构造集合。这就需要新的公理来保证这样做会形成集合： ZF5 幂集公理(axiom of power set)： yz(z∈yzx) 幂集公理的意思是： 对于集合x，其所有的子集构成集合y。直接由ZF5，有y={z|zx}。再根据ZF1可知集合y是唯一的。我们引入符号P(x)表示集合y，即y=P(x)，并称其为集合x的幂集(power set)。比如，对于集合x={,{}}，其幂集P(x)={,{},{{}},{,{}}}。 当然，符号“P”也可以看作在ZF中引入了函数词。 3.7集合代数 根据前面几节里所定义的集合并、交、差运算，以及集合之间的关系，我们可以把集合的这些运算和关系类比“数”的运算和关系，得到关于集合运算和关系的一些基本性质。 根据前几节中xy的定义，再根据ZF1，如果xy并且yx，则x=y。集合x是集合y的子集，有时也称为x包含于y或者y包含x。如果xy并且x≠y，则称集合x为集合y的真子集(proper subset)，用xy表示。 当所讨论的集合都是某一个特定集合a的子集时，那么差集a－x也称为集合x关于集合a的补集或余集，记为xc。因此， xc=a－x={u|u∈a∧ux}(3.7.1) 如果两个集合x、y的交集为，称这两个集合x、y是不相交的或无交的。 关于集合并、交、补运算的基本规律如下。 第一组： x∩y=y∩x，x∪y=y∪x x∩y∩z=x∩(y∩z)，x∪y∪z=x∪(y∪z) 第二组： x∩(y∪z)=(x∩y)∪(x∩z)，x∪(y∩z)=(x∪y)∩(x∪z) x－(y∪z)=(x－y)∩(x－z)，x－(y∩z)=(x－y)∪(x－z) (x∪y)－z=(x－z)∪(y－z)，(x∩y)－z=(x－z)∩(y－z) (x－y)∩z=(x∩z)－(y∩z) 第三组： x∩x=x，x∪x=x x∩xc=，x∪xc=a x∩=，x∪=x x∩a=x，x∪a=a (xc)c=x 第四组： x－y=x∩yc x－y=x－x∩y=x∪y－y x∪y=(x－y)∪y=x∪(y－x) 关于包含关系的一些性质如下。 xx： 如果xy且yz，则xz x(x∪y)，y(x∪y)； (x∩y)x，(x∩y)y： 如果xu且yv，则(x∩y)(u∩v)，(x∪y)(u∪v) (x－y)x： xy，当且仅当，x－y= 有些读者或许已经发现了上面所列出的关于集合运算的表达式，看起来与第1章中的重言等价式“很像”，也就是将命题变元p、q、r视为集合x、y、z，逻辑连接词∨、∧、瘙綈视为∪、∩、(·)c。这种相似性并不是一种巧合，我们是采用ZF体系进行集合理论描述的，而ZF是一种谓词逻辑形式系统，自然ZF中的集合表示中所采用的都是谓词公式。比如，集合常用表示x={u|P(u)}中，采用了谓词公式P(u)，即集合x是由那些令P(u)为真的元素u所构成，当然，对象x={u|P(u)}作为集合是满足ZF公理要求的。自然地，集合的运算表示也可以由谓词逻辑表达，因而集合运算的表达就会看起来和形式逻辑有些“相似”。有了这种相似性，就可以采用形式逻辑中的重言等价式去证明关于集合的一些表达式。 【例3.7.1】证明： (y∪z)c=yc∩zc。 证明： 题目中的表达式实际上是第二组第二个公式，即当y、zx的“简化版”。我们采用第1章中的重言等价式进行证明。 (y∪z)c={u|u(y∪z)}根据补集的定义 ={u|瘙綈(u∈(y∪z))}根据谓词的定义 ={u|瘙綈((u∈y)∨(u∈z))}根据并集公理ZF4 ={u|瘙綈(u∈y)∧瘙綈(u∈z)}根据命题逻辑重言等价式中的德摩根律 ={u|(uy)∧(uz)}根据谓词的定义 ={u|(u∈yc)∧(u∈zc)}根据补集的定义 =yc∩zc根据∩运算的定义 ▇ 从例3.7.1中可以清晰地看出“集合运算”和“逻辑运算”之间的相似性。事实上，例3.7.1中的证明方法是掺杂着形式化的证明的，是一种“半形式化”的证明方法。当然，就如我们反复所强调的，形式化的证明往往比较繁杂，所以一般不会采用这种方法。 另外，本节所列出的关于集合运算和关系的这些性质中，有很多性质都是我们所熟悉的，即使遇到有些不熟悉的，也能直觉上理解它们。对于上面的这些规律，我们选几个证明一下。证明方法主要是利用ZF1来证明两个集合的相等。 【例3.7.2】证明： x－(y∩z)=(x－y)∪(x－z)。 证明： 任取u∈x－(y∩z)，则有u∈x且u(y∩z)。而u(y∩z)说明u不是同时属于y和z的，因而，uy或者uz； 所以就有u∈x，同时uy或者uz。这相当于u∈x且uy，或者u∈x且uz； 即u∈x－y，或者u∈x－z，进而u∈(x－y)∪(x－z)。这也就是说x－(y∩z)(x－y)∪(x－z)。类似地可证x－(y∩z)(x－y)∪(x－z)。 ▇ 需要指出，在例3.7.1中，u(y∩z)并不是uy且uz。uy且uz，也就是u既不属于y也不属于z，这种情况对应的是u(y∪z)。 除了使用ZF1去证明两个集合相等，也可以利用集合运算的恒等式去证明两个集合的相等。 【例3.7.3】证明： x∪(x∩y)=x。 证明： 利用上述集合运算规律第二组的分配率，有 x∪(x∩y)=(x∪x)∩(x∪y)=x∩(x∪y)=x 或者 x∪(x∩y)=(x∩a)∪(x∩y)=x∩(a∪y)=x∩a=x 其中，x、y都是某一个特定集合a的子集。 ▇ 【例3.7.4】证明： 若x∈u，(u－{x})∩v=u∩(v－{x})=u∩v－{x}。 证明： u∩(v－{x})=u∩v－u∩{x}=u∩v－{x} u∩v－{x}=u∩v－{x}∩u∩v=u∩v－{x}∩v=(u－{x})∩v ▇ 集合运算规律第四组中后两个恒等式可以由第一个恒等式x－y=x∩yc得到，此恒等式将集合的减法运算转化为交运算，非常有用。 习题 1. 证明： 是唯一的。 2. 已知x∈y，证明： x(∪y)。 3. 已知{{},{{}}}∈x，证明： ∈(∪x)，∈(∪(∪x))。 4. 已知xy，证明： (∪x)(∪y)。 5. 对于任意的集合x，证明： x=∪(P(x))。 6. 对于集合xy，证明： x∪y=y，x∩y=x。 7. 证明： x－(y∪z)=(x－y)∩(x－z)。 8. 证明： x－(y∩z)=(x－y)∪(x－z)。 9. 证明： (x∪y)－z=(x－z)∪(y－z)。 10. 证明： (x∩y)－z=(x－z)∩(y－z)。 11. 证明： P(x)∩P(y)=P(x∩y)。 12. 证明： ∪(x∪y)=(∪x)∪(∪y)。