离散数学 实数集合与集合基数20页PPT

02
有限集合的基数
定义
基数
有限集合中元素的个数称为该集合的基数。
01
符号表示
用大写字母表示集合，用小写字母表示 元素，例如集合A的基数表示为|A|。
02
03
空集的基数
空集的基数为0。
性质
01
非空有限集合的基数大于0。
02
单元素集合的基数为1。
03
有限集合的子集的基数小于等于原集合的 基数。
04
05
应用与实例
计数问题
组合问题
组合问题涉及到从n个不同元 素中选取k个元素的不同方式 的数量，基数为C(n, k) = n!
/ (k!(n-k)!)。
排列问题
排列问题涉及到从n个不同元 素中选取k个元素并按照一定
顺序排列的不同方式的数量 ，基数为P(n, k) = n! / ((n-
k)!)。
鸽巢原理
一一对应
两个集合之间存在一一对应的关系，意味着每个集合中的元素都可以与另一个集合中的 元素一一对应。
性质
可数集合的子集也是可数的
如果一个可数集合存在一一对应的自然数集合，那么该可 数集合的任何子集也与自然数集合存在一一对应的关系。
有限集合的并集是可数的
如果有限个可数集合的并集存在，那么这个并集也是可数 的。
鸽巢原理是计数原理的一种应 用，它表明如果n个物体要放 入m个容器中，且n > m，则 至少有一个容器包含两个或以 上的物体。
概率论中的基数问题
概率空间
概率空间是概率论的基本概念之 一，它由样本空间和概率函数组 成。样本空间的基数表示所有可 能结果的个数。
概率分布
概率分布是描述随机变量取值概 率的函数，其基数表示随机变量 取值的个数。

6.2.1 可数集
定理6.2.5 可数个可数集的并集仍然是一可数集。
在上面元素的排列中，由左上端开始，其每一斜线上的每一元素
的两足码之和都相同，依次为2，3，4，…，各斜线上元素的个
数依次为1，2，3，4，…，故A的排列为： a11，a21，a12，a31，a22，a13，… 故S是可数的，定理得证。
称 X 绝对劣势于 Y ，记作 X≺· Y ，同样，我们也称 X 的基数小于 Y 的
基数，记作cardX≺· cardY。
6.3 基数的比较
定理 6.3.1 X≈Z。 设 X 、 Y 为两个集合，则 X≼· Y 当且仅当存在 ZY ，使得
证明 先证必要性。因为X≼· Y，所以必存在函数f：X→Y。现令fˊ： X→ranf ，则显然 fˊ是双射函数，所以 X≈ranf 。因此可取 Z = ranf Y。 再证充分性。设ZY，且X≈Z，则必存在双射函数g：X→Z。现构造 一函数gˊ：X→Y，其中对于X中任意元素x，都有gˊ（x）=g （x），则显然gˊ是单射函数，所以X≼· Y。 推论 设X、Y为两个集合， ⑴ 若XY，则X≼· Y；
均为可数集。
定理6.2.1
集合X为可数集的充分必要条件是可以排列成
X={x1，x2，…，xn，…}
的形式。
6.2 可数集和不可数集
6.2.1 可数集
定理6.2.2 任一无限集必含有可数子集。
证明 设X为无限集合，现从X中任意取出一个元素，记为x1，因为 X是无限的，显然X－{x1}还是无限集合，然后从X－{x1}中再取出 一元素，记为x2，而X－{x1，x2}还是无限的，所以又可再取一元 素x3，如此重复这一过程，就可得到X的可数子集。 定理6.2.3 任意无限集，一定与它的某一真子集等势。 证明 设X为无限集合，根据定理6.4，X必含有可数子集A＝{a1， a2， …， an， …}，设B=X－A，定义函数f：X→X－{a1}，使得f （an）=an+1 （n=1， 2，…），而对于任意元素b∈B，有f（b） =b，显然f是双射函数，定理得证

17
例题
计算以下幂集：
，{}；{，{}}
解：
P()={} P({})={，{}} P({，{}})= {, {}，{{}},{，{}}}
18
3.3 集合的运算
集合的运算 并，交，补（绝对补），差（相对补－），和对称差等。
19
集合的并运算
• 定义3.3.1 设A，B为集合，由A和B的所有元素组成的集 合称为A与B的并集， 可表示为： AB={x|xAxB} 其文氏图：
其文氏图如下：
~E = ， ~ = E， ~（~A）= A A ~A = ， A ~A = E
27
德.摩根定律
• 定理3.3.5 设A，B为任意二个集合，则有： • （1） （AB）= A B • （2） （A B）= A B • 证明 设E为全集，显然有AE=A，AE=E成立。 • （1） （AB）= {x | xEx（AB）}= {x |
据的增加、删除、修改、排序，以及数据间关系的描述。
集合论在计算机语言、数据结构、编译原理、数据库与
知识库、形式语言及人工智能等许多领域得到广泛的应
用。
2
3.1 集合及其表示
• 集合是由一些对象聚集在一起构成的。 例如，全体整数 全体中国人 26个英文字母
• 构成集合的对象可以是各种类型的事物。 • 定义3.1.1 集合中的对象叫集合的元素，或成员。
• 集合中的元素可以具有共同性质，也可以表面上看起来不相干。
• 如{2，Tom，计算机，广州}
• 在集合论中，规定元素之间是彼此相异的，并且是没有次序关 系的。
例如，{3,4,5},{3,4,4,5,5},{5,3,4}都是同一个集合。
• 例如，A={3,4,5},

满射。
双射
03
如果一个映射既是单射又是满射，则称该映射为双射。
函数的基本性质
确定性
对于任意一个输入，函数只能有一个输出。
互异性
函数的输出与输入一一对应，没有重复的输 出值。
可计算性
对于任意给定的输入，函数都能计算出唯一 的输出值。
域和陪域
函数的输入值的集合称为函数的定义域，函 数输出的集合称为函数的陪域。
04
集合的运算性质
并集运算性质
并集的交换律
对于任意集合A和B，有A∪B=B∪A。
并集的幂等律
对于任意集合A，有A∪A=A。
并集的结合律
对于任意集合A、B和C，有 A∪(B∪C)=(A∪B)∪C。
并集的零律
对于任意集合A和空集∅，有A∪∅=ቤተ መጻሕፍቲ ባይዱ。
交集运算性质
交集的交换律
对于任意集合A和B，有A∩B=B∩A。
在数学中的应用
集合论
集合论是数学的基础，它为数学提供了基本的逻辑和概念 框架。通过集合，可以定义和讨论概念、关系和性质等。
概率论
在概率论中，集合用来表示事件，事件发生的概率可以定 义为该事件所对应的集合的元素个数与样本空间所对应的 集合的元素个数之比。
拓扑学
拓扑学是研究几何形状在大范围内变化的学科。在拓扑学 中，集合用来表示空间中的点、线、面等元素，以及它们 之间的关系。
THANKS FOR WATCHING
感谢您的观看
03
集合的分类
有穷集和无穷集
有穷集
集合中元素的数量是有限的，可以明 确地列举出集合中的所有元素。例如 ，集合{1, 2, 3}是一个有穷集。
无穷集
集合中元素的数量是无限的，无法列 举出集合中的所有元素。例如，自然 数集N={1, 2, 3,...}是一个无穷集。