Is there such a thing as a countable set with an uncountable subset? Is there such a thing as a countable set with an uncountable subset?


Actually I know the answer. Well, I believe I know the answer, which is NO.
Unfortunately, the professor in a Theory of Computation class said that yes, there is such a subset.

This is to settle a discussion with fellow students. A discussion that is going nowhere so we go to the internets for a verdict.

Thanks in advance for weighing in on this question.
Of course it is easy to see that any subset of a countable set is countable. While enumerating the larger set, just skip over any elements that are not in the subset, and you have an enumeration of the subset. 

Nevertheless, since you mentioned you were in a computability theory course, there are a few computability-like senses in which something like a positive answer to the question is possible.


Every infinite computably enumerable set has numerous subsets that are not computably enumerable. This is simply because every infinite set has uncountably many subsets, and most of these will not be computably enumerable, since there are only countably many c.e. sets. But from a computability perspective, computably enumerable is often the right analogue of countable, since those are the sets with a computable enumeration function, and so this is a very reasonable sense in which the claim is nearly true.
There can be c.e. sets whose complement is infinite, but contains no infinite c.e. subset. Thus, you can enumerate the set $S$, and infinitely many numbers are not in $S$, but there is no computable way to enumerate an infinite set of numbers not in $S$. These are known as the simple sets, and were studied from the time of Post.
Without AC, it is consistent that you can have a set $A$ with an equivalence relation $\sim$ on it, such that the number of equivalence classes of $\sim$ on $A$ is strictly larger than the cardinality of $A$. For example, we can make an equivalence relation $\sim$ having exactly $\mathbb{R}+\omega_1$ many equivalence classes, by saying that two reals are equivalent iff they are equal, or else they both code relations on $\omega$ that are well-orders of the same length. But under the Axiom of Determinacy, there is no $\omega_1$-sequence of distinct real numbers, and so this cardinality is strictly larger than $\mathbb{R}$.
Consider a set which contains a countable collection of uncountable sets.  

One example would be the set whose $m^{th}$ member (even though they are not ordered) is the set of real numbers between $m$ and $m+1$.

Then I can say that such a set has a countable subset, and that each of these subsets contains an uncountable number of elements.

However, I could not say that such a set contains an uncountable subset of a countable subset of real numbers, merely that it contains a countable subset of (uncountable) sets.