# 传递关系

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


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.

== Definition ==

## 定义

A homogeneous relation R on the set X is a transitive relation if,[1] :for all a, b, cX, if a R b and b R c, then a R c.

A homogeneous relation R on the set X is a transitive relation if, for all a, b, c ∈ X, if a R b and b R c, then a R c.

Or in terms of first-order logic:

Or in terms of first-order logic:

$\displaystyle{ \forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, }$

$\displaystyle{ \forall a,b,c \in X: (aRb \wedge bRc) \Rightarrow aRc, }$

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

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

==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.

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.

"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


whenever xy and yz, then also xz
whenever x ≥ y and y ≥ z, then also x ≥ z


whenever x = y and y = z, then also x = z.
whenever x = y and y = z, then also 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) “除以”（可除性，一种自然数里的关系）

"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的 后继数（successor）（一种自然数里的关系）”

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

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

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

The empty relation on any set $\displaystyle{ X }$ is transitive[3][4] because there are no elements $\displaystyle{ a,b,c \in X }$ such that $\displaystyle{ aRb }$ and $\displaystyle{ bRc }$, 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 $\displaystyle{ (x, x) }$ for some $\displaystyle{ x \in X }$ the only such elements $\displaystyle{ a,b,c \in X }$ are $\displaystyle{ a=b=c=x }$, and indeed in this case $\displaystyle{ aRc }$, while if the ordered pair is not of the form $\displaystyle{ (x, x) }$ then there are no such elements $\displaystyle{ a,b,c \in X }$ and hence $\displaystyle{ R }$ is vacuously transitive.

The empty relation on any set $\displaystyle{ X }$ is transitive because there are no elements $\displaystyle{ a,b,c \in X }$ such that $\displaystyle{ aRb }$ and $\displaystyle{ bRc }$, 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 $\displaystyle{ (x, x) }$ for some $\displaystyle{ x \in X }$ the only such elements $\displaystyle{ a,b,c \in X }$ are $\displaystyle{ a=b=c=x }$, and indeed in this case $\displaystyle{ aRc }$, while if the ordered pair is not of the form $\displaystyle{ (x, x) }$ then there are no such elements $\displaystyle{ a,b,c \in X }$ and hence $\displaystyle{ R }$ is vacuously transitive.

== 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.[5]

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}:

• 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==

## 传递扩展和传递闭包

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 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.

R是集合X上的一个二元关系。R, 传递扩展（transitive extension），用 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 R1 = R.

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 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, ... .[7]

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.[7]

The transitive closure of a relation is a transitive relation.

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的亲生父母”的 传递闭包

  --小趣木木（讨论）鼻祖 祖先 可以统一一下
==K先生（讨论）[翻译] 讨论: 因为这里是birth ancestor，前面是ancestor，所以翻译成了鼻祖和祖先，不一样的。


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".
[[游戏石头-剪刀-布是基于一个 非传递和反传递的关系（intransitive and antitransitive relation）“ 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.

 预序-一个具有自反性的 传递关系


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

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.

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

==Counting transitive relations==

## 计算传递关系

No general formula that counts the number of transitive relations on a finite set 模板: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 – 模板: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] 模板: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 ==

## 相关性质

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.

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

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.[18]

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

## 参见

Category:Elementary algebra 类别: 初等代数

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

1. 脚本错误：没有“Footnotes”这个模块。
2. However, the class of von Neumann ordinals is constructed in a way such that ∈ is transitive when restricted to that class.
3. 脚本错误：没有“Footnotes”这个模块。
4. https://courses.engr.illinois.edu/cs173/sp2011/Lectures/relations.pdf
5. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I. Prague: School of Mathematics - Physics Charles University. p. 1. Archived from the original on 2013-11-02.  Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".
6. 脚本错误：没有“Footnotes”这个模块。
7. 脚本错误：没有“Footnotes”这个模块。
8. Steven R. Finch, "Transitive relations, topologies and partial orders", 2003.
9. Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
10. Gunnar Brinkmann and Brendan D. McKay,"Counting unlabelled topologies and transitive relations"
11. since e.g. 3R4 and 4R5, but not 3R5
12. since e.g. 2R3 and 3R4 and 2R4
13. since xRy and yRz can never happen
14. since e.g. 3R2 and 2R1, but not 3R1
15. since, more generally, xRy and yRz implies x=y+1=z+2≠z+1, i.e. not xRz, for all x, y, z
16. Drum, Kevin (November 2018). "Preferences are not transitive". Mother Jones. Retrieved 2018-11-29.
17. Oliveira, I.F.D.; Zehavi, S.; Davidov, O. (August 2018). "Stochastic transitivity: Axioms and models". Journal of Mathematical Psychology. 85: 25–35. doi:10.1016/j.jmp.2018.06.002. ISSN 0022-2496.
18. Sen, A. (1969). "Quasi-transitivity, rational choice and collective decisions". Rev. Econ. Stud. 36 (3): 381–393. doi:10.2307/2296434. JSTOR 2296434. Zbl 0181.47302.