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 'childof' is the relation 'parent are sets 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

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 (sometimes called conversion or transposition) commutes with the order-related operations of the calculus of relations, that is it commutes with union, intersection, and complement.

Examples

For the usual (maybe strict or partial) order relations In order theory is typically called its dual.

A relation may be represented by a logical matrix

Then the converse relation is represented by its transpose matrix

Many kinship relations in English have converses that are also named. Thus the is-a-child-of relation has as its converse the is-a-parent-of relation. Likewise, the converse of is-a-nephew-or-niece-of is is-an-uncle-or-aunt-of. As for the is-a-sibling-of relation, it is its own converse, since it is a symmetric relation.

Properties

In the monoid of binary endorelations on a set (with the binary operation on relations being the composition of relations does equal the identity relation in general. The converse relation does satisfy the (weaker) axioms of a semigroup with involution

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 converse relation conforms to the axioms of a dagger category ( category with involution). 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 (with inclusion of relations as sets), and actually an involutive quantale. Similarly, the category of heterogeneous relations, Rel is also an ordered category.

In the calculus of relations, (the unary operation of taking the converse relation) 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 (weak order), or an equivalence relation, its converse is too.

Inverses

may have an inverse is called

1. called a

2. called a

3. if it is both right-invertible and left-invertible.

all right and left inverses coincide; this unique set is called its 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.

be injective is multi-valued being a partial function then is a (total) function if and only if is surjective is bijective may be called the inverse function

which is not a function, being multi-valued.

Composition with relation

Using composition of relations, a relation can be composed with its converse.

on the power set, both compositions with its converse are the universal relation:

,

; similarly,

.

Now consider the set membership,

,

.

The compositions are used to classify relations according to type: for a relation Q, when the identity relation on the range of Q contains QTQ, then Q is called univalent. When the identity relation on the domain of Q is contained in QQT, then Q is called total. When Q is both univalent and total then it is a function. When QT is univalent, then Q is termed injective. When QT is total, Q is termed surjective.

If Q is univalent, then QQT is an equivalence relation on the domain of Q, see Transitive relation#Related properties.

See also

References