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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email