Equivalence relation and Functions

• Dec 1st 2010, 06:35 PM
mremwo
Equivalence relation and Functions
The problem is:
"Suppose that A is a nonempty set and R is an equivalence relation on A. Show that there is a function f with A as its domain such that (x,y) are elements of R if and only if f(x)=f(y)"

I don't understand how to connect a relation with a function

thank you
• Dec 1st 2010, 06:39 PM
Drexel28
Quote:

Originally Posted by mremwo
The problem is:
"Suppose that A is a nonempty set and R is an equivalence relation on A. Show that there is a function f with A as its domain such that (x,y) are elements of R if and only if f(x)=f(y)"

I don't understand how to connect a relation with a function

thank you

A function is actually a relation, but that's just not how many people think about it. Consider that a function is really just it's graph $\Gamma_f=\left\{(x,f(x)):x\in X\right\}$. This $\Gamma_f$ is the relation.
• Dec 1st 2010, 07:25 PM
topspin1617
Try finding a function $f:A\rightarrow \mathcal{P}(A)$ (the power set of $A$) such that two elements are in the same equivalence class under $R$ if and only if they have the same image under $f$. Can you think of a natural choice for the image under $f$ of an element from $A$?
• Dec 1st 2010, 07:28 PM
Drexel28
Quote:

Originally Posted by topspin1617
Try finding a function $f:A\rightarrow \mathcal{P}(A)$ (the power set of $A$) such that two elements are in the same equivalence class under $R$ if and only if they have the same image under $f$. Can you think of a natural choice for the image under $f$ of an element from $A$?

What does this have to do with anything? Unless you really meant $2^{A\times A}$.
• Dec 1st 2010, 07:33 PM
topspin1617
No. The function $f:A\rightarrow \mathcal{P}(A)$ given by $x \mapsto [x]$ does exactly what the question asks.
• Dec 1st 2010, 07:36 PM
Drexel28
Quote:

Originally Posted by topspin1617
No. The function $f:A\rightarrow \mathcal{P}(A)$ given by $x \mapsto [x]$ does exactly what the question asks.

Touche sir, touche. I misread the question.