Allegory (mathematics) | 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 mathematical field of , an allegory is a that has some of the structure of the category Rel of sets and binary relations between them. Allegories can be used as an abstraction of categories of relations, and in this sense the theory of allegories is a generalization of relation algebra to relations between different sorts. Allegories are also useful in defining and investigating certain constructions in category theory, such as completions. In this article we adopt the convention that morphisms compose from right to left, so RS means "first do S, then do R". An allegory is a in which every morphism is associated with an anti-involution, i.e. a morphism with and and every pair of morphisms with common domain/codomain is associated with an intersection, i.e. a morphism all such that intersections are idempotent: commutative: and associative: anti-involution distributes over intersection: composition is semi-distributive over intersection: and and the modularity law is satisfied: Here, we are abbreviating using the order defined by the intersection: means A first example of an allegory is the . The of this allegory are sets, and a morphism is a binary relation between X and Y. Composition of morphisms is composition of relations, and the anti-involution of is the converse relation : if and only if . Intersection of morphisms is (set-theoretic) intersection of relations. In a category C, a relation between objects X and Y is a of morphisms that is jointly monic. Two such spans and are considered equivalent when there is an isomorphism between S and T that make everything commute; strictly speaking, relations are only defined up to equivalence (one may formalise this either by using equivalence classes or by using ). If the category C has products, a relation between X and Y is the same thing as a monomorphism into X × Y (or an equivalence class of such). In the presence of and a proper factorization system, one can define the composition of relations.

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 publications (1)

Related concepts (3)

Reversible Sesqui-Pushout Rewriting, Graph Transformation

Sandro Stucki

The paper proposes a variant of sesqui-pushout rewriting (SqPO) that allows one to develop the theory of nested application conditions (NACs) for arbitrary rule spans; this is a considerable generalisation compared with existing results for NACs, which onl ...

Springer2014

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.

Composition of relations

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.

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.