How to make an injective function $ f $ such that $ f : \left[0,1\right]\rightarrow2^\mathbb{N} $ using binary notation?

Question

$ 2^\mathbb{N} $ is a power set of $ \mathbb{N} $.

By using binary notation, we can take $ x\in\left[0,1\right]$ and $ x=0.a_1a_2a_3\cdots\left(a_n\in\left\{0,1\right\}\right) $

Then we can make a set $ A=f(x) $ as an element of $ 2^\mathbb{N} $ following next rules:

$n\in A $ when $ a_n=1 $ and $ n\notin A $ when $ a_n=0 $

For example,

$$\begin{align*} 0.00000\cdots&\longmapsto\emptyset\\[5pt] 0.10000\cdots&\longmapsto\left\{1\right\}\\[5pt] 0.01000\cdots&\longmapsto\left\{2\right\} \\[5pt] 0.01111\cdots&\longmapsto\left\{2,3,4,\cdots\right\} \\[5pt] 0.10111\cdots&\longmapsto\left\{1,3,4,5,\ \cdots\right\} \\[5pt] \end{align*}$$

This seems nice. However, since $ 0.10000\cdots=0.01111\cdots $, there exist two $ f(x) $ for same $ x$. I can't fix this problem and I've been thinking of this all night.. How can I make the injective function $ f $ with solving this?

Answer 1

First define an equivalence relation between the binary representations such that $x:=0.a_1a_2 \cdots \sim y:=0.b_1b_2 \cdots \iff x=y$. Then using the function that you defined above we have an injection from $[0,1]/ \sim \, \mapsto 2^{\mathbb{N}}$ where we choose the representative of each equivalence class as the one which has infinitely many 0s (each class will have one expansion ending in all 0s, and one expansion ending in all 1s; choose the first one).

It's important to note that there are only a countable number of binary expansions which end in infinite 1s, and each equivalence class contains at most two elements and so the cardinality of our quotient set is $\aleph$

Answer 2

Define $$ f(x)=\{\,n\in\Bbb N_0\mid \lfloor2^nx\rfloor\text{ is odd}\,\} $$ which has no ambiguity. Note that I used $\Bbb N_0=\{0,1,2,3,\ldots\}$ because I want $f(1)\ne f(0)$. Alternatively, you can work with $\lfloor 2^{n+1}x\rfloor$ or define $f(1)$ instead specifically as a set not reachable otherwise (e.g., $f(1):=\Bbb N$). At any rate, $f$ is readily shown to be injective - but is not surjective because it leaves out all co-finite subsets (except one picked for $f(1)$).

Answer 3

Here's an indirect way to produce the $1-1$ function using the hint that I dropped earlier in comment.

First we show that $P(\mathbb N)$ and $T=\{f| f:\mathbb N\to \{0,1\}\}$ are similar.
Let $A\subseteq \mathbb N$ (i.e, $A\in P(\mathbb N)$). Let's define a function $\chi_A: \mathbb N\to \{0,1\}$ such that $\chi_A(x)= 1,$ if $x\in A$ else $0$. Clearly, $\chi_A\in T$.

Define $\theta: P(\mathbb N)\to T$ by $\theta (A)=\chi_A$. Verify that $\theta$ is a bijection.

Now, every $r$ in $[0,1]$ has a binary representation which can be restricted to "unique binary representation" by choosing the one which has forever repeating $0$s at the end in case of two binary representations (the other being with forever repeating 1s at the end) for some $r$. It's an easy exercise to show that $[0,1]$ and $T$ are similar. Hence there exists a bijection $\phi:[0,1]\to T$.

Now consider the composition $\theta^{-1} o\phi:[0,1]\to P(\mathbb N) $. This is clearly $1-1$.