- #1

- 29

- 0

## 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.