Diagonal Relation is Right Identity

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R \subseteq S \times T$ be a relation on $S \times T$.


Then:

$\mathcal R \circ \Delta_S = \mathcal R$

where $\Delta_S$ is the diagonal relation on $S$, and $\circ$ signifies composition of relations.


Proof

We use the definition of relation equality, as follows:


Equality of Codomains

The codomains of $\mathcal R$ and $\mathcal R \circ \Delta_S$ are both equal to $T$ from Codomain of Composite Relation.


Equality of Domains

The domains of $\mathcal R$ and $\mathcal R \circ \Delta_S$ are also easily shown to be equal.

From Domain of Composite Relation:

$\Dom {\mathcal R \circ \Delta_S} = \Dom {\Delta_S}$

But from the definition of the diagonal relation:

$\Dom {\Delta_S} = \Img {\Delta_S} = S$


Equality of Relations

The composite of $\Delta_S$ and $\mathcal R$ is defined as:

$\mathcal R \circ \Delta_S = \set {\tuple {x, z} \in S \times T: \exists y \in S: \tuple {x, y} \in \Delta_S \land \tuple {y, z} \in \mathcal R}$

But by definition of the diagonal relation on $S$, we have that:

$\tuple {x, y} \in \Delta_S \implies x = y$

Hence:

$\mathcal R \circ \Delta_S = \set {\tuple {y, z} \in S \times T: \exists y \in S: \tuple {y, y} \in \Delta_S \land \tuple {y, z} \in \mathcal R}$


But as $\forall y \in S: \tuple {y, y} \in \Delta_S$, this means:

$\mathcal R \circ \Delta_S = \set {\tuple {y, z} \in S \times T: \tuple {y, z} \in \mathcal R}$

That is:

$\mathcal R \circ \Delta_S = \mathcal R$

Hence the result.

$\blacksquare$


Also see


Sources