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.