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

传递关系

传递关系是一种二元关系:若第一元素与第二元素、第二元素与第三元素有此关系,则第一元素与第三元素也有此关系。

18 个关键词2 个词条链接到这里1 个尚未撰写AI 撰写
二元关系笛卡尔积一阶逻辑实数整数模算术空集等价关系传递关系

传递关系是集合 AA 上的二元关系 RR,满足:只要 aRbaRb 且 bRcbRc,就有 aRcaRc。这里,aRbaRb 表示有序对 (a,b)(a,b) 属于 RR。传递性是定义序关系和等价关系的性质之一,也是对比较链、蕴涵链和可达性进行推理的基础。

定义

形式上,关系 R⊆A×AR\subseteq A\times A 具有传递性,是指

∀a,b,c∈A,(aRb∧bRc)⟹aRc.\forall a,b,c\in A,\qquad (aRb\land bRc)\Longrightarrow aRc.

其中,A×AA\times A 是 AA 与自身的笛卡尔积。

这是一阶逻辑中的一个全称量化条件。它必须对 a,b,ca,b,c 的每一种取值都成立;这些元素不必互不相同。

传递性也可以用关系的复合来表示。定义

R∘R={(a,c)∈A×A:there exists b∈A with aRb and bRc}.R\circ R = \{(a,c)\in A\times A: \text{there exists }b\in A \text{ with }aRb\text{ and }bRc\}.

则有

R is transitive⟺R∘R⊆R.R\text{ is transitive} \quad\Longleftrightarrow\quad R\circ R\subseteq R.

这里的包含关系不一定是相等关系。例如,在两个不同元素组成的集合上,关系 R={(a,b)}R=\{(a,b)\} 具有传递性,但 R∘RR\circ R 为空。

例子与反例

许多常见的数学关系都具有传递性:

  • **相等关系:**若 a=ba=b 且 b=cb=c,则 a=ca=c。
  • 数的大小关系:实数上的 << 和 ≤\leq 都具有传递性。
  • **集合包含关系:**若 A⊆BA\subseteq B 且 B⊆CB\subseteq C,则 A⊆CA\subseteq C。因此,包含关系在任意一族集合上都定义了一个传递关系。
  • **整除关系:**在正整数上,若 a∣ba\mid b 且 b∣cb\mid c,则 a∣ca\mid c。事实上,写成 b=akb=ak 和 c=bℓc=b\ell,便有 c=a(kℓ)c=a(k\ell)。
  • **同余关系:**对于固定的正整数 nn,若 a≡b(modn)a\equiv b\pmod n 且 b≡c(modn)b\equiv c\pmod n,则 a≡c(modn)a\equiv c\pmod n。这是模算术中的一种基本关系。

另有许多关系不具有传递性:

  • 不等关系:1≠21\ne2 且 2≠12\ne1,但 1≠11\ne1 不成立。这说明了为什么检验定义时必须考虑元素重复出现的情况。
  • **“是……的父亲或母亲”关系:**一个人的父母的父母,并不因此就是这个人的父母。相比之下,“是……的祖先”这一关系具有传递性。
  • **距离小于某个固定值的关系:**在实数轴上,以 ∣x−y∣<1|x-y|<1 定义 xRyxRy。此时 0R0.750R0.75 且 0.75R1.50.75R1.5,但 0R1.50R1.5 不成立。
  • **有公共元素的关系:**两个集合可能相交,第二个集合也可能与第三个集合相交,但第一个集合与第三个集合却不相交。

要否定传递性,只需找出一个三元组,使 aRbaRb 和 bRcbRc 成立,而 aRcaRc 不成立。

空真传递性与非传递性

即使一个关系中不存在由两个首尾相接的关系对组成的链,它仍然可以具有传递性。在这种情况下,前提 aRb∧bRcaRb\land bRc 永远不成立,因此定义中的蕴涵式空真。所以,空关系在任意集合上都具有传递性。

需要区分关系不具有传递性与关系具有反传递性这两种情况。反传递性是指

∀a,b,c∈A,(aRb∧bRc)⟹¬aRc.\forall a,b,c\in A,\qquad (aRb\land bRc)\Longrightarrow \neg aRc.

不具有传递性只要求存在至少一个反例;反传递性则要求每一条两步链的两个端点都不具有该关系。一个关系中可能既有端点具有该关系的链,也有端点不具有该关系的链,因此它既不具有传递性,也不具有反传递性。

英文术语 intransitive 有时表示不具有传递性,有时则表示更强的反传递性,因此使用时必须确认其具体含义。对于不存在两步链的关系,传递性和反传递性都空真成立。

与其他关系性质的联系

传递性不同于自反性、对称性和反对称性:

  • **自反性:**对每个 aa,都有 aRaaRa。
  • **对称性:**由 aRbaRb 可推出 bRabRa。
  • **反对称性:**由 aRbaRb 和 bRabRa 同时成立可推出 a=ba=b。
  • **反自反性:**不存在使 aRaaRa 成立的 aa。

这些性质的不同组合定义了若干重要的关系类型。

等价关系

