Showing an infinitely countable set is contained within every uncountable set I'm new to elementary set theory and have this question I am faced with.
"Does every uncountable set have an infinitely countable proper subset?"
My answer for this is yes because by definition the cardinality of an uncountable set is greater than that of the set of natural numbers and therefore we can find a proper subset that is equivalent to the set of natural numbers.
Is my understanding of this correct?
 A: This is true but not quite as trivial as it sounds. Prima facie we could imagine some sort of exotic set that is infinite, and has no bijection with $\mathbb{N}$ (the standard reference set for countability), and yet all of its countable subsets are finite. In fact no such set exists under the usual axioms of set theory, but I believe it requires the axiom of choice, or at least countable choice, to prove this.
A: If uncountable is defined as "infinite and not countable", then you need to argue a bit more. You need to use the fact that every two sets can be compared in their cardinality (which is equivalent to the axiom of choice); or at least the fact that every infinite set has a countably infinite subset (which follows from the axiom of countable choice).
Without assuming countable choice, though, it is consistent that there is a set which is not finite (there is no natural number $n$ which is the cardinality of our set), but still has no subset which is countably infinite. And in that case, the statement is false as given.
If uncountable is defined as "strictly larger than the cardinality of the natural numbers", then you are correct, even without assuming the axiom of choice. (Some people might choose to define uncountable like that, and then make the distinction between "uncountable" and "non-countable", although this seems like an odd choice of terminology to me.)
