1、第二篇 集合論第四章 集合及其運算4.1 集合的基本概念 內容提要4.1.1集合及其元素 集合是一些確定的、作為整體識別的、互相區別的對象的總體。 組成集合的對象稱為集合的成員或元素（member）。通常用一對“ ”把集合的元素括起來，表示一個集合。 元素對于集合的隸屬關系是集合論的另一基本概念。即當對象a是集合A的元素時，稱元素a屬于集合A，記為 aA 當對象a不是集合A的元素時，稱a不屬于A，記為 Ø(aA)或aÏA 對任何對象a和任何集合A，或者aÎA或者aÏA,兩者恰居其一。這正是集合對其元素的“確定性”要求。定義41 空集和只含有有限多個元素的

2、集合稱為有限集（finite sets），否則稱為無限集（infinite sets）。有限集合中元素的個數稱為基數（cardinality）（無窮集合的基數概念將在以后重新嚴格定義）。集合A的基數表示為 |A|。4.1.2 外延公理、概括公理和正規公理集合論依賴于三大基本原理：外延公理（extensionality axiom）、概括公理（comprehension axiom）和正規公理（regularity axiom）。它們從根本上規定了集合概念的意義。外延公理：兩個集合 A和 B相等當且僅當它們具有相同的元素。即對任意集合A，B, A=B «"x(xÎA

3、«xÎB) 外延公理事實上刻劃了集合的下列特性：集合元素的“相異性”、“無序性”，及集合表示形式的不唯一性。 概括公理: 對任意個體域，任一謂詞公式都確定一個以該域中的對象為元素的集合。即對給定個體域U，對任意謂詞公式P(x)，存在集合S，使得 Sx êxÎUP(x) 概括公理規定了集合元素的確定性,以及集合的描述法表示的理論依據，它還規定了空集的存在性。 正規公理：不存在集合A1，A2, A3，使得 ÎA3 Î A2 ÎA1正規公理的一個自然推論是：對任何集合A，A¹A（否則有ÎAÎA

4、6;A）。從而規定了集合A與A的不同層次性,因而正規公理也就規定了集合不能是自己的元素。4.1.3 子集合 定義4.2 集合A稱為集合B的子集合（或子集，subsets），如果A的每一個元素都是B的元素，即 "x(xÎA®xÎB)A是B的子集，表示為AÍB（或BÊA），讀作“A包含于B”（或“B包含A”）。 定理4.1對任意集合A，B，AB當且僅當A Í B且B Í A 。定理4.2 對任意集合A，A Í U。 定理4.3 設A，B，C為任意集合，若A Í B,B Í C，則A 

5、05; C。 定理4.4 對任何集合A，Æ Í A。即空集是任意集合的子集。定理4.5 空集是唯一的。 定理 4.6 設 A 為一有限集合，|A| = n，那么 A的子集個數為2n。 習題解答練習4.1l、證明：如果AÎb，那么bÎA。證 由于A為集合b的元素，而集合b中只有一個元素b，所以A=b；又因為bÎb，所以bÎA。2、用描述法規定下列集合：（1）A 1，3，5（2）B = 2，3，5，7，11，13，17，89，97（3）C0，1，2，3，9（4）全集 U解 （1）A （2）B =，：為小于100的質數 （3）C （4）U

6、為任意一元謂詞公式3、對任意對象a，b,c，d，證明：a,a,bc,c，d 當且僅當 a = c且b = d 證 設a = c且b = d，則顯然a,a,bc,c，d；設a,a,bc,c，d，則有ac，a,bc，d或者ac，d，a,bc。前一種情況有ac且bd；后一種情況有acd且abc，所以有ac且bd。命題得證。4、指出下列集合序列的排列規律，并依此規律再寫出兩個后續集合：Æ ，Æ，Æ,Æ,Æ，Æ，Æ，Æ，解 上述集合序列的排列規律是An+1AnÈAn。兩個后續集合分別為：Æ，Æ，

7、Æ，Æ，Æ，Æ，Æ，Æ；Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ。5、“如果AÎB, BÎC，那么AÎC”對任意對象A,B,C都成立嗎？都不成立嗎？舉例說明你的結論。解 并不都成立，例如：設A1,B1,C1，此時AÎB且BÎC，但AÏC；另一方面，并不是都不成立，例如：A1,B1, C1，1，此時

