離散數(shù)學(xué)：第三章 集合論

集合論集合論是現(xiàn)代數(shù)學(xué)的基礎(chǔ)。集合論的起源可追溯到16世紀末，主要是對數(shù)集進行了卓有成效的研究。集合論實際發(fā)展是由19世紀70年代德國數(shù)學(xué)家康托爾(G.Cantor)在無窮序列和分析的有關(guān)課題的理論研究中創(chuàng)立的?？低袪枌哂腥我馓匦缘臒o窮集合進行了深入的探討，提出了關(guān)于基數(shù)、序數(shù)、超窮數(shù)和良序集等理論，奠定了集合論的深厚基礎(chǔ)。因此，康托爾被譽為集合論的創(chuàng)始人。集合論但隨著集合論的發(fā)展，以及它與數(shù)學(xué)哲學(xué)密切聯(lián)系所作的討論，本世紀初，出現(xiàn)了許多似是而非、自相矛盾的悖論，如著名的羅素(B.A.W.Russell)悖論，有力地沖擊了或者說動搖了集合論的發(fā)展。理發(fā)師悖論：在薩維爾村，有一位理發(fā)師掛出一塊招牌：“我只給村里所有那些不給自己理發(fā)的人理發(fā)?！薄Ｓ腥藛査骸澳憬o不給自己理發(fā)？”理發(fā)師頓時無言以對。由“自指”引發(fā)的悖論：有人說“我在說謊”。如果他在說謊，那么“我在說謊”就是一個謊。因此他說的是實話；但是如果這是實話，他又在說謊。矛盾不可避免。書目悖論：一個圖書館編撰了一本書名詞典，它列出了這個圖書館里所有不列出自己書名的書。那么它列不列出自己的書名呢？這個悖論與理發(fā)師悖論基本一致。由此，激發(fā)許多數(shù)學(xué)家哲學(xué)家為克服這些矛盾建立了各種公理化集合論體系，其中尤以本世紀初、中期的ZFS(E.Zermelo-A.Fraenkel-T.Skolem)和NBG(VonNeumann-P.Bernays-K.G?del)公理化體系最為流行。到20世紀60年代，美國數(shù)學(xué)家L.A.Zadeh

提出了Fuzzy集理論，以及20世紀80年代波蘭數(shù)學(xué)家Z.Pawlak發(fā)表了Rough集理論，這兩種理論區(qū)別以往的集合論，是一種新的模糊集理論，受到了學(xué)術(shù)界的重視和青睞。集合論在計算機科學(xué)、人工智能領(lǐng)域、邏輯學(xué)及語言學(xué)等方面都有著重要的應(yīng)用。對從事計算機科學(xué)的工作者來說，集合論是不可缺少的理論知識，熟悉和掌握它是十分必要的。第三章集合論的公理系統(tǒng)

近百年來，集合論按直觀樸素方法和公理化方法都有很大發(fā)展，特別是公理化集合論系統(tǒng)的發(fā)展已被公認為近代數(shù)學(xué)的最重大成果之一。以有限集合為背景來直觀樸素地闡述集合理論，中學(xué)課程中已做了通俗介紹，人們稱之為“孩子們的集合論”，而且這種理論會出現(xiàn)似是而非的悖論，導(dǎo)致數(shù)學(xué)基礎(chǔ)的危機。我們將按ZFS公理化的方法去展開，以達到用有效的方法解決困難的目的，并給出一個表述簡潔精確、論證嚴謹有序、內(nèi)容協(xié)調(diào)豐富的科學(xué)體系。外延公理：若兩個集合中各個元素都相同，則它們相等。抽象公理：任給一個性質(zhì)，都有一個滿足該性質(zhì)的客體所組成的集合。選擇公理：每個集合都有一個選擇函數(shù)。即對任一非空集合A，都有一個選擇函數(shù)F，dm(F)=P(A)-{Φ},

且對每個B∈dm(F),使F(B)∈B3.1公理導(dǎo)出和基本概念一、羅素悖論

剖析集合論創(chuàng)始人康托爾集合論的許多證明可知，幾乎他所證明的一切定理均能從三個公理得出。這三個公理是：1901年英國哲學(xué)家和數(shù)學(xué)家羅素(BertrandRussell)發(fā)現(xiàn)：“由具有不為自身的成員這一性質(zhì)的所有客體組成的集合”這就是著名的羅素悖論。

引進一個表示屬于關(guān)系的二元謂詞∈(x,y),或者記為x∈y.再使用已熟悉的數(shù)理邏輯符號，則抽象公理可以表示為：

(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)。即導(dǎo)出矛盾。1908年德國數(shù)學(xué)家策墨勒(E.Zermelo)提出了“子集公理”，也稱為“分出公理”:

