# Proof that every infinite set is numerically equivalent to a proper subset of itself

• Apr 13th 2010, 01:34 PM
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,

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).
• Apr 13th 2010, 02:26 PM
Double post.
• Apr 13th 2010, 02:27 PM
Drexel28
Quote:

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,

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).

It's quite long, but from what I've read (I've read most of it) it seems at least going in a valid direction. Why make it hard on yourself though?

Prove that:

a) An infinite subset of a countable set is countable.

b) From this conclude that if $\displaystyle E$ is countable so is $\displaystyle E-\{e\}$ for any $\displaystyle e\in E$

c) For any infinite set $\displaystyle M$ one can extract an countable subset $\displaystyle K$. So, $\displaystyle M=K\cup (M-K)$ and so by previous comment $\displaystyle K\simeq K-\{k\}$ and so $\displaystyle M=K\cup (M-K)\simeq (K-\{k\})\cup (M-K)=M-\{k\}$ (hint, I wrote it like that to make the mapping obvious)

Youre done.
• Apr 13th 2010, 02:41 PM
Plato
Just one comment.
A great many of us use that very statement as the definition of an infinite set.
So what is your definition of infinite set?
Is it just a set that is not finite?
• Apr 13th 2010, 03:41 PM
Quote:

Originally Posted by Drexel28
It's quite long, but from what I've read (I've read most of it) it seems at least going in a valid direction. Why make it hard on yourself though?

Prove that:

a) An infinite subset of a countable set is countable.

b) From this conclude that if $\displaystyle E$ is countable so is $\displaystyle E-\{e\}$ for any $\displaystyle e\in E$

c) For any infinite set $\displaystyle M$ one can extract an countable subset $\displaystyle K$. So, $\displaystyle M=K\cup (M-K)$ and so by previous comment $\displaystyle K\simeq K-\{k\}$ and so $\displaystyle M=K\cup (M-K)\simeq (K-\{k\})\cup (M-K)=M-\{k\}$ (hint, I wrote it like that to make the mapping obvious)

Youre done.

Hey Drexel,

Thanks. I'm not positive, but looking at your argument, it appears to be basically the same as the second paragraph of mine. I take an infinite set and map N into it (this would be your $\displaystyle K$, and my B). Then I remove every other element of B (this would be your $\displaystyle K - {k}$ and my C). I then show that B U (A - B) (which is A) is numerically equivalent to C U (A - B) (which is a subset of A) since we can map C U (A - B) onto B U (A - B) by mapping each element in A - B to itself, and then mapping C onto B, which we can do because C and B are both countably infinite.

So, looking again at my proof in this light, is my proof basically the same as yours (just clumsier), or is there still something that I have left out?

Quote:

Originally Posted by Plato
Just one comment.
A great many of us use that very statement as the definition of an infinite set.
So what is your definition of infinite set?
Is it just a set that is not finite?

Well, I am working through Introduction to Topology and Modern Analysis by G.F. Simmons, and looking back through the past few sections he doesn't appear to give a definition of infinitude. I suppose that "a set that is not finite" is what he implies an infinite set to be:

Quote:

Originally Posted by Introduction to Topology and Modern Analysis, page 32
In a manner of speaking, we ourselves use the infinite set N = {1, 2, 3, . . .} of all positive integers...

The ellipsis at the end of the set definition appears to mean, strictly, that the set does not have some specific number n of elements, but rather that any natural number produced by starting with 1 and successively adding 1 will be an element in N.

Perhaps Drexel can shed some light on this, since I believe that he has already worked through ITMA.

• Apr 13th 2010, 03:45 PM
Drexel28
Quote:

Hey Drexel,

Thanks. I'm not positive, but looking at your argument, it appears to be basically the same as the second paragraph of mine. I take an infinite set and map N into it (this would be your $\displaystyle K$, and my B). Then I remove every other element of B (this would be your $\displaystyle K - {k}$ and my C). I then show that B U (A - B) (which is A) is numerically equivalent to C U (A - B) (which is a subset of A) since we can map C U (A - B) onto B U (A - B) by mapping each element in A - B to itself, and then mapping C onto B, which we can do because C and B are both countably infinite.

So, looking again at my proof in this light, is my proof basically the same as yours (just clumsier), or is there still something that I have left out?

It looks fine, I was just remarking that your notation was cumbersome. Otherwise, good job!
• Apr 13th 2010, 07:01 PM