Converse relation

TheInfoList

OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the converse relation, or transpose, of a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...
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 $X$ and $Y$ are sets and $L \subseteq X \times Y$ is a relation from $X$ to $Y,$ then $L^$ is the relation defined so that $yL^x$ if and only if $xLy.$ In set-builder notation, :$L^ = \.$ The notation is analogous with that for an
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X\ ...
. Although many functions do not have an inverse, every relation does have a unique converse. The
unary operation In mathematics, an unary operation is an operation with only one operand, i.e. a single input. This is in contrast to binary operations, which use two operands. An example is any function , where is a set. The function is a unary operation o ...
that maps a relation to the converse relation is an involution, so it induces the structure of a
semigroup with involution In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered ...
on the binary relations on a set, or, more generally, induces a dagger category on the
category of relations In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms. A morphism (or arrow) ''R'' : ''A'' → ''B'' in this category is a relation between the sets ''A'' and ''B'', so . The composition of two rel ...
as detailed below. As a
unary operation In mathematics, an unary operation is an operation with only one operand, i.e. a single input. This is in contrast to binary operations, which use two operands. An example is any function , where is a set. The function is a unary operation o ...
, 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. Since a relation may be represented by a logical matrix, and the logical matrix of the converse relation is the
transpose In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix by producing another matrix, often denoted by (among other notations). The t ...
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, or the inverse of the original relation, or the reciprocal $L^$ of the relation $L.$ Other notations for the converse relation include $L^, L^, \breve, L^,$ or $L^.$

# Examples

For the usual (maybe strict or partial) order relations, the converse is the naively expected "opposite" order, for examples, $= ,\quad = .$ A relation may be represented by a logical matrix such as $\begin 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end.$ Then the converse relation is represented by its transpose matrix: $\begin 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \end.$ The converse of
kinship In anthropology, kinship is the web of social relationships that form an important part of the lives of all humans in all societies, although its exact meanings even within this discipline are often debated. Anthropologist Robin Fox says tha ...
relations are named: "$A$ is a child of $B$" has converse "$B$ is a parent of $A$". "$A$ is a nephew or niece of $B$" has converse "$B$ is an
uncle An uncle is usually defined as a male relative who is a sibling of a parent or married to a sibling of a parent. Uncles who are related by birth are second-degree relatives. The female counterpart of an uncle is an aunt, and the reciprocal rela ...
or
aunt An aunt is a woman who is a sibling of a parent or married to a sibling of a parent. Aunts who are related by birth are second-degree relatives. Known alternate terms include auntie or aunty. Children in other cultures and families may ref ...
of $A$". The relation "$A$ is a
sibling A sibling is a relative that shares at least one parent with the subject. A male sibling is a brother and a female sibling is a sister. A person with no siblings is an only child. While some circumstances can cause siblings to be raised sep ...
of $B$" is its own converse, since it is a symmetric relation.

# Properties

In the
monoid In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0. Monoids a ...
of binary endorelations on a set (with the
binary operation In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary ope ...
on relations being the
composition of relations In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
), the converse relation does not satisfy the definition of an inverse from group theory, that is, if $L$ is an arbitrary relation on $X,$ then $L \circ L^$ does equal the
identity relation In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on $X$ in general. The converse relation does satisfy the (weaker) axioms of a
semigroup with involution In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered ...
: $\left\left(L^\right\right)^ = L$ and $\left(L \circ R\right)^ = R^ \circ L^.$ Since one may generally consider relations between different sets (which form a
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) * ...
rather than a monoid, namely the
category of relations In mathematics, the category Rel has the class of sets as objects and binary relations as morphisms. A morphism (or arrow) ''R'' : ''A'' → ''B'' in this category is a relation between the sets ''A'' and ''B'', so . The composition of two rel ...
Rel), in this context the converse relation conforms to the axioms of a dagger category (aka category with involution). A relation equal to its converse is a
symmetric relation A symmetric relation is a type of binary relation. An example is the relation "is equal to", because if ''a'' = ''b'' is true then ''b'' = ''a'' is also true. Formally, a binary relation ''R'' over a set ''X'' is symmetric if: :\forall a, b \in X ...
; 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 relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
s, Rel is also an ordered category. In the
calculus of relations In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables. What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate fo ...
, (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 Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, antisymmetric, asymmetric, transitive, connected, trichotomous, a
partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
,
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexi ...
, strict weak order,
total preorder In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered se ...
(weak order), or an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
, its converse is too.

# Inverses

If $I$ represents the identity relation, then a relation $R$ may have an inverse as follows: $R$ is called ; :if there exists a relation $X,$ called a of $R,$ that satisfies $R \circ X = I.$ ; :if there exists a relation $Y,$ called a of $R,$ that satisfies $Y \circ R = I.$ ; :if it is both right-invertible and left-invertible. For an invertible homogeneous relation $R,$ all right and left inverses coincide; this unique set is called its and it is denoted by $R^.$ In this case, $R^ = R^$ holds.

## Converse relation of a function

A
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orien ...
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 $f : X \to Y$ is the relation $f^ \subseteq Y \times X$ defined by the $\operatorname\, f^ = \.$ This is not necessarily a function: One necessary condition is that $f$ be
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
, since else $f^$ is
multi-valued In mathematics, a multivalued function, also called multifunction, many-valued function, set-valued function, is similar to a function, but may associate several values to each input. More precisely, a multivalued function from a domain to a ...
. This condition is sufficient for $f^$ being a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is ...
, and it is clear that $f^$ then is a (total) function
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
$f$ is
surjective In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
. In that case, meaning if $f$ is
bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
, $f^$ may be called the
inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X\ ...
of $f.$ For example, the function $f\left(x\right) = 2x + 2$ has the inverse function $f^\left(x\right) = \frac - 1.$ However, the function $g\left(x\right) = x^2$ has the inverse relation $g^\left(x\right) = \pm \sqrt,$ which is not a function, being multi-valued.

# Composition with relation

Using
composition of relations In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
, 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 The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. A ...
, A ∪ B ⊂ U ⇔ A ⊂ U ⊃ B ⇔ A ⊂ ⊃ B. Now consider the
set membership In mathematics, an element (or member) of a set is any one of the distinct objects that belong to that set. Sets Writing A = \ means that the elements of the set are the numbers 1, 2, 3 and 4. Sets of elements of , for example \, are subsets ...
relation and its converse. :$A \ni z \in B \Leftrightarrow z \in A \cap B \Leftrightarrow A \cap B \ne \empty.$ Thus $A \ni \in B \Leftrightarrow A \cap B \ne \empty .$ The opposite composition $\in \ni$ is the universal relation. The compositions are used to classify relations according to type: for a relation ''Q'', when the
identity relation In mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
on the range of ''Q'' contains ''Q''T''Q'', then ''Q'' is called ''univalent''. When the identity relation on the domain of ''Q'' is contained in ''Q Q''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''.
Gunther Schmidt Gunther Schmidt (born 1939, Rüdersdorf) is a German mathematician who works also in informatics. Life Schmidt began studying Mathematics in 1957 at Göttingen University. His academic teachers were in particular Kurt Reidemeister, Wilhe ...
& Michael Winter (2018) ''Relational Topology'', Springer Lecture Notes in Mathematics #2208, page 8,
If ''Q'' is univalent, then ''QQ''T is an equivalence relation on the domain of ''Q'', see Transitive relation#Related properties.