1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing infinite sets are countable using a proper subset

  1. Mar 25, 2012 #1
    1. The problem statement, all variables and given/known data
    Show if a set is infinite, then it can be put in a 1-1 correspondence with one of its proper subsets.


    2. Relevant equations
    This was included with the problem, but I am sure most already know this.

    A is a proper subset of B if A is a subset of B and A≠B


    3. The attempt at a solution
    Did I do this correctly? Here is my work:


    Showing the forward implication first:

    Show if a set is infinite, then it can be put in a 1-1 correspondence with one of its proper subsets.


    Let A be an infinite set.
    Let B be an infinite set that is a proper subset of A.

    Since A is infinite, there exists a bijective mapping f:X→A, where X is either the set of natural numbers or real numbers depending if the sets are countable or not, be defined by f(x_n)=a_n where x_n is in X and a_n is in A.

    Similarly for B, there exists a bijective mapping g:X→B be defined by g(x_n)=b_n where x_n is in X and b_n is in B.

    Since g is a bijection, its inverse exists and is a bijection.

    Let h=f([itex]g^{-1}[/itex])

    Since [itex]g^{-1}[/itex](b_n)=x_n, then f([itex]g^{-1}[/itex])=a_n

    Therefore if a set is infinite, it can be put into a 1-1 correspondence with one of its proper subsets.

    Reverse implication:

    If a set can be put into a 1-1 correspondence with one of its proper subsets, then it is infinite.

    Suppose a finite set can be put into a 1-1 correspondence with one of its proper subsets.

    Let A={a,b,c,d}
    Let B={c,d}

    Let f:B→A
    Where f(c)=a and f(d)=b

    It is a 1-1 function, but not onto.

    Therefore, if a a set can be put into a 1-1 correspondence with one of its proper subsets, it must be infinite.
     
  2. jcsd
  3. Mar 25, 2012 #2
    What's your definition of an infinite set? Reason I ask is that the property you're trying to prove is very often taken as the definition of an infinite set. So if you're using some other definition, it will be helpful to state it.
     
  4. Mar 25, 2012 #3
    The book defines an infinite set as:

    Let A be an arbitrary set.
    The set A is finite if it is empty or if its elements can be put in a 1-1 correspondence with the natural numbers.

    The set A is infinite if it is not finite.

    I included the finite definition too since the infinite definition is not very descriptive.
     
  5. Mar 25, 2012 #4
    How can a finite set be put into 1-1 correspondence with the natural numbers? Are you sure you wrote that down correctly?
     
  6. Mar 25, 2012 #5
    Sorry, with a finite subset of natural nunbers I meant to write. That was not typed properly.
     
  7. Mar 25, 2012 #6
    Well, what's a finite subset? Isn't that the word we're trying to define?

    Don't mean to be picking at you with details ... but the overall steps here are going to involve

    1) Nailing down the definition of "infinite set."

    2) USING that definition to prove what's required.

    So we're stuck on step 1 here.
     
  8. Mar 25, 2012 #7
    If it is finite, it can be put into a 1-1 correspondence with the set {1,2,3,...,n} for some positive integer n
     
  9. Mar 25, 2012 #8
    Ok!

    Now, can you redo your proof, using that definition?
     
  10. Mar 25, 2012 #9
    Is this supposed to be a contradiction proof? If I am showing that a set is infinite if one of its proper subsets are infinite, then there cannot be a 1-1 correspondence from either of the sets to any set {1,2,3,...n} for some positive integer n.
     
  11. Mar 25, 2012 #10
    Helpful to go directly back to what's required by the problem. You started out " If I am showing that a set is infinite if one of its proper subsets are infinite ..." which is a little confusing.

    By the way, what class is this for? The fact that these two definitions are equivalent is non-trivial and involves some set-theoretical subtleties. However you're only being asked here to prove one direction, so perhaps that's more straightforward.
     
  12. Mar 25, 2012 #11
    It's for a real analysis class. It is a if and only if problem, but I found the forward implication to be difficult. I should have paid attention to what I was typing instead of just transcribing everything I wrote on my paper and not include the reverse.

    Here is the question verbatim from the book: Prove that a set is infinite if and only if it can be put into a 1-1 correspondence with one of its proper subsets. (A set A is a proper subset of B if A[itex]\subseteq[/itex]B and A≠B)
     
  13. Mar 25, 2012 #12
    I don't have time to work this out at the moment ... but here's a link showing why this is a harder problem than it looks. The link doesn't have a proof or even a hint, just some interesting context for the question.

    http://en.wikipedia.org/wiki/Dedekind-infinite_set

    Try posting what you've got so far and perhaps others can jump in.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook