# Show that a set $A/{\sim}$ has the same cardinality as $B$

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$?

• $A / \sim$ is the set of equivalence classes. – Dietrich Burde Sep 11 '16 at 14:27
• 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 – Rot Civ Sep 11 '16 at 14:48
• Thanks! I should now study the stuff related to equivalence classes first. – Rot Civ Sep 11 '16 at 14:48
• @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$ – Michael Hardy Sep 11 '16 at 15:07

## 2 Answers

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.

• 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$ – Michael Hardy Sep 11 '16 at 15:09
• Thanks @MichaelHardy, I was wondering how to display this quotient set correctly. – 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}$.