离散数学：第三章 集合论

集合论集合论是现代数学的基础。集合论的起源可追溯到16世纪末，主要是对数集进行了卓有成效的研究。集合论实际发展是由19世纪70年代德国数学家康托尔(G.Cantor)在无穷序列和分析的有关课题的理论研究中创立的。康托尔对具有任意特性的无穷集合进行了深入的探讨，提出了关于基数、序数、超穷数和良序集等理论，奠定了集合论的深厚基础。因此，康托尔被誉为集合论的创始人。集合论但随着集合论的发展，以及它与数学哲学密切联系所作的讨论，本世纪初，出现了许多似是而非、自相矛盾的悖论，如著名的罗素(B.A.W.Russell)悖论，有力地冲击了或者说动摇了集合论的发展。理发师悖论：在萨维尔村，有一位理发师挂出一块招牌：“我只给村里所有那些不给自己理发的人理发。”。有人问他：“你给不给自己理发？”理发师顿时无言以对。由“自指”引发的悖论：有人说“我在说谎”。如果他在说谎，那么“我在说谎”就是一个谎。因此他说的是实话；但是如果这是实话，他又在说谎。矛盾不可避免。书目悖论：一个图书馆编撰了一本书名词典，它列出了这个图书馆里所有不列出自己书名的书。那么它列不列出自己的书名呢？这个悖论与理发师悖论基本一致。由此，激发许多数学家哲学家为克服这些矛盾建立了各种公理化集合论体系，其中尤以本世纪初、中期的ZFS(E.Zermelo-A.Fraenkel-T.Skolem)和NBG(VonNeumann-P.Bernays-K.Gödel)公理化体系最为流行。到20世纪60年代，美国数学家L.A.Zadeh

提出了Fuzzy集理论，以及20世纪80年代波兰数学家Z.Pawlak发表了Rough集理论，这两种理论区别以往的集合论，是一种新的模糊集理论，受到了学术界的重视和青睐。集合论在计算机科学、人工智能领域、逻辑学及语言学等方面都有着重要的应用。对从事计算机科学的工作者来说，集合论是不可缺少的理论知识，熟悉和掌握它是十分必要的。第三章集合论的公理系统

近百年来，集合论按直观朴素方法和公理化方法都有很大发展，特别是公理化集合论系统的发展已被公认为近代数学的最重大成果之一。以有限集合为背景来直观朴素地阐述集合理论，中学课程中已做了通俗介绍，人们称之为“孩子们的集合论”，而且这种理论会出现似是而非的悖论，导致数学基础的危机。我们将按ZFS公理化的方法去展开，以达到用有效的方法解决困难的目的，并给出一个表述简洁精确、论证严谨有序、内容协调丰富的科学体系。外延公理：若两个集合中各个元素都相同，则它们相等。抽象公理：任给一个性质，都有一个满足该性质的客体所组成的集合。选择公理：每个集合都有一个选择函数。即对任一非空集合A，都有一个选择函数F，dm(F)=P(A)-{Φ},

且对每个B∈dm(F),使F(B)∈B3.1公理导出和基本概念一、罗素悖论

剖析集合论创始人康托尔集合论的许多证明可知，几乎他所证明的一切定理均能从三个公理得出。这三个公理是：1901年英国哲学家和数学家罗素(BertrandRussell)发现：“由具有不为自身的成员这一性质的所有客体组成的集合”这就是著名的罗素悖论。

引进一个表示属于关系的二元谓词∈(x,y),或者记为x∈y.再使用已熟悉的数理逻辑符号，则抽象公理可以表示为：

(y)(x)(x∈y

(x))（1）其中(x)是以x为自由变元且不以y为自由变元的公式。

为了得到罗素悖论，取(x)为“x不为x的成员”，即(x)=┐(x∈x).于是，得到抽象公理的一个特例：

(y)(x)(x∈y

┐(x∈x))（2）在(2)中取x=y，可得：

(y)(y∈y

┐(y∈y))

（3）而(3)等价于(y∈y)┐(y∈y)。即导出矛盾。1908年德国数学家策墨勒(E.Zermelo)提出了“子集公理”，也称为“分出公理”:

