Equivalence relations and the axiom of choice

Question

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?

Answer 1

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)]\}$$

Answer 2

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.

Answer 3

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.