离散数学课件 第3章 集合论

离散数学第三章集合论1/79集合论的创立与康托尔的遭遇

19世纪末期，数学界出现了一件引人注目的事情。一位名叫康托尔（G.Cantor，1845－1918）的德国数学家提出一种令人费解的古怪理论----集合论。它的内容是如此与常识格格不入，以致于一出世就引起了一场轩然大波。2026/9/152/79

自从17世纪牛顿和莱布尼茨）创立微积分理论体系之后，在近一二百年时间里，微积分理论一直缺乏一个严格的逻辑基础。它的一些基本概念的表述，还有某些混乱和自相矛盾之处。从19世纪开始，柯西、魏尔斯特拉斯等人进行了微积分理论严格化的工作。他们建立了极限理论，并把极限理论的基础归结为实数理论。那么，实数理论的基础又该是什么呢？康托尔试图用集合论来作为实数理论，以至整个微积分理论体系的基础。2026/9/153/79

出于这一目的，康托尔用集合的观点重新考察各种数量关系，特别是无穷数量关系。他发现，无穷集合有着有穷数量关系所不具备的性质。比如，在无穷集合领域，所有整数和所有偶数之间是一一对应的，所有有理数和所有整数之间是一一对应的，平面上所有的点和线段上所有的点是一一对应的，……概言之，在无穷的世界里，整体的所有元素和部分的所有元素之间可以是一一对应的。另外，无穷集合并不都是相等的，比如所有实数和所有有理数之间就不是一一对应的。因而，无穷集合是有大小的。集合论用“基数”这个概念来表示无穷集合间的区别。

那么，有没有一个最大的集合呢？康托尔通过研究，否定了这个想法。因为每个已知集合的所有子集所构成集合，其基数都大于已知集合的基数。既然没有最大的基数，当然也没有最大的集合。无穷世界里的这些性质，初看起来，真是令人头晕目眩。2026/9/154/79

康托尔的研究成果发表之后，马上遭致当时一些赫赫有名的数学家的激烈攻击。德国数学家克隆尼克是这些人中言辞最激烈、攻击时间最长的一个。

克隆尼克比康托尔年长22岁。他主张，除非一种数学对象能够用有限步骤从自然数中构造出来，否则不能认为它在数学上是存在的。他有一句“名言”：“上帝创造了自然数，其余的一切才是人做的工作”。因此，他否认无理数的存在，也否认极限理论的意义。虽然康托尔是他的学生，但由于集合论的内容同他的主张大相径庭，所以克隆尼克简直到了不能容忍的程度。他认为，康托尔关于超限数的研究，是一种非常危险的数学疯病。克隆尼克的影响还使康托尔的学术论文一再延误发表日期。2026/9/155/79

除了克隆尼克之外，还有一些著名数学家也对集合论发表了反对意见。

法国数学家彭加勒说：“我个人，而且还不只我一人，认为重要之点在于，切勿引进一些不能用有限个文字去完全定义好的东西”。他把集合论当作一个有趣的“病理学的情形”来谈，并且预测说：“后一代将把（Cantor）集合论当作一种疾病，而人们已经从中恢复过来了”。

德国数学家魏尔认为，康托尔关于基数的等级观点是雾上之雾。

菲利克斯．克莱因也不赞成集合论的思想。

数学家H．A．施瓦兹原来是康托尔的好友，但他由于反对集合论而同康托尔断交。2026/9/156/79

尽管有希尔伯特等著名数学家赞同他的集合论，尽管他的集合论事实上已取得巨大的成功，仍未能使康托尔感到欣慰和满足。

从1884年春天起，即在他40岁的时候，他患了严重的忧郁症，极度沮丧，神态不安。不过，在精神病发作的间歇阶段，康托尔仍然顽强地坚持集合论的研究。而且当每次从精神病发作中恢复过来的时候，他都感到自己的脑子变得格外清晰。他在集合论方面许多非常出色的成果，都是在精神病发作的间歇时期获得的。然而，长期的精神折磨所造成的危害毕竟是不容忽视的。由于健康状况逐渐恶化，1918年，他在哈勒大学附属精神病院去世。

