Let $\sim$ be some equivalence relation on $X$. Is there some function with domain $X$ such that $f(x)=f(y)$ exactly when $x\sim y$?

Question

1. Suppose that $X$ is a set.

a) Let $f$ be some function with domain $X$ (and codomain anything you like), and say that $x \sim y$ means $f(x)=f(y)$. Is $\sim$ an equivalence relation? If it is, then prove it; if not then give a counterexample.

b) Let $\sim$ be some equivalence relation on $X$. Is there some function with domain $X$ such that $f(x)=f(y)$ exactly when $x\sim y$? If there is, then prove it; if not then give a counterexample.

I proved part a, but I don't really understand part b. Wouldn't this be true for any function that exists? Why would someone ask me this question? I think I missed something. Because it seems this is always true. If $x$ is related to $y$, then we immediately know $f(x) = f(y)$, so of course this would be true for any function. If $x$ is not related to $y$ , then we know for sure $f(x) \neq f(y)$ since if it was the case them, $x$ would be related to $y$ . What am I missing?

Answer 1

I think you’re confusing the relation $\sim$ in the first part with the relation $\sim$ in the second part. In the first part, you have defined the relation such that $x\sim y$ if and only if $f(x) = f(y)$. Then you prove that this is an equivalence relation.

In the second part, you are given a new relation $\sim$, which is an equivalence relation on $X$. Then you have to prove that there exists or doesn’t exist a function $f$ such that $x\sim y\iff f(x) =f(y)$.

Not every function satisfies the condition in the second part. I will leave it to you to find if there does exist a function that does satisfy the conditions. The following is an example of a function that doesn’t satisfy the condition.

Let $X$ be the set of integers $Z$ and $\sim$ denote the modular arithmetic relation on $Z$ with the modulus being $2$. That is, $x\sim y\iff x\equiv y( \text{mod } 2)$

Define $f : Z \to Z$ by $$f(x) = x$$ For this function, $f(x) = f(y)$ only when $x=y$. Thus, this does not satisfy the condition in the second part as there exist integers $x$ and $y$ such that $x\sim y$, but $x\ne y$ and therefore $f(x)\ne f(y)$. For a specific example, note that $2\sim 4$ as $2\equiv 4 (\text{mod } 2)$, but $f(2) \ne f(4)$.

Answer 2

The ~ and f for part b are not necessarily the same as part a. The question is asking that for any ~, even if it's not the same as part a, there exists such an f.

Answer 3

For part B, the difficulty is how to pick a distinct fixed element $x_e$ consistently from an arbitrary fixed set $S$ for any element $y \in X$ from a given fixed equivalence class. If we can consistently do this then we can just set $f(y) = x_e$ and your condition is satisfied. The answer is probably in cardinals. If the number of equivalence classes is countable then we can associate with each equivalence class an integer consistently by the definition of the fact number of equivalence class is countable. Similarly we can find the function, for any cardinality equal to number of equivalence classes where the definition of cardinality is based on finding an 1-1 and onto function from a given set. I leave you with this hint, Check out different cardinal numbers and their definition and try to come up with relation with number of equivalence classes equal to that particular cardinality and try finding a mapping based on the definition of cardinality.