對任給一個集合z和集合的每一種性質(zhì)φ，存在一個集合y，它的成員恰是z中那些具有性質(zhì)φ的成員。它允許從給定集合中分出滿足某種性質(zhì)的客體并恰由這些客體組成一個新集合。對于(1)(y)(x)(x∈y

(x))，子集公理的精確形式表示為：

(y)(x)(x∈y

x∈z

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

由(1)到(4)的改變看來是微小的，然而卻十分有效。

(1)無條件斷言集合的存在，而(4)完全是有條件的，這個條件稱為入集條件。即首先要給出集合z，然后才能斷言子集y的存在?？梢?，子集公理能避免悖論，使公理化集合論得以存在和發(fā)展。

(y)(x)(x∈y

(x))（1）

(y)(x)(x∈y

x∈z

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

常元符號：它們是隸屬關(guān)系符∈，空集符，相等符=。

變元符號：A，B，C，…，R，S，f，g，…為集合變元

而x，y，z，…，為以集合或個體為值的一般變元。有時還標出足碼或肩碼。

數(shù)理邏輯符號：聯(lián)結(jié)詞，量詞以及標點符。

元語言符號：它們是永真蘊涵符，永真等價符，定義符：=。

集合論和其它學(xué)科一樣，也有自己的目標語言，該語言的符號可分為三類：常元符、變元符和數(shù)理符號。定義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)也都是原始公式；⑤只有由①到④得到的表達式才是原始公式。

根據(jù)三類符號的結(jié)構(gòu)又分別定義為原始原子公式和原始公式。定義3.1.3

xy：=┐(x∈y)

這里“x

y”表示“x不屬于y”或“x屬于y”為假。同樣，“x≠x”表示“┐(x=x)”定義3.1.4

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

該定義與直觀想法是一致的，一個集合或是具有成員的客體或是空集。三、遞歸定義集合①給出初始的一些元素。②給出用來從已知屬于集合的元素構(gòu)造集合的其他元素的規(guī)則。③只有有限次地使用①和②生成的那些元素才屬于這個集合。下面給出一種具體的定義集合方法，稱為遞歸定義集合，它在數(shù)學(xué)和計算機科學(xué)中被廣泛地使用，其定義步驟如下：例3.1.1字符串集合的遞歸定義。字符表∑上的字符串集合∑*遞歸定義成：①λ∈∑*，其中λ

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

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

形式地表示為：

(x)(x∈A

x∈B)A=B

3.2外延公理與子集公理外延公理表明：①一個集合完全由它所含有的成員所確定，而與這些成員的來由、物理意義、數(shù)學(xué)表示對象無關(guān)；②兩個集合相等這種概念的存在性，若A，B兩集合所含的成員完全一樣，則兩集合A，B相等，寫成A=B。所以兩個集合相等概念是存在的；③所有相同集合的惟一性，若A，B和C是三個集合，A=B，A=C，則外延公理又同時肯定B=C，也就是和A集合相等的集合的惟一性。

在有了集合相等概念的存在性與惟一性以后，便可在公理的基礎(chǔ)上，給出兩個集合相等的定義。定義3.2.1

若A，B是任何兩個集合，當且僅當A，B二集合恰有相同的各成員時，則稱集合A，B是相等的，記為A=B。也可形式地表為：

A=B

(x)(x∈A

x∈B)子集公理模式：

對于任給一個集合A和集合的每一種性質(zhì)φ，存在一個集合B，其成員恰是A中那些具有性質(zhì)φ的成員?？尚问降乇沓桑?/p>

(B)(x)(x∈B

x∈A∧φ(x))其中，B不可在φ中出現(xiàn)。

該公理稱為模式，是因為它同時肯定了無窮多個公理，每一個公理對應(yīng)某一公式以及變元A，B和x。子集公理模式表明：

①確定A和性質(zhì)φ后，存在一個集合B，它使屬于B

的成員皆屬于A且具有性質(zhì)φ（子集存在性）；

②再從外延公理可知，這樣確定的一個子集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二集合就構(gòu)成了一種關(guān)系，即包含(或真包含)關(guān)系。定理3.2.1

x。該定理表明：空集是個沒有任何成員的集合，一無所有。證明：取

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

(B)(x)(x∈B

(x∈∧x≠x))（1）假設(shè)某x在B中，則由(1)知，x≠x，這是矛盾的。即(x∈∧x≠x)為假,

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

。再根據(jù)定義3.1.4：y為集合：=(x)(x∈y∨y=)可知，B=。因此，

(x)(x)

，于是x。0:=，1:={}，2:={,{}}，3:={,{},{,{}}},…,1924年匈牙利-美國數(shù)學(xué)家馮·諾依曼(JohnvonNeumann)依據(jù)自然數(shù)產(chǎn)生抽象的數(shù)的規(guī)律，即次序和個數(shù)兩個特性，使用空集給出自然數(shù)的集合表示。這種集合表示是：也就是：0:=，

1:={0}，

2:={0，1}，

3:={0，1，2}，…不難看出，①自然數(shù)的次序性，可傳性：

0∈1∈2∈3…，而且0∈2，0∈3，…，1∈3，…。這即是“屬于”的可傳性；其由來是這種表示法具有包含關(guān)系：

0123…，而包含關(guān)系可以證明是可傳遞的。②自然數(shù)的“基數(shù)”：

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

必要性：

假設(shè)對任意x,xA，則A中無任何元素，由定義3.1.4y為集合：=(x)(x∈y∨y=),

可知，A=。

集合的包含與真包含關(guān)系的定理有：定理3.2.3①AA；

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

(xAxB)∧(xBxA))

(分配律)(x)(xA?xB)A=B本定理表明包含關(guān)系是自反的，反對稱的和可傳遞的。具有這三種性質(zhì)的關(guān)系稱為偏序關(guān)系。因此，包含關(guān)系是個偏序關(guān)系。定理3.2.4真子集的性質(zhì)①┐(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)下面給出一個有用的結(jié)論：

在ZFS集合論中不存在全總集。定理3.2.5┐(B)(x)(x∈B)證明：(反證法)假設(shè)(B)(x)(x∈B)，即B為全集，一切客體都屬于它。于是在子集公理中，取A為全集B，便有：

(C)(x)(x∈C

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

(C)(x)(x∈C

(x))這便是抽象公理，從而將導(dǎo)出羅素悖論。故全集是不存在,即：┐(B)(x)(x∈B)例3.2.1

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

令j是張中，C是中國，U是聯(lián)合國，則j∈C∈U，但jU。集合的元素可以是一個集合例如：A={a,b,c,D},而D={0,1}。3.3集合的表示法一、枚舉法（列舉法）把集合中的元素一一列舉出來，成員之間用逗號分隔，然后用花括號括起來表示集合。例如“所有小于5的正整數(shù)”這個集合的元素為1,2,3,4,除這4個元素外,再沒有別的元素。如果把這個集合命名為A,就可記為A={1,2,3,4}

在能清楚表示集合成員的情況下可使用省略號,例如,從1到50的整數(shù)集合可記為{1,2,3,…,50},偶數(shù)集合可記為{…,-4,-2,0,2,4,…}。

表征集合S中成員多少的量，稱為集合S的基數(shù)，記為|S|，若|S|=n，其中n∈N，稱S為有限集合。

二、抽象法（描述法）用謂詞描述出集合元素的公共特征來表示這個集合。使用記號：{x|φ(x)}來表示具有性質(zhì)φ(x)的一切客體所組成的集合S，其中φ(x)稱為入集條件，表示x∈S

當且僅當φ(x)是真。例如,上述各例可分別寫成A={a|a∈I∧0＜a∧a＜5},{a|a∈I∧1≤a≤50}這里I表示整數(shù)集合。

{x|1≤x≤6∧x為整數(shù)}即為{1，2，3，4，5，6}。定義模式3.3.1

{x|φ(x)}=y

(

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

為集合)

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

)

由φ(x)的不同可得出不同的集合。于是給出了定義模式和定理模式。若不存在滿足性質(zhì)φ(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}證明：②假設(shè)存在一個y,使得y∈{x

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

φ(y)知，y≠y，這是矛盾的。即對任意y，

(y)(y

{x|x≠x})。根據(jù)定理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)}下面定理模式表明：若兩入集條件(即性質(zhì))是永真等價的，則它們外延必相等。證明：令y1={x|φ(x)},y2={x|ψ(x)}.

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

(x))，則由定義模式3.3.1知，y1=。由本定理模式假設(shè)可有┐(B)(x)(x∈Bψ(x))，則y2=。否則，依據(jù)定義模式3.3.1，便得：

y

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

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

由本定理模式假設(shè)φ(x)ψ(x)知：

y

∈{x|φ(x)}

y

∈{x|ψ(x)}

利用定義3.2.1A=B

(x)(x∈A

x∈B)，可得：

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

首先將給定集合S中元素任意規(guī)定一種次序，例如：

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

設(shè)S={1，2，3，4，5，6，7，8，9，10}，且S中的元素從小到大排序，即ai=i。試問表示S中所有奇數(shù)的子集SO，所有表示偶數(shù)的子集SE以及不超過6的整數(shù)的子集S6的位串是什么？SO：1010101010SE：0101010101S6：11111100003.4偶集公理與聯(lián)集公理

偶集公理：對于給定的任何兩個集合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構(gòu)成的單元集。聯(lián)集公理：對于任何一個集合A，存在一個集合C，C的成員恰是A的成員的成員。本公理形式地表為：

(C)(x)(

x∈C

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

)定義3.4.2

C集合是A集合的一個聯(lián)集，當且僅當

(x)(x∈C

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

C集合常用并運算符號∪表為：C=∪A。

于是，集合A的聯(lián)集按抽象法又可給出：定義3.4.3

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

令A(yù)={{1，2}，{3}，4}，B={4，{5}，{5，6}}

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

兩個集合A和B的初等并運算，可定義為以A，B為成員的偶集{A，B}的聯(lián)集，即：

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，容易構(gòu)成三元集、四元集如下：

{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

}應(yīng)用子集公理給出的子集來定義兩個集合的差，只要取φ(x)為xB，便可有：

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

}兩個集合A、B的差A(yù)-B，也稱為B相對于A的補。集合的差例3.4.1

令A(yù)={{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)，由聯(lián)集公理可得：

{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)證明：①

必要性：假設(shè)x∈∩A,則∩A≠。根據(jù)定義3.4.5∩A：={x|(B)(B∈A→x∈B)}和定義模式3.3.1可推出：

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

現(xiàn)在假設(shè)：┐(B)(B∈A)(2)

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

(B)(BA)

由定理3.2.2知(B)(BA)A=。于是，∩A=，這與假設(shè)x∈∩A矛盾。因此假設(shè)(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)成立,根據(jù)假設(shè)，有B*∈A。由此應(yīng)用子集公理可得：

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

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

成立由此再根據(jù)(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.現(xiàn)在問：是否存在一個集合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=)。

正則公理也稱為基礎(chǔ)公理或限制公理。是否每個集合都有極小元呢?是的，1925年馮·諾伊曼(VonNeumann)提出的正則公理給予了滿意答復(fù)。定理3.5.1

對于任意集合S，有SS。證明：反證法，假設(shè)有S

使得S

∈S.由構(gòu)造單元集合{S}，顯然S

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

∩{S}=。但是，由假設(shè)S

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

∩{S}≠，這是矛盾的。所以對任意集合S，都有SS。定理3.5.2對任何集合S1和S2，都有┐(S1∈S2∧S2∈S1)。證明：設(shè)S={S1,S2}，

則S1和

S2均為S的極小元

。假設(shè)(S1∈S2∧S2∈S1)，則有

S1∈(S2∩S)且S2∈(S1∩S)。于是，S2∩S≠，S1∩S≠，這與正則公理矛盾。因此，對于任意集合S1和S2，都有┐(S1∈S2∧S2∈S1)。定理3.5.3對任意自然數(shù)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+的前驅(qū)，S+為S的后繼，并稱“+”為后繼運算。定義3.6.20:=，1:=0+，2:=1+，一般地，n+1:=n+。顯然，自然數(shù)集合N就是用后繼定義的無窮集合。由上面定義可知，對于n∈N，有①n

∈

n+；②n

n+。由此可見，0，1，2，3，…不單是書寫自然數(shù)符號，而且也是用空集與后繼表示的各個集合。定義3.6.3

若集合A有性質(zhì)：

∈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))證明：根據(jù)無窮公理，確有某歸納集C的存在。現(xiàn)在取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是一個最小歸納集。令I(lǐng)nd(D),則容易看出Ind(C∩D),所以A

C∩D

D，

A是被任何歸納集D所包含的一個歸納集，稱該集合為最小集合，故A是一個最小歸納集。定義3.6.4

稱最小歸納集

ω：={x|(B)(Ind(B)→x∈B)}是自然數(shù)集合，ω的元稱為自然數(shù)。依據(jù)定義3.6.2可知0，1，2，…都是自然數(shù)，并且從自然數(shù)集ω

的最小歸納集性質(zhì)，得到關(guān)于一般數(shù)學(xué)歸納法的根據(jù)。關(guān)于ω的歸納原理：ω的任何一個歸納子集與ω重合。

從外延公理知，這個最小歸納集是唯一的，并稱它是一個自然數(shù)集合。自然數(shù)集合常用N表示。3.7冪集公理

給定一個集合的所有子集，這個集合稱為給定集合的冪集。自然想到：是否對一切集合，其冪集都存在呢？這需要由公理給以保證，為此引進一條新的公理。本公理可形式地表為：

(B)(x)(x∈B

(y)(y∈x

→y∈A))或者用包含關(guān)系表示成：

(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)。

關(guān)于冪集的討論，從有限集合的冪集開始。定義3.7.2

對于一個集合A，如果存在自然數(shù)n，使得A恰有n個元，則稱A是有限的。定理3.7.1

若A

是一個有限集合且BA，令

C=A∪{B}，則C的所有子集的個數(shù)恰是A的所有子集的個數(shù)的二倍。例子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})的子集個數(shù)是P{1，2}的子集元素個數(shù)的二倍。定理3.7.2

對于自然數(shù)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，