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<s 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<q<s [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.

Advertisement

Please leave a reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s