I think you mean “I think you mean all finite subsets of natural numbers” ;)
The power set of the natural numbers is the union of the finite subsets of the natural numbers and the infinite subsets of the natural numbers. The former is in bijective correspondence with N.* So if the infinite subset were in bijective correspondence with N, then N would be in bijective correspondence with its powerset. But this is not the case by Cantor’s theorem, so there cannot be a bijection between N and its infinite subsets.
*Using: {}->[empty sum]+1=1 {1}->2^(1-1)+1=2 {2}->2^(2-1)+1=3 {1,2}->2^(1-1)+2^(2-1)+1=1+2+1=4 {2,3,5,7}->2^(2-1)+2^(3-1)+2^(5-1)+2^(7-1)+1=2+4+16+64+1 etc.
Ah, I was taking So8res to be talking about how, for any infinite subset of the natural numbers, there are bijections between that set and the natural numbers, but your interpretation (bijections between the natural numbers and the set of finite subsets of the natural numbers) makes much more sense. Retracted; thanks.
I think you mean “I think you mean all finite subsets of natural numbers” ;)
The power set of the natural numbers is the union of the finite subsets of the natural numbers and the infinite subsets of the natural numbers. The former is in bijective correspondence with N.* So if the infinite subset were in bijective correspondence with N, then N would be in bijective correspondence with its powerset. But this is not the case by Cantor’s theorem, so there cannot be a bijection between N and its infinite subsets.
*Using:
{}->[empty sum]+1=1
{1}->2^(1-1)+1=2
{2}->2^(2-1)+1=3
{1,2}->2^(1-1)+2^(2-1)+1=1+2+1=4
{2,3,5,7}->2^(2-1)+2^(3-1)+2^(5-1)+2^(7-1)+1=2+4+16+64+1 etc.
Also mentioned at http://lesswrong.com/lw/j8/the_crackpot_offer/
Ah, I was taking So8res to be talking about how, for any infinite subset of the natural numbers, there are bijections between that set and the natural numbers, but your interpretation (bijections between the natural numbers and the set of finite subsets of the natural numbers) makes much more sense. Retracted; thanks.