Množiny získatelné třemi operacemi

Úloha číslo: 3340

Určete maximální možný počet různých množin, které lze získat pomocí operací průniku a sjednocení a množinového rozdílu ze dvou počátečních množin.

  • Řešení

    Máme-li startovní množiny \(A\) a \(B\), můžeme získat 8 množin \(A\), \(B\), \(A \cup B\), \(A \cap B\), \(A \setminus B\), \(B \setminus A\), \((A \setminus B) \cup (B \setminus A)\) a \(\emptyset = A \setminus A\). Rozmyslete si, že všechny tyto množiny mohou být různé.

    Ukážeme, že více množin získat nelze. Rozdělme si \(A \cup B\) na sjednocení tří disjunktních množin \(X = A \setminus B\), \(Y = A \cap B\) a \(Z = B \setminus A\). Ať aplikujeme sjednocení, průnik či množinový rozdíl jakkoliv, nejsme od sebe schopni oddělit jednotlivé prvky v \(X\) (totéž platí pro \(Y\) a \(Z\)). Tedy každá výsledná množina obsahuje buď celou \(X\), nebo neobsahuje nic z \(X\) (totéž platí pro \(Y\) a \(Z\)). Můžeme si tedy zvolit, jestli výsledná množina obsahuje či neobsahuje \(X\), podobně s \(Y\) a \(Z\). Dohromady máme \(2 {\cdot} 2 \cdot 2 = 8\) možností.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze