0
$\begingroup$

$\{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 \}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Christian Blatter Oct 20 '17 at 15:03
  • $\begingroup$ @ChristianBlatter Which is? $\endgroup$ – Tobi Oct 20 '17 at 19:10
1
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.