0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$

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.