Množiny z průniků a sjednocení
Úloha číslo: 3339
Určete maximální možný počet různých množin, které lze získat pomocí binárních operací průniku a sjednocení:
Varianta
Ze dvou počátečních množin.
Řešení
Z počátečních množin \(A\) a \(B\) můžeme určitě získat množiny \(A\), \(B\), \(A \cup B\) a \(A \cap B\) (\(A = A \cup A\)).
Ukážeme, že už žádné jiné množiny získat nemůžeme. Konkrétně chceme ukázat, že když pronikneme nebo sjednotíme libovolné dvě z těchto čtyř množin, tak opět dostaneme některou z těchto čtyř množin. Uvažujme, množiny \(A \cap B\), \(A\) a \(A \cup B\). Ty jsou v inkluzi \(A \cap B \subseteq A \subseteq A\cup B\). Tedy, když pronikneme nebo sjednotíme libovolné dvě z těchto množin, tak opět dostaneme některou ze zmiňovaných dvou množin. Podobná situace nastává pro trojici množin \(A \cap B\), \(B\) a \(A \cup B\). Jediná situace, která není pokrytá těmito dvěmi trojicemi je sjednocení nebo průnik množin \(A\) a \(B\). Jejich sjednocení a průnik se ovšem mezi čtyřmi množinami objevují.
Poznámka k důrazu na výraz binární operace v zadání. Pokud bychom dovolili sjednocení a průniky systémů množin, pak bychom u sjednocení a průniku přes prázdné systémy získali i prázdnou množinu a celé universum.
Odpověď
Ze dvou množin lze získat čtyři množiny pomocí sjednocení a průniků.
Varianta
Ze tří počátečních množin.
Řešení
Z počátečních množin \(A\), \(B\), \(C\) lze vytvořit 15 dalších množin:
– průniky a sjednocení jejich dvojic \(A \cap B\), \(A \cap C\), \(B \cap C\), \(A \cup B\), \(A \cup C\), \(B \cup C\),
– průniky a sjednocení všech tří \(A \cap B \cap C\), \(A \cup B \cup C\),
– průniky jedné se sjednocením zbylých dvou \(A \cap (B \cup C)\), \(B \cap (A \cup C)\), \(C \cap (A \cup B)\)
– sjednocení jedné s průnikem zbylých dvou \(A \cup (B \cap C)\), \(B \cup (A \cap C)\), \(C \cup (A \cap B)\)
– sjednocení všech tří průniků dvojic \((A \cap B) \cup (A \cap C) \cup (B \cap C)\).Rozmyslete si, že všechny tyto množiny mohou být různé (nakreslete si obrázky).
Důkaz, že více množin získat nemůžeme je podobný jako u první varianty, ale je trochu pracnější, protože pracujeme s více množinami. Nejprve je potřeba si rozmyslet, které dvojice množin jsou v inkluzi, protože pak jejich průnik i sjednocení pak zůstanou mezi uvedenými 18 množinami. Pro zbylé dvojice použijeme rovnosti (kde z \(X\), \(Y\) a \(Z\) dosazujeme \(A\), \(B\), \(C\) v libovolném pořadí; pokud nevíte, proč daná rovnost platí, kreslete si obrázek):
\(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\),
Odpověď
Ze dvou množin lze získat 18 množin pomocí sjednocení a průniků.