传递关系是集合 A 上的二元关系 R,满足:只要 aRb 且 bRc,就有 aRc。这里,aRb 表示有序对 (a,b) 属于 R。传递性是定义序关系和等价关系的性质之一,也是对比较链、蕴涵链和可达性进行推理的基础。
定义
形式上,关系 R⊆A×A 具有传递性,是指
∀a,b,c∈A,(aRb∧bRc)⟹aRc.
其中,A×A 是 A 与自身的笛卡尔积。
这是一阶逻辑中的一个全称量化条件。它必须对 a,b,c 的每一种取值都成立;这些元素不必互不相同。
传递性也可以用关系的复合来表示。定义
R∘R={(a,c)∈A×A:there exists b∈A with aRb and bRc}.
则有
R is transitive⟺R∘R⊆R.
这里的包含关系不一定是相等关系。例如,在两个不同元素组成的集合上,关系 R={(a,b)} 具有传递性,但 R∘R 为空。
例子与反例
许多常见的数学关系都具有传递性:
- **相等关系:**若 a=b 且 b=c,则 a=c。
- 数的大小关系:实数上的 < 和 ≤ 都具有传递性。
- **集合包含关系:**若 A⊆B 且 B⊆C,则 A⊆C。因此,包含关系在任意一族集合上都定义了一个传递关系。
- **整除关系:**在正整数上,若 a∣b 且 b∣c,则 a∣c。事实上,写成 b=ak 和 c=bℓ,便有 c=a(kℓ)。
- **同余关系:**对于固定的正整数 n,若 a≡b(modn) 且 b≡c(modn),则 a≡c(modn)。这是模算术中的一种基本关系。
另有许多关系不具有传递性:
- 不等关系:1=2 且 2=1,但 1=1 不成立。这说明了为什么检验定义时必须考虑元素重复出现的情况。
- **“是……的父亲或母亲”关系:**一个人的父母的父母,并不因此就是这个人的父母。相比之下,“是……的祖先”这一关系具有传递性。
- **距离小于某个固定值的关系:**在实数轴上,以 ∣x−y∣<1 定义 xRy。此时 0R0.75 且 0.75R1.5,但 0R1.5 不成立。
- **有公共元素的关系:**两个集合可能相交,第二个集合也可能与第三个集合相交,但第一个集合与第三个集合却不相交。
要否定传递性,只需找出一个三元组,使 aRb 和 bRc 成立,而 aRc 不成立。
空真传递性与非传递性
即使一个关系中不存在由两个首尾相接的关系对组成的链,它仍然可以具有传递性。在这种情况下,前提 aRb∧bRc 永远不成立,因此定义中的蕴涵式空真。所以,空关系在任意集合上都具有传递性。
需要区分关系不具有传递性与关系具有反传递性这两种情况。反传递性是指
∀a,b,c∈A,(aRb∧bRc)⟹¬aRc.
不具有传递性只要求存在至少一个反例;反传递性则要求每一条两步链的两个端点都不具有该关系。一个关系中可能既有端点具有该关系的链,也有端点不具有该关系的链,因此它既不具有传递性,也不具有反传递性。
英文术语 intransitive 有时表示不具有传递性,有时则表示更强的反传递性,因此使用时必须确认其具体含义。对于不存在两步链的关系,传递性和反传递性都空真成立。
与其他关系性质的联系
传递性不同于自反性、对称性和反对称性:
- **自反性:**对每个 a,都有 aRa。
- **对称性:**由 aRb 可推出 bRa。
- **反对称性:**由 aRb 和 bRa 同时成立可推出 a=b。
- **反自反性:**不存在使 aRa 成立的 a。
这些性质的不同组合定义了若干重要的关系类型。
等价关系
等价关系具有自反性、对称性和传递性。传递性保证了通过中间的等价元素联系起来的元素彼此也等价。这些性质共同将一个集合划分为互不相交的等价类。
仅凭对称性和传递性,并不能推出关系在整个底集上具有自反性。不过,对于任何出现在关系对中的元素 a,这两个性质确实能推出 aRa:由 aRb,利用对称性得到 bRa,再利用传递性得到 aRa。
序与预序
偏序具有自反性、反对称性和传递性。集合包含关系和正整数上的整除关系都是典型例子。
预序具有自反性和传递性,但不一定具有反对称性。对于预序 R,定义
a∼b⟺aRb and bRa.
则 ∼ 是一个等价关系。规则
[a]⪯[b]⟺aRb
在其等价类上定义了一个良定义的偏序。
严格偏序具有反自反性和传递性。这两个性质蕴含非对称性:如果 aRb 和 bRa 同时成立,那么传递性就会推出 aRa,这与反自反性矛盾。
链与有向图
反复应用传递性,可以将两步条件推广到任意有限链。若 R 具有传递性,且
a0Ra1,a1Ra2,…,an−1Ran,
其中 n≥1,则 a0Ran。这可以通过数学归纳法证明。
在图论中,一个关系可以用有向图表示:顶点为 A 的元素,每当 aRb 时,就有一条从 a 指向 b 的边。关系具有传递性,当且仅当每条长度为二的有向游走,都有一条从其起点直接指向其终点的边。等价地,每条长度为正的有限有向游走都有这样一条边。
因此,如果一个传递关系包含有向环,那么该环的每个顶点上都必须有自环。反自反的传递关系不可能包含有向环。
传递闭包
R 的传递闭包通常记为 R+,它是包含 R 的最小传递关系。定义 R1=R,并令 Rn 由恰好通过 n 步链相连的元素对组成。则
R+=n=1⋃∞Rn.
因此,aR+b 表示从 a 出发,经过有限个且至少一个 R-步可以到达 b。
自反传递闭包还包含每个恒等对:
R∗=IA∪R+,IA={(a,a):a∈A}.
它允许长度为零的路径,而 R+ 不允许。不过,当 R 中存在环时,R+ 仍可能包含恒等对。
例如,若
R={(a,b),(b,c)},
则
R+={(a,b),(b,c),(a,c)}.
传递闭包可用于计算可达性、间接依赖关系,以及反复应用一个关系所能得到的结果。
矩阵表示与计算
对于有限集 A={a1,…,an},可以用邻接矩阵 M 表示 R:当 aiRaj 时,Mij=1;否则 Mij=0。
利用布尔矩阵乘法,定义
(M⊙M)ij=k=1⋁n(Mik∧Mkj).
该矩阵元素为 1,当且仅当存在一条从 ai 到 aj 的两步路径。因此,
R is transitive⟺M⊙M≤M,
其中,不等式按对应元素逐一比较。
直接检验所有三元组的方法需要 O(n3) 时间,这里使用的是大O记号。Warshall 算法依次允许每个顶点作为中间点,同样可以在 O(n3) 时间内计算传递闭包。
保持传递性的运算
以下几种运算保持传递性:
- **交集:**同一集合上的任意非空族传递关系,其交集仍具有传递性。
- **逆关系:**若 R 具有传递性,则其逆关系 R−1 也具有传递性,其中 aR−1b 当且仅当 bRa。
- **限制:**若 B⊆A,则只要 R 具有传递性,R∩(B×B) 就具有传递性。
并集通常不保持传递性。对于互不相同的 a,b,c,{(a,b)} 和 {(b,c)} 都具有传递性,但它们的并集不具有传递性,因为其中缺少 (a,c)。任意删除关系对同样可能破坏传递性:删除 (a,c),同时保留 (a,b) 和 (b,c),就会产生一个反例。