Given N possibly overlapping sets, give formulas that specify, using intersections and complements of the given sets, N disjoint sets with the same union as the original N sets. The sets that result are to be the same as the given sets in the case where the given sets are already disjoint.

In the below please excuse the inability to get a CAP (intersection symbol) to look correct.

Let's call the sets A, B, C, etc.  Let �� represent intersection and ~ represent complement.

My first thought is to use just A, B��~A, C��~B��~A, etc.

The only problem with this is that some of the sets may be empty.  This is OK if only one is empty, but if more than one is empty, then two of the sets are actually identical, and so we don't really have N sets--we have fewer.

Just to take a simple case, where I don't see any possibility of creating such a set of disjoint sets, take these 5 sets:
{1}, {2},{3},{4},{1,2},{3,4},{1,2,3,4}

That's seven sets.  We can't make seven disjoint sets with only those four elements.

Edited on April 4, 2004, 11:37 am

Posted by Charlie on 2004-04-04 11:30:07