等价关系具有自反性、对称性和传递性。传递性保证了通过中间的等价元素联系起来的元素彼此也等价。这些性质共同将一个集合划分为互不相交的等价类。

仅凭对称性和传递性,并不能推出关系在整个底集上具有自反性。不过,对于任何出现在关系对中的元素 aa,这两个性质确实能推出 aRaaRa:由 aRbaRb,利用对称性得到 bRabRa,再利用传递性得到 aRaaRa。

序与预序

偏序具有自反性、反对称性和传递性。集合包含关系和正整数上的整除关系都是典型例子。

预序具有自反性和传递性,但不一定具有反对称性。对于预序 RR,定义

a∼b⟺aRb and bRa.a\sim b \quad\Longleftrightarrow\quad aRb\text{ and }bRa.

则 ∼\sim 是一个等价关系。规则

[a]⪯[b]⟺aRb[a]\preceq[b] \quad\Longleftrightarrow\quad aRb

在其等价类上定义了一个良定义的偏序。

严格偏序具有反自反性和传递性。这两个性质蕴含非对称性:如果 aRbaRb 和 bRabRa 同时成立,那么传递性就会推出 aRaaRa,这与反自反性矛盾。

链与有向图

反复应用传递性,可以将两步条件推广到任意有限链。若 RR 具有传递性,且

a0Ra1,a1Ra2,…,an−1Ran,a_0Ra_1,\quad a_1Ra_2,\quad \ldots,\quad a_{n-1}Ra_n,

其中 n≥1n\geq1,则 a0Rana_0Ra_n。这可以通过数学归纳法证明。

在图论中,一个关系可以用有向图表示:顶点为 AA 的元素,每当 aRbaRb 时,就有一条从 aa 指向 bb 的边。关系具有传递性,当且仅当每条长度为二的有向游走,都有一条从其起点直接指向其终点的边。等价地,每条长度为正的有限有向游走都有这样一条边。

因此,如果一个传递关系包含有向环,那么该环的每个顶点上都必须有自环。反自反的传递关系不可能包含有向环。

传递闭包

RR 的传递闭包通常记为 R+R^+,它是包含 RR 的最小传递关系。定义 R1=RR^1=R,并令 RnR^n 由恰好通过 nn 步链相连的元素对组成。则

R+=⋃n=1∞Rn.R^+=\bigcup_{n=1}^{\infty}R^n.

因此,aR+baR^+b 表示从 aa 出发,经过有限个且至少一个 RR-步可以到达 bb。

自反传递闭包还包含每个恒等对:

R∗=IA∪R+,IA={(a,a):a∈A}.R^*=I_A\cup R^+, \qquad I_A=\{(a,a):a\in A\}.

它允许长度为零的路径,而 R+R^+ 不允许。不过,当 RR 中存在环时,R+R^+ 仍可能包含恒等对。

例如,若

R={(a,b),(b,c)},R=\{(a,b),(b,c)\},

则

R+={(a,b),(b,c),(a,c)}.R^+=\{(a,b),(b,c),(a,c)\}.

传递闭包可用于计算可达性、间接依赖关系,以及反复应用一个关系所能得到的结果。

矩阵表示与计算

对于有限集 A={a1,…,an}A=\{a_1,\ldots,a_n\},可以用邻接矩阵 MM 表示 RR:当 aiRaja_iRa_j 时,Mij=1M_{ij}=1;否则 Mij=0M_{ij}=0。

利用布尔矩阵乘法,定义

(M⊙M)ij=⋁k=1n(Mik∧Mkj).(M\odot M)_{ij} = \bigvee_{k=1}^{n} (M_{ik}\land M_{kj}).

该矩阵元素为 11,当且仅当存在一条从 aia_i 到 aja_j 的两步路径。因此,

R is transitive⟺M⊙M≤M,R\text{ is transitive} \quad\Longleftrightarrow\quad M\odot M\leq M,

其中,不等式按对应元素逐一比较。

直接检验所有三元组的方法需要 O(n3)O(n^3) 时间,这里使用的是大O记号。Warshall 算法依次允许每个顶点作为中间点,同样可以在 O(n3)O(n^3) 时间内计算传递闭包。

保持传递性的运算

以下几种运算保持传递性:

  • **交集:**同一集合上的任意非空族传递关系,其交集仍具有传递性。
  • **逆关系:**若 RR 具有传递性,则其逆关系 R−1R^{-1} 也具有传递性,其中 aR−1baR^{-1}b 当且仅当 bRabRa。
  • **限制:**若 B⊆AB\subseteq A,则只要 RR 具有传递性,R∩(B×B)R\cap(B\times B) 就具有传递性。

并集通常不保持传递性。对于互不相同的 a,b,ca,b,c,{(a,b)}\{(a,b)\} 和 {(b,c)}\{(b,c)\} 都具有传递性,但它们的并集不具有传递性,因为其中缺少 (a,c)(a,c)。任意删除关系对同样可能破坏传递性:删除 (a,c)(a,c),同时保留 (a,b)(a,b) 和 (b,c)(b,c),就会产生一个反例。