The Converse Relation as an Operator

Introduction

Every relation $R$ has a converse $R^{-1}$, obtained by exchanging the two coordinates of each of its pairs, and the passage $R \mapsto R^{-1}$ is a map on the class of relations. This article studies that map as an operator: it computes how the converse behaves under the composition of relations, under the inclusion order, and under iteration, and it uses the two-element group that the operator generates — the identity and the converse — to decompose the relations into the symmetric ones and the pairs of mutually converse relations, with the symmetrisation $R \mapsto R \cup R^{-1}$ as the canonical map onto the symmetric part.

The article presupposes Sets, Functions and Relations, where relations, the converse, the composite $S \circ R$ and the identity relation $\Delta_X$ are defined, and Order Theory and Lattices, for the inclusion order and the operations of the lattice of subsets. It works with relations on a fixed set $X$ unless it says otherwise, and it uses no structure from a later part.

The converse is placed in the operator layer deliberately. The same map read as an operation of an algebra — the relation algebra axioms, in which the converse is one of the primitive symbols and composition is the product — belongs to Relation Algebras and the Converse, in the * group of this category; the converse read as an adjoint, with a unit and a counit, belongs to The Converse as an Adjoint and The Converse Relation as an Adjoint, in the last group of this category. This article uses neither reading: it treats $R \mapsto R^{-1}$ as an operator on the set of relations and computes with it directly. Nothing topological, metric or linear is used, and no group structure is imported: the only group that occurs is the two-element group generated by the converse, and it is computed from the operator itself.

The Converse Operator

Definition and Elementary Laws

Let $X$ be a set and let $\operatorname{Rel}(X) = \mathcal{P}(X \times X)$ be the set of relations on $X$, ordered by inclusion. For $R \subseteq X \times X$ the converse is

$$ R^{-1} = \{(y,x) : (x,y) \in R\}. $$

Definition. The converse operator on $\operatorname{Rel}(X)$ is the map

$$ c : \operatorname{Rel}(X) \to \operatorname{Rel}(X), \qquad c(R) = R^{-1}. $$

Proposition. The operator $c$ satisfies the following for all $R, S \in \operatorname{Rel}(X)$.

$c(c(R)) = R$.
$R \subseteq S$ if and only if $c(R) \subseteq c(S)$.
$c(\emptyset) = \emptyset$ and $c(X \times X) = X \times X$, and $c(\Delta_X) = \Delta_X$.
$c(R \cup S) = c(R) \cup c(S)$, $c(R \cap S) = c(R) \cap c(S)$, and $c(\overline{R}) = \overline{c(R)}$, where $\overline{R} = (X \times X) \setminus R$.

Proof. (1) $c(c(R)) = (R^{-1})^{-1} = {(z,y) : (y,z) \in R^{-1}} = {(z,y) : (z,y) \in R} = R$. (2) If $R \subseteq S$ and $(y,x) \in R^{-1}$ then $(x,y) \in R \subseteq S$, so $(y,x) \in S^{-1}$; the converse implication is (1) applied to $S \subseteq R$. (3) Immediate, since $\emptyset$, $X \times X$ and $\Delta_X$ are each their own converse. (4) The first two are the elementwise reading of the definition: $(y,x) \in (R \cup S)^{-1}$ exactly when $(x,y) \in R \cup S$, that is, when $(y,x)$ lies in $R^{-1} \cup S^{-1}$, and the same with "and" for the intersection. For the complement, $(y,x) \in c(\overline R)$ exactly when $(x,y) \notin R$, that is, when $(y,x) \notin c(R)$, that is, when $(y,x) \in \overline{c(R)}$.

The Two-Element Group

Property (1) says that $c$ is an involution of $\operatorname{Rel}(X)$; by (2) it is an order automorphism. The maps $\mathrm{id}$ and $c$ therefore form a group of operators,

$$ C_2 = \{\mathrm{id}, c\}, \qquad c^2 = \mathrm{id}, $$

