1

I know this proof is false, but I don't know why. I need your help.

The false proof says that it is possible to create a bijection between a subset of the rational numbers and the Power set of natural numbers.

We can create orderly the subsets of the natural numbers and create a bijection at the same time to some of the rational numbers:

First pairs:

{1,2},{1,3}.... -> 1/2, 1/3..

{2,3},{2,4}.... -> 2/3, 2/4..

now three:

{1,2,3},{1,2,4}... 12/3, 12/4...

{1,3,4},{1,3,5}....13/4, 13/5...

...

{2,3,4}, {2,3,5}...23/4, 23/5...

four...

And so on...

So this false proof says that the cardinal of the rational numbers are, al least the cardinal of P(N)

How can I explain that is false

Thanks.

Pedro
  • 379
  • 3
    Your construction does not contain infinite subsets of $\mathbb{N}$. – Raskolnikov Jan 10 '13 at 07:44
  • And indeed the set $\mathcal P_f(\mathbb N)$ of the finite subsets of $\mathbb N$ is countable. – Did Jan 10 '13 at 07:46
  • Not only have you not defined your function on any infinite subset of $\Bbb{N}$, you haven't defined it on all the finite subsets either. I at least cannot guess from your description how you indeed to deal with sets of size four, let alone larger ones. – Chris Eagle Jan 10 '13 at 07:53
  • I think that the main problem is that I don't have the infinite subsets in act...but I don't understand the rules very well. Why in the bijecction between rational and naturals we understand we have contructed all infinite numbers and in this false proof we cannot say e have constructed all even numbers or all quadratic numbers? – Pedro Jan 10 '13 at 08:00
  • @did :"the set Pf(N) of the finite subsets of N is countable" – Pedro Jan 10 '13 at 08:55
  • Thank you. Now I see the light. – Pedro Jan 10 '13 at 08:56

2 Answers2

1

Ignoring that I don't think that map is going to be injective on finite subsets of the natural numbers. Where do you send $\mathbb N$ or the set of all even numbers?

I will add that if you consider the set $\mathcal A =\{ B \subset \mathbb N : |B| < \infty\}$ that $|\mathcal A |=\mathbb Q$. You can find an injection by taking an enumeration of the primes for instance and mapping $\varphi(B)=\prod_{i \in B}p_i$.

JSchlather
  • 15,427
  • Hello Jacob. With the groups of four I have {1,3,5,7}, in the groups of five {1,3,5,7,9} and so on...I'm not havig the even subset in act as a infinite subset. – Pedro Jan 10 '13 at 07:55
  • @Pedro I don't understand your question. Where does the set ${2,4,6,8,10,\dots} \in \mathcal P(\mathbb N)$ get sent to under your mapping? – JSchlather Jan 10 '13 at 07:58
  • That's the problem. Ok, I see – Pedro Jan 10 '13 at 08:06
0

Your proof describes a function whose domain is the set of all finite subsets of the naturals and whose codomain is a subset of the rationals. If you will check carefully you will find that that function is not injective, but even if it were your question is already answered: the domain is not all of the power set of the naturals.

You can fix the injectivity problem in various ways, thus proving that the cardinality of all finite subsets of the naturals is countable.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • "Your proof describes a function whose domain is the set of all finite subsets of the naturals and whose codomain is a subset of the rationals" Ok, yes; I understand. – Pedro Jan 10 '13 at 08:08