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?
 A: 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.
A: [Edited 10/22/15: there were embarrassing errors in my original answer, which were pointed out in another question; I've corrected these, and I've written up further details in a blog post.]

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 (1952), 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$.  (In fact, Rokhlin's definition is given for a measure space, not just a measured $\sigma$-algebra, and requires that $\Gamma$ separate points of the space.)  Since we're already using the word "separable" for (S), let's say that in this case $(S,\mu)$ is one-sided countably generated mod zero, and denote this property by (CG0+).  
So that's two conditions.  Another natural condition would be that $S$ itself is countably generated, that is, that $S = \sigma(\Gamma)$ for some countable $\Gamma$; call this (CG), and not that it applies to the Borel $\sigma$-algebra on $[0,1]$, but not the Lebesgue $\sigma$-algebra.  The latter satisfies the weaker condition (CG0+), and hence is also countably generated mod zero, meaning that there is a countable $\Gamma \subset S$ such that for every $A\in S$, there exists $B\in \sigma(\Gamma)$ such that $\mu(A \bigtriangleup B) = 0$.
(In the previous version of this answer I got carried away and also defined (S1), one-sided separability, to be the property that every $A\in S$ and $\epsilon>0$ there exists $B\in \Gamma$ such that $A\subset B$ and $\mu(B\setminus A) < \epsilon$.  As was correctly pointed out by Rina Shora and Nik Weaver on another question, this fails to hold for even the most standard examples.)
It is immediate that (CG) $\Rightarrow$ (CG0+) $\Rightarrow$ (CG0), and [JDH] shows that (CG0) $\Rightarrow$ (S) (it is written with (CG) in mind, but works just as well for (CG0)).  In fact one can also show that (S) $\Rightarrow$ (CG0) (details are in this blog post) -- that is, separability is equivalent to being countably generated mod zero -- and that the first two implications above are strict (the Lebesgue $\sigma$-algebra satisfies (CG0+) but not (CG), and the $\sigma$-algebra of Lebesgue subsets of $[0,1]$ with measure 0 or 1 satisfies (CG0) but not (CG0+)).
Finally, another related condition would be that $S$ is contained in the completion of a countably generated $\sigma$-algebra; this property lies somewhere between (CG) and (CG0), but its relation to (CG0+) is not clear to me.
The example in [JDH] involving the club filter shows that (S) (and hence (CG0)) is not enough to imply this condition.
A: 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.

A: 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.
