离散数学之集合论

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。

本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。

第2-1章 集合及其运算

§2-1-1 集合的概念及其表示

一、集合的概念

“集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

a A，读作“a属于A”。否则，若a不属于A，就记为a A，读作“a不属于A”。一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。

集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{ }”在两边括起来，表示这些元素构成整体。

例2-1-1.1 A＝｛a , b , c , d｝； B＝｛1 ，2 ，3 ， ｝ ；

D＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；E {a,a2,a3, }。 集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设x为某类对象的一般表示，P(x)为关于x的一个命题，我们用{xP(x)}表示“使P(x)成立的对象x所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。

例2-1-1.2 全体正奇数集合表示为 S1 {xx是正奇数}，

所有偶自然数集合可表示为 E {m2m且m N} 其中 2|m表示2能整除m。

[0,1]上的所有连续函数集合表示为 C[0,1] {f(x)f(x)在[0，1]上连续}

集合的元素也可以是集合。例如S {a,{1,2},p,{q}}，

{1,2} S，但必须注意：q {q}，而q S，同理1 {1,2}，S a {1，2} p

1 2 {q} q 而1 S。

两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合A，B相等，记作A B，两个集合不相等，记作A B。

集合中的元素是无次序的，集合中的元素也是彼此不相同的。

例如： {1,2,4} {1,4,2},{1,2,4} {1,2,2,4},

{{1,2}，4} {1,2,4},{1,3,5, } {xx是正奇数}。

集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程 x2 1 0的实根的集合是空集。

二、集合与集合间的关系

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。

定义2-1-1.1 设A，B是任意两个集合，如果A中的每一个元素都是B的元素，则称A是B的子集，或A包含于B内，或B包含A。记作A B，或B A。

即 A B x(x A x B)

可等价地表示为 A B x(x B x A)。

例2-1-1.3 设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则 N Q R C，

{1} N,{1,1.2,9.9} Q,{2, } R。

如果A不是B的子集，则记为A B（读作A不包含在B内），显然，

A B x((x A) (x B))。

集合间的包含关系“ ”具有下述性质：

2-1-1. 自反性 A A；

2. 传递性 (A B) (B C) (A C)。

证明：采用逻辑演绎的方法证明。

⑴ A B P

⑵ x((x A) (x B)) T(1)E

⑶ (a A) (a B) US(2)

⑷ B C P

⑸ x((x B) (x C)) T(4)E

⑹ (a B) (a C) US(5)

⑺ (a A) (a C) T(3)(6)I

⑻ x((x A) (x C)) UG(8)

⑼ A C T(8)E

离散数学四大核心：代数系统、集合论、数理逻辑、图论。

定义2-1-1.2 如果集合A的每一元素都属于集合B，而集合B中至少有一元素不属于A，则称A为B的真子集，记作A B。

即 A B x((x A) (x B)) x((x B) (x A))

例如：{a,b}是{a,b,c}的真子集；N是Q的真子集，Q是R的真子集；R是C的真子集。

注意符号“∈”和“ ”在概念上的区别，“∈”表示元素与集合间的“属于”关系，“ ”表示集合间的“包含”关系。

定理2-1-1.1 集合A＝B的充分必要条件是：A B且B A。（外延性原则） 证明：必要性， 即证：A B (A B) (B A)

A B ( x((x A) (x B))) ( x((x B) (x A))) (A B) (B A) 充分性，即证：(A B) (B A) A B

A B x((x A) (x B)) A B (A B) (A B) F

或 A B x((x B) (x A)) B A (B A) (B A) F # 定理2-1-1.2 对于任一集合A， A，且空集是唯一的。

证明： 假设 A为假，则至少存在一个元素x，使x 且x A，因为空集 不包含任何元素，所以这是不可能的。

设 与 都是空集，由上述可知， 且 ，根据定理2-1-1.1知 ，所以，空集是唯一的。

注意： { }， {xP(x) P(x)} P(x)是任一谓词。

例2-1-1.4 设 A {2,3},B为方程 x2 5x 6 0的根组成的集合，则 A＝B 。

定理2-1-1.1指出了一个重要原则：要证明两个集合相等，即要证明每一个集合中的任一元素均是另一集合的元素。这种证明是靠逻辑推理理论，而不是靠直观。证明两个集合相等是应该掌握的方法。

定义2-1-1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全

离 …… 此处隐藏：2962字，全部文档内容请下载后查看。喜欢就下载吧 ……