Prove that $ f $ is a function

Question

$ \textbf{Question} $ (from Dudley's $ \textit{Real Analysis and Probability} $):

Let $ E \subset X \times X $ be an equivalence relation on a set $ X $ and let $ \displaystyle f(x) := \{y \in X \; | \; yEx\} $ and $ f(y) = \{x \in X \; | \; xEy\}. $

Prove that $ f $ is a function iff $ f(x) = f(y). $

For the only if part, since $ xEy = yEx, $ we must have $ \displaystyle f(x) = \{y \in X \; | \; yEx\} = f(y) = \{x \in X \; | \; xEy\}. $ So at this point the set $ f(x) $ and $ f(y) $ are equal, but I don't know why the theorem requires that $ f $ must be a function in this case.

Now for the if part, if $ f(x) = f(y), $ then $ \displaystyle \{y \in X \; | \; yEx\} = \{x \in X \; | \; xEy\}, $ but this certainly doesn't imply that $ f $ must be a function. For example, if $ f(x) = \{x, y, z \} $ for some $ y, z \in X $ such that $ zEx $ and $ yEx, $ then $ f(y) = \{y, x, z\}. $

I have no direction to go for this problem so any help would be appreciated.

Answer 1

The exact passage in the book is as follows:

Given an equivalence relation $E$, an equivalence class is a set of the form $\{y\in X: yEx\}$ for any $x\in X$. It follows from the definition of equivalence relations that two equivalence classes are either disjoint or identical. Let $f(x):=\{y\in X: yEx\}$. Then $f$ is a function and $xEy$ if and only if $f(x)=f(y)$, so $E=E_f$, and every equivalence relation can be written in the form $E_f$.

Let me first introduce some new notation. I define $\bar{x}=\{y\in X: xEy\}$ where $x\in X$.

In this passage it is implied that $f\subset X\times S$ where $S=\{\bar{x}: x\in X, \}$.

So given any function $f\subset X\times Y$ we can form an equivalance relation $E\subset X\times X$ by defining $E=\{(x_1,x_2)\in X\times X: f(x_1)=f(x_2)\}$.

Vice verse given an equivalance relation E, we can form a function $f\subset X\times S$ by defining $f(x):= \bar{x}$. Clearly if $f(x)= \bar{x_1}$ and $f(x)=\bar{x_2}$ by equivalance $\bar{x_1}=\bar{x_2}$ so $f$ is indeed a function.

Note: Functions are seen in terms of relations in this chapter of the book so if you are given a function $f:\mathbb{R}\to \mathbb{R}$ where $f(x)=x^2$. In this chapter $f$ would be instead rewritten as $f:=\{(x,x^2): x\in X\}$ or in general given $f:X\to Y$ we define $f$ to be $f:=\{(x,f(x)): x\in X, f(x)\in Y\}$.