acting on $\operatorname{Rel}(X)$. The action is what the rest of the article computes with: the orbit of a relation $R$ under $C_2$ is the set

$$ C_2 \cdot R = \{R, R^{-1}\}, $$

which has one element when $R = R^{-1}$ and two otherwise.

Definition. A relation is symmetric if $R = R^{-1}$, and the set of symmetric relations is written $\operatorname{SymRel}(X)$.

A relation and its converse are the two halves of the same object: $(x,y) \in R$ if and only if $(y,x) \in R^{-1}$. The operator $c$ is the identity exactly on the symmetric relations, so $\operatorname{SymRel}(X)$ is the fixed-point set of the operator, and the orbits of the complementary relations pair off the non-symmetric ones.

Example. On $X = \{1,2,3\}$ the relation $R = \{(1,2),(2,3)\}$ has converse $R^{-1} = {(2,1),(3,2)}$, and $R \neq R^{-1}$; the orbit is ${R, R^{-1}}$. The relation $S = {(1,2),(2,1)}$ satisfies $S = S^{-1}$ and is symmetric, so its orbit is the singleton ${S}$.

Example. The order relation $\leq$ on a partially ordered set is reflexive and antisymmetric, and its converse is the opposite order $\geq$; the pair $\{\leq, \geq\}$ is the standard orbit of size two, and the symmetric relation $\leq \cap \geq$ is the diagonal, because antisymmetry says that $x \leq y$ and $y \leq x$ force $x = y$.

Composition and Iteration

The Anti-Automorphism Property

Recall that the composite of $R$ with $S$ is

$$ S \circ R = \{(x,z) : \text{there is } y \text{ with } (x,y) \in R \text{ and } (y,z) \in S\}. $$

Proposition. For all $R, S \in \operatorname{Rel}(X)$,

$$ (S \circ R)^{-1} = R^{-1} \circ S^{-1}. $$

Proof. Let $(z,x) \in (S \circ R)^{-1}$. Then $(x,z) \in S \circ R$, so there is $y$ with $(x,y) \in R$ and $(y,z) \in S$. Then $(y,x) \in R^{-1}$ and $(z,y) \in S^{-1}$, so $(z,x) \in R^{-1} \circ S^{-1}$. Each step is reversible, which gives the reverse inclusion.

Thus $c$ is an anti-automorphism of the monoid $(\operatorname{Rel}(X), \circ, \Delta_X)$: it reverses the order of the factors. The identity relation is fixed by $c$, by property (3), so $c$ is an anti-automorphism of the monoid and not merely of the semigroup. A monoid with an involution that reverses the product is called an involutive semigroup when the identity is not required to be fixed; here the identity is fixed, and the pair $(\operatorname{Rel}(X), \circ, c)$ is the standard example. The categorical name for the same datum is a dagger, and the general theory of involutions of this kind on the morphisms of a category is developed in Involutive Categories and the Dagger Functor, in the * group of this category; it is not used here.

Proposition (composites on one side). For every $R \in \operatorname{Rel}(X)$ the relations $R \circ R^{-1}$ and $R^{-1} \circ R$ are symmetric.

Proof. By the anti-automorphism property and property (1), $(R \circ R^{-1})^{-1} = (R^{-1})^{-1} \circ R^{-1} = R \circ R^{-1}$, and dually for $R^{-1} \circ R$.

Remark. The two composites are the relations of sharing a preimage and of sharing an image: $(x, z) \in R \circ R^{-1}$ exactly when there is a $y$ with $(y,x) \in R$ and $(y,z) \in R$, so that $x$ and $z$ have a common preimage under $R$, while $(x,z) \in R^{-1} \circ R$ exactly when there is a $y$ with $(x,y) \in R$ and $(z,y) \in R$, so that $x$ and $z$ have a common image. They are therefore the two natural symmetric relations attached to $R$.

Powers and the Closures

For $n \geq 1$ let $R^n = R \circ R \circ \cdots \circ R$ be the $n$-fold composite, and put $R^0 = \Delta_X$.

