离散数学[5]-集合论-集合代数

一、关于无限

集合论概念

•  集合论是以集合概念为基础，研究集合的一 般性质的数学分支学科。

  • “集合”是比“数”更简单的概念
  • 集合论试图从研究集合出发，定义“数”和数的“运算”， 进而发展到整个数学，是研究数学基础的学科

• 集合是简单而又基本的不作定义的初始概念 一般来说，集合是一些确定的、相异的事物的总体

• 按照集合中事物数目是否有限，可以分为有限集合和无限集合 无限集合是集合论研究的主要对象，也是集合论建 立的关键和难点

集合论与无限

•  集合论的全部历史都是围绕无限概念 展开的 人们把康托尔(G.Cantor，1845-1918) 于1873年12月7日给戴德金(R.Dedekind， 1831-1916)的信中最早提出集合论思想 的那一天定为集合论诞生日。
•  康托尔对无限集合的研究使集合论成 为数学中最富创造性的伟大成果之一 人们对于无限的研究可以追溯到两千 多年以前

芝诺(Zeno)悖论，公元前5世纪

• 二分法悖论:一个物体从A地出发，永远不能到达B地 从A到B，必须经过A和B的中点，还有中点的中 点……，有限的时间内不能经过无限个点，所以A永 远不能到B
• 阿基里斯追乌龟悖论    飞毛腿阿基里斯追不 上他前面的乌龟 当阿基里斯到达乌龟的出发点，乌龟已经向前走了 一段，阿基里斯再走过这一段的时候，乌龟又向前 走了一段，这样，两者永远保持一段距离，所以阿 基里斯怎么也追不上乌龟
• 飞箭不动 飞箭在任何瞬间总是处在一个确定的位置，因此在此刻处在静止状态，无限个静止的总和还是静止， 所以飞箭总是静止的。
• 芝诺悖论涉及到时间空间的连续性问题，以及无限集合
  • 自从芝诺悖论提出以来，人们一直试图指出其中的 错误所在，然而直到今天，仍然没有一个完全满意 的解答
• 但芝诺悖论涉及的无限问题却使数学家和哲 学家关注了两千多年去试图解决
• 古希腊数学家排除了无限概念，几何学里设 置了“整体大于部分”的公理

两种无限:进程和整体

• 潜无限

  • 作为过程的无限，指永远延伸、永远完成不了的进程，如 自然数数列1,2,3,…,n,..

• 实无限

  • 作为已完成的整体的无限，如自然数全体组成的整体 {1,2,3,…,n,…}

• 亚 里 士 多 德 (Aristotle,B.C.384-322) 最先 提出要区分潜无限和实无限并认为只存在潜无限，实无限即无限集合是不存在的，因 为无限多个事物不能构成一个固定的整体。

• 由于无限集合不符合常识和经验，两千多年 来，数学家都和亚里士多德一样对无限集合 持否定态度

无限集合(实无限)的性质被陆续发现

•  普罗克拉斯(Proclus,410-485)在研究直径 分圆的问题时发现直径数量和将圆分成部分 的数量有一一对应的关系

  • 由于直径的数量是无穷的，所以表明直径的数量集 合{1,2,3,…n,…}和圆被分成部分数量集合 {2,4,6,…2n,…}之间存在一一对应的关系

•  两个大小不同的同心圆上面的点可以通过公共半径来一一对应

• 伽利略(G.Galileo,1564-1642)也发现不等长线段上的点可以构成一一对应关系。

一一对应关系

• 捷克数学家波尔察诺(B.Bolzano,1781- 1848)最先明确承认并坚决拥护无限集合的概

  • 将发现的一一对应关系称作等价关系 并用大量实例指出这种关系真实存在
  • 如实数集[0,5]和实数集[0,12]之间的点可以建立 一一对应关系:y=(12/5)x

康托尔对无限集合的贡献

• 《所有实代数数集合的一个性质》，较全面阐述了无限集合思想
• 康托尔以异于常识的思考定义了无限集合， 还区分了两种不同的无限集合:可数集和具有连续统的势的集合

和自然数构成一一对应关系的可数集

和实数区间[0,1]构成一一对应的具有连续统的势的集

•  康托尔进一步证明了一条直线上的点和整个 n维空间中的点具有一一对应的关系

