Transitive relation in mathematics

Lecture

In mathematics, a binary relation R on a set X is transitive if for all elements a , b , c of X , if R relates a to b and b to c , then R also relates a to c .

Any partial ordering and any equivalence relation are transitive. For example, the relations «less than» and «equality» among real numbers are transitive: if a < b and b < c , then a < c ; and if x = y and y = z , then x = z .

Definition

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

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

Or, in the language of first-order logic :

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

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

Examples

As a non-mathematical 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 is also an ancestor of Carrie.

On the other hand, the relation «is the biological mother of» is not transitive, because if Alice is the biological mother of Brenda, and Brenda is the biological mother of Claire, then it does not follow that Alice is the biological mother of Claire. In fact, this relation is antitransitive : Alice can never be the biological mother of Claire.

Relations that are neither transitive nor antitransitive include sporting competitions (playoff schedules), «knows» and «talks to».

The examples «greater than», «at least as great as» and «equal to» ( equality ) are transitive relations on various sets. For example, the set of real numbers or the set of natural numbers:

If x > y and y > z , then also x > z.

If x ≥ y and y ≥ z , then also x ≥ z.

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

A few more examples of transitive relations:

«is a subset of» (set inclusion, a relation on sets)
«divides» ( divisibility , a relation on natural numbers)
"implies" ( implication , denoted by the symbol "⇒", a relation on propositions )

Examples of non-transitive relations:

«is a successor of» (a relation on natural numbers)
«is a member of the set» (denoted as «∈») ^{[ 2 ]}
" perpendicular " (a relation between lines and lines in Euclidean geometry )

The empty relation on any set $X$ $X$ is transitive ^{[ 3 ]} , because there are no elements $a, b, c \in X$ $a,b,c\in X$ such that $a R b$ $aRb$ and $b R c$ $bRc$ Therefore, the transitivity condition is vacuously satisfied. A relation R, containing only one ordered pair , is also transitive: if the ordered pair has the form $(x, x)$ $(x,x)$ for some $x \in X$ $x\in X$ the only such elements $a, b, c \in X$ $a,b,c\in X$ are $a = b = c = x$ $a=b=c=x$ and indeed in this case $a R c$ $aRc$ , whereas if the ordered pair does not have the form $(x, x)$ $(x,x)$ then no such elements exist. $a, b, c \in X$ $a,b,c\in X$ and, consequently $R$ $R$ is vacuously transitive.

Vacuous transitivity — is transitivity when the relation lacks ordered pairs of the form ( a , b ) and ( b , c ).

Properties

Closure properties

The converse (inverse) of a transitive relation is always transitive. For example, knowing that «is a subset of» is transitive, and «is a superset of» — is its converse, one can conclude that the latter is also transitive.
The intersection of two transitive relations is always transitive. ^{[ 4 ]} For example, knowing that «was born before» and «has the same name as» are transitive, one can conclude that «was born before and also has the same name as» is also transitive.
The union of two transitive relations need not be transitive. For example, «was born before or has the same name as» is not a transitive relation, since, for example, Herbert Hoover is a relative of Franklin D. Roosevelt , who, in turn, is a relative of Franklin Pierce , while Hoover is not a relative of Franklin Pierce.
The complement of a transitive relation need not be transitive. ^{[ 5 ]} For example, although «equals» is transitive, «does not equal» is transitive only for sets containing at most one element.

Other properties

A transitive relation is asymmetric if and only if it is irreflexive . [ 6 ]

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

R = { (1,1), (2,2), (3,3), (1,3), (3,2) } is reflexive, but not transitive, since the pair (1,2) is missing.
R = { (1,1), (2,2), (3,3), (1,3) } is a reflexive and transitive set, so it is a preorder.
R = { (1,1), (2,2), (3,3) } is reflexive and transitive, another preorder relation.
R = { (1,2), (2,3), (1,3) } is transitive, but not reflexive.

As a counterexample, consider the relation $<$ $<$ The phrase «on the real numbers» is transitive, but not reflexive.

Transitive extensions and transitive closure

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

