1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第1 1章章 集合与计数集合与计数（上）（上）2022-8-52022-8-5 可数集与不可数集可数集与不可数集2 2 基本计数技术基本计数技术3 3 集合的基本知识集合的基本知识1 1 高级计数技术高级计数技术4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4集合的基本知识集合的基本知识&集合的基本知识
2、集合的基本知识J 数学危机与集合论数学危机与集合论4 集合的概念与表示集合的概念与表示4 集合的基本运算集合的基本运算4 集合的二进制表示集合的二进制表示2022-8-5计算机应用技术研究所计算机应用技术研究所6&第一次数学危机第一次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所7&第二次数学危机第二次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所8&第二次数学危机第二次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所9&第二次数学危机第二次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所10&第三次数学危机第三次数学危机20
3、22-8-5计算机应用技术研究所计算机应用技术研究所11&第三次数学危机第三次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所12&第三次数学危机第三次数学危机2022-8-5计算机应用技术研究所计算机应用技术研究所13&集合论的地位集合论的地位 集合论在解决数学危机数学危机中的作用，确定了其在整个数学体系中的基础地位。&集合的基本知识集合的基本知识4 数学危机与集合论数学危机与集合论J 集合的概念与表示集合的概念与表示4 集合的基本运算集合的基本运算4 集合的二进制表示集合的二进制表示2022-8-5计算机应用技术研究所计算机应用技术研究所15&集合论集合论2022-8-5计
4、算机应用技术研究所计算机应用技术研究所16&集合的概念集合的概念什么是集合：什么是集合：l 在朴素集合论中不能精确定义；在朴素集合论中不能精确定义；l 在公理集合论中通过公理来定义。在公理集合论中通过公理来定义。：由由指定范围指定范围内满足给定条件且内满足给定条件且能相互区分的能相互区分的所有对象所有对象的聚集。的聚集。中国中国所有真皮沙发所有真皮沙发的聚集的聚集指定指定范围范围所有所有对象对象集合中每个对象称为该集合的一集合中每个对象称为该集合的一个个或或2022-8-5计算机应用技术研究所计算机应用技术研究所17&集合与元素的关系集合与元素的关系2022-8-5计算机应用技术研究所计算机应
5、用技术研究所18 【例例】（罗素悖论）在一个很僻静的孤岛上，住着罗素悖论）在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些不自己理发的人理发。那么，谁给些并且只给那些不自己理发的人理发。那么，谁给这位理发师理发？这位理发师理发？【解解】设设C Cx|xx|x是不给自己理发的人是不给自己理发的人，b b是这位是这位理发师理发师 如如 b b C C，则，则 b b C C；如如 b b C C，则，则 b b C C。&集合与元素的关系集合与元素的关系2022-8-5计算机应用技术研究所计算机应用技术研究所19&元素
6、的基本性质元素的基本性质2022-8-5计算机应用技术研究所计算机应用技术研究所20&集合的记法集合的记法2022-8-5计算机应用技术研究所计算机应用技术研究所21&集合的表示法集合的表示法2022-8-5计算机应用技术研究所计算机应用技术研究所22&枚举法枚举法列出集合中全部元素或部分元素的方法叫列出集合中全部元素或部分元素的方法叫枚举法枚举法适用场景：适用场景：u 一个集合仅含有限个元素一个集合仅含有限个元素u 一个集合的元素之间有明显关系一个集合的元素之间有明显关系 2022-8-5计算机应用技术研究所计算机应用技术研究所23&枚举法的优劣枚举法的优劣u 是一种显式表示法是一种显式表示
7、法u 优点：优点：具有透明性具有透明性u 缺点：缺点：在表示具有某种特性的集合或集合中元素过多时在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法受到了一定的局限，而且，从计算机的角度看，显式法是一种是一种“静态静态”表示法，如果一下子将这么多的表示法，如果一下子将这么多的“数据数据”输入到计算机中去，那将占据大量的输入到计算机中去，那将占据大量的“内存内存”。2022-8-5计算机应用技术研究所计算机应用技术研究所24&描述法描述法 通过刻画集合中通过刻画集合中元素所具备的某种特性元素所具备的某种特性来表示来表示集合的方法称为集合的方法称为描述法描述法
8、。表示方法表示方法：A Ax|x|P(x)P(x)适用场景：适用场景：含有很多或无穷多个元素；集合的元含有很多或无穷多个元素；集合的元素之间有容易刻画的共同特征。素之间有容易刻画的共同特征。突出优点：突出优点：不要求列出集合中全部元素，只要给不要求列出集合中全部元素，只要给出集合中元素的特性。出集合中元素的特性。X X所具有的所具有的性质性质p p2022-8-5计算机应用技术研究所计算机应用技术研究所25&描述法描述法2022-8-5计算机应用技术研究所计算机应用技术研究所26归纳法归纳法注意：第一部分注意：第一部分和和第二部分第二部分指出一个集合指出一个集合至少包括至少包括的元素的元素，第
9、三部分第三部分指出一个集合指出一个集合至多要包含的元素至多要包含的元素&归纳法归纳法2022-8-5计算机应用技术研究所计算机应用技术研究所27&归纳法归纳法2022-8-5计算机应用技术研究所计算机应用技术研究所28【例例】设设 a a0 0 1 1，a ai+1 i+1 2a2ai i（i i 0 0）定义定义S Saa0 0，a a1 1，a a2 2，.aak k|k|k 0 0，试写出集合试写出集合S S中的所有元素。中的所有元素。&递归法递归法2022-8-5计算机应用技术研究所计算机应用技术研究所29&文氏图法文氏图法2022-8-5计算机应用技术研究所计算机应用技术研究所30设
10、设E=x|(x-1)(x-2)(x-3)=0,xRE=x|(x-1)(x-2)(x-3)=0,xR F=x|(x Z F=x|(x Z+)且且(x(x2 212)12)。试指出集合试指出集合E E和和F F中的元素。中的元素。&集合之间的关系集合之间的关系1 1 2022-8-5计算机应用技术研究所计算机应用技术研究所31&集合之间的关系集合之间的关系相等关系的性质相等关系的性质 自反性：自反性：对任何集合A，有A=A。传递性：传递性：对任何集合A、B、C，如果有A=B且 B=C，则A=C。对称性：对称性：对任何集合A、B，如果有A=B，则B=A。2022-8-5计算机应用技术研究所计算机应用
11、技术研究所32&集合之间的关系集合之间的关系由【例题1.9】可以看出，集合C中的每个元素都是集合A中的元素，此时A完全包含了C，可将C看成是A的一个部分。2022-8-5计算机应用技术研究所计算机应用技术研究所33【定义定义 设设A,BA,B是任意两个集合是任意两个集合，如果 B B的每个元素都是的每个元素都是A A的元素的元素，则称则称B B是是A A的的(Subset)，亦称A A包含包含B B，或称B B被被A A包含包含。记作A A B B 或B B A A。&集合之间的关系集合之间的关系上述包含定义可用数学语言描述为：上述包含定义可用数学语言描述为：B B A A对任意对任意x x，
12、如，如x x B B，则，则x x A A。2022-8-5计算机应用技术研究所计算机应用技术研究所34&集合之间的关系集合之间的关系2022-8-5计算机应用技术研究所计算机应用技术研究所35&集合之间的关系集合之间的关系 自反性自反性：对任何集合A，有A A。反对称性反对称性：对任何集合A、B，如果有A B且B A，则A=B。传递性传递性：对任何集合A、B、C，如果有A B且 B C，则A C。2022-8-5计算机应用技术研究所计算机应用技术研究所36【定义定义】设设A,BA,B是任意两个集合，如果是任意两个集合，如果B B A A并且并且ABAB则称则称B B是是A A的的(Prope
13、r Subset)，记作，记作B B A A。真子集的符号描述为：真子集的符号描述为：B B A A 对任意对任意x x，如，如x x B B，则，则x x A A，并且存在并且存在y y A A，但是，但是y y B B&集合之间的关系集合之间的关系3 真包含关系真包含关系BA2022-8-5计算机应用技术研究所计算机应用技术研究所37【例例】试判断下列集合之间的包含关系。试判断下列集合之间的包含关系。（1 1）a,ba,b和和a,b,c,da,b,c,d；（2 2）a,b,c,da,b,c,d和和a,b,c,da,b,c,d。&例例 题题【例例】设设A=a是一个集合，是一个集合，B=a,a
14、，试问：试问：AB和和A B同时成立吗？同时成立吗？2022-8-5计算机应用技术研究所计算机应用技术研究所38&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所39空集可以符号化为：空集可以符号化为：=x|xx=x|xx空集是客观存在的。空集是客观存在的。【例例】设设A=x|(xR)A=x|(xR)且且(x(x2 20)0)，试列，试列举集合举集合A A中的所有元素。中的所有元素。&空集的概念与性质空集的概念与性质不含任何元素的集合叫做不含任何元素的集合叫做空集空集(Empty(Empty Set)Set)，记作，记作。2022-8-5计算机应用技术研究所计算机应用技术研究
15、所40 （1 1）空集是一切集合的子集；）空集是一切集合的子集；（2 2）空集是绝对唯一的。）空集是绝对唯一的。【例例】指出下列结论中哪些是错误的指出下列结论中哪些是错误的 （1 1）;（2 2）;（3 3）;（4 4）&空集的概念与性质空集的概念与性质2022-8-5计算机应用技术研究所计算机应用技术研究所41在一个在一个相对固定的范围内相对固定的范围内，包含此范围，包含此范围内所有元素的集合，称为内所有元素的集合，称为或或(Universal(Universal Set)Set)，用，用U U或或E E表示。表示。U&全集的概念与性质全集的概念与性质 全集是相对唯一的全集是相对唯一的.20
16、22-8-5计算机应用技术研究所计算机应用技术研究所42 如果如果|A|A|是有限的，则称集合是有限的，则称集合A A为为有限集有限集，如果如果|A|A|是无限的，则称集合是无限的，则称集合A A为为无限集无限集。&有限集和无限集有限集和无限集集合集合A A中元素的数目称为集合中元素的数目称为集合A A的的（base number)base number)，记为，记为|A|A|。2022-8-5计算机应用技术研究所计算机应用技术研究所43&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所44【例例】设设A=a,b,cA=a,b,c，求出其全部，求出其全部m m元子集，元子集，
17、并证明并证明n n元集合元集合的子集总数为的子集总数为2 2n n2 2|A|A|&m元子集元子集如果一个集合如果一个集合A A含有含有n n个元素，则称集个元素，则称集合合A A为为，称，称A A的含有的含有m m个个(0mn)(0mn)元素的子元素的子集为集为A A的的。分析：对于分析：对于n n元集，它的元集，它的m m（0 0 m m n n）元子集有）元子集有C(n,m)C(n,m)个，个，所以不同的子集总数有：所以不同的子集总数有：2022-8-5计算机应用技术研究所计算机应用技术研究所45&幂幂集的概念与性质集的概念与性质设设A A为任一集合，称为任一集合，称A A的所有不同子集
18、构成的所有不同子集构成的集合为的集合为A A的的(power set)(power set)，记为，记为P(A)P(A)或或2 2A A。上述幂集定义可用数学语言描述为：上述幂集定义可用数学语言描述为：通常将以集合为元素的集合称为通常将以集合为元素的集合称为集族集族(family of set)(family of set)。显然，幂集是集族。显然，幂集是集族。2022-8-5计算机应用技术研究所计算机应用技术研究所46&幂幂 集集【例例】集合集合00，1 1，22的幂集合是什么？的幂集合是什么？【解解】幂集合幂集合P(0,1,2)P(0,1,2)是是00，1 1，22所所有子集的集合。因此有
19、：有子集的集合。因此有：P(0,1,2)=,0,1,2,0,1,0,P(0,1,2)=,0,1,2,0,1,0,2,1,2,0,1,22,1,2,0,1,22022-8-5计算机应用技术研究所计算机应用技术研究所47&例例 题题【例例】空集的幂集合是什么？集合空集的幂集合是什么？集合的幂集的幂集合是什么？合是什么？【解解】空集只有一个子集，这就是它自己。因空集只有一个子集，这就是它自己。因此有：此有：P()=P()=集合集合有两个子集，即有两个子集，即和集合和集合自自身。故有：身。故有：P()=,P()=,&集合的基本知识集合的基本知识4 数学危机与集合论数学危机与集合论4 集合的概念与表示集
20、合的概念与表示J 集合的基本运算集合的基本运算4 集合的二进制表示集合的二进制表示2022-8-5计算机应用技术研究所计算机应用技术研究所49&交运算交运算设设A,BA,B为任意两个集合，为任意两个集合，=且且x x 交运算的文氏图表示为：交运算的文氏图表示为：U2022-8-5计算机应用技术研究所计算机应用技术研究所50&交运算交运算交运算的性质交运算的性质幂等律幂等律 对任何集合对任何集合A A，有，有AA=AAA=A。交换律交换律 对任何集合对任何集合A A、B B，有，有AB=BAAB=BA结合律结合律 对任何集合对任何集合A A、B B、C C，有，有 (AB)C=A(BC)(AB)
21、C=A(BC)。同一律同一律 对任何集合对任何集合A A，有，有AE=AAE=A。零零 律律 对任何集合对任何集合A A，有，有A=A=。A A B B AB=AAB=A2022-8-5计算机应用技术研究所计算机应用技术研究所51&并运算并运算设设A,BA,B为任意两个集合，为任意两个集合，A AB BA AB BA AB B=x xx xA A或xB BU并运算的文氏图表示为：并运算的文氏图表示为：2022-8-5计算机应用技术研究所计算机应用技术研究所52&并运算并运算并运算的性质并运算的性质幂等律幂等律 对任何集合对任何集合A A，有，有AA=AAA=A交换律交换律 对任何集合对任何集合
22、A A、B B，有，有AB=BAAB=BA结合律结合律 对任何集合对任何集合A A、B B、C C，有，有 (AB)C=A(BC)(AB)C=A(BC)同一律同一律 对任何集合对任何集合A A，有，有A=AA=A零零 律律 对任何集合对任何集合A A，有，有AU=UAU=U2022-8-5计算机应用技术研究所计算机应用技术研究所53&并运算并运算并运算的性质（续）并运算的性质（续）2022-8-5计算机应用技术研究所计算机应用技术研究所54&差运算运算差运算运算设设A,BA,B为任意两个集合，为任意两个集合，A-B=xxA且x BU差运算为亦称为差运算为亦称为，其文氏图为：其文氏图为：2022
23、-8-5计算机应用技术研究所计算机应用技术研究所55 U&补运算补运算设设A A为任一集合，为任一集合，=U-A=xxU且xAA AA AA A补运算的文氏图表示为：补运算的文氏图表示为：2022-8-5计算机应用技术研究所计算机应用技术研究所56&补运算补运算2022-8-5计算机应用技术研究所计算机应用技术研究所57&环和运算环和运算设设A,BA,B为任意两个集合，为任意两个集合，A A B B称为称为A A与与B B的的或或A B=(A-B)(B-A)环和运算的文氏图表示为：环和运算的文氏图表示为：U2022-8-5计算机应用技术研究所计算机应用技术研究所58&环和运算环和运算2022-
24、8-5计算机应用技术研究所计算机应用技术研究所59&环和运算环和运算环和运算的性质环和运算的性质 A A B=BB=B A A (A(A B)B)C=AC=A(B(B C)C)A A=A=A A A A A=A A =U =U A A(B(B C)=(AB)C)=(AB)(AC)(AC)A A2022-8-5计算机应用技术研究所计算机应用技术研究所60&环和运算环和运算2022-8-5计算机应用技术研究所计算机应用技术研究所61&环和运算环和运算【证明(续)】2022-8-5计算机应用技术研究所计算机应用技术研究所62&环积运算环积运算环和运算的文氏图表示为：环和运算的文氏图表示为：2022-
25、8-5计算机应用技术研究所计算机应用技术研究所63&环积运算环积运算2022-8-5计算机应用技术研究所计算机应用技术研究所64&集合运算的基本性质集合运算的基本性质2022-8-5计算机应用技术研究所计算机应用技术研究所65A=AA=AAA&集合运算的基本性质集合运算的基本性质A A B B=A A B BA A B B=A A B B2022-8-5计算机应用技术研究所计算机应用技术研究所66DeMorganDeMorgan律：律：AAB=AB=AB BAAB=AB=AB B (1)A(1)ABABAB B(2)A(2)ABABAB B&证明示例证明示例2022-8-5计算机应用技术研究所
26、计算机应用技术研究所67证明（1）式xAxAB BAABABAB B xAxAB BxA且xA且xBxB x xA AB BxA且xA且xBxB xAxAB BxA且xA且xBxBxA且xA且xBxB x xA AB BxAxAB BAABABAB BAAB=AB=AB B2022-8-5计算机应用技术研究所计算机应用技术研究所68证明（2）式A A B B=A A B BAAB=AB=AB=AB=AB BA AB B AAB=AB=AB B AAB=AB=AB B&集合的基本知识集合的基本知识4 数学危机与集合论数学危机与集合论4 集合的概念与表示集合的概念与表示4 集合的基本运算集合的基本
27、运算J 集合的二进制表示集合的二进制表示2022-8-5计算机应用技术研究所计算机应用技术研究所70&集合的二进制表示集合的二进制表示2022-8-5计算机应用技术研究所计算机应用技术研究所71&二进制编码方法二进制编码方法2022-8-5计算机应用技术研究所计算机应用技术研究所72&二进制编码方法二进制编码方法2022-8-5计算机应用技术研究所计算机应用技术研究所73&二进制编码方法二进制编码方法2022-8-5计算机应用技术研究所计算机应用技术研究所74&二进制编码方法二进制编码方法2022-8-5计算机应用技术研究所计算机应用技术研究所75&二进制编码方法二进制编码方法2022-8-5
28、计算机应用技术研究所计算机应用技术研究所76&二进制编码方法二进制编码方法2022-8-5计算机应用技术研究所计算机应用技术研究所772022-8-52022-8-5 集合的基本知识集合的基本知识1 1 基本计数技术基本计数技术3 3 可数集与不可数集可数集与不可数集2 2 高级计数技术高级计数技术4 4&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所79可数集与不可数集可数集与不可数集&可数集与不可数集可数集与不可数集J 无限集的度量问题无限集的度量问题4 自然数集的定义自然数集的定义4 无限集的基数比较无限集的基数比较2022-8-5计算机应用技术研究所计
29、算机应用技术研究所81问题一、下列哪个集合中的元素比较多？问题一、下列哪个集合中的元素比较多？1.1,2,3,1.1,2,3,2.1 2.12 2,2,22 2,3,32 2,&无限集的度量问题无限集的度量问题问题二、伽利略悖论问题二、伽利略悖论2022-8-5计算机应用技术研究所计算机应用技术研究所82质质 变变 无限集合无法用确切的个数来描述无限集合无法用确切的个数来描述 无限集的度量问题该怎么解决？无限集的度量问题该怎么解决？度量无限集合的尺子是什么？度量无限集合的尺子是什么？有限集有限集无限集无限集量量 变变&无限集的度量问题无限集的度量问题2022-8-5计算机应用技术研究所计算机应
30、用技术研究所833.3 集合定义的自然数和归纳法证明集合定义的自然数和归纳法证明&等势的概念等势的概念设设A，B是两个集合，若在是两个集合，若在A，B之间之间存在存在1-1对应的关系：对应的关系：则称集合则称集合A与与B等势等势(equipotent)，记为：，记为：A B。【注意注意】若若A AB B，则，则 A A B B。若若A A B B，则，则 A AB B （）（）2022-8-5计算机应用技术研究所计算机应用技术研究所84&等势的概念等势的概念2022-8-5计算机应用技术研究所计算机应用技术研究所85&等势的概念等势的概念2022-8-5计算机应用技术研究所计算机应用技术研究所
31、86&等势的基本性质等势的基本性质2022-8-5计算机应用技术研究所计算机应用技术研究所87&等势的基本性质等势的基本性质2022-8-5计算机应用技术研究所计算机应用技术研究所88&等势的特性等势的特性&可数集与不可数集可数集与不可数集4 无限集的度量问题无限集的度量问题J 自然数集的定义自然数集的定义4 无限集的基数比较无限集的基数比较2022-8-5计算机应用技术研究所计算机应用技术研究所90&佩亚诺公理佩亚诺公理2022-8-5计算机应用技术研究所计算机应用技术研究所91&关键问题关键问题1.首符号(0)的定义；2.后继的定义；2022-8-5计算机应用技术研究所计算机应用技术研究所
32、92&基本思路基本思路2022-8-5计算机应用技术研究所计算机应用技术研究所933.3 集合定义的自然数和归纳法证明集合定义的自然数和归纳法证明 （1 1）称空集）称空集 为自然数，记为为自然数，记为0 0。（2 2）称）称A A A A AA为集合为集合A A的直接后继。的直接后继。a,ba,b,a,b =,=,&集合的后继集合的后继2022-8-5计算机应用技术研究所计算机应用技术研究所94归纳定义自然数集归纳定义自然数集N N：（l l）基础条款：）基础条款：N N 。（2 2）归纳条款：若）归纳条款：若x x N N ，则，则x x=x x x x N N3.3 集合定义的自然数和归
33、纳法证明集合定义的自然数和归纳法证明&自然数的归纳定义自然数的归纳定义2022-8-5计算机应用技术研究所计算机应用技术研究所950 0，1 1 00，2 2 ,0,10,1 .n n0,1,2,3,.n-10,1,2,3,.n-1 .故有：故有：N N0,1,2,3,.,n,.0,1,2,3,.,n,.&自然数的归纳定义自然数的归纳定义2022-8-5计算机应用技术研究所计算机应用技术研究所96&自然数集的合法性自然数集的合法性2022-8-5计算机应用技术研究所计算机应用技术研究所97&自然数集的合法性自然数集的合法性【证明(续)】2022-8-5计算机应用技术研究所计算机应用技术研究所9
34、8&自然数的基本性质自然数的基本性质（1）0是自然数集的最小数。是自然数集的最小数。（2）自然数集的所有非空子集具有最小数（）自然数集的所有非空子集具有最小数（最小数最小数原理原理），从而正整数集的所有非空子集均有最小数。），从而正整数集的所有非空子集均有最小数。（3）自然数集合的所有非空有限子集均有最大数，）自然数集合的所有非空有限子集均有最大数，从而正整数集合的所有非空有限子集均有最大数。从而正整数集合的所有非空有限子集均有最大数。2022-8-5计算机应用技术研究所计算机应用技术研究所99&自然数的归纳证明自然数的归纳证明【数学归纳法第一原理】【数学归纳法第一原理】假设P(n)是一个关于
35、自然数n的命题，若有：（1）基础步骤基础步骤：P(0)为真；（2）归纳步骤归纳步骤：对于任意正整数k，如果P(k)为真，则P(k+1)为真。则：P(n)对一切自然数对一切自然数n均为真。均为真。2022-8-5计算机应用技术研究所计算机应用技术研究所100&自然数的归纳证明自然数的归纳证明2022-8-5计算机应用技术研究所计算机应用技术研究所101&自然数的归纳证明自然数的归纳证明2022-8-5计算机应用技术研究所计算机应用技术研究所102&自然数的归纳证明自然数的归纳证明2022-8-5计算机应用技术研究所计算机应用技术研究所103&自然数的归纳证明自然数的归纳证明2022-8-5计算机
36、应用技术研究所计算机应用技术研究所104&自然数的归纳证明自然数的归纳证明&无限集及其性质无限集及其性质4 无限集的基本概念无限集的基本概念4 自然数的集合定义自然数的集合定义J 可数集与不可数集可数集与不可数集2022-8-5计算机应用技术研究所计算机应用技术研究所106凡是与凡是与自然数集合自然数集合等势的集合，统称为等势的集合，统称为可数集合可数集合(可列集可列集)(Countable Set)(Countable Set)。可数集。可数集合记为：合记为：0 0(读作阿列夫零读作阿列夫零)。下列集合都是可数集合：下列集合都是可数集合：1)O1)O+x|xx|x N N，x x是正奇数是正
37、奇数;2)P 2)Px|xx|x N N，x x是素数是素数;3)3)有理数集合有理数集合Q.Q.&可数集合可数集合2022-8-5计算机应用技术研究所计算机应用技术研究所107&O O+是可数集合是可数集合2022-8-5计算机应用技术研究所计算机应用技术研究所108&P P是可数集合是可数集合在在P P与与N N之间建立如下之间建立如下1-11-1对应关系对应关系 N N .P P 11.11.所以，所以，P P是可数集合。是可数集合。2022-8-5计算机应用技术研究所计算机应用技术研究所109&Q Q是可数集合是可数集合2022-8-5计算机应用技术研究所计算机应用技术研究所110&不
38、可数集合不可数集合开区间开区间(0,1)(0,1)称为不可数集合，其称为不可数集合，其基数基数设为设为(读作阿列夫读作阿列夫)；凡是与开区间；凡是与开区间(0,1)(0,1)等等势的集合都是不可数集合。势的集合都是不可数集合。(1)(1)闭区间闭区间0,1 0,1 是不可数集合；是不可数集合；(2)(2)实数集合实数集合R R是不可数集合。是不可数集合。2022-8-5计算机应用技术研究所计算机应用技术研究所111在闭区间在闭区间0,10,1和开区间和开区间(0,1)(0,1)之间建立如之间建立如下对应关系：下对应关系：n nn n+2 20 0 1 1/4 4,1 1 1 1/2 2,R R:1 11 1n n=1 1,2 2,3 3,L L,2 22 2n n n n其其 他他 n n(0 0,1 1).&0,10,1是不可数集合是不可数集合2022-8-5计算机应用技术研究所计算机应用技术研究所112在实数集在实数集R R和开区间和开区间(0,1)(0,1)之间建立如之间建立如下对应关系：下对应关系：&R R是不可数集合是不可数集合2n-12n-1nntantan2 22022-8-5计算机应用技术研究所计算机应用技术研究所113&无限集的规模无限集的规模2022-8-5计算机应用技术研究所计算机应用技术研究所114
