Prove that every infinite subset contains a countably infinite subset.
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.