• 又引入了基数、序数、超限基数、超限序数 等概念，并规定了它们的运算

  • 基数(势)的引入描述了集合中元素数量的一种刻 画，并规定和区分了不同层次无限集合的基数

• 集合论需要严格运用纯理性的论证，其结论 不是人的直观和常识所能够掌握的

• 康托尔的朴素集合论成为整个数学的基础

公理化集合论

•  为了在朴素集合论中消除悖论，人们想了各 种办法来限制“病态集合”的产生

  • 罗素的“类型论”，限制集合和元素之间的缠绕

• 最成功的是采用希尔伯特公理化思想对朴素 集合论进行公理化

  • 将集合作为不作定义的基本概念，通过一系列公理 描述集合的性质，并避免产生悖论。

• 公理化集合论产生发展以后，普遍认为它给数学提供了一个可靠的基础

关于无限的故事:希尔伯特旅馆

• 一家具有无限间房间的旅馆
•  某一天，已客满
• 又来了一位客人，住下了 （1号搬到2号，2号搬到3n）
•  又来了无限位客人，也住下了(所有n号房间的搬到2n号房间，n号房间空着)
•  先前的无限位客人每人带来了无限位 朋友，还是都住下了……（）

二、集合基本概念

什么是集合?

•  集合(set):做为整体识别的、确定的、 互相区别的一些对象的总体。

  • 整体识别:不再分割

  • 确定:属于或者不属于整体

  • 互相区别:各异的对象

  • 集合的例子

    • 北京大学的全体学生:组成对象是学生
    • 全体自然数0，1，2，……:组成对象是各个自然数
    •  北京大学的全体学生 ：组成对象是学生
    • 全体自然数0，1，2，…… ：组成对象是各个自然数
    •  方程x2-2x+1=0的根 ：组成对象是1(不是两个1)
    • 方程x2+x+1=0的根 ：如果讨论复数，则组成对象是两个复数 如果讨论实数，则是一个没有任何组成对象的集合

集合的基本概念:成员

• 组成集合的对象称为成员(member)或者元素(element)

  • 元素可以是任何具体或者抽象的事物
  • 元素也可以是集合

• 集合的记号“{,}”

  • A={1,2,3}
  • S={1,{2,3},10}
  • N={ }

• 元素和集合的隶属关系

  • 当对象a是集合A的成员时，称a属于A，记做“a∈A”
  • 当对象a不是集合A的成员时，称a不属于A，记做 “¬(a∈A)”或者“aA”

规定集合的方式:列举法、描述法、归纳法

• 列举法:将所有元素列举 A={1,2,3} B={a1,a2,…,an}
• 描述法:将集合中元素的特征用谓词 公式描述 A={x|P(x)}或者A={x:P(x)} 表示x∈A当且仅当P(x)
•  归纳法 后面的章节专门说明 我们已经用归纳法定义了数理逻辑中命题公 式、个体项等

一些集合规定的例子

•  {0,1}={x|x=0∨x=1}
•  N={0,1,2,3,…}={x|x是自然数}
• I+={1,2,3,…}={x|x是正整数}
• Nn={0,1,2,…,n-1}={x|x∈N∧0≤x<n}
•  前n个自然数集合的集合
•  ={{0},{0,1},{0,1,2},…} ={x|x=Nn∧n∈I+}
•  ={Nn|n∈I+}

集合的基本概念

• 空集

  • 没有任何元素的特定集合称为空集，记做ø ø={}={x|x≠x}

• 有限集(finitesets)

  • 空集和只含有限多个元素的集合称作有限集 否则，称作无限集(infinite sets)

• 基数(cardinality) 有限集合中成员的个数称作集合的基数(无 限集合的基数定义更为复杂)

• 集合A的基数记做|A|

集合论的三大基本原理

• 外延公理、概括公理、正规公理:规定了集合概念的意义

•  外延公理(extensionality axiom)

  •  两个集合A和B相等当且仅当它们具有相同的元素。
  •  A=B ↔ x(x∈A↔x∈B)
  • {0,1}={1,0}={x|x=0∨x=1}
  • 说明集合元素的无序性，以及集合表示形式的不唯一性

