第二部分 集合论
引言
集合是数学中最为基本的概念，又是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的一个分支。
G.康托尔是作为数学分支的集合论的奠基人。1870年前后，他关于无穷序列的研究导致集合论的系统发展。1874年他发表了关于实数集合不能与自然数集合建立一一对应的有名的证明。1878年，他引进了两个集合具有相等的“势”的概念。然而，朴素集合论中包含着悖论。第一个悖论是布拉利-福尔蒂的最大序数悖论。1901年罗素发现了有名的罗素悖论。1932年康托尔也发表了关于最大基数的悖论。 集合论的现代公理化开始于1908年E.策梅罗所发表的一组公理，经过A.弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。另外一种系统是冯*诺伊曼-伯奈斯-哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。K.哥德尔证明了连续统假设与策梅罗-弗兰克尔集合论的相容性，P.J.科恩证明了连续统假设与策梅罗-弗兰克尔集合论的独立性。现在把策梅罗-弗兰克尔集合论与选择公理一起称为ZFC系统。
本部分主要介绍朴素集合论的主要内容，其中包括集合代数（第六章）、二元关系（第七章）、函数（第八章）、集合的基数（第九章）等。 本部分的先行知识及各部分的关系如下图所示：
6.1 集合的基本概念
一．集合的表示
集合是不能精确定义的基本概念。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如：
方程x2－1＝0的实数解集合；
26个英文字母的集合；
坐标平面上所有点的集合；
……
集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
表示一个集合的方法有两种：列元素法和谓词表示法，前一种方法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。例如
A={a，b，c，…，z}
Z={0，±1，±2，…}
都是合法的表示。谓词表示法是用谓词来概括集合中元素的属性，例如集合
B＝{x|x∈R∧x2－1＝0}
表示方程x2－1＝0的实数解集。许多集合可以用两种方法来表示，如B也可以写成{-1，1}。但是有些集合不可以用列元素法表示，如实数集合。
集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素，如
{1，1，2，2，3}＝{1，2，3}
集合的元素是无序的，如
{1，2，3}＝{3，1，2}
在本书所采用的体系中规定集合的元素都是集合。
元素和集合之间的关系是隶属关系，即属于或不属于，属于记作∈，不属于记作，例如
A＝{a，{b，c}，d，{{d}}}
这里a∈A，{b，c}∈A，d∈A，{{d}}∈A，但bA，{d}A. b和{d}是A的元素的元素。可以用一种树形图来表示这种隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。上述集合A的树形图如图6.1所示。图中的a，b，c，d也是集合，由于所讨论的问题与a，b，c，d的元素无关，所以没有列出它们的元素。鉴于集合的元素都是集合这一规定，隶属关系可以看作是处在不同层次上的集合之间的关系。
为了体系上的严谨性，我们规定：对任何集合A都有A
A。
二．集合之间的关系
下面考虑在同一层次上的两个集合之间的关系。
定义6.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的
子集合，简称子集。这时也称B被A包含，或A包含B，记作B
如果B不被A包含，则记作B
包含的符号化表示为
B
例如N
显然对任何集合A都有A
A。
Z
Q
R
C，但Z
N。
A
x(x∈B→x∈A)
A。
A。
隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。例如
A＝{a，{a}}和{a}
既有{a}∈A，又有{a}
A。前者把它们看成是不同层次上的两个集合，后者把它们看
成是同一层次上的两个集合，都是正确的。
定义6.2 设A，B为集合，如果A
如果A与B不相等，则记作A≠B。
相等的符号化表示为
A＝B
A
B∧B
A
B且B
A，则称A与B相等，记作A＝B。
定义6.3 设A，B为集合，如果B
A。
如果B不是A的真子集，则记作B
真子集的符号化表示为
B
例如N
Z
Q
R
C，但N
A
B
A∧B≠A
A且B≠A，则称B是A的真子集，记作B
A。
N。
定义6.4 不含任何元素的集合叫做空集，记作
空集可以符号化表示为
＝{x|x≠x}。
。
例如{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集，因为该方程无实数解，所以是空集。