Collection of Maths Problems

Sets from intersection and union

Task number: 3347

• Variant

  From two initial sets.

• Solution

  From initial sets \(A\) and \(B\) we can certainly obtain the sets \(A\), \(B\), \(A \cup B\) and \(A \cap B\) (\(A = A \cup A\)).

  We will show that we can obtain no further sets. Concretely, we'd like to show that when we take the intersection or union of any two of these four sets, then we once again obtain one of these four sets. Consider the sets \(A \cap B\), \(A\) and \(A \cup B\). They satisfy the inclusion \(A \cap B \subseteq A \subseteq A\cup B\). So when we take the intersection or union of any two of these sets, we once again obtain one of the two sets. The situation is similar for the three sets \(A \cap B\), \(B\) and \(A \cup B\). The only situation that is not covered by these cases is the union or intersection of the sets \(A\) and \(B\). But their union and intersection belong to the four sets listed above, of course.

  A note on the emphasis on the expression binary operation in the assignment. If we allowed the union and intersection of arbitrary systems of sets, then through the intersection and union of the empty system we'd also obtain the empty set and the universal set.

• Answer

  From two sets it's possible to obtain four sets using the intersection and union operations.

• Variant

  From three initial sets.

• Solution

  From the initial sets \(A\), \(B\), \(C\) we can form 15 further sets:
  – the intersection and union of pairs \(A \cap B\), \(A \cap C\), \(B \cap C\), \(A \cup B\), \(A \cup C\), \(B \cup C\),
  – the intersection and union of all three \(A \cap B \cap C\), \(A \cup B \cup C\),
  – the intersection of one with the union of the remaining two \(A \cap (B \cup C)\), \(B \cap (A \cup C)\), \(C \cap (A \cup B)\)
  – the union of one with the intersection of the remaining two \(A \cup (B \cap C)\), \(B \cup (A \cap C)\), \(C \cup (A \cap B)\)
  – the union of all three intersections of pairs \((A \cap B) \cup (A \cap C) \cup (B \cap C)\).

  Think about why all of these sets may be distinct (draw pictures).

  The proof that we cannot obtain more sets is similar to the first variant, but is a bit more laborious, because we are working with more sets. We must first consider which pairs of sets are in an inclusion relationship, because then their intersection or union will still be among the 18 sets. For the remaining pairs we use the following identities (where we substitute \(A\), \(B\), \(C\) for \(X\), \(Y\) and \(Z\) in any order; if you don't know why any identity holds, draw a picture):

  \(X \cap (Y \cap (X \cup Z)) = X \cap Y\),
  \(X \cup (Y \cap (X \cup Z)) = X \cup (Y \cap Z)\),
  \(X \cap (Y \cup (X \cap Z)) = X \cap (Y \cup Z)\),
  \(X \cup (Y \cup (X \cap Z)) = X \cup Y\),
  \(X \cap ((X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)) = X \cap (Y \cup Z)\),
  \(X \cup ((X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)) = X \cup (Y \cap Z)\),
  \((X \cap Y) \cap (X \cap Z) = X \cap Y \cap Z\),
  \((X \cap Y) \cup (X \cap Z) = X \cap (Y \cup Z)\),
  \((X \cap Y) \cap (X \cap (Y \cup Z)) = X \cap Y \cap Z\),
  \((X \cap Y) \cup (X \cap (Y \cup Z)) = (X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)\),
  \((X \cup Y) \cap (X \cup Z) = X \cup (Y \cap Z)\),
  \((X \cup Y) \cup (X \cup Z) = X \cup Y \cup Z\),
  \((X \cup Y) \cap (Z \cup (X \cap Y)) = (X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)\),
  \((X \cup Y) \cup (Z \cup (X \cap Y)) = X \cup Y \cup Z\),
  \((X \cap (Y \cup Z)) \cap (Y \cap (X \cup Z)) = X \cap Y\),
  \((X \cap (Y \cup Z)) \cup (Y \cap (X \cup Z)) = (X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)\),
  \((X \cup (Y \cap Z)) \cap (Y \cup (X \cap Z)) = (X \cap Y) \cup (X \cap Z) \cup (Y \cap Z)\),
  \((X \cup (Y \cap Z)) \cup (Y \cup (X \cap Z)) = X \cup Y\),
  

• Answer

  From three sets we may obtain 18 sets using the union and intersection operations.