传递关系

本词条由K先生翻译。 此词条暂由彩云小译翻译。

 --小趣木木（讨论）英文译文缺失 需要补充

In mathematics, a homogeneous relation R over a set X is transitive if for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive.

In mathematics, a homogeneous relation R over a set X is transitive if for all elements a, b, c in X, whenever R relates a to b and b to c, then R also relates a to c. Each partial order as well as each equivalence relation needs to be transitive.

在数学上，若对于某个集合X中的所有元素a,b,c而言，每当齐次关系R将a与b，b与c建立联系时，R也将a与c联系起来，称集合X中的R是可传递的，每个偏序和每个等价关系都需要是可传递的。

== Definition ==

定义

A homogeneous relation R on the set X is a transitive relation if,

A homogeneous relation R on the set X is a transitive relation if,

一个集合X中的齐次关系R,其传递关系是不确定的，

for all a, b, c ∈ X, if a R b and b R c, then a R c.

for all a, b, c ∈ X, if a R b and b R c, then a R c.

对所有元素a，b，c ∈ X来说，如果存在a R b和b R c，那么就有a R c。

Or in terms of first-order logic:

Or in terms of first-order logic:

或者按照一阶逻辑:

[math]\displaystyle{ \forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, }[/math]

[math]\displaystyle{ \forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, }[/math]

where a R b is the infix notation for (a, b) ∈ R.

where a R b is the infix notation for (a, b) ∈ R.

其中，对于(a, b) ∈ R，a R b是其中缀表示法。

==Examples==

例子

As a nonmathematical example, the relation "is an ancestor of" is transitive. For example, if Amy is an ancestor of Becky, and Becky is an ancestor of Carrie, then Amy, too, is an ancestor of Carrie.

As a nonmathematical example, the relation "is an ancestor of" is transitive. For example, if Amy is an ancestor of Becky, and Becky is an ancestor of Carrie, then Amy, too, is an ancestor of Carrie.

一个非数学的例子，关系“谁是谁的祖先”就是一种传递关系。例如，如果Amy是Becky的祖先，而Becky是Carrie的祖先，那么Amy也是Carrie的祖先。

On the other hand, "is the birth parent of" is not a transitive relation, because if Alice is the birth parent of Brenda, and Brenda is the birth parent of Claire, then Alice is not the birth parent of Claire. What is more, it is antitransitive: Alice can never be the birth parent of Claire.

On the other hand, "is the birth parent of" is not a transitive relation, because if Alice is the birth parent of Brenda, and Brenda is the birth parent of Claire, then Alice is not the birth parent of Claire. What is more, it is antitransitive: Alice can never be the birth parent of Claire.

另一方面，“谁是谁的亲生父母” 不是一个传递关系，因为如果 Alice 是 Brenda 的亲身父母，而 Brenda 是 Claire 的亲身父母，那么 Alice 不会是 Claire 的亲身父母。更重要的是，它是一种反传递关系: Alice 永远不可能是 Claire 的亲身父母。

 --小趣木木（讨论）亲身父母  亲生父母

"Is greater than", "is at least as great as", and "is equal to" (equality) are transitive relations on various sets, for instance, the set of real numbers or the set of natural numbers:

"Is greater than", "is at least as great as", and "is equal to" (equality) are transitive relations on various sets, for instance, the set of real numbers or the set of natural numbers:

“ 大于”、“大于等于”和“ 等于”(相等关系)是各种集合上的传递关系，例如实数集合或自然数集合:

whenever x > y and y > z, then also x > z

whenever x > y and y > z, then also x > z

只要 x > y 且 y > z，那么 x > z

whenever x ≥ y and y ≥ z, then also x ≥ z

whenever x ≥ y and y ≥ z, then also x ≥ z

只要 x ≥y 且 y ≥ z，那么 x ≥ z

whenever x = y and y = z, then also x = z.

whenever x = y and y = z, then also x = z.

只要 x = y，y = z，那么 x = z。

More examples of transitive relations:

More examples of transitive relations:

更多传递关系的例子:

• "is a subset of" (set inclusion, a relation on sets)

"is a subset of" (set inclusion, a relation on sets) “XX是XX的子集”（集合里的包含关系，属于一种集合上的关系）

• "divides" (divisibility, a relation on natural numbers)

"divides" (divisibility, a relation on natural numbers) “除以”（可除性，一种自然数里的关系）

