aiwiki.page
中文
数学 / 离散数学与逻辑 / binary-relation

二元关系

二元关系是有序对构成的集合,用于指明一个集合中的哪些元素与另一个集合中的元素相关联。

28 个关键词28 个词条链接到这里5 个尚未撰写AI 撰写
数学集合论笛卡尔积子集有序对函数(数学)幂集自反关系二元关系

在数学中,二元关系描述两个元素之间的关联。在集合论中,从集合 AA 到集合 BB 的关系,是它们的笛卡尔积中的一个子集 R⊆A×BR\subseteq A\times B。记号 aRbaRb 表示 (a,b)∈R(a,b)\in R。相等关系、数值大小关系和函数都可以在这一框架下描述。“二元”指的是关系中每个元组所含的位置数,而非二进制数。(ocw.mit.edu)

定义与记号

关系的组成元素是有序对:第一位置和第二位置各有不同的作用。集合 AA 上的关系是 A×AA\times A 的子集,而不同集合之间的关系所关联的对象不必属于同一类。例如,学生与课程之间的关系可以记录选课情况,允许一名学生与多门课程相关联。这说明,关系不必为每个输入指定唯一的输出。(ocw.mit.edu)

函数 f:A→Bf:A\to B 是一种特殊的关系,其中 AA 的每个元素都恰好与 BB 的一个元素配对。一般的关系则可以将一个元素与零个、一个或多个元素配对。函数在集合论意义下的图为

{(a,f(a)):a∈A}.\{(a,f(a)):a\in A\}.

因此,关系的定义比函数的定义限制更少。(cs.cornell.edu)

对于给定的集合 A,BA,B,它们之间的所有关系构成幂集 P(A×B)\mathcal P(A\times B)。因此,如果 AA 和 BB 分别有 mm 个和 nn 个元素,就有 2mn2^{mn} 个可能的关系:每个可能的有序对都可以包含在关系中,也可以不包含在其中。(ocw.mit.edu)

集合上关系的性质

关系 R⊆A×AR\subseteq A\times A 可以按以下性质分类:

  • 自反性: 对每个 a∈Aa\in A,都有 aRaaRa。
  • 反自反性: 对任何 a∈Aa\in A,aRaaRa 都不成立。
  • 对称性: 若 aRbaRb,则 bRabRa。
  • 反对称性: 若 aRbaRb 与 bRabRa 同时成立,则 a=ba=b。
  • 非对称性: 若 aRbaRb,则 bRabRa 不成立。
  • 传递性: 若 aRbaRb 且 bRcbRc,则 aRcaRc。(cs.cornell.edu)

反对称性并不是对称性的否定:它只禁止不同元素之间存在双向关联。非对称性还禁止元素与自身关联。例如,≤\leq 具有自反性、反对称性和传递性,而 << 具有反自反性、非对称性和传递性。相等关系既具有对称性,也具有反对称性。(cs.cornell.edu)

这些条件都采用全称量化,因此,缺少某些有序对并不一定违反这些条件。空关系具有对称性和传递性,因为相应条件的前提从不成立。在非空的底集上,空关系不具有自反性;但在空集上,自反性也因空真而成立。(cs.cornell.edu)

等价与序

等价关系具有自反性、对称性和传递性。它表达的是按某个选定标准来看相同,而不一定意味着对象本身完全相同。每个元素 aa 都确定一个等价类

[a]R={b∈A:aRb}.[a]_R=\{b\in A:aRb\}.

各个不同的等价类构成 AA 的一个集合划分:每个元素恰好属于一个等价类。这些等价类组成的集合就是商集 A/RA/R。(cs.cornell.edu)

例如,在整数上,被某个固定的正整数除后余数相同,是一种等价关系。它给出了模算术中使用的等价类。(cs.cornell.edu)

预序具有自反性和传递性。偏序还满足反对称性。如果任意两个元素都可比较,即 aRbaRb 或 bRabRa,那么它就是全序。偏序允许存在不可比较的元素,集合的包含关系就是一个例子。严格偏序具有反自反性和传递性。(cs.cornell.edu)

关系的运算

由于关系是集合,同一个笛卡尔积中的关系可以进行并、交、差运算,以及相对于该笛卡尔积的补运算。并集包含属于任一关系的有序对;交集包含同时属于两个关系的有序对。逆关系将每个有序对的次序颠倒:

R−1={(b,a):(a,b)∈R}.R^{-1}=\{(b,a):(a,b)\in R\}.

这一记号并不意味着 RR 是可逆函数。(cs.cornell.edu)

对于 R⊆A×BR\subseteq A\times B 和 S⊆B×CS\subseteq B\times C,关系复合通过一个中间元素将元素关联起来:

S∘R={(a,c):∃b∈B, aRb 且 bSc}.S\circ R=\{(a,c):\exists b\in B,\ aRb\text{ 且 }bSc\}.

这里先应用 RR,遵循函数复合的惯例;有些文献采用相反的顺序。复合满足结合律,但通常不满足交换律。恒等关系 IA={(a,a):a∈A}I_A=\{(a,a):a\in A\} 是相应复合运算的单位元。(cs.cornell.edu)

图、闭包与计算

集合 AA 上的关系可以用有向图表示:元素对应顶点,每个有序对 (a,b)(a,b) 对应一条箭头 a→ba\to b。自反性要求每个顶点都有自环;对称性要求每条箭头都有一条反向箭头;传递性要求,只要两条首尾相接的箭头形成一条路径,这条路径的起点和终点之间就必须有一条直接相连的箭头。(cs.cornell.edu)

传递闭包 R+R^+ 恰好补入所有通过一步或多步关系连接起来的有序对。自反传递闭包 R∗R^* 还允许零步:

R+=⋃n≥1Rn,R∗=⋃n≥0Rn,R0=IA.R^+=\bigcup_{n\geq1}R^n,\qquad R^*=\bigcup_{n\geq0}R^n,\qquad R^0=I_A.

它们分别是包含 RR 的最小传递关系和最小自反传递关系。(cs.cornell.edu)

在形式验证中,程序可以被解释为初始状态与最终状态之间的关系。复合用于建模顺序执行,自反传递闭包则用于建模任意次数的重复执行,包括零次。这种解释不仅适用于确定性函数,也能涵盖具有多种可能结果的计算。(cs.cornell.edu)

参考来源

  1. ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_04…ocw.mit.edu
  2. cs.cornell.edu/courses/cs6861/2025fa/handouts/ka-book.pdfcs.cornell.edu
  3. cs.cornell.edu/courses/cs2800/2017sp/lectures/lec06-relations.htmlcs.cornell.edu
  4. cs.cornell.edu/courses/cs4160/2020sp/sf/lf/full/Rel.htmlcs.cornell.edu
  5. cs.cornell.edu/courses/cs2800/2017sp/lectures/lec07-equivalence.htmlcs.cornell.edu
  6. cs.cornell.edu/courses/cs6860/2019sp/Handouts/HKT1-3.pdfcs.cornell.edu