这是一本面向计算机科学与技术类专业和数学专业，全面介绍康托集合论基础知识的教材。 本书基于计算机科学与技术一级学科人才培养科学理论，按照计算机科学与技术学科教材系列一体化设计的纲要，全面介绍了康托素朴集合论的基本内容，包括集合的基本概念和基本运算、映射与关系、基数理论、序数理论和素朴集合论的公理化发展。该书按照知识发现的逻辑及其历史脉络来组织有关内容，并将数学学科方法论的有关内容融入到教材中，突出数学思想与方法的介绍。同时，尽可能揭示出集合论与计算机科学与技术之间的联系，使学生感到学有所用。这样做，不但有助于提高学生学习的兴趣，调动其学习的积极性，培养学生的创新能力，而且有利于使学生的知识融会贯通。 该书可作为计算机科学与技术类专业和数学专业“集合论”课程的教材，也可供高等学校的教师、学生和广大工程技术人员学习集合论时参考。基于计算机科学与技术一级学科人才培养科学理论

前 言 12 年前，我在计算机科学与技术暑期高级研讨班(贵阳·花溪)上学习了“程序设计语言的形式语义学”和“模型论”两门课程后，深感计算机科学与技术专业的学生仅就其在“离散数学”课程中学习的那点集合论的基础知识，要支撑包括这两门在内的一批后续计算机科学核心课程的学习是远远不够的。因此，从那时起就一直寄希望于国内计算机教育界能够编写一本更深入一些的集合论基础的教材，以满足深入学习的需要。很遗憾，十多年时间过去了，一直没能看到这样的教材。 直到去年，为我校计算机科学与技术专业2010 级教育与教学改革试点班的学生开设“集合论与图论”课程时，对照新要求，选择一本合适的教材这件事着实让我为难，这促使我下决心抽出时间自己编写一本，以满足教学改革的需要。幸好，去年春天，北京师范大学数学学院的罗里波先生应邀参加了在我校召开的“2012 年春季全国计算机科学与技术教育与教学改革工作会议”，会议期间我把欲编写一本集合论基础教材的想法告诉了他，先生欣然表示支持。于是，会后我就开始积极地思考起本书的创作原则和内容体系，并与厦门大学的赵致琢教授多次讨论有关的学术问题，直到去年暑假前，才把本书的创作原则 和内容体系理出一个眉目来。 既然本书的内容是集合论基础，那么，其重点应该侧重素朴集合论的一些基本思想、概念、理论、方法、技巧等基本知识的介绍，而不是纯粹形式化的公理集合论的内容。当然，本书所选内容对于数学、电子科学与技术、计算机科学与技术等专业的学生来说应该是自足的，同时还要保持素朴集合论自身体系的完整性和系统性，以便使学生对素朴集合论的整体结构有一个比较清晰的了解，这是作者编写本教材所坚持的第一原则。 本科教育是高等教育的基础教育，其目的在于提高人的素质。在本科教育中，不但要为学生未来成长打下厚实的基础，而且更重要的是在夯实基础的同时，培养学生科学的思想方法，使学生获得未来自主更新知识、创造新知识的能力。为此，在教材的创作中，要按照知识发现的逻辑及其历史脉络来组织教材内容，并将数学学科方法论的有关内容融入到教材中，突出数学思想与方法的介绍，这是作者编写教材所坚持的第二原则。 基于上述两个创作原则，全书的内容体系构成如下： 第0 章是绪论，介绍对课程认知和导学的内容，它是认知课程和导学的纲，也是教材具体内容的抽象总结； 第1 章是集合的基本概念和基本运算，主要介绍集合的基本概念、基本运算及其性质； 第2 章是映射与关系，主要介绍映射概念的由来、内涵及其性质，映射的运算及其性质，以及常见的两种关系——等价关系与序关系，进而介绍一般关系的概念、运算和性质； 第3 章和第4 章分别是基数和序数，它们是康托无穷集合论的两个重要组成部分，也是全书的核心部分； 第5 章是素朴集合论的公理化，主要介绍素朴集合论公理化的背景、目标和ZFC 公理化系统框架。 当确定了创作原则和内容体系后，我于去年暑假开始了教材的写作。尽管由于上课、管理工作和其它琐事常干扰我的编写工作，但还是因为教学急需所迫，只好用上所有的课余闲暇，包括春节，历时近10 个月，终于完成了教材的初稿(内部讲义)。为了提高教材的质量，今年春天，结合石家庄经济学院(原河北地质学院)计算机科学与技术专业的教育与教学改革项目工作，在2011 级学生中进行了改革试验，由我担任课程的主讲教师。经过8 周课程的教学实践，发现、修正和改进了原稿中存在的错误和不足，使得讲义得以印刷。 通过这一次的教学试用和总结，提出以下几点意见供使用者参考：（1）课程安排课堂讲授30 学时是必要而且是恰当的(带*号的部分不作教学要求)。根据计算机科学与技术一级学科教育与教学改革的内容要求和计算机科学与技术一级学科系列教材一体化设计、规划和建设报告，由于第1 章的内容在“计算机科学与技术导论”课程(参见文献[54])中已有详细介绍，因此在授课时这一章的内容可以略过不讲，由学生在假期提前复习或自学。课程教学的重点在于第2、3、4 章的内容。（2）为了在规定的学时内完成教学任务，同时为了培养学生的自学能力，我们不赞成目前应试教育背景下中学数学课程所普遍使用的授课方式，即将内容讲得详之又详，面面俱到，不给学生留下任何思考的余地和悬念，试图在课 堂上解决“所有”问题，生怕学生有学不会的内容的做法。针对中国基础教育培养的学生，为了造就高素质创新人才，有必要在大学的课程体系内，有针对性地选择一些难度不是很大的课程，有意识地通过改进授课的方式方法，培养学生自主更新知识，独立思考，勇于探索、创新的能力。我们倡导的大学的授课方式是：讲思想、讲思维、讲思路、讲框架、讲方法、讲重点、讲难点、讲感悟。只有这样，才能真正使授课内容少而精，才能使学生真正感受到数学思想和思维的强大威力，体会到知识内在的逻辑和发现规律的快乐；也只有这样，才能使学生在启发式教育下，真正积极、主动地思考问题，通过艰苦的阅读、训练、思考、探索、感悟、归纳、总结，才能真正培养学生强大的自学能力，探索精神、创新意识和能力。而这种意识和能力的培养正是中国大学课堂教学改革所要努力的方向。（3）由于该课程的难度远比数学分析和高等代数要小，计算机科学与技术专业的学生由于在学习了前两年的基础数学课程之后，已经初步实现了思维方式的数学化，因此，在集合论基础部分的教学中，为了节约学时，建议教师使用PPT 课件的方式教学，这样可以把节约下来的时间留给“集合论与图论”课程后续的图论部分的教学，为图论部分教学往深度和广度迈进奠定基础。 在教材即将付梓之际，要特别感谢北京师范大学数学学院的罗里波先生，从2007 年9 月到2010 年9 月，他在石家庄经济学院工作期间，我曾亲自聆听了他给年轻教师讲授的“形式语言与自动机理论”、“数理逻辑基础”、“可计算性与计算复杂性理论”、“模型论”、“抽象代数和范畴论”等五门课程，为本书的写作做了十分有益的准备。另外，在写作的过程中，我还经常通过电话向他请教问题，罗先生总是不厌其烦地给出满意的回答。还要特别感谢南京航空航天大学计算机学院的朱梧槚先生，我不仅从他的著作中吸收了很多好东西，而且也曾多次通过电话向他请教，尽管我们不曾谋过面，不过从与他热情的交流中可以看到老一代学者的诲人不倦、乐意提携后人的高尚品质。谢谢这两位国内知名的从事集合论研究的学者！ 感谢厦门大学计算机科学与技术系教授赵致琢博士，尽管他没有直接参与本书的创作，但是书中“将学科方法论的内容贯彻到教材的始终”的思想源于他(1996 年下半年，他在给我的一封信中谈到教材建设问题时，明确提出了这一思想)。赵致琢教授对计算机科学与技术教育事业倾注了大量心血，提出了“科学办学，内涵发展”的高等教育办学思想和计算机科学与技术一级学科人才培养的科学理论体系，他对我国计算机科学与技术教育事业的发展可谓贡献良多。近30 年来，我一直在他的指导下从事计算机科学与技术专业教学和科学研究工作，他的勇往直前、追求真理的精神永远激励着我。谨将本书献给这 位值得尊敬的导师！作者十分怀念原武汉大学和中国地质大学(武汉)教授康立山先生。尽管康先生已经离开了我们，但他的音容笑貌和谆谆教诲却常常浮现在我的眼前。康先生的严谨求真的治学风范，精深厚重的学术修养，宽慈谦和的人格魅力，春风化雨的教育精神深深感染着我，促使我尽全力把本书的写作工作做好。谨以本书纪念我的导师——康立山先生！ 我还要感谢石家庄经济学院2011 级计算机科学与技术专业教学改革试点班上的所有学生和年轻老师，是他们在我边创作，边讲授，边交付内部印刷使用的情况下，积极踊跃地提出问题，发现并更正了讲义中的错误，使我能够创造性地完成这项试验任务。此时，我对“教学相长”这一成语有了更深刻的感悟，也使我更加钦佩美国著名的物理学家、物理学思想家和物理学教育家惠勒(John Archibald Wheeler，1911—2008)教授对“大学真谛”问题的精辟回答，他说：“大学里为什么要有学生？那是因为老师有不懂的东西，需要学生来帮助解答。”多么深刻的见解啊！惠勒教授的真知灼见永远值得我们深思。从这 个角度来说，本次的教学实践是成功的，我从这些学生们的身上看到了教学改革的希望，从而也更加坚定了教学改革的理想和信心。 刘坤起 二0 一三年十二月底于石家庄

