2
$\begingroup$

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

  • 0
    @ArturoMagidin Why not post your first comment as answer?2011-12-15

1 Answers 1

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.