等价关系、相容关系、偏序关系

https://www.jianshu.com/p/00b9dbde90ca

https://www.zhihu.com/question/22525311

等价关系:自反 + 对称 + 传递

(1) 集合上的恒等关系,全域关系是等价关系.
(2) 三角形的全等关系,三角形的相似关系是等价关系.
(3) 在一个班级里“年龄相等”的关系是等价关系.
(4)同余(奇数偶数划分)
(5)平行线
(6)矩阵相似、等价、合同

若说传递性的扁平化还没有消除关系的方向性,那么它与对称性的配合就彻底的让关系变成了零维的,完全失去了阶级性(偏序还保持这一点)。之前说,传递性可以理解为上/下三角,那么配合对称(以及比较trivial的自反性,它就是对角线),那么就是个正方形了。
正方形意味着,其内部关系的完整性,以及与其他元素的隔离性。而对于等价关系,它的关系矩阵一定可以转换为只在其对角线围绕着一串正方形的形式。
在等价关系中,一个等价类不分阶级、不同等价类不可比较。应该很好理解了。商集,就是所有等价类的集合;划分,就是所有等价类摆在一起;块数,就是划分的秩。

我们如何求一个划分呢?根据问题中的等价条件,抽象出等价的形式定义就好啦。

总结:等价关系是一种条件极其强大(简单)的关系,它完全消解的关系运算中的invariant,完全扁平化。

2. 相容关系:自反 + 对称

朋友的朋友不一定是朋友,但也很有可能是朋友,朋友关系就是相容关系的一个很好例子。
相容关系中,最主要的就是“对称性”,也就是双向性,是相容的意味。相容关系消解了方向性。一个朋友圈,就是一个相容类(主要是“最大相容类”概念):这个圈子内的人彼此都是朋友,这是类似等价类的概念。但一个人可以处于多个圈子内,这是与等价类不同处。
我们想象一个N个人的完整的社交圈:那就是要看这些人的朋友关系的完全覆盖,即所有最大相容类的集合。再申,一个人可以出现在多个最大相容类中,这是与等价关系的差异。

3. 偏序关系:自反 + 反对称 + 传递

还用三角的比喻,偏序关系就是带对角线的三角,且不允许出现边长大于1的正方形。

两个元素可比,意味着在同一个三角形上(还是逻辑上的三角形,可能需要堆关系矩阵经过变换得到)。
全序,则是一个巨大的三角形。覆盖关系,用于找到在偏序集上最紧凑的(相邻的)两个元素,用于后面画哈斯图。

由于偏序关系有方向,还是保持着某种“距离”的含义,但它对这个关系本身无任何内涵上的联系,只是用来画图而已。
偏序集:集合 + 偏序运算。

哈斯图:就是很像树的图,“父子”的关系是覆盖。哈斯图中可能有许多树。每棵树可以有许多树根【极小元】。每棵树可以倒过来,看起来还是一棵树。上下界、上下确界,存在性也就很显然啦。无限,也就可能无界,正如因果链,有没有第一因呢!对于无限集合,确界,也可能在关系的定义域之外,类似开区间与其边界的关系。

一点点拓展:链、反链、良序A的子集B若任意B中两个元素都可比,称B是A的一条链,元素个数称为链的长度;
A的子集B若任意B中两个不同元素都不可比,称B是A的一条反链,元素个数称为反链的长度;
它们有一点点性质:集合最长的链长n,则集合可以分解为n条反链:
不断获取极小元组成一个反链集合最长反链长n,则集合可以分解为n条链:(算法似乎还没有?)可以发现拓扑排序与链的关系。

良序:任意非空子集都存在最小元的偏序集。

这三个概念,也可以加深对于关系的理解~ 不过,我们会发现我们的思维是越来越抽象的,自底向上,似乎已经远远离开了关系的定义了: -)

发表新评论