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.