离散数学-第六章集合基数

离散数学

第六章

集合的基数2023/1/826.1

可数集和不可数集将N的前n个自然数集合记为定义6.1.4

设A和B是任意集合。若存在从A到B的双射，则称A与B是等势的，记为；若A与B不等势，则记为。例6.1.2

证作

2023/1/836.1

可数集和不可数集定义6.1.5若有,

使

则称A是有限集,且称其基数为n,记为；若A不是有限集,则称A为无限集例6.14自然数集N是无限集证用反证法若N是有限的,则有,使得存在双射取则,但不存在使这与f是双射矛盾2023/1/846.1

可数集和不可数集定理6.1.1

任何有限集都不能与它的真子集等势例6.1.4

设且令作则f是双射,因此而

2023/1/856.1

可数集和不可数集定理6.1.2设A是有限集，B是无限集，C是任意集合

(1)若则C是有限集

(2)

若则C是无限集定义6.1.6设A是任意集合。若则称A是可数无限集,并称A的基数为(读作阿列夫零),记为。有限集和可数无限集称为可数集；非可数集称为不可数集。例6.1.7(1)N是可数无限集

2023/1/866.1

可数集和不可数集(2)I是可数无限集证作

(3)I+是可数无限集

2023/1/876.1

可数集和不可数集若A是可数集,

则存在双射或于是A中的元素可无重复地排列成或反之,

若A中元素可无重复地排列成或则存在双射或2023/1/886.1

可数集和不可数集可以证明“无重复”这一条件是可以省略的。即要证明一个集合是可数的,

只要证明该集合中的所有元素能够排成一个序列即可。例6.1.8

是可数无限集证的元素可以按下列方式排列

2023/1/896.1

可数集和不可数集例6.1.9

是可数无限集证的元素可以按下列方式排列2023/1/8106.1

可数集和不可数集定理6.1.3

可数集的任何子集都是可数集例6.1.11

都是可数集证由以及N是可数集便知。定理6.1.4可数个可数集的并集是可数集

证下面分两种情况讨论

(1)

有限个可数集的并集设是可数集,

且

(若是有限集,则重复的最后一个元素)2023/1/8116.1

可数集和不可数集

中所有元素可如下排列

(2)可数无限个可数集的并集设是可数集,

且2023/1/8126.1

可数集和不可数集

中所有元素可如下排列2023/1/8136.1

可数集和不可数集例6.1.11是可数集证作显然f是双射，于是由知故是可数集又由定理6.1.4知是可数集定理6.1.5

若A和B是可数集，则是可数集定理6.1.6[0,1]不是可数无限集证设将f的值顺序排列为十进制小数为2023/1/8146.1

可数集和不可数集

其中2023/1/8156.1

可数集和不可数集

则但这就说明了f不是满射，故不是双射由f的任意性知N与[0,1]之间不存在双射，故[0,1]不是可数无限集。定义6.1.7设A是任意集合。若则称A的基数为(读作阿列夫),并称A是具有连续统势的集合，记为|A|=。2023/1/8166.1

可数集和不可数集例6.1.14下列集合的基数都为

(1)

(2)

(3)R

证

(1)

作双射

(2)

设集合

作双射2023/1/8176.1

可数集和不可数集(3)

作双射则为从[0,1]到R的双射2023/1/818习题习题6.1

2(2)(5)(7)3(4)2023/1/8196.2

基数的比较定义6.2.1

设A和B是任意集合。

(1)

若存在从A到B的双射,则称A和B有相同的基数,记为|A|=|B|；否则说A的基数不等于B的基数,记为

(2)

若存在从A到B的单射,则称A的基数小于或等于B的基数,记为

(3)

若且则称A的基数小于B的基数,记为2023/1/8206.2

基数的比较例6.2.1(1)(2)(3)定理6.2.1设A和B是任意集合，则|A|=|B|，和恰有一个成立。定理6.2.2

设A和B是任意集合，若且则|A|=|B|。

2023/1/8216.2

基数的比较例6.2.2

证明证(1)

证作：

f1是单射,

所以作：

f2是单射，所以因此

2023/1/8226.2

基数的比较(2)

证作

g1是单射，故作

g2是单射，故因此有2023/1/8236.2

基数的比较定理6.2.3下列3个条件是等价的：

(1)A是无限集；

(2)A有可数无限子集；

(3)A有与其自身等势的真子集。定理6.2.4(1)

若A是有限集，则

(2)

若A是无限集，则2023/1/8246.1

可数集和不可数集1设A和B是无限集,C是有限集.

下列集合是否一定是无限集？

(1)(2)(3)(4)

解(1)不一定.反例

(2)不一定.反例

(3)一定是.无限集

(4)一定是.

否则有限,不可2023/1/8256.1

可数集和不可数集4设A是可数无限集，B是有限集，求下列集合的基数

(1)(2)

解(1)(2)基数为5证明：无理数集是不可数集证用反证法若无理数集S是可数集则实数集是可数集，不可2023/1/826作业习题4.4

4设是上的自反和传递的二元关系，且满足则是A上的等价关系。证由知故是自反的。

2023/1/827作业故是对称的。

若故是传递的。因此是A上的等价关系。

2023/1/828作业习题4.5

1(3)

分别求出下列集合关于的极大(小)元、最大(小)

元、上界、下界、最小上界和最大下界

(a)A(b){c,d}(c){b,e}(d){b,d,e}abcdfe2023/1/829作业习题4.55设是全序集,

定义当且仅当判断R1是否A上的偏序、拟序、线序或良序关系解是偏序关系证(1)自反性由知

(2)反对称性2023/1/830作业

(3)

传递性由于R1不是反自反的，故不是拟序关系由于A中至少有两个元素a,b。不妨设则或都不成立所以R1不是线序关系

2023/1/831作业习题5.1

3

下列函数哪些是单射、满射或双射?(2)(5)

解(2)单射

(5)满射

2023/1/832作业习题5.110设A和B是非空有限集,且|A|=m,|B|=n(1)从A到B的不同单射共有多少个?(2)从A到B的不同满射共有多少个?(3)从A到B的不同双射共有多少个?

解(1)

不同单射共有个

(3)

不同双射共有个2023/1/833作业

(2)

设满射函数的个数

2023/1/834作业习题5.22设存在正整数n使得.证明：f是双射函数。证当n=1时，是双射函数。当时，由知是双射函数。

2023/1/835作业4设证明：若f是单射(满射,双射)，则也是单射(满射,双射)。证对n用归纳法当n=1时，结论显然成立。设当n=k时，结论成立。当n=k+1时，由便知是单射(满射,双射)。

2023/1/836作业5设证明：当且仅当h是满射。证必要性若