2
$\begingroup$

Let $A$ be a finite set and $\mathcal R$ an equivalence relation in A. Prove that exists a function $f: A \to \Bbb N$ such that $\forall a, b \in A$ the following is true: $$a \mathcal R b \iff f(a) = f(b)$$

I've already proved that $f(a) = f(b)$ is an equivalence relation. $\mathcal R$ is a subset of the cartesian product $A \times A$, and I know that for $f$ to be a function each element $a \in A$ has to have one and only one image. If any two elements in the domain have the same image I could think of a constant function, that maps every element to the same $n \in \Bbb N$ ... but if this is right, I still don't know how to prove it. So, is ok to think the problem like this? If it is, how would you prove it? I would appreciate your help or tips, thanks!

$\endgroup$
3
$\begingroup$

HINT: Show that the relation has only finitely many equivalence classes, say $C_1,\ldots,C_m$, and use the subscripts on the equivalence classes to define your function $f$.

$\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.