# Partition of Set: Proof

Let $f : A\to B$. If $\{B_1,B_2,\dots,B_n\}$ is a partition of $B$, prove that $\{f^{-1}(B_1),f^{-1}(B_2),\dots,f^{-1}(B_n)\}$ is partition of $A$.

I approached it like following: Since $f^{-1}$ exists $f$ must be one one and onto. So for each $x$ in $A$ there is one distinct image in $B$ under $A$. Converse, "for each $y$ in $B$ there is distinct pre-image under $f$". This implies that we can define a set $A_i \subseteq A$ which is the set of all elements in A whose image lies in $B_i$ under the $f$ i.e., $A_i=_f^{-1}(B_i)$. Since $f$ is onto $f$ covers all of $B$ and hence union of $A_i$s is equal to $A$.
Since $B_i$ is non-empty set, there exist a $y$ in $B_i$ such that $f(x)=y$. This means that $x$ is pre-image of $y$ under $f$. Hence $x$ belongs to $A_i$. So $A_i$ is non empty set.
Now since $B_i \cap B_j$ is empty if $i\ne j$, them there is no $y$ such that it belongs to both $B_i$ and $B_j$. Now $f$ is one one so there is no pre-image $x$ such that it belongs to both $A_i$ and $A_j$. So $A_i \cap A_j$ is empty. Hence set of all $A_i$s form a partition of $A$.

I think my logic is correct but can someone help me writing it in formal way. Also since there is one one correspondence between equivalence relations and partitions, how to approach this using relations.

• Maybe it's just a nit in how the question is worded, but nothing here implies that $f^{-1}$ does exist. – chepner Aug 31 '18 at 15:38

## 4 Answers

No, here $f$ is not necessarily a bijection. This is my hint: show that if $X, Y\subset B$ then $$f^{-1}(X \cap Y) = f^{-1}(X) \cap f^{-1}(Y)\quad\text{and}\quad f^{-1}(X \cup Y) = f^{-1}(X) \cup f^{-1}(Y)$$ where the preimage $f^{-1}(X):=\{a\in A: f(a)\in X\}$. Can you take it from here?

Edit. As regards the intersection-property, see how to prove $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$ . The union-property can be shown in a similar way.

• Beat me by just a second! – Niki Di Giano Aug 31 '18 at 8:37
• @NikiDiGiano Sorry! ;-) – Robert Z Aug 31 '18 at 8:39
• @RobertZ Thanks for the correction – Avanish Singh Aug 31 '18 at 8:55
• @RobertZ Can you also help me in defining the equivalence relation for this? – Avanish Singh Aug 31 '18 at 8:55
• @Jimmy Let $aRa'$ iff there is $1\leq i\leq n$ such that $f(a)\in B_i$ and $f(a')\in B_i$. Show that $R$ is an equivalence relation in $A$. – Robert Z Aug 31 '18 at 9:09

I think $f^{-1}$ in your exercise doesn't mean the inverse function, but $f^{-1}(B_i)$ is just the preimage of $B_i$ under $f$.

To show that these preimages build a partition of $A$, let $a \in A$. Then $f(a)\in B$ lies in one of the $B_i$, say $f(a)\in B_j$, then $a \in f^{-1}(B_j)$. Since $a$ was arbitrary, the preimages cover $A$.

Try to show the other properties of a partition in a similar fashion.

Ok. For starters, you cannot say that $f$ is bijective. $$f^{-1}(B_i)=\{x\in A:f(x)\in B_i\}.$$ Next, in order to show that $\{f^{-1}(B_1),f^{-1}(B_2),\dots,f^{-1}(B_n)\}$ is a partition of $A$ you want to show two things. First, $$A=\bigcup_{i=1}^{n}f^{-1}(B_i)$$ and second that $$f^{-1}(B_i)\cap f^{-1}(B_j)=\emptyset.$$ For the first point use the fact that $$\bigcup_{i=1}^{n}f^{-1}(B_i)=f^{-1}\left(\bigcup_{i=1}^{n}B_i\right)=f^{-1}(B)=A.$$ For the second point note that $$f^{-1}(B_i)\cap f^{-1}(B_j)=f^{-1}\left(B_i\cap B_j\right)=f^{-1}(\emptyset)=\emptyset.$$ So you indeed have a partition.

No, you are not given that f is a bijection.
If x in A, then f(a) in B.
If K subset A, then f(K) = { f(x) : x in A }.
If L subset B, then $f^{-1}$(L) = { x : f(x) in L }.

This is the set extension of f and how the problem is to be understood.