I would like to find an efficient way to determine the smallest $\sigma$-algebra $\sigma(F)$ in $X=\{1,2,3,4\}$ that contains one of the following $F$'s:
(a) $F=\{\{1\},\{2,3\}\}$
(b) $F=\{\{1,3\},\{2,3\}\}$
(c) $F=\{\{1\},\{1,3\}\}$
Before we begin our discussion, let us review some definitions related to $\sigma$-algebra. We define a $\sigma$-algebra in $X$ to be a collection of subsets of $X$ that is closed under complements, countable unions, and countable intersections. As for what is meant by $\sigma(F)$, we define
$$\sigma(F)=\bigcap\{\Lambda:\text{$\Lambda$ is a $\sigma$-algebra in $X$ containing $F$}\}.\tag{$*$}$$
For (a), I simply considered what it would be like to have $\Lambda_a$ as a $\sigma$-algebra in $X$ containing $\{\{1\},\{2,3\}\}$. For example, because $\{1\}\in\Lambda_a$, we must have $\{1\}^c=\{2,3,4\}\in\Lambda_a$. Likewise, we must have $\{2,3\}^c=\{1,4\}\in\Lambda_a$, thereby leading to $\{2,3,4\}\cap\{1,4\}=\{4\}\in\Lambda_a$. Continuing in this manner, I got
$$\Lambda_a=\{\emptyset,\{1\},\{4\},\{2,3\},\{1,4\},\{1,2,3\},\{2,3,4\},X\}.$$
I claim that $\Lambda_a=\sigma(F)$ because if any set in $\Lambda_a$ is removed, the resulting product $\Lambda_a'$ will no longer be a $\sigma$-algebra in $X$ containing $F$. Now let me ask two questions:
- Is $\Lambda_a$ really equal to $\sigma(F)$? I did NOT even make use of ($*$) to get $\sigma(F)$!
- Even if my approach is correct, it is kind of time-consuming. Is there any other approach that is both effective and efficient?
Thank you for your patience.
Best Answer
There is an approach that works strictly for $X$ at most countable. It doesn't work when $X$ is uncountable.
Let $\mathcal F$ be a collection of subsets on $X$. Now, the point is, if $X$ is at most countable, then one can find an at most countable collection of sets $\{A_i\}_{i \in \mathbb N}$ such that
$A_i \in \sigma(\mathcal F)$ for all $i$.
$A_i \cap A_j = \emptyset$ for $i \neq j$.
$\bigcup_{i=1}^\infty A_i = X$.
Once you find such a collection of $A_i$, then it is not difficult to prove that $\sigma(\mathcal F) = \{\bigcup_{s \in S} A_s : S \subset \mathbb N\}$.
Furthermore, if $X$ is finite, then one can ensure that $A_i$ is also a finite collection of sets. All we need to do then, is merely find some $A_i$ which work : and we are done.
Finding the $A_i$ is actually quite simple practically : suppose that $B \in \mathcal F$ but no non-empty subset of $B$ is in $\mathcal F$. Then, $B$ can be taken as one of the $A_i$, and then you can repeat the procedure on $X \setminus B$ and so on.
So when you see an $A \in \mathcal F$, try to see if the other sets in $\mathcal F$, when intersected with $A$, are able to provide non-empty subsets of $A$. Find all such subsets, add the complements of those subsets in $A$ into the collection. Remove $A$. Change your $A$ to something else. Leave subsets that don't intersect with other sets alone. Eventually, $\mathcal F$ will consist of disjoint subsets, and you will be done after adding the last set which is the complement of the union of these subsets.
For example, let's take $(a)$. We already have $\{1\}$ and $\{2,3\}$ in $\mathcal F$. These are already disjoint (so no further non-empty subsets can be formed by their intersection), and their union $\{1,2,3\}$ has complement $\{4\}$. Thus, we can take the decomposition $A_1 = \{1\},A_2 = \{2,3\},A_3 = \{4\}$. Thus, we get that $\sigma(\mathcal F)$ equals $\{\cup_{s \in S} A_s : S \subset \{1,2,3\}\}$ with the $A_i$ defined as earlier.
Now, let's take $(b)$. We have $\{1,3\},\{2,3\}$. Now, let's take $A = \{1,3\}$. Intersect it with $\{2,3\}$ to get $\{3\}$. The complement of $\{3\}$ in $\{1,3\}$ is $\{1\}$. So you now get $\{1\},\{3\},\{2,3\}$. Now take $A = \{2,3\}$. Clearly $\{2,3\} \cap \{3\} = \{2\}$, whose complement in $\{2,3\}$ is $\{3\}$. Thus, you get $\{1\},\{2\},\{3\}$ which are disjoint! Now, taking the complement of their union gives $A_i = \{i\}$ for $i=1,2,3,4$. In this case, you see that $\sigma(\mathcal F)$ actually equals the power set of $X$ i.e. the set of subsets of $X$.
Now, let's take $(c)$. We have $\{1\},\{1,3\}$. We take $A = \{1,3\}$ so that $\{1,3\} \cap \{1\} = \{1\}$ whose complement in $\{1,3\}$ is $\{3\}$. Thus, we get $\{1\},\{3\}$ which is disjoint, and the complement of their union is $\{2,4\}$. So you can take $A_1 = \{1\}$, $A_2 = \{3\}$ and $A_3 = \{2,4\}$ with $\sigma(\mathcal F) = \{\bigcup_{s \in S} A_s , S \subset \{1,2,3\}\}$.
This method is uber-efficient once you practice it with five or six more examples.
To see why this works, we need to go back to your working and realize a key fact : you don't need $(*)$ to prove that $\sigma(\mathcal F)$ is what you've written (I call it your "candidate" below). Instead, focus on two things :
Your candidate is a sigma-algebra.
Your candidate is necessarily contained in any $\sigma$-algebra by virtue of closure under intersection/union/complements.
These two facts alone will tell you that your candidate is in fact equal to $\sigma(\mathcal F)$, because it is a sigma-algebra and is therefore contained in $\sigma(\mathcal F)$ by virtue of $(*)$, but then in the intersection defining $(*)$, every sigma-algebra in there also contains your candidate, and therefore $\sigma(\mathcal F)$ contains your candidate.
Now : in your working, you actually proved necessarily that $\Lambda_a$ must be equal in $\sigma(\mathcal F)$. That is because :
You asserted that $\Lambda_a$ is a sigma-algebra.
Everything you did before this, showed something stronger : every sigma-algebra containing $\{1\}$ must contain $\{2,3,4\}$, for example. Therefore, all your manipulations held not just for membership in $\Lambda_a$, but in fact for any sigma-algebra that contains the sets in the premise. That's why $(*)$ comes into play ,and you get the result.
So you've actually dovetailed well with $(*)$.
Something similar applies to the proof of the following statement :
To prove this, call the RHS of the assertion as $Y$. Then $Y$ is a sigma-algebra : for $S = \emptyset$ you get the empty set and for $S = \mathbb N$ you get $X$. It's closed under complements : the union over $S^c$, is the complement of the union over $S$. It's obviously closed under countable unions : the union of the respective index sets give the index set of the union of $Y$.
But then, $Y$ must obviously be contained in $\sigma(\mathcal F)$, because each $A_i$ belongs in $\sigma(\mathcal F)$, so every union of the form $\cup_{s \in S} A_s \in \sigma(\mathcal F)$ for $S \subset \mathbb N$. That obviously covers every subset of $Y$. Thus, we are done.
So, we have a concrete way of "disjointing" an initial set $\mathcal F$ and producing the $A_i$, and then a way of expressing $\sigma(\mathcal F)$ in terms of these $A_i$. I think this is what was asked for.