## Separable sigma-algebra: equivalence of two definitions

The two definitions alluded to in the title can be found here: http://en.wikipedia.org/wiki/Separable_sigma_algebra (one is that the $\sigma$-algebra is countably generated, the other is pretty much the standard usage of the word separable wrt the semi-metric given by the measure). Why are they equivalent?

-
 For convenience, I copied the Wikipedia article in a community wiki answer. – François G. Dorais♦ Jun 8 2010 at 18:43 I'm too lazy to try to prove this right now, but where does your proof get stuck? – Nate Eldredge Jun 8 2010 at 19:16 Say the $\sigma$-algebra is countably generated. How do I pick the countable dense subset in the semi-metric given by $\mu(A\Delta B)$? – Kestutis Cesnavicius Jun 8 2010 at 21:07 Kestutis, I explain how to do this in my updated answer. You can use the finite Boolean combinations of the generating set. – Joel David Hamkins Jun 9 2010 at 2:31

The two notions are not equivalent. Indeed, they are not equivalent even when one considers completing the measure by adding all null sets with respect to any countably generated $\sigma$-algebra. Nevertheless, the forward implication holds.

First, let me explain the forward implication. Suppose that $S$ is a $\sigma$-algebra generated by a countable subfamily $S_0$ and $\mu$ is a finite measure defined on $S$. The semi-metric on $S$ is defined by $d(A,B)=\mu(A\triangle B)$. Let $S_1$ be the collection of finite Boolean combinations of sets in $S_0$. This is a countable family, and I claim it is dense in the semi-metric. To see this, let $S_2$ be the closure of $S_1$ in the semi-metric, that is, the sets $A\in S$ that are approximable by sets in $S_1$, in the sense that for any $r\gt 0$ there is $B\in S_1$ such that $d(A,B)\lt r$. Note that $S_2$ contains $S_1$ and is closed under complement since the measure was finite. I claim it is also closed under countable unions: if each $A_n$ is approximable by $B_n$ to within $r/2^n$, then $\cup_n A_n$ is approximated by $\cup_n B_n$ to within $r$, and so one may find an approximating finite union. So $S_2$ is actually a $\sigma$-algebra, and since it contains $S_0$, it follows that $S_2=S$. That is, every set in $S$ is approximable by sets in $S_1$, and so $S_1$ is a countable dense set in the semi-metric, as desired.

Let's turn now to the reverse implication, which is not generally true. The easiest counterexample for this in the strict sense of the question is to let $X$ be a set of size continuum and $S=P(X)$, the full power set of $X$. This is a $\sigma$-algebra, but it is easily seen not to be countably generated on cardinality grounds. Fix any $p\in X$ and let $\mu$ be the measure placing mass $1$ at $p$ and 0 mass outside {p}. In this case, the family {emptyset, X} is dense in the semi-metric, since every subset is essentially empty or all of $X$, depending on whether it contains $p$. So the semi-metric is separable, but the $\sigma$-algebra is not countably generated.

Note that in this counterexample, the $\sigma$ algebra is obtained from the counting measure on {p} by adding a large cardinality set of measure $0$ and taking the completion. Similar counterexamples can be obtained by adding such large cardinality set of measure $0$ to any space and taking the completion.

At first, I thought incorrectly that one could address the issue by considering the completion of the measure, and showing that the $\sigma$-algebra would be contained within the completion of a countably generated $\sigma$-algebra. But I now realize that this is incorrect, and I can provide a counterexample even to this form of the equivalence.

To see this, consider the filter $F$ of all sets $A\subset \omega_1$ that contain a closed unbounded set of countable ordinals. This is known as the club filter, and it is closed under countable intersection. The corresponding ideal $NS$ consists of the non-stationary sets, those that omit a club, and these are closed under countable union. It follows that the collection $S=F\cup NS$, which are the sets measured by a club set, forms a $\sigma$-algebra. The natural measure $\mu$ on $S$ gives every set in $F$ measure $1$ and every set in $NS$ measure $0$. This is a countably additive 2-valued measure on $S$. Note that every set in $S$ has measure $0$ or $1$; in particular, there are no disjoint positive measure sets. It follows that the family {emptyset,$\omega_1$} is dense in the semi-metric, since every set in $S$ either contains or omits a club set, and hence either agrees with emptyset or with the whole set on a club. Thus, the semi-metric is separable. But for any countable subfamily $S_0\subset S$, we may intersect the clubs used to decide the members of $S_0$, and find a single club set $C\subset\omega_1$ that decides every member of $S_0$, in the sense that every member of $S_0$ either contains or omits $C$. This feature is preserved under complements, countable unions and intersections, and therefore $C$ decides every member of the $\sigma$-algebra generated by $S_0$. The completion of the measure on the $\sigma$-algebra generated by $S_0$ is therefore contained within the principal filter generated by $C$ together with its dual ideal. This is not all of $S$, since there are club sets properly contained within $C$, such as the set of limit points of $C$. Thus, this is a measure space that has a separable semi-metric, but the $\sigma$-algebra is not contained in the completion of any countably generated $\sigma$-algebra.