2026/9/157/79公理化集合论的建立

到二十世纪初集合论已得到数学家们的赞同。数学家们为一切数学成果都可建立在集合论基础上的前景而陶醉了。他们乐观地认为从算术公理系统出发，借助集合论的概念，便可以建造起整个数学的大厦。在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“……数学已被算术化了。今天，我们可以说绝对的严格已经达到了。”

然而这种自得的情绪并没能持续多久。不久，集合论有漏洞的消息迅速传遍了数学界。这就是1902年罗素得出的罗素悖论。2026/9/158/79

罗素构造了一个所有不属于自身（即不包含自身作为元素）的集合R。现在问R是否属于R？

如果R属于R，则R满足R的定义，因此R不应属于自身，即R不属于R；另一方面，如果R不属于R，则R不满足R的定义，因此R应属于自身，即R属于R。这样，不论何种情况都存在着矛盾。

这一仅涉及集合与属于两个最基本概念的悖论如此简单明了以致根本留不下为集合论漏洞辩解的余地。绝对严密的数学陷入了自相矛盾之中。这就是数学史上的第三次数学危机。2026/9/159/79

1908年，策梅罗提出公理化集合论，后经改进形成无矛盾的集合论公理系统，简称ZF公理系统。原本直观的集合概念被建立在严格的公理基础之上，从而避免了悖论的出现。这就是集合论发展的第二个阶段：公理化集合论。与此相对应，在1908年以前由康托尔创立的集合论被称为朴素集合论。公理化集合论是对朴素集合论的严格处理。它保留了朴素集合论的有价值的成果并消除了其可能存在的悖论，因而较圆满地解决了第三次数学危机。

2026/9/1510/79主要内容集合的概念及其表示集合的运算及恒等式有穷集的计数和包含排斥原理应用与拓展2026/9/1511/792026/9/1512/79集合是由某些特殊对象汇集在一起构成的。一般来说这些对象具有某种共同的性质。组成集合的那些个体称为集合的元素。全体中国人全部整数全国的高校全部叫李明的人用大写字母表示集合（如A），小写字母表示集合中的事物（如a）若个体a是集合中A的元素，记作“a∈A”若个体a不是集合中A的元素，记作“aA”3.1集合的概念及其表示一、集合和元素2026/9/1513/79一、集合和元素注意：集合中的元素也可以是集合。2026/9/1514/79二、集合的表示方法（1）枚举法：把集合中的元素写在一个花括号内，元素间用逗号隔开。

例如：A={2,a,b,9},B={4,5,6,7,8}（2）构造法：构造法又叫谓词法。如果P(x)是表示元素x具有某种性质P的谓词，则所有具有性质P的元素构成了一个集合，记作A={x|P(x)}。例如：集合B可以表示成B={a|a∈N且4≤a≤8}D={2x∣x∈Z且x≤50},即D={0,2,4,6,…,98,100}2026/9/1515/79二、集合的表示方法几个常见的集合的表示符号：N：所有正整数的集合。Z：所有非负整数的集合。R：所有实数的集合。I：所有整数的集合。Q：所有有理数的集合。P：所有素数的集合。Nm：从1到m，这m个正整数的集合。Zm：从0到m-1，这m个非负整数的集合。2026/9/1516/79小插曲公务员考试、公司招聘的可能题目：23,29,31,37.下一个数是什么？3,5,8,13,21,()………..2026/9/15数列的通项公式--谓词17/79三、集合的外延和内涵符合某个概念R的那些客体的集合A，叫作该概念R的外延；集合A中诸客体共有的本质属性P(x)，叫作该概念R的内涵。

外延：所有人的集合人内涵：人所共有的本质属性（外貌、思想等）一个概念的外延越大，则内涵越小。（人，黄种人）外延性原理：两个集合相等，当且仅当它们有相同的元素。记作A=B