If a relation is transitive, then its transitive extension — is the relation itself, that is, if R — is a transitive relation, then R 1 = R .

The transitive extension of R 1 will be denoted as R 2 , and, continuing in this way, in general the transitive extension of R i will be R i + 1. The transitive closure of R , denoted as R * or R ∞, — is the union of the sets R , R 1 , R 2 , ... . [ 8 ]

The transitive closure of a relation is a transitive relation. [ 8 ]

The relation «is a biological parent» on a set of people is not transitive. However, in biology it often becomes necessary to consider biological parenthood over an arbitrary number of generations: the relation «is a biological ancestor» is transitive and is the transitive closure of the relation «is a biological parent».

In the above example with cities and roads, ( A , C ) ∈ R *, provided that one can travel between cities A and C over any number of roads.

Types of relations requiring transitivity

Preorder – a reflexive and transitive relation
Partial order – an antisymmetric preorder
Total preorder – a connected (formerly called total) preorder
Equivalence relation – a symmetric preorder
Strict weak order — a strict partial order in which incomparability is an equivalence relation.
Total order – a connected (total), antisymmetric, and transitive relation.

Counting transitive relations

No general formula is known that counts the number of transitive relations on a finite set (sequence A006905 in the OEIS ). [ 9 ] 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 ), symmetric and transitive, symmetric, transitive and antisymmetric, as well as connected, transitive and antisymmetric. Pfeiffer [ 10 ] has made some progress in this direction, expressing relations with combinations of these properties in terms of one another, but computing even one of them is still difficult. See also Brinkmann and McKay (2005) ^{[ 11 ]} and Mala (2022). ^{[ 12 ]}

Since the reflexivization of any transitive relation is a preorder relation , the number of transitive relations on an n-element set is at most 2n times the number of preorder relations, and consequently it is asymptotically equal to $2$ $2^{(1/4+o(1))n^{2}}$ by the results of Kleitman and Rothschild. ^{[ 13 ]}

Number of n -element binary relations of various types
Elements	Any	Transitive	Reflexive	Symmetric	Preorder	Partial order	Total preorder	Total order	Equivalence relation
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4096	1024	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ( n −1)}	2 ^{n ( n +1)/2}			∑n k =0 k ! S ( n , k )	n !	∑n k =0 S ( n , k )
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Note that S ( n , k ) denotes the Stirling numbers of the second kind .

Related objects

Циклическая диаграмма — The game « Rock-paper-scissors » is based on the non-transitive and antitransitive relation « x beats y ».

A relation R is called non-transitive 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 imply that xRz does not hold. For example, the relation defined as xRy if xy — is an even number , is non-transitive [ 14 ] , but not antitransitive [ 15]. The relation defined as xRy if x — is even and y — is odd , is both transitive and antitransitive [16]. The relation defined as xRy if x — is the successor of y, is both non-transitive [ 17 ] and antitransitive [ 18 ] . Unexpected examples of non-transitivity arise in situations such as political questions or group preferences [ 19 ] .

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

A quasitransitive relation — is another generalization; [ 5 ] it is required to be transitive only on its asymmetric part. Such relations are used in social choice theory or microeconomics . [ 21 ]

Proposition: If R — is a univalent operator , then R;R T is transitive.

Proof: Suppose

x

$xR;R^{T}yR;R^{T}z.$ Then there exist a and b such that

x R a R^{T} y R b R^{T} z .

$xRaR^{T}yRbR^{T}z.$ Since R is univalent, yRb and aR ^Ty imply a = b . Consequently, x R a R ^Tz , hence x R;R ^Tz and R;R ^T is transitive.

Corollary : If R is univalent, then R;R T is an equivalence relation on the domain of R.

Proof: R;R T is symmetric and reflexive on its domain. By the univalence of R the transitive requirement of equivalence is satisfied.

Transitive relation in mathematics

Definition

Examples

Properties

Closure properties

Other properties

Transitive extensions and transitive closure

Types of relations requiring transitivity

Counting transitive relations

Related objects

See also

Comments

To leave a comment

Lectures and tutorial on "Discrete Math. Set theory. Graph theory. Combinatorics."

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.