8、AÎB，BÎC，且AÎC。 6、確定下列各命題的真、假； （1）ÆÍ Æ （2）ÆÌ Æ （3）ÆÎÆ （4）Æ ÍÆ （5）ÆÎÆ （6）a, b Ía , b , c,a， b，c （7）a, bÎa， b， c，a， b，c （8）a, bÍa，b，a，b（9）a, bÎa，b，a，b（10）a, bÌa，b，a，b （11）對任意集合A，B，C，、若A

9、6;B，B Í C則AÎC。 （12）對任意集合A，B，C，若AÎB，B ÍC則A Í C。 （13）對任意集合A，B，C，若A Í B，BÎ C則A Î C。（l4）對任意集合A，B，C，若A Í B，B Î C則A Í C。解 （1）真，（2）假，（3）假，（4）真，（5）真，（6）真，（7）假，（8）假，（9）真，（10）真，（11）真，（12）假，（13）假，（14）假。 7、指出下列各組集合中的集合間的不同之處，并列出每一集合的元素和全部子集： （1） Æ，

10、98;（2）a，b，c，a，b，c，a，b，c解 （1）不同之處：前者是以空集為元素的集合，而后者是以前者為元素的集合。Æ的元素為Æ，全部子集為：Æ，ÆÆ的元素為Æ，全部子集為：Æ，Æ（2）第一個集合由3個元素組成；第二個集合由2個元素組成，其中一個元素為集合；第三個集合由1個元素組成，該元素為一個集合。a，b，c的元素為：a，b，c；全部子集為：Æ，a，b，c，a，b，b，c，a，c，a，b，c。a，b，c的元素為：a，b，c；全部子集為：Æ，a，b，c，a，b，c。a，b，c的元素為：a，b

11、，c；全部子集為：Æ，a，b，c。 8、羅素曾用下列較通俗的悖論來解釋他的集合論悖論（羅素悖論）：某鎮上一位理發師宣布，他只給那些不給自己刮臉的人刮臉。問：為什么這是一個悖論？解 如果理發師給自己刮臉，那么按照規定，理發師不能給自己刮臉（因為他只給那些不給自己刮臉的人刮臉）；如果理發師不給自己刮臉，那么按照規定，理發師應該給自己刮臉（因為他給那些不給自己刮臉的人刮臉）。這樣，理發師給自己刮臉或不給自己刮臉都得出矛盾。所以這是一個悖論。9、說明為什么在確定個體域上使用抽象原理(即使用概括公理)時羅素悖論不再成立。解 在確定的個體域D上使用概括公理時，羅素悖論中的集合當我們再問時，回答時

12、不會導致矛盾，因為。從而避免了羅素悖論的產生。10、設A，B為任意集合證明：如果對任意的集合C，C Í A當且僅當C Í B，那么AB。證 因為C為任意的集合，因此，當令CA時有A Í B，當令CB時有B Í A，因此有AB。11、證明：不能使用“一切集合的集合（所謂大全集）”作為個體域U。（提示：若用大全集作為個體域；概括公理也將導致羅素悖論。）解 如題9，加上確定的個體域D為大全集U，則概括公理為S = x | xÎU Ù P(x)，它等價于S = x | P(x)，這就相同于抽象原理，會產成悖論。4.2 集合運算 內容提要4.2

13、.1 并、交、差、補運算 定義4.4 設A，B為任意集合。 （l） AB稱為A與B的并集（union set），定義為 ABxxAxB稱為并運算。 （2） AB稱為A與B的交集（intersection set），定義為 AB =xxAx B稱為交運算。 （3） A-B稱為A與B的差集（difference set），定義為 A-BxxAx Ï B- 稱為差運算。 （4）A稱為A的補集（complement set），定義為 A=U-A =x | xUxÏA 稱為補運算，它是一元運算，是差運算的特例。定理4.7 設A，B，C為任意集合，那么 （l）AÈAA A&#

14、199;AA （冪等律） （2）AÈB = BÈA AÇB = BÇA （交換律） （3）AÈ（BÈC）=（AÈB）ÈC AÈ（BÈC）=（AÈB）ÈC （結合律） （4）AÈÆA， AÇU=A （同一律） （5）AÇÆ=Æ， AÈU = U （零一律） （6）AÈ(BÇC)=(AÈB)Ç(AÈC) AÇ(BÈC)=(AÇB)&

15、#200;(AÇC) （分配律） （7） AÈ（AÇB）= A， AÇ（AÈB）= A （吸收律） 定理 4.8 對任意集合 A，B，C， （l） A - BAÇB （2）A - AÆ， A - ÆA， A U = Æ （3）A - (BÈC)(A - B)Ç(A - C) A - (BÇC)(A - B)È(A - C) 定理4.9 對任意集合A，B（1） AA （雙重否定律）（2） UÆ , ÆU （補余律）（3） AÈAU , A

16、ÇAÆ （互否律） （4）(AÈB)AÇ B (AÇB)AÈ B （德摩根律） 定理4.10 對任意集合A , B , C , D， （1）A Í AÈB，B Í AÈB （2）AÇB Í A AÇB Í B。 （3）A - B Í A （4）A Í B, A - B = Æ,AÈB = B , AÇB = A 四個命題等價。 （5）若A Í B,則BÍ A 定理4.11 對任意集合A，

17、B若它們滿足 （l）AÈBU （2）AÇBÆ 那么BA4.2.2 求冪運算和廣義并、交運算* 定義 4.5 對任意集合 A，(A)稱為A的冪集（Power set），定義為 (A)x | xÍA 即A的全體子集構成A的冪集。此種運算稱為集合A的求冪運算。 定理4.12 設A,B為任意集合, AÍB當且僅當(A) Í(B) 。 定義4.6 若集合C的每個元素都是集合，則稱C為集合族（collections）。若集合族C可表示為 C =Sd|d ÎD則稱 D為集合族的標志集（index set）。定義4.7 設C為非空集合族，（

18、l） 稱為C的廣義并，定義為 （2） 稱為C的廣義交。定義為 （3）當集合族C =Ad|d ÎD時，和可分別表示為，當D為自然數集N時，它們又可分別表示為 ， 定理4.13 對任意集合A和集合族C，有 定理4.14 對任意集合A和集合族C，有 定理4.15 對任意集合族C有 定理4.16 對任意集合*4.2.3環和、環積運算 定義4.8 對任意集合A，B， AÅB稱為A與B 的環和（cycle sum）或對稱差，定義為 AÅB = （A-B）È（B-A） AÄB稱為A與B 的環積（cycle product），定義為 AÄB = （A

19、ÅB）- 定理4.17 對任意集合A，B， 有（1） AÅB = （AÈB）-（A Ç B）（2） AÄB = （AÈB-）Ç（A- ÈB）定理4.18 對任意集合A，B，C，（1）A Å B = B Å A（2）A Å A = Æ（3）A- Å B- = A Å B （4）A Ä B = （A Å B）- = A- Å B = A Å B- （5）（A Å B）Å C = A Å （B

20、 Å C）（6）A Ä B = B Ä A（7）A Ä A = U（8）A- Ä B- = A Ä B（9）（A Ä B）Ä C = A Ä （B Ä C） 習題解答練習4.2l、證明定理4.7之（5）。證 （1）所以（2）所以2、證明定理4.8之（2）中的第二式。所以3、證明定理4.9之（4）。 證 所以。 4試以下列次序證明定理4.10的（4）：PÞ R ÞSÞQÞP證 P：A Í B，R：A È B = B，S：A Ç

21、B = A，Q：A B = Æ1）PÞ R：由定理4.10的（1）容易知道B Í A È B，下面要證明A È B Í B。設xÎA È B，那么xÎA或xÎB。若xÎA，因為A Í B，所以xÎB。因此有A È B Í B。所以A È B = B。2）R Þ S：由定理4.10的（2）容易知道A Ç B Í A，下面要證明A Í A Ç B。設xÎA，則xÎ A &

22、#200; B。因為已知A È B = B，那么有xÎ B，所以xÎ A Ç B，從而A Í A Ç B。故A Ç B = A得證。3）S Þ Q：反設A BÆ，那么至少有一個元素xÎ A且xÏ B，則A Ç BA，與已知條件S矛盾，故A B = Æ得證。4）Q Þ P：設xÎA，設xÏ B，則xÎ A B，與A B = Æ矛盾，所以xÎ B，故A Í B得證。5說明下列各命題是否為真，為什么。（

