A $\sigma$-algebra on $\Omega=\{0,1\}^{\Bbb N}$ strictly smaller than $2^{\Omega}$ Let $\Omega=\{0,1\}^{\Bbb N}$ and $X_n:\Omega\to\{0,1\}$ be the projection onto $n^{\text{th}}$ coordinate, i.e. $X_n(\omega)=\omega_n$ for $\omega=(\omega_1,\omega_2,\dots)$. Consider the $\sigma$-algebra $\mathcal A:=\sigma\left(\{X_n:n\in\Bbb N\}\right)$ generated by $X_n$'s. How do we show that $\mathcal A\ne 2^{\Omega}$? 
One way I could think of is to find a $\sigma$-algebra $\mathcal B$ containing all sets of the form $\{\omega\in\Omega:\omega_n=0\}$ and that $\mathcal B$ is strictly smaller than $2^{\Omega}$. For now I couldn't find such $\mathcal B$ yet. The other way is to write down $\mathcal A$ constructively but that seems even harder.
PS: I learned of this statement from a crash course in probability, where a $\sigma$-algebra is thought of as some kind of information available to us, $X_n$ representing the outcome of the $n^{\text{th}}$ coin toss. If that is the case, then doesn't the $\sigma$-algebra $\mathcal A$ contain all possible events since we know the outcome of every toss? Could someone explain why this naive reasoning is incorrect?
 A: The sets in $\mathcal{A}$ are the Borel sets in $\{0,1\}^{\Bbb N}$.
There are $2^{\aleph_0}$ Borel sets, but $\{0,1\}^{\Bbb N}$.
has $2^{2^{\aleph_0}}$ subsets.
A: Another way to see this is to identify (a subset of) $(\Omega,\mathcal A)$ with $([0,1),\mathcal B)$, where $\mathcal B$ is the Borel $\sigma$-algebra. Since we know there are non-Borel measurable sets, this shows there are sets in $2^\Omega\setminus\mathcal A$. In fact, it even gives you explicit examples.
Let $\overline\Omega:=\big\{\omega\in\Omega:\{n:\omega_n=0\}\text{ is infinite} \big\}$. It is easy to show that $\overline\Omega\in\mathcal A$. (Hint: show $\Omega\setminus\overline\Omega\in\mathcal A$ by using the fact that $\{A\subseteq\mathbb N:A\text{ is finite}\}$ is countable.) Thus, it suffices to show that $\overline{\mathcal{A}}\neq2^{\overline\Omega}$, where $\overline{\mathcal A}:=\{A\in\mathcal A:A\subseteq\overline\Omega\}$ is the inherited $\sigma$-algebra. Define $F:\overline\Omega\to[0,1)$ by
$$F(\omega)=\sum_{n=1}^\infty2^{-n}\omega_n.$$
Clearly $F$ is measurable. It is also a bijection. Indeed, $F^{-1}(x)=(f_n(x))_{n\in\mathbb N}$, where
\begin{align*}
f_1&:=\mathbf1_{[\frac12,1)},\\
f_2&:=\mathbf1_{[\frac14,\frac12)\cup[\frac34,1)},\\
f_3&:=\mathbf1_{[\frac18,\frac14)\cup[\frac38,\frac12)\cup[\frac58,\frac34)\cup[\frac78,1)}\\
\vdots&
\end{align*}
etc. (If you are having trouble understanding where $F$ is coming from, observe that $F^{-1}$ is simply the expression of $x\in[0,1)$ as an infinite binary decimal. Using $\overline\Omega$ rather than $\Omega$ guarantees the uniqueness of the expansion, since $0.0101111111\ldots=0.0110000000\ldots$ in binary, for example.) Since each $f_n$ is measurable, $F^{-1}$ is measurable. In particular, this implies $F$ maps measurable sets to measurable sets: if $A\in\overline{\mathcal A}$, then $F(A)=(F^{-1})^{-1}(A)$ is measurable since $F^{-1}$ is a measurable function.
Now simply let $A$ be your favorite non-Borel-measurable subset of the unit interval - for instance, the Vitali set - and let $B:=F^{-1}(A)$. If $B$ were measurable, then $A=F(B)$ would be measurable, which is not true. This completes the proof.
