Converse relation: Difference between revisions

In mathematics, the inverse relation of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the inverse of the relation 'child of' is the relation 'parent of'. In formal terms, if ${\displaystyle X{\text{ and }}Y}$ are sets and ${\displaystyle L\subseteq X\times Y}$ is a relation from X to Y then ${\displaystyle L^{-1}}$ is the relation defined so that ${\displaystyle y\,L^{-1}\,x}$ if and only if ${\displaystyle x\,L\,y}$ (Halmos 1975, p. 40). In set-builder notation, ${\displaystyle L^{-1}=\{(y,x)\in Y\times X\mid (x,y)\in L\}}$.

The notation comes by analogy with that for an inverse function. Although many functions do not have an inverse; every relation does have a unique inverse. Despite the notation and terminology, the inverse relation is not an inverse in the sense of group inverse; the unary operation that maps a relation to the inverse relation is however an involution, so it induces the structure of a semigroup with involution on the binary relations on a set, or more generally induces a dagger category on the category of relations as detailed below.

The inverse relation is also called the converse relation or transpose relation— the latter in view of its similarity with the transpose of a matrix.^[1] Other notations for the inverse relation include L^C, L^T, L^~ or ${\displaystyle {\breve {L}}}$.

This section needs expansion. You can help by adding to it.

For usual (maybe strict or partial) order relations, the converse is the naively expected "opposite" order, e.g. ${\displaystyle \leq ^{-1}=\ \geq ,~<^{-1}=\ >}$, etc.

A function is invertible if and only if its inverse relation is a function, in which case the inverse relation is the inverse function.

The inverse relation of a function ${\displaystyle f:X\to Y}$ is the relation ${\displaystyle f^{-1}:Y\to X}$ defined by ${\displaystyle \operatorname {graph} \,f^{-1}=\{(y,x)\mid y=f(x)\}}$.

This is not necessarily a function: One necessary condition is that f be injective, since else ${\displaystyle f^{-1}}$ is multi-valued. This condition is sufficient for ${\displaystyle f^{-1}}$ being a partial function, and it is clear that ${\displaystyle f^{-1}}$ then is a (total) function if and only if f is surjective. In that case, i.e. if f is bijective, ${\displaystyle f^{-1}}$ may be called the inverse function of f.

In the monoid of binary endorelations on a set (with the binary operation on relations being the composition of relations), the inverse relation does not satisfy the definition of an inverse from group theory, i.e. if L is an arbitrary relation on X, then ${\displaystyle L\circ L^{-1}}$ does not equal the identity relation on X in general. The inverse relation does satisfy the (weaker) axioms of a semigroup with involution: ${\displaystyle (L^{-1})^{-1}=L}$ and ${\displaystyle (L\circ R)^{-1}=R^{-1}\circ L^{-1}}$.^[2]

Since one may generally consider relations between different sets (which form a category rather than a monoid, namely the category of relations Rel), in this context the inverse relation conforms to the axioms of a dagger category (aka category with involution).^[2] A relation equal to its inverse is a symmetric relation; in the language of dagger categories, it is self-adjoint.

Furthermore, the semigroup of endorelations on a set is also a partially ordered structure (with inclusion of relations as sets), and actually an involutive quantale. Similarly, the category of heterogenous relations, Rel is also an ordered category.^[2]

In relation algebra, the operation of taking the inverse relation commutes with other binary operations of union and intersection. Taking the inverse also commutes with unary operation of complementation as well as with taking suprema and infima. It is also compatible with the ordering of relations by inclusion.^[1]

If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, total, trichotomous, a partial order, total order, strict weak order, total preorder (weak order), or an equivalence relation, its inverse is too.

• Bijection
• Function (mathematics)
• Inverse function
• Relation (mathematics)
• Transpose graph

• Halmos, Paul R. (1974), Naive Set Theory, ISBN 978-0-387-90092-6