One-to-Many Relation Composite with Inverse is Coreflexive

From ProofWiki
Jump to navigation Jump to search


Let $\RR \subseteq S \times S$ be a relation which is one-to-many.

Then the composite of $\RR$ with its inverse is a coreflexive relation:

$\RR^{-1} \circ \RR \subseteq \Delta_X$

That is, by Relation is Symmetric and Antisymmetric iff Coreflexive, $\RR^{-1} \circ \RR$ is both symmetric and antisymmetric.


As $\RR$ is one-to-many, it follows from Inverse of Many-to-One Relation is One-to-Many that $\RR^{-1}$ is many-to-one.

Let $\tuple {x, z} \in \RR^{-1} \circ \RR$.


$\exists y \in S: \tuple {x, y} \in \RR, \tuple {y, z} \in \RR^{-1}$

As $\tuple {x, y} \in \RR$, from the definition of inverse relation:

$\tuple {y, x} \in \RR^{-1}$

As $\RR^{-1}$ is many-to-one:

$\tuple {y, z} = \tuple {y, x}$

Thus if $\tuple {x, z} \in \RR^{-1} \circ \RR$, it follows that:

$\tuple {x, z} = \tuple {x, x}$


$\RR^{-1} \circ \RR \subseteq \Delta_X$

The result follows by definition of coreflexive relation.