2
$\begingroup$

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

  • 8
    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.2011-12-14
  • 5
    Sorry, 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
  • 0
    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.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 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.