2026/9/1518/79四、集合的基数集合A中不同元素的个数叫集合A的基数，记作#A或|A|。例如：A={2,3,4},#A=3，A为有限集.

A={x|x∈Z},#A无穷大，A为无限集.，#S=4.五、空集不包含任何元素的集合为空集，记作

。例如：A={x|x∈R且x2+8=0}=

注意：与的区别2026/9/1519/79六、集合之间的关系1.集合的包含

定义3.1：设有集合A、B，如果A的每一个元素都是B的元素，则称A是B的子集或B是A的包含集，记或。例如：可以得出

注意：若，则有2026/9/1520/79六、集合之间的关系1.集合的相等

定义3.2：若A、B是两个集合，当且仅当A、B两集合恰恰有完全相同的成员时，称A、B两集合相等，记作A=B。例如：设A={x|x∈N

且

x能整除24}，

B={1,2,3,4,6,8,12,24}

则

A=B

注意：1.集合中不考虑重复元素。例如：{1,2,3}={1,2,2,3}.2.集合中不考虑元素的排列顺序。例如：{1,2,3}={3,2,1}.3.{1,2,3}{1,{2,3}}.2026/9/1521/79集合的包含关系应具有以下性质：(1)对任意集合A，都有(2)对任意集合A，都有(3)对任意集合A、B，(4)对任意集合A、B、C，若，那么证明:(1)（反证法）假设是假，则至少有一个元素x，使得且，然而这与空集不包含任何元素相矛盾，所以以上假设不成立，即为真。A的平凡子集2026/9/15六、集合之间的关系22/79六、集合之间的关系3.集合的真包含定义3.3：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则A称为B的真子集，或A真包含于B，记作。

例如：设A={0，1}，B={0，1，2}，C={0}

则2026/9/1523/79

A⊆CA∈C

ABCD提交多选题1分七、全集定义3.5：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E。举例：全集的概念相当于论域，如在初等数论中，全体整数组成了全集。UAAB2026/9/1524/79八、幂集定义3.6：给定集合A，由集合A的所有子集为元素组成的集合称为集合A的幂集，记为。例：设A={a}

1个元素的子集：{a}则0个元素的子集：

设B={a,b}

1个元素的子集：{a},{b}

2个元素的子集：{a,b}则0个元素的子集：

设C={a,b,c}

1个元素的子集：{a},{b},{c}2个元素的子集：{a,b},{a,c},{b,c}

3个元素的子集：{a,b,c}则0个元素的子集：；2026/9/1525/79九、幂集2026/9/15定理3.2若有限集合A有n个元素，则它的幂集P(A)有2ⁿ个元素。证明应用数学归纳法。当n=0时，A=∅，P(A)={∅}，有2⁰=1个元素。假设集合A有n个元素时，P(A)有2ⁿ个元素。向A中添加新元素aₙ₊₁后，所得幂集中的子集分为两类：①不含aₙ₊₁的子集，共2ⁿ个；②含aₙ₊₁的子集，也共2ⁿ个。因此共有2ⁿ+2ⁿ=2ⁿ⁺¹个子集，定理得证。26/79幂集的编码表示以S={a,b,c}为例说明可得2026/9/1527/7929（多选）

以下命题中，正确的有

ABCD提交多选题1分3.2集合的运算及恒等式定义3.7：由集合A和B的所有公共元素所组成的集合，称为集合A和B的交集。记作一、相交运算例如：

设A={a,b,c,d},B={d,f,a},C={e,f,g}则可以看出AB2026/9/1529/79一、相交运算证明：若则，对任一，则且，即且，故，因此。集合的交运算具有如下性质：AB2026/9/1530/79一、相交运算类推至多个集合的情况，集合的交运算仍满足结合律。假设有n个集合A1,A2,…An，那么这些集合的交集可表示为：2026/9/1531/79二、联合运算（集合的并）定义3.7：由集合A和B的所有元素组成的集合称为A和B的并集，记作AB例如设A={a,b,c},B={c,d,f},C={b,e}那么可以看出2026/9/1532/79二、集合的并集合的并运算具有如下性质：注意：假设有n个集合A1,A2,…An，那么这些集合的并集可表示为：2026/9/1533/79二、集合的并2026/9/15例3.1证明：A∪(B−C)⊇(A∪B)−(A∪C)。证明对于任意x，x∈(A∪B)−(A∪C)⇔x∈A∪B且x∉A∪C⇔(x∈A或x∈B)且(x∉A且x∉C)⇔x∉A且x∈B且x∉C⇒x∈A或(x∈B且x∉C)⇔x∈A∪(B−C)。因此，A∪(B−C)⊇(A∪B)−(A∪C)。34/79二、集合的并2026/9/15例3.2证明：A∩(B−C)=(A∩B)−(A∩C)。证明对于任意x，x∈(A∩B)−(A∩C)⇔x∈A∩B且x∉A∩C⇔(x∈A且x∈B)且(x∉A或x∉C)⇔x∈A且x∈B且x∉C⇔x∈A且x∈B−C⇔x∈A∩(B−C)。因此，A∩(B−C)=(A∩B)−(A∩C)。35/79二、集合的并2026/9/15例3.3证明：A∩(B−C)=(A∩B)−(A∩C)。证明A∩(B−C)=A∩B∩∼C；又(A∩B)−(A∩C)=(A∩B)∩∼(A∩C)=(A∩B)∩(∼A∪∼C)=(A∩B∩∼A)∪(A∩B∩∼C)=A∩B∩∼C。因此，A∩(B−C)=(A∩B)−(A∩C)。36/79二、集合的并2026/9/15例3.4证明：(A⊕B)⊕C=A⊕(B⊕C)。证明利用A⊕B=(A∩∼B)∪(∼A∩B)，分别展开等式两边，可得(A⊕B)⊕C=(A∩∼B∩∼C)∪(A∩B∩C)∪(∼A∩B∩∼C)∪(∼A∩∼B∩C)，A⊕(B⊕C)=(A∩∼B∩∼C)∪(A∩B∩C)∪(∼A∩B∩∼C)∪(∼A∩∼B∩C)。两式右端相同，因此(A⊕B)⊕C=A⊕(B⊕C)。37/7939

A∪B=BA∩B=AA−B=∅

ABCD提交多选题1分三、差分运算（集合的补）定义3.7：设A,B是两个集合，所有属于A而不属于B的元素组成的集合，称为A和B的差集或B对A的相对补集。记作A-B绝对补集：B对E的相对补集叫做绝对补集，简称补集，记作~BAB

A-BA~A38/79三、差分运算（集合的补）例：设A是小于10的素数集合，B是奇数集合，求A-B。解：A={2,3,5,7}B={1,3,5,7,9}

A-B={2}例：设U=I(I是整数集合)

解：39/79三、差分运算（集合的补）集合的差分运算还具有如下性质：A~A40/79三、差分运算（集合的补）例3.5证明：A⊕B=A⊕C⇒B=C。证明由于A⊕B=A⊕C，因此A⊕(A⊕B)=A⊕(A⊕C)⇒(A⊕A)⊕B=(A⊕A)⊕C⇒∅⊕B=∅⊕C⇒B=C。41/79三、差分运算（集合的补）例3.6证明：A∪B=B⇔A⊆B⇔A∩B=A⇔A−B=∅。①A∪B=B⇒A⊆B。任取x∈A，则x∈A∪B；由A∪B=B，得x∈B，因此A⊆B。②A⊆B⇒A∩B=A。由A⊆B，得A∩B=A。42/79三、差分运算（集合的补）例3.6（续）③A∩B=A⇒A−B=∅。A−B=A∩∼B=(A∩B)∩∼B=A∩(B∩∼B)=∅。④A−B=∅⇒A∪B=B。A∪B=B∪(A−B)=B∪∅=B。因此，A∪B=B⇔A⊆B⇔A∩B=A⇔A−B=∅。43/79三、差分运算（集合的补）例3.7化简：((A∪B∪C)∩(A∪B))−((A∪(B−C))∩A)。解因为A∪B⊆A∪B∪C，且A⊆A∪(B−C)，所以((A∪B∪C)∩(A∪B))−((A∪(B−C))∩A)=(A∪B)−A=B−A。44/79四、对称差分运算定义3.8：设A、B为任意两个集合。属于A但不属于B的所有元素和属于B但不属于A的所有元素的并集，称为A和B的对称差集，记作。例如：A={1,2,3}B={3,2,4}

则={1,4}ABE45/79四、对称差分运算集合的对称差分运算满足如下性质：ABE46/79四、对称差分运算定理3.3

(A−B)∪(B−A)=(A∪B)−(A∩B)。证明对任意x，有x∈(A∪B)−(A∩B)⇔x∈A∪B且x∉A∩B⇔(x∈A或x∈B)且非(x∈A且x∈B)⇔(x∈A且x∉B)或(x∈B且x∉A)⇔x∈A−B或x∈B−A⇔x∈(A−B)∪(B−A)。47/79四、对称差分运算定理3.3（续）由任意元素x的等价关系可知：(A−B)∪(B−A)=(A∪B)−(A∩B)。结合定义3.8，亦可写为：A⊕B=(A−B)∪(B−A)=(A∪B)−(A∩B)。48/79四、对称差分运算上述证明结果可以通过以下文氏图清楚看出。EABCBACE49/7952

C⊆(A∩B)∪~(A∪B)​

C⊆A∪B

ABCD提交多选题1分五、集合定律50/79五、集合定律51/79五、集合定律52/79证明:(39)转化为假设为假，证明为假。由为假可知，和均__为假，即并且为真，也就是为真，使得为假。53/793.3有穷集的计数和包含排斥原理集合的运算，可用于有限个元素的技术问题。集合的基数：集合所含元素的个数。集合A的基数用|A|或#A表示。设A1,A2是有限集合，用|A1|,|A2|分别表示它们的基数，那么可以推出：54/793.3有穷集的计数和包含排斥原理两个有限集合的计数公式设A₁、A₂是有限集合，则|A₁∪A₂|=|A₁|+|A₂|−|A₁∩A₂|。当A₁∩A₂=∅时，上式化为|A₁∪A₂|=|A₁|+|A₂|。55/793.3有穷集的计数和包含排斥原理补充例题假设在10名青年中有5名是工人，7名是学生，其中兼具工人与学生双重身份的青年有3名，问既不是工人又不是学生的青年有几名？解设工人集合为W，学生集合为S，则|W|=5，|S|=7，|W∩S|=3，|W∪S|=5+7−3=9。因此，既不是工人又不是学生的青年有10−9=1（人）。56/793.3有穷集的计数和包含排斥原理包含排斥原理在三个有限集和上的推广：57/79例3.8

