对任意有理数x.y定义运算如下:x△y=ax+by+cxy.这里a.b.c是给定的数.等式右边是通常数的加法及乘法运算.如当a=1.b=2.c=3时.l△3=1×l+2×3+3×1×3=16.现已知所定义的新运算满足条件.1△2=3.2△3=4.并且有一个不为零的数d使得对任意有理数x△d=x.求a.b.c.d的值． 题目和参考答案——精英家教网——
暑假天气热？在家里学北京名师课程，
& 题目详情
对任意有理数x、y定义运算如下：x△y=ax+by+cxy，这里a、b、c是给定的数，等式右边是通常数的加法及乘法运算，如当a=1，b=2，c=3时，l△3=1×l+2×3+3×1×3=16，现已知所定义的新运算满足条件，1△2=3，2△3=4，并且有一个不为零的数d使得对任意有理数x△d=x，求a、b、c、d的值．&
【答案】a的值为5、b的值为0、c的值为﹣1、d的值为4【解析】试题分析：由x△d=x，得ax+bd+cdx=x，即（a+cd﹣1）x+bd=0，得①，由1△2=3，得a+2b+2c=3②，2△3=4，得2a+3b+6c=4③，解以上方程组成的方程组即可求得a、b、c、d的值．解：∵x△d=x，∴ax+bd+cdx=x，∴（a+cd﹣1）x+bd=0，∵有一个不为零的数d使得对任意有理数x△d=x，则有①，∵1△2=3，∴a+2b+2c=3②，∵2△3=4，∴2a+3b+6c=4③，又∵d≠0，∴b=0，∴有方程组解得．故a的值为5、b的值为0、c的值为﹣1、d的值为4．考点：单项式乘多项式．点评：本题是新定义题，考查了定义新运算，解方程组．解题关键是由一个不为零的数d使得对任意有理数x△d=x，得出方程（a+cd﹣1）x+bd=0，得到方程组，求出b的值．&
练习册系列答案
科目：初中数学
老师为同学们表演了这样一个魔术：请你任意想一个数，把这个数乘2后加8，然后除以4，再减去你原来所想的那个数的一半，老师马上猜出你所得的结果．聪明的小霞作了如下的探索：（1）如果任取的那个数是5，请列式后计算结果；（2）再取一个负数试试；（3）请用数学的方法解密老师的魔术（即证明对任意一个有理数，结果为定值）．
科目：初中数学
来源：江苏省太仓市学年七年级上学期期中考试数学试题(苏教版)
老师为同学们表演了这样一个魔术：请你任意想一个数，把这个数乘2后加8，然后除以4，再减去你原来所想的那个数的一半，老师马上猜出你所得的结果．聪明的小霞作了如下的探索：
(1)如果任取的那个数是5，请列式后计算结果；
(2)再取一个负数试试；
(3)请用数学的方法解密老师的魔术(即证明对任意一个有理数，结果为定值)．
科目：初中数学
来源：江苏省期中题
题型：解答题
老师为同学们表演了这样一个魔术：请你任意想一个数，把这个数乘2后加8，然后除以4，再减去你原来所想的那个数的一半，老师马上猜出你所得的结果．聪明的小霞作了如下的探索：（1）如果任取的那个数是5，请列式后计算结果；（2）再取一个负数试试；（3）请用数学的方法解密老师的魔术（即证明对任意一个有理数，结果为定值）．
精英家教网新版app上线啦！用app只需扫描书本条形码就能找到作业，家长给孩子检查作业更省心，同学们作业对答案更方便，扫描上方二维码立刻安装！
请输入姓名
请输入手机号博主最新文章
博主热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)当前位置： >>
第1章 集合代数
第 1 章 集合代数集合理论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念――集合 （sets）出发，定义数及其运算，进而发展到整个数学。集合理论产生于 16 世纪末。当时， 只是由于微积分学的需要，人们仅对数集进行了研究。19 世纪末，即 1876 一 1883 年间， 康托尔 （Georg Cantor 1845 一 1918 年,德国数学家） 对任意元素的集合进行了系统的研究。 康托尔被公认为集合理论的创始人。[1] 人们称康托尔开创的集合理论为朴素集合论，因为他没有对集合论作完全公理化的描 述，从而导致了理论的不一致（产生了悖论） 。为弥补朴素集合理论的不足，本世纪初出现 了各种公理化集合论体系,为数学奠定了一个良好的基础。更有意义的是，从此集合基本概 念不断深入人心， 被广泛地应用于数学理论和其他学科的基础研究和实际应用中， 集合论的 原理和方法成为名副其实的数学基本技术。基于本书的教学目的，以“集合代数”为标题的 本章，主要讨论集合基本概念和集合运算。它与第二章在一起，被视为全书学习所必备的最 基本的数学知识和工具，在以后讨论的内容中将不断地运用它们。因此，本章将不涉及公理 化集合论体系。 事实上， 集合不仅可用来表示数及其运算， 更可以用于非数值信息及离散结构的表示和 处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的 数值计算来处理，但可以用集合运算来实现。集合论被广泛应用在计算机科学中，如数据结 构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、 CAD 等，这也是本章学习集合理论基础知识的目的。1.1 集合的概念与表示 1.1.1 集合及其元素在中学的数学课程中,大家对集合及其元素的意义已经有所了解,因此， 下面我们做些简 要的回顾。 集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。 严格地说这不是集合的定义，因为“总体”只是“集合”一词的同义反复。实际上，在 集合论中，集合是一个不作定义的原始概念（就像几何学中的点、线、面等概念） 。不过， 上述关于集合概念的描述，有益于对它的内涵和外延作直观的理解和认识。 例 1.1 （1） “北洋大学全体学生”为一集合，组成这一集合的对象是北洋大学的学生。 （2） “全体正整数”为一集合，其组成对象是正整数。 （3） “本书中所有汉字”的集合，其组成对象是本书的汉字。 （4） “获 1988 年诺贝尔文学奖的作家”构成一个集合，尽管它只有一个对象――埃及 作家纳吉布 ?马夫兹。 “获 2002 年诺贝尔生理学或医学奖的科学家”构成一个集合，它包括 英国科学家悉尼 ?布雷内,美国科学家罗伯特 ?霍维茨,英国科学家约翰 ?苏尔斯顿三名成 员。 （5） “解放军理工大学所有学员队”的集合，其组成对象是学员队，而不是学员，因为 集合中对象是整体识别的，尽管学员队又是学员的集合。 （6） “好书的全体”不构成集合，因为难以对每一本书的好坏作出确定的判断。 （7） “方程 x(x2-2x+1)=0 的所有根”组成一个集合，它只有一个对象 0 和一个（而不是 两个）对象 1，因为集合中对象是相互区别的。 （8） “方程 x2 +x+1=0 的根”组成一个集合。当在复数域上讨论时，它由两个对象组成； 而当在实数域上讨论时，它不含有任何对象，是一个特定集合。 组成集合的对象称为集合的成员或元素（members） 请注意，这里“对象”的概念是相当普遍的，可以是任何具体的或抽象的客体，还可以 又是集合， 因为人们有时以集合为其讨论的对象， 而又需涉及它们的一个总体――以集合为 其元素的集合。例如，例 1.1（5 ）的集合，以学员队集体为其元素；又如集合{1，{1，2}， {1}，2}，数 1，2 是它的成员，集合{1}和{1，2}也是它的成员。因此，尽管集合与其成员 是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。因此必须注意，a 不 同于{a}，前者为一对象 a，后者为仅含该对象 a 的单元素集合；同样，{a}≠{{a}}，{{a}}是 1仅含{a}的单元素集。 通常用大写拉丁字母 A，B，C 等表示集合，用小写字母 a, b, c 等表示集合的元素。 但是，由上可知，这种表示形式不是绝对的。a 作为 A 的元素时，并不排斥 a 作为集合的可 能性。同样，集合 A 也可能是别的集合的元素。 元素对于集合的隶属关系是集合理论的另一基本概念。当对象 a 是集合 A 的成员时， 称 a 属于 A，记为 a∈A 当对象 a 不是集合 A 的成员时，称 a 不属于 A，记为 a?A 对任何对象 a 和任何集合 A，或者 a?A 或者 a?A,两者恰居其一。这正是集合论对其元素的 “确定性”要求。1.1.2 集合的表示集合的表示方式主要有以下三种： （l）列举法：表示一个集合 A 时，将 A 中元素―一列举，或列出足够多的元素以反映 A 中成员的特征，其表示形如 A ＝｛a1，a2，?，an｝或 A =｛a1，a2，a3, ?｝ （2）描述法；表示一个集合 A 时，将 A 中元素的特征用一个性质来描述，其表示形式 如 A =｛x ? P(x)｝或 A =｛x : P(x)｝ 其中 P(x)表示“x 满足性质 P”或“x 具有性质 P” =｛x ? P(x)｝或 A =｛x : P(x)｝的意义 。A 是：集合 A 由且仅由满足性质 P 的那些对象所组成，也就是说 a?A 当且仅当 a 满足性质 P（或 P(a)真） 例题 1.1 中的集合都是采用这种方式表示的。 （3）归纳法：将在 1.3 节中详细介绍。 例 1.2 以下是常常要用到的一些集合以及它们的表示。 （1）{0，l}＝{x?x＝0 或 x＝l} （2）自然数集合 N = {0，1，2，3，?} = {x?x 是自然数} 正整数集合 I+ = {1，2，3，?} = {x?x 是正整数} （注意， 这里我们所说的自然数集合与中学课本定义的自然数集合略有不同, 它使自然数 集合有别于正整数集合, 自然数集合包括数 0,这是计算机科学的一个通常做法。 ） （3）整数集合 I ＝ {?，-2，-l，0，l，2，?} =｛x?x 是正整数,或零,或负整数｝ （4）偶整数集合 E = {?，-4，-2，0，2，4，?}＝{x?x 是偶数} = {x?x?I 且 2?x} (2?x 表示 2 整除 x) （5）前 n 个自然数的集合 Nn＝{0，1，2，?，n-1} ＝{ x? x?N 且 0≤x＜n} （6）前 n 个自然数集合的集合 = {{0},{0 , 1}，{0，1，2}，?} = {x?x= Nn ?n?I+} = { Nn ?n? I+} 定义 1.1 没有任何元素的特定集合称为空集，记为 ?，即 ?＝{}＝{x? P(x)恒假}；由全 体对象组成的集合称为全集，记为 U，即 U = {x? P(x)恒真} 定义 1.2 空集和只含有有限多个元素的集合称为有限集（finite sets） ，否则称为无限集 （infinite sets） 。有限集合中成员的个数称为集合的基数（cardinatity） （无限集合的基数概念 将在以后严格定义） 。集合 A 的基数表示为 ?A ?。 例 1.3 例 1.2 之（l） （5）是有限集，其它为无限集。?{0，1}?=2，? ? ?＝0，?{?}? = 1。 即 ? 不同于{?}，前者是没有任何元素的集合，后者是恰含一个元素――空集的单元素集。 有些常用特定的集合通常用特定字母符号来表示。如：N 表示所有自然数组成的集合， I （Z）表示所有整数组成的集合，Q 表示所有有理数组成的集合，R 表示所有实数组成的集 合，C 表示所有复数组成的集合，Q+表示所有正有理数组成的集合，R-表示所有负实数组成 的集合，Nn 表示前 n 个自然数的集合。 21.1.3 外延性公理与子集合外延性公理是用于规定集合相等意义的重要约定。 外延性公理（extensionality axiom） ：集合 A 和集合 B 相等，当且仅当它们具有相同的 元素。也就是说，集合 A,B 满足 A=B，当且仅当对任意元素 x，x 属于 A 蕴涵 x 属于 B;反 之,x 属于 B 蕴涵 x 也属于 A 。 例 1.4 根据外延公理， {0，l}＝{ l，0}＝{xOx(x2 - 2x＋ l)＝ 0} = {x ?x＝1 或 x＝0} 因此，外延性公理事实上也确认了集合成员的“相异性”“无序性” 、 ，及集合表示形式 的多样性。 定义 1.3 集合 A 称为集合 B 的子集合（或子集，subsets） ，如果 A 的每一个元素都是 B 的元素，即,若元素 x 属于 A ,那么 x 属于 B。 A 是 B 的子集，表示为 A?B（或 B?A） ，读作“A 包含于 B” （或“B 包含 A”。A 不 ） 是 B 的子集用 A?B 来表示。 集合之间的子集关系或包含关系是集合之间最重要的关系之一。 读者必须彻底弄清集合 之间的子集关系和元素与集合之间的隶属关系这两个完全不同的概念。 例 1.5 {a，b} ? {a，c，b，d}，{a，b，c} ? {a，b，c}，{a} ? {a，b}，但 a ?{a，b}， 只有 a ? {a，b} 。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。 例如，{l}? {1，{l}}，且{1}? {1，{l}}。 关于子集关系我们有以下定理和定义。 定理 1.1 对任意集合 A，B，A＝B 当且仅当 A ? B 且 B ? A 。特别地，对任意集合 A, A ? A 。 证.由外延性公理和子集定义立即可得。 定理 1.2 对任意集合 A，A ? U。 此定理显然成立。 定理 1.3 设 A，B，C 为任意集合，若 A ? B , B ? C，则 A ? C。 证.设 x 为 A 中任一元素．由于 A ? B，因此 x?B;又因为 B ? C，故 x?C。这就是说， A 的所有元素都是 C 的成员，故 A ? C。 定理 1.4 对任何集合 A，? ? A。 证 假设 ? ? A，即 ? 不是集合 A 的子集，于是有元素 x??，但 x?A，而 x?? 与 ? 是空集矛盾，因此 ? ? A。 定理 1.5 空集是唯一的。 证. 设有空集 ?1, ? 2． 据定理 1.4， 应有 ?1 ? ?2 和 ?2 ? ?1， 从而由定理 1.1 知 ?1= ?2。 定理 1.6 设 A 为一有限集合，A ?n，那么 A 的子集个数为 2 。0 0 C n 个（ C n ＝1）; 恰含 A 中一个元素的n证 集合 A 的子集有：没有元素的子集 ?，计 子集计 n 个,恰含 A 中两个元素的子集计 因此 A 的子集个数为C12 n C n 个, ? , 恰含 A 中 n 个元素的子集计 C n 个。0 1 n C n + C n ＋?＋ C n = 2 n设集合 A = {1，?, {1, 3 }}, 则 A 有 2 = 8 个子集，分别为：?，{1}，{?}，{{1，3}}， {1，?}，{1，{1，3}}，{?，{1，3}}，{1，?，{1，3}}。 定义 1.4 集合 A 称为集合 B 的真子集，如 A?B 且 A ? B。 是 B 的真子集”记为 “A A?B。 显然，空集 ? 是所有非空集合的真子集。3练习 1.1l、证明：如果 A?{{b}}，那么 b?A。 2、用描述法表示下列集合： 3（1）A ＝｛1，3，5｝ （2）B = {2，3，5，7，11，13，17，?，89，97} （3）C＝｛ ， ， ， ，?， ｝ ｛0｝｛1｝｛2｝｛3｝ ｛9｝ （4）全集 U 3、对任意对象 a, b, c, d 证明： {{a}, {a,b}}＝{{c}, {c，d}} 当且仅当 a = c 且 b = d 4、指出下列集合序列的排列规律，并依此规律再写出两个后续集合： ? ， ｛?｝｛?,｛?｝ ， ｝,｛?， ｛?｝｛?， ， ｛?｝｝ ｝，┅ 5、 “如果 A?B, B?C，那么 A?C”对任意对象 A,B,C 都成立吗？都不成立吗？举例说 明你的结论。 6、确定下列各命题的真、假； （1）? ? ? （2）??? （3）? ?｛?｝ （4）??｛?｝ （5） b｝ ?｛a , b , c,｛a， b，c｝ ｛a, ｝ （6） b｝?｛a， b， c， ｛a, ｛a， b，c｝ ｝ （7） b｝?｛ ｛a, ｛a，b｝｛ ，｛a，b｝｝ ｝ （8） b｝?｛ ｛a, ｛a，b｝｛ ，｛a，b｝｝ ｝ （9）对任意集合 A，B，C，若 A?B，B ? C 则 A?C。 （10）对任意集合 A，B，C，若 A?B，B ?C 则 A ? C。 （11）对任意集合 A，B，C，若 A?B，B? C 则 A ? C。 （l2）对任意集合 A，B，C，若 A?B，B ?C 则 A ? C。 7、指出下列各组集合中的集合的不同之处，列出每一集合的元素和全部子集： （1） ｛?｝｛ ，｛?｝ ｝ （2） ｛a，b，c｝｛a， ， ｛b，c｝，｛a，b，c｝ ｝｛ ｝ 8、设 A，B 为任意集合证明：如果对任意的集合 C，C ? A 当且仅当 C ? B，那么 A ＝B。1.2集合运算集合运算指以集合为运算对象、以集合为值的运算。 本书中的符号“ ? ”表示术语“当且仅当” （if and only if）1.2.1 并、交、差、补运算并、交、差、补运算是集合的最基本的运算，读者在中学阶段也已有所接触。 定义 1.5 设 A，B 为任意集合。 （l） A∪B 称为 A 与 B 的并集（union set） ，定义为 A∪B＝｛xOx∈A 或 x∈B｝ ∪称为并运算。 （2） A∩B 你为 A 与 B 的交集（intersection set） ，定义为 A∩B =｛xOx∈A 且 x∈ B｝ ∩称为交运算。 （3） A-B 称为 A 与 B 的差集（difference set） ，定义为 A-B＝｛xOx∈A 且 x ? B｝ - 称为差运算。 （4）称为 A 的补集（complement set） ，定义为A =U-A =｛x ? x?A｝ 称为补运算，它是一元运算，是差运算的特例。 例 1.6 设 U＝{0, 1，2，3，?，9}，A = {2，4}，B = {4, 5, 6 ,7}， C = {0，8，9}，D ＝{l, 2, 3}： A?B＝｛2，4，5，6，7｝ A?B?C?D＝U ，C4A?B ＝｛4｝ ，A?C= ? A-B = {2}，B-A =｛5，6，7｝ - C =｛2，4｝ ，AA =｛0，l，3，5，6，7，8，9｝ B ＝｛0，l，2，3，8，9｝ ，定理 1.7 设 A，B，C 为任意集合，*代表运算 ? 或 ?，那么 （l） A ? A ? A （2） A ? B ? B ? A （等幂律） （交换律）（3） A ? ( B ? C ) ? ( A ? B) ? C （结合律） （4）A?? ＝A， A?U = U A?? = ?， A?U = A （5）A?(B?C)=(A?B) ?(A?C) A?(B?C)＝(A?B)?(A?C) （分配律） （6）A?( A?B)=A A?(A?B) =A （吸收律） 证 （1）（2）（3）由定义立得， ， ， ， （5）（6）的证明留给读者。现证（4） 。 对任意 x， x?A?? ? x?A 或 x?? ? x?A（x?? 为假） 故 A??＝A 。而 x?A?? ? x?A 且 x?? ? x??（ x?? 为假） 故 A?? = ? 。其余两式请读者补证。 定理 1.8 对任意集合 A，B，C， （l） （2）A ? A ? ?， A ? ?＝ A ， A ?U ? ? A ? ( B ? C ) ? ( A ? B) ? ( A ? C )A ? ( B ? C ) ? ( A ? B) ? ( A ? C )证 我们只证（2）中第一式，其余留给读者， 对任意 x，x ? A ? (B ? C) ? x ? A 且 x ? B ? C? x ? A且 x ? B 且 x ?C ? ( x ? A 且 x ? B) 且 ( x ? A且x ? C )? ( x ? A ? B) 且 ( x ? A ? C )? x ? ( A ? B) ? ( A ? C ) 故 A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) 。定理 1.9 对任意集合 A，BU ＝? , ? ＝U （2） A ? A ＝U , A ? A ＝? （3） A ? B ＝ A ? B（1） A ＝A ,A? B ＝ A? B（4） A ? B ＝ A ? B 证 （1）,（2）,（4）易证，现证（3）的第一式。A ? B ＝ U ? ( A ? B) ＝ (U ? A) ? (U ? B)＝ A? B 定理 1.10 对任意集合 A , B , C , D， （1） A ? A ? B 5（2） A ? B ? A （3） A ? B ? A （4） A ? B , A ? B ? ?, A ? B ? B ,A ? B ? A 四命题等价。（5）若 A ? B ,则 B ? A 。 证（1）（2）（3）,（5）易证，我们仅证明（4） ， ， 。 设（4）中 4 个命题为 P, Q, R, S ，我们来证明 P?Q?R?S?P（? 表示“推出” ）,从 而证实 4 命题等价。 （P?Q） ：设 A C B ? ?，则有 a?A C B，即 a?A，但 a?B，这与 A ? B 矛盾。故 A C B = ? 。得证。 （Q?R） ：为证 A?B = B ，需证 1）B ? A?B 。但由定理 1.10 之(1)，此已得证。 2）A?B ? B 。为此设 x 为 A?B 中任一元素，从而 x?A 或 x?B。当 x?B 时目的已达 到。当 x?A 时，若 x?B，则 x?A C B，此与 A C B = ? 矛盾。故 x?B。总之，A?B 中元素 x 必为 B 中元素，2）又得证。综合 1） 2）可知 A?B = B 。 、 （R?S） ：因 A?B = B，故 A?B = A?(A?B) =A(吸收律) （S?P） 设 A?B = A。 ： 要证 A?B， 现设 x 为 A 中任一元素。 A?B = A， 由 可得 x? A?B 从而知 x? B。故 A?B 得证。 定理 1.11 对任意集合 A，B．若它们满足 （l） A ? B ? U （2） A ? B ? ? 那么 B ? A B ? B ?? 证 ＝ B ? ( A ? A) ) ＝ ( B ? A) ? ( B ? A) ＝ U ? ( B ? A) ＝ ( A ? A) ? ( B ? A) ＝ ( A ? B) ? A ＝? ? A ＝A 本定理的证明思路是利用已知等式进行推演， 这种证明集合等式的方法简明， 但难度有 时较大。本定理还可直接用外延性公理来证，这种方法虽较繁锁，但思路清晰，易掌握。先 证 B ? A 。设 x?B，由于 A?B=?，故 x?A,即 x? A ，B? A 得证。再证 A ?B。设 x? A ， 则 x?A;由于 A?B＝U，故必有 x?B， A ?B 又得证。因此 B＝ A 。1.2.2 幂集运算和广义并、交运算 定义 1.6 对任意集合 A， ? ( A) 称为 A 的幂集（power sets） ，定义为? ( A) ? {X X ? A}即 A 的全体子集组成的集合是 A 的幂集。 由于，??A, A?A 故必有 ? ? ? ( A) , A ? ? ( A) 。 例 1.7（1）A=｛a，b｝时， ? ( A) ＝｛?， ， ， ｛a｝｛b｝｛a，b｝。 ｝ 6（2）A=｛0，{1，2}｝时， ? ( A) ＝｛?， ， ，{｛1，2｝}｛0，{1，2｝}｝ ｛0｝｛1｝ 。 定理 1.12 设 A,B 为任意集合, A?B 当且仅当 ? ( A) ? ? (B ) 。 证 我们曾指出，当集合 A 的基数为 n 时，A 有 2n 个子集，因此| ? ( A) |= 2n 。 先证必要性。设 A?B。为证 ? ( A) ? ? (B ) ，又设 X 为 ? ( A) 中任一元素，从而X?A。由于 A?B，故 X?B，从而有 X? ? (B ) 。 ? ( A) ? ? (B ) 得证考虑单元素集合｛a｝｛a｝? ? ( A) ，但｛a｝? ? (B ) ，与 ? ( A) ? ? (B ) 矛盾，A?B 得证。 ， 为了讨论广义的并、交运算，需要以下术语。 定义 1.7 若集合 C 的每个元素都是集合，则称 C 为集合族（collections） 。若集合族 C 可表示为 C =｛Sd|d ?D｝ 则称 D 为集合族的标志集（index set） 。 例 1.8 C =｛ ， ｛0｝｛0，1｝｛0，1，2｝, ?｝为一集合族,它没有标志集。若集合族 C = ， ｛A1，A2，A3, ?｝,则 C 的标志集为正整数集 I+；集合族 C＝｛S 甲，S 乙， S 丙｝ ，则 C 的 标志集为集合｛甲，乙，丙｝ 。 定义 1.8 设 C 为集合族，且 C 非空。 （l）再证充分性。设 ? ( A) ? ? (B ) ，反设 A?B 不成立，那么至少有一元素 a?A，但 a?B 。? C ? ?x : 有S使S ? C且x ? S? （2） ? C 称为 C 的广义交。定义为 ? C ? ?x : 对所有S ? C均有x ? S )? （3）当集合族 C =｛Ad|d ?D｝时， ? C 和 ? C 可分别表示为? C ? ? Add ?D?? C 称为 C 的广义并，定义为?C ?d?D ， 当 D 为自然数集 N 时，它们又可分别表示为?Ad? C ? ? Add ?0， 显然，当 C ＝｛A，B｝时， 例 1.9? C ? ? Add ?0??C ? A? B，?C ? A? B（1）当 C =｛ ， ｛0｝｛0， 1｝｛0， l， 2｝ ， ，?｝时， ? C ＝N， ? C ＝｛0｝ 。 （2）当 C＝｛S1，S2，S3｝时，?C ??C ?d ??1, 2 , 3???S d ? ? S d ? S1 ? S 2 ? S 3d ?133d ??1, 2 , 3?S d ? ? S d ? S1 ? S 2 ? S 3d ?1定理 1.13 对任意集合 A 和集合族 C，有A ? (?C ) ? ??A ? S : S ? C? A ? (?C ) ? ??A ? S : S ? C?x ? A ? (?C ) ? x ? A并且有S ? C使得x ? S7证 我们只证第一式，第二式雷同。 设 x 为任一元素，? 有S ? C使得( x ? A且x ? S ) ? 有S ? C使得x ? A ? S 故 A ? (?C ) ? ??A ? S : S ? C? 定理 1.14 对任意集合 A 和集合族 C，有 ? x ? ??A ? S : S ? C?A ? (?C ) ? ??A ? S : S ? C? A ? (?C ) ? ??A ? S : S ? C?证 证第一式，第二式留给读者． 故 x? ? ?A ? S : S ? C?。反之，设 x ? ??A ? S : S ? C?，则对每一 S?C，均有 x?A-S， 从而 x?A 且对每一 S?C，x?S，此即 x?A 而 x? ? C ，故 x ? A ? (?C ) 。 两方面的证明证实 A ? (?C ) ? ??A ? S : S ? C?。 定理 1.14 的自然推论是 定理 1.15 对任意集合族 C 有 设 x ? A ? (?C ) ，那么 x?A，且对每一个 S?C，x?S。于是，对每一 S?C，x?A-S，( ?C ) ? ? ??S ? : S ? C( ?C ) ?? ? ??S : S ? C ??定理 1.16 对任意集合 A, 证 设 x 为任一元素，? ? ( A) ? A ．故 ? ? ( A) ? A .x ? ? ? ( A) ? 有S ? ? ( A)使得x ? S ? 有S ? A使得x ? S ? x?A1．2．3 集合的笛卡儿积 定义 1.9 设 a ， b 为任意对象，称集合 {{a}, {a, b}} 为二元有序组，或序偶（ordered pairs） ，简记为 ? a, b ? 。称 a 为 ? a, b ? 的第一分量，称 b 为第二分量。注意，第一、二分量可以相同。 定理 1.17 对任意序偶 ? a, b ? , ? c, d ? , ? a, b ? = ? c, d ? 当且仅当 a ? c, 且b?d。证 其充分性是显然的。 为证必要性，设 ? a, b ? = ? c, d ? ，那么{{a}, {a, b}} ＝ {{c}, {c, d}}（1－1）? {{a}, {a, b}} ＝ ? {{c}, {c, d}} {a, b} ＝ {c, d } ? {{a}, {a, b}} ＝ ? {{c}, {c, d }} 以及 {a} ＝ {c} 由式（1－2） ，式（1－3）两式知 a ? c, b ? d 。（1－2）（1－3）? 因此， 要充分注意 ? a, b ? 与 {a, b} 的区别， 即当 a≠b 时， a, b ? ≠ ? b, a ? ， 但{a， b}={b,a}; &a,a&≠&a&,但 {a,a}={a}. 定义 1.10 定义 n 元序组 &a1，?，an& ： &a1，a2& =｛ 1｝｛a1 , a2｝ ｛a ， ｝8&a1，a2，a3& = &&a1，a2&，a3& ?? &a1，?，an& = &&a1，?，an-1&, an& 本质上, n 元序组依然是序偶。ai 称为 n 元序组的第 i 分量。 定理 1.18 对任意对象 a1，?，an，b1，?，bn， &a1，?，an& = & b1，?，bn &当且仅当 a1 = b1 ，?，an= bn 证明略。 显然，序偶和 n 元序组都是集合，但由于它们的特殊结构，把次序赋予了有关对象，我 们以后更多关心的是它们的这种“序特性” 。而较少谈论定义它们的原有的集合结构细节。 定义 1.11 对任意集合 A1，A2 , ?，An，定义 A1 ? A2 ? ? ? An ： A1 ? A2，称为集合 A1 , A2 的笛卡尔积(Cartesian product)，定义为 A1 ? A2=｛&u,v& ? u ?A1,v?A2｝ A1 ? A2 ? A3= (A1 ? A2)? A3 ?? A1 ? A2 ? ? ? An= (A1 ? A2 ? ?? An-1 )? An 当 A1 = A2 = ? =An =A 时，A1 ? A2 ? ? ? An 简记为 An 定理 1. 19 对任意集合 A1，A2 , ?，An， A1 ? A2 ? ? ? An=｛&& a1, ?, an-1&, an& ? a1 ?A1,?,an ?An｝ 本定理同样是易于证明的，请读者完成之。 例 1.10 设 A =｛1 , 2｝ = ｛a , b, c｝ =｛?｝, R 为实数集， ，B ，C 那么 （l） A?B =｛&1, a&，&l, b&，&1, c&，&2, a&，&2, b&，&2, c&｝ B?A＝｛&a, 1&，&b, 1&，&c, 1&，&a, 2&，&b, 2&，&c, 2&｝ （2）A?B?C = ( A?B)?C =｛&1, a, ?&，&l, b, ?&，&1, c, ?&，&2, a, ?&，&2, b, ?&， &2, c, ?&｝ A? ( B?C ) =｛&1, &a, ?&&，&l, &b, ?&&，&1, &c, ?&&，&2, &a, ?&&，&2, &b, ?&&， &2, &c, ?&&｝ （3）A?? = ??A = ? （4）R2 =｛&u,v& ? u ,v 是实数｝ 2 为笛卡儿平面。显然 R3 为三维笛卡儿空间． ，R 我们注意到，一般地 A?B ? B?A，(A?B)?C ?A?(B?C) 。此外，? 也用来表示不含任 何序组的笛卡儿积。 关于笛卡儿积有以下性质。 定理 1.20 设 A, B, C 为任意集合，*表示 ?，? 或 C 运算， 那么A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) ( B ? C ) ? A ? ( B ? A) ? (C ? A) 证 我们仅证明 A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) 和 A ? ( B ? C ) ? ( A ? B) ? ( A ? C )对任意 x，y， &x, y& ? A?(B ? C) ? x? A 且 y?(B ? C) ? x? A 且(y?B 或 y?C) ? (x? A 且 y?B)或(x? A 且 y?C) ? &x, y& ? A?B 或&x, y& ? A?C ? &x, y& ? (A?B) ?(A? C) 为证第二式， 设&x, y&为 A?( B C C)中任一序偶， 那么 x? A , y?B， y?C， 从而&x,y&?A?B， &x,y&?A?C，即&x,y&?A?B C A?C , A?(B C C) ? (A? B) C (A ? C) 得证。另一方面，设&x,y& 为(A? B) C (A ? C)中任一序偶，那么&x,y&?A?B，&x,y&?A?C，从而 x?A，y?B, y?C（否 则由于 x?A，&x,y&?A?C ） ，故可知 y?B C C ，&x,y&? A?(B C C)，于是(A? B) C (A ? C) ? A?(B C C)得证。这就完成了 A?(B C C)＝(A? B) C (A ? C) 的证明。 定理 1.21 对任意有限集合 A1，?，An，有: 9A1 ? ? ? An ? A1 ? ? ? An这是十分直观的，证明省略。 ? 定理 1.22 对任意非空集合 A，B， （l） ? (?( A ? B)) ? A ? B （2） A ? B ? ? ( ? ( A ? B) 证( 其中?为数乘运算)? (?( A? B))= ? (??? a, b ?: a ? A ? b ? B?)? , ? ＝ ? (?? ?a? ?a, b? : a ? A ? b ? B?)＝? ( ? ??a???a?Aa?A?b?B???a, b??)? ? ) ＝ ? (? a?: a ? A?? ? a, b?: a ? A ? b ? B?=a?A? ?a??a?A?b?B??a, b?= A ? ( A ? B) = A? B （2）设&x,y&为 A?B 中任一序偶，即 x?A，y?B 。现需证 由于 x?A,故｛x｝? ρ(A?B)；又由于 x?A，y?B，故｛x,y｝? ? ( A ? B) 。因此， ｛ ｛x｝,｛x,y｝ ? ( A ? B) ｝? 即｛ ｛x｝,｛x,y｝ ｝? ? ( ? ( A ? B)) 。故 A ? B ? ? ( ? ( A ? B) 。 事实上，结论（1） （2）对 A，B 为空集时也真。 &x,y& =｛ ｛x｝,｛x,y｝ ｝? ? ( ? ( A ? B))练习 1.2l、证明定理 1.7 之（5） 。 2、证明定理 1.8 之（2）中的第二式。 3、证明定理 1.9 之（4） 。 4．试以下列次序证明定理 1.10： P?R?S?Q?P 5．对任意集合 A，B，C，证明：( A ? C) ? (B ? C) ? A ? B6．对任意集合 A，B，C，证明： （1） A ? ( B ? C ) ? ( A ? B) ? C ? ( A ? C ) ? B （2） ( A ? B) ? C ? A ? ( B ? C ) ? ( A ? C ) ? B （3） ( A ? B) ? C ? A ? ( B ? C ) 当且仅当 A ? C ? ? （4） ( A ? B) ? C ? ( A ? C ) ? ( B ? C ) 7．证明：对任意集合 A，B 下列命题等价， （1） A ? B （2） A ? B = U （3） A ? B = ? 8．设 A = ???，B = ?1，2?，求 ? ( ? ( ? ( A))) ， ? ( ? ( B)) 。 9．对任意集合 A，B。求证： （1）A = B 当且仅当 ? ( A) = ? (B)10（2） ? ( A) ? ? (B) ＝ ? ( A ? B) （3） ? ( A) ? ? (B) ? ? ( A ? B) 10. 若 C ={{ x} x ? B}{ {x} : x?B} 求 ? C 。11. 对下列诸 C，求 ? C 和 ? C 。 （1）C =｛?｝ （2）C =｛?， ｛?｝ ｝ （3）C = {{a}, {b}, {a, b}} （4）C = ? ( ? ( N )) 12．对任意非空集合族 C1，C2，证明： （1） (?C1) ? (?C 2) ? ?(C1 ? C 2) （2） (?C1) ? (?C 2) ? ??S1 ? S 2 : S1 ? C1 ? S 2 ? C 2? （3） (?C1) ? (?C 2) ? ??S1 ? S 2 : S1 ? C1 ? S 2 ? C 2? （4） (?C1) ? (?C 2) ? ?(C1 ? C 2) 13．设 A = {1, 2, 3}, R 为实数集,请在笛卡儿平面上表示出 A?R 和 R?A 。 14．以下各式是否对任意集合 A，B，C，D 均成立？试对成立的给出证明，对不成立 的给出适当的反例。 （1） ( A ? B) ? C ? ( A ? B) ? ( A ? C ) （2） ( A ? B) ? (C ? D) ? ( A ? B) ? (C ? D) （3） ( A ? B) ? (C ? D) ? ( A ? C ) ? ( B ? D) （4） ( A ? B) ? (C ? D) ? ( A ? C ) ? ( B ? D) 15．设 A , B , C , D 为任意集合，求证： （1）若 A ? C, B ? D ，那么 A ? B ? C ? D 。 （2）若 C ? ? , A ? C ? B ? C ，则 A ? B 。 （3） ( A ? B) ? (C ? D) ? (( A ? C ) ? B) ? ( A ? ( B ? D)) 1.3 集合的归纳定义1.3.1 集合的归纳定义我们已经提到集合有三种表示方式，其中之一是归纳定义（inductive definition） 。现在 我们要来介绍什么是归纳定义。 集合的归纳定义由三部分组成: （1）基础条款：规定待定义集合以某些元素为其基本成员，集合的其它元素可以从它 们出发逐步确定。 （2）归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则。于是，可以 从基本元素出发，反复运用这些规则来确认待定义集合的所有成员。 （3）终极条款：规定待定义集合只含有（l）（2）条款所确定的成员。 ， 条款（l）（2）又称归纳定义的完备性条款，它们必须保证毫无遗漏地产生出待定义集 ， 合的全部成员；条款（3）又称归纳定义的纯粹性条款，它保证整个定义过程所规定的集合 只包括满足要求的那些对象。 例 1.11 设 U 为整数集 I，现用归纳定义规定偶数集 E： （l）基础条款：0 ? E． （2）归纳条款：若 x?E，则 x+2?E, x-2?E． （3）终极条款：除有限次使用（l）（2）条款确定的元素外，E 中没有别的元素。 ， 许多关于形式语言（例如一阶谓词演算系统的语言、计算机程序设计语言等）的概念及 形式语言本身，都是归纳定义的。 11通常把一个非空符号集合称为字母表，常用Σ 表示之，Σ 上的字（即符号串）的概念可 + 如下归纳定义。用Σ 表示Σ 上的字的集合。 + （1）基础条款：Σ ?Σ 。 + + （2）归纳条款：若ξ ?Σ ，w?Σ 则ξ w?Σ 。 （这里ξ w 表示字符号ξ 与字符串 w 的 并置，或毗连，即自然连接） 。 + （3）终极条款：除有限次使用（l）（2）条款确定的元素外，Σ 中没有别的元素。 ， + * 如果用λ 表示空字（即空符号串，对任何字 w，λ w = wλ = w） ，记Σ ??λ ?=Σ 。当 * 然也可以用归纳定义来规定Σ 。 * 符号串集合 L 称为Σ 上的一个形式语言(formal languages)，如果 L?Σ 。 字头、字尾的概念也是形式语言中常用的。它们也可以归纳地定义。先定义字 w 的字 头 w’的概念: （1）基础条款：λ 是 w 的字头。 * （2） 归纳条款： w’为 w 的字头， = w’ ξ w’’ 若 w （其中ξ ?Σ , w’,w’’ ?Σ ） 那么 w’ ξ ， 也是 w 的字头。 （3）终极条款（略） 。 当 w’为 w 的字头，w = w’ w’’，则称 w’’为 w 的字尾。对字尾也可以直接作归纳定义。 + + 例 1.12 设Σ 为数字集 D＝｛0，l，2，?，9｝ ，那么Σ ＝D 可看作为全体自然数的集 * 合。 当Σ ＝ ｛a,b｝ 时， = Σ ｛λ , a , b ， ab， aa， ba， bb， 。 ｛λ ， ?｝ L＝ ab， aabb， aaabbb， ?｝ * ?Σ ，L 为Σ 上的一个语言（请读者归纳定义之） 之中所有字的字头中 a 的数目不少于 b 。L 的数目，字尾中 a 的数目不多于 b 的数目。 最后一个例子说明归纳定义在计算机科学中有十分广泛的应用。 例 1.13 假定我们已经规定了“变元集”“算术表达式集”“条件语句集” 、 、 ，现归纳定 义“while 程序集” ，记为 WP。 （1）基础条款：V←E 在 WP 中。其中 V 为变元，E 为算术表达式。 （2）归纳条款： （2.l）若 C 为条件语句， P1，P2 为 whlile 程序，则 if C then P1 else P2 end if 在 WP 中。 （2.2）若 C 为条件语句，P 为 while 程序．则 while C do P end while 在 WP 中。 （2.3）若 P1，P2 为 whlile 程序，则 P1；P2 在 WP 中。 （3）终极条款（略） 。 *1.3.2 集合定义的自然数 本章一开始我们就指出，集合论开创的初衷就是要为数学奠基,为此首先要在集合论中 定义最基础的数学概念：自然数（它原本是不作定义的原始概念） ，即用集合来定义自然数。 由于这一定义可用归纳定义的形式给出，因而正好成为一个归纳定义的生动的例子。 自然数是大家熟悉的。从本质上看，它们是满足下列特性的一列符号； （1）它们中有一个为首的符号。 （2）每个符号都有且仅有一个直接的后继符号。 （3）为首的符号不是任何符号的直接后继符号。 （4）没有两个符号具有相同的直接后继符号。 （5）自然数仅指这列符号中的符号。 由于自然数的一切性质均可以从这五个特性推得，因此皮亚诺（Peano）用五条公理刻 划自然数概念： P1．至少有一个客体是自然数，它被记为 0。 P2．如果 n 是自然数，那么 n 必定恰有一个直接后继者，记为 n’。 P3．0 不是任何自然数的直接后继。 P4．如果自然数 m，n，的直接后继 m’,n’相同，那么 m = n。 P5．没有不满足上述条件的客体是自然数。 现在我们需要在集合论中，实实在在地拿出一列符号来，并使它们满足这五条公理，从 而定义出自然数。 一种容易想到的定义自然数集合 N 的方式是： 12（1） 0?N 。 （2）如果 x?N ,则 x+1?N 。 （3） （终极条款） 。 但这一定义是不适当的。 为何物？集合否？”,“尚无自然数时，加 1 意义何在？”为了 “0 在集合论中定义自然数，首先要选择一个集合，例如 ?，作为为首的自然数，并给 ? 起一 个自然数名“0” 。其次需确定一种集合运算，作为求直接后继的运算。 定义 1.12 （1）称空集 ? 为自然数，记为 0。 （2）称 A’为集合 A 的直接后继，如果 A’＝A ?｛A｝ 例 1.14｛a，b｝ ’＝｛a，b， ｛a，b｝ ｝ ?’＝? ?｛?｝= ｛?｝ ｛?｝ ’= ｛?｝?｛ ｛?｝ ｝= ｛?,｛?｝ ｝ ｛?,｛?｝’=｛?,｛?｝,｛?,｛?｝｝ ｝ ｝ 定义 1.13 归纳定义自然数集 N： （l）基础条款：??N 。 （2）归纳条款：如果 x?N ，则 x’= x ?｛x｝? N。 （3）终极条款（略） ． 按照上述定义。自然数集 N 由下列元素组成： ?， ｛?｝｛?， ， ｛?｝， ｝｛?， ｛?｝｛?， ， ｛?｝｝ ｝，? 或 0，0’ ，0’，? ，0” ” 将它们依次表示为 0，1，2，3，? 这样定义的自然数的表示形式是有趣的： 1 ＝｛0｝ ，2 ＝｛0，l｝ =｛0，l，2｝ ，3 ，?，n ＝｛0，l，2，?，n-1｝ 这是因为 n ＝（n-1）?｛n-1｝ （当 n ? 0 时） 。 现在我们来证明, 如上定义的自然数满足皮亚诺的五条公理。事实上只要证明它们满足 P1―P4． P1 显然被满足，至少有 ? 作为自然数 0 在 N 中。 为证 P2，设 n 为一自然数。首先， n 有后继 n’＝n ?｛n｝ 。其次可证 n’是唯一的， 因为 n ?｛n｝＝｛0，l，2，?，n｝是唯一确定的集合。 为证 P3，反设 ? 是自然数 n 的后继。n’＝ n ?｛n｝ ，从而 ?＝ n ?｛n｝ ，但这是 不可能的，因为右边至少有元素 n 。因此 ? 不是任何自然数的后继。 为证 P4，反设有自然数 m，n，m’= n’ ，但是 m ? n 。 由于 m’= n’ ?｛m｝= n ?｛n｝ ，m 。因 m ? n，故总有元素 x?m, 但 x?n; 或 x?n, 但 x?m。不妨设 x?m,但 x?n 。于是我们有 x?m ?｛m｝= n ?｛n｝ ，进而知 x? n ?｛n｝ 。由 于 x?n，故 x?｛n｝ ，即 x＝n。这样便有 x＝n?m 。由 n?m 可导出 m ? n，m?n 。这与 m ? ｛m｝= n ?｛n｝矛盾，因为左边集合以 m 为元素，右边集合决无元素 m 。矛盾的导出表 明 m = n，P4 得证。 有了自然数，便可以定义自然数集合上的运算和函数。关于这一点我们留待第 11 章讨 论。练习 1.31．归纳定义 ? （? ＝? ????） ，令 ?= ?a，b?。 2．令 ?= ?a,b,c?，归纳定义： （l） L ? ?*，使 L 中所有字里都有字 ab 的出现，且所有含字 ab 的字全在 L 中。 （2） L ? ?*，使 L 中所有字里都含有字符 a 和 b，且所有含字符 a,b 的字全在 L 中。 3．归纳定义下列集合： （1）十进制无符号整数集合，非零数不得以 0 为字头。 （2）十进制非负有穷小数。* * +13（3）全体十进制有理数(分数)。 （4）二进制形式的非负偶数，非零数不得以 0 为字头 4．数学表达式中允许出现的括号的嵌套和毗连所形成的括号串称为成形括号串。归纳 定义成形括号串集合（假定它含有空括号串 ?） 。 5．直接归纳定义形式语言中字尾的概念。14第 1 章 集合代数集合理论是一门研究数学基础的学科，它试图从一个比“数”更简单的概念――集合 （sets）出发，定义数及其运算，进而发展到整个数学。集合理论产生于 16 世纪末。当时， 只是由于微积分学的需要，人们仅对数集进行了研究。19 世纪末，即 1876 一 1883 年间， 康托尔 （Georg Cantor 1845 一 1918 年,德国数学家） 对任意元素的集合进行了系统的研究。 康托尔被公认为集合理论的创始人。[1] 人们称康托尔开创的集合理论为朴素集合论，因为他没有对集合论作完全公理化的描 述，从而导致了理论的不一致（产生了悖论） 。为弥补朴素集合理论的不足，本世纪初出现 了各种公理化集合论体系,为数学奠定了一个良好的基础。更有意义的是，从此集合基本概 念不断深入人心， 被广泛地应用于数学理论和其他学科的基础研究和实际应用中， 集合论的 原理和方法成为名副其实的数学基本技术。基于本书的教学目的，以“集合代数”为标题的 本章，主要讨论集合基本概念和集合运算。它与第二章在一起，被视为全书学习所必备的最 基本的数学知识和工具，在以后讨论的内容中将不断地运用它们。因此，本章将不涉及公理 化集合论体系。 事实上， 集合不仅可用来表示数及其运算， 更可以用于非数值信息及离散结构的表示和 处理。像数据的删节、插入、排序，数据间关系的描述，数据的组织和查询都很难用传统的 数值计算来处理，但可以用集合运算来实现。集合论被广泛应用在计算机科学中，如数据结 构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、 CAD 等，这也是本章学习集合理论基础知识的目的。1.1 集合的概念与表示 1.1.1 集合及其元素在中学的数学课程中,大家对集合及其元素的意义已经有所了解,因此， 下面我们做些简 要的回顾。 集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。 严格地说这不是集合的定义，因为“总体”只是“集合”一词的同义反复。实际上，在 集合论中，集合是一个不作定义的原始概念（就像几何学中的点、线、面等概念） 。不过， 上述关于集合概念的描述，有益于对它的内涵和外延作直观的理解和认识。 例 1.1 （1） “北洋大学全体学生”为一集合，组成这一集合的对象是北洋大学的学生。 （2） “全体正整数”为一集合，其组成对象是正整数。 （3） “本书中所有汉字”的集合，其组成对象是本书的汉字。 （4） “获 1988 年诺贝尔文学奖的作家”构成一个集合，尽管它只有一个对象――埃及 作家纳吉布 ?马夫兹。 “获 2002 年诺贝尔生理学或医学奖的科学家”构成一个集合，它包括 英国科学家悉尼 ?布雷内,美国科学家罗伯特 ?霍维茨,英国科学家约翰 ?苏尔斯顿三名成 员。 （5） “解放军理工大学所有学员队”的集合，其组成对象是学员队，而不是学员，因为 集合中对象是整体识别的，尽管学员队又是学员的集合。 （6） “好书的全体”不构成集合，因为难以对每一本书的好坏作出确定的判断。 （7） “方程 x(x2-2x+1)=0 的所有根”组成一个集合，它只有一个对象 0 和一个（而不是 两个）对象 1，因为集合中对象是相互区别的。 （8） “方程 x2 +x+1=0 的根”组成一个集合。当在复数域上讨论时，它由两个对象组成； 而当在实数域上讨论时，它不含有任何对象，是一个特定集合。 组成集合的对象称为集合的成员或元素（members） 请注意，这里“对象”的概念是相当普遍的，可以是任何具体的或抽象的客体，还可以 又是集合， 因为人们有时以集合为其讨论的对象， 而又需涉及它们的一个总体――以集合为 其元素的集合。例如，例 1.1（5 ）的集合，以学员队集体为其元素；又如集合{1，{1，2}， {1}，2}，数 1，2 是它的成员，集合{1}和{1，2}也是它的成员。因此，尽管集合与其成员 是两个截然不同的概念，但一个集合完全可以成为另一个集合的元素。因此必须注意，a 不 同于{a}，前者为一对象 a，后者为仅含该对象 a 的单元素集合；同样，{a}≠{{a}}，{{a}}是 15仅含{a}的单元素集。 通常用大写拉丁字母 A，B，C 等表示集合，用小写字母 a, b, c 等表示集合的元素。 但是，由上可知，这种表示形式不是绝对的。a 作为 A 的元素时，并不排斥 a 作为集合的可 能性。同样，集合 A 也可能是别的集合的元素。 元素对于集合的隶属关系是集合理论的另一基本概念。当对象 a 是集合 A 的成员时， 称 a 属于 A，记为 a∈A 当对象 a 不是集合 A 的成员时，称 a 不属于 A，记为 a?A 对任何对象 a 和任何集合 A，或者 a?A 或者 a?A,两者恰居其一。这正是集合论对其元素的 “确定性”要求。1.1.2 集合的表示集合的表示方式主要有以下三种： （l）列举法：表示一个集合 A 时，将 A 中元素―一列举，或列出足够多的元素以反映 A 中成员的特征，其表示形如 A ＝｛a1，a2，?，an｝或 A =｛a1，a2，a3, ?｝ （2）描述法；表示一个集合 A 时，将 A 中元素的特征用一个性质来描述，其表示形式 如 A =｛x ? P(x)｝或 A =｛x : P(x)｝ 其中 P(x)表示“x 满足性质 P”或“x 具有性质 P” =｛x ? P(x)｝或 A =｛x : P(x)｝的意义 。A 是：集合 A 由且仅由满足性质 P 的那些对象所组成，也就是说 a?A 当且仅当 a 满足性质 P（或 P(a)真） 例题 1.1 中的集合都是采用这种方式表示的。 （3）归纳法：将在 1.3 节中详细介绍。 例 1.2 以下是常常要用到的一些集合以及它们的表示。 （1）{0，l}＝{x?x＝0 或 x＝l} （2）自然数集合 N = {0，1，2，3，?} = {x?x 是自然数} 正整数集合 I+ = {1，2，3，?} = {x?x 是正整数} （注意， 这里我们所说的自然数集合与中学课本定义的自然数集合略有不同, 它使自然数 集合有别于正整数集合, 自然数集合包括数 0,这是计算机科学的一个通常做法。 ） （3）整数集合 I ＝ {?，-2，-l，0，l，2，?} =｛x?x 是正整数,或零,或负整数｝ （4）偶整数集合 E = {?，-4，-2，0，2，4，?}＝{x?x 是偶数} = {x?x?I 且 2?x} (2?x 表示 2 整除 x) （5）前 n 个自然数的集合 Nn＝{0，1，2，?，n-1} ＝{ x? x?N 且 0≤x＜n} （6）前 n 个自然数集合的集合 = {{0},{0 , 1}，{0，1，2}，?} = {x?x= Nn ?n?I+} = { Nn ?n? I+} 定义 1.1 没有任何元素的特定集合称为空集，记为 ?，即 ?＝{}＝{x? P(x)恒假}；由全 体对象组成的集合称为全集，记为 U，即 U = {x? P(x)恒真} 定义 1.2 空集和只含有有限多个元素的集合称为有限集（finite sets） ，否则称为无限集 （infinite sets） 。有限集合中成员的个数称为集合的基数（cardinatity） （无限集合的基数概念 将在以后严格定义） 。集合 A 的基数表示为 ?A ?。 例 1.3 例 1.2 之（l） （5）是有限集，其它为无限集。?{0，1}?=2，? ? ?＝0，?{?}? = 1。 即 ? 不同于{?}，前者是没有任何元素的集合，后者是恰含一个元素――空集的单元素集。 有些常用特定的集合通常用特定字母符号来表示。如：N 表示所有自然数组成的集合， I （Z）表示所有整数组成的集合，Q 表示所有有理数组成的集合，R 表示所有实数组成的集 合，C 表示所有复数组成的集合，Q+表示所有正有理数组成的集合，R-表示所有负实数组成 的集合，Nn 表示前 n 个自然数的集合。 161.1.3 外延性公理与子集合外延性公理是用于规定集合相等意义的重要约定。 外延性公理（extensionality axiom） ：集合 A 和集合 B 相等，当且仅当它们具有相同的 元素。也就是说，集合 A,B 满足 A=B，当且仅当对任意元素 x，x 属于 A 蕴涵 x 属于 B;反 之,x 属于 B 蕴涵 x 也属于 A 。 例 1.4 根据外延公理， {0，l}＝{ l，0}＝{xOx(x2 - 2x＋ l)＝ 0} = {x ?x＝1 或 x＝0} 因此，外延性公理事实上也确认了集合成员的“相异性”“无序性” 、 ，及集合表示形式 的多样性。 定义 1.3 集合 A 称为集合 B 的子集合（或子集，subsets） ，如果 A 的每一个元素都是 B 的元素，即,若元素 x 属于 A ,那么 x 属于 B。 A 是 B 的子集，表示为 A?B（或 B?A） ，读作“A 包含于 B” （或“B 包含 A”。A 不 ） 是 B 的子集用 A?B 来表示。 集合之间的子集关系或包含关系是集合之间最重要的关系之一。 读者必须彻底弄清集合 之间的子集关系和元素与集合之间的隶属关系这两个完全不同的概念。 例 1.5 {a，b} ? {a，c，b，d}，{a，b，c} ? {a，b，c}，{a} ? {a，b}，但 a ?{a，b}， 只有 a ? {a，b} 。不过存在这样两个集合，其中一个既是另一个的子集、又是它的元素。 例如，{l}? {1，{l}}，且{1}? {1，{l}}。 关于子集关系我们有以下定理和定义。 定理 1.1 对任意集合 A，B，A＝B 当且仅当 A ? B 且 B ? A 。特别地，对任意集合 A, A ? A 。 证.由外延性公理和子集定义立即可得。 定理 1.2 对任意集合 A，A ? U。 此定理显然成立。 定理 1.3 设 A，B，C 为任意集合，若 A ? B , B ? C，则 A ? C。 证.设 x 为 A 中任一元素．由于 A ? B，因此 x?B;又因为 B ? C，故 x?C。这就是说， A 的所有元素都是 C 的成员，故 A ? C。 定理 1.4 对任何集合 A，? ? A。 证 假设 ? ? A，即 ? 不是集合 A 的子集，于是有元素 x??，但 x?A，而 x?? 与 ? 是空集矛盾，因此 ? ? A。 定理 1.5 空集是唯一的。 证. 设有空集 ?1, ? 2． 据定理 1.4， 应有 ?1 ? ?2 和 ?2 ? ?1， 从而由定理 1.1 知 ?1= ?2。 定理 1.6 设 A 为一有限集合，A ?n，那么 A 的子集个数为 2 。0 0 C n 个（ C n ＝1）; 恰含 A 中一个元素的n证 集合 A 的子集有：没有元素的子集 ?，计 子集计 n 个,恰含 A 中两个元素的子集计 因此 A 的子集个数为C12 n C n 个, ? , 恰含 A 中 n 个元素的子集计 C n 个。0 1 n C n + C n ＋?＋ C n = 2 n设集合 A = {1，?, {1, 3 }}, 则 A 有 2 = 8 个子集，分别为：?，{1}，{?}，{{1，3}}， {1，?}，{1，{1，3}}，{?，{1，3}}，{1，?，{1，3}}。 定义 1.4 集合 A 称为集合 B 的真子集，如 A?B 且 A ? B。 是 B 的真子集”记为 “A A?B。 显然，空集 ? 是所有非空集合的真子集。3练习 1.1l、证明：如果 A?{{b}}，那么 b?A。 2、用描述法表示下列集合： 17（1）A ＝｛1，3，5｝ （2）B = {2，3，5，7，11，13，17，?，89，97} （3）C＝｛ ， ， ， ，?， ｝ ｛0｝｛1｝｛2｝｛3｝ ｛9｝ （4）全集 U 3、对任意对象 a, b, c, d 证明： {{a}, {a,b}}＝{{c}, {c，d}} 当且仅当 a = c 且 b = d 4、指出下列集合序列的排列规律，并依此规律再写出两个后续集合： ? ， ｛?｝｛?,｛?｝ ， ｝,｛?， ｛?｝｛?， ， ｛?｝｝ ｝，┅ 5、 “如果 A?B, B?C，那么 A?C”对任意对象 A,B,C 都成立吗？都不成立吗？举例说 明你的结论。 6、确定下列各命题的真、假； （1）? ? ? （2）??? （3）? ?｛?｝ （4）??｛?｝ （5） b｝ ?｛a , b , c,｛a， b，c｝ ｛a, ｝ （6） b｝?｛a， b， c， ｛a, ｛a， b，c｝ ｝ （7） b｝?｛ ｛a, ｛a，b｝｛ ，｛a，b｝｝ ｝ （8） b｝?｛ ｛a, ｛a，b｝｛ ，｛a，b｝｝ ｝ （9）对任意集合 A，B，C，若 A?B，B ? C 则 A?C。 （10）对任意集合 A，B，C，若 A?B，B ?C 则 A ? C。 （11）对任意集合 A，B，C，若 A?B，B? C 则 A ? C。 （l2）对任意集合 A，B，C，若 A?B，B ?C 则 A ? C。 7、指出下列各组集合中的集合的不同之处，列出每一集合的元素和全部子集： （1） ｛?｝｛ ，｛?｝ ｝ （2） ｛a，b，c｝｛a， ， ｛b，c｝，｛a，b，c｝ ｝｛ ｝ 8、设 A，B 为任意集合证明：如果对任意的集合 C，C ? A 当且仅当 C ? B，那么 A ＝B。1.2集合运算集合运算指以集合为运算对象、以集合为值的运算。 本书中的符号“ ? ”表示术语“当且仅当” （if and only if）1.2.1 并、交、差、补运算并、交、差、补运算是集合的最基本的运算，读者在中学阶段也已有所接触。 定义 1.5 设 A，B 为任意集合。 （l） A∪B 称为 A 与 B 的并集（union set） ，定义为 A∪B＝｛xOx∈A 或 x∈B｝ ∪称为并运算。 （2） A∩B 你为 A 与 B 的交集（intersection set） ，定义为 A∩B =｛xOx∈A 且 x∈ B｝ ∩称为交运算。 （3） A-B 称为 A 与 B 的差集（difference set） ，定义为 A-B＝｛xOx∈A 且 x ? B｝ - 称为差运算。 （4）称为 A 的补集（complement set） ，定义为A =U-A =｛x ? x?A｝ 称为补运算，它是一元运算，是差运算的特例。 例 1.6 设 U＝{0, 1，2，3，?，9}，A = {2，4}，B = {4, 5, 6 ,7}， C = {0，8，9}，D ＝{l, 2, 3}： A?B＝｛2，4，5，6，7｝ A?B?C?D＝U ，C18A?B ＝｛4｝ ，A?C= ? A-B = {2}，B-A =｛5，6，7｝ - C =｛2，4｝ ，AA =｛0，l，3，5，6，7，8，9｝ B ＝｛0，l，2，3，8，9｝ ，定理 1.7 设 A，B，C 为任意集合，*代表运算 ? 或 ?，那么 （l） A ? A ? A （2） A ? B ? B ? A （等幂律） （交换律）（3） A ? ( B ? C ) ? ( A ? B) ? C （结合律） （4）A?? ＝A， A?U = U A?? = ?， A?U = A （5）A?(B?C)=(A?B) ?(A?C) A?(B?C)＝(A?B)?(A?C) （分配律） （6）A?( A?B)=A A?(A?B) =A （吸收律） 证 （1）（2）（3）由定义立得， ， ， ， （5）（6）的证明留给读者。现证（4） 。 对任意 x， x?A?? ? x?A 或 x?? ? x?A（x?? 为假） 故 A??＝A 。而 x?A?? ? x?A 且 x?? ? x??（ x?? 为假） 故 A?? = ? 。其余两式请读者补证。 定理 1.8 对任意集合 A，B，C， （l） （2）A ? A ? ?， A ? ?＝ A ， A ?U ? ? A ? ( B ? C ) ? ( A ? B) ? ( A ? C )A ? ( B ? C ) ? ( A ? B) ? ( A ? C )证 我们只证（2）中第一式，其余留给读者， 对任意 x，x ? A ? (B ? C) ? x ? A 且 x ? B ? C? x ? A且 x ? B 且 x ?C ? ( x ? A 且 x ? B) 且 ( x ? A且x ? C )? ( x ? A ? B) 且 ( x ? A ? C )? x ? ( A ? B) ? ( A ? C ) 故 A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) 。定理 1.9 对任意集合 A，BU ＝? , ? ＝U （2） A ? A ＝U , A ? A ＝? （3） A ? B ＝ A ? B（1） A ＝A ,A? B ＝ A? B（4） A ? B ＝ A ? B 证 （1）,（2）,（4）易证，现证（3）的第一式。A ? B ＝ U ? ( A ? B) ＝ (U ? A) ? (U ? B)＝ A? B 定理 1.10 对任意集合 A , B , C , D， （1） A ? A ? B 19（2） A ? B ? A （3） A ? B ? A （4） A ? B , A ? B ? ?, A ? B ? B ,A ? B ? A 四命题等价。（5）若 A ? B ,则 B ? A 。 证（1）（2）（3）,（5）易证，我们仅证明（4） ， ， 。 设（4）中 4 个命题为 P, Q, R, S ，我们来证明 P?Q?R?S?P（? 表示“推出” ）,从 而证实 4 命题等价。 （P?Q） ：设 A C B ? ?，则有 a?A C B，即 a?A，但 a?B，这与 A ? B 矛盾。故 A C B = ? 。得证。 （Q?R） ：为证 A?B = B ，需证 1）B ? A?B 。但由定理 1.10 之(1)，此已得证。 2）A?B ? B 。为此设 x 为 A?B 中任一元素，从而 x?A 或 x?B。当 x?B 时目的已达 到。当 x?A 时，若 x?B，则 x?A C B，此与 A C B = ? 矛盾。故 x?B。总之，A?B 中元素 x 必为 B 中元素，2）又得证。综合 1） 2）可知 A?B = B 。 、 （R?S） ：因 A?B = B，故 A?B = A?(A?B) =A(吸收律) （S?P） 设 A?B = A。 ： 要证 A?B， 现设 x 为 A 中任一元素。 A?B = A， 由 可得 x? A?B 从而知 x? B。故 A?B 得证。 定理 1.11 对任意集合 A，B．若它们满足 （l） A ? B ? U （2） A ? B ? ? 那么 B ? A B ? B ?? 证 ＝ B ? ( A ? A) ) ＝ ( B ? A) ? ( B ? A) ＝ U ? ( B ? A) ＝ ( A ? A) ? ( B ? A) ＝ ( A ? B) ? A ＝? ? A ＝A 本定理的证明思路是利用已知等式进行推演， 这种证明集合等式的方法简明， 但难度有 时较大。本定理还可直接用外延性公理来证，这种方法虽较繁锁，但思路清晰，易掌握。先 证 B ? A 。设 x?B，由于 A?B=?，故 x?A,即 x? A ，B? A 得证。再证 A ?B。设 x? A ， 则 x?A;由于 A?B＝U，故必有 x?B， A ?B 又得证。因此 B＝ A 。1.2.2 幂集运算和广义并、交运算 定义 1.6 对任意集合 A， ? ( A) 称为 A 的幂集（power sets） ，定义为? ( A) ? {X X ? A}即 A 的全体子集组成的集合是 A 的幂集。 由于，??A, A?A 故必有 ? ? ? ( A) , A ? ? ( A) 。 例 1.7（1）A=｛a，b｝时， ? ( A) ＝｛?， ， ， ｛a｝｛b｝｛a，b｝。 ｝ 20（2）A=｛0，{1，2}｝时， ? ( A) ＝｛?， ， ，{｛1，2｝}｛0，{1，2｝}｝ ｛0｝｛1｝ 。 定理 1.12 设 A,B 为任意集合, A?B 当且仅当 ? ( A) ? ? (B ) 。 证 我们曾指出，当集合 A 的基数为 n 时，A 有 2n 个子集，因此| ? ( A) |= 2n 。 先证必要性。设 A?B。为证 ? ( A) ? ? (B ) ，又设 X 为 ? ( A) 中任一元素，从而X?A。由于 A?B，故 X?B，从而有 X? ? (B ) 。 ? ( A) ? ? (B ) 得证考虑单元素集合｛a｝｛a｝? ? ( A) ，但｛a｝? ? (B ) ，与 ? ( A) ? ? (B ) 矛盾，A?B 得证。 ， 为了讨论广义的并、交运算，需要以下术语。 定义 1.7 若集合 C 的每个元素都是集合，则称 C 为集合族（collections） 。若集合族 C 可表示为 C =｛Sd|d ?D｝ 则称 D 为集合族的标志集（index set） 。 例 1.8 C =｛ ， ｛0｝｛0，1｝｛0，1，2｝, ?｝为一集合族,它没有标志集。若集合族 C = ， ｛A1，A2，A3, ?｝,则 C 的标志集为正整数集 I+；集合族 C＝｛S 甲，S 乙， S 丙｝ ，则 C 的 标志集为集合｛甲，乙，丙｝ 。 定义 1.8 设 C 为集合族，且 C 非空。 （m）再证充分性。设 ? ( A) ? ? (B ) ，反设 A?B 不成立，那么至少有一元素 a?A，但 a?B 。? C ? ?x : 有S使S ? C且x ? S? （2） ? C 称为 C 的广义交。定义为 ? C ? ?x : 对所有S ? C均有x ? S )? （3）当集合族 C =｛Ad|d ?D｝时， ? C 和 ? C 可分别表示为? C ? ? Add ?D?? C 称为 C 的广义并，定义为?C ?d?D ， 当 D 为自然数集 N 时，它们又可分别表示为?Ad? C ? ? Add ?0， 显然，当 C ＝｛A，B｝时， 例 1.9? C ? ? Add ?0??C ? A? B，?C ? A? B（1）当 C =｛ ， ｛0｝｛0， 1｝｛0， l， 2｝ ， ，?｝时， ? C ＝N， ? C ＝｛0｝ 。 （2）当 C＝｛S1，S2，S3｝时，?C ??C ?d ??1, 2 , 3???S d ? ? S d ? S1 ? S 2 ? S 3d ?133d ??1, 2 , 3?S d ? ? S d ? S1 ? S 2 ? S 3d ?1定理 1.13 对任意集合 A 和集合族 C，有A ? (?C ) ? ??A ? S : S ? C? A ? (?C ) ? ??A ? S : S ? C?x ? A ? (?C ) ? x ? A并且有S ? C使得x ? S21证 我们只证第一式，第二式雷同。 设 x 为任一元素，? 有S ? C使得( x ? A且x ? S ) ? 有S ? C使得x ? A ? S 故 A ? (?C ) ? ??A ? S : S ? C? 定理 1.14 对任意集合 A 和集合族 C，有 ? x ? ??A ? S : S ? C?A ? (?C ) ? ??A ? S : S ? C? A ? (?C ) ? ??A ? S : S ? C?证 证第一式，第二式留给读者． 故 x? ? ?A ? S : S ? C?。反之，设 x ? ??A ? S : S ? C?，则对每一 S?C，均有 x?A-S， 从而 x?A 且对每一 S?C，x?S，此即 x?A 而 x? ? C ，故 x ? A ? (?C ) 。 两方面的证明证实 A ? (?C ) ? ??A ? S : S ? C?。 定理 1.14 的自然推论是 定理 1.15 对任意集合族 C 有 设 x ? A ? (?C ) ，那么 x?A，且对每一个 S?C，x?S。于是，对每一 S?C，x?A-S，( ?C ) ? ? ??S ? : S ? C( ?C ) ?? ? ??S : S ? C ??定理 1.16 对任意集合 A, 证 设 x 为任一元素，? ? ( A) ? A ．故 ? ? ( A) ? A .x ? ? ? ( A) ? 有S ? ? ( A)使得x ? S ? 有S ? A使得x ? S ? x?A1．2．3 集合的笛卡儿积 定义 1.9 设 a ， b 为任意对象，称集合 {{a}, {a, b}} 为二元有序组，或序偶（ordered pairs） ，简记为 ? a, b ? 。称 a 为 ? a, b ? 的第一分量，称 b 为第二分量。注意，第一、二分量可以相同。 定理 1.17 对任意序偶 ? a, b ? , ? c, d ? , ? a, b ? = ? c, d ? 当且仅当 a ? c, 且b?d。证 其充分性是显然的。 为证必要性，设 ? a, b ? = ? c, d ? ，那么{{a}, {a, b}} ＝ {{c}, {c, d}}（1－1）? {{a}, {a, b}} ＝ ? {{c}, {c, d}} {a, b} ＝ {c, d } ? {{a}, {a, b}} ＝ ? {{c}, {c, d }} 以及 {a} ＝ {c} 由式（1－2） ，式（1－3）两式知 a ? c, b ? d 。（1－2）（1－3）? 因此， 要充分注意 ? a, b ? 与 {a, b} 的区别， 即当 a≠b 时， a, b ? ≠ ? b, a ? ， 但{a， b}={b,a}; &a,a&≠&a&,但 {a,a}={a}. 定义 1.10 定义 n 元序组 &a1，?，an& ： &a1，a2& =｛ 1｝｛a1 , a2｝ ｛a ， ｝22&a1，a2，a3& = &&a1，a2&，a3& ?? &a1，?，an& = &&a1，?，an-1&, an& 本质上, n 元序组依然是序偶。ai 称为 n 元序组的第 i 分量。 定理 1.18 对任意对象 a1，?，an，b1，?，bn， &a1，?，an& = & b1，?，bn &当且仅当 a1 = b1 ，?，an= bn 证明略。 显然，序偶和 n 元序组都是集合，但由于它们的特殊结构，把次序赋予了有关对象，我 们以后更多关心的是它们的这种“序特性” 。而较少谈论定义它们的原有的集合结构细节。 定义 1.11 对任意集合 A1，A2 , ?，An，定义 A1 ? A2 ? ? ? An ： A1 ? A2，称为集合 A1 , A2 的笛卡尔积(Cartesian product)，定义为 A1 ? A2=｛&u,v& ? u ?A1,v?A2｝ A1 ? A2 ? A3= (A1 ? A2)? A3 ?? A1 ? A2 ? ? ? An= (A1 ? A2 ? ?? An-1 )? An 当 A1 = A2 = ? =An =A 时，A1 ? A2 ? ? ? An 简记为 An 定理 1. 19 对任意集合 A1，A2 , ?，An， A1 ? A2 ? ? ? An=｛&& a1, ?, an-1&, an& ? a1 ?A1,?,an ?An｝ 本定理同样是易于证明的，请读者完成之。 例 1.10 设 A =｛1 , 2｝ = ｛a , b, c｝ =｛?｝, R 为实数集， ，B ，C 那么 （l） A?B =｛&1, a&，&l, b&，&1, c&，&2, a&，&2, b&，&2, c&｝ B?A＝｛&a, 1&，&b, 1&，&c, 1&，&a, 2&，&b, 2&，&c, 2&｝ （2）A?B?C = ( A?B)?C =｛&1, a, ?&，&l, b, ?&，&1, c, ?&，&2, a, ?&，&2, b, ?&， &2, c, ?&｝ A? ( B?C ) =｛&1, &a, ?&&，&l, &b, ?&&，&1, &c, ?&&，&2, &a, ?&&，&2, &b, ?&&， &2, &c, ?&&｝ （3）A?? = ??A = ? （4）R2 =｛&u,v& ? u ,v 是实数｝ 2 为笛卡儿平面。显然 R3 为三维笛卡儿空间． ，R 我们注意到，一般地 A?B ? B?A，(A?B)?C ?A?(B?C) 。此外，? 也用来表示不含任 何序组的笛卡儿积。 关于笛卡儿积有以下性质。 定理 1.20 设 A, B, C 为任意集合，*表示 ?，? 或 C 运算， 那么A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) ( B ? C ) ? A ? ( B ? A) ? (C ? A) 证 我们仅证明 A ? ( B ? C ) ? ( A ? B) ? ( A ? C ) 和 A ? ( B ? C ) ? ( A ? B) ? ( A ? C )对任意 x，y， &x, y& ? A?(B ? C) ? x? A 且 y?(B ? C) ? x? A 且(y?B 或 y?C) ? (x? A 且 y?B)或(x? A 且 y?C) ? &x, y& ? A?B 或&x, y& ? A?C ? &x, y& ? (A?B) ?(A? C) 为证第二式， 设&x, y&为 A?( B C C)中任一序偶， 那么 x? A , y?B， y?C， 从而&x,y&?A?B， &x,y&?A?C，即&x,y&?A?B C A?C , A?(B C C) ? (A? B) C (A ? C) 得证。另一方面，设&x,y& 为(A? B) C (A ? C)中任一序偶，那么&x,y&?A?B，&x,y&?A?C，从而 x?A，y?B, y?C（否 则由于 x?A，&x,y&?A?C ） ，故可知 y?B C C ，&x,y&? A?(B C C)，于是(A? B) C (A ? C) ? A?(B C C)得证。这就完成了 A?(B C C)＝(A? B) C (A ? C) 的证明。 定理 1.21 对任意有限集合 A1，?，An，有: 23A1 ? ? ? An ? A1 ? ? ? An这是十分直观的，证明省略。 ? 定理 1.22 对任意非空集合 A，B， （l） ? (?( A ? B)) ? A ? B （2） A ? B ? ? ( ? ( A ? B) 证( 其中?为数乘运算)? (?( A? B))= ? (??? a, b ?: a ? A ? b ? B?)? , ? ＝ ? (?? ?a? ?a, b? : a ? A ? b ? B?)＝? ( ? ??a???a?Aa?A?b?B???a, b??)? ? ) ＝ ? (? a?: a ? A?? ? a, b?: a ? A ? b ? B?=a?A? ?a??a?A?b?B??a, b?= A ? ( A ? B) = A? B （2）设&x,y&为 A?B 中任一序偶，即 x?A，y?B 。现需证 由于 x?A,故｛x｝? ρ(A?B)；又由于 x?A，y?B，故｛x,y｝? ? ( A ? B) 。因此， ｛ ｛x｝,｛x,y｝ ? ( A ? B) ｝? 即｛ ｛x｝,｛x,y｝ ｝? ? ( ? ( A ? B)) 。故 A ? B ? ? ( ? ( A ? B) 。 事实上，结论（1） （2）对 A，B 为空集时也真。 &x,y& =｛ ｛x｝,｛x,y｝ ｝? ? ( ? ( A ? B))练习 1.2l、证明定理 1.7 之（5） 。 2、证明定理 1.8 之（2）中的第二式。 3、证明定理 1.9 之（4） 。 4．试以下列次序证明定理 1.10： P?R?S?Q?P 5．对任意集合 A，B，C，证明：( A ? C) ? (B ? C) ? A ? B6．对任意集合 A，B，C，证明： （2） A ? ( B ? C ) ? ( A ? B) ? C ? ( A ? C ) ? B （2） ( A ? B) ? C ? A ? ( B ? C ) ? ( A ? C ) ? B （3） ( A ? B) ? C ? A ? ( B ? C ) 当且仅当 A ? C ? ? （4） ( A ? B) ? C ? ( A ? C ) ? ( B ? C ) 7．证明：对任意集合 A，B 下列命题等价， （1） A ? B （2） A ? B = U （3） A ? B = ? 8．设 A = ???，B = ?1，2?，求 ? ( ? ( ? ( A))) ， ? ( ? ( B)) 。 9．对任意集合 A，B。求证： （1）A = B 当且仅当 ? ( A) = ? (B)24（2） ? ( A) ? ? (B) ＝ ? ( A ? B) （3） ? ( A) ? ? (B) ? ? ( A ? B) 10. 若 C ={{ x} x ? B}{ {x} : x?B} 求 ? C 。11. 对下列诸 C，求 ? C 和 ? C 。 （1）C =｛?｝ （2）C =｛?， ｛?｝ ｝ （3）C = {{a}, {b}, {a, b}} （4）C = ? ( ? ( N )) 12．对任意非空集合族 C1，C2，证明： （1） (?C1) ? (?C 2) ? ?(C1 ? C 2) （2） (?C1) ? (?C 2) ? ??S1 ? S 2 : S1 ? C1 ? S 2 ? C 2? （3） (?C1) ? (?C 2) ? ??S1 ? S 2 : S1 ? C1 ? S 2 ? C 2? （4） (?C1) ? (?C 2) ? ?(C1 ? C 2) 13．设 A = {1, 2, 3}, R 为实数集,请在笛卡儿平面上表示出 A?R 和 R?A 。 14．以下各式是否对任意集合 A，B，C，D 均成立？试对成立的给出证明，对不成立 的给出适当的反例。 （1） ( A ? B) ? C ? ( A ? B) ? ( A ? C ) （2） ( A ? B) ? (C ? D) ? ( A ? B) ? (C ? D) （3） ( A ? B) ? (C ? D) ? ( A ? C ) ? ( B ? D) （4） ( A ? B) ? (C ? D) ? ( A ? C ) ? ( B ? D) 15．设 A , B , C , D 为任意集合，求证： （1）若 A ? C, B ? D ，那么 A ? B ? C ? D 。 （2）若 C ? ? , A ? C ? B ? C ，则 A ? B 。 （3） ( A ? B) ? (C ? D) ? (( A ? C ) ? B) ? ( A ? ( B ? D)) 1.3 集合的归纳定义1.3.1 集合的归纳定义我们已经提到集合有三种表示方式，其中之一是归纳定义（inductive definition） 。现在 我们要来介绍什么是归纳定义。 集合的归纳定义由三部分组成: （1）基础条款：规定待定义集合以某些元素为其基本成员，集合的其它元素可以从它 们出发逐步确定。 （2）归纳条款：规定由已确定的集合元素去进一步确定其它元素的规则。于是，可以 从基本元素出发，反复运用这些规则来确认待定义集合的所有成员。 （3）终极条款：规定待定义集合只含有（l）（2）条款所确定的成员。 ， 条款（l）（2）又称归纳定义的完备性条款，它们必须保证毫无遗漏地产生出待定义集 ， 合的全部成员；条款（3）又称归纳定义的纯粹性条款，它保证整个定义过程所规定的集合 只包括满足要求的那些对象。 例 1.11 设 U 为整数集 I，现用归纳定义规定偶数集 E： （l）基础条款：0 ? E． （2）归纳条款：若 x?E，则 x+2?E, x-2?E． （3）终极条款：除有限次使用（l）（2）条款确定的元素外，E 中没有别的元素。 ， 许多关于形式语言（例如一阶谓词演算系统的语言、计算机程序设计语言等）的概念及 形式语言本身，都是归纳定义的。 25通常把一个非空符号集合称为字母表，常用Σ 表示之，Σ 上的字（即符号串）的概念可 + 如下归纳定义。用Σ 表示Σ 上的字的集合。 + （1）基础条款：Σ ?Σ 。 + + （2）归纳条款：若ξ ?Σ ，w?Σ 则ξ w?Σ 。 （这里ξ w 表示字符号ξ 与字符串 w 的 并置，或毗连，即自然连接） 。 + （3）终极条款：除有限次使用（l）（2）条款确定的元素外，Σ 中没有别的元素。 ， + * 如果用λ 表示空字（即空符号串，对任何字 w，λ w = wλ = w） ，记Σ ??λ ?=Σ 。当 * 然也可以用归纳定义来规定Σ 。 * 符号串集合 L 称为Σ 上的一个形式语言(formal languages)，如果 L?Σ 。 字头、字尾的概念也是形式语言中常用的。它们也可以归纳地定义。先定义字 w 的字 头 w’的概念: （1）基础条款：λ 是 w 的字头。 * （2） 归纳条款： w’为 w 的字头， = w’ ξ w’’ 若 w （其中ξ ?Σ , w’,w’’ ?Σ ） 那么 w’ ξ ， 也是 w 的字头。 （3）终极条款（略） 。 当 w’为 w 的字头，w = w’ w’’，则称 w’’为 w 的字尾。对字尾也可以直接作归纳定义。 + + 例 1.12 设Σ 为数字集 D＝｛0，l，2，?，9｝ ，那么Σ ＝D 可看作为全体自然数的集 * 合。 当Σ ＝ ｛a,b｝ 时， = Σ ｛λ , a , b ， ab， aa， ba， bb， 。 ｛λ ， ?｝ L＝ ab， aabb， aaabbb， ?｝ * ?Σ ，L 为Σ 上的一个语言（请读者归纳定义之） 之中所有字的字头中 a 的数目不少于 b 。L 的数目，字尾中 a 的数目不多于 b 的数目。 最后一个例子说明归纳定义在计算机科学中有十分广泛的应用。 例 1.13 假定我们已经规定了“变元集”“算术表达式集”“条件语句集” 、 、 ，现归纳定 义“while 程序集” ，记为 WP。 （1）基础条款：V←E 在 WP 中。其中 V 为变元，E 为算术表达式。 （2）归纳条款： （2.l）若 C 为条件语句， P1，P2 为 whlile 程序，则 if C then P1 else P2 end if 在 WP 中。 （2.2）若 C 为条件语句，P 为 while 程序．则 while C do P end while 在 WP 中。 （2.3）若 P1，P2 为 whlile 程序，则 P1；P2 在 WP 中。 （3）终极条款（略） 。 *1.3.2 集合定义的自然数 本章一开始我们就指出，集合论开创的初衷就是要为数学奠基,为此首先要在集合论中 定义最基础的数学概念：自然数（它原本是不作定义的原始概念） ，即用集合来定义自然数。 由于这一定义可用归纳定义的形式给出，因而正好成为一个归纳定义的生动的例子。 自然数是大家熟悉的。从本质上看，它们是满足下列特性的一列符号； （1）它们中有一个为首的符号。 （2）每个符号都有且仅有一个直接的后继符号。 （3）为首的符号不是任何符号的直接后继符号。 （4）没有两个符号具有相同的直接后继符号。 （5）自然数仅指这列符号中的符号。 由于自然数的一切性质均可以从这五个特性推得，因此皮亚诺（Peano）用五条公理刻 划自然数概念： P1．至少有一个客体是自然数，它被记为 0。 P2．如果 n 是自然数，那么 n 必定恰有一个直接后继者，记为 n’。 P3．0 不是任何自然数的直接后继。 P4．如果自然数 m，n，的直接后继 m’,n’相同，那么 m = n。 P5．没有不满足上述条件的客体是自然数。 现在我们需要在集合论中，实实在在地拿出一列符号来，并使它们满足这五条公理，从 而定义出自然数。 一种容易想到的定义自然数集合 N 的方式是： 26（1） 0?N 。 （2）如果 x?N ,则 x+1?N 。 （3） （终极条款） 。 但这一定义是不适当的。 为何物？集合否？”,“尚无自然数时，加 1 意义何在？”为了 “0 在集合论中定义自然数，首先要选择一个集合，例如 ?，作为为首的自然数，并给 ? 起一 个自然数名“0” 。其次需确定一种集合运算，作为求直接后继的运算。 定义 1.12 （1）称空集 ? 为自然数，记为 0。 （2）称 A’为集合 A 的直接后继，如果 A’＝A ?｛A｝ 例 1.14｛a，b｝ ’＝｛a，b， ｛a，b｝ ｝ ?’＝? ?｛?｝= ｛?｝ ｛?｝ ’= ｛?｝?｛ ｛?｝ ｝= ｛?,｛?｝ ｝ ｛?,｛?｝’=｛?,｛?｝,｛?,｛?｝｝ ｝ ｝ 定义 1.13 归纳定义自然数集 N： （l）基础条款：??N 。 （2）归纳条款：如果 x?N ，则 x’= x ?｛x｝? N。 （3）终极条款（略） ． 按照上述定义。自然数集 N 由下列元素组成： ?， ｛?｝｛?， ， ｛?｝， ｝｛?， ｛?｝｛?， ， ｛?｝｝ ｝，? 或 0，0’ ，0’，? ，0” ” 将它们依次表示为 0，1，2，3，? 这样定义的自然数的表示形式是有趣的： 1 ＝｛0｝ ，2 ＝｛0，l｝ =｛0，l，2｝ ，3 ，?，n ＝｛0，l，2，?，n-1｝ 这是因为 n ＝（n-1）?｛n-1｝ （当 n ? 0 时） 。 现在我们来证明, 如上定义的自然数满足皮亚诺的五条公理。事实上只要证明它们满足 P1―P4． P1 显然被满足，至少有 ? 作为自然数 0 在 N 中。 为证 P2，设 n 为一自然数。首先， n 有后继 n’＝n ?｛n｝ 。其次可证 n’是唯一的， 因为 n ?｛n｝＝｛0，l，2，?，n｝是唯一确定的集合。 为证 P3，反设 ? 是自然数 n 的后继。n’＝ n ?｛n｝ ，从而 ?＝ n ?｛n｝ ，但这是 不可能的，因为右边至少有元素 n 。因此 ? 不是任何自然数的后继。 为证 P4，反设有自然数 m，n，m’= n’ ，但是 m ? n 。 由于 m’= n’ ?｛m｝= n ?｛n｝ ，m 。因 m ? n，故总有元素 x?m, 但 x?n; 或 x?n, 但 x?m。不妨设 x?m,但 x?n 。于是我们有 x?m ?｛m｝= n ?｛n｝ ，进而知 x? n ?｛n｝ 。由 于 x?n，故 x?｛n｝ ，即 x＝n。这样便有 x＝n?m 。由 n?m 可导出 m ? n，m?n 。这与 m ? ｛m｝= n ?｛n｝矛盾，因为左边集合以 m 为元素，右边集合决无元素 m 。矛盾的导出表 明 m = n，P4 得证。 有了自然数，便可以定义自然数集合上的运算和函数。关于这一点我们留待第 11 章讨 论。练习 1.31．归纳定义 ? （? ＝? ????） ，令 ?= ?a，b?。 2．令 ?= ?a,b,c?，归纳定义： （l） L ? ?*，使 L 中所有字里都有字 ab 的出现，且所有含字 ab 的字全在 L 中。 （2） L ? ?*，使 L 中所有字里都含有字符 a 和 b，且所有含字符 a,b 的字全在 L 中。 3．归纳定义下列集合： （1）十进制无符号整数集合，非零数不得以 0 为字头。 （2）十进制非负有穷小数。* * +27（3）全体十进制有理数(分数)。 （4）二进制形式的非负偶数，非零数不得以 0 为字头 4．数学表达式中允许出现的括号的嵌套和毗连所形成的括号串称为成形括号串。归纳 定义成形括号串集合（假定它含有空括号串 ?） 。 5．直接归纳定义形式语言中字尾的概念。第 2 章 两个常用数学基本原理本章和第一章一样是今后学习的必要的数学准备， 它介绍两个最常用的数学基本原 理：归纳原理和鸽笼原理。2.1 归纳原理 归纳原理是一种重要的数学思想和证明技术， 它广泛地应用在各种离散结构 的数学证明中。 2.1.1 结构归纳原理设集合 A 是归纳定义的集合，现欲证 A 中所有元素具有性质 P，即欲证:对任意 x?A 有 P(x)真。那么，可如下进行证明： （1） （归纳基础）证明归纳定义基础条款中规定的 A 的基本元素 x 均使 P(x)真。 （2） （归纳推理）证明归纳定义的归纳条款是“保性质 P 的” 。即在假设归纳条款中已 确定元素 x1,?, xn 使 P(xi)真(i = 1,2,?,n)的前提下，证明用归纳条款中的操作 g 所生成元素 g(x1,?, xn)依然有性质 P, 即 P(g(x1,?, xn))真。 归纳推理中的假设称为归纳假设。 由于 A 仅由（1）（2） 条款所确定的元素组成，因此当上述证明过程完成时， ， “A 中 所有元素具有性质 P”得证。这种推理原理称为归纳原理，应用这一原理进行证明的方法称 为归纳法（induction） 。为区别于通常所说的“数学归纳法” ，它又称为“结构归纳法” ．数 学归纳法是它的特例。 例 2.1．回忆成形括号串集合（假定它含有空括号串 ?）的定义（练习 1.3 之 4, 为了视 觉明晰，用括号 [ ] 代替括号（ ） ） （1） （基础条款）空括号串 ? 是成形括号串。 （2） （归纳条款）如果 x,y 是成形括号串，那么[x] , xy 都是成形括号串。 （3） （终极条款）除有限次使用（1）（2）条款确定的对象外，没有别的对象是成形括 、 号串。 （a）证明：成形括号串中左括号数等于右括号数。 （b）证明：成形括号串的字头中，左括号数不少于右括号数。 证（a）设 L( x ), R( x ) 分别表示成形括号串 x 中的左、右括号数。 ） （归纳基础） L( x) ? R( x) ? 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 ) 。（b） ） （归纳基础） ：空成形括号串的字头的左括号数不少于右括号数显然真。 ） （归纳推理） ：设成形括号串 x，y 的字头中左括号数大于或等于右括号数，那么[x] 的字头为“ ? ”或 “ [ ”或“ [ 毗连 x 的字头” 或“[x]” ，而 x 的字头中左括号数大于 或等于右括号数， 因此[x]的字头， 无论是 ? ” “ [ ” 或 “ [ 毗连 x 的字头” “[x]” “ 或 或 ， 其中的左括号数总大于或等于右括号数。 又 xy 的字头集合中包括 x 的字头以及 x 与 y 的字头毗连而成的字头。 因为 x， 的字头 y 中左括号数大于或等于右括号数， x 中左括号数等于右括号数， 而 因此 xy 的字头 （无论是 x 的字头或 x 与 y 的字头毗连而成的字头）的左括号数也总大于或等于右括号数。 归纳完成，命题得证。282.1.2 数学归纳原理我们已经指出， 数学归纳原理是上述结构归纳原理的特例， 因为它只是在归纳定义的自 然数集上进行归纳推理。读者在中学学习过的数学归纳法是数学归纳原理的最基本的形式。 数学归纳法的基本模式（第一数学归纳法） 回忆，用第一数学归纳法证明所有自然数具有性质 P 时，只要如下进行推理： （1） 归纳基础：证 P(0)真，即证明数 0 有性质 P。 （2） 归纳过程：对任意 k(R0)假设 P(k)真（归纳假设“k 满足性质 P”）时,推出 P(k ＋l)真（k＋l 也满足性质 P） 。 （3） 结论：所有自然数具有性质 P。 多米诺骨牌是数学归纳法基本模式的一个形象的释例。 例 2.2 用归纳法证明：对任意自然数 n 有(0 ? 1 ? 2 ? ? ? n) 2 ? 03 ? 13 ? 23 ? ? ? n 32 3 证 ）归纳基础：当 n = 0 时， 0 ? 0）归纳过程：设当 n = k 时， (0 ? 1 ? 2 ? ? ? k ) ? 0 ? 1 ? 2 ? ? ? k ,那么当 n = k +1 时，2 3 3 3 3(0 ? 1 ? 2 ? ? ? k ? k ? 1) 2 ? 03 ? 13 ? 23 ? ? ? k 3 ? (k ? 1) 2 ? 2(1 ? 2 ? ? ? k )( k ? 1) ? 03 ? 13 ? 23 ? ? ? k 3 ? (k ? 1) 2 ? k (k ? 1) 2 ? 03 ? 13 ? 2 3 ? ? ? k 3 ? (k ? 1) 3归纳完成，命题得证。 对数学归纳法的这种基本模式，读者在中学已熟练掌握，这里不多举例了。下面仅对它 的一些变形作些说明。 起始于任意自然数 n0 的归纳证明模式 用第一数学归纳法证明所有大于或等于 n0 的自然数具有性质 P 时， 只要如下进行推理： （1） 归纳基础：证 P(n0)真，即证明数 n0 有性质 P。 （2） 归纳过程：对任意 k(Rn0)假设 P(k)真（归纳假设“k 满足性质 P”）时,推出 P(k ＋l)真（k＋l 也满足性质 P） 。 （3） 结论：所有大于或等于 n0 的自然数具有性质 P。 起始于多个值的归纳证明模式（例如起始于两个值，起始于更多个值的情况雷同） 用起始于 2 个值的第一数学归纳法证明所有自然数具有性质 P 时，只要如下进行推理： （1） 归纳基础：证 P(0)真，P(1)真，即证明数 0 和数 1 都有性质 P。 （2） 归纳过程：对任意 k(R0)假设 P(k)真（归纳假设“k 满足性质 P”）时,推出 P(k ＋2)真（k＋2 也满足性质 P） 。 （3） 结论：所有自然数具有性质 P。 例 2.3 证明用 3 分币和 5 分币可以组成 8 分以上的任何币值。 证. 对 8 分以上的币值 n 归纳。 因为 8 = 3+5，9 = 3＋3＋3，10 = 5 十 5，因此,当 n 为 8，9，10 时可用 3 分币及 5 分币 组成。 设 n＝k 时命题真，即 k 可用 3 分币及 5 分币组成，需证 n = k＋3 时命题真，然而这是 显然的,只要在组成 k 的 3 分币及 5 分币组合中新添一个 3 分币即可。 归纳完成，命题得证。 允许有参变数的归纳证明模式：设 P(m,n)为依赖自然数 m,n 的性质。为证 P(m,n)对一 切自然数 m，n 均真时，可只对其中一个变元进行归纳，而将另一变元视为参变元。 例 2.4 设 f 是以自然数集为定义域的函数，满足f (0, m) ? m ? 1f (n ? 1, m) ? f (n, m 2 ) ? f (n,2nm) 求证：对任意 m，n， f (n, m) ? 0 。29证对 n 归纳，把 m 看作参数。 当 n = 0 时， f (0, m) ? m ? 1 ? 0 。 当 n = k 时，设对任意 m 有 f (k , m) ? 0 。那么，n = k+1 时，f (n, m) ? f (k ? 1, m) ? f (k , m 2 ) ? f (k ,2km)据归纳假设， f (k , m ) ? 0 ， f (k ,2km) ? 0 ，故 f (k ? 1, m) ? 0 。 归纳完成，命题得证。 有时待证命题虽只有一个变元， 但变元所处的不同地位造成了归纳证明的困难。 这时可 以引人参数， “拆裂”变元进行证明。2? (n ? 1) 。 例 2.5 求证: n 为不小于 3 的自然数时有 n 在 n = 3 时易证，但归纳推理相当困难，因为同一变元 n 分处于底数和指数的位置，归nn ?1? (k ? 1) 难以利用。为此，我们将底数上 n 与指数上 n 拆裂开。即引入变元 u， 纳假设 k 去证明一个更加一般的结论：uRnR3 时有kk ?1nun ? (u ? 1) n证 对 n 归纳，视 u 为参数。 n = 3 时，uR3，而(2--1)3u 3 ? u 3 ? 2uu 2 ? u 3 ? 6u 2 ? u 3 ? 3u 2 ? 3u ? 1 ? (u ? 1) 3因此 n = 3 时式（2--1）得证。 设 n = k 时式（2--1）对一切 uR3 成立,即 ku ? (u ? 1) 。那么 n = k+1 时，k knun ? (k ? 1)u k ?1? (k ? 1)uuk? (ku ? u)u k? (u ? 1)kuk? (u ? 1)( u ? 1) ? (u ? 1) k ?1从而 n = k+1 时式（2--1）亦成立。k（因 u ? n ? k ? 1 ） （归纳假设 ku ? (u ? 1) ）k k? (n ? 1) 。例 2.5 证毕。 式（2--1）由归纳法得证。在式（2--1）中令 u = n , 即得 n 强数学归纳法的证明模式（第二数学归纳法） 用第二数学归纳法证明所有自然数具有性质 P 时，只要如下进行推理： （1） 归纳基础：证 P(0)真，即证明数 0 有性质 P。 （2） 归纳过程：对任意 k(R0)假设 P(i)真, k & i R 0（归纳假设“0,1,?,k-1 均满足 性质 P”）时,推出 P(k)真（k 也满足性质 P） 。 （3） 结论：所有自然数具有性质 P 例 2.6 有数目相等的两堆棋子(每一堆中棋子数目为 n)，甲、乙两人玩取棋子游戏。规 定两人轮流取子，每次两人取子数相同，不能不取，也不能同时在两堆中取子，取得最后一 枚棋子者为胜者。求证：后取者必胜。 证 设甲为先取者。乙为后取者，对每一堆中棋子数目 n 归纳证明乙必胜。n = 1 时，两 堆各有一枚棋子，甲必先从一堆中取走一枚，余下最后一枚必被乙取走，乙胜。 设 n＜k 时乙必胜。现证 n＝k 时乙亦必胜。 设第一轮取子时，甲从一堆中取走 r 枚棋子，余下 k-r＜k 枚棋子，那么，乙只要从另一 堆棋子中也取走 r 枚棋子，亦留下 k－r＜k 枚棋子。若nn ?130（l）r = k，那么乙取到了最后一枚棋子，乙胜。 （2）l＜r＜k，那么 0＜k－r＜k 。对留下的两堆棋子，每一堆为是 k－r 枚，据归纳假 设，在以后甲乙的搏奕中乙必胜，因此全局亦必是乙胜。 归纳完成，命题得证。 化归于数学归纳法的结构归纳：数学归纳法是结构归纳的特例，数学归纳法显然更易 于掌握和运用。但我们要指出，许多结构归纳证明可以化归为数学归纳法，从而也变得好学 好懂易表达。例如，可定义成形括号串中括号的嵌套和毗连的次数为括号串的秩，因而可对 秩用数学归纳法证明例 2.1。在以后的学习中，我们会遇到这样的例子。 最后我们要强调，归纳证明的两个部分，归纳基础及归纳推理是缺一不可的，并且要注 意归纳基础的充分性和归纳推理中“k”的任意性。 仅有归纳基础，没有归纳推理，即使对许多（乃至无穷多）情况已分别证明命题成立， 仍不能据此作出一般化的结论。例如哥德巴赫猜想，已被大量数值验证，但仍不能称它在整 个自然数集上为真。 仅有归纳推理，没有归纳基础，归纳证明也不能成立的。例如；仅作归纳推理可由 k = k+1（归纳假设） ，导出 k+1 = k+2 。从而得出 n＝n + 1 的荒谬结论。 归纳基础的充分性是需严密关注的。n 2 例 2.7 证明：对任何自然数，有 2.5 ? n 。证 n = 0 时， 2.5 ? 1 ? 0 ? 0 ，故命题真。 设 n＝k 时命题真。现设 n = k+1，那么0 22.5k ?1 ? 2.5 ? 2.5k ? 2 ? 2.5k ? 2.5k ? 2.5k ? k 2 ? k 2 （归纳假设）? ? k 2 ? 2k ? 1 ? (k ? 1) 2归纳似已完成，但仔细的读者会发现, ?标记的步骤是有疑问的，因为 k 2R2k +1 只是在 kR3 时才成立,因而归纳基础只对 n = 0 进行是不充分的。因此， 应对 n = 0，n = 1，n = 2, n = 3 分别证明（作为归纳基础）后再进行上述归纳推理才对。 （请读者补证） 归纳推理中，假定 P(k)真而证明 P(k+1)成立的过程中，k 必须是“任意的” 。例 2.7 中， 2 我们也是先考虑到 k R2k +1 并非对任意 k 成立，才察觉归纳基础的不充分。下面的例子更 好地说明了这一点。 例 2.8 下列命题和证明是错误的： 命题：任意 n 条直线必重合于同一条直线。 证明：n = l 时显然命题真。 设 n = k 时命题成立， 即任意 k 条直线均重合于同一条直线。 现考虑 n = k + 1， 即有 k+1 条直线：l1，l2，?，lk，lk+1。据归纳假设，l1，l2，?，lk，这 k 条直线必重合于同一条；l2，?， lk，lk+1 这 k 条直线也必重合于同一条．由于这两组直线中有公共的成员，因此这两组直线 事实上重合于同一条直线。归纳完成，命题证毕。 问题出在哪儿呢？出在 k 的任意性在推理中被忽略。不难看出，k = 1（n = 2）时，两 组直线分别只含一条直线，它们不会有公共成员。 最后我们来讨论数学归纳原理的正确性。 在接受“自然数集合的任一非空子集都有最小元素”这一浅显事实的基础上，可以证明 数学归纳原理的正确性。 现应用反证法证明第一数学归纳法的正确性。 假设我们已经完成以 下推理： （1） 归纳基础：证 P(0)真，即证明数 0 有性质 P。 （2） 归纳过程：对任意 k(R0)假设 P(k)真（归纳假设“k 满足性质 P”）时,推出 P(k ＋l)真（k＋l 也满足性质 P） 。 但是，并非所有自然数都有性质 P。那么不满足性质 P 的自然数组成一个自然数集合的 非空子集，因而它有最小元素，设之为 k。显然 k≠0，并且 k C 1 一定具有性质 P，即 P(k C 1 ) 真，而 P(k)假。这是与已经证明的事实（2）矛盾的。因此，所有自然数都应有性质 P， 也就是说第一数学归纳法是正确的。练习 2.1311. 证明：成形括号串的字尾中，右括号数不少于左括号数。 A ? n 时， ? ( A) ? 2 n 。 2．用归纳法证明：当3. 设集合族 C = {A1，?，An}，用归纳法证明： (1) (2)( ? Ai ) ? ? ? Ai?i ?1 n i ?1 nnn( ? Ai ) ? ? ? Ai?i ?1 i ?14. 用数学归纳法证明“从 n 个不同元素中每次取出 r 个不同元素的