Results 1 to 9 of 9

Math Help - Proof that every infinite set is numerically equivalent to a proper subset of itself

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    20

    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).
    Last edited by Poophead; April 13th 2010 at 02:27 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2010
    Posts
    20
    Double post.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Poophead View Post
    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).
    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 E is countable so is E-\{e\} for any e\in E

    c) For any infinite set M one can extract an countable subset K. So, M=K\cup (M-K) and so by previous comment K\simeq K-\{k\} and so 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,680
    Thanks
    1618
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    20
    Quote Originally Posted by Drexel28 View Post
    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 E is countable so is E-\{e\} for any e\in E

    c) For any infinite set M one can extract an countable subset K. So, M=K\cup (M-K) and so by previous comment K\simeq K-\{k\} and so 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 K, and my B). Then I remove every other element of B (this would be your 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.

    Poophead
    Last edited by Poophead; April 13th 2010 at 03:52 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Poophead View Post
    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 K, and my B). Then I remove every other element of B (this would be your 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?

    Poophead
    It looks fine, I was just remarking that your notation was cumbersome. Otherwise, good job!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    20
    Thanks. I'll keep an eye on my notation. Hopefully it will naturally improve as I become more mathematically mature.

    Poophead
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    [QUOTE=Poophead;493334... more mathematically mature.

    Poophead[/QUOTE]

    Maybe you'll change your name then too
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2010
    Posts
    20
    You mean like...Dr. Poophead?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. If no proper subset of X is dense..
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 10th 2011, 06:03 AM
  2. Replies: 2
    Last Post: October 4th 2010, 03:53 PM
  3. Numerically Equivalent Sets
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: May 12th 2010, 04:58 PM
  4. Replies: 4
    Last Post: June 3rd 2009, 10:15 PM
  5. Prove: every set with an infinite subset is infinite
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2009, 04:22 PM

Search Tags


/mathhelpforum @mathhelpforum