During research, I hit a set theoretic claim that I could neither proof nor disproof.

Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that

  1. $S_1,S_2,S_3$ are closed w.r.t. $\cap$ and $\cup$ and

  2. for each pair $u,v \in U$, there are two disjoint sets $X \in S_i, Y \in S_j$, $i,j \in \{1,2,3\}$, $i \neq j$, such that $u \in X$ and $v \in Y$.

Then, there is a partition of $U$ into at most three sets, each from a different set system.

  • $\begingroup$ Is $U$ finite? Countable? $\endgroup$ – kodlu Apr 28 '15 at 1:45
  • $\begingroup$ This is not set theory but set systems. $\endgroup$ – domotorp Apr 28 '15 at 9:12

They don't necessarily imply a partition, here is a counterexample. Each set in each $S_i$ will have an even size, while $U$ will have an odd number of elements, this already guarantees that a partition is impossible. $U$ is the nine vertices of a cycle of length $9$, whose edges are colored with $3$ colors, in an alternating way. With the union operation each color class generates a set system, these will be the $S_i$. In more detail, the generating edges are 01, 34, 67 for $S_1$, 12, 45, 78 for $S_2$ and 23, 56, 80 for $S_3$. It is easy to check that your separating condition holds.


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.