- #1
honestrosewater
Gold Member
- 2,143
- 6
Homework Statement
Given
[tex]s : \mathbb{N} \to \mathcal{P}(\mathbb{N})[/tex]
[tex]s(n) = \{i | \exists (b_0,\ldots,b_k) \in \{0,1\}^{k+1} [n = \sum_j b_j2^j \,\wedge\, b_i = 1]\}[/tex]
show that s is a bijection between N and the finite subsets of N.
In other words, if you express n as the sum of powers of 2 using each power at most once, s maps n to the set of powers used in this sum: s = {(1, {0}), (2, {1}), (3, {0,1}), (4, {2}), (5, {0,2}), (6, {1,2}), (7, {0,1,2})...}.
The Attempt at a Solution
So s is obviously an injection since each set only represents one number. I'm not sure what else exactly I need to show. The work would seem to be showing that there is exactly one way to represent each number as such a sum, but that s is given as a (complete) function implies that there is at least one and at most one such representation. No? So what am I supposed to show?