Non-Measurable Sets

Probability and measure theory relies on the concept of measurable sets. On the real numbers ℝ, in particular, there are several different sigma-algebras which are commonly used, and a set is said to be measurable if it lies in the one under consideration. Probabilities and measures are only defined for events lying in a specific sigma-algebra, so it is essential to know if sets are measurable. Fortunately, most simply constructed events will indeed be measurable, but this is not always the case. In fact, once we start working with more complex setups, such as continuous-time stochastic processes observed at random times, non-measurable sets occur more commonly than might be expected. To avoid such issues, it is usual to enlarge the underlying sigma-algebra defining a probability space as much as possible.

The Borel sets form the smallest sigma-algebra containing the open sets or, equivalently, containing all intervals. This is denoted as ${\mathcal B({\mathbb R})}$ , which I will also shorten to ${\mathcal B}$ . An explicit construction of a non-Borel set was given by Lusin in 1927. Every irrational real number can be expressed uniquely as a continued fraction

$\displaystyle x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots\,}}}}$

where a₀ is an integer and a_i are positive integers for i ≥ 1. Lusin considered the set of irrationals whose continued fraction coefficients contain a subsequence a_k₁, a_k₂, … such that each term is a divisor of the subsequent term.

Other examples can be given along similar lines to Lusin’s. Every real number has a binary expansion

$\displaystyle x=a_0.a_1a_2a_3\ldots$

where a₀ is an integer and a_i is in {0, 1} for each i ≥ 1. Consider the set of reals having a binary expansion for which there is an infinite sequence of positive integers k₁, k₂, …, each term strictly dividing the next, such that a_k_i = 1. I will give proofs that these examples are non-Borel in this post.

There is a general method of enlarging sigma-algebras known as the completion. Consider a measure μ defined on a measurable space ${(X,\mathcal E)}$ consisting of sigma-algebra ${\mathcal E}$ on set X. The completion ${\mathcal E_\mu}$ consists of all subsets S ⊆ X which can be sandwiched between sets in ${\mathcal E}$ whose difference has zero measure. That is, A ⊆ S ⊆ B for ${ A,B\in\mathcal E}$ with μ(B ∖ A) = 0. It can be shown that ${\mathcal E_\mu}$ is a sigma-algebra containing ${\mathcal E}$ , and μ uniquely extends to a measure on this by taking μ(S) = μ(A) = μ(B) for S, A, B as above.

The Lebesgue measure λ is uniquely defined on the Borel sets by specifiying its value on intervals as λ((a, b)) = b – a. The completion ${\mathcal B_\lambda}$ is the Lebesgue sigma-algebra, which I will denote by ${\mathcal L}$ . Usually, when saying that a subset of the reals is measurable without further qualification, it is understood to mean that it is in ${\mathcal L}$ . The non-Borel set constructed by Lusin can be shown to be measurable (in fact, its complement has zero Lebesgue measure).

While the Lebesgue measure extends uniquely to ${\mathcal L}$ , this is not true for for all measures defined on the Borel sigma-algebra. In particular, it will not be true for singular measures, which assign a positive value to some Lebesgue-null sets. An example is the uniform probability measure (or, Haar measure) on the Cantor middle-thirds set C. This has zero Lebesgue measure, so every subset of C is in ${\mathcal L}$ , but the uniform measure on C cannot be extended uniquely to all subsets. For this reason, universal completions are often used. For a measurable space ${(X,\mathcal E)}$ , the universal completion ${\bar{\mathcal E}}$ consists of the subsets of X which lie in the completion of ${\mathcal E}$ with respect to every possible sigma-finite measure.

$\displaystyle \bar{\mathcal E}=\bigcap_\mu\mathcal E_\mu.$

The intersection is taken over all sigma-finite measures μ on ${\mathcal E}$ . It is enough to take the intersection over finite or, even, probability measures, since every sigma-finite measure is equivalent to such. The universal completion is a bit tricky to understand in an explicit way but, by construction, all sigma-finite measures on a sigma-algebra extend uniquely to its universal completion. It can be shown that Lusin’s example of a non-Borel set does lie in the universal completion ${\bar{\mathcal B}}$ .

Finally, the power set ${\mathcal P(X)}$ consisting of all subsets of a set X is a sigma-algebra. For uncountable sets such as the reals, this is often too large to be of use and measures cannot be extended in any unique way. However, we have four common sigma-algebras of the real numbers,

$\displaystyle \mathcal B\subseteq\bar{\mathcal B}\subseteq\mathcal L\subseteq\mathcal P.$

(1)

In this post, I show that each of these inclusions is strict. That is, there are subsets of the reals which are not Lebesgue measurable, there are Lebesgue sets which are not in the universal completion ${\bar{\mathcal B}}$ , and there are sets in ${\bar{\mathcal B}}$ which are not Borel. Lusin’s construction is an example of the latter. The strictness of the other two inclusions does depend crucially on the axiom of choice so, unlike Lusin’s set, the examples demonstrating that these are strict are not explicit. Continue reading “Non-Measurable Sets” →

Proof of Measurable Section

I will give a proof of the measurable section theorem, also known as measurable selection. Given a complete probability space ${(\Omega,\mathcal F,{\mathbb P})}$ , we denote the projection from ${\Omega\times{\mathbb R}}$ by

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} &\displaystyle\pi_\Omega\colon \Omega\times{\mathbb R}\rightarrow\Omega,\smallskip\\ &\displaystyle\pi_\Omega(\omega,t)=\omega. \end{array}$

By definition, if ${S\subseteq\Omega\times{\mathbb R}}$ then, for every ${\omega\in\pi_\Omega(S)}$ , there exists a ${t\in{\mathbb R}}$ such that ${(\omega,t)\in S}$ . The measurable section theorem says that this choice can be made in a measurable way. That is, using ${\mathcal B({\mathbb R})}$ to denote the Borel sigma-algebra, if S is in the product sigma-algebra ${\mathcal F\otimes\mathcal B({\mathbb R})}$ then ${\pi_\Omega(S)\in\mathcal F}$ and there is a measurable map

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} &\displaystyle\tau\colon\pi_\Omega(S)\rightarrow{\mathbb R},\smallskip\\ &\displaystyle(\omega,\tau(\omega))\in S. \end{array}$

It is convenient to extend ${\tau}$ to the whole of ${\Omega}$ by setting ${\tau=\infty}$ outside of ${\pi_\Omega(S)}$ .

measurable section — Figure 1: A section of a measurable set

We consider measurable functions ${\tau\colon\Omega\rightarrow{\mathbb R}\cup\{\infty\}}$ . The graph of ${\tau}$ is

$\displaystyle [\tau]=\left\{(\omega,\tau(\omega))\colon\tau(\omega)\in{\mathbb R}\right\}\subseteq\Omega\times{\mathbb R}.$

The condition that ${(\omega,\tau(\omega))\in S}$ whenever ${\tau < \infty}$ can then be expressed by stating that ${[\tau]\subseteq S}$ . This also ensures that ${\{\tau < \infty\}}$ is a subset of ${\pi_\Omega(S)}$ , and ${\tau}$ is a section of S on the whole of ${\pi_\Omega(S)}$ if and only if ${\{\tau < \infty\}=\pi_\Omega(S)}$ .

The proof of the measurable section theorem will make use of the properties of analytic sets and of the Choquet capacitability theorem, as described in the previous two posts. [Note: I have since posted a more direct proof which does not involve such prerequisites.] Recall that a paving ${\mathcal E}$ on a set X denotes, simply, a collection of subsets of X. The pair ${(X,\mathcal E)}$ is then referred to as a paved space. Given a pair of paved spaces ${(X,\mathcal E)}$ and ${(Y,\mathcal F)}$ , the product paving ${\mathcal E\times\mathcal F}$ denotes the collection of cartesian products ${A\times B}$ for ${A\in\mathcal E}$ and ${B\in\mathcal F}$ , which is a paving on ${X\times Y}$ . The notation ${\mathcal E_\delta}$ is used for the collection of countable intersections of a paving ${\mathcal E}$ .

We start by showing that measurable section holds in a very simple case where, for the section of a set S, its debut will suffice. The debut is the map

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} &\displaystyle D(S)\colon\Omega\rightarrow{\mathbb R}\cup\{\pm\infty\},\smallskip\\ &\displaystyle \omega\mapsto\inf\left\{t\in{\mathbb R}\colon (\omega,t)\in S\right\}. \end{array}$

We use the convention that the infimum of the empty set is ${\infty}$ . It is not clear that ${D(S)}$ is measurable, and we do not rely on this, although measurable projection can be used to show that it is measurable whenever S is in ${\mathcal F\otimes\mathcal B({\mathbb R})}$ .

Lemma 1 Let ${(\Omega,\mathcal F)}$ be a measurable space, ${\mathcal K}$ be the collection of compact intervals in ${{\mathbb R}}$ , and ${\mathcal E}$ be the closure of the paving ${\mathcal{F\times K}}$ under finite unions.

Then, the debut ${D(S)}$ of any ${S\in\mathcal E_\delta}$ is measurable and its graph ${[D(S)]}$ is contained in S.

Continue reading “Proof of Measurable Section” →

Choquet’s Capacitability Theorem and Measurable Projection

In this post I will give a proof of the measurable projection theorem. Recall that this states that for a complete probability space ${(\Omega,\mathcal F,{\mathbb P})}$ and a set S in the product sigma-algebra ${\mathcal F\otimes\mathcal B({\mathbb R})}$ , the projection, ${\pi_\Omega(S)}$ , of S onto ${\Omega}$ , is in ${\mathcal F}$ . The previous post on analytic sets made some progress towards this result. Indeed, using the definitions and results given there, it follows quickly that ${\pi_\Omega(S)}$ is ${\mathcal F}$ -analytic. To complete the proof of measurable projection, it is necessary to show that analytic sets are measurable. This is a consequence of Choquet’s capacitability theorem, which I will prove in this post. Measurable projection follows as a simple consequence.

