Originally Posted by

**Poophead** Is the following a valid proof? I'm virtually certain that the first part is correct, and the second part seems valid, but I'm not quite sure that it is. If there's a flaw somewhere, can someone give me a hint as to how to fix it? If the entire approach is wrong, can someone point me in the right direction?

Thanks,

Poophead

The proof:

Let A be an infinite set. If A is countable, then order the elements of A arbitrarily and remove every other element, starting with the first. Call the diminished set B. A can be put into a one-to-one correspondence with **N**, so attempt to create such a correspondence from B to **N**. The element corresponding to 1 is missing, but the element corresponding to 2 is present; the element corresponding to 3 is missing, but the element corresponding to 4 is present; and so on. So B can be put into a one-to-one correspondence with **E**: {x in **N**: x is even}. But **E** can itself be put into a one-to-one correspondence with **N**, so B can be put into the one-to-one correspondence with **N** *fg*, where *g* maps B onto **E** and *f* maps **E** onto **N**. But then B, which is clearly a proper subset of A, is countably infinite, and since all countably infinite sets are numerically equivalent, A is numerically equivalent to B.

So suppose that A is uncountable. Since A is infinite, we can create a one-to-one mapping of **N** into A by simply pairing each integer with some arbitrary unique element of A. But since A is uncountable, this mapping will not be onto. So there is a subset B of A which is countably infinite, namely the image of **N** in A. Let D = A - B, and let C be the subset of B defined by removing every other element. As was shown above, B and C are numerically equivalent. Also, D is obviously numerically equivalent to itself. Now, the union of D and C is numerically equivalent to the union of D and B, since we can map D onto itself via the identity mapping, and we know that we can map C onto B since each is countably infinite, and this gives us a piecewise-defined mapping of the union of D and C onto the union of D and B. But the union of D and C is a proper subset of the union of D and B, since every element of D is in D and every element of C is in B, but B contains elements which are not in C (since C is B with every other element removed).