-
 Why is every $A\in S$ obtained by a union of the form you're claiming? – Kestutis Cesnavicius Jun 8 2010 at 21:01 Indeed, the Borel $\sigma$-field on $\mathbb{R}$ is generated by the countable family of intervals with rational endpoints, but certainly not every Borel set is a countable union of such sets and their complements! (Any closed bounded set is already a counterexample.) – Nate Eldredge Jun 8 2010 at 21:41 Nate, of course you are right, since the closure process generally proceeds in an $\omega_1$ hierarchy, so this part of my argument is wrong. But I've realized that the equivalence is not correct even when one considers the completion, and I'll update my answer shortly to explain. – Joel David Hamkins Jun 8 2010 at 23:36 I updated my argument. The example shows that from separability in the semi-metric space, one cannot necessarily find the $\sigma$-algebra in the completion of a countably generated $\sigma$-algebra. – Joel David Hamkins Jun 9 2010 at 1:31 I have now added a proof of the forward implication. – Joel David Hamkins Jun 9 2010 at 2:32

Here is the Wikipedia text in question.

In mathematics, σ-algebras are usually studied in the context of measure theory. A separable σ-algebra (or separable σ-field) is a sigma algebra that can be generated by a countable collection of sets. To learn what is meant by the σ-algebra generated by a collection of sets, refer to the article on sigma algebras.

A separable measure space has a natural metric that renders it separable as a metric space. The distance between two sets is defined as the measure of the symmetric difference of the two sets. Note that the symmetric difference of two distinct sets can have measure zero; hence the metric as defined above is not a true metric. However, if sets whose symmetric difference has measure zero are identified into a single equivalence class, the resulting quotient set can be properly metrized by the above metric. If the measure space is separable, it can be shown that the corresponding metric space is, too.

-

The wikipedia article is misleading. These two definitions are not equivalent.

The first definition makes sense for the $\sigma$-algebra of Borel sets on a topological space. If the space is Borel standard (that is, a Borel subset of a complete separable metric space), then it is countably generated. Note that a countably generated $\sigma$-algebra in the sense of the first definition has the cardinal of the continuum, this is proven just as for the $\sigma$-algebra of Borel set in [0,1], by a transfinite induction.

The second definition makes sense up to null sets. It is equivalent to saying that the algebra is generated by a countable collection of subsets, together with the null sets, and it is in my opinion a better definition. The collection of null sets (and their complementary sets) usually have a cardinality greater than the continuum if the $\sigma$-algebra is complete w.r.t the measure, hence it is cannot be countably generated. Here again, you may think of the Lebesgue measurable sets in [0,1]. This is not countably separated in the sense of the first definition, for cardinality reasons, but this is countably generated in the sense of the second definition.

Now let me add a few words to explain what is going on with the second definition. Putting the metric $d(A,B)=\mu(A\Delta B)$ on the $\sigma$-algebra amounts to embedding the $\sigma$-algebra in $L^1$ with the map $A\rightarrow {\bf 1}_A$ and recovering the distance from the $L^1$ norm: $d(A,B)=||{\bf 1}_A-{\bf 1}_B||$. This should explain why the $\sigma$-algebra is separable in the sense of the second definition if and only if $L^1$ itself is separable, and also prove that the collection of Lebesgue measurable sets is a separable $\sigma$-algebra.

-
 Why does the first definition only makes sense for $\sigma$-algebra of Borel sets? Why is the second definition \emph{equivalent} to saying that the algebra is generated by a countable collection of subsets, together with the null sets? – Kestutis Cesnavicius Jun 8 2010 at 20:59 @Kestutis. I should have said: the first definition is useful when studying Borel sets, but is too restrictive when studying e.g. Lebesgue measurable sets. Now for the equivalence, this comes from the fact that any subset (in our case {1_A, A measurable}) of a separable metric space (in our case L^1) is separable. And from the fact that 1_{A_n} converges to 1_A in L1 norm iff A=limsup A_n=liminf A_n up to a negligible set. See e.g. the book of Dudley, "Real analysis and probability". – coudy Jun 8 2010 at 21:29

I'm late to the party, but here's my two cents. References in what follows are to

• [Ha] P.R. Halmos, Measure Theory, Springer, 1950.
• [Ro] V.A. Rokhlin, On the fundamental ideas of measure theory, Transl. AMS, Series 1, No. 10 (1962), 1-54. (The original Russian article is from 1949. A pdf of the English translation is presently available here.)
• [JDH] will denote the answer already given to this question by Joel David Hamkins.

Consider a measured $\sigma$-algebra $(S,\mu)$. Assume that $\mu$ is normalised to have total weight 1, and that $S$ is complete (contains all subsets of null sets).

