0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How is $F(j)$ defined? Also the tag set-theory is not okay here. $\endgroup$ – drhab Sep 29 '18 at 13:39
  • $\begingroup$ Oh sorry. Will edit it in. $\endgroup$ – user370967 Sep 29 '18 at 13:41
  • $\begingroup$ Done. Thanks for the remark. $\endgroup$ – user370967 Sep 29 '18 at 13:43
  • $\begingroup$ 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. $\endgroup$ – drhab Sep 29 '18 at 14:06
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user370967 Sep 29 '18 at 14:05
  • $\begingroup$ You are very welcome. $\endgroup$ – drhab Sep 29 '18 at 14:07
  • $\begingroup$ 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) $\endgroup$ – user370967 Oct 2 '18 at 21:27
  • 1
    $\begingroup$ Yes on both questions. Even stronger: it is closed under arbitrary unions. $\endgroup$ – drhab Oct 3 '18 at 6:33
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

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