集合论初步和关系

第二篇集合论研究内容本篇由集合论初步、关系、有限集与无限集、函数四部分构成。集合论的发展历程集合论是现代各科数学的基础，它是德国数学家康托（GeogCantor,1845～1918）于1874年创立的。1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。罗素悖论1901年罗素提出以下悖论：设论述域是所有集合的集合，并定义集合这样，S是不以自身为元素的全体集合的集合，那么“S”是不是它自己的元素呢？罗素悖论起因于集合可以是自己的元素的概念。康脱以后创立的许多公理化集合论都直接或间接地限制集合成为它自己的元素，因而避免了罗素悖论。{|}SAAA罗素的理发师悖论住在一个村子里的理发师挂了一个牌子，上面写到：我只给不给自己理发的人理发。考虑这个理发师给不给自己理发？集合论发展的详细历程G.Cantor(康脱)是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯·诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。集合论的应用现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。第一章集合论初步集合是现代数学各分支的共同基础，当然也是本书的基础，要求熟练地掌握本章的全部内容。本章的一些内容，如集合的定义、并、交、文氏图等已在中学及大学的其他课程中学习过，但为了内容的完整及这些内容基础地位，仍然会简单介绍一下。本章主要讲述集合的基础理论、基本方法和应用。§1.1集合的基本概念集合的定义具有某种共同性质的事物汇集为一个整体称为集合。集合不能精确定义。一般用A、X等表示。元素构成这个集合的每一个事物称为元素。可以是具体东西，也可以是抽象的。任一元素或属于该集合或不属于该集合，记为aaAA或集合的表示方法列举法列出集合的所有元素。描述法用谓词来概括集合中元素的属性来表示这个集合。例：B＝{x|x∈R且x2－1＝0}表示方程x2－1＝0的实数解集。归纳定义法集合间的关系设A、B为集合，两集合的元素相等，则集合相等记为A=B；否则A≠B设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作。真包含关系:记作BA,BAxAxxBBA,.BAastaAaB且但注意集合、元素之间的关系属于关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如A＝{a，{a}}和B={a}，既有{a}∈A，又有{a}A。前者把它们看成是不同层次上的两个集合，后者把它们看成是同一层次上的两个集合，都是正确的。定义全集、空集及相关定理定义：全集---所有考虑对象的全体；空集---不含任何元素的集合；有限集---集合的元素个数为有限个；无限集---集合的元素个数为无限个。定理：设A、B是一集合，E为全集，有（1）（2）A=B的充要条件是A、B相互包含。AE集合代数（A、B为集合）A和B的交记为，定义为：A和B的并记为，定义为：A和B的差记为，定义为：A和B的对称差记为，定义为：A的补记为，定义为：若，则称A、B是分离的。AB{|}ABxxAxB且AB{|}ABxxAxB或AB{|}ABxxAxB且ABABA-BB-A)=(AB)-(AB)（）（AAEAAB集合运算的定律(1)交换律(2)结合律(3)分配律(4)幂等律ABBAABBA()()()()ABCABCABCABC()()()()()()ABCABACABCABACAAAAAA(5)同一律(6)零一律(7)吸收律(8)德摩根律(9)双补律UAAAAAUUA()AABA()AABA()BABA()BABAAA（）UU例1证明A－(B∪C)＝(A－B)∩(A－C)证：对任意x,有故A－(B∪C)＝(A－B)∩(A－C)xABCxAxBCxAxA且且(xB且xC)=(且xB)且(xA且xC)=xA-B且xA-C例2证明A∪(A∩B)＝A证：A∪(A∩B)＝(A∩E)∪(A∩B)＝A∩(E∪B)＝A∩(B∪E)＝A∩E＝A例3化简((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)。解：由A∪BA∪B∪C，AA∪(B－C)，有原式＝(A∪B)－A＝B－A例4证明ABBABAAB,ABBABxxAxAxBxABxBAB（1）证，或因此有A,AAAABABABABxxAxAxBxABAB（2）证显然，只需证，且因此有注意：上式给出了AB的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。AA（3）证AB=AA-B=A-B=AB=(AB）B=（BB）==（4）证Ａ－Ｂ=ＡＢ=ＢＡＢＢ（ＡＢ）＝Ｂ＝Ｂ§1.2幂集、n元有序组、笛卡尔乘积定义幂集设A是一个集合，A的幂集是A的所有子集的集合，即定理若集合A为n个元素的有限集，则A的幂集的元素个数为2n，因此A的幂集也记为2A。(){|}ABBA求下列集合的幂集例1例2例3Ｂ＝｛ａ，｝Ｃ＝Ａ＝｛０，１，２｝n元有序组定义：两个按照一定次序排列的客体a、ｂ组成一个有序序列称为有序偶，记以（ａ，ｂ）。其中ａ为第一客体，ｂ为第二客体。序偶相等：有序偶（ａ，ｂ）＝（ｃ，ｄ），如果有ａ＝ｃ，ｂ＝ｄ，则说序偶相等。例：平面坐标系中点的坐标。定义ｎ个按一定次序排列的客体组成一个有序序列，称为ｎ元有序组，并记以例：身份证号码时间的表示学生的学号１２ｎ｛ｘ，ｘ,．．．,ｘ｝笛卡尔乘积定义：集合Ａ、Ｂ的笛卡尔乘积表示为例1：一小时内的时间表示，某时某分（a,b）可用笛卡尔乘积表示。教材第12页。例2：A={1，2}，B={a,b},则ＡＢ＝｛（ａ，ｂ）ａＡ，ｂＢ｝ＡＢ＝｛（１，ａ），（１，ｂ），（２，ａ），（２，ｂ）｝几个定义集合A的笛卡尔乘积定义定义：集合Ａ、Ｂ、C的笛卡尔乘积表示为以此类推，可以定义n个集合的笛卡尔乘积考虑是否相等？ｎＡ＝ＡＡ．．．Ａ４ＡＡＡＡ和ＡＡＢC＝｛（ａ,b,c）ａＡ，ｂＢ,cC｝第二章关系在现实世界中，事物之间都有联系，单值依赖联系是事物之间联系中比较简单的，比如说日常生活中事物的成对出现，而这种成对出现的事物具有一定的顺序，例如，上、下；大、小；左、右；父、子；高、矮等等。通过这种联系，研究事物的运动规律或状态变化。世界是复杂的，运动也是复杂的，事物之间的联系形式是各种各样的，不仅有单值依赖关系，更有多值依赖关系。“关系”这个概念就提供了一种描述事物多值依赖的数学工具。这样，集合，映射关系等概念是描述自然现象及其相互联系的有力工具，为建立系统的、技术过程的数学模型提供了描述工具和研究方法。映射是关系的一种特例。本章主要讨论关系及其表示，关系的运算及一些常见的关系。关系是一个基本概念，在数学和计算机中用关系来描述各集合及各元素间的联系。§2.1关系的基本概念例设有两间学生宿舍a、b,有6位同学分配宿舍。讨论“某位同学住哪间宿舍”这种关系，用R来表示。设分配方案如下:1-a,2-b,3-b,4-a,5-a,6-a(1)可记为1Ra,2Rb,3Rb,4Ra,5Ra,6Ra；(2)也可用序偶的形式定义为R={(1,a),(2,b),(3,b),(4,a),(5,a),(6,a)}(3)从子集的角度上定义，设A={1，2，3，4，5，6}，B={a,b},R是笛卡尔乘积AB的一个子集。定义设A、B为集合，称的一个子集R为从A到B的一个二元关系。关系R中的有序偶即是集合R的元素。对于二元关系，若，则称ｘ、ｙ有关系Ｒ，可记作xRy；若，则记作。D(R):R的定义域。R中序偶的第一客体允许选择对象的范围。C(R):R的值域。R中序偶的第二客体允许选择对象的范围。AB,xyR,xyRxRy空关系：全关系：A上的关系：当集合A=B时，或者Ｄ（Ｒ）＝Ｃ（Ｒ）=A。定义：n元关系R是的一个子集。A上的恒等关系通常记IA。RRAB12...nAAA例子例1.设A={1,2}，B={2,3,4},{(1,3),(2,3)}，{(1,4)},,{(1,2),(2,2)}都是从A到B的二元关系，同时{(1,2),(2,2)}也是A上的二元关系。例2.实数集上的大于关系。例3.设A={2，3，4，5，6}，A上的整除关系。“/”=R={(2,2),(3,3),(4,4),(5,5),(6,6),(2,4),(3,6),(2,6)}关系的表示方法关系的表示方法有三种：集合表示法，关系矩阵和关系图。1.集合表示法因为关系是一个集合，因此可以用集合的列举法或描述法来表示它。在前面的叙述中，已经多次采用了这两种方法。例：R1={(a,b)|(a+b)/5是整数}用的是描述法，R2={(1,2),(2,4),(3,3)}用的是列举法。关系的图的表示通常可以用图来刻画关系。关系图使关系表示更直观。设,,RA×B,在平面上用°或·分别标出A、B中元素的点（称为结点）。如果，则自结点ai至结点bj作一条有向弧，箭头指向bj，采用这种方法连接起来的图称为R的关系图。},,,{21maaaA},,,{21nbbbBRbaji,例1设A={1,2,3,4},R={1,1,1,3,2,3,4,4}，R的关系图为：1423例2设A={1,2,3,4}，R是A上关系。R={(1,1),(1,2),(2,3),(2,4),(4,2)}，写出R的关系图。关系的矩阵表示关系矩阵：设，R是A上的关系，令，则称为R的关系矩阵，记作MR。关系矩阵为关系的运算提供了数学运算对象。12{,,,}nAxxx10ijijijxRxrxRx(,1,2,,)ijn111212122212