Proof that every infinite set is numerically equivalent to a proper subset of itself
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 natural number 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).