目 录 第0 章 绪论——对“集合论”课程的认知与导学········1 0.1 对“集合论”课程的认知········1 0.1.1 集合论的发展简介········1 0.1.2 集合论的研究对象和要解决的基本问题········5 0.1.3 素朴集合论的基本原则、思想和方法········5 0.1.4 素朴集合论中的数学思想和方法········5 0.1.5 集合论与数学和计算机科学的关系········6 0.1.6 “集合论”课程的特点及其在学科专业教育中的地位和作用········7 0.2 对“集合论”课程的导学········7 0.2.1 本课程的学习方法········7 0.2.2 关于数学学科基本工作流程方式的讨论········ 11 0.2.3 关于数学学科知识结构的构建与学科知识的融会贯通问题的讨论········12 第1 章 集合的基本概念与基本运算········14 1.1 集合的基本概念········ 14 1.1.1 集合及其表示············· 14 1.1.2 集合之间的关系········· 16 1.2 集合的运算及其性质····· 17 1.2.1 集合的并、交、补、差、对称差、求幂集运算及其性质························ 17 1.2.2 集合的广义并、广义交运算及其性质··············· 21 1.3 有穷集和无穷集··· 22 附录1 集合论的基本思想和方法讨论之一——概括原则和外延原则····· 24 习题· 24 第2 章 映射与关系····26 2.1 映射······················ 26 2.1.1 函数概念的发展········· 26 2.1.2 映射的概念及其性质· 29 2.1.3 映射的合成（复合） · 36 ·XVI· 2.1.4 逆映射························ 39 2.1.5 运算是特殊的映射····· 40 2.2 关系······················ 41 2.2.1 等价关系···················· 41 2.2.2 序关系························ 47 2.2.3 关系···························· 54 2.2.4* 多元关系与关系数据库····· 67 2.2.5* 映射、谓词和集合··· 69 附录2A 数学研究的基本思想和方法讨论之一——抽象的方法··············· 71 附录2B 数学研究的基本思想和方法讨论之二——特殊化与一般化······ 71 习题· 72 总思考题······················· 73 第3 章 基数···············75 3.1 无穷集合··············· 75 3.1.1 两种不同的无穷观——潜无穷与实无穷··········· 75 3.1.2 可数（列）集············· 77 3.1.3 无穷集的特征············· 84 3.1.4 连续统························ 85 3.2 集合的基数及其比较····· 87 3.2.1 基数的概念················ 87 3.2.2 连续统假设················ 89 3.2.3 基数的比较················ 91 3.3 基数算术··············· 94 附录3A 集合论的基本思想和方法讨论之二——一一对应原则··············· 99 附录3B 集合论的基本思想和方法讨论之三——对角线方法···················· 99 习题100 总思考题······················100 第4 章 序数············· 102 4.1 自然数系统··········102 4.2 全序集的序型及其运算107 4.2.1 全序集的序型··········· 107 4.2.2 全序集序型的加法和乘法运算························ 109 4.3 良序集及其序型··111 ·XVII· 4.3.1 良序集······················ 111 4.3.2 良序集的序型——序数······ 115 4.3.3 序数与基数的关系··· 118 4.4 序数的比较··········120 4.5 超穷归纳法··········123 4.6 序数算术··············125 附录4A 集合论的基本思想和方法讨论之四——延伸原则和穷竭原则127 附录4B 集合论的基本思想和方法讨论之五——选择原则······················ 128 习题129 总思考题······················129 第5 章 集合论的公理化发展···························· 131 5.1 集合论的公理化背景和目标·······················131 5.1.1 集合论公理化的背景········· 131 5.1.2 集合论公理化的目标········· 133 5.1.3 集合论公理化的思想和方法···························· 133 5.2 序数和基数··········134 5.2.1 序数·························· 134 5.2.2 基数·························· 136 5.3 ZFC 公理化系统简介····137 附录5 数学研究的基本思想和方法讨论之三——公理化方法················ 140 习题142 参考文献···················· 143 附录 中英文名词对照········· 148 后记··························· 156