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