4.1 有限集合
无限的概念是用集合的语言表达的。集合是一系列可区分对象的合集。这些对象可以是任何事物和所有事物(包括其他集合)。集合中的对象称为该集合的元素。集合可以用大括号包围其元素的形式表示。所以集合
{a,b,c}
有3个元素,分别是字母a、b和c。我们可以谈论某个班级的学生组成的集合、红色汽车组成的集合、美国居民组成的集合、分数组成的集合等。
集合有多种不同的表示方法。我们可以逐个列出集合的元素,如
{狗,猫,鹦鹉,鱼,蛇}
我们也可以用描述的方式表示同一个集合:
{ x : x 是5种最受欢迎的家养宠物之一}
这个集合读作“包含所有 x 的集合, x 是5种最受欢迎的家养宠物之一”。还有一个例子:
{3,5,7,9,11}
它和下面这个集合是一样的:
{ x : x 是大于等于3并小于12的奇数}
在谈论无限集合的时候,我有时会用省略号(…)表示这个集合是无限延伸的。例如,素数的集合可以写成
{2,3,5,7,11,13,…}
大写字母可以作为描述特定集合的名称:
D ={1,3,5,7,9,11,13,15,…}
对于两个集合而言,如果每个集合的每个元素都是另一集合的元素,反之亦然,那么这两个集合是相等的。所以如果
F ={ x : x 是奇数}
很显然,
D = F
某些集合会成为其他集合的子集合,简称子集。某个班级女生的集合很显然是该班级所有学生的集合的子集。这是因为这个班级的每个女生都是班上的学生。一般而言,对于两个集合 S 和 T ,如果 S 的每个元素都是 T 的元素,我们就可以说 S 是 T 的一个 子集 。需要注意的是, T 的子集也可以等于集合 T 本身。如果 S 是 T 的子集且不等于 T ,那么 S 就是 T 的 真子集 (proper subset)。也就是说,如果某个子集等于整个集合的话,它就不是该集合的真子集。如果 T 的某些元素不是 S 的元素,那么 S 就是 T 的真子集。就元素的数量而言,如果 S 的元素数量少于或等于 T , S 就是 T 的子集。如果 S 的元素数量少于 T ,那么它就是 T 的真子集。当我们在4.2节遇到无限集合时,关于有限集合的这一显而易见的事实将成为关键问题所在。
存在一个特殊的集合,它没有任何元素。这个集合叫作空集,表示为∅。对于任意集合 S 而言,下列命题都是正确的:
∅的每个元素也是 S 的元素。
因为∅中没有元素,所以∅是 S 的子集。
对于任意集合
S
,我们将
S
的所有子集组成的集合称为
S
的
幂集
(powerset),表示为
(
S
)。例如,如果
S
={
a
,
b
},则:
( S )={∅,{ a },{ b },{ a , b }}
注意,这个集合拥有4个元素,其中3个是 S 的真子集。如果 S 有3个元素,例如 S ={ a , b , c },那么 S 的幂集除了拥有之前的子集即∅,{ a },{ b },{ a , b }之外,还可以在这些子集的每一个中加上一个元素 c ,于是我们得到了子集{ c },{ a , c },{ b , c },{ a , b , c }。所以我们有
({
a
,
b
,
c
})={∅,{
a
},{
b
},{
a
,
b
},{
c
},{
a
,
c
},{
b
,
c
},{
a
,
b
,
c
}}
也就是说,通过在集合 S 中加入元素 c ,子集的数量翻了一番。对于含有两个元素的集合,其幂集含有4个元素。对于含有3个元素的集合,其幂集含有2×4=8个元素。对于含有4个元素的集合,其幂集含有2×8=16个元素。一般地,含有 n 个元素的集合的幂集拥有
![](https://bookbk.img.zhangyue01.com/group62/r2/du/e1f699b73ff9e7fb7bd4df402c36eb21.jpg?v=DnWGRrTq&t=fwAAAWZJaJA.)
个元素。所以通常情况下,一个集合的幂集比该集合大得多。两个集合在什么情况下大小相等呢?思考集合
S ={ a , b , c , d , e }
和家养宠物集合
T ={狗,猫,鹦鹉,鱼,蛇}
这两个集合很显然大小相等:它们都拥有5个元素。然而不如让我们用另一种方式审视这一显而易见的事实。 S 和 T 大小相等,是因为我们可以将 S 的每一个元素与 T 的每个独一无二的元素一一对应起来。也就是说, S 和 T 大小相等,因为存在某种关联可以将 S 的每个元素与 T 的每个独一无二的元素配对,反之亦然。对 S 的每个元素来说,集合 T 中都有一个独一无二的对应元素,而对 T 的每个元素来说,集合 S 中也有一个独一无二的对应元素。这种配对关系可以用下图表示:
![](https://bookbk.img.zhangyue01.com/group62/tX/Xp/a9978233cba6f1b7e8c0e70485176377.jpg?v=6QXiiXy7&t=fwAAAWZJaJA.)
这两个集合还存在其他配对关系,例如,
![](https://bookbk.img.zhangyue01.com/group62/4B/TO/53b5eec71cce2a092a41616a5b8d5bd5.jpg?v=6JERS1vU&t=fwAAAWZJaJA.)
实际上, S 和 T 都能与下列集合建立这种关联:
{1,2,3,4,5}
在这些对应关系下,我们可以很确定地说,所有这些集合都拥有5个元素。
这个简单的概念是本章的核心。如果任意两个集合 S 和 T 之间存在这种对应关系,我们会说它们是 等势的 (equinumerous)或大小相等的。这两个集合会被认为拥有相等的 势 (cardinality)。
等势集合的例子非常多,举例如下。
•全世界人类心脏的集合与全世界人类的集合大小相等。(注意,这不能推广到耳朵上,因为人一般有两只耳朵。)
•美国各州的集合
{亚拉巴马州,阿拉斯加州,亚利桑那州,…,威斯康星州,怀俄明州}
可以和美国各州政府驻地的集合建立对应关系:
{蒙哥马利,朱诺,菲尼克斯,…,麦迪逊,夏延},
后者可以和下面的集合建立对应关系:
{1,2,3,…,49,50}。
•国际标准书号(ISBN)的集合可以和出版图书的集合对应起来。
有限集合的世界以及它们之间的对应关系非常直截了当。对两个集合大小相等的定义是绝对合理的。现在让我们向前踏出一小步,进入无限的疆域吧。