# Analytic Sets

We will shortly give a proof of measurable projection and, also, of the section theorems. Starting with the projection theorem, recall that this states that if ${(\Omega,\mathcal F,{\mathbb P})}$ is a complete probability space, then the projection of any measurable subset of ${\Omega\times{\mathbb R}}$ onto ${\Omega}$ is measurable. To be precise, the condition is that S is in the product sigma-algebra ${\mathcal{F}\otimes\mathcal B({\mathbb R})}$, where ${\mathcal B({\mathbb R})}$ denotes the Borel sets in ${{\mathbb R}}$, and ${\pi\colon\Omega\times{\mathbb R}\rightarrow\Omega}$ is the projection ${\pi(\omega,t)=\omega}$. Then, ${\pi(S)\in\mathcal{F}}$. Although it looks like a very basic property of measurable sets, maybe even obvious, measurable projection is a surprisingly difficult result to prove. In fact, the requirement that the probability space is complete is necessary and, if it is dropped, then ${\pi(S)}$ need not be measurable. Counterexamples exist for commonly used measurable spaces such as ${\Omega= {\mathbb R}}$ and ${\mathcal F=\mathcal B({\mathbb R})}$. This suggests that there is something deeper going on here than basic manipulations of measurable sets.

The techniques which will be used to prove the projection theorem involve analytic sets, which will be introduced in this post, with the proof of measurable projection to follow in the next post. [Note: I have since posted a more direct proof of measurable projection and section, which does not make use of analytic sets.] These results can also be used to prove the optional and predictable section theorems which, at first appearances, seem to be quite basic statements. The section theorems are fundamental to the powerful and interesting theory of optional and predictable projection which is, consequently, generally considered to be a hard part of stochastic calculus. In fact, the projection and section theorems are really not that hard to prove, although the method given here does require stepping outside of the usual setup used in probability and involves something more like descriptive set theory.

Let us consider how one might try and approach a proof of the projection theorem. As with many statements regarding measurable sets, we could try and prove the result first for certain simple sets, and then generalise to measurable sets by use of the monotone class theorem or similar. For example, let ${\mathcal S}$ denote the collection of all ${S\subseteq\Omega\times{\mathbb R}}$ for which ${\pi(S)\in\mathcal F}$. It is straightforward to show that any finite union of sets of the form ${A\times B}$ for ${A\in\mathcal F}$ and ${B\in\mathcal B({\mathbb R})}$ are in ${\mathcal S}$. If it could be shown that ${\mathcal S}$ is closed under taking limits of increasing and decreasing sequences of sets then the result would follow from the monotone class theorem. Increasing sequences are easily handled — if ${S_n}$ is a sequence of subsets of ${\Omega\times{\mathbb R}}$ then from the definition of the projection map,

$\displaystyle \pi\left(\bigcup_{n=1}^\infty S_n\right)=\bigcup_{n=1}^\infty\pi\left(S_n\right).$

If ${S_n\in\mathcal S}$ for each n, this shows that the union ${\bigcup_nS_n}$ is again in ${\mathcal S}$. Unfortunately, decreasing sequences are much more problematic. If ${S_n\subseteq S_m}$ for all ${n\ge m}$ then we would like to use something like

 $\displaystyle \pi\left(\bigcap_{n=1}^\infty S_n\right)=\bigcap_{n=1}^\infty\pi\left(S_n\right).$ (1)

However, this identity does not hold in general. For example, consider the decreasing sequence ${S_n=\Omega\times(n,\infty)}$. Then, ${\pi(S_n)=\Omega}$ for all n, but ${\bigcap_nS_n}$ is empty, contradicting (1). There is some interesting history involved here. In a paper published in 1905, Henri Lebesgue claimed that the projection of a Borel subset of ${{\mathbb R}^2}$ onto ${{\mathbb R}}$ is itself measurable. This was based upon mistakenly applying (1). The error was spotted in around 1917 by Mikhail Suslin, who realised that the projection need not be Borel, and lead him to develop the theory of analytic sets.

