16
$\begingroup$

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.

4 Answers 4

39

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}$.

  • 5
    @starflyer Yes. I would advise you to not even to start thinking of ever using the terms synonymously. That would only get you in trouble.2011-01-27
8

A set is countably infinite if there is an injective function from it to the natural numbers.

Suppose $A$ is countable and $f\colon A \to \omega$ is an injection witnessing that, then if $B\subseteq A$ the restriction of $f$ to $B$ is an injective function from $B$ to the natural numbers, therefore $B$ is countable.

A side note is that without the axiom of choice there are infinite sets without a countable subset. That's a whole other deal though.

  • 0
    @Arturo, tha$n$ks for the answer. Definitely food for thought.2011-01-27
2

If your course was a TCS-Course, then maybe your professor mixed up countable sets with enumerable sets. (This happens sometimes, especially in german language areas, where it is "abzählbar" vs. "aufzählbar).

Every subset of a countable set is countable or finite (or empty). However, not every subset of an enumerable set is enumerable.

For example, $\mathbb{N}$ is trivially enumerable. But the codomain of the busy bever function, which is a subset of $\mathbb{N}$, is not.

  • 0
    As I mentioned earlier, I suspected this to be the case. But the prof was adamant about the statement, even after defining "countable".2011-01-30
-2

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.

  • 3
    This is irrelevant.2011-01-27