23、1）若A È B = A È C，則B = C 。（2）若A Ç B = A Ç C，則B = C 。解 （1）命題不為真。例，令A = 1,2，B = 1，C = 2。（2）命題不為真。例，令A = Æ，B = 1，C = 2。6對任意集合A，B，C，證明： （A È C）-（B È C）Í A - B證：xÎ（A È C）-（B È C）Û xÎ（A È C）Ç（B È C） Û xÎ（A È C）&#

24、199; BÇ CÛ xÎ（A Ç BÇ C）È（C Ç BÇ C）Û xÎ（A Ç BÇ C）Þ xÎ A Ç BÛ xÎ A - B故（A È C）-（B È C）Í A- B得證。 7對任意集合A，B，C，證明；（1） A -（B È C）（A - B）- C（A - C）- B（2）（A Ç B）- C = A Ç（B- C）=（A - C）Ç B

25、（3）（A - B）- CA -（B - C）當且僅當A Ç C = Æ（4）（A - B）- C =（A - C）-（B - C）證：（1）A -（B È C）A Ç（B È C） A Ç BÇ C （A - B）Ç C （A - B）- CA -（B È C）A Ç（B È C） A Ç BÇ C A Ç CÇ B =（A - C）Ç B （A - C）- B故A-（B È C）（A - B）- C（A - C）- B得證

26、。（2）（A Ç B）- C A Ç B Ç C A Ç（B Ç C） A Ç（B - C） （A Ç B）- C A Ç B Ç C A Ç CÇ B （A - C）Ç B故（A Ç B）- C = A Ç（B- C）=（A - C）Ç B得證。（3）設（A - B）- CA -（B - C）成立，為證A Ç C = Æ，反設有xÎA Ç C，則xÎA 且xÎC。而：（A - B）-

27、CA Ç BÇ C，所以xÏ A Ç BÇ C，從而xÏ（A - B）- C；A -（B - C）A Ç（B Ç C）A Ç（BÈ C）（A Ç B）È（A Ç C），由假設xÎA Ç C，則xÎ（A Ç B）È（A Ç C），從而x Î A -（B - C）。這與（A - B）- CA -（B - C）矛盾，所以假設不成立，故A Ç C = Æ得證。）設A Ç C

28、= Æ，此時設x為A中的任一元素，即xÎA，則x Ï C，所以A - CA，那么：（A - B）- C（A - B）ÇCA Ç BÇ CA Ç CÇ B（A - C）Ç BA Ç B；A -（B - C）A Ç（B Ç C）A Ç（BÈ C）（A Ç B）È（A Ç C）A Ç B所以在A Ç C = Æ 時，（A - B）- CA -（B - C）。綜合）、），故（A - B）- CA -（B

29、- C）當且僅當A Ç C = Æ得證。（4）證：（A - B）- C（A - B）Ç CA Ç BÇ C（A - C）-（B - C）（A Ç C）Ç（B Ç C） （A Ç C）Ç（BÈ C） （A Ç CÇ B）È（A Ç CÇ C） A Ç BÇ C故（A - B）- C（A - C）-（B - C）得證。 8證明；對任意集合A，B下列命題等價， （1）A Í B （2）AÈ B = U（

30、3）A Ç B= Æ證：（1）Þ（2）：為證AÈ B = U，反設有xÎ（AÈ B），即xÎ A Ç B，所以xÎ A且xÏB；而由A Í B知道xÎ A必有xÎ B，矛盾，故有AÈ B = U。（2）Þ（3）：因為AÈ B = U，所以對任一x，有xÎA或xÎ B）若xÎA，則xÏA，那么xÏ A Ç B）若xÎB，則xÏB，那么xÏ A

31、99; B即沒有一個元素在集合A Ç B中，所以A Ç B= Æ。（3）Þ（1）：反證設A不包含于B，即有xÎ A且xÏB，所以有xÎ A Ç B，與已知A Ç B= Æ矛盾。所以A Í B。9設A = Æ，B = 1，2，求（A），（B）。解：A = Æ，所以（A）= Æ，Æ，（A）= Æ，Æ，Æ，Æ，Æ，故（A）= Æ，Æ，Æ，Æ，Æ，

32、8;，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ。B = 1，2，所以（B）= Æ，1，2，1，2，故（B）= Æ，Æ，1，

