离散数学高等里离散数学-课件-CHAP4.ppt

离散数学 第四章 可数集与不可数集 §4.1 等势 等势 定义4.1.1：设A和B是集合，若存在A到B的双射，则称A与B等势，记为A ~ B .(可形象理解为A与B的元素一样多。) “~”是一个等价关系。(请证之?) 例1 自然数集N与偶自然数集E是等势的，其中定义N到E的双射?为： ?(n) = 2n , n∈N. 有限与无限 定义4.1.2：设Nn={0,1, ? , n– 1} , n?1 ,若集合A与Nn等势，则称A为有限集；否则称A为无限集。 无限多的自然数 定理4.1.1 自然数集合N是无限集。 证明：设n∈N，n ?1 , 令?是从Nn到N的映射，Nn={0,1, ? , n–1} ，下证?不是双射。 令k=1+max{?(0), ?(1), ? , ?(n–1)} , 于是k∈N，但对任意x∈Nn ,均有?(x) ≠k , 因此，?不是满射，更不是双射。由定义知，N为无限集。 抽屉原理 定理4.1.2 任何有限集均不能和其真子集等势 此定理也称为抽屉原则：若将n+1个物体放入n个抽屉中，则至少有一个抽屉中放了两个或两个以上的物体。 抽屉原则对无限集并不总是成立，即无限集能够与其真子集等势。这是无限集合的一个非常重要的性质。 我们已经看到自然数集合等势于它的真子集，偶数集合。下面我们再给一个例子。 正实数和全体实数一样多 令R和R+分别为实数集合和正实数集合，即R+={x∈R | x 0} ，显然，R+ ? R ，即R+是R的真子集。但是R~R+ 证明：定义映射 f 如下： f (x) = ex , x∈R 于是，对任意的x∈R，存在唯一的y∈R+ ,使 y = ex = f (x) ； 另一方面，对任意的y∈R+ ,存在唯一的 x =lny∈R , 使 f (x) = ex = elny = y , 这说明 f 是R到R+的一个双射。因此， R~R+ 。 §4.2 集合的基数 几个记号 同有限集合中元素的个数的记法一样，集合A的基数用 |A|表示。 每个有限集合都与某个集合Nn= {0,1, ? , n–1}等势，其中n ? 0 , N0 = ?。如果A ~ Nn , 则A中有n个元素，即|A| = n; 若A为无限集，则用一个特殊的符号?i(读作阿列夫i，i是一个正整数)来表示它的基数。例如，对于自然数集合N，令|N| = ?0 ( 读作 “ 阿列夫零 ” ) 。 如何比较集合的大小 (1)若A~B ,即存在A到B的双射，则称它们的基数相等, 记为|A|=|B|。 (2)若存在A到B的单射，则称A的基数小于或等于B的基数，记为|A| ? |B|；或称A的基数大于或等于B的基数，记为|B| ? |A|。 (3)若两者基数不等且|A|?|B|，则记为|A| |B|。 集合大小是可比的 定理4.2.1 设A和B为两个集合，总有 |A| ? |B|或者|B| ? |A| 。(即任意两个集合总可比较大小。） 等势是集合间的等价关系 定理4.2.2： 基数之间的相等关系“= ”是一个等价关系,即对任何集合A , B和C, 有: (1)|A|=|A|; (2)若|A|=|B| ,则 |B|=|A|; (3)若|A|=|B|且|B|=|C| , 则|A|=|C| . 基数间的≤是偏序关系 定理4.2.3 基数之间的小于或等于关系“? ”是一个偏序关系,即对任何集合A , B和C, 有: (1)|A| ? |A|; (2)若|A| ? |B|且|B|? |A| ,则 |A|=|B|; (3)若|A| ? |B|且|B| ? |C| , 则|A| ? |C| . 几个关于基数的问题 我们知道自然数有无限多个。那么自然数集合是不是就是最大集合的呢？ 如果自然数集合不是最大的，那么比它更大的集合是什么样的呢？ 是不是存在最大的基数呢？ 不！不存在最大的集合。山外有山，天外有天。我们的口号是：没有最大，只有更大 ！ 山外青山楼外楼 定理4.2.4 对任意集合A,均有|A| |? (A)| ,其中?(A)为A的幂集。 证明： 令 f : A??(A)。f (a) ={a}， a∈A。 显然，f 是单射,于是|A|? |?(A)| . 显然，象集{ {a} | a∈A }是?(A)的真子集，所以，f 不是满射，从而不是双射。于是我们有|A| ＜ |?(A)|。 山外青山楼外楼 假设|A| = |?(A)|，则存在A到?(A)的双射g . 令B={a∈A | a ? g(a)} (