Another bijection Log Out | Topics | Search
Moderators | Register | Edit Profile

Ask NRICH » Archive 2011-2012 » Higher Dimension » Another bijection « Previous Next »

Author Message
Weasel8778
Regular poster

Post Number: 29
Posted on Sunday, 16 October, 2011 - 02:33 pm:   

Give an example of a bijection between Domain: {A | A C N, |A| < infinity}, Codomain: N} (read 'C' as 'a subset or equal to' and 'N' as 'natural numbers not including 0').

Hard to know where to start... It seems that for every single element of the codomain N (eg 25), there is a corresponding element of the domain (eg {25}), AS WELL as all of the non-singular elements of the domain (eg {25, 1}, {25, 1, 15}) so there doesn't seem to be any way of having a bijection between them...
GCS
Veteran poster

Post Number: 795
Posted on Sunday, 16 October, 2011 - 02:46 pm:   

well, you could make do with an injection first off, and then compose it with another map to turn it into a bijection....

Geoff
lebesgue
Veteran poster

Post Number: 2400
Posted on Sunday, 16 October, 2011 - 03:43 pm:   

Let N={0,1,2,...}. Can't such a subset A of N encode the positions of ones in binary expansion of that f(A) somehow?
Weasel8778
Regular poster

Post Number: 30
Posted on Sunday, 16 October, 2011 - 03:59 pm:   

Ok, in my search for an injection for Geoff's suggestion I think I ended up finding a bijection (and a crazy one at that). I THINK this works, but I'm not sure how to write it in notation...

f(empty set) = 1, f(A) = 1 + Sum from r = 1 to |A| of 2^(ar - 1) where A is not the empty set (read 'ar' as 'a' subscript 'r')

where A = {a1, a2, a3, ..., a|A|) (the numbers next to 'a' are subscript)

So:
{} -> 1
{1} -> 2
{2} -> 3
{3} -> 5
{4} -> 9
(So between each singular set, there is a gap exactly large enough for all the other sets that have that number as its maximum element to slot in e.g.)
{1, 2} -> 4
{1, 3} -> 6
{2, 3} -> 7
{1, 2, 3} -> 8

I wonder if that post made any sense at all...
GCS
Veteran poster

Post Number: 796
Posted on Sunday, 16 October, 2011 - 08:26 pm:   

So you are really using a `binary' idea, as lebesgue suggested.

Add Your Message Here
Posting is currently disabled in this topic. Contact your discussion moderator for more information.

Topics | Last Day | Last Week | Tree View | Search | Help/Instructions | Program Credits Administration