1～1000范围内（包含1和1000）不能被5整除、不能被6整除，以及不能被8整除的数共有多少个？解设S={x|x∈Z且1≤x≤1000}，A={x|x∈S且5整除x}，B={x|x∈S且6整除x}，C={x|x∈S且8整除x}。则|A|=200，|B|=166，|C|=125；|A∩B|=33，|A∩C|=25，|B∩C|=41，|A∩B∩C|=8。58/79例3.8（续）根据包含排斥原理，所求元素个数为|~A∩~B∩~C|=|S|−(|A|+|B|+|C|)+(|A∩B|+|A∩C|+|B∩C|)−|A∩B∩C|=1000−(200+166+125)+(33+25+41)−8=600（个）。59/793.3有穷集的计数和包含排斥原理补充例题某工厂装配30辆汽车，可选设备为收音机、空气调节器和对讲机。已知15辆有收音机、8辆有空气调节器、6辆有对讲机，且3辆三种设备都有。求没有任何设备的汽车数量。解设三个集合分别为A₁、A₂、A₃。由于两两交集至少包含三者交集，|A₁∩A₂|≥3，|A₁∩A₃|≥3，|A₂∩A₃|≥3，故|A₁∪A₂∪A₃|≤15+8+6−3−3−3+3=23。因此至少有30−23=7辆汽车没有任何设备。60/793.3有穷集的计数和包含排斥原理定理3.4（包含排斥原理）设S为有穷集，P₁，P₂，…，Pₙ是n个性质，Aᵢ表示S中具有性质Pᵢ的元素构成的子集，则S中不具有这些性质的元素个数为|∼A₁∩∼A₂∩…∩∼Aₙ|=|S|−Σ|Aᵢ|+Σ|Aᵢ∩Aⱼ|−Σ|Aᵢ∩Aⱼ∩Aₖ|+…+(−1)ⁿ|A₁∩A₂∩…∩Aₙ|。61/79定理3.4证明由德·摩根定律，∼A₁∩∼A₂∩…∩∼Aₙ=∼(A₁∪A₂∪…∪Aₙ)，因此|∼A₁∩∼A₂∩…∩∼Aₙ|=|S|−|A₁∪A₂∪…∪Aₙ|。只需证明并集的基数公式：|A₁∪…∪Aₙ|=Σ|Aᵢ|−Σ|Aᵢ∩Aⱼ|+…+(−1)ⁿ⁻¹|A₁∩…∩Aₙ|。62/79定理3.4证明（续）当n=2时，|A₁∪A₂|=|A₁|+|A₂|−|A₁∩A₂|，公式成立。假设公式对n个集合成立。对n+1个集合，有|A₁∪…∪Aₙ∪Aₙ₊₁|=|A₁∪…∪Aₙ|+|Aₙ₊₁|−|(A₁∪…∪Aₙ)∩Aₙ₊₁|。63/79定理3.4证明（续）利用分配律，(A₁∪…∪Aₙ)∩Aₙ₊₁=(A₁∩Aₙ₊₁)∪…∪(Aₙ∩Aₙ₊₁)。对右端n个集合应用归纳假设，并与|A₁∪…∪Aₙ|的展开式合并同类项。64/79定理3.4证明（续）合并后得到|A₁∪…∪Aₙ₊₁|=Σ|Aᵢ|−Σ|Aᵢ∩Aⱼ|+Σ|Aᵢ∩Aⱼ∩Aₖ|−…+(−1)ⁿ|A₁∩A₂∩…∩Aₙ₊₁|，其中各求和指标均遍历1≤i<j<k<…≤n+1。65/79定理3.4证明（续）于是包含排斥公式对n+1个集合也成立。由数学归纳法，公式对任意有限个集合成立。再由|∼A₁∩…∩∼Aₙ|=|S|−|A₁∪…∪Aₙ|，即可得到定理所述公式。66/79定理3.4证明完毕|∼A₁∩∼A₂∩…∩∼Aₙ|=|S|−Σ|Aᵢ|+Σ|Aᵢ∩Aⱼ|−Σ|Aᵢ∩Aⱼ∩Aₖ|+…+(−1)ⁿ|A₁∩A₂∩…∩Aₙ|。67/793.3有穷集的计数和包含排斥原理补充例题求1到250之间能被2、3、5、7中任何一个整除的整数个数。解设A₁、A₂、A₃、A₄分别表示能被2、3、5、7整除的整数集合。|A₁|=125，|A₂|=83，|A₃|=50，|A₄|=35；|A₁∩A₂|=41，|A₁∩A₃|=25，|A₁∩A₄|=17，|A₂∩A₃|=16，|A₂∩A₄|=11，|A₃∩A₄|=7。68/793.3有穷集的计数和包含排斥原理补充例题（续）|A₁∩A₂∩A₃|=8，|A₁∩A₂∩A₄|=5，|A₁∩A₃∩A₄|=3，|A₂∩A₃∩A₄|=2，|A₁∩A₂∩A₃∩A₄|=1。由包含排斥原理，|A₁∪A₂∪A₃∪A₄|=125+83+50+35−(41+25+17+16+11+7)+(8+5+3+2)−1=193。69/79补充例题某系100名学生至少学习法、德、英三种语言中的一种。学习法语、德语、英语的分别有42、45、65人；学习法德、法英、德英的分别有15、20、25人。求同时学习三种语言的人数和仅学习英语的人数。70/79补充例题（续）设A、B、C分别表示学习法语、德语、英语的学生集合，则|A∪B∪C|=100，|A|=42，|B|=45，|C|=65，|A∩B|=15，|A∩C|=20，|B∩C|=25。由包含排斥原理，|A∩B∩C|=8。仅学习英语的人数为|C|−|A∩C|−|B∩C|+|A∩B∩C|=65−20−25+8=28。71/79例3.10求欧拉函数的值。欧拉函数φ(n)表示{0,1,…,n−1}中与n互素的数的个数。例如φ(12)=4，因为与12互素的数有1、5、7、11。利用包含排斥原理给出欧拉函数的计算公式。解给定正整数n，设n=p₁ᵃ¹p₂ᵃ²…pₖᵃᵏ为n的素因子分解式，令Aᵢ={x|0≤x<n，且pᵢ整除x}，则φ(n)=|~A₁∩~A₂∩…∩~Aₖ|。72/79下面计算等式右边的各项，例3.10（续）由|Aᵢ|=n/pᵢ，|Aᵢ∩Aⱼ|=n/(pᵢpⱼ)，…，根据包含排斥原理，φ(n)=n−Σ(n/pᵢ)+Σ(n/(pᵢpⱼ))−…+(−1)ᵏn/(p₁p₂…pₖ)=n(1−1/p₁)(1−1/p₂)…(1−1/pₖ)。例如φ(12)=12(1−1/2)(1−1/3)=4。73/793.4应用与拓展3.4.1合PointNet与DeepSets：让计算机“看懂”三维世界的集合。

