# Every countably infinite set has a countably infinite set

1. Mar 1, 2012

### k3k3

1. The problem statement, all variables and given/known data
Show that every infinite set contains a countably infinite set.

2. Relevant equations

3. The attempt at a solution
Let A be an infinite set

Since A is infinite and not empty, there exists an a∈A
Let f be a mapping such that for all n in ℕ such that f(n)=$a_{n}$ for some $a_{n}$.

Then f(1)=$a_{1}$. A is an infinite set, so there exists another element $a_{2}$ that is not $a_{1}$ such that f(2)=$a_{2}$ and so on.

This makes f a 1-1 function.

Since every element of ℕhas an image, the subset generated by f is onto ℕ.

Therefore, since f creates a subset of A, infinite subsets have a countable subset.

--
Is this a valid proof on why infinite sets have a countably infinite subset?

2. Mar 1, 2012

### Dick

Yes, it is. I would rephrases some of the sentences, but in spirit it's correct.