Give a description for the smallest field generated by finitely many sets.

Question

Suppose $A_1, \dots, A_m$ are non-empty sets in a set $\Omega$.Prove that

$$f( \{A_1, \dots, A_m\}) = \{\bigcup_{j \in J} F(j)\mid \emptyset \neq J \subseteq \{0,1\}^m\} \cup \{\emptyset\}$$

where $F(j) = F(j_1, \dots, j_m) = \bigcap_{i=1}^m A_i^{(j_i)}$, $A_i^{(0)} = A_i, A_i^{(1)} = A_i^{\complement}$ and where $f(\mathcal{A})$ is "the smallest field (contains the universum, closed under finite unions, closed under complementation) containing $\mathcal{A}$"

Attempt:

I showed that the right set is in the left set, and so by minimality it suffices to show that $\{\bigcup_{j \in J} F(j)\mid \emptyset \neq J \subseteq \{0,1\}^m\} \cup \{\emptyset\}$ is a field. I showed that it contains $\Omega$ and is closed under finite unions, but I have trouble showing that this set preserves complementation.

I am pretty sure that $$\left(\bigcup_{j \in J} F(j)\right)^{\complement} = \bigcup_{j \in J^{\complement}} F(j)$$

but I was unable to prove this.

How can I prove this?

Answer 1

The set collection: $$\{F(j)\mid j\in \{0,1\}^m\}\subseteq\wp(\Omega)$$ forms a "pseudo-partition" of the set $\Omega$ in the sense that $i\neq j\implies F(i)\cap F(j)=\varnothing$ and the union of these sets equals $\Omega$.

It is not excluded however that $F(j)=\varnothing$ and that's why I use the term "pseudo".

This implies directly that: $$\left(\bigcup_{j \in J} F(j)\right)^{\complement} = \bigcup_{j \in J^{\complement}} F(j)$$

Answer 2

Your intuition is correct: each $j$ basically represents a row in a truth table over boolean variables corresponding to the $A_i$.

It will be enough to show that the $F(j)$ are pairwise disjoint and that their union is $\Omega$.