Binary expansion and bijection

Question

Using the idea of binary expansion ($1011$ is $1\cdot2^0 + 1\cdot2^1+0\cdot2^2+1\cdot2^3 = 11$) to find a bijection that

(a) maps $\mathbb{N}$ to the set of all finite subsets of $\mathbb{N}$

(b) maps the set of all finite subsets of $\mathbb{N}$ to $\mathbb{N}$

For (a) I am looking at a table of the first $30$ $\mathbb{N}$ and trying to figure out how I can map that into {{1},{2},{3}...{n},{1,1},{1,2},{1,3}...{1,n} and so on}, but I am drawing a complete blank. Any suggestions would be greatly appreciated!

Answer 1

For any natural number $n$ written in base 2, you can construct the finite subset of $\mathbb N$ $f(n)$ such that

• $\forall p\in \mathbb N$, $p \in f(n)$ if and only if the $p$th number of $n$ is $1$.

For example, if $n=13$, ie $n=1101$ in binary, then $f(n)$ is the set $\{0,2,3\}$ (the $0$th digit of $n$ is 1, so we take 0, the $1$st digit of $n$ is 0, so we don't take 1, the $2$nd digit is 1, so we take 2, and the $3$rd digit is $1$, so we take 3)

Using the same idea, you can define a map from finite subsets of $\mathbb N$ to $\mathbb N$, and show they are each other inverses.