Can we use Cantor's theorem to figure this out?

Intuitively the domain seems to be a subset of the codomain, but where do powersets come in?

Thanks in advance!


marked as duplicate by Asaf Karagila elementary-set-theory Aug 19 '18 at 22:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Once you know the connection between indicator functions and subsets, this is a duplicate of these, and probably a handful of others. $\endgroup$ – Asaf Karagila Aug 19 '18 at 22:44

Hint: Call $A$ the first set and $B$ the second set. There is a natural (and quite famous) bijection between $B$ and $\mathcal P(\Bbb N)$. On the other hand, the map \begin{align}G:A&\to \Bbb N\\ G(x)&=\sum_{i=0}^\infty 2^ix(i)\end{align} is a bijection.

  • $\begingroup$ Can you specify the famous bijection or tell how to Google it? Thanks! $\endgroup$ – alwaysiamcaesar Aug 19 '18 at 21:37
  • 1
    $\begingroup$ Me not telling it was a deliberate act. $\endgroup$ – Saucy O'Path Aug 19 '18 at 21:50
  • $\begingroup$ I don't see how I can learn without being given the tools to at least look up the problem. I don't have nearly enough training in math, and this is part of an introductory course to upper division mathematics which uses no textbook. So, I, literally, don't know where to go from here. If I were an expert in the subject I wouldn't be asking a question here. But I do appreciate your answer, it helped me get there halfway. $\endgroup$ – alwaysiamcaesar Aug 19 '18 at 21:59
  • $\begingroup$ @alwaysiamcaesar You may want to keep in mind what the programming language C++ does: logical predicates are actually bult-in functions that return $0$ when they mean "false" and $1$ when they mean "true"... $\endgroup$ – Saucy O'Path Aug 19 '18 at 23:42
  • $\begingroup$ I gave a +1 to this answer because it is very clever. With that being said, usually life is not so simple. It is important to know how you can figure out the cardinality without finding a concrete bijection with a set of known cardinality. Bernstein's equivalence theorem is a very useful tool, for example. In this particular case, the first set is countable, because you can easily break it down to a countable collection of sets, all of which are at most countable. Just check the cardinality of the set of sequences with a given finite number of 1 digits. But anyway, really nice argument. $\endgroup$ – A. Pongrácz Aug 20 '18 at 8:06

The first set is naturally isomorphic to the set of all finite subsets of $\mathbb N$; whereas the second set is $P(\mathbb N)$ (in each case consider the subset $S$ such that $i\in S$ precisely when $x(i)=1$)...

It is well known that $\mid P(\mathbb N)\mid= \mathfrak c$, the cardinality of the continuum.

The first set on the other hand has cardinality less than or equal to what you get if you consider only rational real numbers. This is because irrationals have infinite nonrepeating decimals. (Think of the binary representation of the reals.) This set is countable.

Perhaps have a look at this question of mine...

  • $\begingroup$ You're right. I'll try to fix it. $\endgroup$ – Chris Custer Aug 19 '18 at 22:14

Show that the first set is countable, and the second set has cardinality continuum.


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