1. ## Relations

The question is as follows,

Assume $q:X \rightarrow Y$ is onto. Define a relation of $X$ given by $x_1 {\sim}_q x_2$ iff $q(x_1) = q(x_2)$.

1) Show that every equivalence class with respect to ${\sim}_q$ is of the form $q^{-1}(\{y\})$ for some element $y \in Y$.

So, the equivalence classes of $x$ are given by

$[x] = \{x^{\prime} \in X : q(x) = q(x^{\prime})\}$

which I possibly could write as

$[x] = \{x^{\prime} \in X : x = q^{-1}(q(x^{\prime}))\}$

where, $q(x^{\prime}) \in Y$. But, how can this inverse exist in the first place; he defined the map to be onto, and not one-to-one! Am I thinking about this the wrong way?

2) Show that the there is a one-to-one correspondence between $Y$ and the set of equivalence classes of ${\sim}_q$

My argument goes a little like this; we have our set $Y$, and denote our set ${\sim}_q$ by $\{[x_1], [x_2], \ldots, [x_n]\}$. Then, we have that each of these elements are unique. If this is the case, then each equivalence on the set $X$ corresponds to a unique element on the set $Y$. This satisfies injectivity.

I'm not sure if this is even a correct argument, or if I'm on the right tracks, and how would this all be formalised?

3) Prove that for every equivalence relation $\sim$ on $X$, one can find a $Y$ and an onto map $q:X \rightarrow Y$ such that $\sim = \sim$

I have not got a clue what on earth this is even asking! Any help on this would be much appreciated.

Thank you all in advance,

HTale.

2. Originally Posted by HTale

1) Show that every equivalence class with respect to ${\sim}_q$ is of the form $q^{-1}(\{y\})$ for some element $y \in Y$.

So, the equivalence classes of $x$ are given by

$[x] = \{x^{\prime} \in X : q(x) = q(x^{\prime})\}$

which I possibly could write as

$[x] = \{x^{\prime} \in X : x = q^{-1}(q(x^{\prime}))\}$

where, $q(x^{\prime}) \in Y$. But, how can this inverse exist in the first place; he defined the map to be onto, and not one-to-one! Am I thinking about this the wrong way?
For $x\in X$ we let $[x] = \{ x' \in X | q(x') = q(x) \}$.
Let $y = q(x)$ then $q^{-1} (\{y\}) = \{ x' \in X | q(x') \in \{ y\} \} = \{ x' \in X | q(x') = q(x) \} = [x]$.

3. Originally Posted by HTale
3) Prove that for every equivalence relation $\sim$ on $X$, one can find a $Y$ and an onto map $q:X \rightarrow Y$ such that $\sim = \sim$
All three of these turn on the simple fact that there is a one-to-one correspondence between equivalence relations on a set and partitions of that set. So to see #3, consider the partition induced by an equivalence relation on X [the equivalence classes]. Because each cell of a partition is not empty and no two distinct cells overlap, we can use a choice function to choose one element in each cell. That collection becomes Y. Then map any element in a cell to the chosen representative of that cell.