Actually, there is at least one situation where (1) can be shown to hold. Suppose that for each ${\omega\in\Omega}$, the slices

$\displaystyle S_n(\omega)=\{t\in{\mathbb R}\colon(\omega,t)\in S_n\}$

are compact. For each ${\omega\in\bigcap_n\pi(S_n)}$, ${S_n(\omega)}$ is a decreasing sequence of compact sets, so has nonempty intersection. Then, ${\omega\in\pi(\bigcap_nS_n)}$ and (1) follows. This argument is connected to the use of compactness in the definition of analytic sets given below. However, the compactness property will not be central to any of the arguments here and, in fact, all the results stated below would hold if it is dropped, but it will be a vital part in the proof of the projection theorem in the next post.

One way to try and fix the method considered above to prove the projection theorem is to put additional restrictions on the collection ${\mathcal{S}}$ of subsets of ${\Omega\times{\mathbb R}}$. That is, for ${S\in\mathcal S}$, in addition to requiring that ${\pi(S)}$ is measurable, we include constraints that ensure that ${\mathcal S}$ is closed under limits of increasing and decreasing sequences. One way of achieving this is to let ${\mathcal S}$ be the collection of ${\mathcal F\times\mathcal B}$-analytic sets, as defined below.

Roughly, then, the outline of the proof of the measurable projection theorem the following:

1. Every set in ${\mathcal F\otimes\mathcal B({\mathbb R})}$ is analytic.
2. The projection ${\pi\colon\Omega\times{\mathbb R}\rightarrow\Omega}$ maps analytic sets to analytic sets.
3. Every analytic subset of ${\Omega}$ is in ${\mathcal F}$.

The first point is proven below in corollary 4, and relies on showing that countable unions and intersections of analytic sets are analytic. The second point is stated as theorem 2, and is a direct consequence of the definitions. Finally, the third point uses Choquet’s capacitability theorem, and will be left until the next post.

One issue with introducing the concept of analytic sets is to settle on which definition to use. The fact that there are many different looking, but equivalent, ways of defining them just shows how they are a fundamental and flexible idea. Often, they are introduced as specific to Polish spaces. We would prefer not to restrict to this setting here. Alternatively, they can be defined using the Suslin operation. However, I will follow Bichteler (Stochastic Integration With Jumps, 2002), which seems to be one of the most direct approaches for our purposes.

I now introduce a bit of notation. The term paving on a set X will be used to denote, simply, any collection of subsets of X. Then, for a paving ${\mathcal E}$ on a set X, the pair ${(X,\mathcal E)}$ will be referred to as a paved space. Examples of paved spaces include any topological space with the paving given by either its open or its closed subsets, and any measurable space where the paving is a sigma-algebra. For a paving ${\mathcal E}$, we use ${\mathcal E_\sigma}$ and ${\mathcal E_\delta}$ to represent its closure under, respectively, countable unions and countable intersections.

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} &\displaystyle \mathcal E_\sigma=\left\{\bigcup_{n=1}^\infty A_n\colon A_n\in\mathcal E\right\}\smallskip\\ &\displaystyle \mathcal E_\delta=\left\{\bigcap_{n=1}^\infty A_n\colon A_n\in\mathcal E\right\} \end{array}$

It is clear that ${\mathcal E\subseteq\mathcal E_\sigma,\mathcal E_\delta}$, that ${\mathcal E_{\sigma\sigma}=\mathcal E_{\sigma}}$, and that ${\mathcal E_{\delta\delta}=\mathcal E_\delta}$.