• "implies" (implication, symbolized by "⇒", a relation on propositions)

"implies" (implication, symbolized by "⇒", a relation on propositions) “必然包含”(涵盖，推出，用“⇒”表示，一种命题里的关系)

Examples of non-transitive relations:

Examples of non-transitive relations:

不是传递关系的例子:

• "is the successor of" (a relation on natural numbers)

"is the successor of" (a relation on natural numbers) “XX是XX的后继数”（一种自然数里的关系）

• "is a member of the set" (symbolized as "∈")

"is a member of the set" (symbolized as "∈") “XX是集合里的元素”（用“∈”表示）

• "is perpendicular to" (a relation on lines in Euclidean geometry)

"is perpendicular to" (a relation on lines in Euclidean geometry) “垂直于”（一种欧几里得几何中的线关系）

The empty relation on any set [math]\displaystyle{ X }[/math] is transitive because there are no elements [math]\displaystyle{ a,b,c \in X }[/math] such that [math]\displaystyle{ aRb }[/math] and [math]\displaystyle{ bRc }[/math], and hence the transitivity condition is vacuously true. A relation R containing only one ordered pair is also transitive: if the ordered pair is of the form [math]\displaystyle{ (x, x) }[/math] for some [math]\displaystyle{ x \in X }[/math] the only such elements [math]\displaystyle{ a,b,c \in X }[/math] are [math]\displaystyle{ a=b=c=x }[/math], and indeed in this case [math]\displaystyle{ aRc }[/math], while if the ordered pair is not of the form [math]\displaystyle{ (x, x) }[/math] then there are no such elements [math]\displaystyle{ a,b,c \in X }[/math] and hence [math]\displaystyle{ R }[/math] is vacuously transitive.

The empty relation on any set [math]\displaystyle{ X }[/math] is transitive because there are no elements [math]\displaystyle{ a,b,c \in X }[/math] such that [math]\displaystyle{ aRb }[/math] and [math]\displaystyle{ bRc }[/math], and hence the transitivity condition is vacuously true. A relation containing only one ordered pair is also transitive: if the ordered pair is of the form [math]\displaystyle{ (x, x) }[/math] for some [math]\displaystyle{ x \in X }[/math] the only such elements [math]\displaystyle{ a,b,c \in X }[/math] are [math]\displaystyle{ a=b=c=x }[/math], and indeed in this case [math]\displaystyle{ aRc }[/math], while if the ordered pair is not of the form [math]\displaystyle{ (x, x) }[/math] then there are no such elements [math]\displaystyle{ a,b,c \in X }[/math] and hence [math]\displaystyle{ R }[/math] is vacuously transitive.

任何集合上的空关系是可传递的，因为没有元素a，b，c ∈ X使得满足a R b和b R c的条件，因此空关系的可传递性为真。仅包含一个有序对的关系也是可传递的：若对于x∈X,有序对的形式是（x,x）,只有这样的元素a，b，c ∈ X满足a=b=c=x时，在这种情况下确实有a R c，但是当有序对的形式不是（x,x），那么存在这样的元素a，b，c ∈ X，因此R是空传递的。

== Properties ==

性质

=== Closure properties ===

闭包性

• The inverse (converse) of a transitive relation is always transitive. For instance, knowing that "is a subset of" is transitive and "is a superset of" is its inverse, one can conclude that the latter is transitive as well.

The inverse (converse) of a transitive relation is always transitive. For instance, knowing that "is a subset of" is transitive and "is a superset of" is its inverse, one can conclude that the latter is transitive as well. 传递关系的逆命题总是可传递的。例如，我们知道“XX是XX的一个子集”是可传递的，其逆命题是“XX是XX的一个超集”，则可得到该命题也是可传递的。

• The intersection of two transitive relations is always transitive. For instance, knowing that "was born before" and "has the same first name as" are transitive, one can conclude that "was born before and also has the same first name as" is also transitive.

两个传递关系的交集总是可传递的。例如，我们知道“出生于...之前”的关系和“与...同名”的关系是可传递的，则可得到“既出生于...之前又与...同名”的关系也是可传递的。

 --小趣木木（讨论）例如，“孔子早于孟子，孟子早于苟子，所以，孔子早于苟子。”传递关系推理是一种有效推理。如果其前提为真，那么其结论也必然真；这里的“出生于...之前”的关系和“与...同名”的关系 或许可以根据这个理解重新组织一下语言