Proposition. For all $n \geq 0$, $(R^n)^{-1} = (R^{-1})^n$.

Proof. Induction on $n$: the case $n = 0$ is $c(\Delta_X) = \Delta_X$, and the induction step is $(R^{n+1})^{-1} = (R^n \circ R)^{-1} = R^{-1} \circ (R^n)^{-1} = R^{-1} \circ (R^{-1})^n = (R^{-1})^{n+1}$.

Because $c$ preserves arbitrary unions, by the family case of property (4), it commutes with every closure built from unions of powers.

Definition. The transitive closure of $R$ is $R^{+} = \bigcup_{n \geq 1} R^n$, and the reflexive–transitive closure is $R^{*} = \bigcup_{n \geq 0} R^n$.

Proposition. $(R^{+})^{-1} = (R^{-1})^{+}$ and $(R^{*})^{-1} = (R^{-1})^{*}$.

Proof. By the family case of property (4), $c(\bigcup_n R^n) = \bigcup_n c(R^n) = \bigcup_n (R^{-1})^n$, and the same with the union starting at $n = 0$.

So the operator $c$ commutes with the transitive closure, and a relation is contained in its converse exactly when it is symmetric: $R \subseteq R^{-1}$ implies $R^{-1} \subseteq R$ by applying $c$, so $R = R^{-1}$. The operator therefore cannot be used to orient a relation — a relation that is contained in its converse is already symmetric — and orientation is a genuinely additional datum.

The Lattice of Relations

The Converse as a Lattice Automorphism

The set $\operatorname{Rel}(X) = \mathcal{P}(X \times X)$ is a complete distributive lattice under inclusion, by Order Theory and Lattices, with the union as join, the intersection as meet, $\emptyset$ as least and $X \times X$ as greatest element, and the complement as complementation.

Proposition. The converse operator is a lattice automorphism of $\operatorname{Rel}(X)$: it preserves the order in both directions, the joins, the meets, the least and the greatest elements and the complement.

Proof. This is the conjunction of properties (1) to (4): a bijective map preserving binary joins and meets, together with $c(\emptyset) = \emptyset$ and $c(X \times X) = X \times X$ and the complement, is exactly a lattice automorphism of the power-set algebra.

Thus the converse operator is an element of the group $\operatorname{Aut}(\operatorname{Rel}(X))$ of lattice automorphisms, and it is an involution there. It is an anti-automorphism of the monoid $(\operatorname{Rel}(X), \circ)$, and the contrast is the point: the operator respects the lattice structure and reverses the monoid structure, so the two structures of the set of relations are carried differently by the same map.

The Symmetric Relations

Proposition. The symmetric relations form a sublattice of $\operatorname{Rel}(X)$: they are closed under $\cup$, $\cap$ and the complement, they contain $\emptyset$ and $X \times X$, and they form a complete distributive lattice under inclusion.

Proof. If $R = R^{-1}$ and $S = S^{-1}$ then $(R \cup S)^{-1} = R^{-1} \cup S^{-1} = R \cup S$, and the same with the intersection and the complement; the constants are symmetric. The lattice axioms are inherited from $\operatorname{Rel}(X)$, and closure under arbitrary unions follows directly. So $\operatorname{SymRel}(X)$ is a sublattice in the strong sense: it is closed under the operations and under the constants, and it is complete.

The symmetric relations are not closed under composition. If $R$ and $S$ are symmetric then $(S \circ R)^{-1} = R^{-1} \circ S^{-1} = R \circ S$, so $S \circ R$ is symmetric exactly when $S \circ R = R \circ S$, that is, when the two relations commute. A relation that is symmetric and transitive is an equivalence relation on the set of elements it relates to something; the symmetric relations that are also transitive are therefore the equivalence relations on the subsets of $X$.

