Past exam of the mathematics course of the University of Cambridge / 2018 / ia / Paper 4 / 8E (Numbers and Sets)

A set is countable if it is finite or bijects with a subset of $\mathbb{N}$. For any $f:X\to \mathcal{P}(X)$, the Cantor diagonal argument set $D=\{x:x\notin f(x)\}$ differs from every $f(y)$ at $y$. Hence no such map is surjective. Binary sequences are indicator functions of subsets of $\mathbb{N}$, so $\{0,1{\}}^{\mathbb{N}}\cong \mathcal{P}(\mathbb{N})$ is uncountable.

Every member of $L$ corresponds to a unique permutation $(a_0,a_1,\dots )$ of $\mathbb{N}$, with $F_n=\{a_0,\dots ,a_{n-1}\}$. Let $p(j)$ be the position of $j$.

For $L_0$, $p(n)<n$ eventually. Choose $N$ after which this holds and then $m$ larger than all $p(0),\dots ,p(N-1)$. The $m$ positions $0,\dots ,m-1$ would contain all $m+1$ values $0,\dots ,m$, a contradiction. Thus $L_0$ is empty, hence countable.

For $L_1$, $p(n)\le n$ eventually. For every sufficiently large $m$, all values $0,\dots ,m$ occur in positions $0,\dots ,m$, so this initial segment is invariant. Comparing consecutive invariant initial segments gives $p(m)=m$ eventually. These are the finite-support permutations, of which there are countably many. Hence $L_1$ is countable.