• The union of two transitive relations need not be transitive. For instance, "was born before or has the same first name as" is not a transitive relation, since e.g. Herbert Hoover is related to Franklin D. Roosevelt, which is in turn related to Franklin Pierce, while Hoover is not related to Franklin Pierce.

The union of two transitive relations need not be transitive. For instance, "was born before or has the same first name as" is not a transitive relation, since e.g. Herbert Hoover is related to Franklin D. Roosevelt, which is in turn related to Franklin Pierce, while Hoover is not related to Franklin Pierce. 两个传递关系的并集不一定是可传递的。例如，“出生于...之前或与...同名”的关系就不是可传递的，因为如，Herbert Hoover与Franklin D. Roosevelt有亲属关系，而Franklin D. Roosevelt与 Franklin Pierce有亲属关系，但是Herbert Hoover与Franklin Pierce没有亲属关系。

• The complement of a transitive relation need not be transitive. For instance, while "equal to" is transitive, "not equal to" is only transitive on sets with at most one element.

传递关系的补集不一定是可传递的。例如，尽管“等于”关系是可传递的，但是“不等于”关系仅在最多只有一个元素的集合中是可传递的。

=== Other properties ===

其他性质

A transitive relation is asymmetric if and only if it is irreflexive.

A transitive relation is asymmetric if and only if it is irreflexive.

当且仅当传递关系具有反自反性时，它具有反对称性。

A transitive relation need not be reflexive. When it is, it is called a preorder. For example, on set X = {1,2,3}:

A transitive relation need not be reflexive. When it is, it is called a preorder. For example, on set X = {1,2,3}:

传递关系不一定具有自反性。当传递关系具有自反性时，它被称为一个预序。例如，集合 X= {1,2,3}:

• R = {模板:Hair space(1,1), (2,2), (3,3), (1,3), (3,2)模板:Hair space} is reflexive, but not transitive, as the pair (1,2) is absent,
  
• R = {(1,1),(2,2),(3,3),(1,3),(3,2)}具有自反性，但不是可传递的，因为缺失(1,2)，

• R = {模板:Hair space(1,1), (2,2), (3,3), (1,3)模板:Hair space} is reflexive as well as transitive, so it is a preorder,
  
• R = {(1,1),(2,2),(3,3),(1,3)}同时具有自反性和传递性，所以它是一个预序，

• R = {模板:Hair space(1,1), (2,2), (3,3)模板:Hair space} is reflexive as well as transitive, another preorder.
  
• R = {(1,1),(2,2),(3,3)}也具有自反性和传递性，所以它是另一个预序。

==Transitive extensions and transitive closure==

传递扩展和传递闭包

Main article: Transitive closure

Let R be a binary relation on set X. The transitive extension of R, denoted R₁, is the smallest binary relation on X such that R₁ contains R, and if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R₁. For example, suppose X is a set of towns, some of which are connected by roads. Let R be the relation on towns where (A, B) ∈ R if there is a road directly linking town A and town B. This relation need not be transitive. The transitive extension of this relation can be defined by (A, C) ∈ R₁ if you can travel between towns A and C by using at most two roads.

Let R be a binary relation on set X. The transitive extension of R, denoted R1, is the smallest binary relation on X such that R1 contains R, and if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R1.[6] For example, suppose X is a set of towns, some of which are connected by roads. Let R be the relation on towns where (A, B) ∈ R if there is a road directly linking town A and town B. This relation need not be transitive. The transitive extension of this relation can be defined by (A, C) ∈ R1 if you can travel between towns A and C by using at most two roads.

Let be a binary relation on set . The transitive extension of , denoted , is the smallest binary relation on such that contains , and if and then . For example, suppose is a set of towns, some of which are connected by roads. Let be the relation on towns where if there is a road directly linking town and town . This relation need not be transitive. The transitive extension of this relation can be defined by if you can travel between towns and by using at most two roads.

设R是集合X上的一个二元关系。R,的传递扩展，用 R1表示，是在X上最小的二元关系以至于R1包含R,，并且如果(a, b) ∈ R，(b, c) ∈ R,那么(a, c) ∈ R1。例如，假设X是一组城镇，其中一些城镇通过公路相连。设R表示城镇上的关系，存在（A，B）∈R，若有一条公路直接连接城镇A和城镇B，则该关系不一定是可传递的。若最多仅有两条公路连接城镇A和城镇C，这种关系的传递扩展可以用（A，C）∈R1来定义。

