Let $A$, $B$ be sets. $f\,\colon A\rightarrow B$ is a surjective function. Define a relation $\sim$ in A by:

for every $x$, $y\in A$, $x\sim y$ if $f(x)=f(y)$

(a) Show that $\sim$ is an equivalence relation.

(b) Show that $A/{\sim}$ has the same cardinality as $B$.

I have finished (a) but do not know how to start with part (b). What does $A/{\sim}$ mean? Does it mean that exclude the elements satisfying $\sim$ and in set $A$?

  • 3
    $\begingroup$ $A / \sim$ is the set of equivalence classes. $\endgroup$ – Dietrich Burde Sep 11 '16 at 14:27
  • $\begingroup$ I think the quiestion in (b) implies that the function is also injective as we exclude all the element in A with ~ . Then it is bijective. But how should I write down such deduction $\endgroup$ – Rot Civ Sep 11 '16 at 14:48
  • $\begingroup$ Thanks! I should now study the stuff related to equivalence classes first. $\endgroup$ – Rot Civ Sep 11 '16 at 14:48
  • $\begingroup$ @DietrichBurde and Rot Civ : When you write $x\sim y$, the symbol $\sim$ has the amount of spacing before and after it that is appropriate to binary relation symbols, and that's why you see an inappropriate amount of space in the expression $A/\sim$. The remedy is to code that as A/{\sim}, with {curly braces} around that symbol so that nothing appears to its left or right. Then it looks like this: $A/{\sim}\,. \qquad$ $\endgroup$ – Michael Hardy Sep 11 '16 at 15:07

Hint: Let $\pi\colon A\to A/{\sim}$ be the canonical projection. Show that $\tilde{f}\colon A/{\sim}\to B$ defined by the relation $\tilde{f}\circ\pi=f$ is bijective.

  • 1
    $\begingroup$ Notice this difference: $$ A/\sim \qquad \text{versus} \qquad A/{\sim} $$ They look different for a reason. See my comment under the question. I edited the answer accordingly. $\qquad$ $\endgroup$ – Michael Hardy Sep 11 '16 at 15:09
  • $\begingroup$ Thanks @MichaelHardy, I was wondering how to display this quotient set correctly. $\endgroup$ – Philippe Malot Sep 11 '16 at 17:55

I haven't posted an answer here because Dietrich Burde already posted the answer in a comment, but some hours have passed and he hasn't made it into an answer.

$A/{\sim}$ is the set of equivalence classes.

For eample, suppose $A=\{a,b,c,d,e\}$ and $a,b,c$ are equivalent to each other, and $d,e$ are equivalent to each other but not to $a$ or $b$ or $c$. Thus $$ a\sim b\sim c \quad \text{and}\quad d\sim e. $$ Then $A/{\sim}$ has two members: $$ A/{\sim} = \big\{\ \{a,b,c\},\ \{d,e\}\ \big\}. $$ It is as if we are regarding $a,b,c$ as being just one thing rather than three, and that one thing is one member of $A/{\sim}$ and there is one other member, called either $d$ or $e$.

Or one could say that $a,b,c$ are different in their roles as members of $A$, but are the same as each other in their roles as members of $A/{\sim}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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