Dick said:
The way you prove two sets are the same size is to show there is a bijection between them.
Yes, which is why I would rather not start out assuming a bijection exists in order to prove that this particular function is one.
I started my solution a few ways making different assumptions. I haven't gotten to proving injection without using facts about the binary representation.
PROBLEM. Show that s : \mathbb{N} \to \mathcal{F}(\mathbb{N}), s(n) = \{i | \exists (b_0,...,b_k) \in \{0,1\}^{k+1}[n = \sum_j b_j 2^j\ \wedge \ b_i=1]\}, where \mathcal{F}(\mathbb{N}) is the set of finite subsets of \mathbb{N}, is bijective. (Note: 0 \in \mathbb{N} \Leftrightarrow \emptyset \in \mathcal{F}(\mathbb{N}))
PROOF. Assuming
s is indeed a function,
s is injective since each set sums to at most one number (i.e., \forall n,m \in \mathbb{N}\ [s(n) = s(m) \implies n = m]).
s is surjective since each set sums to at least one number in \mathbb{N} (i.e., \forall x \in \mathcal{F}(\mathbb{N}) \exists n \in \mathbb{N}\ [x=s(n)]). In other words,
s-1 is a function, so both are bijective.
Alternatively, note that the members of
s(n) correspond to the positions of
1s in the base-two representation of
n, with 0 corresponding to the last/ones position. Let
T be the set of base-two representations of members of \mathbb{N}, f : \mathbb{N} \to T be the function encoding the representations, and g: T \to \mathcal{F}(\mathbb{N}) be the function that collects the positions of the
1s of a representation into a set. Then
f and
g are both bijections, and
s is the composition of
g with
f, thus
s is also a bijection.
Alternatively, let s^{-1} : \mathcal{F}(\mathbb{N}) \to \mathbb{N}, s^{-1}(\{x_1,\ldots,x_k\}) = \sum_j 2^{x_j}. That
s-1 is a surjection follows by induction. s^{-1}(\emptyset) = 0, and if s^{-1}(x)=n, then there exists some y \in \mathcal{F}(\mathbb{N}) such that s^{-1}(y)=n+1. There are two cases: (i) if 0 \notin x, then y = x \cup \{0\}; (ii) if 0 \in x, then if first-missing(
x) is the smallest number not in
x and below-first-missing(
x) is the set of numbers less than first-missing(
x), then y = (x - \text{below-first-missing}(x)) \cup \text{first-missing}(x). The mechanics for this working can be seen by considering the noted correspondence with
T. If the base-two representation of
n ends in
0 (0 \notin x), then adding 1 will change the last digit to
1 and leave the other digits unchanged. If the representation of
n ends in
1, then the added 1 will carry until it reaches the first position containing
0, changing it to
1 and all positions passed over to
0. (This dependence on the correspondence with
T is merely expository, as is singling out the first case, which is just a special case of the second.)
That
s-1 is injective... not sure. I was thinking of trying induction and breaking it into cases of odd and even. If
n is even, and
x is the unique set mapped to
n, then
x U {0} is clearly (by properties of odds and evens wrt addition and multiplication) the only way to get a set for
n+1, which is unique by hypothesis. The even case is not as obvious to me, but I was thinking of a reductio argument as I was falling alseep last night. But it seems troublesomely complicated to start a contradiction when already in the second case of an induction.
