# Proving completeness of Nikodym Metric

I'm trying to prove completeness directly of the metric given by $d(A, B) = \mu (A \triangle B)$ on a finite measure space $(X, M, \mu)$.

Edit: I should make clear that I'm referring to completeness of the actual Nikodym Metric $M/\sim$ under the relation $A \sim B$ if and only if $\mu(A \triangle B) = 0$. I leave a number of minor details left implicit with respect to this relation (like when I'm talking about a class vs a representative), but they're all rather mundane.

Let $M_1, M_2, ...$ be a Cauchy sequence in our metric space.

Take a subsequence such that for all $m, p > n$, $d(A_m, A_p) < 1/2^n$, where $A_1, A_2, ...$ denotes our subsequence.

Let $A = \limsup M_i$.

Then $A$ is also the $\limsup$ of the $A_i$'s, since $x$ belongs to infinitely many sets in one sequence if and only if it belongs to infinitely many in the other.

Edit 2: The above bolded argument is erroneous. The $\limsup$ of the $A$'s should differ from the $\limsup$ of the $M$'s only on a set of measure zero, but we may very well lose elements when we pass to a $\limsup$ of the subsequence.

Let $n \in N$.

We use measure continuity from above on $A \setminus A_n$ and from below on $A_n \setminus A$.

\begin{align*} \mu(A \setminus A_n) &= \mu(( \bigcap_{k \geq 1}^\infty \bigcup_{j=k}^\infty A_j \setminus A_n)) \\ &= \mu( \bigcap_{k \geq 1}^\infty \bigcup_{j=k}^\infty (A_j \setminus A_n)) \\ &= \lim_{k \rightarrow \infty} \mu(\bigcup_{j=k}^\infty (A_j \setminus A_n)) \end{align*} At this point I'm stuck - using subadditivity of $\mu$ does not help, as $A_j$ might grow further from $A_n$ as $j \rightarrow \infty$, so that the measure of their difference will grow, making the infinite sum infinite for every $k$.

Bounding the other difference is quite simple, however. Using DeMorgan's laws: \begin{align*} \mu(A_n \setminus A) &= \mu(A_n \setminus ( \bigcap_{k \geq 1}^\infty \bigcup_{j=k}^\infty A_j)) \\ &= \mu(A_n \cap ( \bigcap_{k \geq 1}^\infty \bigcup_{j=k}^\infty A_j)^c) \\ &= \mu( \bigcup_{k \geq 1}^\infty \bigcap_{j=k}^\infty (A_n \setminus A_j)) \\ &= \lim_{k \rightarrow \infty} \mu(\bigcap_{j=k}^\infty (A_n \setminus A_j)) \\ &< 1/2^n \end{align*}

If we had the same bound on the first difference as well, then we'd have

$\mu(A_n \triangle A) = \mu(A_n \setminus A) + \mu(A \setminus A_n) < 1/2^{n-1} \rightarrow 0$ as $n \rightarrow \infty$

Which would prove convergence of the subsequence to $A$.

But a Cauchy sequence with a convergent subsequence converges to the same limit, which would prove the result.

I was working with a similar problem recently. I will replace notation $M$ by $\mathcal{M}$ to distinguish a set and a $\sigma$-algebra. Here's my opinion:

