# Show that $\sigma(\mathcal{H})$ is equal to $\mathcal{P}(\mathbb{N})$.

Let $\mathbb{N} = \{1,2,3,4,\dots \}$ and define the sets $A_k \subset \mathbb{N}$ by $$A_k = \{k,2k,3k,\dots \}$$ for $k = 1,2,\dots$. We denote by $\mathcal{H}$ the collection $\{A_1, A_2, \dots \} \cup \emptyset$.

Show that $\sigma(\mathcal{H})$ (the sigma-algebra generated by $\mathcal{H}$) is equal to $\mathcal{P}(\mathbb{N})$ (the power set of $\mathbb{N}$).

We know that $A_i^c \in \sigma(\mathcal{P})$ and finite intersections are again in the sigma-algebra. I tried to construct singletons out of these operations because if they are in $\sigma(\mathcal{H})$ then could construct the powerset by taking unions (I think) but I couldn't do it. I also found out that $A_i \cap A_j = A_{lcm(i,j)} \in \mathcal{H}$. So that $\mathcal{H}$ is stable under finite intersections. But now I'm stuck.

• Hint: Can you show the singleton $\{47\}$ is in $\sigma(\mathcal H)$? Commented Feb 7, 2016 at 14:05
• Is it true because $47$ is a prime number the set $\{47 \}$ is only in $A_1$ and $A_{47}$. So that for example with $2$, because it is prime as well, we can construct $\{2 \} = A_2 \cap (\cup_{3}^{\infty} A_i)$? Commented Feb 7, 2016 at 14:17
• Next, how about $\{k\}$ for composite $k$? Commented Feb 7, 2016 at 14:20
• I think we can extend this technique to composite numbers as well. $\{6\}\in A_6 = A_2 \cap A_3$. But isn't it true that $\{6\} = A_6 \cap (\cup_{i=7}^{\infty} A_i)$. If that's true we constructed the singletons and we're done! Commented Feb 7, 2016 at 14:37
• Perhaps you want $\{6\} = A_6 \setminus (\cup_{i=7}^{\infty} A_i)$. Commented Feb 7, 2016 at 14:41

We can construct the singletons as follows: $$\{i\} = A_i \backslash \cup_{t = i+1}^{\infty}A_t, \quad \forall i \in \mathbb{N}.$$ Now that we know $\sigma(\mathcal{H})$ contains all the singletons and therefore we know that this sigma-algebra is equal to the powerset of $\mathbb{N}$, because we can construct it by taking unions of singletons.