工科离散数学课件 第五章 5_3_集合的基数(3) - 可数集与不可数集.pptx

5.3.3 可数集与不可数集5.3 集合的基数-可数集与不可数集[可数集&不可数集] 与自然数集?等势的集合称为可数集。不可数的无限集称为不可数集。可数集 = 可列集。问：“可数”如何理解？答：“可数” 就是无论指定集合中的哪个元素，总可以从头数到它。如果A~?，可以将A的元素与?对应地排列，从而A也是可数的。问：为什么可数集又称为可列集？答：若A是可数集，则存在双射 f： ?→A ，于是，A 的元素可列成 a0 = f (0)， a1 = f (1)， a2 = f (2)， … 可列就是指排成一行或一列。 ——“证明：设A的元素为a0, a1, a2, …”，对吗？ [至多可数集] 有限集和可数集的统称。——无限集包括可数（无限）集和不可数（无限）集5.3 集合的基数-可数集与不可数集定理：可数集的无限子集是可数集。证明：设A是可数集，B 为A的无限子集。若A的元素可排列成如下形式：a0, a1, … ,an, …对于 B 的任意元素，从a0开始，沿此排列顺序搜索并不断舍弃非 B 的元素，即可数到 B 的指定元素，并建立起B 与N之间的一一对应：ai0, ai1, … , ain, …故B是可数集。 5.3 集合的基数-可数集与不可数集例5-10： 证明可数个可数集的并是可数集。证明：记 Ai ={ai1, ai2, ai3 , … ,} ，i = 1, 2, 3, …是可数个可数集，不妨假定它们互不相交。令A = ??i =1 Ai，将其元素如图排列，规律是每条斜线上的元素的两个下标之和相同。从a11开始，按箭头方向所指的下标之和逐渐增大的方式排列: a11,a21,a12,a31,a22,a13,a41,a32,a23,a14,a51,a42,a33,a24,a15, …建立了A 与 ?之间的一一对应，故 A 是可数集。a11 a12 a13 a14 … a21 a22 a23 a24 …a31 a32 a33 a34 …a41 a42 a43 a44 …a51 a52 a53 a54 … …康托尔对角线论证法Try it：至多可数个至多可数集的并是至多可数集。 5.3 集合的基数-可数集与不可数集例5-11：证明整数集?、???和有理数集?是可数集。(2) 构造双射 f： ???→?，满足 f (m, n) = (m+n)(m+n+1)/2+m证明：(1)构造双射 f： ?→ ?，满足f (n) = { 2n , n?0-2n-1 , n<0<0,0> <0,1> <0,2> <0,3> <0,4> …<1,0> <1,1> <1,2> <1,3> <1,4> …<2,0> <2,1> <2,2> <2,3> <2,4> …<3,0> <3,1> <3,2> <3,3> <3,4> …<4,0> <4,1> <4,2> <4,3> <4,4> …… (3)有理数集?可分为正有理数集? + 、负有理数集? - 和0，即? = ? +∪ ? -∪{0}因为任何有理数可表示成p/q（p、q为整数），写成<p, q>形式可知， ?+是???的一个无限子集，因此是可数的，进而?也是可数的。5.3 集合的基数-可数集与不可数集[可数集的基数] 可数集的基数记作?0，读作“阿列夫零”。|?| = ?0。 定理：实数集?是不可数的。5.3 集合的基数-可数集与不可数集证明：首先证明(0,1)区间内的实数是不可数的。否则，所有这些纯小数可以排列成如下形式：a1=0.a11a12a13a14a15…a2=0.a21a22a23a24a25…a3=0.a31a32a33a34a35…a4=0.a41a42a43a44a45… …现构造一个小数b = 0.b1b2b3b4…，使bi ≠ aii，即b与数列中第i个数的第i位是不同的。那么，上述数列中一定不包含b，这与所有数可列矛盾。因此，(0,1)区间内的实数是不可数的。因为区间(0,1)~ ?，因此，?是不可数的。 [实数集的基数] 实数集?的基数记作?，读作“阿列夫”。——还可以将此基数记作C，称其为“连续统的势”，因为具有基数C的集合被称为“连续统” 。5.3 集合的基数-可数集与不可数集无限集有限集不可数集可数集至多可数集集合的分类集合