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 ${\displaystyle X}$ and ${\displaystyle Y}$ are sets and ${\displaystyle L\subseteq X\times Y}$ is a relation from ${\displaystyle X}$ to ${\displaystyle Y,}$ then ${\displaystyle L^{\operatorname {T} }}$ is the relation defined so that ${\displaystyle yL^{\operatorname {T} }x}$ if and only if ${\displaystyle xLy.}$ In set-builder notation,

${\displaystyle L^{\operatorname {T} }=\{(y,x)\in Y\times X:(x,y)\in L\}.}$

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^[1][2][3][4] is also called the transpose relation.^[5] It has also been called the opposite or dual of the original relation,^[6] the inverse of the original relation,^{[7][8][9][10]} or the reciprocal ${\displaystyle L^{\circ }}$ of the relation ${\displaystyle L.}$^[11]

Other notations for the converse relation include ${\displaystyle L^{\operatorname {C} },L^{-1},{\breve {L}},L^{\circ },}$ or ${\displaystyle L^{\vee }.}$^{[citation needed]}

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)^{[citation needed]} 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)

, the converse is the naively expected "opposite" order, for examples, ${\displaystyle {\leq ^{\operatorname {T} }}={\geq },\quad {<^{\operatorname {T} }}={>}.}$

A relation may be represented by a logical matrix such as

Then the converse relation is represented by its

:

The converse of kinship relations are named: "${\displaystyle A}$ is a child of ${\displaystyle B}$" has converse "${\displaystyle B}$ is a parent of ${\displaystyle A}$". "${\displaystyle A}$ is a

of ${\displaystyle B}$" has converse "${\displaystyle B}$ is an uncle or aunt of ${\displaystyle A}$". The relation "${\displaystyle A}$ is a sibling of ${\displaystyle B}$" is its own converse, since it is a symmetric relation.

Properties

In the

), the converse relation does not satisfy the definition of an inverse from group theory, that is, if ${\displaystyle L}$ is an arbitrary relation on ${\displaystyle X,}$ then ${\displaystyle L\circ L^{\operatorname {T} }}$ does not equal the identity relation on ${\displaystyle X}$ in general. The converse relation does satisfy the (weaker) axioms of a semigroup with involution: ${\displaystyle \left(L^{\operatorname {T} }\right)^{\operatorname {T} }=L}$ and ${\displaystyle (L\circ R)^{\operatorname {T} }=R^{\operatorname {T} }\circ L^{\operatorname {T} }.}$^[12]

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 (aka category with involution).^[12] 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

In the

If a relation is

, its converse is too.

Inverses

If ${\displaystyle I}$ represents the identity relation, then a relation ${\displaystyle R}$ may have an inverse as follows: ${\displaystyle R}$ is called

right-invertible

if there exists a relation ${\displaystyle X,}$ called a right inverse of ${\displaystyle R,}$ that satisfies ${\displaystyle R\circ X=I.}$

left-invertible

if there exists a relation ${\displaystyle Y,}$ called a left inverse of ${\displaystyle R,}$ that satisfies ${\displaystyle Y\circ R=I.}$

invertible

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

For an invertible homogeneous relation ${\displaystyle R,}$ all right and left inverses coincide; this unique set is called its inverse and it is denoted by ${\displaystyle R^{-1}.}$ In this case, ${\displaystyle R^{-1}=R^{\operatorname {T} }}$ holds.[5]^: 79

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 ${\displaystyle f:X\to Y}$ is the relation ${\displaystyle f^{-1}\subseteq Y\times X}$ defined by the ${\displaystyle \operatorname {graph} \,f^{-1}=\{(y,x)\in Y\times X:y=f(x)\}.}$

This is not necessarily a function: One necessary condition is that ${\displaystyle f}$ be

, since else ${\displaystyle f^{-1}}$ is . 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 ${\displaystyle f}$ is . In that case, meaning if ${\displaystyle f}$ is , ${\displaystyle f^{-1}}$ may be called the inverse function of ${\displaystyle f.}$

For example, the function ${\displaystyle f(x)=2x+2}$ has the inverse function ${\displaystyle f^{-1}(x)={\frac {x}{2}}-1.}$

However, the function ${\displaystyle g(x)=x^{2}}$ has the inverse relation ${\displaystyle g^{-1}(x)=\pm {\sqrt {x}},}$ which is not a function, being multi-valued.

Composition with relation

Using composition of relations, the converse may be composed with the original relation. For example, the subset relation composed with its converse is always the universal relation:

∀A ∀B ∅ ⊂ A ∩B ⇔ A ⊃ ∅ ⊂ B ⇔ A ⊃ ⊂ B. Similarly,

For U = universe, A ∪ B ⊂ U ⇔ A ⊂ U ⊃ B ⇔ A ⊂ ⊃ B.

Now consider the

relation and its converse.

${\displaystyle A\ni z\in B\Leftrightarrow z\in A\cap B\Leftrightarrow A\cap B\neq \emptyset .}$

Thus ${\displaystyle A\ni \in B\Leftrightarrow A\cap B\neq \emptyset .}$ The opposite composition ${\displaystyle \in \ni }$ is the universal relation.

The compositions are used to classify relations according to type: for a relation Q, when the

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

See also

• Duality (order theory) – Term in the mathematical area of order theory
• Transpose graph – Directed graph with reversed edges

References

• ISBN 978-0-387-90092-6