The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

injection from decimal number to power set of natural numbers

Hi. I came across this proof for a bijection between the real numbers and power set of the natural numbers.
However I didnt quite understand the reasoning for the injection from the power set of natural numbers to [0,1]

Let us now take care of the one-to-one function g between P(N) and [0,1]. Take a set I∈P(N). I is a set of natural numbers say I={1,20,56,109,...}. We construct a number d in decimal of the form d=0.1011101110111.. where the ith position after the fixed point has a 1 if i∈I and a 0 otherwise. We can verify in class that this gives a one-to-one mapping from P(N) to reals R.

In particular I didn't understand why they said "where the ith position after the fixed point has a 1 if i∈I and a 0 otherwise" - because if thats the case, then it should read d=0.111111111111111... because all elements of i belong to I ?
Original post by Person1001
Hi. I came across this proof for a bijection between the real numbers and power set of the natural numbers.
However I didnt quite understand the reasoning for the injection from the power set of natural numbers to [0,1]

Let us now take care of the one-to-one function g between P(N) and [0,1]. Take a set I∈P(N). I is a set of natural numbers say I={1,20,56,109,...}. We construct a number d in decimal of the form d=0.1011101110111.. where the ith position after the fixed point has a 1 if i∈I and a 0 otherwise. We can verify in class that this gives a one-to-one mapping from P(N) to reals R.

In particular I didn't understand why they said "where the ith position after the fixed point has a 1 if i∈I and a 0 otherwise" - because if thats the case, then it should read d=0.111111111111111... because all elements of i belong to I ?


I is an element of the power set of natural numbers. As such it is a set in its own right consisting of a subset of the natural numbers, finite or otherwise.

If I={1,4,6}

then d= 0.100101 where there is a 1 in the 1st, 4th and 6th place.

Presumably this is a binary representation.
Reply 2
Avatar for Person1001
Person1001
OP
12
Original post by ghostwalker
I is an element of the power set of natural numbers. As such it is a set in its own right consisting of a subset of the natural numbers, finite or otherwise.

If I={1,4,6}

then d= 0.100101 where there is a 1 in the 1st, 4th and 6th place.

Presumably this is a binary representation.


Oh I see thank you very much :smile:
Original post by Person1001
Oh I see thank you very much :smile:


PS: You should note that this is not a 1-1 function, from what you've posted.

It suffers from the problem that 0.1=0.01˙0.1 = 0.0\dot{1}. I.e. any "decimal" expansion (again I assume this is binary) where the places are eventually all zero, can also be represented by another string where all the places are eventually all one.

So, there is a 1-1 correspondence between the power set and the decimal expansions, but some numbers in [0,1] have more than one decimal expansion.
Reply 4
Avatar for DFranklin
DFranklin
18
Yes - this does NOT give an injection.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you