• 概括公理(comprehension axiom)

  •  对于任意个体域U，任一谓词公式P都确定 一个以该域中的对象为元素的集合S。
  •  S={x|x∈U∧P(x)}
  •  规定了集合成员的确定性
  •  空集:P(x)为永假式

• 正规公理(regularity axiom)

  • 不存在集合A1, A2, A3, … 使得:…∈A3∈A2∈A1
  • 直观来说就是集合的有限可分，个体域的元素是“基本粒子”
  • 正规公理确立了元素和集合的不同层次性， 集合不能是自己的成员
  • 排除了A={A}这样的“病态”集合

引发罗素悖论的抽象原理

• 康托尔的朴素集合论中没有考虑个体域的概念

  〉 S={x|P(x)} 〉 罗素悖论:考虑

谓词Q(x)=xx，和集合B={x|Q(x)} 〉 要判定Q(B)的真值:

如果Q(B)为真，那么B∈B，但得到Q(B)假 如果Q(B)为假，那么BB，但得到Q(B)真

三、子集合

子集合

• 集合A称作集合B的子集合，如果A的 每一个元素都是B的元素

  •  x(x∈A→x∈B)，那么 A是B的子集，记做A⊆B

• 集合的两个基本关系:隶属和包含

子集合的例子

•  {a,b}{a,b,c,d}
•  {a,b,c}  {a,b,c}
•  a{a,b,c}不成立，只有a∈{a,b,c}
•  {a,b}{{a,b},{c,d}}:false
•  {a,b}∈{{a,b},{c,d}}:true
•  有时候隶属和包含关系会同时成立 {1}和{1,{1}}之间的关系

子集合的性质

定理1:对于任意集合A和B，A=B当且仅当A⊆B且B⊆ A 特别的，对于任意集合A，有A⊆ A

证明:

A=B
∀x(x∈A↔x∈B)......外延公理
∀x((x∈A→x∈B)∧(x∈B→x∈A))
∀x(x∈A→x∈B)∧x(x∈B→x∈A)
(A⊆B)∧(B⊆A)

定理2:设A,B,C为任意集合，若 (A⊆ B)∧(B⊆ C)，则有A⊆ C

利用逻辑蕴涵式I6: (A→B)∧(B→C)╞A→C来证明

定理3:对于任意集合A，A⊆ U

因为x∈U是恒真的，所以∀x(x∈A→x∈U) 也是恒真的

定理4:对于任何集合A，ø⊆ A

因为x∈ø是恒假的，所以∀x(x∈ø→x∈A) 是恒真的

定理5:空集是唯一的

假设有两个空集ø1和ø2，
根据定理4，有ø1⊆ ø2，而且ø2⊆ ø1
再根据定理1， ø1=ø2

定理6:设A为一有限集合，|A|=n，那么A 的子集个数为 2n次幂

A的子集有: ø:Cn0=1个
只有包含A中1个元素的子集:Cn1个 只有包含A中2个元素的子集:Cn2个
......
包含A中所有元素的子集:A本身， Cnn=1个
总和: Cn0+Cn1+...+ Cnn=2n个
例:{1,2}的子集:ø,{1},{2},{1,2}

真子集(proper subset)

如果A⊆ B且A≠B，记做:A⊂B 空集ø是所有非空集合的真子集

判断题:

ø⊆ø
ø∈ø
ø⊆{ø}
ø∈{ø} 如果A∈B且B∈C，那么A∈C

四、集合运算

集合基本运算

集合运算指以集合作为运算对象，结果还是集合的运算

并运算:∪(union)
定义:A∪B={x|x∈A∨x∈B}
{1,2}∪{1,3,4}={1,2,3,4}

交运算:∩(intersection)
定义:A∩B={x|x∈A∧x∈B} {1,2}∩{2,3}={2}

差运算-(difference)
定义:A-B={x|x∈A∧x∉B}

{1,2,3}-{2,3,4}={1}

补运算~(complement)
定义:A~=U-A={x|x∉A}
{0,1,2,3,4}~={5,6,7,...}(U=N)

交和并运算性质

A∪A=A;A∩A=A
交换律:A∪B=B∪A;A∩B=B∩A
结合律:A∪(B∪C)=(A∪B)∪C;A∩(B∩C)=(A∩B)∩C
A∪ø=A;A∪U=U;A∩ø=ø;A∩U=A
分配律:A∪(B∩C)=(A∪B)∩(A∪C)，A∩(B∪C)=(A∩B)∪(A∩C)

A∩(A∪B)=A，A∪(A∩B)=A

差和补运算性质

A-A=ø，A-ø=A，A-U=ø

A-(B∪C)=(A-B)∩(A-C)
A-(B∩C)=(A-B)∪(A-C)
利用德摩根律得证
A~~=A，U~=ø，ø~=U
A∪A~=U，A∩A~=ø
(A∪B)~=A~∩B~，(A∩B)~=A~∪B~
A-B=A∩B~

集合运算和子集关系

A⊆A∪B
A∩B⊆A
A-B⊆A
A⊆ B  ⇔ A-B=ø⇔ A∪B=B⇔ A∩B=A
如果A⊆ B，则有B~⊆ A~

利用运算性质证明

对于任意集合A,B，如果有A∪B=U且 A∩B=ø，那么A=B~

证明1:按照A=B的定义

证明2:按照运算性质的等式

A =A∩U =A∩(B∪B~)

=(A∩B)∪(A∩B~) =ø∪(A∩B~)
=(B∩B~)∪(A∩B~)......分配律，提出B~
=(B∪A)∩B~ =U∩B~

幂集(power set)运算

对任意集合A，ρ(A)称作A的幂集，定义为:

ρ(A)={x|x⊆A}

A的所有子集作为元素构成的集合(族)

因为ø⊆ A，A⊆A;所以必有ø∈ρ(A)， A∈ρ(A)

例:ρ({1,2})={ø,{1},{2},{1,2}}

幂集的基数:|ρ(A)|=2|A|

幂集的性质

设A,B为任意集合:
A⊆B当且仅当ρ(A)  ρ(B)
证明必要性:(A⊆ B)→(ρ(A)⊆ ρ(B))
设A⊆B，又设任意X∈ρ(A)，有X⊆ A
因为A⊆B，所以X⊆B
有X∈ρ(B)
根据子集定义，ρ(A)⊆ ρ(B)

证明充分性:(ρ(A)⊆ ρ(B))→(A⊆B)

〉 设ρ(A)⊆ ρ(B)，假设A⊆ B不成立
〉 则存在a∈A，但是a∉B
〉 也就是{a}∈ρ(A)，但是{a}∉ ρ(B)
〉 这个与ρ(A)⊆ ρ(B)矛盾
〉 所以A⊆B得证

五、集合族及运算

集合族与标志集

• 集合族(collections)

  • 如果集合C中的每个元素都是集合，称C为 集合族

•  集合族的标志集(indexset)

  • 如果集合族C可以表示为某种下标的形式 C={Sd|d∈D}
  • 那么这些下标组成的集合称作集合族C的标志集

• 标志集可以是自然数、某些连续符号

集合族和标志集例子

•  C={{0},{0,1},{0,1,2},…}是集合族，但是没有标志集
• 如果定义Nn={0,1,2,…,n-1}，那么C就可以表示为{Nn|n∈I+}，这样C的标志集就是 I+
• 集 合 族 C={Sa,Sb,Sc}={Sd|d ∈ {a,b,c}} ， 标志集就是{a,b,c}
• A的幂集ρ(A)是一个集合族

集合族的运算

广义并:集合族中所有集合的并集

∪C={x|∃S(S∈C∧x∈S)}

广义交:集合族中所有集合的交集

∩C={x|∀s(S∈C→x∈S)}

如果C恰含两个集合A,B

则∪C=A∪B，∩C=A∩B

有标志集的表示方法:C={Ad|d∈D}

∪C=∪d∈DAd， ∩C= ∩d∈DAd

集合族运算例子

C={{0},{0,1},{0,1,2},...}

∪C=N
∩C={0}
C={{1},{1,2},{1,3,5}}

∪C={1,2,3,5}
∩C={1}

集合族运算性质

任意集合A和集合族C，有

A∩(∪C)=∪{A∩S:S∈C}
A∪(∩C)=∩{A∪S:S∈C}
A-(∩C)=∪{A-S:S∈C}
A-(∪C)=∩{A-S:S∈C}
(∪C)~=∩{S~:S∈C}
(∩C)~=∪{S~:S∈C}

证明:A-(∪C)= ∩{A-S:S∈C}

x∈A-(∪C)
<=>x∈A∧x∉ UC
<=>x∈A∧¬(∃S(S∈C∧x∈S))
<=>x∈A∧∀S(S∉ C∨x∉ S)
<=>∀S((x∈A∧S∉C)∨(x∈A∧x∉S))
<=>∀S((x∉A∨S∈C)→(x∈A-S))
<=>∀S(((x∉A)→(x∈A-S))∧((S∈C) →(x∈A-S)))

<=>∀S((S∈C)→(x∈A-S))
<=>x∈∩{A-S:S∈C}

幂集与集合族运算

证明:对任意集合A，∪ρ(A)=A

x∈∪ρ(A)
<=>∀S(S∈ρ(A) ∧x∈S)
<=>∀S(S⊆ A∧x∈S)
<=>∀S(x∈A)

<=>x∈A

六、归纳定义

集合的归纳定义

〉 集合定义的另两种方式:列举法、描述法
〉 归纳定义(inductivedefinition)

基础条款:规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定

归纳条款:规定由已确定的集合元素去进一步确定其它元素的规则

终极条款:规定待定义集合只含有基础条款和归纳条款所确定的成员

〉 基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生 集合中所有成员

〉 终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款 的那些对象

归纳定义例子:“圣诞节”

•  基础条款   耶稣基督降生的那天是圣诞节
• 归纳条款    如果某天是圣诞节，则这一天后的第365天 也是圣诞节(不考虑闰年)
• 终极条款    除了上面两条所包括的日子，其它日子都不是圣诞节

归纳定义例子:偶数集合

•  个体域U为自然数集，定义偶数集E
•  基础条款:0∈E
•  归纳条款:若x∈E，则x+2∈E
•  终极条款:除了有限次使用上述条款 确定的元素以外，E中没有别的元素
• 奇数集O的定义?

归纳定义例子:程序

•  基础条款: v:=e是程序(其中v是变量，e是算术表达式)

• 归纳条款: 若p1,p2是程序，则p1;p2也是程序 若p1,p2是程序，则if c then p1 else p2 end if也是程序(其中c是条件 表达式); 若p是程序，则while c do p end while也是程序;

• 终极条款(略)

七、自然数定义

自然数定义

• 数学中“数”是最基本的原始概念，在集合论创立之后，采用集合来定义自然数，使得数学建立在更为简单的概念“集合”基础之上

•  在算术公理化系统中，皮亚诺(Peano)的5大公理刻画了自然数概念

  • P1:至少有一个对象是自然数，记做0;
  • P2:如果n是自然数，那么n必定恰有一个直接后继，记做n'
  • P3:0不是任何自然数的直接后继
  • P4:如果自然数m,n的直接后继m',n’相同，那么m=n
  • P5:没有不满足上述条件的对象是自然数

利用集合定义自然数要考虑的几个问题

•  找一个最简单的集合作为0
• ∅
•  找一种集合运算定义“直接后继”
•  ∪? ∩?-?
• 这种集合运算不可能得到0对应的那个集合
• ∅
•  可以通过集合关系反应自然数的顺序性质
• ⊆、 ⊂

自然数集N的归纳定义

•  基础条款:∅∈N

• 归纳条款:如果x∈N，则x'=x∪{x} ∈N

• 终极条款(略)

• 自然数集的列举定义:

  •  {∅, {∅}, {∅,{∅}}, {∅, {∅}, {∅,{∅}}}, …}
  • 实际上有:1={0}, 2={0,1}, 3={0,1,2}
  • 0∈1∈2∈3…同时也有0∈3
  • 还有0⊆ 1⊆ 2⊆ 3…
  • 1⊆ 2，4⊆ 10，10⊆ 10体现了顺序关系，而 且子集关系具有传递性

如果我们用x'={x}∈N作直接后继会如何?

•  {∅ ,{∅ },{{∅ }},{{{∅ }}},….}
•  0∈1∈2∈3
• 但是没有1∈3
• 子集关系⊆ 在自然数之间也不成立

递归定义自然数的运算:+、×

