0
$\begingroup$

Given a function $f : A → B$, let $R$ be the relation defined on $A$ by $aRa′$ whenever $f(a) = f(a′)$. Prove that $R$ is an equivalence relation and determine the equivalence classes.

To prove that $R$ is an equivalence relation, I know I have to show that R is reflexive, symmetric, and transitive. And from there, I can also determine the equivalence classes. However, I'm not sure where exactly to start. What exactly is the relation?

$\endgroup$
  • 1
    $\begingroup$ $R \subseteq A \times A : (a,b) \in R$ iff $f(a)=f(b)$. Thus, e.g. for reflexivity, $(a,a) \in R$ because, obviously: $f(a)=f(a)$. $\endgroup$ – Mauro ALLEGRANZA Apr 24 '16 at 17:17
  • 1
    $\begingroup$ As a matter of fact, this is the easiest and also only example of equivalence relations $\endgroup$ – Hagen von Eitzen Apr 24 '16 at 17:20
0
$\begingroup$

$f(a) = f(a) \implies R$ is reflexive, and if $aRb \implies f(a) = f(b) \implies f(b) = f(a) \implies bRa$, hence $R$ is symmetric. And if $aRb, bRc \implies f(a) = f(b), f(b) = f(c) \implies f(a) = f(c) \implies aRc$. Thus $R$ is equivalence relation on $A$. The equivalent classes consist of the $f^{-1}(x)'s $ whereas $x \in $ the range of $f$.

$\endgroup$
  • $\begingroup$ How can we tell that the equivalent classes consist of that? $\endgroup$ – discsq12 Apr 24 '16 at 22:44
0
$\begingroup$

It is equivalent to speak about an equivalence relation $R$ on a set $A$ and a partition of $A$ into its classes of equivalence.

Hence there is a natural partition by the preimages $f^{-1}(b)$ for all $b \in B$ (which are either disjoint or identical), in other terms:

$$aRa' \Leftrightarrow f(a)=f(a') \Leftrightarrow a \ \text{and} \ a' \ \text{belong to the same preimage} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.