对任给一个集合z和集合的每一种性质φ，存在一个集合y，它的成员恰是z中那些具有性质φ的成员。它允许从给定集合中分出满足某种性质的客体并恰由这些客体组成一个新集合。对于(1)(y)(x)(x∈y

(x))，子集公理的精确形式表示为：

(y)(x)(x∈y

x∈z

(x))（4）其中，y不为(x)的自由变元。

由(1)到(4)的改变看来是微小的，然而却十分有效。

(1)无条件断言集合的存在，而(4)完全是有条件的，这个条件称为入集条件。即首先要给出集合z，然后才能断言子集y的存在。可见，子集公理能避免悖论，使公理化集合论得以存在和发展。

(y)(x)(x∈y

(x))（1）

(y)(x)(x∈y

x∈z

(x))（4）二、符号和基本概念

常元符号：它们是隶属关系符∈，空集符，相等符=。

变元符号：A，B，C，…，R，S，f，g，…为集合变元

而x，y，z，…，为以集合或个体为值的一般变元。有时还标出足码或肩码。

数理逻辑符号：联结词，量词以及标点符。

元语言符号：它们是永真蕴涵符，永真等价符，定义符：=。

集合论和其它学科一样，也有自己的目标语言，该语言的符号可分为三类：常元符、变元符和数理符号。定义3.1.1

形如(vw)或(v=w)的表达式，称为原始原子公式。定义3.1.2

原始公式归纳定义为：①每个原始原子公式是原始公式；②若P为原始公式，则(┐P)也为原始公式；③若P和Q为原始公式，则(P∧Q)、(P∨Q)、(P→Q)和(PQ)也为原始公式；④若P为原始公式，v为变元，则(v)(P)、(v)(P)和(!v)(P)也都是原始公式；⑤只有由①到④得到的表达式才是原始公式。

根据三类符号的结构又分别定义为原始原子公式和原始公式。定义3.1.3

xy：=┐(x∈y)

这里“x

y”表示“x不属于y”或“x属于y”为假。同样，“x≠x”表示“┐(x=x)”定义3.1.4

y为集合：=(x)(x∈y∨y=)

该定义与直观想法是一致的，一个集合或是具有成员的客体或是空集。三、递归定义集合①给出初始的一些元素。②给出用来从已知属于集合的元素构造集合的其他元素的规则。③只有有限次地使用①和②生成的那些元素才属于这个集合。下面给出一种具体的定义集合方法，称为递归定义集合，它在数学和计算机科学中被广泛地使用，其定义步骤如下：例3.1.1字符串集合的递归定义。字符表∑上的字符串集合∑*递归定义成：①λ∈∑*，其中λ

是不包含任何字符的空串；②若ω∈∑*且

x∈∑*时，则ωx∈∑*。③有限次地使用①和②生成的元素才属于∑*。外延公理：具有相同各元素的集合是相等的。

形式地表示为：

(x)(x∈A

x∈B)A=B

3.2外延公理与子集公理外延公理表明：①一个集合完全由它所含有的成员所确定，而与这些成员的来由、物理意义、数学表示对象无关；②两个集合相等这种概念的存在性，若A，B两集合所含的成员完全一样，则两集合A，B相等，写成A=B。所以两个集合相等概念是存在的；③所有相同集合的惟一性，若A，B和C是三个集合，A=B，A=C，则外延公理又同时肯定B=C，也就是和A集合相等的集合的惟一性。

在有了集合相等概念的存在性与惟一性以后，便可在公理的基础上，给出两个集合相等的定义。定义3.2.1

若A，B是任何两个集合，当且仅当A，B二集合恰有相同的各成员时，则称集合A，B是相等的，记为A=B。也可形式地表为：

A=B

(x)(x∈A

x∈B)子集公理模式：

对于任给一个集合A和集合的每一种性质φ，存在一个集合B，其成员恰是A中那些具有性质φ的成员。可形式地表成：

(B)(x)(x∈B

x∈A∧φ(x))其中，B不可在φ中出现。

该公理称为模式，是因为它同时肯定了无穷多个公理，每一个公理对应某一公式以及变元A，B和x。子集公理模式表明：

①确定A和性质φ后，存在一个集合B，它使属于B

的成员皆属于A且具有性质φ（子集存在性）；

②再从外延公理可知，这样确定的一个子集B是

