Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm currently reading "Naive Set Theory" by P.H. Halmos and I got confused with an exposition in the middle of the text. Here it is:

"If $f$ is an arbitrary function, from $X$ onto $Y$, then there is a natural way of defining an equivalence relation $R$ in $X$; write $aRb$ (where $a$ and $b$ are in $X$) in case $f(a)= f(b)$. For each element $y$ of $Y$, let $g(y)$ be the set of all those elements $x$ in $X$ for which $f(x)=y$. The definition of $R$ implies that $g(y)$ is, for each $y$, an equivalence class of the relation $R$; in other words, $g$ is a function from $Y$ onto the set $X/R$ of all equivalence classes of $R$."

Right after that he states that $g$ is a one-to-one correspondence.

As an example of this construction I tried $f: X \to Y$, $f(x)= x^{2}$, with $X=\{-3, -2, 2, 3\}$ and $Y=\{4, 9, 11\}$. In this case: $$R=\{(-3, -3), (-3, 3), (3,3), (3, -3), (-2, -2), (-2, 2), (2, 2), (2, -2)\}$$ and $$X/R=\{\{-3, 3\}, \{-2, 2\}\}.$$ And for each element $y$ in $Y$, $$g(4)=\{-2, 2\};$$ $$g(9)=\{-3, 3\};$$ $$g(11)=\{\}.$$ But then, $g(11)=\{\} \notin X/R$, when $g(11)$ should be an equivalence class of $R$.

Probably there's some gross mistake above. I'd appreciate if someone could point it to me. Thanks!

share|cite|improve this question
up vote 2 down vote accepted

The text states that $f$ is a function from $X$ onto $Y$. This means that for every $y\in Y$, there is at least one $x\in X$ such that $f(x)=y$. The function you gave is not onto, hence the failure of the claim.

share|cite|improve this answer

"$f$ is an arbitrary function, from $X$ onto $Y$"

The word onto means that $f$ is surjective, and hence why your counterexample fails.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.