I was trying to prove that $P \left( \mathbb{N} \right)$ is bijective with the interval $\left[ 0, 1 \right)$. I wish to employ Schoder-Berstein theorem which states that if there there are two one-to-one functions between two sets, then those sets are bijective.

To obtain the first one-to-one function, I formed $f: P \left( \mathbb{N} \right) \rightarrow \left[ 0, 1 \right)$ as

$$f \left( S \right) = \begin{cases} 0, & S = \emptyset \\ 0.a_1a_2a_3\cdots, & S \neq \emptyset \end{cases}$$

where $a_n = \begin{cases} 1, & n \in S \\ 0, & n \notin S \end{cases}$.

Clearly, this is a one-to-one function, as commented upon in Bijection from $\mathcal{P}(\mathbb{N})$ to $(0,1)$.

However, I find it difficult to create the other one-to-one function. I tried to form $g: \left[ 0, 1 \right) \rightarrow P \left( \mathbb{N} \right)$ as

$$g \left( x \right) = \begin{cases} \emptyset, & x = 0 \\ \left\lbrace a_1, a_2, \cdots \right\rbrace, & x = 0.a_1a_2\cdots \end{cases}$$

However, clearly, this is not one-to-one since $0.1$ and $0.11$ are mapped to the same set $\left\lbrace 1 \right\rbrace$. Also, it is not well-defined since $0.01$ is not mapped anywhere.

Any hints for constructing this one-to-one function will be appreciated.

Note: I would like to use the decimal expansion only for the construction, and not base-two expansion.


Consider the base-two expansion of $x\in [0,1)$: $$x=0.b_1b_2\cdots=\sum_{n=1}^\infty b_n2^{-n}$$ with each $b_n\in\{0,1\}$. Consider the set $\{n\in\Bbb N:b_n=1\}$.


An injective map $g: \left[ 0, 1 \right) \rightarrow P \left( \mathbb{N} \right)$ is $$g(x)=\{p_n^{\lfloor 10^n x \rfloor}: n\in\mathbb{N}\}$$ where $p_n$ is the $n$-th prime number and with the restriction that we forbid decimal representations with a trailing infinite sequence of $9$s.

  • $\begingroup$ Consider $x = 0.0999999\cdots = 0.1$. Then, $g \left( x \right) = \left\lbrace 2 \right\rbrace$ by considering the decimal expansion $0.1$. On the other hand, if we consider the other decimal expansion, we will have $g \left( x \right) = \left\lbrace 1, 3^9, 5^{99}, 7^{999}, \cdots \right\rbrace$, which are clearly two different sets. So, $g$ is not well-defined. $\endgroup$ – Aniruddha Deshmukh Oct 28 '19 at 5:13
  • 1
    $\begingroup$ @AniruddhaDeshmukh Please se my edit. Conventionally, the decimal representation without trailing 9's is preferred. See en.wikipedia.org/wiki/… $\endgroup$ – Robert Z Oct 28 '19 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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