Real Analysis: countably infinite subsets of infinite sets proof

[TeenieBopper]

Homework Statement

Prove that every infinite subset contains a countably infinite subset.

Homework Equations

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.

 

[jbunniii]

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 $n \in \mathbb{N}$, choose a distinct element $x_n \in S$, so that $x_n \neq x_m$ if $n \neq m$. Suppose this were impossible for some $n$. What would that imply about $S$?

 

[SteveL27]

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.

It's puzzling that you'd be asked to prove this before you've seen the Axiom of Choice.

 

[TeenieBopper]

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.