唯一的（子集唯一性）。定义3.2.2

B集合是

A集合的一个子集当且仅当B的每个成员也是A的一个成员。若用符号BA

表示B是A的一个子集，则该定义可形式地表示为：BA：=(x)(x∈B

→

x∈A

)

B是A的真子集，记作BA，其形式定义为：

BA:=BA∧B≠AB是A的子集(或真子集)也称B包含(或真包含)于A，或者A包含(或真包含)B。这时A，B二集合就构成了一种关系，即包含(或真包含)关系。定理3.2.1

x。该定理表明：空集是个没有任何成员的集合，一无所有。证明：取

φ(x)为x≠x,A=，由子集公理得

(B)(x)(x∈B

(x∈∧x≠x))（1）假设某x在B中，则由(1)知，x≠x，这是矛盾的。即(x∈∧x≠x)为假,

所以x∈B为假,故有(x)(xB)

。再根据定义3.1.4：y为集合：=(x)(x∈y∨y=)可知，B=。因此，

(x)(x)

，于是x。0:=，1:={}，2:={,{}}，3:={,{},{,{}}},…,1924年匈牙利-美国数学家冯·诺依曼(JohnvonNeumann)依据自然数产生抽象的数的规律，即次序和个数两个特性，使用空集给出自然数的集合表示。这种集合表示是：也就是：0:=，

1:={0}，

2:={0，1}，

3:={0，1，2}，…不难看出，①自然数的次序性，可传性：

0∈1∈2∈3…，而且0∈2，0∈3，…，1∈3，…。这即是“属于”的可传性；其由来是这种表示法具有包含关系：

0123…，而包含关系可以证明是可传递的。②自然数的“基数”：

0没有元，1有一个元，2有二个元，3有三个元，…。定理3.2.2(x)(xA)A=证明：充分性：若A=，由定理3.2.1知，xA。

必要性：

假设对任意x,xA，则A中无任何元素，由定义3.1.4y为集合：=(x)(x∈y∨y=),

可知，A=。

集合的包含与真包含关系的定理有：定理3.2.3①AA；

②AB∧BAA=B；③AB∧BCAC证明:②AB∧BA(x)(xAxB)∧(x)(xBxA)(x)(

(xAxB)∧(xBxA))

(分配律)(x)(xA↔xB)A=B本定理表明包含关系是自反的，反对称的和可传递的。具有这三种性质的关系称为偏序关系。因此，包含关系是个偏序关系。定理3.2.4真子集的性质①┐(AA)

(非自反的)②AB┐(BA)(非对称的)③AB∧BCAC

(传递的)证明:②AB

AB

∧A≠B(x)(xAxB)∧(x)(xB∧xA)

(x)(xAxB)(化简式)(x)(xAxB)∨(x)(xB∨xA)(附加式)┐(

(x)(xA∧xB)

∧(x)(xB

∧xA))┐(

(x)

(xBxA)∧(x)(xA

∧xB))┐(BA∧B≠A)┐(BA)下面给出一个有用的结论：

在ZFS集合论中不存在全总集。定理3.2.5┐(B)(x)(x∈B)证明：(反证法)假设(B)(x)(x∈B)，即B为全集，一切客体都属于它。于是在子集公理中，取A为全集B，便有：

(C)(x)(x∈C

x∈B∧(x))由于B为全集，故x∈B为永真，因此得到：

(C)(x)(x∈C

(x))这便是抽象公理，从而将导出罗素悖论。故全集是不存在,即：┐(B)(x)(x∈B)例3.2.1

。例3.2.2{}∈{{}}，∈{}，但{{}}。例3.2.3

令j是张中，C是中国，U是联合国，则j∈C∈U，但jU。集合的元素可以是一个集合例如：A={a,b,c,D},而D={0,1}。3.3集合的表示法一、枚举法（列举法）把集合中的元素一一列举出来，成员之间用逗号分隔，然后用花括号括起来表示集合。例如“所有小于5的正整数”这个集合的元素为1,2,3,4,除这4个元素外,再没有别的元素。如果把这个集合命名为A,就可记为A={1,2,3,4}

在能清楚表示集合成员的情况下可使用省略号,例如,从1到50的整数集合可记为{1,2,3,…,50},偶数集合可记为{…,-4,-2,0,2,4,…}。

表征集合S中成员多少的量，称为集合S的基数，记为|S|，若|S|=n，其中n∈N，称S为有限集合。

二、抽象法（描述法）用谓词描述出集合元素的公共特征来表示这个集合。使用记号：{x|φ(x)}来表示具有性质φ(x)的一切客体所组成的集合S，其中φ(x)称为入集条件，表示x∈S

当且仅当φ(x)是真。例如,上述各例可分别写成A={a|a∈I∧0＜a∧a＜5},{a|a∈I∧1≤a≤50}这里I表示整数集合。

{x|1≤x≤6∧x为整数}即为{1，2，3，4，5，6}。定义模式3.3.1

{x|φ(x)}=y

(

(x)(x∈yφ(x))∧y

为集合)

∨(y=∧┐(B)(x)(x∈Bφ(x))

)

由φ(x)的不同可得出不同的集合。于是给出了定义模式和定理模式。若不存在满足性质φ(x)的客体所组成的非空集合，则定义中后析取项便令：{x|φ(x)}=。定理模式3.3.1

y∈{x|φ(x)}

φ(y)证明：如果y∈{x|φ(x)}，则{x|φ(x)}≠,

即{x|φ(x)}=A为集合。由定义模式3.3.1{x|φ(x)}=A

((x)(x∈Aφ(x))∧A为集合)可知，

(x)(x∈Aφ(x))y∈Aφ(y)故y∈{x|φ(x)}

φ(y)

定理3.3.2①A={x|x∈A}；

②={x|x≠x}证明：②假设存在一个y,使得y∈{x

|x≠x}为真。由定理模式3.3.1y∈{x|x≠x}

φ(y)知，y≠y，这是矛盾的。即对任意y，

(y)(y

{x|x≠x})。根据定理3.2.2(x)(xA)A=,可得：

={x|x≠x}。定义模式3.3.2{(x1,x2,…,xn)|φ(x1,x2,

…，xn)}={y|(x1)(x2)…(xn)(y=(x1,x2,…,xn)∧φ(x1,x2,…,xn))}，其中(x1,x2,…,xn)为项，而x1,x2,…,xn为自由变元。定理模式3.3.3

(φ(x)ψ(x)){x|φ(x)}={x|ψ(x)}下面定理模式表明：若两入集条件(即性质)是永真等价的，则它们外延必相等。证明：令y1={x|φ(x)},y2={x|ψ(x)}.

若┐(B)(x)(x∈B

(x))，则由定义模式3.3.1知，y1=。由本定理模式假设可有┐(B)(x)(x∈Bψ(x))，则y2=。否则，依据定义模式3.3.1，便得：

y

∈{x|φ(x)}φ(y)，y

∈{x|ψ(x)}ψ(y)

由本定理模式假设φ(x)ψ(x)知：

y

∈{x|φ(x)}

y

∈{x|ψ(x)}

利用定义3.2.1A=B

(x)(x∈A

x∈B)，可得：

{x|φ(x)}={x|ψ(x)}三、集合的计算机表示

首先将给定集合S中元素任意规定一种次序，例如：

a1，a2，…，an。于是，可以用长度为n的位串表示S的子集A：若ai∈A，则位串第i位是1；若aiA，则位串中第i位是0.例3.3.1

设S={1，2，3，4，5，6，7，8，9，10}，且S中的元素从小到大排序，即ai=i。试问表示S中所有奇数的子集SO，所有表示偶数的子集SE以及不超过6的整数的子集S6的位串是什么？SO：1010101010SE：0101010101S6：11111100003.4偶集公理与联集公理

偶集公理：对于给定的任何两个集合A，B，存在一个集合C，其成员恰是A和B。形式地表为：

(C)(x)(x∈C

(x=A∨x

=B))定义3.4.1

集合{A，B}是一个偶集即二元集，当且仅当A和B是集合。本定义可形式地表为：

{A，B}=C(x)(x∈C

x=A∨x

=B)由同一个集合A给出的偶集{A，A}，按外延公理它是{A}。从而可定义：

{A}：={A，A}它是由A构成的单元集。联集公理：对于任何一个集合A，存在一个集合C，C的成员恰是A的成员的成员。本公理形式地表为：

(C)(x)(

x∈C

(B)(B∈A∧x∈B)

)定义3.4.2

C集合是A集合的一个联集，当且仅当

(x)(x∈C

(B)(B∈A∧x∈B))。

C集合常用并运算符号∪表为：C=∪A。

于是，集合A的联集按抽象法又可给出：定义3.4.3

∪A：={x|(B)(B∈A∧x∈B)}例3.4.1

令A={{1，2}，{3}，4}，B={4，{5}，{5，6}}

则∪A={1，2，3}，∪B={5，6}

两个集合A和B的初等并运算，可定义为以A，B为成员的偶集{A，B}的联集，即：

A∪B：=∪{A，B}它说明：(A)(B)(C)(x)(x∈C

x∈A∨x∈B)，所以又可给出集合A和集合B

的并集定义如下：定义3.4.4

A∪B：={x|x∈A∨x∈B

}有了偶集与并集的定义，对于任何集合A，B，C和D，容易构成三元集、四元集如下：

{A，B，C}：={A，B}∪{C}{A，B，C，D}：={A，B}∪{C，D}集合的交定义3.4.5

∩A：={x|(B)(B∈A→x∈B)}

∪A：={x|(B)(B∈A∧x∈B)}定义3.4.6

A∩B：={x|x∈A∧x∈B

}

A∪B：={x|x∈A∨x∈B

}应用子集公理给出的子集来定义两个集合的差，只要取φ(x)为xB，便可有：

A-B：={x|x∈A∧xB

}两个集合A、B的差A-B，也称为B相对于A的补。集合的差例3.4.1

令A={{1，2}，{3}，4}，B={4，{5}，{5，6}}

则∪A={1，2，3}，∪B={5，6}∩A=，

∩B={5}，

A∪B={{1，2}，{3}，4，{5}，{5，6}}A∩B={4}

A-B={{1，2}，{3}}。

定理3.4.1

①x∈∪A

(B)(B∈A∧x∈B)②x∈A∪B

x∈A∨x∈B

③∪(A∪B)=(∪A)∪(∪B)

④A∈BA∪B定理3.4.1

①x∈∪A(B)(B∈A∧x∈B)证明：①在定义模式3.3.1{x|φ(x)}=y

((x)(x∈yφ(x))∧y为集合)∨(y=∧┐(B)(x)(x∈Bφ(x)))令(x)

为(B)(B∈A∧x∈B)，由联集公理可得：

{x|φ(x)}={

x|(B)(B∈A∧x∈B)}=y

(x)(x∈y↔(B)(B∈A∧x∈B)∧y为集合)又知

∪A=｛x|(B)(B∈A∧x∈B)｝=y

，因此有，

(x)(x∈∪A

↔(B)(B∈A∧x∈B))（即为永真式）,即x∈∪A

(B)(B∈A∧x∈B)

。定理3.4.2①A∪B=B∪A②A∪(B∪C)=(A∪B)∪C③AC∧BCA∪BC证明：③AC∧BC

(x)(x∈A→x∈C)∧(x)(x∈B→x∈C)

(x)((x∈A→x∈C)∧(x∈B→x∈C)

)(x)((x∈A∨x∈B)→x∈C

)(x)(x∈(A∪B)→x∈C

)A∪BC定理3.4.3①x∈∩A(B)(B∈A→x∈B)∧(B)(B∈A)证明：①

必要性：假设x∈∩A,则∩A≠。根据定义3.4.5∩A：={x|(B)(B∈A→x∈B)}和定义模式3.3.1可推出：

x∈∩A↔(B)(B∈A→x∈B)(1)

现在假设：┐(B)(B∈A)(2)

于是，┐(B)(B∈A)

(B)(BA)

由定理3.2.2知(B)(BA)A=。于是，∩A=，这与假设x∈∩A矛盾。因此假设(2)不成立，即有(B)(B∈A)。②∩(A∪B)=(∩A)∩(∩B)③(A∪B)∩C=(A∩C)∪(B∩C)④(A∩B)∪C=(A∪C)∩(B∪C)证明：①充分性：若(B)(B∈A→x∈B)∧(B)(B∈A)成立,根据假设，有B*∈A。由此应用子集公理可得：