The condition that the underlying probability space is complete is necessary and, if this condition was dropped, then the result would no longer hold. Recall that, if ${(\Omega,\mathcal F,{\mathbb P})}$ is a probability space, then the completion, ${\mathcal F_{\mathbb P}}$ , of ${\mathcal F}$ with respect to ${{\mathbb P}}$ consists of the sets ${A\subseteq\Omega}$ such that there exists ${B,C\in\mathcal F}$ with ${B\subseteq A\subseteq C}$ and ${{\mathbb P}(B)={\mathbb P}(C)}$ . The probability space is complete if ${\mathcal F_{\mathbb P}=\mathcal F}$ . More generally, ${{\mathbb P}}$ can be uniquely extended to a measure ${\bar{\mathbb P}}$ on the sigma-algebra ${\mathcal F_{\mathbb P}}$ by setting ${\bar{\mathbb P}(A)={\mathbb P}(B)={\mathbb P}(C)}$ , where B and C are as above. Then ${(\Omega,\mathcal F_{\mathbb P},\bar{\mathbb P})}$ is the completion of ${(\Omega,\mathcal F,{\mathbb P})}$ .

In measurable projection, then, it needs to be shown that if ${A\subseteq\Omega}$ is the projection of a set in ${\mathcal F\otimes\mathcal B({\mathbb R})}$ , then A is in the completion of ${\mathcal F}$ . That is, we need to find sets ${B,C\in\mathcal F}$ with ${B\subseteq A\subseteq C}$ with ${{\mathbb P}(B)={\mathbb P}(C)}$ . In fact, it is always possible to find a ${C\supseteq A}$ in ${\mathcal F}$ which minimises ${{\mathbb P}(C)}$ , and its measure is referred to as the outer measure of A. For any probability measure ${{\mathbb P}}$ , we can define an outer measure on the subsets of ${\Omega}$ , ${{\mathbb P}^*\colon\mathcal P(\Omega)\rightarrow{\mathbb R}^+}$ by approximating ${A\subseteq\Omega}$ from above,

$\displaystyle {\mathbb P}^*(A)\equiv\inf\left\{{\mathbb P}(B)\colon B\in\mathcal F, A\subseteq B\right\}.$

(1)

Similarly, we can define an inner measure by approximating A from below,

$\displaystyle {\mathbb P}_*(A)\equiv\sup\left\{{\mathbb P}(B)\colon B\in\mathcal F, B\subseteq A\right\}.$

It can be shown that A is ${\mathcal F}$ -measurable if and only if ${{\mathbb P}_*(A)={\mathbb P}^*(A)}$ . We will be concerned primarily with the outer measure ${{\mathbb P}^*}$ , and will show that that if A is the projection of some ${S\in\mathcal F\otimes\mathcal B({\mathbb R})}$ , then A can be approximated from below in the following sense: there exists ${B\subseteq A}$ in ${\mathcal F}$ for which ${{\mathbb P}^*(B)={\mathbb P}^*(A)}$ . From this, it will follow that A is in the completion of ${\mathcal F}$ .

It is convenient to prove the capacitability theorem in slightly greater generality than just for the outer measure ${{\mathbb P}^*}$ . The only properties of ${{\mathbb P}^*}$ that are required is that it is a capacity, which we now define. Recall that a paving ${\mathcal E}$ on a set X is simply any collection of subsets of X, and we refer to the pair ${(X,\mathcal E)}$ as a paved space.

Definition 1 Let ${(X,\mathcal E)}$ be a paved space. Then, an ${\mathcal E}$ -capacity is a map ${I\colon\mathcal P(X)\rightarrow{\mathbb R}}$ which is increasing, continuous along increasing sequences, and continuous along decreasing sequences in ${\mathcal E}$ . That is,

if ${A\subseteq B}$ then ${I(A)\le I(B)}$ .

if ${A_n\subseteq X}$ is increasing in n then ${I(A_n)\rightarrow I(\bigcup_nA_n)}$ as ${n\rightarrow\infty}$ .

if ${A_n\in\mathcal E}$ is decreasing in n then ${I(A_n)\rightarrow I(\bigcap_nA_n)}$ as ${n\rightarrow\infty}$ .

As was claimed above, the outer measure ${{\mathbb P}^*}$ defined by (1) is indeed a capacity.

Lemma 2 Let ${(\Omega,\mathcal F,{\mathbb P})}$ be a probability space. Then,

${{\mathbb P}^*(A)={\mathbb P}(A)}$ for all ${A\in\mathcal F}$ .

For all ${A\subseteq\Omega}$ , there exists a ${B\in\mathcal F}$ with ${A\subseteq B}$ and ${{\mathbb P}^*(A)={\mathbb P}(B)}$ .

${{\mathbb P}^*}$ is an ${\mathcal F}$ -capacity.

Continue reading “Choquet’s Capacitability Theorem and Measurable Projection” →

	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Brownian Bridges
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula
	Anonymous on Spitzer’s Formula