Example. On $\{1,2\}$ there are eight symmetric relations: the three pairs $(1,1)$ and $(2,2)$ and the pair of pairs $\{(1,2),(2,1)\}$ may be chosen independently, and the eight form an eight-element Boolean lattice. The remaining eight relations fall into four orbits of size two under the converse operator.

Mutually Converse Pairs and Symmetrisation

Orbits and the Symmetrisation

Definition. The symmetrisation of a relation $R$ is

$$ R^{\mathrm{s}} = R \cup R^{-1}. $$

The relation $R^{\mathrm{s}}$ is symmetric, because $(R \cup R^{-1})^{-1} = R^{-1} \cup R = R^{\mathrm{s}}$.

Proposition. The symmetrisation operator $(-)^{\mathrm{s}} : \operatorname{Rel}(X) \to \operatorname{SymRel}(X)$ is monotone, extensive ($R \subseteq R^{\mathrm{s}}$) and idempotent, and it is the least symmetric relation containing $R$; it preserves arbitrary unions.

Proof. Monotonicity and extensiveness are immediate from the definition. Idempotence: $(R^{\mathrm{s}})^{\mathrm{s}} = R^{\mathrm{s}}$, because $R^{\mathrm{s}}$ is already symmetric. If $T$ is symmetric and $R \subseteq T$ then $R^{-1} \subseteq T^{-1} = T$, so $R^{\mathrm{s}} \subseteq T$; hence $R^{\mathrm{s}}$ is the least symmetric relation containing $R$. Finally $(\bigcup_i R_i)^{\mathrm{s}} = \bigcup_i R_i \cup \bigcup_i R_i^{-1} = \bigcup_i (R_i \cup R_i^{-1})$, so the operator commutes with unions.

A monotone, extensive, idempotent operator is a closure operator, in the sense of Order Theory and Lattices, and the symmetrisation is one: its closed elements are exactly the symmetric relations, and it is the least closure operator on $\operatorname{Rel}(X)$ with that property. The general theory of closure operators on a lattice, and in particular the consequence operator of a logic, is the subject of Closure Operators and the Consequence Operator, in this group; the symmetrisation is its first example on the lattice of relations.

Remark. The symmetrisation is not the only closure operator attached to $c$. The reflexive–transitive–symmetric closure, which is the transitive closure of $R^{\mathrm{s}}$ and is written $R^{\mathrm{eq}}$, is the smallest equivalence relation containing $R$; the operator $R \mapsto R^{\mathrm{eq}}$ is again monotone, extensive and idempotent, and it is the one used to generate the equivalence relation of a partition in Sets, Functions and Relations. It is the composite of the symmetrisation with the transitive closure, and it commutes with $c$ by the results above.

The Symmetric Interior and the Asymmetric Part

The operator $c$ gives a second canonical operator beside the symmetrisation.

Definition. The symmetric interior of $R$ is

$$ R^{\mathrm{i}} = R \cap R^{-1}, $$

and the asymmetric part of $R$ is $R^{\mathrm{a}} = R \setminus R^{-1}$.

Proposition. For every relation $R$ the following hold.

$R^{\mathrm{i}}$ is the greatest symmetric relation contained in $R$.
$R^{\mathrm{a}}$ satisfies $R^{\mathrm{a}} \cap (R^{\mathrm{a}})^{-1} = \emptyset$.
$R = R^{\mathrm{i}} \cup R^{\mathrm{a}}$, and the two parts are disjoint.

Proof. (1) $R^{\mathrm{i}}$ is symmetric by the formula $(R \cap R^{-1})^{-1} = R^{-1} \cap R$. If $T$ is symmetric and $T \subseteq R$ then $T = T^{-1} \subseteq R^{-1}$, so $T \subseteq R^{\mathrm{i}}$. (2) $(R \setminus R^{-1}) \cap (R^{-1} \setminus R) = \emptyset$, since an element of the left side would lie both in $R^{-1}$ and outside it. (3) Every pair $(x,y) \in R$ either has $(y,x) \in R$, in which case it lies in $R \cap R^{-1}$, or has $(y,x) \notin R$, in which case $(y,x) \notin R^{-1}$ and it lies in $R \setminus R^{-1}$; and the two sets are disjoint because $R \setminus R^{-1}$ excludes $R^{-1}$ while $R \cap R^{-1}$ is inside it.

