From sets of subsets to partitions

Question

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.

Answer 1

For each $s\in S$ define $p_s$ as the intersection of all elements of $Q$ containing $s$, intersected with the intersection of all complements of elements of $Q$ that do not contain $s$. Then if $p_s$ intersects $p_t$, we must have $p_s=p_t$, this gives the desired partition.

In other words, for each $s$ and each $q\in Q$ let $r_{s,q}=q$ if $s\in q$, and let $r_{s,q}=S\setminus q$ if $s\not\in q$. Then let $p_s=\cap_{q\in Q} r_{s,q}$. Clearly $s\in p_s$. Also, if $p_s\not=p_t$ for some $s\not=t$ then there must be a $q\in Q$ such that $s\in q$ but $t\not\in q$ (if necessary switch $s$ and $t$). Then $p_s\subseteq q$ but $p_t\cap q=\emptyset$, hence $p_s$ and $p_t$ are disjoint.

Also, argue that an element of $P'$ is maximal if and only if it is of the form $p_s$ for some $s$.