1. $d(A,B):=\mu(A\Delta B)$ is just a pseudometric since it doesn't guarantee that \begin{align} d(A,B)=0\iff A=B. \end{align} To make $d$ a metric, we should consider an equivalence relation $\sim$ defined by \begin{align} A\sim B\quad\mbox{if}\quad \mu(A\Delta B)=0 \end{align} and define the metric $d$ on $\mathcal{M}/\sim$ by \begin{align} d(\tilde{A},\tilde{B})=\mu(A\Delta B) \end{align} where $\tilde{A}$, $\tilde{B}$ are equivalence classes in $\mathcal{M}/\sim$ and $A$, $B$ are their representatives, respectively. Therefore, I think you need to change your argument accordingly.
2. I would set \begin{align} B_n=\bigcup_{k=n}^\infty{A_k}. \end{align} Two things need to be proved: \begin{align} \mu(B_n\Delta A)\rightarrow0\\ \mu(A_n\Delta B_n)\rightarrow0 \end{align} The first one follows from that measure is continuous from above. As for the second one, note that \begin{align} \bigcup_{k=n}^\infty{A_k}\setminus A_n&=(A_{n+1}\setminus A_n)\cup(A_{n+2}\setminus A_n)\cup\dots\\ &=(A_{n+1}\setminus A_n)\cup(A_{n+2}\setminus(A_n\cup A_{n+1}))\cup\dots\\ &\subset(A_{n+1}\setminus A_n)\cup(A_{n+2}\setminus A_{n+1})\cup\dots. \end{align} Next, we have \begin{align} \mu(A_n\Delta A)\leq\mu(A_n\Delta B_n)+\mu(B_n\Delta A) \end{align} and the result follows.
• I avoided getting into the equivalence relation since it doesn't affect the argument (you'll notice I took $M_i$ from the metric space, not the $\sigma$-algebra). The trick to replace $A_{n+i} \setminus A_n$ with $A_{n+i} \setminus A_{n+i-1}$ definitely helps though - it seems I was trying to use subadditivity too soon. – Saigyouji Oct 16 '13 at 13:08
• Well, there are some issues if not getting into the equivalence relation. First, $\limsup{M_n}\neq\limsup{A_n}$, you can just say $\mu(\limsup{M_n}\Delta\limsup{A_n})=0$. And second, since the limit is not unique, the sequence is not convergent. – Pin Oct 16 '13 at 14:51
• I think we can not talk about completeness in a pseudometric space. Another thing is that it would be clearer if you explain the step $\mu(\bigcap_{k=1}^\infty\bigcup_{j=k}^\infty{(A_j\setminus A_n)})=\lim_{k\rightarrow\infty}\mu(\cup_{j=k}^\infty{(A_j\setminus A_n)})$. Here you change the order of taking the measure and taking the limit, and I don't think it's a trivial thing. – Pin Oct 16 '13 at 15:07
• As for "changing the order of taking the measure and taking the limit", I"m just using measure continuity there. We have an intersection of shrinking sets of finite measure, so the measure of the intersection is the limit of the measures. – Saigyouji Oct 16 '13 at 15:48
• Consider $M_n=\{0,1\}$ if $n$ is odd and $M_n=\{0\}$ otherwise. $A_n=M_{2n}$. Then $\limsup{A_n}=\{0\}$ but $\limsup{M_n}=\{0,1\}$. – Pin Oct 16 '13 at 17:02

Let's denote our $\sigma$-algebra by $\mathcal A$ where we define $\mathcal A/\!\sim$ to be the set of equivalence relations on $\mathcal A$ such that $E\sim F$ iff $\mu(E\,\Delta \,F)=0.$

Note that $E \Delta G \subseteq E \Delta F \cup F \Delta G$ since:

• Let $x \in E \Delta G = (E \cup G) \setminus (E \cap G) = (E \setminus G) + (G \setminus E)$. Suppose, without loss of generality, that $x \in E$ and $x \notin G$. If $x \in F$, then $x \in F \cup G$ and $x \notin F \cap G$, so $x \in (F \cup G) \setminus (F \cap G)$. If $x \notin F$, then $x \in E \cup F$, but $x \notin (E \cap F)$, so $x \in (E \cup F) \setminus (E \cap F)$. Hence, we can conclude that $(E \cup G) \setminus (E \cap G) \subseteq (E \cup F) \setminus (E \cap F) \cup (F \cup G) \setminus (F \cap G)$.

