Proving a Bijection between (0,1) and P(N)

[podboy6]

My proofs professor gave us this problem as a challenge, but I'm stuck, which is why I'm here:

Let A,B sets
Define set A to be (0,1)
Define set B to be P(N), where N is the set of natural numbers, and P(N) is its power set.

Question: Construct a bijection between (0,1) and P(N) or a related set.

So I need to show that \exists f:A \rightarrow B, a bijection

Now, I know that both (0,1) and P(N) are both uncountably infinite.

The first thought that came to me was to use the Shroeder-Bernstein theorem and prove that set A is 1:1 with set B and vice verse, which would make it onto as well.

But, I guess, what I'm failing to grasp, is how an uncountably infinite set can be 1:1 with another uncountably infinite set, and vice verse, and thus be a bijective mapping?

He did also say that we could try to prove that both sets have the same cardinality, but did not elaborate. He mentioned that this was going to be difficult. I guess I'm just having difficulty starting.

 

[matt grime]

An example of the things you're struggling with, let N be the natural numbers and let N be the natural numbers, then there are injections from N to N that are not surjections, (eg x ---> 2x) in both directions, the same for the reals... replace N with R if it helps to see it for noncountable (countable is a misleading property).

The same holds even if you can't see both sets are obviously the same (cardinality)

 

[AKG]

There are three ways I can think of doing this problem:

1) Find an explicit bijection between A and B.

2) Prove |A| = |B|. There should be a theorem which allows you to conclude that there is a bijection from A to B given |A| = |B|.

3) Explicitly construct injections from A into B (and vice versa). Use the Shroeder-Bernstein Theorem to conclude that there is a bijection between the two.

Which option do you think you want to try? I don't know enough set theory to know how to do option 2. Whenever I've wanted to show two sets had the same cardinality, I did so by FIRST showing that there is a bijection between them, so I would be better off just doing option 1. So for me, I would do option 1 or option 3. Option 3 might be the easiest.

For a hint for an injection from A to B, think about the binary expansion of numbers in (0,1). Note that some numbers don't have unique expansions, for example 0.1 = 0.011111..., just like 0.3 = 0.2999... You'll have to make a simple choice about whether to express a number with a terminating decimal expansion in its terminating form or in its form that has all 1's after a certain point. Making this stipulation, there's a relatively obvious choice for the injection from A to B. The fact that you have to make this choice should tell you why you can't use the exact same idea to go backwards from B to A. But there's a very simple way to use the same idea on two separate parts of B, and just make sure that these separate parts of B go to totally separate parts of A. This might all sound vague. It's just the answer I thought of, but with all the details removed so it doesn't give you the answer. I don't know if this makes for a good hint, but do what you can with it.

 

[CarlB]

It seems, at least intuitively, that the number of pairs of binary fractions that map to the same real number, is countable. Is this the case?

Carl

 

[matt grime]

Under what map?