33、2， 1，2 ，Æ，1，Æ，2，Æ，1，2，1，2，1，1，2，2，1，2，Æ，1，2，Æ，1，1，2，1，2，1，2，Æ，2，1，2，Æ，1，2，1，2。 10對任意集合A，B。求證： （1）A = B當且僅當（A）=（B） （2）（A）Ç（B）（A Ç B）（3）（A）È（B）Í（A È B）證：（1）若A = B成立，那么有xÎ（A）Û x Í A Û x Í BÛ x Î（B）故有（A）=（B）；若

34、（A）=（B）成立，反設A B，那么有xÎ A且xÏ B（因為A，B為任意集合，所以作此假設是合理的），則xÎ（A），而（A）=（B），則xÎ（B），這與xÏ B矛盾。因此A = B。綜上所述，故A = B當且僅當（A）=（B）得證。（2）xÎ（A）Ç（B）Û x Í A Ù x Í B Û x Í A Ç B Û x Î（A Ç B）故（A）Ç（B）（A Ç B）得證。（3）xÎ（A）È

35、;（B）Û x Í A Ú x Í B Þ x Í A È B Û x Î（A È B）故（A）È（B）Í（A È B）得證。11. 若C = x| xÎB 求。解：= B。 12. 對下列諸C，求 和。 （l）C =Æ （2）C =Æ，Æ （3）C =a，b，a,b （4）C =（N）（5）若允許C = Æ,請討論和。解：（1）= Æ，= Æ。（2）=Æ，= Æ。（3）=a，

36、b，= Æ。（4）=（N），= Æ。（5）=x | $s (s Î C Ù x Î s)，=x | "s (s Î C ® x Î s)，那么當C = Æ時,C中無任何元素，則此時 ， 13對任意非空集合族C1，C2，證明： （1） （2） （3）（4）證 （1）x ÎÈÛ $s (s ÎÙ x Î s) Ú $s (s ÎÙ x Î s) Û $s (s ÎÙ x

37、Î s) Ú (s ÎÙ x Î s) Û $s (s Î(È)Ù x Î s) Û因此， 。（2）設xÎ() Ç ()，那么xÎ()且xÎ()，則：$s (s ÎÙ x Î s)且$s (s ÎÙ x Î s)，那么有：$(s1 Ç s2)(s Í (s1 Ç s2) Ù x Î s Ù s1 ÎÙ s2

38、Î)， 則：x Î s1 Ç s2| s1 ÎÙ s2 Î，即有() Ç () Í s1 Ç s2| s1 ÎÙ s2 Î；且以上推導均可逆，故有Ç s1 Ç s2| s1 ÎÙ s2 Î。（3）設對于任一x Î()，則對任一s1 Î有x Î s1或對任一s2 Î有x Î s2，那么對任一s1 È s2（s1 Î，s2 Î）有x Î s1

39、 È s2，因此：x Î s1 È s2| s1 ÎÙ s2 Î，所以()Í s1 È s2| s1 ÎÙ s2 Î，且以上推導均可逆，故有() = s1 È s2| s1 ÎÙ s2 Î。（4）仿上題，易證ÇÍ；而對任一s，sÎÈ，有xÎs，則對任一s1Î，有x Î s1，且對任一s2Î有xÎ s2，因此ÍÇ。故有Ç=。 *1

40、4對任意集合A，B，C，證明： （1）A Å A Å B = B （2）（A - B）Å B = A È B （3）（A Ä B）È C =（A È C） Ä（B È C） （4）（A Å B）Ç C =（A Ç C） Å（B Ç C） （5）（A Å B） C =（A C） Å（B C） （6）A È B = A Å（B Å（A Ç B）證 （1）A Å A Å B = &#

41、198; Å B = ( Æ B) È (B Æ) = B（2）(AB) Å B = (A Ç B) Å B = (A Ç B B) È (B A Ç B) = (A Ç B) È B = (A È B) Ç (B È B) = A È B（3）(A Ä B) È C = (A Å B) È C = (A B) È (B A) È C = (AÇ B) È

42、(A Ç B) È C(A È C) Ä (B È C) = (A È C) Å (B È C) = (A È C) (B È C) È (B È C) (A È C) ) = (AÇ CÇ BÇ C) È (B È C) Ç (A È C) = (AÇ BÇ C) È (A Ç B) È C = (AÇ BÇ C) È