Now we want to show completeness. Let $(A_n)$ be a Cauchy sequence under the metric, then given $\varepsilon > 0$, there exists $N > 0$ such that if $n, m > N$, then $d(A_n, A_m) < \varepsilon$. Let $j \in \mathbb N$, then there exists $n_j > 0$ such that if $n, m > n_j$, then $d(A_n, A_m) < \frac{1}{2^j}$. Without loss of generality, choose $n_j < n_{j + 1}$. Notice that if $i < j$, then $n_i < n_j$ and then $d(A_{n_i}, A_{n_j}) < \frac{1}{2^i}$. Define $A = \liminf A_{n_k} = \bigcup_{k = 1}^\infty \bigcap_{j = k}^\infty A_{n_j}$ and define $B_k = \bigcap_{j = k}^\infty A_{n_j}$. Let $n > n_k$ and observe that $d(A, A_n) \leq d(A, A_{n_k}) + d(A_{n_k}, A_n)$. Since $n > n_k$, then $d(A_{n_k}, A_n) < \frac{1}{2^k}$. Observe that $A \Delta A_{n_k} \subseteq A \Delta B_k \cup B_k \Delta A_{n_k} \subseteq \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}$. The latter inclusion takes some showing:

• ($A \Delta B_k \subseteq \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}$): Let $x \in A \Delta B_k$. Observe that if $x \in B_k$, then immediately $x \in A$ since $A = \bigcup_{k = 1}^\infty B_k$, so we can't have any elements such that $x \in B_k$ and $x \notin A$. So consider $x \in A = \bigcup_{i = 1}^\infty \bigcap_{j = i}^\infty A_{n_j}$, but $x \notin B_k = \bigcap_{j = k}^\infty A_{n_j}$. This means there exists $k'$ such that $x \in \bigcap_{j = k'} A_{n_j} = B_{k'}$. We can find the smallest $k'$ such that $x \in B_{k'}$, but $x \notin B_{k' - 1}$ with $k' - 1 \geq k$. This means that $x \in \bigcap_{j = k'}^\infty A_{n_j}$ but $x \notin \bigcap_{j = k' - 1}^\infty A_{n_j}$ or in other words, $x \in A_{n_{k'}}$ but $x \notin A_{n_{k' - 1}}$ so $x \in A_{n_{k' - 1}} \Delta A_{n_{k'}}$. Since $k' - 1 \geq k$, we can conclude that $x \in \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}$.
• ($B_k \Delta A_{n_k} \subseteq \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}$): Let $x \in B_k \Delta A_{n_k}$. Observe that if $x \in B_k$, then immediately $x \in A_{n_k}$ since $B_k = \bigcap_{j = k}^\infty A_{n_j}$, so we can't have any elements such that $x \in B_k$ and $x \notin A_{n_k}$. So consider $x \in A_{n_k}$, but $x \notin B_k = \bigcap_{j = k}^\infty A_{n_j}$. This means that there exists $k' > k$ such that $x \notin A_{n_{k'}}$. Find the smallest $k'$ such that $x \notin A_{n_{k'}}$ but $x \in A_{n_{k' - 1}}$ with $k' - 1 \geq k$. This means that $x \in A_{n_{k' - 1}} \Delta A_{n_{k'}}$. Since $k' - 1 \geq k$, we can conclude that $x \in \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}$.

Now, using monotonicity and subadditivity of measure, observe that \begin{align*} d(A_, A_{n_k}) &= \mu(A \Delta A_{n_k}) \\ &\leq \mu(A \Delta B_k \cup B_k \Delta A_{n_k})\\ &\leq \mu \bigg( \bigcup_{j = k}^\infty A_{n_j} \Delta A_{n_{j + 1}}\bigg) \\ &\leq \sum_{j = k}^\infty \mu(A_{n_j} \Delta A_{n_{j + 1}})\\ &= \sum_{j = k}^\infty d(A_{n_j}, A_{n_{j + 1}})\\ &< \sum_{j = k}^\infty \frac{1}{2^j} = 1 - \sum_{j = 1}^{k - 1} \frac{1}{2^j} = 1 - \frac{2^{k - 1} - 1}{2^{k - 1}} = \frac{2^{k - 1} - 2^{k - 1} + 1}{2^{k - 1}} = \frac{1}{2^{k - 1}} \end{align*}

Hence, if $n > n_k$, then $d(A, A_n) \leq d(A, A_{n_k}) + d(A_{n_k}, A_n) < \frac{1}{2^{k - 1}} + \frac{1}{2^k}$ which converges to zero as $k \to \infty$. Thus by definition $A_n \to A$ under the metric. Conclude that every Cauchy sequence converges to an element of our space, and hence $\mathcal A /\! \sim$ is a complete metric space.