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

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?

• How is $F(j)$ defined? Also the tag set-theory is not okay here. – drhab Sep 29 '18 at 13:39
• Oh sorry. Will edit it in. – user370967 Sep 29 '18 at 13:41
• Done. Thanks for the remark. – user370967 Sep 29 '18 at 13:43
• I would leave out the demand that $\varnothing\neq J$. Then automatically the empty set - which is the empty union - will be an element of the collection, so that you can leave out the appendix $\cdots\cup\{\varnothing\}$ as well. – drhab Sep 29 '18 at 14:06

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)$$

• Incredibly smart trick. I was looking too "local" (in the sense that I was writing out what the union was) while the solution here is found by looking at the "global" structure. Thank you. – user370967 Sep 29 '18 at 14:05
• You are very welcome. – drhab Sep 29 '18 at 14:07
• Could you tell me if this is also a sigma-algebra? Is this also the smallest sigma algebra generated by those sets? Thanks in advance. ( I think the answer is yes) – user370967 Oct 2 '18 at 21:27
• Yes on both questions. Even stronger: it is closed under arbitrary unions. – drhab Oct 3 '18 at 6:33

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$$.