Set of Mappings which map to Same Element induces Equivalence Relation
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
- 1975: Bert Mendelson: Introduction to Topology (3rd ed.) ... (previous) ... (next): Chapter $1$: Theory of Sets: $\S 7$: Relations: Exercise $5$