Diagonal Relation is Left Identity

From ProofWiki
Jump to: navigation, search

Theorem

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


Then:

$\Delta_T \circ \mathcal R = \mathcal R$

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


Proof

We use the definition of relation equality, as follows:


Equality of Domains

The domains of $\mathcal R$ and $\Delta_T \circ \mathcal R$ are equal from Domain of Composite Relation:

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


Equality of Codomains

From Codomain of Composite Relation, the codomains of $\Delta_T \circ \mathcal R$ and $\Delta_T$ are both equal to $T$.

But from the definition of the diagonal relation, the codomain of $\Delta_T$ is $\Dom {\Delta_T} = T$.


Equality of Relations

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

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

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

$\tuple {y, z} \in \Delta_T \implies y = z$

Hence:

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


But as $\forall y \in T: \tuple {y, y} \in \Delta_T$, this means:

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

That is:

$\Delta_T \circ \mathcal R = \mathcal R$

Hence the result.

$\blacksquare$


Also see


Sources