The set of all subsets of $\{0,1\}^*$ is not countably infinite, but does this mean that every subset is countable?
Is every subset of $\{0,1\}^*$ countable?
2
$\begingroup$
elementary-set-theory
cardinals
formal-languages
-
8Since $\{0,1\}$ is finite, $\{0,1\}^*$ is countably infinite. In particular, every subset is countable; but the set of all subsets is uncountable; however, there is no logical implication between "the set of all subsets of $X$ is not countably infinite" to "every subset of $X$ is countable", so "does this mean" is incorrect in the sentence above. – 2011-12-14
-
5Sorry, but what is $\{0,1\}^*$? – 2011-12-14
-
5@David: The set of all finite strings over the alphabet $\{0,1\}$, that is $\bigcup_{k=0}^\infty \{0,1\}^k$. – 2011-12-14
-
0@DavidMitra, also known as the Kleene closure. – 2011-12-15
-
0I would interpret "does this mean" as "imply" in which case the answer is no. As $P(\{0,1\}^*)$ is uncountable any subset that deletes a finite number of elements is also uncountable. – 2011-12-15
-
0@Ross: Ah, yet another reading that I didn't see. You are interpreting "every subset" as "every subset of the set of all subsets", whereas I interpret "every subset" as "every subset of $\{0,1\}^*$".
I hate it when that happens... – 2011-12-15 -
0@ArturoMagidin: I don't get the Billy Crystal reference. But I was interpreting "every subset" as every subset of the power set of $\{0,1\}^*$ (not the universe). As the base set is infinite, the power set is uncountable. Then a subset of the power set can also be uncountable. – 2011-12-15
-
0@Ross: [A SNL sketch](http://snltranscripts.jt.org/84/84ewillie.phtml). Yes, I understood what you meant. My point is that I interpreted it as "every subset of $\{0,1\}^*$", you interpreted as "every subset of the power set". The sentence is ambiguous, as I think both interpretations are valid given what is written... – 2011-12-15
-
0@ArturoMagidin Why not post your first comment as answer? – 2011-12-15
1 Answers
4
If $X$ is a set of a certain cardinality, Cantor's theorem guarantees that $|X|<|P(X)|$. That is the set of all subsets of $X$ is much larger.
However $A\in P(X)$ is exactly to say that $A\subseteq X$. Therefore the identity function $Id:A\to A$ can be thought as an injective function $f:A\to X$ given by $f(a)=a$.
This means that $|A|\le |X|$. In particular, if $X$ is countable, every subset is at most countable (i.e. finite or countable).
If by subset you meant subset of $P(X)$, then this is of course not true since we can take $P(X)$ itself, and if $X$ is countable then of course $P(X)$ is not.