Paper 4, Section II, 8E

Define what it means for a set to be countable.

Show that for any set $X$, there is no surjection from $X$ onto the power set $\mathcal{P}(X)$. Deduce that the set $\{0,1\}^{\mathbb{N}}$ of all infinite $0-1$ sequences is uncountable.

Let $\mathcal{L}$ be the set of sequences $\left(F_{n}\right)_{n=0}^{\infty}$ of subsets $F_{0} \subset F_{1} \subset F_{2} \subset \ldots$ of $\mathbb{N}$ such that $\left|F_{n}\right|=n$ for all $n \in \mathbb{N}$ and $\bigcup_{n} F_{n}=\mathbb{N}$. Let $\mathcal{L}_{0}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n}$ for all but finitely many $n \in \mathbb{N}$. Let $\mathcal{L}_{1}$ consist of all members $\left(F_{n}\right)_{n=0}^{\infty}$ of $\mathcal{L}$ for which $n \in F_{n+1}$ for all but finitely many $n \in \mathbb{N}$. For each of $\mathcal{L}_{0}$ and $\mathcal{L}_{1}$ determine whether it is countable or uncountable. Justify your answers.

*Typos? Please submit corrections to this page on GitHub.*