Let S be a non-empty set, and Q be a set of non-empty subsets of S such that $\bigcup Q=S$. Let $P'$ be the set of all non-empty subsets x of S such that:
$\forall q\in Q. x\subseteq q \lor x\cap q=\emptyset$
and $P$ be the set of all maximal elements of $P'$.
Is P a partition of S? How can I prove this? Is there some "constructive" way of proving it?
Here is my attempt so far:
- $\bigcup P = S$. Take an arbitrary $s\in S$, and let $x$ be its singleton set. For all $q\in Q$, either $x\subseteq q$ or $x \cup q = \emptyset$. Thus, either $x$ is itself a member of $P$, or it is a proper part of a member of $P$. Either way, there is some $p\in P$ of which $s$ is a member. Since $s$ was chosen arbitrarily, this holds for all members of $S$.
- I'm not sure how to prove that any two distinct members of P are disjoint.