Category of relations

Last updated
Category of Relations Rel.
Rel's opposite Relop.

In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms.

Contents

A morphism (or arrow) R : AB in this category is a relation between the sets A and B, so RA × B.

The composition of two relations R: AB and S: BC is given by

(a, c) ∈ SoR ⇔ for some bB, (a, b) ∈ R and (b, c) ∈ S. [1]

Rel has also been called the "category of correspondences of sets". [2]

Properties

The category Rel has the category of sets Set as a (wide) subcategory, where the arrow f : XY in Set corresponds to the relation FX × Y defined by (x, y) ∈ Ff(x) = y. [3] [4]

A morphism in Rel is a relation, and the corresponding morphism in the opposite category to Rel has arrows reversed, so it is the converse relation. Thus Rel contains its opposite and is self-dual. [5]

The involution represented by taking the converse relation provides the dagger to make Rel a dagger category.

The category has two functors into itself given by the hom functor: A binary relation RA × B and its transpose RTB × A may be composed either as R RT or as RTR. The first composition results in a homogeneous relation on A and the second is on B. Since the images of these hom functors are in Rel itself, in this case hom is an internal hom functor. With its internal hom functor, Rel is a closed category, and furthermore a dagger compact category.

The category Rel can be obtained from the category Set as the Kleisli category for the monad whose functor corresponds to power set, interpreted as a covariant functor.

Perhaps a bit surprising at first sight is the fact that product in Rel is given by the disjoint union [5] :181 (rather than the cartesian product as it is in Set), and so is the coproduct.

Rel is monoidal closed, with both the monoidal product AB and the internal hom AB given by cartesian product of sets.

The category Rel was the prototype for the algebraic structure called an allegory by Peter J. Freyd and Andre Scedrov in 1990. [6] Starting with a regular category and a functor F: AB, they note properties of the induced functor Rel(A,B) → Rel(FA, FB). For instance, it preserves composition, conversion, and intersection. Such properties are then used to provide axioms for an allegory.

Relations as objects

David Rydeheard and Rod Burstall consider Rel to have objects that are homogeneous relations. For example, A is a set and RA × A is a binary relation on A. The morphisms of this category are functions between sets that preserve a relation: Say SB × B is a second relation and f: AB is a function such that ${\displaystyle xRy\implies f(x)Sf(y),}$ then f is a morphism. [7]

The same idea is advanced by Adamek, Herrlich and Strecker, where they designate the objects (A, R) and (B, S), set and relation. [8]

Related Research Articles

Category theory formalizes mathematical structure and its concepts in terms of a labeled directed graph called a category, whose nodes are called objects, and whose labelled directed edges are called arrows. A category has two basic properties: the ability to compose the arrows associatively, and the existence of an identity arrow for each object. The language of category theory has been used to formalize concepts of other high-level abstractions such as sets, rings, and groups. Informally, category theory is a general theory of functions.

In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied.

In mathematics, a category is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.

In category theory, a branch of mathematics, an initial object of a category C is an object I in C such that for every object X in C, there exists precisely one morphism IX.

In category theory, an epimorphism is a morphism f : XY that is right-cancellative in the sense that, for all objects Z and all morphisms g1, g2: YZ,

In mathematics, and especially in category theory, a commutative diagram is a diagram such that all directed paths in the diagram with the same start and endpoints lead to the same result. It is said that commutative diagrams play the role in category theory that equations play in algebra.

In category theory, a branch of mathematics, an enriched category generalizes the idea of a category by replacing hom-sets with objects from a general monoidal category. It is motivated by the observation that, in many practical applications, the hom-set often has additional structure that should be respected, e.g., that of being a vector space of morphisms, or a topological space of morphisms. In an enriched category, the set of morphisms associated with every pair of objects is replaced by an object in some fixed monoidal category of "hom-objects". In order to emulate the (associative) composition of morphisms in an ordinary category, the hom-category must have a means of composing hom-objects in an associative manner: that is, there must be a binary operation on objects giving us at least the structure of a monoidal category, though in some contexts the operation may also need to be commutative and perhaps also to have a right adjoint.

In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets. This functor makes it possible to think of the objects of the category as sets with additional structure, and of its morphisms as structure-preserving functions. Many important categories have obvious interpretations as concrete categories, for example the category of topological spaces and the category of groups, and trivially also the category of sets itself. On the other hand, the homotopy category of topological spaces is not concretizable, i.e. it does not admit a faithful functor to the category of sets.

In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the Cartesian product of sets, the direct product of groups or rings, and the product of topological spaces. Essentially, the product of a family of objects is the "most general" object which admits a morphism to each of the given objects.

In mathematics, a monoidal category is a category equipped with a bifunctor

The following outline is provided as an overview of and guide to category theory, the area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows, where these collections satisfy certain basic conditions. Many significant areas of mathematics can be formalised as categories, and the use of category theory allows many intricate and subtle mathematical results in these fields to be stated, and proved, in a much simpler way than without the use of categories.

In mathematics, especially in category theory, a closed monoidal category is a category that is both a monoidal category and a closed category in such a way that the structures are compatible.

In category theory, a branch of mathematics, a closed category is a special kind of category.

In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed categories. Categories without adjoined products may still have an exponential law.

This is a glossary of properties and concepts in category theory in mathematics.

In mathematics, a full subcategory A of a category B is said to be reflective in B when the inclusion functor from A to B has a left adjoint. This adjoint is sometimes called a reflector, or localization. Dually, A is said to be coreflective in B when the inclusion functor has a right adjoint.

In category theory, a branch of mathematics, a dagger category is a category equipped with a certain structure called dagger or involution. The name dagger category was coined by Peter Selinger.

In the mathematical field of category theory, an allegory is a category 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 exact completions.

In mathematics, the category of rings, denoted by Ring, is the category whose objects are rings and whose morphisms are ring homomorphisms. Like many categories in mathematics, the category of rings is large, meaning that the class of all rings is proper.

In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms are functions; in linear algebra, linear transformations; in group theory, group homomorphisms; in topology, continuous functions, and so on.

References

1. Mac Lane, S. (1988). Categories for the Working Mathematician (1st ed.). New York: Springer-Verlag. p. 26. ISBN   0-387-90035-7.
2. Pareigis, Bodo (1970). Categories and Functors. Pure and Applied Mathematics. 39. Academic Press. p. 6. ISBN   978-0-12-545150-5.
3. This category is called SetRel by Rydeheard and Burstall.
4. George Bergman (1998), An Invitation to General Algebra and Universal Constructions , §7.2 RelSet, Henry Helson Publisher, Berkeley. ISBN   0-9655211-4-1.
5. Michael Barr & Charles Wells (1998) Category Theory for Computer Scientists Archived 2016-03-04 at the Wayback Machine , page 83, from McGill University
6. Peter J. Freyd & Andre Scedrov (1990) Categories, Allegories, pages 79, 196, North Holland ISBN   0-444-70368-3
7. David Rydeheard & Rod Burstall (1988) Computational Category Theory, page 41, Prentice-Hall ISBN   978-0131627369
8. Juri Adamek, Horst Herrlich, and George E. Strecker (2004) [1990] Abstract and Concrete Categories, section 3.3, example 2(d) page 22, from Research group KatMAT at University of Bremen