I'll list all my questions about this question/proof below.

The question that is to be proved: Let $\mathscr{F}$ be the set of all functions $\mathbb{R}\rightarrow\{0.1\}$. Show that $\vert\mathbb{R}\vert<\vert\mathscr{F}\vert$.

The proof: Let $\mathscr{F}$ be the set of all functions from $\mathbb{R}$ to {0,1}. To show $\vert\mathbb{R}\vert<\vert\mathscr{F}\vert$ it suffices to show that $\vert\mathscr{F}\vert=\vert\mathscr{P}(\mathbb{R})\vert$. Now we will define a function $f:\mathscr{F}\rightarrow\mathscr{P}(\mathbb{R})$ by: $$f(\beta)=\{x\in\mathbb{R}: \beta(x) = 1\}$$

This is injective as suppose by the definition of our function:

$$f(\beta_1)=f(\beta_2)=A$$ $$\beta_1(x)=\beta_2(x)=1\textrm{ if } x \in A$$ $$\beta_1(x)=\beta_2(x)=0\textrm{ if } x \notin A$$

Since both $\beta_1$ and $\beta_2$ take on identical values, they must be equal. Therefore $f$ is injective.

This mapping is also surjective since any subset $B\subseteq \mathbb{R}$ we may define as $\beta:\mathbb{R}\rightarrow\{0,1\}$ such that $\beta(x)=1$ if $x\in B$ $(f(\beta)= B)$. This the map $f$ is bijective.

$\therefore$ $\vert\mathbb{R}\vert<\vert\mathscr{P}(\mathbb{R})\vert=\vert\mathscr{F}\vert$

My questions:

  • How do we know that $\mathscr{F}=\mathscr{P}(\mathbb{R})$ and not $\mathscr{F}=\mathscr{P}(\mathscr{P}(\mathbb{R}))$? How do we know what level(?) of infinity we can compare this set of all functions to?
  • How would you even come up with: $f(\beta)=\{x\in\mathbb{R}: \beta(x) = 1\}$ as the bijective function for this proof?

The rest of the proof I "understand" but still don't. Like the part of the proof showing it is injective shows: $$\beta_1(x)=\beta_2(x)=1\textrm{ if } x \in A$$ $$\beta_1(x)=\beta_2(x)=0\textrm{ if } x \notin A$$ because it has to equal 0 or 1 on the RHS because that is the codomain of all the functions in $\mathscr{F}$? But something is still not clicking to make this make complete sense to me.

We only had two questions like this in our homework for my Foundations of Math Proof class with no previous exposure in class to this and I'm concerned that if I don't understand this now, it will reappear in either my Analysis I or Abstract Algebra class I am taking next semester. Is this something I am supposed to fully comprehend or more of a "you'll actually understand this way later in your studies" thing?


2 Answers 2


What you're really doing here is applying Cantor's theorem in a slightly different setting. Cantor's theorem tells you that $|\mathbb{R}|<|\mathcal{P}(\mathbb{R})|$, so if you can show that $|\mathcal{F}|=|\mathcal{P}(\mathbb{R})|$, then the result follows.

You need to show a bijection $f$ between $\mathcal{F}$ and $\mathcal{P}(\mathbb{R})$. Informally, this means you have a way to interpret subsets $B$ of $\mathbb{R}$ as functions $\mathcal{B}:\mathbb{R}\to\{0,1\}$, and vice versa. What is a subset of $\mathbb{R}$? A subset $B$ of $\mathbb{R}$ is some way of deciding which elements of $\mathbb{R}$ are in $B$. For each element of $\mathbb{R}$, you either decide that yes, it is in $B$, or no, it is not in $B$. If you replace yes and no with $1$ and $0$, that determines a function $\mathcal{B}:\mathbb{R}\to\{0,1\}$, and conversely, such a function determines a subset $B$ of $\mathbb{R}$. This correspondence between $B$, a subset of $\mathbb{R}$, and $\mathcal{B}$, a function from $\mathbb{R}$ to $\{0,1\}$, is in fact a bijection, which you can prove by showing that it is injective and surjective, or by showing that it has an inverse.

What you're really using here is the idea of the indicator function of a set. This is a natural way to interpret sets as functions, and it's why you look at $\mathcal{P}(\mathbb{R})$. If this is your first time seeing something like this, it may look strange and difficult to understand, but once you understand what's really happening here, it will feel natural.


The idea of the proof you've cited is that each function $\mathbb R \to \{0, 1\}$ describes a subset of $\mathbb R$, and vice versa. Indeed, when you're picking such a function, you need to, for each $x \in \mathbb R$, either set $f(x) = 0$ or $f(x) = 1$. Likewise, when you're picking a subset $S \subset \mathbb R$, you pick, for each $x \in \mathbb R$, either $x \in S$ or $x \notin S$.

Noticing this should be your first step in solving such a problem. Then you immediately see that the cardinality of $\mathscr F$ is $\mathscr P(\mathbb R)$. The next steps are writing it out in a level of detail you and your audience will find satisfactory.

Is this something I am supposed to fully comprehend or more of a "you'll actually understand this way later in your studies" thing?

I would consider this to be quite a simple problem. You are supposed to fully comprehend this.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .