Converse relation

In mathematics, the converse 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,
Since a relation may be represented by a logical matrix, and the logical matrix of the converse relation is the transpose of the original, the converse relation is also called the transpose relation. It has also been called the opposite or dual of the original relation, the inverse of the original relation, or the reciprocal of the relation
Other notations for the converse relation include or
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. The unary operation that maps a relation to the converse relation is 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]. As a unary operation, taking the converse commutes with the order-related operations of the calculus of relations, that is it commutes with union, intersection, and complement.

Examples

For the usual order relations, the converse is the naively expected "opposite" order, for examples,
A relation may be represented by a logical matrix such as
Then the converse relation is represented by its transpose matrix:
The converse of kinship relations are named: " is a child of " has converse " is a parent of ". " is a nephew or niece of " has converse " is an uncle or aunt of ". The relation " is a sibling of " is its own converse, since it is a symmetric relation.

Properties

In the monoid of binary endorelations on a set, the converse relation does not satisfy the definition of an inverse from group theory, that is, if is an arbitrary relation on then does equal the identity relation on in general. The converse relation does satisfy the axioms of a semigroup with involution: and
Since one may generally consider relations between different sets, in this context the converse relation conforms to the axioms of a dagger category. A relation equal to its converse 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, and actually an involutive quantale. Similarly, the category of heterogeneous relations, Rel is also an ordered category.
In the calculus of relations, commutes with other binary operations of union and intersection. Conversion also commutes with unary operation of complementation as well as with taking suprema and infima. Conversion is also compatible with the ordering of relations by inclusion.
If a relation is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive, connected, trichotomous, a partial order, total order, strict weak order, total preorder, or an equivalence relation, its converse is too.

Inverses

If represents the identity relation, then a relation may have an inverse as follows: is called
For an invertible homogeneous relation all right and left inverses coincide; this unique set is called its and it is denoted by In this case, holds.

Converse relation of a function

A function is invertible if and only if its converse relation is a function, in which case the converse relation is the inverse function.
The converse relation of a function is the relation defined by the
This is not necessarily a function: One necessary condition is that be injective, since else is multi-valued. This condition is sufficient for being a partial function, and it is clear that then is a function if and only if is surjective. In that case, meaning if is bijective, may be called the inverse function of
For example, the function has the inverse function
However, the function has the inverse relation which is not a function, being multi-valued.

Composition with relation

Using composition of relations, a relation can be composed with its converse.
For the subset relation on the power set of a universe, both compositions with its converse are the universal relation on :
Indeed, for any,
which holds by taking ; similarly,
which holds by taking.
Now consider the set membership relation and its converse. For sets,
so is the "nonempty intersection" relation on. Conversely, for elements,
which always holds ; hence is the universal relation on.
The compositions are used to classify relations according to type: for a relation Q, when the identity relation on the range of Q contains Q^TQ, then Q is called univalent. When the identity relation on the domain of Q is contained in QQ^T, then Q is called total. When Q is both univalent and total then it is a function. When Q^T is univalent, then Q is termed injective. When Q^T is total, Q is termed surjective.
If Q is univalent, then QQ^T is an equivalence relation on the domain of Q, see Transitive relation#Related properties.