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.

-

4 Answers

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

-

2
I agree with the computable enumerable statement completely. I think what happened was that the prof used "countable" instead of "computably enumerable." I agree that there are infinitely many subsets, but each subset is still countable. The subset may not be computably enumerable. If in the subject you replace "countable" with "computably enumerable" then I agree! :) – starflyer Jan 27 '11 at 5:24

2
Wait, so when you say it's "nearly true", you mean it's true if we think of countable as computably enumerable. But strictly speaking, they are not equivalent. – starflyer Jan 27 '11 at 6:08

12
Good on you to figure out a reasonable interpretation of the question. – Ross Millikan Jan 27 '11 at 7:45

4
@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. – Raphael Jan 27 '11 at 8:38

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.

-
typo in the second word, I think... – Arturo Magidin Jan 27 '11 at 5:11
Thank you for the answer. It's pretty much the proof I gave. I know it's pretty simple. As for your side note, so without AC, there exist infinite sets without a countable subset. So this means that there still exists infinite sets with countable subsets. How is this possible? Thanks in advance. – starflyer Jan 27 '11 at 5:13
@Arturo: thanks, iPhones are nice but typos are not uncommon when writing from them. :-) – Asaf Karagila Jan 27 '11 at 5:15

1
@starflyer: You have it slightly off: if we don't assume AC, then the statement "every infinite set has a countable subset" is undecidable (assuming ZF consistent); so there are models of set theory without AC in which this is a false statement, meaning that there are at least some infinite subsets (in that model) without countable subsets. But there will also be infinite subsets with countable subsets (e.g., every infinite ordinal contains $\omega$ as a subset). So in ZF without AC you can add the axiom "there exists at least one set $S$ that is infinite and has no countable subset." – Arturo Magidin Jan 27 '11 at 5:19
@Arturo, thanks for the answer. Definitely food for thought. – starflyer Jan 27 '11 at 13:42

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.

-

As I mentioned earlier, I suspected this to be the case. But the prof was adamant about the statement, even after defining "countable". – starflyer Jan 30 '11 at 6:18

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.

-
Like you said, that is different from the original statement. The uncountable subset is not a subset of the original set but an element of the set. So strictly speaking is not a subset. – starflyer Jan 27 '11 at 13:06

2
This is irrelevant. – Qiaochu Yuan Jan 27 '11 at 15:47
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9504237771034241, "perplexity_flag": "head"}