## Puzzle corner: Solution to Sylvy’s puzzle #4

Cross-reference to puzzle page on my website

In this post I want to discuss the solution to Puzzle #4. Let’s recall the puzzle: it was to find an uncountable chain in $(\mathcal{P}(\mathbb{N}),\subseteq)$.

#### Solution

First we note that $\mathbb{N}$ and $\mathbb{Q}$ have the same cardinality, i.e. $\aleph_{0}$. There are several well-known bijections that are often used to show this, but as I was writing this post I was reminded that none of the bijections that I’m familiar with are explicit in the sense of being given by some sort of `formula’. Here is a stackexchange discussion of this point (in particular, see the answer by Thomas Andrews).

Anyway, for the sake of this puzzle, we just need some bijection $f:\mathbb{N}\longrightarrow\mathbb{Q}$.

Now, for each $r\in\mathbb{R}$, let $A_{r}:=f^{-1}(\mathbb{Q}\cap(-\infty,r])$ be the preimage (under $f$) of the set of rational numbers in the interval $(-\infty,r]$.

Proposition $\{A_{r}\;|\;r\in\mathbb{R}\}$ is an uncountable chain

This doesn’t need too much proof. Let $r be real numbers. If $n\in\mathbb{N}$ is such that $f(n)\leq r$ then also $f(n)\leq s$. Thus $A_{r}\subseteq A_{s}$.

Furthermore, there exists a rational number $q$ such that $r [why?]. Therefore $q\in (-\infty,s]\setminus(-\infty,r]$, and so $f^{-1}(q)\in A_{s}\setminus A_{r}$. This shows that $A_{r}\subset A_{s}$, as required.