Prove this representation of naturals is a bijection

[honestrosewater]

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?

 

[Dick]

It may obvious each set only represents one number. But to show it's injective, you need to give an argument showing that two subsets can't correspond to the same number. I don't know how saying it's a 'complete' function (whatever that is) proves it. Then you want to show it's surjective.

 

[honestrosewater]

It may obvious each set only represents one number. But to show it's injective, you need to give an argument showing that two subsets can't correspond to the same number.

I might be mistaken, but to me, this would show it's injective in the other direction, from P(N) to N. Injection in the original direction means that two different numbers don't get mapped to the same set, which is just saying that a set only sums to a single number. Of course, if the inverse is an injection, I have a bijection, but that is the next part.

I don't know how saying it's a 'complete' function (whatever that is) proves it. Then you want to show it's surjective.

By "complete", I mean defined on the whole domain (as opposed to a partial function). The surjective part is what I am not sure about. For it, I need to show that every set gets used, which should be true if every number has at most one representation under this scheme. Then, given some set, you would know that it gets used because it represents some number in the domain and is the only set that represents that number (which must get mapped to some set since the function is complete).

I'm not immediately sure how to attack the question of the uniqueness of the representation, but it seems that it might not even be necessary since s is given as a function, which means every member of the domain gets mapped to only one member of the codomain. The definition says nothing about choosing among alternate sets. The value of s at n is defined to be the set such that [...]. Do you see what I mean? The question is really whether s is indeed a function. But it's given as such, so... isn't my work done?

 

[Samuelb88]

To show s is surjective, Suppose for every X={k_1, k_2, ..., k_m} in Powerset(setN), prove there exists a natural i such that X=s(i). Start by supposing X={k_1, k_2, ..., k_m} and by the definition of s, we can construct such i and therefore prove s is surjective.

So s is obviously an injection since each set only represents one number. I'm not sure what else exactly I need to show.

Be careful. Can you assert this without proof? Obvious is a dangerous word to use in proofs. To show s is injective. Suppose for every natural i,j, s(i) = s(j) and prove i=j. Start by supposing *s(i) = {l_1, l_2, ...,l_p}=s(j) and use the definition of s to construct such naturals i and j. To me, from * it seems pretty apparent that i=j and therefore we have proven s is injective.

Edit: Sorry if I am misunderstanding the definition of your function... but given your definition of s, how can we possible define a bijection from setN to Powerset(setN)? If I am understanding this correctly, s(1) = {0}, s(2) = {1}, s(3)={0,1}, s(4)={2}, and so on... Well, for which natural number, say q, does the image of q equal the set of all natural numbers? That is, symbolically: s(q) = setN ?

 

[Dick]

I might be mistaken, but to me, this would show it's injective in the other direction, from P(N) to N. Injection in the original direction means that two different numbers don't get mapped to the same set, which is just saying that a set only sums to a single number. Of course, if the inverse is an injection, I have a bijection, but that is the next part.

This just shows that it is a well defined function from a countable subset (the finite sets) of P(N) to N. Whether it is injective or surjective have yet to be shown. Here's a hint. The sum of the numbers 2^k from k=0 to k=n-1 is equal (2^n)-1. That's less than 2^n.

 

[honestrosewater]

Yes, the problem statement is a little confusing since the codomain is defined to be the powerset of N, and I only want a bijection between N and the finite subsets of N. There of course is no bijection between any infinite set and its powerset.

Apparently, we can't agree on what injections and surjections are. A function f : D -> C is an injection iff, for all x and y in D, x != y implies f(x) != f(y), and f is surjective iff its range equals C. Agreed or not?

In this case, this means that two different numbers in N never get mapped to the same set in P(N), or equivalently, applying the function described by s backwards to a single set -- which just involves adding -- doesn't result in two different sums, which is just saying that addition is an operation, as I'm sure the TA knows.

Two different sets being able to sum to the same number would mean that some member of the domain could be mapped to more than one member of the codomain, which, if that happened, would violate the uniqueness requirement that s must satisfy in order to be a function, as it's defined to be.