The operator $(-)^{\mathrm{i}}$ is monotone, intensive ($R^{\mathrm{i}} \subseteq R$) and idempotent, so it is the interior operator dual to the symmetrisation; it is the greatest operator of the form $\mathrm{id} \wedge \theta$ below $c$. The passage from a relation to its symmetric interior is the part of the pair that the operator $c$ cannot move, and the asymmetric part is the part on which $c$ acts without fixed points.

Example. Let $X = \{1,2,3\}$ and $R = \{(1,2),(2,1),(2,3)\}$. Then $R^{-1} = {(2,1),(1,2),(3,2)}$ and

$$ R^{\mathrm{i}} = \{(1,2),(2,1)\}, \qquad R^{\mathrm{a}} = \{(2,3)\}, \qquad R^{\mathrm{s}} = \{(1,2),(2,1),(2,3),(3,2)\}. $$

The decomposition of (3) reads $R = R^{\mathrm{i}} \cup R^{\mathrm{a}}$, and the orbit of $R$ is the pair $\{R, R^{-1}\}$, with $R^{-1} = R^{\mathrm{i}} \cup (R^{\mathrm{a}})^{-1}$.

Summary

The converse operator $c(R) = R^{-1}$ is an involution of the set of relations on a set, an order automorphism for inclusion, and a lattice automorphism of the power-set algebra of $X \times X$; it is an anti-automorphism of the monoid of relations under composition, $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$, and it fixes the identity relation. The operators $\mathrm{id}$ and $c$ form a two-element group whose orbits are the singletons of the symmetric relations and the pairs $\{R,R^{-1}\}$ of mutually converse relations.

The operator commutes with iteration, $(R^n)^{-1} = (R^{-1})^n$, hence with the transitive and the reflexive–transitive closure, and it commutes with arbitrary unions, intersections and complements. The symmetric relations form a complete sublattice of the lattice of relations, but not a submonoid under composition.

Every relation decomposes as the disjoint union of its symmetric interior $R \cap R^{-1}$ and its asymmetric part $R \setminus R^{-1}$; the symmetrisation $R \mapsto R \cup R^{-1}$ is the least symmetric relation containing $R$ and is a closure operator on the lattice of relations whose closed elements are the symmetric relations, while the symmetric interior is the dual interior operator. A relation contained in its converse is already symmetric, so the converse operator does not orient a relation; the adjoint reading, which does supply an orientation through a unit and a counit, is deferred to the last group of this category.

Summary of Notation

Symbol	Meaning
$\operatorname{Rel}(X) = \mathcal{P}(X \times X)$	The set of relations on $X$, a complete distributive lattice
$R^{-1}$	The converse of $R$
$c$	The converse operator, $c(R) = R^{-1}$; an involution
$C_2 = \{\mathrm{id}, c\}$	The two-element group generated by the converse
$S \circ R$	Composite of relations, $(S \circ R)^{-1} = R^{-1} \circ S^{-1}$
$\Delta_X$	The identity relation, fixed by $c$
$R^n$, $R^{+}$, $R^{*}$	Powers of $R$; transitive and reflexive–transitive closures
$\operatorname{SymRel}(X)$	The symmetric relations, the fixed points of $c$
$R^{\mathrm{s}} = R \cup R^{-1}$	Symmetrisation; least symmetric relation containing $R$
$R^{\mathrm{i}} = R \cap R^{-1}$	Symmetric interior; greatest symmetric relation inside $R$
$R^{\mathrm{a}} = R \setminus R^{-1}$	Asymmetric part; $R = R^{\mathrm{i}} \cup R^{\mathrm{a}}$
$R^{\mathrm{eq}}$	Equivalence relation generated by $R$