I was given a question today which asks to find a subset of the power set of natural numbers having cardinality $2^{\aleph_0}$ and in which any two subsets have finitely many elements in their intersection.
My solution was to consider the sequences of rationals converging to a real number, for every real, and then to take the bijection of those sequences of rationals to sequences of naturals.
Can one prove this more directly? That is, show an explicit subset of the power set?
Best Answer
Let ${^\Bbb N}\{0,1\}$ be the set of infinite sequences of $0$’s and $1$’s, and let $\Sigma$ be the set of finite sequences of $0$’s and $1$’s. For each $\sigma\in{^\Bbb N}\{0,1\}$ let $$S_\sigma=\{s\in\Sigma:s\text{ is an initial segment of }\sigma\}\;;$$ it’s not hard to show that if $\sigma,\tau\in{^\Bbb N}\{0,1\}$, and $\sigma\ne\tau$, then $S_\sigma\cap S_\tau$ is finite.
Finally, $\Sigma$ is countably infinite, so it admits a bijection with $\Bbb N$. With a bit of work one can produce an explicit bijection $h:\Sigma\to\Bbb N$, and then the collection $\big\{h[S_\sigma]:\sigma\in{^\Bbb N}\{0,1\}\big\}$ has the desired properties.
Added: Here’s a pretty nice bijection $h$. If $s=\langle b_0,\dots,b_{n-1}\rangle\in\Sigma$, let $$h(s)=2^n+\sum_{k=0}^{n-1}b_k2^k\;.$$ As $s$ runs over all sequences in $\Sigma$ of length $n$, $\sum_{k=0}^{n-1}b_k2^k$ runs over all non-negative integers in $\{0,\dots,2^n-1\}$, and $h(s)$ runs over $\{2^n,\dots,2\cdot2^n-1\}=\{2^n,\dots,2^{n+1}-1\}$, so $h$ is clearly a bijection from $\Sigma$ to $\Bbb N$. Indeed, given $n\in\Bbb N$, we can calculate $h^{-1}(n)$ as follows.
First let $k=\lfloor \lg n\rfloor$, where $\lg x$ is the binary log; then $2^k\le n<2^{k+1}$. Let $m=n-2^k$; then $0\le m<2^k$, so $m$ has a unique binary representation $$m=\sum_{i=0}^{k-1}b_i2^i\;,$$ where each $b_i\in\{0,1\}$, and $h^{-1}(n)=\langle b_0,\dots,b_{k-1}\rangle$.