集合论

来自计算思维百科
跳转至: 导航搜索

数学的一个基本的分支学科,研究对象是一般集合。

基本概念

集合论在数学中占有一个独特的地位,它的基本概念已渗透到数学的所有领域。集合论或集论是研究集合(由一堆抽象物件构成的整体)的数学理论,包含了集合、元素和成员关系等最基本的数学概念。在大多数现代数学的公式化中,集合论提供了要如何描述数学物件的语言。集合论和逻辑与一阶逻辑共同构成了数学的公理化基础,以未定义的“集合”与“集合成员”等术语来形式化地建构数学物件。

在朴素集合论中,集合被当做一堆物件构成的整体之类的自证概念。

在公理化集合论中,集合和集合成员并不直接被定义,而是先规范可以描述其性质的一些公理。在此一想法之下,集合和集合成员是有如在欧式几何中的点和线,而不被直接定义。

发展

集合论的创始人是德国数学家康托尔(G.Cantor,1845-1918),他对集合论的思考与研究是从三角级数研究中产生的。1871年他给出了集合的定义,包括定义集合的交与并等基本运算。1872年他利用有理数的基本序列概念给出了无理数的定义,严格了实数理论,并建立了点集论。1874年他发表第一篇关于无穷集合的文章,用集合论证明了超越数存在且远远“多”于代数数,这在当时轰动了整个数学界。1878年他引进了无穷集的“势”,并提出了“连续性”问题。1883年给出了超限基数的定义等。

康托尔所创立的是朴素集合论,由于在定义上缺乏限制,最终可能会导致悖论。1908年,德国数学家策墨罗(E.Zermelo)建立了第一个集合论的公理系统。此后,从集合论出发,许多科学家推出了数学上许多重要的结论。100多年来,集合论迅速地发展,逐渐形成了公理化的集合论和抽象的集合论。而且,在集合论的基础上,先后建立了实变函数、复变函数、泛函分析、概率论、测度论和信息论等许多新兴的数学学科。

目前,集合论的发展远远地超过了数学学科的范畴,已经深入到各种学科和科技领域之中。集合论可以直接应用到计算机科学的各个分支,比如数据结构、编译原理、形式语言及数据库等等。

集合代数

集合代数是研究集合运算和集合关系的基本性质的学科,研究这些性质可以深入探究集合的本质,也有助于实际应用。集合代数相当于集合论中的算术代数,它是关于集合论运算,如交集、并集、补集,以及集合论关系,如等于、包含等。

集合是由它的元素构成的,通常集合用大写的英文字母表示。例如,Z表示全体整数构成的集合,称为整数集;Q表示全体有理数构成的集合,称为有理数集;R表示全体实数构成的集合,称为实数集;C表示全体复数构成的集合,称为复数集。

集合有两种常见的表示法,即列举法和描述法。

① 列举法(Enumeration Method):把集合中的元素一一列举出来。例如,

字母集A={a, b, c, …, z}

自然数集N={0, 1, 2, 3, …}

② 描述法(Description Method):用文句来描述一个集合由哪些元素构成,即{x | 关于x的一个命题P},通常也称为谓词法。例如上述集合可以表示为:

字母集A={x | x是英文字母}

自然数集N={x | x是自然数}

一般来说,集合的元素可以是任何类型的事物,但集合的元素构成具有如下共性:互异性(即各不相同)、无序性(即不考虑顺序)、确定性(即元素是明确的)。集合也可以没有元素,这种没有元素的集合称为空集。此外,由一个元素构成的集合,称为单点集。当集合A中元素个数有限时,称A为有限集,否则称为无限集。

集合代数是系统研究如何进行集合表示以及集合运算和集合关系的操作,主要包括子集、空集、幂集,集合的并、交、补、差、对称差,有限集合的容斥定理及有限集的子集的表示方法等。利用特征函数的定义,可以简化集合的运算性质的证明。

二元关系

宇宙间存在着各式各样的联系,这些联系正是各门学科所研究的主要对象。不论是社会科学,还是自然科学,可以说关系是无所不在的。生活也有各种关系,例如血缘关系,师生关系,雇主与雇员之间的关系等等。在计算机科学中,关系的概念在数据库、信息检索、算法分析和程序设计等方面都起着很重要的作用。

作为一个数学的概念,关系是由至少两个集合在给定的条件下所产生的新的集合。在某些特殊的情况下,它是从一个集合到它自身所构成的新的集合。集合中表示两个元素之间的关系称为二元关系;表示三个或三个以上的元素之间的关系则称为多元关系。

因为二元关系本身也是集合,所以可以用集合的列元素法和谓词表示法,也可以用其他表示法,如列表、图解、矩阵等。二元关系的性质有自反性、对称性和传递性等。二元关系的运算除了并、交、差、补等基本运算外,还有关系的逆运算、复合运算和闭包运算等。在众多的关系中有两种特殊的关系值得特别研究。一种是偏序关系,它揭示集合中元素间的某种次序;另一种是等价关系,这个概念在数学的不少领域成为引进新概念的工具。

函数

随着数学研究的不断进步,人们逐步发展并完善了对函数的认识。以前有人用三角级数表示函数,而不考虑这些级数的收敛与否,终因引起混乱而遭到批评。18世纪的数学家大多相信函数必须有统一的解析表达式,函数的原型是代数函数等。但是欧拉、拉格朗日、傅立叶和狄利克雷等人的工作使得函数的概念更为清晰。

到目前为止,数学家大多接受函数的两种观点:一是视函数为规则,函数是自变量确定后得到因变量的规则;二是视函数为图像,函数可以用图描绘出来。函数也常称为映射或变换。

根据函数具有的不同性质,可以将函数分成不同的类型。比如满射函数、单射函数和双射函数,常值函数和恒等函数,以及单调递增函数和单调递减函数等。

函数是一种特殊关系,对关系可以进行运算,自然对函数也可以进行运算,即如何由已知函数运算得到新的函数。函数的复合运算是利用两个具有一定性质的已知函数,通过复合运算可以得到新的合成函数。通过逆运算施加于函数,可以得到逆函数。

函数是许多数学工具的基础。在计算机科学中,诸如逻辑理论、自动机理论、可计算性理论等都有着广泛地应用。

集合的基数

集合的基数就是指集合的元素个数的多少。对于有限集来说,基数就是集合所含元素的个数。但对于无穷集,它所含的元素有无穷多个,这时如何去“数”这个集合的元素?自然数集的元素比整数集少吗?自然数集与有理数集有一样多的元素吗?为了回答这些问题,首先要确定两个集合元数相等(即有相同基数)的条件,定出几个标准集合的基数,然后再考虑集合的元素多少。

集合的基数是有限集元素个数概念的推广和精确化,主要内容有集合的等势、有限集与无限集、可数集与不可数集以及较为常见的集合的基数等。集合的基数也是集合的一种性质,一种与该集合等势的集合构成的集合族的共同性质。