Let $U$ be a set which acts as a universe (all other sets are subsets of $U$ and complementation is done w.r.t. $U$), and $f : \mathcal P(U) \times \ldots \times \mathcal P(U) \to \mathcal P(U)$ a function of $n$ arguments on subsets of $U$. Is there any way to characterise those functions for which $$ A_1 \cap f(A_1, \ldots, A_n) = A_1\cap f(U, A_2, \ldots, A_n) $$ or $$ (U\setminus A_1) \cap f(A_1, \ldots, A_n) = A_1\cap f(\emptyset, A_2, \ldots, A_n) $$ or for which we have a decomposition $$ f(A_1, A_2, \ldots, A_n) = (U\setminus A_1) \cap f(\emptyset, (U\setminus A_1) \cap A_2, \ldots, (U\setminus A_1)\cap A_n) \cup (A_1 \cap f(U, A_1 \cap A_2, \ldots, A_1 \cap A_n) $$ and these same holds for every $A_i$ (where $A_1$ is just one instance).

If $B := f(A_1, \ldots, A_n)$ is built up from the arguments by the usual set operations like union, complement and so on, then this holds, as then the characteristic function $\chi_B$ of $B$ has the form $$ g(\chi_{A_1}(x), \ldots, \chi_{A_n}(x)) $$ for some boolean function $g : \mathbb B^n \to \mathbb B$, and for boolean function we have \begin{align*} x_1 g(x_1, \ldots) & = x_1 g(1, \ldots), \\ x_1 + g(x_1, \ldots) & = x_1 + g(0,\ldots), \\ g(x_1,\ldots) & = \overline{x_1} g(0, \ldots) + x_1 g(1, \ldots). \end{align*} But are these the only examples?

Surely there exists functions for which it does not hold, like $f(U) = \emptyset$ and $f(A_1) = A_1$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.