[离散数学之集合论.doc

第二篇 集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章 集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素属于集合记作，读作“属于”。否则，若不属于，就记为，读作“不属于”。一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。 集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{ }”在两边括起来，表示这些元素构成整体。 例2-1-1.1 ＝｛a , b , c , d｝； ＝｛1 ，2 ，3 ，＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；。 集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设为某类对象的一般表示，为关于的一个命题，我们用表示“使成立的对象所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。 例2-1-1.2 全体正奇数集合表示为 ， 所有偶自然数集合可表示为 其中 2|m表示2能整除m。 [0,1]上的所有连续函数集合表示为 集合的元素也可以是集合。例如， 但必须注意：，而，同理，，而。 两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合，相等，记作，两个集合不相等，记作。 集合中的元素是无次序的，集合中的元素也是彼此不相同的。 例如： 。 集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程 的实根的集合是空集。 二、集合与集合间的关系 “集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。 定义2-1-1.1 设，是任意两个集合，如果中的每一个元素都是的元素，则称是的子集，或包含于内，或包含。记作，或。 即 可等价地表示为 。 例2-1-1.3 设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则 ， 。 如果不是的子集，则记为（读作不包含在内），显然， 。 集合间的包含关系“”具有下述性质： 2-1-1. 自反性 ； 2. 传递性 。 证明：采用逻辑演绎的方法证明。 ⑴ P ⑵ T(1)E ⑶ US(2) ⑷ P ⑸ T(4)E ⑹ US(5) ⑺