If a relation is transitive then its transitive extension is itself, that is, if R is a transitive relation then R₁ = R.

If a relation is transitive then its transitive extension is itself, that is, if is a transitive relation then . If a relation is transitive then its transitive extension is itself, that is, if R is a transitive relation then R1 = R. 如果一个关系是可传递的，那么它的传递扩展是它本身，即若R是一个传递关系，那么有 R1 = R.

The transitive extension of R₁ would be denoted by R₂, and continuing in this way, in general, the transitive extension of R_i would be R_{i + 1}. The transitive closure of R, denoted by R* or R^∞ is the set union of R, R₁, R₂, ... .

The transitive extension of would be denoted by , and continuing in this way, in general, the transitive extension of would be . The transitive closure of , denoted by or is the set union of , , , ... . The transitive extension of R1 would be denoted by R2, and continuing in this way, in general, the transitive extension of Ri would be Ri + 1. The transitive closure of R, denoted by R* or R∞ is the set union of R, R1, R2, ... . R1的传递扩展可以用R2来表示，并以这种方式继续下去，一般来说，Ri的传递扩展是Ri+1。R的传递闭包用 R* 或R∞来表示，它是 R, R1, R2, ...的集合。

The transitive closure of a relation is a transitive relation.

The transitive closure of a relation is a transitive relation. However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words, equivalence relations – , those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also.

关系的传递闭包是传递关系。然而，有一个公式可以计算同时具有自反性、对称性和传递性的关系的数量——换句话说，即等价关系——具有对称性和传递性的关系，具有对称性、传递性和反对称性的关系，具有完全性、传递性和反对称性的关系。Pfeiffer 已经在这个方向上取得了一些进展，通过结合这些性质表示相互之间的关系，但是仍然很难计算。请参见。

The relation "is the birth parent of" on a set of people is not a transitive relation. However, in biology the need often arises to consider birth parenthood over an arbitrary number of generations: the relation "is a birth ancestor of" is a transitive relation and it is the transitive closure of the relation "is the birth parent of". 在一群人中的关系“XX是XX的亲生父母”不是一个传递关系。但是，生物学上，经常需要考虑任意多代人的亲生关系：关系“XX是XX的鼻祖”是一个传递关系，并且它是关系“XX是XX的亲生父母”的传递闭包。

  --小趣木木（讨论）鼻祖 祖先 可以统一一下

For the example of towns and roads above, (A, C) ∈ R* provided you can travel between towns A and C using any number of roads. 以上述城镇和公路为例，（A，C）∈R*的前提假设是你可以在城镇A和C之间的任意数量的公路上行驶。

The Rock–paper–scissors game is based on an intransitive and antitransitive relation "x beats y".
游戏石头-剪刀-布是基于一个非传递和反传递的关系“ x 胜过 y”。

== Relation properties that require transitivity ==

依赖传递性的关系性质

A relation R is called intransitive if it is not transitive, that is, if xRy and yRz, but not xRz, for some x, y, z.

如果关系 R 不是可传递的，则称之为非传递性，即对于某个 x，y，z而言，若存在 xRy 和 yRz ，而没有xRz，则称之为非传递性。

• Preorder – a reflexive transitive relation
• 预序 -一个具有自反性和传递性的关系

In contrast, a relation R is called antitransitive if xRy and yRz always implies that xRz does not hold.

相反，如果 xRy 和 yRz 总是表明 xRz 不成立，则关系R被称为具有反传递性。

• Partial order – an antisymmetric preorder

偏序-一个具有反对称性的预序

For example, the relation defined by xRy if xy is an even number is intransitive, but not antitransitive. The relation defined by xRy if x is even and y is odd is both transitive and antitransitive.

例如，如果 xy 是偶数，由 xRy 定义的关系具有非传递性，而不是反传递性。如果 x 是偶数，y 是奇数，则 xRy 定义的关系既具有传递性又具有反传递性。

• Total preorder – a total preorder

总预序-一个总预序 The relation defined by xRy if x is the successor number of y is both intransitive and antitransitive. Unexpected examples of intransitivity arise in situations such as political questions or group preferences.

如果 x 是 y 的后继数，则 xRy 定义的关系既具有非传递性，又具有反传递性。非传递性的例外出现在政治问题或群体偏好等情况中。

• Equivalence relation – a symmetric preorder

等价关系-一个对称的预序

• Strict weak ordering – a strict partial order in which incomparability is an equivalence relation