We say that a paving ${\mathcal K}$ is compact if every ${\mathcal S\subseteq\mathcal K}$ with empty intersection has a finite subset ${\mathcal S^\prime\subseteq\mathcal S}$ with empty intersection. For example, a Hausdorff space together with its compact subsets is a compact paved space. For two paved spaces ${(X,\mathcal E)}$ and ${(Y,\mathcal F)}$, we use ${\mathcal E\times\mathcal F}$ to denote the paving on the Cartesian product ${X\times Y}$ consisting of the sets ${A\times B}$ for ${A\in\mathcal E}$ and ${B\in\mathcal F}$. It is straightforward to show that the product ${\mathcal E\times\mathcal F}$ of compact pavings ${\mathcal E}$ and ${\mathcal F}$ is itself compact. Finally, for any two sets X and Y, ${\pi_X\colon X\times Y\rightarrow X}$ will be used to denote the projection ${\pi_X(x,y)=x}$.

Definition 1 Let ${(X,\mathcal{E})}$ be a paved space. Then, a set ${A\subseteq X}$ is ${\mathcal{E}}$-analytic if and only if there exists a compact paved space ${(K,\mathcal{K})}$ and ${S\in(\mathcal{E}\times\mathcal{K})_{\sigma\delta}}$ such that ${A=\pi_X(S)}$.

This definition makes use of an auxilliary compact paved space. It does not matter at the moment what this space might be, but it is possible show that it is always possible to take, for example, ${K={\mathbb R}}$ and ${\mathcal K}$ to be the collection of closed bounded intervals.

We use ${\mathcal{A}(\mathcal{E})}$ to denote the collection of all ${\mathcal{E}}$-analytic sets in ${X}$. Clearly, every element of ${\mathcal{E}}$ is itself ${\mathcal{E}}$-analytic,

 $\displaystyle \mathcal{E}\subseteq\mathcal{A}(\mathcal{E}).$ (2)

From the definition of ${(\mathcal E\times\mathcal K)_{\sigma\delta}}$, the set S in definition 1 can be expressed as

$\displaystyle S=\bigcap_{m=1}^\infty\bigcup_{n=1}^\infty E_{mn}\times L_{mn},$

for sets ${E_{mn}\in\mathcal E}$ and ${L_{mn}\in\mathcal K}$. This can be rearranged as

$\displaystyle S=\bigcup_{\omega\in{\mathbb N}^{\mathbb N}}\left(\bigcap\nolimits_n E_{n,\omega_n}\right)\times\left(\bigcap\nolimits_n L_{n,\omega_n}\right).$

Consider the set C of ${\omega\in{\mathbb N}^{\mathbb N}}$ such that ${\bigcap_n L_{n,\omega_n}}$ is nonempty. Compactness of the paving ${\mathcal K}$ ensures that C is closed in the product topology. The set ${A=\pi_X(S)}$ can then be expressed purely in terms of the closed set ${C\subseteq{\mathbb N}^{\mathbb N}}$ and ${E_{mn}\in\mathcal E}$ as,

 $\displaystyle A = \bigcup_{\omega\in C}\bigcap_{n=1}^\infty E_{n,\omega_n}.$ (3)

This shows that the precise details of the auxiliary paved space in definition 1 are not important, and all that matters is which subsets of ${\mathcal K}$ have nonempty intersection. Note that the union in (3) need not be countable, so we cannot infer the measurability of A.

As was promised, we show that projections of analytic sets are analytic. This is a direct consequence of the definition.

Theorem 2 Let ${(X,\mathcal{E})}$ and ${(Y,\mathcal{F})}$ be paved spaces, with ${\mathcal{F}}$ compact. Then, for any ${\mathcal{E}\times\mathcal{F}}$-analytic set ${S}$, the projection ${\pi_X(S)}$ is ${\mathcal{E}}$-analytic.

Proof: As S is analytic, there is a compact paved space ${(K,\mathcal{K})}$ such that S can be expressed be expressed as a projection, ${S=\pi_{X\times Y}(U)}$ for some ${U\in(\mathcal{E\times F\times K})_{\sigma\delta}}$. As both ${\mathcal{F}}$ and ${\mathcal{K}}$ are compact, it follows that ${\mathcal{\tilde K}\equiv\mathcal{F\times K}}$ is compact, and ${\pi_X(S)=\pi_X(U)}$ for ${U\in(\mathcal{E\times\tilde K})_{\sigma\delta}}$. ⬜

We move on to the main statement and proof of this post, that countable unions and intersections of analytic sets are analytic. For a metric space X with collection of closed sets ${\mathcal F}$ and open sets ${\mathcal G}$, this can be used to show that all Borel sets are both ${\mathcal F}$-analytic and ${\mathcal G}$-analytic. Similarly, for a pair of measurable spaces ${(X,\mathcal E)}$ and ${(Y,\mathcal F)}$, it shows that product sigma-algebra ${\mathcal E\otimes\mathcal F}$ consists of ${\mathcal E\times\mathcal F}$-analytic sets.

Theorem 3 Let ${(X,\mathcal{E})}$ be a paved space and ${(A_n)_{n=1,2,\ldots}}$ be ${\mathcal{E}}$-analytic. Then, ${\bigcup_n A_n}$ and ${\bigcap_n A_n}$ are also ${\mathcal{E}}$-analytic. Equivalently,

$\displaystyle \mathcal{A}(\mathcal{E})_\sigma=\mathcal{A}(\mathcal{E})_\delta=\mathcal{A}(\mathcal{E}).$

Proof: As ${A_n}$ are ${\mathcal{E}}$-analytic sets, there are compact paved spaces ${(K_n,\mathcal{K}_n)}$ and sets ${S_n\in(\mathcal{E}\times\mathcal{K}_n)_{\sigma\delta}}$ such that ${A_n=\pi_X(S_n)}$. We outline two different ways to embed the pavings ${\mathcal{K}_n}$ into a larger paved space ${(K,\mathcal{K})}$, which, respectively, will lead to the representation of the union and the intersection of the ${A_n}$ as analytic sets.

First consider the cartesian product ${K=\prod_nK_n}$. This comes with projections ${\pi_nK\rightarrow K_n}$ satisfying ${\bigcap_n\pi_n^{-1}(L_n)\not=\emptyset}$ for nonempty ${L_n\subseteq K_n}$. Let ${\mathcal K}$ be the collection of subsets of K of the form ${\pi_n^{-1}(L)}$ for some ${n\in{\mathbb N}}$ and ${L\in\mathcal K_n}$.

It can be seen that ${\mathcal K}$ is a compact paving. Consider a collection of sets ${\pi_{n_k}^{-1}(L_k)\in\mathcal K}$ as ${k}$ runs through some index set I. The intersection is

$\displaystyle \bigcap_k\pi_{n_k}^{-1}(L_k)=\bigcap_{n=1}^\infty\bigcap_{n_k=n}\pi_n^{-1}\left(L_k\right)=\bigcap_{n=1}^\infty\pi_n^{-1}\left(\bigcap_{n_k=n}L_k\right).$

The only way that this can be empty is if there is some n such that ${\bigcap_{n_k=n}L_k}$ is empty. By compactness of ${\mathcal{K}_n}$, this shows that there is a finite ${J\subseteq I}$ such that ${n_k=n}$ for ${k\in J}$ and ${\bigcap_{k\in J}L_k}$ is empty. So, ${\mathcal K}$ is compact.

If we let ${\rho_n\colon X\times K\rightarrow X\times K_n}$ be the projection ${\rho_n(x,y)=(x,\pi_n(y))}$, then ${\rho_n^{-1}(Z)\in\mathcal E\times\mathcal K}$ for all ${Z\in\mathcal E\times\mathcal K_n}$. If follows that, for ${S_n\in(\mathcal E\times\mathcal K_n)_{\sigma\delta}}$ then ${\rho^{-1}_n(S_n)}$ is in ${(\mathcal E\times\mathcal K)_{\sigma\delta}}$. Using ${A_n=\pi_X(S_n)}$, we have that an ${x\in X}$ is in ${A_n}$ if and only if, for all n, there is a ${y_n\in K_n}$ such that ${(x,y_n)\in S_n}$. Choosing ${y\in K}$ with ${\pi_n(y)=y_n}$, this is equivalent to the existence of a ${y\in K}$ such that, for all n, ${(x,y)\in\rho_n^{-1}(S_n)}$. Hence,

$\displaystyle \bigcap_{n=1}^\infty A_n =\pi_X\left(\bigcap_n\rho_n^{-1}(S_n)\right).$

This expresses ${\bigcap_nA_n}$ as the projection of a set in ${(\mathcal E\times\mathcal K)_{\sigma\delta}}$, so is ${\mathcal E}$-analytic.

Next, consider the disjoint union ${K=\coprod_nK_n}$. This comes with inclusion maps ${i_n\colon K_n\rightarrow K}$ which are one-to-one and ${i_m(x)\not=i_n(y)}$ for ${m\not=n}$. Let ${\mathcal K}$ be the collection of subsets of K of the form ${i_n(L)}$ for ${n\in{\mathbb N}}$ and ${L\in\mathcal K_n}$.

It can be seen that this definition of ${\mathcal K}$ also gives a compact paving. Consider a collection of sets ${C_k=i_{n_k}(L_k)\in\mathcal K}$ as ${k}$ runs through some index set I. If ${n_j\not=n_k}$ for some j and k, then ${C_j\cap C_k=\emptyset}$ giving a finite subcollection with empty intersection. On the other hand, if ${n_k=n}$ for some fixed n and all k then

$\displaystyle \bigcap_k C_k=i_n\left(\bigcap_k L_k\right).$

For this to be empty, the intersection of the ${L_k}$ must be empty so, by compactness of ${\mathcal K_n}$, ${\bigcap_{k\in J}L_k=\emptyset}$ for a finite subset ${J\subseteq I}$. So, ${\mathcal K}$ is compact.

Now, the sets ${S_n\in(\mathcal E\times\mathcal K_n)_{\sigma\delta}}$ can, by definition, be expressed as ${\bigcap_mS_{nm}}$ for ${S_{nm}}$ in ${(\mathcal E\times\mathcal K_n)_{\sigma}}$. Letting ${j_n\colon X\times K_n\rightarrow X\times K}$ be the inclusion maps ${j_n(x,y)=(x,i_n(y))}$, then ${j_n(Z)\in\mathcal E\times\mathcal K}$ for all ${Z\in\mathcal E\times\mathcal K_n}$. As ${j_n}$ is one-to-one, it follows that ${j_n(S_{nm})}$ is in ${(\mathcal E\times\mathcal K)_{\sigma}}$.

The union of the sets ${A_n=\pi_X(S_n)}$ can be written as,

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} \displaystyle\bigcup_{n=1}^\infty A_n&\displaystyle=\bigcup_{n=1}^\infty\pi_X(j_n(S_n))=\pi_X\left(\bigcup_n j_n(S_n)\right)\smallskip\\ &\displaystyle=\pi_X\left(\bigcup_n\bigcap_m j_n(S_{nm})\right)\smallskip\\ &\displaystyle=\pi_X\left(\bigcap_m\bigcup_n j_n(S_{nm})\right) \end{array}$

The final two equalities here hold because ${j_n}$ is one-to-one and the images of ${j_{n_1}}$ and ${j_{n_2}}$ are disjoint for ${n_1\not=n_2}$. This expresses ${\bigcup_nA_n}$ as the projection of a set in ${(\mathcal E\times\mathcal K)_{\sigma\delta}}$, so is ${\mathcal E}$-analytic ⬜

Suppose, for example, that X is a metric space and ${\mathcal E}$ consist of either the collection of open sets or the collection of closed sets. The following consequence of theorem 3 then implies that Borel sets are ${\mathcal E}$-analytic.

