# Equivalence relations and the axiom of choice

Let $X,Y$ be two sets and $f:X\rightarrow Y$ a function. If we define an equivalence relation $\sim$ on $X$ and we assume that if $x_1\sim x_2$ then $f(x_1)=f(x_2)$, we can define a function $\overline f:X/_\sim\rightarrow Y$ such that $\overline f([x]):=f(x)$. Practically if we have a set of representatives $R$ for the relation $\sim$, then we completely "know" the function $\overline f$. But if we don't assume the axiom of choice, the set $R$ can be empty, is it right?

-
"algebra-precalculus" seems an odd tag for a question about the Axiom of Choice. – Gerry Myerson Jan 25 '13 at 12:08
edited, many thanks. – Dubious Jan 25 '13 at 12:11
Are you trying to define $\bar{f}$ without the Axiom of Choice? – arjafi Jan 25 '13 at 12:13
Yes I'm asking if $\overline f$ exists without assuming the axiom of choice. – Dubious Jan 25 '13 at 12:21
@Galoisfan: my answer explains that it does – Carl Mummert Jan 25 '13 at 12:22

We may not have a set of representatives without the axiom of choice. That doesn't mean the set of representatives is empty, it just means it does not exist - there is no set that satisfies the definition of a set of representatives for $X/\sim$.

But we do not need a set of representatives to define the function $\bar f$ in ZF. It can be defined as follows: $$\bar f (C) = y \Leftrightarrow (\forall x \in C)[f(x) =y]$$ In other words, $\bar f$ is the set of pairs $(C,y)$ where $C \in X/\sim$ and $(\forall x \in C)[f(x) = y]$. That definition of $\bar f$ works in ZF without the axiom of choice. Rather than using representatives for the equivalence classes, we can just use the equivalence classes themselves.

In case you are worried about $X/\sim$ itself, it is definable as $$\{ C \subseteq X : (\exists z)(\forall y)[y \in C \leftrightarrow (y \in X \land y \sim z)]\}$$

-
I don't know if the following remark is helpful: by adopting a more "functional" perspective one could say that to give a set of representatives is to give a function $r \colon X/{\sim} \to X$ right inverse to the projection $X \to X/{\sim}, x \mapsto [x]$. One can then define $\bar{f} = f \circ r$ and check that $\bar{f}$ is independent of the choice of $r$. You show that the detour back to $X$ is unnecessary for establishing the existence of $\bar{f}$. – Martin Jan 25 '13 at 12:33

This is essentially as saying that every $f\colon X\to Y$ can be restricted to some $R\subseteq X$, and the restriction is an injective function with the same range as $f$.

The above is equivalent to the axiom of choice, so whenever the axiom of choice fails this principle must fail somewhere as well.

It should be pointed out, however, that the set of equivalence classes still exists. The set of representatives (to which you want to restrict the function to) does not. For example $\mathbb{R/Q}$ always exists, but if all sets are measurable then you cannot define a Vitali set, which is that system of representatives.

-
And this marks my 200th answer on [axiom-of-choice]. – Asaf Karagila Jan 25 '13 at 12:19
Congrats. How long did that take? – alancalvitti Jan 25 '13 at 13:45
I started meddling seriously about topics of choice two years ago. I may have gathered a couple of answers before that, but roughly two years ago I began taking it more seriously. – Asaf Karagila Jan 25 '13 at 13:48
Congrats on the gold! Too bad Brian got his bronze badge a while ago. – arjafi Jan 25 '13 at 13:52
@Arthur: Yeah... Good luck to Vera/congratulation to you both, by the way. – Asaf Karagila Jan 25 '13 at 13:54

Yes, if you have a function $f:X\to Y$ then you completely know the function if you define the equivalence relation $x~x'$ if $f(x)=f(x')$, choosing a representative from each equivalence class and recording the value of $f$ on each representative (notice that this is slightly more accurate than the original statement in the question). Without the axiom of choice, or some extra knowledge of the domain of $f$ and/or $f$ itself, there is no guarantee that the set of all representatives exists.

-