Composition of relations | EPFL Graph Search

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

In the mathematics of binary relations, the composition of relations is the forming of a new binary relation R; S from two given binary relations R and S. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product. Function composition is the special case of composition of relations where all relations involved are functions. The word uncle indicates a compound relation: for a person to be an uncle, he must be the brother of a parent. In algebraic logic it is said that the relation of Uncle () is the composition of relations "is a brother of" () and "is a parent of" (). Beginning with Augustus De Morgan, the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition. If and are two binary relations, then their composition is the relation In other words, is defined by the rule that says if and only if there is an element such that (that is, and ). The semicolon as an infix notation for composition of relations dates back to Ernst Schroder's textbook of 1895. Gunther Schmidt has renewed the use of the semicolon, particularly in Relational Mathematics (2011). The use of semicolon coincides with the notation for function composition used (mostly by computer scientists) in , as well as the notation for dynamic conjunction within linguistic dynamic semantics. A small circle has been used for the infix notation of composition of relations by John M. Howie in his books considering semigroups of relations. However, the small circle is widely used to represent composition of functions which reverses the text sequence from the operation sequence. The small circle was used in the introductory pages of Graphs and Relations until it was dropped in favor of juxtaposition (no infix notation). Juxtaposition is commonly used in algebra to signify multiplication, so too, it can signify relative multiplication. Further with the circle notation, subscripts may be used.

About this result

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 concepts (30)

Related courses (2)

Related lectures (72)

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.

Composition of relations

Category of relations

In mathematics, the Rel has the class of sets as and binary relations as . A morphism (or arrow) R : A → B in this category is a relation between the sets A and B, so R ⊆ A × B. The composition of two relations R: A → B and S: B → C is given by (a, c) ∈ S o R ⇔ for some b ∈ B, (a, b) ∈ R and (b, c) ∈ S. Rel has also been called the "category of correspondences of sets". The category Rel has the Set as a (wide) , where the arrow f : X → Y in Set corresponds to the relation F ⊆ X × Y defined by (x, y) ∈ F ⇔ f(x) = y.

CIVIL-475: Civil Engineering teaching unit: Docta Manus

L'Unité introduira le dessin comme l'outil clé de la communication entre ingénieurs et architectes et comme médiateur entre la construction et l'étudiant. Grâce au dessin, nous analyserons des projets

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

Relations: Sets, Functions and Composition CS-101: Advanced information, computation, communication I

Covers binary relations, functions, set operations, composition, and n-ary relations.

Advanced Analysis II: General Variable Change MATH-105(b): Advanced analysis II

Explores general variable change in advanced analysis with practical examples.

Differential Privacy: Hypothesis Testing and Composition COM-622: Topics in information-theoretic cryptography

Explores differential privacy, hypothesis testing, and composition of mechanisms, discussing optimal privacy regions and privacy degradation under repeated accesses.