# Is every subset of $\{0,1\}^*$ countable?

The set of all subsets of $\{0,1\}^*$ is not countably infinite, but does this mean that every subset is countable?

-
Since $\{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. –  Arturo Magidin Dec 14 '11 at 20:26
Sorry, but what is $\{0,1\}^*$? –  David Mitra Dec 14 '11 at 20:29
@David: The set of all finite strings over the alphabet $\{0,1\}$, that is $\bigcup_{k=0}^\infty \{0,1\}^k$. –  Alexander Thumm Dec 14 '11 at 20:38
@DavidMitra, also known as the Kleene closure. –  sxd Dec 15 '11 at 3:25
I 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. –  Ross Millikan Dec 15 '11 at 4:59

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.