I might want to know for its own sake why there is exactly one such sum for each number, but the proof doesn't seem necessary for this problem. The problem has presumably already granted that s is a function and so there is (i) at least one such sum for each number since s must be defined on the whole domain and (ii) at most one such sum for each number because s must satisfy uniqueness. Unless we're not supposed to assume that s is function, it seems like an easy problem.

 

[Dick]

Let me restate the question in the way that I understand it. If I'm wrong correct me. Let F(N) be the set of finite subsets of N. Define a map s:F(N)->N by s({x1...xn})=2^x1+...+2^xn. This is clearly a well defined function. It's not clearly injective or surjective by any sort of technicalities involving function definition that I can think of. I think there is something to prove here. If you try and define it as you originally did as a function s:N->P(N) it's not even clear it's well defined. If you indeed ASSUME that it is a well defined function, that might help you proving some things. But assuming it's well defined doesn't seem very fair until you give an algorithm for finding the set corresponding to an integer n. There is one. It's the binary representation of integers.

 

[honestrosewater]

Dick,

As you say, it's obvious that s's inverse exists (assuming s : N -> F(N) is a function), but a function has an inverse iff it is bijective, right? So there is what seems to me a silly technical way that they are both bijections. I think the professor is looking for the binary representation algorithm, but it seemed strange that the work seemed to be just showing that s was a function, so I thought I might have been mistaken. But I do just need to show that it's a function.

Thanks.

 

[Dick]

Yes, if a function has an inverse it's bijective, sure. I'm just saying giving a less than clear description of the inverse function by doing some special cases doesn't prove it has an inverse. It does, but it has to be proved. I think you get the point now.

 

[honestrosewater]

Who's trying to prove it has an inverse by giving special cases?

I just realized I was wrong originally. I was assuming, without realizing it, that the domain and codomain were the same size, i.e., that there were no "extra" sets floating around in the codomain. It's not enough that there is exactly one representation for each number. This would be true also for s from a finite domain to an infinite one, where clearly no bijection exists. Right?

So to show that s is surjective, it's not enough to show that there is at most one representation for each number. If there's exactly one and the sets are the same size, then it works. But could I prove it without needing to know their size beforehand?

 

[Samuelb88]

Apparently, we can't agree on what injections and surjections are. A function f : D -> C is an injection iff, for all x and y in D, x != y implies f(x) != f(y), and f is surjective iff its range equals C. Agreed or not?

I agree with your definition. But contrapositively,, a function f: D -> C is injective if and only for all x,y in D, f(x)=f(y) implies x=y. Moreover. to say the functions range is equal to its codomain is the same as saying for every, say b in C, we can find, say an a in D such that b=f(a).

I think if you follow my hints in my previous proof, you'll find it quite easy to prove s is both injective and surjective.

 

[Dick]

Who's trying to prove it has an inverse by giving special cases?

I just realized I was wrong originally. I was assuming, without realizing it, that the domain and codomain were the same size, i.e., that there were no "extra" sets floating around in the codomain. It's not enough that there is exactly one representation for each number. This would be true also for s from a finite domain to an infinite one, where clearly no bijection exists. Right?

So to show that s is surjective, it's not enough to show that there is at most one representation for each number. If there's exactly one and the sets are the same size, then it works. But could I prove it without needing to know their size beforehand?

The way you prove two sets are the same size is to show there is a bijection between them. You need to show there is exactly one set corresponding to each natural number which expresses it as the sum of powers of two.

 

[honestrosewater]

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 [itex]s : \mathbb{N} \to \mathcal{F}(\mathbb{N}),[/itex] [itex]s(n) = \{i | \exists (b_0,...,b_k) \in \{0,1\}^{k+1}[/itex][itex][n = \sum_j b_j 2^j\ \wedge \ b_i=1]\}[/itex], where [itex]\mathcal{F}(\mathbb{N})[/itex] is the set of finite subsets of [itex]\mathbb{N}[/itex], is bijective. (Note: [itex]0 \in \mathbb{N} \Leftrightarrow \emptyset \in \mathcal{F}(\mathbb{N})[/itex])

