In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the category

Category (mathematics)

In mathematics, a category is an algebraic structure that comprises "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...

 Rel has the class of sets as objects and binary relation

Binary relation

In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...

s as morphisms.

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

The composition

Composition of relations

In mathematics, the composition of binary relations is a concept of forming a new relation from two given relations R and S, having as its most well-known special case the composition of functions.- Definition :...

 of two relations R: A → B and S: B → C is given by: ∈ S o R if (and only if) for some b ∈ B, (a, b) ∈ R and (b, c) ∈ S.

Properties

Category Rel has the category of sets

Category of sets

In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets A and B are all functions from A to B...

 Set as a (wide) subcategory

Subcategory

In mathematics, a subcategory of a category C is a category S whose objects are objects in C and whose morphisms are morphisms in C with the same identities and composition of morphisms. Intuitively, a subcategory of C is a category obtained from C by "removing" some of its objects and...

, where the arrow (function) in Set corresponds to the functional relation defined by: .

Category Rel can be obtained from category Set as the Kleisli category

Kleisli category

In category theory, a Kleisli category is a category naturally associated to any monad T. It is equivalent to the category of free T-algebras. The Kleisli category is one of two extremal solutions to the question Does every monad arise from an adjunction? The other extremal solution is the...

 for the monad

Monad (category theory)

In category theory, a branch of mathematics, a monad, Kleisli triple, or triple is an functor, together with two natural transformations...

 whose functor

Functor

In category theory, a branch of mathematics, a functor is a special type of mapping between categories. Functors can be thought of as homomorphisms between categories, or morphisms when in the category of small categories....

 corresponds to power set, interpreted as a covariant functor.

The involutary operation of taking the inverse

Inverse relation

In mathematics, the inverse relation of a binary relation is the relation that occurs when you switch the order of the elements in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'...

 (or converse) of a relation, where if and only if , induces a contravariant functor that leaves the objects invariant but reverses the arrows and composition. This makes Rel into a dagger category

Dagger category

In mathematics, a dagger category is a category equipped with a certain structure called dagger or involution...

. In fact, Rel is a dagger compact category

Dagger compact category

In mathematics, dagger compact categories first appeared in 1989 in the work of Doplicher and Roberts on the reconstruction of compact topological group from their category of finite-dimensional continuous unitary representations...

.

See also

• Allegory (category theory)
  Allegory (category theory)
  In mathematical category theory, an allegory is a category that has some of the structure of the category 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...
  
  . The category of relations is the paradigmatic example of an allegory.