{{Short description|Reversal of the order of elements of a binary relation}} {{For|functions decreasing as 1/x|inverse proportion}} {{For|inverse relationships in statistics|negative relationship}}
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 <math>X</math> and <math>Y</math> are sets and <math>L \subseteq X \times Y</math> is a relation from <math>X</math> to <math>Y,</math> then <math>L^{\operatorname{T}}</math> is the relation defined so that <math>yL^{\operatorname{T}}x</math> if and only if <math>xLy.</math> In set-builder notation, :<math>L^{\operatorname{T}} = \{ (y, x) \in Y \times X : (x, y) \in L \}.</math>
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<ref>Ernst Schröder, (1895), ''[https://archive.org/details/vorlesungenberd03mlgoog Algebra der Logik (Exakte Logik) Dritter Band, Algebra und Logik der Relative]'', Leibzig: B. G. Teubner via Internet Archive Seite 3 ''Konversion''</ref><ref>Bertrand Russell (1903) [https://archive.org/details/principlesofmath005807mbp/page/96/mode/2up?q=converse Principles of Mathematics], page 97 via Internet Archive</ref><ref>C. I. Lewis (1918) [https://archive.org/details/asurveyofsymboli00lewiuoft/page/272/mode/2up A Survey of Symbolic Logic, page 273] via Internet Archive</ref><ref>{{cite book |last=Schmidt |first=Gunther |author-link=Gunther Schmidt |year=2010 |title=Relational Mathematics |url=https://books.google.com/books?id=E4dREBTs5WsC |page=39|location=Cambridge |publisher=Cambridge University Press |isbn=978-0-521-76268-7 }}</ref> is also called the '''transpose relation'''.<ref name=R&G>{{cite book|author1=Gunther Schmidt|author2=Thomas Ströhlein|title=Relations and Graphs: Discrete Mathematics for Computer Scientists|url=https://archive.org/details/relationsgraphsd00schm|url-access=limited|year=1993|publisher=Springer Berlin Heidelberg|isbn=978-3-642-77970-1|pages=[https://archive.org/details/relationsgraphsd00schm/page/n16 9]–10}}</ref> It has also been called the '''opposite''' or '''dual''' of the original relation,<ref>{{cite book|author1=Celestina Cotti Ferrero|author2=Giovanni Ferrero|title=Nearrings: Some Developments Linked to Semigroups and Groups|year=2002|publisher=Kluwer Academic Publishers|isbn=978-1-4613-0267-4|page=3}}</ref> the '''inverse''' of the original relation,<ref>{{cite book|author=Daniel J. Velleman|title=How to Prove It: A Structured Approach|url=https://books.google.com/books?id=sXt-ROLLNHcC&pg=PA173|year=2006|publisher=Cambridge University Press|isbn=978-1-139-45097-3|page=173}}</ref><ref name=S&S>{{cite book|author1=Shlomo Sternberg|author2=Lynn Loomis|title=Advanced Calculus|year=2014|publisher=World Scientific Publishing Company|isbn=978-9814583930|page=9}}</ref><ref>{{Cite book|last=Rosen|first=Kenneth H.|title=Handbook of discrete and combinatorial mathematics|others=Rosen, Kenneth H., Shier, Douglas R., Goddard, Wayne.|year=2017|isbn=978-1-315-15648-4|edition=Second|location=Boca Raton, FL|pages=43|oclc=994604351}}</ref><ref name=rega2016>Gerard O'Regan (2016): ''Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications'' {{isbn|9783319445618}}</ref> or the '''reciprocal''' <math>L^{\circ}</math> of the relation <math>L.</math><ref>Peter J. Freyd & Andre Scedrov (1990) Categories, Allegories, page 79, North Holland {{ISBN|0-444-70368-3}}</ref>
Other notations for the converse relation include <math>L^{\operatorname{C}}, L^{-1}, \breve{L}, L^{\circ},</math> or <math>L^{\vee}.</math>{{cn|reason=Give an example citation for each notation.|date=November 2023}}
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'''){{cn|date=November 2023}} 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, the converse is the naively expected "opposite" order, for examples, <math>{\leq^\operatorname{T}} = {\geq},\quad {<^\operatorname{T}} = {>}.</math>
A relation may be represented by a logical matrix such as <math display=block>\begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}. </math>
Then the converse relation is represented by its transpose matrix: <math display=block>\begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}. </math>
The converse of kinship relations are named: "<math>A</math> is a child of <math>B</math>" has converse "<math>B</math> is a parent of <math>A</math>". "<math>A</math> is a nephew or niece of <math>B</math>" has converse "<math>B</math> is an uncle or aunt of <math>A</math>". The relation "<math>A</math> is a sibling of <math>B</math>" 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), the converse relation does not satisfy the definition of an inverse from group theory, that is, if <math>L</math> is an arbitrary relation on <math>X,</math> then <math>L \circ L^{\operatorname{T}}</math> does {{em|not}} equal the identity relation on <math>X</math> in general. The converse relation does satisfy the (weaker) axioms of a semigroup with involution: <math>\left(L^{\operatorname{T}}\right)^{\operatorname{T}} = L</math> and <math>(L \circ R)^{\operatorname{T}} = R^{\operatorname{T}} \circ L^{\operatorname{T}}.</math><ref name="Lambek2001"/>
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).<ref name="Lambek2001"/> 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.<ref name="Lambek2001">{{cite book|editor= Ewa Orłowska|editor-link= Ewa Orłowska |editor2=Andrzej Szalas|title=Relational Methods for Computer Science Applications|year=2001|publisher=Springer Science & Business Media|isbn=978-3-7908-1365-4|pages=135–146|chapter=Relations Old and New|author=Joachim Lambek|author-link=Joachim Lambek}}</ref>
In the calculus of relations, {{em|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.<ref name=R&G/>
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== If <math>I</math> represents the identity relation, then a relation <math>R</math> may have an '''inverse''' as follows: <math>R</math> is called ;{{visible anchor|Right-invertible relation|text=right-invertible}} :if there exists a relation <math>X,</math> called a '''{{visible anchor|Right inverse relation|text=right inverse}}''' of <math>R,</math> that satisfies <math>R \circ X = I.</math> ;{{visible anchor|Left-invertible relation|text=left-invertible}} :if there exists a relation <math>Y,</math> called a '''{{visible anchor|Left inverse relation|text=left inverse}}''' of <math>R,</math> that satisfies <math>Y \circ R = I.</math> ;{{visible anchor|Invertible relation|text=invertible}} :if it is both right-invertible and left-invertible.
For an invertible homogeneous relation <math>R,</math> all right and left inverses coincide; this unique set is called its '''{{visible anchor|Inverse relation|text=inverse}}''' and it is denoted by <math>R^{-1}.</math> In this case, <math>R^{-1} = R^{\operatorname{T}}</math> holds.<ref name=R&G/>{{rp|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 <math>f : X \to Y</math> is the relation <math>f^{-1} \subseteq Y \times X</math> defined by the <math>\operatorname{graph}\, f^{-1} = \{ (y, x) \in Y \times X : y = f(x) \}.</math>
This is not necessarily a function: One necessary condition is that <math>f</math> be injective, since else <math>f^{-1}</math> is multi-valued. This condition is sufficient for <math>f^{-1}</math> being a partial function, and it is clear that <math>f^{-1}</math> then is a (total) function if and only if <math>f</math> is surjective. In that case, meaning if <math>f</math> is bijective, <math>f^{-1}</math> may be called the '''inverse function''' of <math>f.</math>
For example, the function <math>f(x) = 2x + 2</math> has the inverse function <math>f^{-1}(x) = \frac{x}{2} - 1.</math>
However, the function <math>g(x) = x^2</math> has the inverse relation <math>g^{-1}(x) = \pm \sqrt{x},</math> 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 <math>\subseteq</math> on the power set <math>\mathcal P(U)</math> of a universe <math>U</math>, both compositions with its converse are the universal relation on <math>\mathcal P(U)</math>: :<math> (\subseteq)\circ(\supseteq)=\mathcal P(U)\times\mathcal P(U) \quad\text{and}\quad (\supseteq)\circ(\subseteq)=\mathcal P(U)\times\mathcal P(U). </math> Indeed, for any <math>A,C\subseteq U</math>, :<math> A\big((\subseteq)\circ(\supseteq)\big)C \iff \exists B\subseteq U:\ A\subseteq B \land C\subseteq B </math> which holds by taking <math>B=A\cup C</math>; similarly, :<math> A\big((\supseteq)\circ(\subseteq)\big)C \iff \exists B\subseteq U:\ B\subseteq A \land B\subseteq C, </math> which holds by taking <math>B=A\cap C</math>.
Now consider the set membership relation <math>\in\; \subseteq\ U\times\mathcal P(U)</math> and its converse <math>\ni\; \subseteq\ \mathcal P(U)\times U</math>. For sets <math>A,B\subseteq U</math>, :<math> A\,(\ni\circ\in)\,B \iff \exists z\in U:\ z\in A \land z\in B \iff A\cap B\neq\emptyset, </math> so <math>\ni\circ\in</math> is the "nonempty intersection" relation on <math>\mathcal P(U)</math>. Conversely, for elements <math>x,y\in U</math>, :<math> x\,(\in\circ\ni)\,y \iff \exists A\subseteq U:\ x\in A \land y\in A, </math> which always holds (e.g. for <math>A=\{x,y\}</math>); hence <math>\in\circ\ni = U\times U</math> is the universal relation on <math>U</math>.
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''<sup>T</sup>''Q'', then ''Q'' is called ''univalent''. When the identity relation on the domain of ''Q'' is contained in ''QQ''<sup>T</sup>, then ''Q'' is called ''total''. When ''Q'' is both univalent and total then it is a ''function''. When ''Q''<sup>T</sup> is univalent, then ''Q'' is termed ''injective''. When ''Q''<sup>T</sup> is total, ''Q'' is termed ''surjective''.<ref>Gunther Schmidt & Michael Winter (2018) ''Relational Topology'', Springer Lecture Notes in Mathematics #2208, page 8, {{ISBN|978-3-319-74450-6}}</ref>
If ''Q'' is univalent, then ''QQ''<sup>T</sup> is an equivalence relation on the domain of ''Q'', see Transitive relation#Related properties.
==See also==
* {{annotated link|Duality (order theory)}} * {{annotated link|Transpose graph}}
==References==
{{reflist}}
* {{Citation|last1=Halmos|first1=Paul R.|author1-link=Paul R. Halmos|title=Naive Set Theory|isbn=978-0-387-90092-6|year=1974|page=[https://archive.org/details/naivesettheory0000halm_r4g0/page/40 40]|publisher=Springer }}
{{Order theory}}
Category:Binary relations Category:Mathematical logic