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[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 of the relation [11]

Other notations for the converse relation include or [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

edit

For the usual (maybe strict or partial) 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

edit

In the monoid of binary endorelations on a set (with the binary operation on relations being the composition of relations), the converse relation does not satisfy the definition of an inverse from group theory, that is, if   is an arbitrary relation on   then   does not equal the identity relation on   in general. The converse relation does satisfy the (weaker) axioms of a semigroup with involution:   and  [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 quantale. Similarly, the category of heterogeneous relations, Rel is also an ordered category.[12]

In the calculus of relations, conversion (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.[5]

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

edit

If   represents the identity relation, then a relation   may have an inverse as follows:   is called

right-invertible
if there exists a relation   called a right inverse of   that satisfies  
left-invertible
if there exists a relation   called a left inverse of   that satisfies  
invertible
if it is both right-invertible and left-invertible.

For an invertible homogeneous relation   all right and left inverses coincide; this unique set is called its inverse and it is denoted by   In this case,   holds.[5]: 79 

Converse relation of a function

edit

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 (total) 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

edit

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 set membership relation and its converse.

 

Thus   The opposite composition   is the universal relation.

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 Q QT, 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.[13]

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

See also

edit

References

edit
  1. ^ Ernst Schröder, (1895), Algebra der Logik (Exakte Logik) Dritter Band, Algebra und Logik der Relative, Leibzig: B. G. Teubner via Internet Archive Seite 3 Konversion
  2. ^ Bertrand Russell (1903) Principles of Mathematics, page 97 via Internet Archive
  3. ^ C. I. Lewis (1918) A Survey of Symbolic Logic, page 273 via Internet Archive
  4. ^ Schmidt, Gunther (2010). Relational Mathematics. Cambridge: Cambridge University Press. p. 39. ISBN 978-0-521-76268-7.
  5. ^ a b c Gunther Schmidt; Thomas Ströhlein (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Springer Berlin Heidelberg. pp. 9–10. ISBN 978-3-642-77970-1.
  6. ^ Celestina Cotti Ferrero; Giovanni Ferrero (2002). Nearrings: Some Developments Linked to Semigroups and Groups. Kluwer Academic Publishers. p. 3. ISBN 978-1-4613-0267-4.
  7. ^ Daniel J. Velleman (2006). How to Prove It: A Structured Approach. Cambridge University Press. p. 173. ISBN 978-1-139-45097-3.
  8. ^ Shlomo Sternberg; Lynn Loomis (2014). Advanced Calculus. World Scientific Publishing Company. p. 9. ISBN 978-9814583930.
  9. ^ Rosen, Kenneth H. (2017). Handbook of discrete and combinatorial mathematics. Rosen, Kenneth H., Shier, Douglas R., Goddard, Wayne. (Second ed.). Boca Raton, FL. p. 43. ISBN 978-1-315-15648-4. OCLC 994604351.{{cite book}}: CS1 maint: location missing publisher (link)
  10. ^ Gerard O'Regan (2016): Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications ISBN 9783319445618
  11. ^ Peter J. Freyd & Andre Scedrov (1990) Categories, Allegories, page 79, North Holland ISBN 0-444-70368-3
  12. ^ a b c Joachim Lambek (2001). "Relations Old and New". In Ewa Orłowska; Andrzej Szalas (eds.). Relational Methods for Computer Science Applications. Springer Science & Business Media. pp. 135–146. ISBN 978-3-7908-1365-4.
  13. ^ Gunther Schmidt & Michael Winter (2018) Relational Topology, Springer Lecture Notes in Mathematics #2208, page 8, ISBN 978-3-319-74450-6