Bijection from $\{0,1\}^k \rightarrow P(\{1, …, k\})$

$\{0,1\}^k \rightarrow P(\{1, ..., k\})$

I need this bijection.

I can see both sets have a cardinality of $2^k$, I also noticed that you can perform a (computer) AND-like operation using the bit string, $\{0,1\}^k$, as a mask, to get all the possible combinations of subsets, making for a bijection between the set of all bit-strings of length $k$, and the power set of positive integers up to $k$.

What I tried doing is this:

$$I(k) = \{ x \in \mathbb{N}^1 : x \le k \} \\ b(x) = \{\ I(|x|)_i : i \in \mathbb{N}, i < |x|, x_i = 1\}$$

I'm new to all of this notation, constructive criticism is appreciated - also, should the set-index, $i$, start at $0$ or $1$?

Does the combination of the functions $I$ and $b$ result in the bijection I desire? How can it be improved / simplified?

I realised that the index $i$, within the $b$ function, is essentially the set returned by the function $I$, so have resorted to this:

$$b(x) = \{ i \in \mathbb{N}_1 : i \le |x|, x_i = 1 \}$$

• This is much simpler than you think. "What I tried $\ldots$" is much to farfetched. The $2^k$ bitstrings encode the $2^k$ subsets of $[k]$ in the most obvious way. – Christian Blatter Oct 20 '17 at 15:03
• @ChristianBlatter Which is? – Tobi Oct 20 '17 at 19:10

Hint: The simplest way to obtain a bijection between $\{0,1\}^k$ and $P(1,2,...,k)$ is to map $$(x_1,...,x_k) \mapsto \{i : x_i = 1\}.$$

I'll leave the rest to you (i.e to prove that this is a bijection).

Hope this helps - feel free to ask for clarification.

• Does my solution work? I dont understand what's going on in yours. – Tobi Oct 20 '17 at 14:13

View a sequence of zeros and ones from $\{0,1\}^k$ as a function $f:\{0,..,k\}\to\{0,1\}$. Then your bijection $\phi$ can be given via the preimage:

$$\{0,1\}^k\ni f\quad\mapsto\quad f^{-1}(1)\in\mathcal P(\{1,...,k\}).$$

Its inverse $\phi^{-1}$ can be given as

$$\mathcal P(\{1,...,k\})\ni X\quad\mapsto\quad f(i)=\begin{cases} 0&\text{for i\not\in X} \\ 1&\text{for i\in X}\end{cases}.$$

you can see $\{0,1\}^k$ as strings of length $k$ having $0's\ and \ 1's$

So to define a bijection from this set of strings to power set of $\{1,2,...k\}$ think of a mapping like this:

1) in the string of $0,1$ let 1 denote that you are choosing that index number in your set. for example for $k = 3\ \{001\} \ means \ \{3\}$ ie only choosing 3 (which is index of 1) as the element in set.

Observe that this mapping is one one as every string corresponds to unique element of $P\{1,2,...k\}$.

Also as you know that their cardinality is same we can say that it is a bijection