(C)(x)(x∈C↔x∈B*∧(B)(B∈A→x∈B)

)(3)因此，由B*∈A及假设中的(B)(B∈A→x∈B)，可推出x∈B*

成立由此再根据(3)可推得：

(C)(x)(x∈C↔(B)(B∈A→x∈B))(4)故由(4)，∩A的定义∩A={x|(B)(B∈A→x∈B)}及定义模式3.3.1推得x∈∩A。定理3.4.4①x∈A-Bx∈A∧xB

②(A∪B)-B=A-B

③A-(B∪C)=(A-B)∩(A-C)④A-(B∩C)=(A-B)∪(A-C)

证明：②令x为任意元，则

x∈(A∪B)-Bx∈(A∪B)∧xB(x∈A∨x∈B)∧xB(x∈A∧xB)∨(x∈B∧xB)(x∈A∧xB)x∈A-B

所以，(A∪B)-B=A-B。③证明：令x为任意元，

x∈A-(B∪C)

x∈A∧┐(x∈B∨x∈C)

x∈A∧xB∧xC(x∈A∧xB)∧(x∈A∧xC)x∈(A-B)∧x∈(A-C)x∈(A-B)∩(A-C)

所以，A-(B∪C)=(A-B)∩(A-C)3.5极小元与正则公理一个集合S可以是另一个集合S1的成员，特别是S1={S}时，总有S∈{S},亦即S∈S1.现在问：是否存在一个集合S，使得S∈S?定义3.5.1

对于任何的集合S1与S2，当S1∈S2且S1∩S2=时，则称S1为S2的一个极小元。即:极小元S1里的成员不能成为集合S2的成员。例3.5.1

令S1={1}，S2={{1}，2}，因为S1∈S2且S1∩S2=，则有S1是S2的极小元。例3.5.2

令S={1，{1}，{2}}，则

{2}是S的极小元，而{1}不是S的极小元，因为{1}∩S={1}≠。例3.5.3

令S={{1}，{2}}，则{1}和{2}都是S的极小元。

可见每个集合的极小元并不都是惟一的。正则公理:

每个不空的集合，都有一极小元。

形式地可表为：

A≠(x)(x∈A∧x∩A=)。

正则公理也称为基础公理或限制公理。是否每个集合都有极小元呢?是的，1925年冯·诺伊曼(VonNeumann)提出的正则公理给予了满意答复。定理3.5.1

对于任意集合S，有SS。证明：反证法，假设有S

使得S

∈S.由构造单元集合{S}，显然S

∈{S}，即{S}不空。由正则公理知，{S}有一极小元。然而{S}只有元S，故S

∩{S}=。但是，由假设S

∈S，因此S与{S}有公共元S，即S

∩{S}≠，这是矛盾的。所以对任意集合S，都有SS。定理3.5.2对任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)。证明：设S={S1,S2}，

则S1和

S2均为S的极小元

。假设(S1∈S2∧S2∈S1)，则有

S1∈(S2∩S)且S2∈(S1∩S)。于是，S2∩S≠，S1∩S≠，这与正则公理矛盾。因此，对于任意集合S1和S2，都有┐(S1∈S2∧S2∈S1)。定理3.5.3对任意自然数n和任意集合S1，S2，…，Sn，都有┐(S1∈S2∧S2∈S3∧…∧Sn-1∈Sn∧Sn∈S1)3.6无穷公理定义3.6.1

对任意集合S，其后继记为S+，定义为S∪{S}，即

S+：=S∪{S}称S为S+的前驱，S+为S的后继，并称“+”为后继运算。定义3.6.20:=，1:=0+，2:=1+，一般地，n+1:=n+。显然，自然数集合N就是用后继定义的无穷集合。由上面定义可知，对于n∈N，有①n

∈

n+；②n

n+。由此可见，0，1，2，3，…不单是书写自然数符号，而且也是用空集与后继表示的各个集合。定义3.6.3

若集合A有性质：

∈A∧(x)(x∈A→x+∈A)则称A是一个归纳集。换句话说，若A是在后继运算“+”下封闭且包含有，则A是一个归纳集。

由本定义可知，归纳集是个无穷集合，其存在性由下面公理提供了保证。无穷公理：

有一个归纳集的存在。形式可表为：

