# Sigma algebra question from Williams' book

I'm trying to study measure theory on my own from David Williams' Probability with Martingales.

While motivating the need for measure theory, he poses the following exercise: Let $\mathcal{C}$ be the class of subsets of $\mathbb{N}$ for which the "density" $$\lim\limits_{m\rightarrow \infty} \frac{\#\{k:1\leq k\leq m; k \in \mathcal{C}\}}{m}$$ exists. We might like to think of this density (if it exists) as "the probability that a number chosen at random belongs to $\mathcal{C}$". But there are many reasons why this does not conform to proper probability theory. For example, find elements $F$ and $G$ in $\mathcal{C}$ such that $F \cap G \notin \mathcal{C}$.

I would appreciate if somebody could help me find such $F$ and $G$. I'm unable to come up with an example on my own.

• Which subsets not in C do you know?
– Did
Nov 11, 2013 at 9:19
• I can't think of any. Any set that has multiples of a number don't count. I don't think prime numbers, perfect squares, cubes etc. count because their density goes to 0. Nov 11, 2013 at 16:42

Some ideas to get you started (I will add a full solution later if needed):

The fraction

$$K_m = \frac{\#\{k:1\leq k\leq m; k \in K\}}{m}$$

lies between $0$ and $1$, so that the only way the limit $\lim_{m\to\infty} K_m$ can fail to exist is if $0 \le \liminf_{m\to\infty} K_m < \limsup_{m\to\infty} K_m \le 1$, and perhaps the simplest way of arranging for this is to look for sequences where we have blocks of increasing length of included integers followed by blocks of missing integers.

For example:

$$F = \bigcup_{k=0}^\infty \, \{ 2^{2k}+1, \dots , 2^{2k+1}\} = \{2, \,\,\,\,5,\dots,8, \,\,\,\,17,\dots,32, \,\,\,\,\dots\}$$

Can you prove that for this sequence $F$, the liminf will be 1/3 and the limsup will be 2/3, so that this sequence is definitely not in $\mathcal{C}$?

[Edit:

I have realised that this could be done more simply by shifting my definition of $F$ by $1$, and noting that $F$ would then consist of integers whose binary representations have an odd number of digits.]

Intuitively, what we do to construct $F$ is: include 2, exclude the next 2 integers, include the next 4 integers, exclude the next 8 integers, etc. so that if you calculate the fraction $F_m$ just after a block of included integers, you get a fraction close to 2/3, but if you calculate $F_m$ just after an excluded block integers, you get a fraction close to 1/3.

This sequence $F$ will eventually be the intersection of two other sequences (which do belong to $\mathcal{C}$), thereby giving you the required example.

Next we construct two more sequences, $H, K$ as follows:

For $H$, you take the sequence consisting of all the integers which are even AND are in $F$, and to construct $K$ you take all the odd integers which are NOT in $F$.

Unfortunately, $H$ and $K$ are still not in $\mathcal{C}$, but we are nearly there ...

Let $E$ be the sequence consisting of all even integers, This easily seen to be in $\mathcal{C}$ and has "density" 1/2.

Finally define the sequence $A = H \cup K$ and show that it has "density" 1/2, and is hence in $\mathcal{C}$, and then $E$ and $A$ are (at last) the sequences we need, they are both in $\mathcal{C}$, but their intersection is not.

• Thanks! If I understand your solution right, the two sets we consider are: 1) the set of all even numbers 2) $H \cup K$ with $H$ and $K$ defined as above. This set will have density half because its size is roughly $\frac{1}{2}(|F|+|F^c|)=\frac{1}{2}|\mathbb{N}|$. Finally, their intersection is the set of all even integers in $F$, which has a size roughly half of $F$, and its density fluctuating between $\frac{1}{6}$ and $\frac{1}{3}$. Nov 11, 2013 at 21:49
• Pretty much, yes. You are absolutely right about 1) and 2), but I would be a bit more pedantic about assertions like " ... because it is roughly ... ", and would prefer to give a more precise argument - but then I am a grumpy old mathematician! I suspect I could have explained the construction a bit more clearly if I had time, but I was basically copying from some old notes. Nov 11, 2013 at 21:55