Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.