PROOF. Assuming s is indeed a function, s is injective since each set sums to at most one number (i.e., [itex]\forall n,m \in \mathbb{N}\ [s(n) = s(m) \implies n = m][/itex]). s is surjective since each set sums to at least one number in [itex]\mathbb{N}[/itex] (i.e., [itex]\forall x \in \mathcal{F}(\mathbb{N}) \exists n \in \mathbb{N}\ [x=s(n)][/itex]). 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 [itex]\mathbb{N}[/itex], [itex]f : \mathbb{N} \to T[/itex] be the function encoding the representations, and [itex]g: T \to \mathcal{F}(\mathbb{N})[/itex] 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 [itex]s^{-1} : \mathcal{F}(\mathbb{N}) \to \mathbb{N}, s^{-1}(\{x_1,\ldots,x_k\}) = \sum_j 2^{x_j}[/itex]. That s^-1 is a surjection follows by induction. [itex]s^{-1}(\emptyset) = 0[/itex], and if [itex]s^{-1}(x)=n[/itex], then there exists some [itex]y \in \mathcal{F}(\mathbb{N})[/itex] such that [itex]s^{-1}(y)=n+1[/itex]. There are two cases: (i) if [itex]0 \notin x[/itex], then [itex]y = x \cup \{0\}[/itex]; (ii) if [itex]0 \in x[/itex], 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 [itex]y = (x - \text{below-first-missing}(x)) \cup \text{first-missing}(x)[/itex]. 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 ([itex]0 \notin x[/itex]), 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.

 

[Dick]

I DEFINITELY do not like the proof that assumes s is a function. That's a big assumption that makes the proof as trivial as you say, and seems to me to miss the whole point of what you need to prove. The first 'alternatively' it seems to me assumes that the binary representation of a number exists and is unique. Which is what you need to really prove. The second 'alternatively' seems to be getting there, but I'm not sure I understand it.

Look, think of it this way. Suppose {a1,...,an} with a1<a2<...<an and {b1,...,bm} with b1<b2<...<bm represent the same number. Can you show an=bm for a start? See my hint in post 5.

 

[honestrosewater]

Ohh... I think I just got your hint. The key is the rate of change of 2ⁿ. Since 2ⁿ > [itex]\sum_{i=0}^{n-1} 2^i[/itex], you need to use the largest 2ⁿ that will work as an addend because you can't make up for skipping over it even by using all of the smaller powers. Yeah?

 

[honestrosewater]

Okay, I think I'm done. Thanks for all your help. Is this is intelligible?

That s^-1 is injective follows from the rate of change of 2ⁿ, i.e., the fact that [itex]2^n = (\sum_{i=0}^{n-1} 2^i) + 1[/itex]. Assume that s^-1(x) = s^-1(y) = k. Let 2ⁿ be the largest power of 2 less than or equal to k, so k = 2ⁿ + p for some [itex]p \in \mathbb{N}[/itex]. If n is not in x, then some combination of the remaining powers {2^n-1,...,2⁰} must sum to 2ⁿ + p. But the sum of the remaining powers is less than 2ⁿ, so this is impossible. Thus n must be in x. Any other members of x must sum to p, and the same argument applies with p as the ``new k'', or new goal. So after every inclusion, the largest remaining power less than or equal to the current goal must be included in x. This rules out any way for x and y to differ. Thus s^-1(x) = s^-1(y) implies x = y.

 

[Dick]

Okay, I think I'm done. Thanks for all your help. Is this is intelligible?

That s^-1 is injective follows from the rate of change of 2ⁿ, i.e., the fact that [itex]2^n = (\sum_{i=0}^{n-1} 2^i) + 1[/itex]. Assume that s^-1(x) = s^-1(y) = k. Let 2ⁿ be the largest power of 2 less than or equal to k, so k = 2ⁿ + p for some [itex]p \in \mathbb{N}[/itex]. If n is not in x, then some combination of the remaining powers {2^n-1,...,2⁰} must sum to 2ⁿ + p. But the sum of the remaining powers is less than 2ⁿ, so this is impossible. Thus n must be in x. Any other members of x must sum to p, and the same argument applies with p as the ``new k'', or new goal. So after every inclusion, the largest remaining power less than or equal to the current goal must be included in x. This rules out any way for x and y to differ. Thus s^-1(x) = s^-1(y) implies x = y.

That looks good to me. What you have there is an algorithm for finding the set given a number k. It shows there is a unique way to associate a set with k. Isn't that a lot more satisfying a proof than assuming s is a function?