(A)(∈A∧(x)(x∈A

→x+∈A))若用Ind(A)表示A是一个归纳集，则无穷公理又可表成：(A)(Ind(A))。下面证明最小归纳集的存在性。

定理3.6.1(A)(Ind(A)∧(B)(Ind(B)→AB))证明：根据无穷公理，确有某归纳集C的存在。现在取A是所有归纳集的交，它是C的一个子集，所以它是一个集合，故可得：

A：=∩｛B|B

C∧

Ind(B)｝。

(1)先证A是一个归纳集。因为若Ind(B)，则∈B，A是所有归纳集的交，故∈A；又若x∈A，则对于每个归纳集BC，x∈B。因此，对所有的B

有x+∈B，这就表明x+∈A。所以A是一个归纳集。(2)再证A是一个最小归纳集。令Ind(D),则容易看出Ind(C∩D),所以A

C∩D

D，

A是被任何归纳集D所包含的一个归纳集，称该集合为最小集合，故A是一个最小归纳集。定义3.6.4

称最小归纳集

ω：={x|(B)(Ind(B)→x∈B)}是自然数集合，ω的元称为自然数。依据定义3.6.2可知0，1，2，…都是自然数，并且从自然数集ω

的最小归纳集性质，得到关于一般数学归纳法的根据。关于ω的归纳原理：ω的任何一个归纳子集与ω重合。

从外延公理知，这个最小归纳集是唯一的，并称它是一个自然数集合。自然数集合常用N表示。3.7幂集公理

给定一个集合的所有子集，这个集合称为给定集合的幂集。自然想到：是否对一切集合，其幂集都存在呢？这需要由公理给以保证，为此引进一条新的公理。本公理可形式地表为：

(B)(x)(x∈B

(y)(y∈x

→y∈A))或者用包含关系表示成：

(B)(x)(x∈B

xA)幂集公理：对于任何一个集合A，存在一个集合B，集合B的元恰是A的各个子集。定义3.7.1

集合B是集合A的一个幂集，当且仅当

(x)(x∈B

xA)。

由外延公理知B是惟一的，并称B是A的幂集。因此有A的幂集B记作Pw(A)，便有

Pw(A)：={x|x

A}

为方便不引起混淆情况，常将A的幂集记作P(A)。

关于幂集的讨论，从有限集合的幂集开始。定义3.7.2

对于一个集合A，如果存在自然数n，使得A恰有n个元，则称A是有限的。定理3.7.1

若A

是一个有限集合且BA，令

C=A∪{B}，则C的所有子集的个数恰是A的所有子集的个数的二倍。例子P({1，2})={，{1}，{2}，{1，2}}；P({1，2，3})={，{1}，{2}，{3}，

{1，2}，{1，3}，{2，3}，{1，2，3}}；可见P({1，2，3})的子集个数是P{1，2}的子集元素个数的二倍。定理3.7.2

对于自然数n，如果集合A恰有n个元，则P(A)恰有2n个元。因此有的教材将幂集记为2A

。定理3.7.3

①B∈P(A)BA②A∈P(A)

③ABP(A)P(B)

④P(A-B)(P(A)-P(B))∪{}

⑤P(A)∈P(B)

A∈B③ABP(A)P(B)证明：必要性：若AB，对任意C∈P(A)，由幂集定义可知CA，又因为AB所以有CB，从而C∈P(B),所以P(A)P(B)。充分性：若P(A)P(B)，

对任意x∈A，有{x}∈P(A)。又因为P(A)P(B)，可得{x}∈P(B)。所以x∈B，即AB。

④

P(A-B)(P(A)-P(B))∪{}证明：任意C∈P(A-B)，由幂集定义可知

CA-B，所以CA，C∈P(A)。

若C=，则C∈{}，从而C∈(P(A)-P(B))∪{}；

若C≠，则┐(CB)，即CP(B),

所以C∈P(A)-P(B),

从而C∈(P(A)-P(B))∪{}

。所以P(A-B)(P(A)-P(B))∪{}

。⑤

P(A)∈P(B)

A∈B证明：由幂集定义可知A∈P(A)，

又因为P(A)∈P(B)，则P(A)B,

所以A∈B。定义3.7.3

给定集合A，对于任何集合x和y，若x∈y

且y∈A，则有x∈A，