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 nonsingular 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, ..., aA) (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. 