In [Ha], $(S,\mu)$ is said to be separable if it has a countable subset that is dense w.r.t. the metric $\rho(A,B) = \mu(A\bigtriangleup B)$. We denote this property by (S).

In [Ro], $(S,\mu)$ is said to be separable if it has a countable subset $\Gamma$ such that for every $A\in S$, there exists $B\in \sigma(\Gamma)$ such that $A\subset B$ and $\mu(B\setminus A) = 0$. Here $\sigma(\Gamma)$ is the $\sigma$-algebra generated by $\Gamma$. Since we're already using the word "separable" for (S), let's say that in this case $(S,\mu)$ is one-sided countably generated, and denote this property by (CG1). To keep terminology manageable, we won't explicitly say "mod zero", but this is understood, and thus we need to specify "one-sided" because of the restriction that $A\subset B$, which means that the "mod zero" only applies to the outer approximation, whereas the inner must be exact.

So that's two conditions. Let's round it out by saying that $(S,\mu)$ is one-sided separable if it has a countable subset $\Gamma$ that is not only dense w.r.t. $\rho$ but also has the property that for every $A\in S$ and $\epsilon>0$ there exists $B\in \Gamma$ such that $A\subset B$ and $\mu(B\setminus A) < \epsilon$; we denote this property by (S1). Similarly, say $(S,\mu)$ is countably generated if it has a countable subset $\Gamma$ such that for every $A\in S$ there exists $B\in \sigma(\Gamma)$ such that $\rho(A,B)=0$.

Now we have four conditions: two of them involve approximations from the outside, while the other two allow arbitrary approximations. Clearly (CG1) implies (CG), and similarly (S1) implies (S). It was shown in [JDH] that (CG) implies (S), but the converse is not true.

So far this is just a summary of what others have already said here. Here's the new bit.

Equivalence when non-atomic. Recall that an atom is a set $E\in S$ such that $\mu(E)>0$ and every subset $A\subset E$ has either $\mu(A)=0$ or $\mu(A)=\mu(E)$. If $(S,\mu)$ is non-atomic (has no atoms), then in fact all four definitions are equivalent. To see this, observe that any of the four imply (S), and that (S) in turn implies that there is a $\sigma$-algebra isomorphism from $(S,\mu)$ to the Lebesgue sets on the unit interval equipped with Lebesgue measure [Ha, Sec. 41, Theorem C]. Since all four properties hold for the Lebesgue space, we are done.

Atomic pieces. Intuitively, one expects that if $E$ is an atom in $(S,\mu)$, then there should be a $\sigma$-algebra map $(S|_E, \mu|_E) \to (T,\nu)$ that is a mod zero isomorphism, where $T$ is a $\sigma$-algebra with only two elements ($\emptyset$ and a single point) and $\nu$ is a point mass with total weight $\mu(E)$. In particular, this requires that there exists a set $F\subset E$ such that $\mu(F) = \mu(E)$ and every null set $A\subset E$ has $A\cap F = \emptyset$. The example in [JDH] shows that this need not always be the case, and that an atomic space need not be (mod zero) isomorphic to a point mass even if (S) holds.

The one-sided conditions (S1) and (CG1) serve to fill this gap and let us deal appropriately with the atomic pieces. Indeed, if either of these properties hold, then one can show the following:

(A) There exist atoms $E_n \in S$ such that $S|_{E_n}$ is the trivial $\sigma$-algebra for every $n$, and $S|_{(\bigcup_n E_n)^c}$ is isomorphic to the Lebesgue sets on an interval of length $1 - \sum_n \mu(E_n)$.

So at the end of the day, we see that (CG1) and (S1) are equivalent, and imply both (CG) and (S). Furthermore, (CG) implies (S), and the converse is true if $(S,\mu)$ is non-atomic, but may fail if it has atoms.

I don't know if (CG) is equivalent to (CG1) and (S1). I suspect it is not, because otherwise I doubt that [Ro] would introduce the extra condition that $A\subset B$. However, I do not know a counterexample.

Comments on the proof of (A). For the proof of (A), one must use (CG1) or (S1) to take an atom $E\in S$ and produce a subset $F\subset E$, $F\in S$ such that $F\cap A = \emptyset$ for all $A\in S$ with $\mu(A)=0$. The key to this is that both conditions allow you to produce a countable family $S'\subset S$ such that for every $\epsilon>0$ and every null set $A$, we have $A\subset \bigcup_n B_n$ for some $B_n \in S'$ with $\mu(\bigcup_n B_n) < \epsilon$. (For (S1) one takes $S' = \Gamma$, while for (CG1) one takes $S'$ to be the set of all finite intersections of sets in $\Gamma$ and their complements.) Then because $E$ is an atom, we can conclude that $\mu(B_n \cap E) = 0$ for all $n$, and so the collection of all null sets in $E$ can be covered by a countable collection of null sets, whose union therefore has measure zero.

-