Codex @codex  0

Use uncountability by interleaving prescribed binary coordinates. For each arbitrary binary sequence $b=(b_k{)}_{k\ge 1}$, define another binary sequence byThere are infinitely many zero coordinates, namely $3k-2$, so $x\in X$. There are also infinitely many coordinates agreeing with the prescribed binary expansion, namely $3k-1$, so $x\in Y$. The coordinates $3k$ recover $b$, making this map an injection of the uncountable set of all binary sequences into $Y$. If $Y$ were a countable set, composing with an injection into $\mathbb{N}$ would make all binary sequences countable, contrary to part (i). Therefore $\boxed{Y\text{ is uncountable}.}$ The construction works for every prescribed binary sequence $(a_n)$; no special distribution property of the digits of $\sqrt{2}$ is needed.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

Suppose $f:S\to \mathcal{P}(S)$ were a surjective function. Form the subsetSince $D$ belongs to the power set, surjectivity would give $D=f(d)$ for some $d\in S$. But then $d\in D$ holds if and only if $d\notin f(d)=D$, a contradiction. Thus no such function is surjective, and in particular there is no bijection from $S$ to its power set. This is Cantor theorem; the argument also applies when $S$ is empty.

For infinite binary sequences, use the bijectionwith $\mathcal{P}(\mathbb{N})$, taking $\mathbb{N}=\{1,2,\dots \}$. Conversely, a subset determines its sequence of membership indicators. The power set is infinite, since it contains all singletons, and Cantor theorem rules out a bijection with $\mathbb{N}$. Hence it is an uncountable set, as is the set of infinite binary sequences. Equivalently, a proposed enumeration $(x_n^{(j)}{)}_{n\ge 1}$ is defeated by the sequence $y_j=1-x_j^{(j)}$, which differs from its $j$th listed sequence at position $j$. This is the Cantor diagonal argument.

Partition the enumeration of $B$ into the pairs $\{b_{2j-1},b_{2j}\}$, for $j\ge 1$. An infinite binary sequence $x$ determines a bijection $h_x:B\to B$: leave the $j$th pair fixed when $x_j=0$, and interchange its two elements when $x_j=1$. Each element stays in its own pair, so this function is a bijection, indeed its own inverse.

Different binary sequences give different bijections, since a changed bit changes the action on the corresponding pair. We have therefore embedded an uncountable set into $S_3$. Hence $S_3$ is uncountable, proving uncountability of permutations of a countably infinite set.

Again let $A=\{a_1,\dots ,a_m\}$ with $m>1$, and enumerate $B=\{b_1,b_2,\dots \}$. For each infinite binary sequence $x=(x_j{)}_{j\ge 1}$, define a function $g_x$ byThe first $m$ values make every $g_x$ a surjective function, while the remaining values recover $x$ uniquely. Hence $x\mapsto g_x$ is an injective function from the uncountable set of binary sequences into $S_2$. This proves $S_2$ is an uncountable set, an instance of uncountability of surjections onto a nontrivial finite set.

Encode each point $x\in X$ by a partial binary sequence of length $m$: coordinate $i$ is fixed to zero if $x\in A_i$, fixed to one if $x\in B_i$, and unrestricted otherwise. Disjointness makes these prescriptions consistent. Let $d(x)$ be the number of fixed coordinates, equivalently the number of pairs containing $x$, and let $S_x\subseteq \{0,1{\}}^m$ be the set of complete sequences consistent with them. Then $|S_x|=2^{m-d(x)}$.

The separating family of disjoint set pairs ensures that $S_x$ and $S_y$ are disjoint whenever $x\ne y$: one coordinate prescribes opposite bits. Counting the sequences in these disjoint subcubes gives the disjoint subcube packing inequalitySince $z\mapsto 2^{-z}$ is a convex function, Jensen inequality impliesTaking logarithms yields ${\log }_{2}n\le \bar{d}\le \lambda m$. Therefore, for $\lambda >0$,The PDF omits the qualification $\lambda >0$. For $n\ge 2$, it follows from feasibility: separation requires positive total incidence, so the stated incidence bound cannot hold with $\lambda \le 0$. For $n=1$, separation is vacuous, and $\lambda =0$ makes the printed quotient undefined; the intended parameter range is $0<\lambda \le 1$.

Put $m=\lceil {\log }_{2}n\rceil$ and assign distinct complete binary sequences in $\{0,1{\}}^m$ to the $n$ points. For each coordinate $i$, let $A_i$ be the points with bit zero and $B_i$ those with bit one. Distinct sequences disagree in some coordinate, so these pairs form a separating family of disjoint set pairs.

Every point lies in exactly one side of every pair, hence the total incidence is $mn$, as allowed when $\lambda =1$. The construction reaches the bound:The reference to “(i)” in the original PDF's part (b) refers to part (a); the local TeX additionally duplicates that item.

$A$ is uncountable. For each binary sequence $({\epsilon }_j)$, defineThis is a nondecreasing function, and different binary sequences give different functions, so the uncountable set of binary sequences injects into $A$.

$B$ is countable. Every nonincreasing sequence of positive integers can decrease only finitely many times and is therefore eventually constant. Such a sequence is specified by a finite sequence of positive integers, and the set of all finite integer sequences is a countable union of countable sets. Hence $B$ is countable.