**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Transitive relation

Summary

In mathematics, a relation R on 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.
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:
where a R b is the infix notation for (a, b) ∈ R.
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, 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 this does not imply that Alice is the birth parent of Claire. What is more, it is antitransitive: Alice can never be the birth parent of Claire.
Non-transitive, non-antitransitive relations include sports fixtures (playoff schedules), 'knows' and 'talks to'.
"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 x = y and y = z, then also x = z.
More examples of transitive relations:
"is a subset of" (set inclusion, a relation on sets)
"divides" (divisibility, a relation on natural numbers)
"implies" (implication, symbolized by "⇒", a relation on propositions)
Examples of non-transitive relations:
"is the successor of" (a relation on natural numbers)
"is a member of the set" (symbolized as "∈")
"is perpendicular to" (a relation on lines in Euclidean geometry)
The empty relation on any set is transitive because there are no elements such that and , and hence the transitivity condition is vacuously true.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (30)

Related people (2)

Related publications (13)

Related concepts (23)

Related MOOCs (2)

Related lectures (51)

Ontological neighbourhood

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

PHYS-100: Advanced physics I (mechanics)

La Physique Générale I (avancée) couvre la mécanique du point et du solide indéformable. Apprendre la mécanique, c'est apprendre à mettre sous forme mathématique un phénomène physique, en modélisant l

MATH-101(g): Analysis I

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

Homogeneous relation

In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. This is commonly phrased as "a relation on X" or "a (binary) relation over X". An example of a homogeneous relation is the relation of kinship, where the relation is between people. Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations.

Symmetric relation

A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if a = b is true then b = a is also true. Formally, a binary relation R over a set X is symmetric if: where the notation means that . If RT represents the converse of R, then R is symmetric if and only if R = RT. Symmetry, along with reflexivity and transitivity, are the three defining properties of an equivalence relation. "is equal to" (equality) (whereas "is less than" is not symmetric) "is comparable to", for elements of a partially ordered set ".

Converse relation

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation, The notation is analogous with that for an inverse function. Although many functions do not have an inverse, every relation does have a unique converse.

Advanced statistical physics

We explore statistical physics in both classical and open quantum systems. Additionally, we will cover probabilistic data analysis that is extremely useful in many applications.

Advanced statistical physics

We explore statistical physics in both classical and open quantum systems. Additionally, we will cover probabilistic data analysis that is extremely useful in many applications.

General Physics: Mechanics

Explores mechanics concepts, including moments of inertia for common solids and their practical applications.

Force-extension relation of a polymer

Explores the force-extension relation of polymers through experiments and models.

Friction Forces

Explores friction forces, Newton's laws applications, and momentum calculation on various surfaces.

Rainer Beck, Maarten Eduard van Reijzen, Bo-Jung Chen, Jörn Werdecker

The fate of vibrational energy in the collision of methane (CH4) in its antisymmetric C-H stretch vibration (ν3) with a Ni(111) surface has been studied in a state-to-state scattering experiment. Laser excitation in the incident molecular beam prepared the ...

2018We present Counterexample-Guided Accelerated Abstraction Refinement (CEGAAR), a new algorithm for verifying infinite-state transition systems. CEGAAR combines interpolation-based predicate discovery in counterexample guided predicate abstraction with accel ...

2012,

We present Counterexample-Guided Accelerated Abstraction Refinement (CEGAAR), a new algorithm for verifying infinite-state transition systems. CEGAAR combines interpolation-based predicate discovery in counterexample guided predicate abstraction with accel ...

2012