43、; C È (A Ç B) = (AÇ B) È C) Ç (C È C) È (A Ç B) = (AÇ B) È C È (A Ç B)所以有（A Ä B）È C =（A È C） Ä（B È C）。（4）(A Ç C) Å (B Ç C) = (A Ç C) (B Ç C) È (B Ç C) (A Ç C) = (A Ç C &#

44、199; (BÈ C) È (B Ç C Ç (AÈ C) = (A Ç C Ç B) È (A Ç C Ç C) È (B Ç CÇ A) È (B Ç C Ç C) = (A Ç C Ç B) È (B Ç CÇ A) = (A Ç B) È (AÇ B) Ç C = (A B) È (B A) Ç C = (A Å

45、; B) Ç C所以有(A Å B) Ç C = (A Ç C) Å (B Ç C)。（5）(A Å B) C = (A Ç B) È (AÇ B) Ç C = (A Ç B) Ç C) È (AÇ B) Ç C) = (A Ç B Ç C) È (AÇ B Ç C) (A C) Å (B C) = (A C) (B C) È (B C) (A C) = (A

46、99; CÇ (B C) È (BÇ CÇ (A C) = (A Ç CÇ (B È C) È (BÇ CÇ(A È C) = (A Ç CÇ B) È (AÇ CÇ C) È (BÇ CÇ A) È (BÇ CÇ C) = (A Ç CÇ B) È (BÇ CÇ A)所以有(A Å B) C = (A Ç

47、CÇ B) È (BÇ CÇ A)。（6）A Å (B Å (A Ç B) = A Å (B A Ç B) È (A Ç B B) = A Å (B Ç(A Ç B) ) È (A Ç BÇ B) = A Å (B Ç(A È B) = A Å (A Ç B) = (A A Ç B) È (A Ç B A) = (A Ç (A È

48、; B) È (A Ç B Ç A) = A È (A Ç B) È (A Ç B)= (AÈ A) Ç (A È B) È (A Ç B)= (A È B) È (A Ç B)= (A È B È A) Ç (A È BÇ B)= A È B所以有A È B = A Å (B Å (A Ç B)。*15.對任意集合A，B，C，證明：（1） 若A

49、C = B C，則A Å B Í C。（2）若A Å B = A Å C，則B = C。證 （1）反設(A Å B) Í C，則存在xÎ(A B) È (B A)且xÏC，）若xÎ A B，則有xÎA，xÏB，xÏC，所以xÎ A C而xÏ B C，與已知的A C = B C矛盾；）若xÎ B A，則有xÎ B，xÏ A，xÏC，所以xÎ B C而xÏ A C，與已知的A C = B C

50、矛盾。因此，A Å B Í C。（2） 反設B = C，那么不妨設有x，xÎB，xÏC。）若xÎ A，則xÏ A Å B，但xÎA Å C，與A Å B = A Å C矛盾。）若xÏA，則x ÎA Å B，但xÏA Å C，又與A Å B = A Å C矛盾。因此有B = C。4.3 集合的歸納定義及歸納法證明 內容提要4.3.1集合的歸納定義 集合的歸納定義由三部分組成: （1）基礎條款：規定待定義集合以某些元素為

51、其基本成員，集合的其它元素可以從它們出發逐步確定。 （2）歸納條款：規定由已確定的集合元素去進一步確定其它元素的規則。于是，可以從基本元素出發，反復運用這些規則來確認待定義集合的所有成員。 （3）終極條款：規定待定義集合只含有（l），（2）條款所確定的成員。條款（l），（2）又稱歸納定義的完備性條款，它們必須保證毫無遺漏地產生出待定義集合的全部成員；條款（3）又稱歸納定義的純粹性條款，它保證整個定義過程所規定的集合只包括滿足要求的那些對象。4.3.2 自然數的集合論定義 定義 4.9 （l）稱空集 Æ 為自然數，記為0。 （2）稱A為集合A的直接后繼，如果 AA ÈA 定義

52、4.10 歸納定義自然數集N： （l）基礎條款：ÆÎN 。 （2）歸納條款：如果xÎN ，則x= x ÈxÎ N。 （3）終極條款（略） 按照上述定義。自然數集N由下列元素組成： Æ，Æ，Æ，Æ，Æ，Æ，Æ，Æ，或 0，0，0”，0”，將它們依次表示為 0，1，2，3， 習題解答練習 4.31歸納定義å*（å*å+Èl），令å= a，b。解 （1）基礎條款：å Í å*，l Î

53、 å*（2）歸納條款：如果xÎ å，yÎ å*，則xyÎ å*（3） 終極條款：除有限次使用（1）、（2）條款確定的元素外，å*中沒有別的元素。 2令å= a,b,c，歸納定義： （l） L Í å*，使L中所有字里都有字ab的出現，且所有含字 ab的字全在L中。（2） L Í å*，使L中所有字里都含有字符a和b，且所有含字符a,b的字全在L中。解 （1）基礎條款：ab Î L）歸納條款：如果xÎ å，yÎ L，則xy &#

54、206;L，yx ÎL）終極條款：除有限次使用（1）、（2）條款確定的元素外，L中沒有別的元素。（2）基礎條款：abÎ L，baÎ L）歸納條款：如果xÎ å，yÎ L，y=w1w2則w1xw2ÎL）終極條款：除有限次使用（1）、（2）條款確定的元素外，L中沒有別的元素。 3歸納定義下列集合： （1）十進制無符號整數集合，非零數不得以 0為字頭。 （2）十進制非負有窮小數。 （3）全體十進制有理數。（4）二進制形式的非負偶數， 非零數不得以0為字頭解 （1）設I表示十進制無符號整數集合，其歸納定義如下：）基礎條款：0，1，2

55、，3，4，5，6，7，8，9Í I）歸納條款：如果xÎ I且x 0，yÎ I，則xy Î I 。）終極條款：除有限次使用（1）、（2）條款確定的元素外，I中沒有別的元素。（2）設R表示十進制非負有窮小數集合，其歸納定義如下：）基礎條款：x. ê xÎ IÍ R）歸納條款：如果xÎ R，yÎ0，1，2，3，4，5，6，7，8，9，則xyÎ R）終極條款：除有限次使用（1）、（2）條款確定的元素外，R中沒有別的元素。（3）設Q表示全體十進制有理數集合，其歸納定義如下：）基礎條款：I Í Q

56、 (I為整數集)）歸納條款：如果xÎ Q且x 0，yÎ Q，則x/y Î Q）終極條款：除有限次使用（1）、（2）條款確定的元素外，Q中沒有別的元素。 4 回憶命題公式的定義（公式中括號不省略）?，F將公式中命題變元、命題常元和聯結詞全部刪去，所留下的括號串稱為成形括號串。 （l）歸納定義成形括號串集合（假定它含有空括號串l）。 （2）證明：成形括號串中左括號數等于右括號數。（3）證明：成形括號串的字頭中，左括號數不少于右括號數。解 （1）設R表示成形括號串集合，其歸納定義如下（為了明晰，用 代替（ ） ）：）基礎條款：lÎ R）歸納條款：如果x、y

57、06;R，則x ÎR，xy ÎR）終極條款：除有限次使用（1）、（2）條款確定的元素外，R中沒有別的元素。（2）證明：設L（x），R（x）分別表示成形括號串x中的左、右括號數。）基礎：L（l）= R（l）= 0，命題成立。）歸納：設L（x）= R（x），L（y）= R（y），則 L（x）= L（x）+ 1 = R（x）+ 1 = R（x）， L（xy）= L（x）+ L（y）= R（x）+ R（y）= R（xy）因此對一切成形括號串x，有L（x）= R（x）。（3）證明：）基礎：空成形括號串的字頭的左括號數不少于右括號數無義地真。）歸納：設成形括號串x，y的字頭中左括號數大于或等于右括號數，則x的字頭為l 或 或 毗連x的字頭，而x的字頭中左括號數大于或等于右括號數，因此x的字頭中左括號數大于或等于右括號數。又xy的字頭集合中包括x的字頭以及x與y的字頭毗連而成的字頭。因為x，y的字頭中左括號數大于或等于右括號數，而x中左括號數等于右括號數，因此xy的字頭的左括號數大于或等于右括號數。歸納完成，命題得證。5用歸納法證明：對任意正整數n有 (1 + 2 + + n)213 + 23 + + n3證 ）基礎：當n = 1時，12 13）歸納：設當n = k時，(1 + 2 + + k)213 + 23 + + k3那么當n = k