Why is this proof false?

Question

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.

Answer 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$.

Answer 2

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.