Discrete mathematics, equivalence relations, functions.

142 Views Asked by At

I'd like some insight on how to 'solve' this problem (more towards understanding what the problem is asking)

Suppose that $A$ is a nonempty set and $\mathcal{R}$ is an equivalence relation on $A$. Show that there is a function $f$ with $A$ as its domain such that $(x,y) \in \mathcal{R}$ if and only if $f(x) = f(y)$.

I do not understand the idea of "how to show that there is a function $f$". The elements of $A$ are arbitrary, so there is nothing specified about what's actually in $A$ other than it is a non-empty set. I also know that $\mathcal{R}$ is reflexive, symmetric and transitive.

I feel that the function f is somewhat related to the relation $\mathcal{R}$ in the problem, and what I'm supposed to do is show that this function is $\mathcal{R}$.

Am I completely missing the point or am I on the right track?

1

There are 1 best solutions below

1
On

You are not completely missing the point, but you're a bit off the mark.

Firstly, let go of the fact that you know nothing about the elements of the set $A$. It really is not important. (Incidentally, the claim remains true even if $A$ is empty.) What you have to do is construct the function $f$. To construct a function you must specify its domain and codomain. In this case the domain is given to be $A$. You must figure out what the codomain of the function must be, and then you must define the function. Now, certainly, the fact that you are given an equivalence relation on $A$ is crucial. So, what would be a natural candidate for the codomain of $f$? In your studies of equivalence relations, have you seen how to construct the quotient set? It's the set of equivalence classes: $A/{\sim} = \{[x]\mid x\in A\}$. Can you now think of a function $f\colon A\to A/\sim$? There is really only one sensible way for defining such a function, and then you'll be able to show it satisfies the required property.