Corollary 4 Let ${(X,\mathcal{E})}$ be a paved space such that ${X\setminus E\in\mathcal E_\sigma}$ for all ${E\in\mathcal{E}}$.

Then, all ${\mathcal{E}}$-measurable sets are ${\mathcal{E}}$-analytic. That is,

$\displaystyle \sigma(\mathcal{E})\subseteq\mathcal{A}(\mathcal{E}).$

Proof: As we know from theorem 3 that ${\mathcal{ A(E)}}$ is closed under countable intersections and unions, this is a standard argument. Consider the collection ${\mathcal B}$ of sets ${B\in\mathcal{A(E)}}$ such that ${X\setminus B}$ is in ${\mathcal{A(E)}}$. From the condition that the complement of every ${B\in \mathcal E}$ is in ${\mathcal E_\sigma\subseteq\mathcal {A(E)}}$, we have ${\mathcal E\subseteq\mathcal B}$. Given any sequence ${B_n\in\mathcal B}$, the union will be in ${\mathcal{A(E)}}$ by theorem 3, with complement,

$\displaystyle X\setminus\bigcup_nB_n=\bigcap_n(X\setminus B_n)$

which is again in ${\mathcal{A(E)}}$ by theorem 3. Therefore, ${\mathcal B}$ is closed under countable unions and under complements, so is a sigma-algebra containing ${\mathcal E}$. ⬜

The map ${\mathcal E\mapsto\mathcal{A(E)}}$ on the pavings of a set X is a closure operator.

$\displaystyle \setlength\arraycolsep{2pt} \begin{array}{rl} &\displaystyle\mathcal E\subseteq\mathcal{A(E)},\smallskip\\ &\displaystyle\mathcal E\subseteq\mathcal F\Rightarrow\mathcal{A(E)}\subseteq\mathcal{A(F)},\smallskip\\ &\displaystyle\mathcal{A(A(E))}=\mathcal{A(E)}. \end{array}$

The first two statements are immediate from the definition. For the third statement, we start with the following simple lemma.

Lemma 5 For any two paved spaces ${(X,\mathcal E)}$ and ${(Y,\mathcal F)}$ we have

$\displaystyle \mathcal E\times\mathcal{A(F)}\subseteq\mathcal{A(E\times F)}$

Proof: If ${A\in\mathcal E}$ and ${B\in\mathcal{A(F)}}$ then ${B=\pi_Y(S)}$ for a compact paved space ${(K,\mathcal K)}$ and ${S\in(\mathcal{F\times K})_{\sigma\delta}}$. It follows that ${A\times S\in(\mathcal{E\times F\times K})_{\sigma\delta}}$ and ${A\times B=\pi_{X\times Y}(A\times S)}$ is ${\mathcal{E\times F}}$-analytic. ⬜

Finally, we show that ${\mathcal A(\cdot)}$ is a closure operator.

Theorem 6 Let ${(X,\mathcal{E})}$ be a paving. Then, a set ${A\subseteq X}$ is ${\mathcal{A}(\mathcal{E})}$-analytic if and only if it is ${\mathcal{E}}$-analytic. That is,

$\displaystyle \mathcal{A}(\mathcal{A}(\mathcal{E}))=\mathcal{A}(\mathcal{E}).$

Proof: The inclusion ${\mathcal{A(E)}\subseteq\mathcal{A(A(E))}}$ is immediate from the definition of analytic sets, or from (2). For the reverse inclusion, suppose that ${A\in\mathcal{A(A(E))}}$. Then, ${A=\pi_X(S)}$ for some compact paved space ${(K,\mathcal K)}$ and ${S\in(\mathcal{A(E)}\times\mathcal K)_{\sigma\delta}}$. From lemma 5, ${S\in\mathcal A(\mathcal{E\times K)}_{\sigma\delta}}$ so, by theorem 3, ${S\in\mathcal A(\mathcal{E\times K)}}$. Finally, theorem 2 says that ${A\in\mathcal{A(E)}}$ as required. ⬜