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!

Homework Help: Real Analysis: countably infinite subsets of infinite sets proof

  1. Mar 1, 2012 #1
    1. The problem statement, all variables and given/known data
    Prove that every infinite subset contains a countably infinite subset.

    2. Relevant equations

    3. The attempt at a solution

    Right now, I'm working on a proof by cases.

    Let S be an infinite subset.

    Case 1: If S is countably infinite, because the set S is a subset of itself, it contains a countably infinite subset.

    Case 2: If S is uncountably infinite....

    And this is where I'm stuck. I know it's true (the Reals contains the Integers, the power set of the Reals still contains the Integers, etc) I've done some other searching online, and I keep seeing references to the Axiom of Choice used to prove this; we haven't talked about it in class, so I'd like to avoid this if at all possible, since if I use it, I'd have to prove that too.
  2. jcsd
  3. Mar 1, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't think you can prove it without the axiom of choice, which allows you to build a set by making an infinite number of choices. You don't prove the axiom of choice. That's why it is an axiom. There are consistent models of set theory with and without it.

    If you assume the axiom of choice, the proof should be pretty straightforward. For each [itex]n \in \mathbb{N}[/itex], choose a distinct element [itex]x_n \in S[/itex], so that [itex]x_n \neq x_m[/itex] if [itex]n \neq m[/itex]. Suppose this were impossible for some [itex]n[/itex]. What would that imply about [itex]S[/itex]?
  4. Mar 1, 2012 #3
    It's puzzling that you'd be asked to prove this before you've seen the Axiom of Choice.
  5. Mar 1, 2012 #4
    I'm not exactly sure what you're asking; if it's impossible to choose an x_n for some n, doesn't that mean S is finite?

    Does this work?

    Case 2: S is uncountably infinite.

    Let n ε Z+. For each n, choose on distinct element s_n ε S. This establishes a one to one correspondence between Z+ and a subset of S. Because Z+ is countably infinite, this subset is countably infinite. Thus, S has a countably infinite subset.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook