xry

离散数学反对称关系_《离散数学》学习记录-集合论

来源：北京⼤学《离散数学》公开课

2.1有序对和卡⽒积

有序对：有顺序，类似于数组，可以⽤集合定义。

性质：有序对内元素对应相等

卡⽒积A×B：所有元素⼀个来⾃A集合，另⼀个来⾃B集合的有序对

性质：不满⾜交换律，不满⾜结合律，对并和交满⾜分配律，具有单调性（证明见北⼤教材p25）

2.2⼆元关系

A到B的⼆元关系定义：A×B的任⼀⼦集，即A×B幂集中的⼀个元素组成的集合（注意⼆元关系也是集合）

A到B的⼆元关系的总个数：|P(A×B)|

A上的特殊⼆元关系：空关系、恒等关系、全域关系、整除关系，⼤于⼩于关系，包含关系（只有包含关系定义在幂集P(A)上，见

p26）

定义域、值域、域（由⼆元关系定义的集合）

关系的特殊情况：F是单根的、F是单值的（即F定义了⼀个函数）

⼆元关系的运算：

1.逆F^-1：将关系集合中所有的有序对反向

2.逆序合成FoG：有公共中间元素的有序对的集合

3.限制F↑A：x属于A的关系集合

4.象F[A]：F↑A的值域，定义域为A的有序对集合对应的值域

合成运算定理1：合成运算结合律（重要）

合成运算定理2：A与B合成运算的逆=B逆与A逆的合成运算

2.3关系的表⽰和关系的性质

关系矩阵（图的矩阵表⽰）

关系图

关系的性质

1.⾃反性：每个点都有环

2.反⾃反性：每个点都没有环

3.对称性：任意两点间要么有两条边要么没边

4.反对称性：任意两点间都没有两条边

5.传递性：可⾛捷径（注意考虑有环的情况）

2.4关系幂运算和关系闭包

（⼀）关系幂

1.关系R的n次幂：R与⾃⼰合成n次后得到的关系集合。也可以理解为G(R)中长度为n的路径的起点和终点组成的有序对的集合

2.关系幂具有指数律：R^m*R^n=R^(m+n)，(R^m)^n=R^(mn)

（⼆）闭包

1.R的闭包的定义：包含R，满⾜给定性质，最⼩的有序对集合（包含于任意⼀个）

2.闭包的种类：

⾃反闭包：r(R)

对称闭包：s(R)

传递闭包：t(R)

3.闭包运算的性质

定理2.19：闭包运算有不动点

定理2.20：闭包运算有单调性（即较⼤的集合的闭包也较⼤）

定理2.21：闭包运算对⾃反闭包和对称闭包的并有分配律，对传递闭包的并没有分配率

4.闭包的集合求法：

定理2.22：⾃反闭包=RU恒等关系

定理2.23：对称闭包=RUR的逆

定理2.24：传递闭包=RUR^2UR^3U.....（求传递闭包，就是把从此点可⾛到的点直接连起来）

5.闭包的图求法：

⾃反闭包：所有定点加环

对称闭包：所有单向边化为双向边

传递闭包：遍历所有点，把从此点可达到的点直接与此点连起来

6.闭包的矩阵求法：

⾃反闭包：主对⾓线全部改成1

对称闭包：改为对称矩阵

传递闭包：矩阵R逻辑或矩阵R^2逻辑或矩阵R^3........（逻辑或指：对所有运算式中的矩阵的每个对应位置上的元素进⾏或运算）

7.定理2.25：求闭包后关系性质是否改变

⾃反性在求闭包后保持不变

对称性在求闭包后保持不变

传递性在求对称闭包后可能改变（反例：a->b具有传递性，但它的对称闭包为a<->b，不具有传递性，因为a到a要两步才能达到）

8.定理2.26：闭包运算的交换律

求⾃反闭包和对称闭包运算可交换

求⾃反闭包和传递闭包运算可交换

求对称闭包和传递闭包运算不可交换，其中先求传递闭包再求对称闭包得到的闭包较⼤

2.5等价关系和划分

1.等价关系

定义

等价关系R是⾃反，对称，传递的⼆元关系

⽤等价关系分类

空关系（不是等价关系）、恒等关系（是等价关系，把每个元素⾃⼰分成⼀类）、全域关系（是等价关系，把所有元素分成⼀类）

2.等价类

R的等价类定义

所有与x有R关系的y的集合，记为[x]

等价类的⼀个例⼦

R为除以3后的同余关系（即x与y除以3的余数相等）

可证：除以n后的同余关系为等价关系（证：xRy等价于关系式x-y=k*n,其中k为整数。由定义易证此关系式满⾜⾃反性、对称性，传递

性）

现取dom={1,2,3,4,5}

那么有等价类：

[1]=[4]={1,4}（1,4是⼀个等价类，余数都是1）

[2]=[5]={2,5}（2,5是⼀个等价类，余数都是2）

[3]={3}（3是⼀个等价类，余数都是0）

在G(R)上可观察到，1,4；2,5；3分别满⾜全域关系（所有的点之间连通），即每个等价类内部具有全域关系

由此性质可知，得到关系的等价类后，就可以直接推导出所有的关系

等价类的性质（定理2.27）

1.⾮空（由于等价关系需满⾜⾃反性，所以等价类中⾄少包含x⾃⼰）

2.若xRy，则[x]R=[y]R（因为等价关系R满⾜对称性和传递性。由对称性：y与x有关，由传递性：y与x有关，x与其他元素有关，则y

与所有与x有关的元素有关。反之，x与所有与y有关的元素有关，所以x与y的相关元素相同）

3.若x和y⽆关，则[x]R与[y]R不相交（反证法：若[x]R与[y]R有⼀个共同元素z，那么参考2的思路，由对称性和传递性可得x和y必有

关）

4.所有等价类的并为A（结论显⽽易见，严格证明⽤集族的单调性，因为每个等价类都包含于A，所以所有等价类的并包含于A的并，即

A⾃⼰）

可见：等价类是对A的⼀个划分（A的每个元素都只在其中⼀个等价类中，且等价类的并为A）

⽽等价关系确定等价类的基础。⼀切划分从确定⼀个⾃反、对称、传递的等价关系开始。

（插⼀句题外话：等价类让我想起了麦肯锡咨询⾥的⼀个原则：MECE：MutuallyExclusiveCollectivelyExhaustive（相互独⽴、完全

穷尽）。麦肯锡把这个原则视为咨询的黄⾦法则，其实也就是离散数学中的划分等价类。可见许多商业逻辑的原型都是数学。）

3.商集

定义

A/R：A上R的等价类组成的集合（就是A⽤R划分的结果）

例⼦（对应刚刚等价类中的那个例⼦）

{{1,4}，{2,5}，3}

A上的等价关系有：

恒等关系

2.E全域关系

=IAU{,}（其中i不等于j，即所有点都有环，并且i和j结点有双向边。易证⾃反，对称，传递）

空关系不是等价关系

对应的商集

1.A/IA={{a1},{a2},...{an}}

2.A/E={{a1,a2,...,an}}

3.A/Rij=ai和aj为⼀类，其他元素各成⼀类

例⼦：求A={a,b,c}的等价关系（5种）和商集（5个）

4.划分（和商族等价）

定义：

A的⼀个划分是A的⼀个包含于A幂集的集族，满⾜：

集族中每个集合⾮空、集族中每个集合不相交，集族的并为A

定理2.28：

1.R为A上的等价关系->A/R是A的划分

2.A是A的划分->A的同块关系（即划分出的其中⼀个集合的关系）是A上的等价关系

Stirling⼦集数

2.6序关系

（⼀）偏序

1.偏序关系

R⾃反、反对称（反对称指：若xRy且yRx，则x=y）、传递，则称R为偏序关系

xRy记作x≤y

2.偏序集

⼀个带有偏序关系≤的集合A即为偏序集，记作

3.加细关系

划分x包含于划分y，则x是y的加细，xRy成⽴

4.可⽐

x≤y或y≤x，则x和y可⽐

5.覆盖

x≤y且x!=y，则y覆盖x

6.哈斯图

具有偏序关系的两个结点相连接，其中若y覆盖x，则y置于x上⽅

哈斯图可⽤于绘制组织框架图

7.全序关系

偏序集A中任意元素之间都可⽐，则为全序集

等价于哈斯图为直线

（⼆）拟序

1.拟序关系

R反⾃反、传递（蕴含了R是反对称的）

2.定理2.30

拟序关系有三歧性（要么x

(xx=y

以下4组概念可以类⽐⾼数中的最⼤值，最⼩值等（严格定义见p52）

3.最⼤元，最⼩元

4.极⼤元，极⼩元

5.上界，下界

6.上确界，下确界

7.链，反链

偏序集中两两都可⽐，就是链，否则是反链

总结：

偏序是⾃反，传递，反对称。实数上的⼩于等于是偏序关系

拟序是反⾃反，传递，反对称。实数上的⼩于是偏序关系

3.1函数

（⼀）函数的基本概念

函数F：F为⼀个⼆元关系，且F是单值的（单值：domF中每个x⾄多对应ranF中⼀个y）

偏函数：domF包含于A，ranF包含于B，即A中每个x在F上不⼀定有B中对应的y，严格定义见p58

真偏函数：在偏函数的基础上，domF真包含于A，即A中⼀定有x在F上没有有B中对应的y，严格定义见p58

全函数：A中每个x在F上⼀定有B上对应的y

（之后讨论的都是全函数上的情况）

（⼆）函数的性质

单射：F是单根的

满射：值域=B

双射：x和y⼀⼀对应

象和原象

特征函数

单调函数（定义在任意的偏序关系上）

⾃然映射

f:A->A/R（映射到等价类上）

函数的合成

反函数

4.1⾃然数的定义

封闭：F是函数，F(A)属于A->F是A上的⼀元运算

⽪亚诺系统：F:M->M

1.F是单射

2.e不属于F的值域

3.e属于M

4.M最⼩

5.M在F下封闭

后继运算：A+=AU{A}

归纳集D：集合D含有空集合，且对后继运算封闭

⾃然数⽤集合定义：属于每个归纳集的集合。从空集合出发，做有限次后继运算的集合⼀定是⾃然数集（0对应空集合，1对应空集合

的后继，以此类推）

⾃然数集N：包含于每个归纳集的集合。N=归纳集D的⼴义交

后继函数：N->N

后继函数是单射

定理4.1⾃然数集是归纳集

定理4.2为⽪亚诺系统

定理4.3任何⾃然数的元素均为它的⼦集

定理4.4m,n属于⾃然数集，m的后继属于n的后继等价于m属于n

定理4.5任何⾃然数都不是⾃⼰的元素

定理4.6空集属于除0以外的任何⾃然数

定理4.7单歧性：m属于n，m=n和n属于m有且仅有⼀个成⽴

4.2⾃然数的性质

传递集：A中的任何元素也是A的元素

⾃然数是传递集

定理4.10

A是传递集，等价于A的⼴义并包含于A，等价于y属于A，有y包含于A，等价于A包含于P(A)

定理4.11

A为传递集，等价于P(A)为传递集

定理4.12

A为传递集，等价于A后继运算的⼴义并为A

定理4.13

每个⾃然数都是传递集

⾃然数集合N时传递集

⾃然数集上的⼆元运算

1.加法

2.乘法

5.1集合的等势

等势：

A与B等势：存在f，使A->B双射

eg.整数集和⾃然数集是等势的

康托定理：

任何的集合A和它的幂集P(A)之间都不能建⽴双射

有穷集：

与某个⾃然数等势的集合，不能与⾃⼰的真⼦集建⽴双射的集合

⽆穷集

不能与⾃然数等势的集合

5.2基数

集合等势则基数card相同

对⾃然数集N，cardN=N(阿列夫)

cardA=Ni,则cardP(A)=Ni=1