•  加法的定义:

  *  x+0=x
  
  *  x+y'=(x+y)' 〉 如: 3+2=(3+1)'=((3+0)')' =(3')'=4'=5
  

•  乘法的定义

  •  x×0=0
  •  x×y'=(x×y)+x
  • 例子
  • 如:3×2=(3×1)+3 =((3×0)+3)+3
  • =(0+3)+3 =(0+2)'+3 =((0+1)')'+3
  • =(((0+0)')')'+3 =((0')')'+3 =3+3
  • =……
  • =6

八、归纳原理

归纳原理

• 设集合A是归纳定义的集合
• 要证明A中所有元素具有性质P，即: ∀x(x∈A→P(x))，可以进行如下的证明:

(归纳基础)针对归纳定义的基础条款，证 明基础条款中的所有元素均使P(x0)真

(归纳推理)证明归纳条款是“保持性质P 的”

即在假设归纳条款中已确定元素x使P(x)真 的前提下，证明用归纳条款中的操作g所生 成的g(x) 依然有性质P，即P(g(x))为真

证明:命题公式中左括号的数量等于右括号的数量

• 命题公式，是由归纳定义所定义的集合
• 设L[A],R[A]分别表示公式A的左括号数量和右括号的数量
•  (归纳基础):对于命题变元(或常元)p，L[p]=R[p]=0
•  (归纳推理):设L[A]=R[A],L[B]=R[B]，那么:

L[(¬A)]=L[A]+1=R[A]+1=R[(¬A)] L[(A→B)]=L[A]+L[B]+1=R[A]+R[B]+1=R[(A→B)]

所以对于一切命题公式，左括号数量等于右括号数量

九、数学归纳法

数学归纳法

• 既然自然数集合也是归纳定义的，对于自然数的一些性质，也可以通过归纳原理来证明，即我们通常用的“数学归纳法”
• 第一数学归纳法

归纳基础:证明P(0)为真

归纳过程:对于任意k≥0假设P(k)为真时， 推出P(k+1)也为真

结论:所有自然数n都使P(n)为真

数学归纳法例子

证明对任意自然数有(0+1+2+…+n)2=03+13+23+…+n3 归纳基础:当n=0，02=03

归纳过程:

设当n=k时， (0+1+2+...+k)2=03+13+23+...+k3成立，
当n=k+1时， (0+1+2+...+k+(k+1))2
=03+13+23+...+k3+(k+1)2+2(0+1+2+...+k)(k+1)
=03+13+23+...+k3+(k+1)2+k(k+1)2
=03+13+23+...+k3+(k+1)3
归纳完成，命题得证※

数学归纳法的变种

•  起始于任意自然数n0的数学归纳法 证明所有大于等于n0的自然数都具有性质P

• 起始于多个自然数的数学归纳法

  • 归纳基础:证明P(0),P(1)真
  • 归纳过程:对于任意k≥0假设P(k)为真时， 推出P(k+2)也为真
  • 结论:所有自然数具有性质P

• 允许有参变量的数学归纳法 对于二元谓词P(m,n)，证明对于一切自然 数m,n都为真，可以视情况只对一个变量进 行归纳，另一个变量作为参数

数学归纳法例子

证明:3分币和5分币可以组成8分以上任何币值

证明:8=3+5;9=3+3+3;10=5+5

假设k可以用3分和5分币组成， 需要证明k+3时命题真， 这是显然的，只要再加一个3分币即 可

数学归纳法的正确性证明

假设我们已经完成下面的推理:

归纳基础:P(0)真;
归纳推理:∀k(P(k)→P(k+1))
但是还并非所有自然数都有性质P
将这些不满足性质P的自然数构成一个非空自然数子集，这样，子集中必定有 一个最小的自然数，设为m
显然m>0，记做n+1，这样n一定具有性质P，即P(n)为真
∃n(P(n)∧¬P(n+1))╞╡ ¬∀k(¬P(k)∨P(k+1))╞╡¬∀k(P(k)→P(k+1))
假设推理结果与已经完成的归纳推理矛盾，所以假设错误
即数学归纳法成立，所有自然数都有性质P

参考资料

北京大学地球与空间科学学院 陈斌 https://www.coursera.org/learn/dmathgen/home/week/4