Set of Mappings which map to Same Element induces Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $X$ and $Y$ be sets.

Let $E$ be the set of all mappings from $X$ to $Y$.

Let $b \in X$.

Let $\RR \subseteq E \times E$ be the relation on $E$ defined as:

$\RR := \set {\tuple {f, g} \in \RR: \map f b = \map g b}$


Then $\RR$ is an equivalence relation.


Proof

Checking in turn each of the criteria for equivalence:


Reflexivity

$\forall f \in E: \map f b = \map f b$

That is:

$\forall f \in E: \tuple {f, f} \in \RR$

Thus $\RR$ is seen to be reflexive.

$\Box$


Symmetry

\(\ds \tuple {f, g}\) \(\in\) \(\ds \RR\)
\(\ds \leadsto \ \ \) \(\ds \map g b\) \(=\) \(\ds \map f b\)
\(\ds \leadsto \ \ \) \(\ds \map g b\) \(=\) \(\ds \map f b\)
\(\ds \leadsto \ \ \) \(\ds \tuple {g, f}\) \(\in\) \(\ds \RR\)

Thus $\RR$ is seen to be symmetric.

$\Box$


Transitivity

Let $f, g, h \in E$.

\(\ds \tuple {f, g}\) \(\in\) \(\ds \RR\)
\(\, \ds \land \, \) \(\ds \tuple {g, h}\) \(\in\) \(\ds \RR\)
\(\ds \leadsto \ \ \) \(\ds \map f b\) \(=\) \(\ds \map g b\)
\(\, \ds \land \, \) \(\ds \map g b\) \(=\) \(\ds \map h b\)
\(\ds \leadsto \ \ \) \(\ds \map f b\) \(=\) \(\ds \map h b\)
\(\ds \leadsto \ \ \) \(\ds \tuple {f, h}\) \(\in\) \(\ds \RR\)

Thus $\RR$ is seen to be transitive.

$\Box$


$\RR$ has been shown to be reflexive, symmetric and transitive.

Hence by definition it is an equivalence relation.

$\blacksquare$


Sources