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?

  • 2
    $\begingroup$ There are four proofs that you can find an almost disjoint family of size $2^{\aleph_0}$ of $\mathbb N$ in hcm.uni-bonn.de/fileadmin/geschke/papers/…, pages 2 and 3. $\endgroup$ – Ross Millikan Oct 16 '12 at 20:17
  • $\begingroup$ What is more explicit than that, by the way? You can take a very specific subset of rationals for each irrational (the continued fraction expansion) if you want to avoid seeming to use choice. (For the rational $q$, you can just use $\{q-2^{-k}\}$.) $\endgroup$ – Thomas Andrews Oct 16 '12 at 20:30
  • $\begingroup$ Well, the first idea one has is to approach it directly, whereas the way through the rationals seems a bit indirect to me. (Also, the explicit bijection between the rationals and naturals is pretty ugly) $\endgroup$ – Tanay Oct 16 '12 at 20:39

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$.


For each infinite set of integers $A\subset \omega$, associate the infinite set of integers $S_A = \{\sum_{i \in A \cap n} 2^i : n<\omega\}$. If $i \in A \setminus B$ then all but finitely many elements of $S_A$ have a "1" in the $i$-th place in their binary expansion, and no elements of $S_B$ do, so $S_A \cap S_B$ is finite. It remains to observe that the are continuum many infinite sets of integers $A \subset \omega$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.