Sets obtainable using three operations
Task number: 3348
Determine the maximal number of distinct sets that we may obtain using the operations of intersection, union and set difference from two initial sets.
Solution
If we have starting sets \(A\) and \(B\), we can obtain 8 sets \(A\), \(B\), \(A \cup B\), \(A \cap B\), \(A \setminus B\), \(B \setminus A\), \((A \setminus B) \cup (B \setminus A)\) and \(\emptyset = A \setminus A\). Think about why all these sets may be distinct.
We will show that it's not possible to obtain more sets. We divide \(A \cup B\) into the union of three distinct sets \(X = A \setminus B\), \(Y = A \cap B\) and \(Z = B \setminus A\). No matter how we apply the union, intersection or set difference operations, we cannot separate individual elements in \(X\) (and the same holds for \(Y\) and \(Z\)). So every possible obtainable set contains either all of \(X\), or nothing from \(X\) (and the same holds for \(Y\) and \(Z\)). We can therefore choose whether a resulting set contains or does not contain \(X\), similarly \(Y\) and \(Z\). Altogether we have \(2 {\cdot} 2 \cdot 2 = 8\) possibilities.