严格弱序–一种严格的偏序，其中不可比性是一种等价关系 Generalized to stochastic versions (stochastic transitivity), the study of transitivity finds applications of in decision theory, psychometrics and utility models.

将传递性的研究推广到随机版本（随机传递性），在决策理论、心理测量学和效用模型中都有应用。

• Total ordering – a total, antisymmetric transitive relation

总序-一个具有完全性、反对称性和传递性的关系

A quasitransitive relation is another generalization; it is required to be transitive only on its non-symmetric part. Such relations are used in social choice theory or microeconomics.

（传递性研究的）另一种推广是拟传递关系，它只要求在它的非对称部分是可传递的。这种关系被用于社会选择理论或微观经济学当中。

==Counting transitive relations==

计算传递关系

No general formula that counts the number of transitive relations on a finite set 模板:OEIS is known. However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words, equivalence relations – 模板:OEIS, those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also. 模板:Number of relations

No general formula that counts the number of transitive relations on a finite set (sequence A006905 in the OEIS) is known.[8] However, there is a formula for finding the number of relations that are simultaneously reflexive, symmetric, and transitive – in other words, equivalence relations – (sequence A000110 in the OEIS), those that are symmetric and transitive, those that are symmetric, transitive, and antisymmetric, and those that are total, transitive, and antisymmetric. Pfeiffer[9] has made some progress in this direction, expressing relations with combinations of these properties in terms of each other, but still calculating any one is difficult. See also.[10] 目前还没有计算有限集上传递关系数量的通用公式（OEIS中的序列A006905）。[8]但是，有一个公式可以用来计算同时具有自反性、对称性和传递性的关系数量——换句话说，即等价关系（OEIS中的序列A000110），具有对称性和传递性的关系，具有对称性、传递性和反对称性的关系，具有完全性、传递性和反对称性的关系。Pfeiffer 已经在这个方向上取得了一些进展，通过结合这些性质表示相互之间的关系，但是仍然很难计算。请参见[10]。

== Related properties ==

相关性质

文件:Rock-paper-scissors.svg

The Rock–paper–scissors game is based on an intransitive and antitransitive relation "x beats y".

A relation R is called intransitive if it is not transitive, that is, if xRy and yRz, but not xRz, for some x, y, z. A relation R is called intransitive if it is not transitive, that is, if xRy and yRz, but not xRz, for some x, y, z.

如果关系 R 不是可传递的，则称之为非传递性，即对于某个 x，y，z而言，若存在 xRy 和 yRz ，而没有xRz，则称之为非传递性。 In contrast, a relation R is called antitransitive if xRy and yRz always implies that xRz does not hold.

相反，如果 xRy 和 yRz 总是表明 xRz 不成立，则关系R被称为具有反传递性。 For example, the relation defined by xRy if xy is an even number is intransitive, but not antitransitive. The relation defined by xRy if x is even and y is odd is both transitive and antitransitive.

例如，如果 xy 是偶数，由 xRy 定义的关系具有非传递性，而不是反传递性。如果 x 是偶数，y 是奇数，则 xRy 定义的关系既具有传递性又具有反传递性。 The relation defined by xRy if x is the successor number of y is both intransitive and antitransitive. Unexpected examples of intransitivity arise in situations such as political questions or group preferences.

如果 x 是 y 的后继数，则 xRy 定义的关系既具有非传递性，又具有反传递性。非传递性的例外出现在政治问题或群体偏好等情况中。

Generalized to stochastic versions (stochastic transitivity), the study of transitivity finds applications of in decision theory, psychometrics and utility models.

将传递性的研究推广到随机版本（随机传递性），在决策理论、心理测量学和效用模型中都有应用。

A quasitransitive relation is another generalization; it is required to be transitive only on its non-symmetric part. Such relations are used in social choice theory or microeconomics.

（传递性研究的）另一种推广是拟传递关系，它只要求在它的非对称部分是可传递的。这种关系被用于社会选择理论或微观经济学当中。

==See also==

参见

• Transitive reduction
• 传递归约
• Nontransitive dice
• 非传递骰子
• Rational choice theory
• 理性选择理论
• Hypothetical syllogism — transitivity of the material conditional
• 假言推理-物质条件的传递三元组

Category:Elementary algebra 类别: 初等代数

This page was moved from wikipedia:en:Transitive relation. Its edit history can be viewed at 传递关系/edithistory