Pairwise intersection of parts in two set partitions gives a new set partition

Question

This problem is from Velleman's "How to prove it" Sec 4.6 Prob 17. I'm stuck at a point

Suppose $\mathcal{F}$ and $\mathcal{G}$ are paritions of a set $A$. Define a new family of sets $\mathcal{F}\cdot\mathcal{G}$ as follows:

$\mathcal{F}\cdot\mathcal{G} = \{Z \in\mathscr{P}(A) \mid Z\neq\emptyset \text{ and } \exists X\in\mathcal{F}, \exists Y\in\mathcal{G}\,(Z=X\cap Y)\}$

Prove that $\mathcal{F}\cdot\mathcal{G}$ is a partition of set $A$.

It is obvious that $\mathcal{F}\cdot\mathcal{G}$ is pairwise disjoint and that $\emptyset\notin\mathcal{F}\cdot\mathcal{G}$.

For proving $\cup_{Z\in\mathcal{F}\cdot\mathcal{G}} Z = A$, I'm proving LHS is a subset of RHS and vice versa. I'm stuck at the evaluation of $\cup_{Z\in\mathcal{F}\cdot\mathcal{G}} (X\cap\ Y)$ by using distributive property of union over intersection as cardinality of $\mathcal{F}\cdot\mathcal{G}$,$\mathcal{F}$ and $\mathcal{G}$ may not be same.

I don't want to prove it by proving the relation over A induced by $\mathcal{F}\cdot\mathcal{G}$ as an equivalence relation as it is alluded to in problem 19 of the same excercise.

Answer 1

Let $a$ be an arbitrary element of $A$.

Then $a\in X$ for some $X\in\mathcal F$ and $a\in Y$ for some $Y\in\mathcal G$.

We conclude that $a\in X\cap Y\in\mathcal F\cdot\mathcal G$ which proves that $\mathcal F\cdot\mathcal G$ covers $A$.

Conversely every set $Z\in\mathcal F\cdot\mathcal G$ is evidently a subset of $A$ so that $\bigcup(\mathcal F\cdot\mathcal G)\subseteq A$.

Answer 2

You know that $\displaystyle{A=\bigcup_{X\in \mathcal{F}}X=\bigcup_{Y\in \mathcal{G}}Y}$. Then, $$A=A\cap A=\left(\bigcup_{X\in \mathcal{F}}X\right)\cap\left(\bigcup_{Y\in \mathcal{G}}Y\right)=\bigcup_{X\in \mathcal{F},Y\in\mathcal{G}}(X\cap Y)\subseteq \bigcup_{Z\in \mathcal{F}\cdot \mathcal{G}} Z.$$

[The last contenence can be explained as follows: If $\displaystyle{a\in \bigcup_{X\in \mathcal{F},Y\in\mathcal{G}}(X\cap Y)}$, then $a\in X\cap Y$ for some $X\in \mathcal{F},Y\in\mathcal{G}$. Then $a\in Z:=(X\cap Y)\in \mathcal{F}\cdot \mathcal{G}$.]

The other direction follows from the fact that $Z\subseteq A$ for all $Z\in \mathcal{F}\cdot \mathcal{G}$.