在数学中,二元关系描述两个元素之间的关联。在集合论中,从集合 到集合 的关系,是它们的笛卡尔积中的一个子集 。记号 表示 。相等关系、数值大小关系和函数都可以在这一框架下描述。“二元”指的是关系中每个元组所含的位置数,而非二进制数。(ocw.mit.edu)
定义与记号
关系的组成元素是有序对:第一位置和第二位置各有不同的作用。集合 上的关系是 的子集,而不同集合之间的关系所关联的对象不必属于同一类。例如,学生与课程之间的关系可以记录选课情况,允许一名学生与多门课程相关联。这说明,关系不必为每个输入指定唯一的输出。(ocw.mit.edu)
函数 是一种特殊的关系,其中 的每个元素都恰好与 的一个元素配对。一般的关系则可以将一个元素与零个、一个或多个元素配对。函数在集合论意义下的图为
因此,关系的定义比函数的定义限制更少。(cs.cornell.edu)
对于给定的集合 ,它们之间的所有关系构成幂集 。因此,如果 和 分别有 个和 个元素,就有 个可能的关系:每个可能的有序对都可以包含在关系中,也可以不包含在其中。(ocw.mit.edu)
集合上关系的性质
关系 可以按以下性质分类:
- 自反性: 对每个 ,都有 。
- 反自反性: 对任何 , 都不成立。
- 对称性: 若 ,则 。
- 反对称性: 若 与 同时成立,则 。
- 非对称性: 若 ,则 不成立。
- 传递性: 若 且 ,则 。(cs.cornell.edu)
反对称性并不是对称性的否定:它只禁止不同元素之间存在双向关联。非对称性还禁止元素与自身关联。例如, 具有自反性、反对称性和传递性,而 具有反自反性、非对称性和传递性。相等关系既具有对称性,也具有反对称性。(cs.cornell.edu)
这些条件都采用全称量化,因此,缺少某些有序对并不一定违反这些条件。空关系具有对称性和传递性,因为相应条件的前提从不成立。在非空的底集上,空关系不具有自反性;但在空集上,自反性也因空真而成立。(cs.cornell.edu)
等价与序
等价关系具有自反性、对称性和传递性。它表达的是按某个选定标准来看相同,而不一定意味着对象本身完全相同。每个元素 都确定一个等价类
各个不同的等价类构成 的一个集合划分:每个元素恰好属于一个等价类。这些等价类组成的集合就是商集 。(cs.cornell.edu)
例如,在整数上,被某个固定的正整数除后余数相同,是一种等价关系。它给出了模算术中使用的等价类。(cs.cornell.edu)
预序具有自反性和传递性。偏序还满足反对称性。如果任意两个元素都可比较,即 或 ,那么它就是全序。偏序允许存在不可比较的元素,集合的包含关系就是一个例子。严格偏序具有反自反性和传递性。(cs.cornell.edu)
关系的运算
由于关系是集合,同一个笛卡尔积中的关系可以进行并、交、差运算,以及相对于该笛卡尔积的补运算。并集包含属于任一关系的有序对;交集包含同时属于两个关系的有序对。逆关系将每个有序对的次序颠倒:
这一记号并不意味着 是可逆函数。(cs.cornell.edu)
对于 和 ,关系复合通过一个中间元素将元素关联起来:
这里先应用 ,遵循函数复合的惯例;有些文献采用相反的顺序。复合满足结合律,但通常不满足交换律。恒等关系 是相应复合运算的单位元。(cs.cornell.edu)
图、闭包与计算
集合 上的关系可以用有向图表示:元素对应顶点,每个有序对 对应一条箭头 。自反性要求每个顶点都有自环;对称性要求每条箭头都有一条反向箭头;传递性要求,只要两条首尾相接的箭头形成一条路径,这条路径的起点和终点之间就必须有一条直接相连的箭头。(cs.cornell.edu)
传递闭包 恰好补入所有通过一步或多步关系连接起来的有序对。自反传递闭包 还允许零步:
它们分别是包含 的最小传递关系和最小自反传递关系。(cs.cornell.edu)
在形式验证中,程序可以被解释为初始状态与最终状态之间的关系。复合用于建模顺序执行,自反传递闭包则用于建模任意次数的重复执行,包括零次。这种解释不仅适用于确定性函数,也能涵盖具有多种可能结果的计算。(cs.cornell.edu)
参考来源
- ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_04…ocw.mit.edu
- cs.cornell.edu/courses/cs6861/2025fa/handouts/ka-book.pdfcs.cornell.edu
- cs.cornell.edu/courses/cs2800/2017sp/lectures/lec06-relations.htmlcs.cornell.edu
- cs.cornell.edu/courses/cs4160/2020sp/sf/lf/full/Rel.htmlcs.cornell.edu
- cs.cornell.edu/courses/cs2800/2017sp/lectures/lec07-equivalence.htmlcs.cornell.edu
- cs.cornell.edu/courses/cs6860/2019sp/Handouts/HKT1-3.pdfcs.cornell.edu