在三维计算机视觉与自动驾驶领域，激光雷达采集的数据通常以点云形式呈现——即三维空间中一组无序的坐标点。从数学上看，一个包含若干点的点云就是一个集合，其中每个元素代表一个三维坐标。关键难点在于：点云是无序的，交换任意两点的索引不改变点云所表示的物体形状。传统深度学习方法要求输入具有规则网格结构，因此必须先将点云转换为体素或多视图图像，这导致数据冗余且破坏了集合的本质特性。DeepSet理论为这一问题提供了严格的数学基础。Zaheer等人在2017年证明：任何定义在有限集合上的置换不变函数，都可以分解为两个部分的组合——首先是对每个元素独立进行变换，然后是对所有变换结果进行对称聚合。这一结论直接对应集合论中的基本性质：集合由其元素唯一确定，与枚举顺序无关。

74/792026/9/15PointNet是这一理论在工程上的首个成功落地。其架构严格遵循DeepSets的分解形式：首先通过共享的多层感知机对每个点独立提取特征；随后使用对称池化层（最大池化或求和池化）聚合所有点的信息，得到全局特征向量。该过程保证了无论输入点以何种顺序排列，网络输出的特征表示保持不变。后续的PointNet++进一步引入了分层集合学习，通过在最优度量空间内递归地对点集进行嵌套划分，对应于集合论中子集族与覆盖的概念，从而捕获局部几何结构与多尺度上下文。在工具层面，PointNet的官方实现基于TensorFlow，而PyTorchGeometric等现代图神经网络库已将其封装为标准的卷积层，支持端到端的点云分类、分割与检测任务。从理论到工程的映射关系十分清晰：集合的无序性通过置换不变的网络架构得以保持，而集合元素数量的可变性则通过共享权重与池化操作天然处理。75/792026/9/153.4.2DETR：用集合匹配让计算机“一眼看清”画面中所有目标当我们观察街景照片时，车辆、行人和红绿灯等目标天然构成一个无序集合。传统目标检测方法通常依赖大量预设锚框，并通过非极大值抑制（NMS）去除重复预测，流程较为复杂。2020年提出的DETR将目标