# Constructing injection questions

• Oct 17th 2011, 11:59 AM
wopashui
Constructing injection questions
Let $\displaystyle S_2$ = {0,1}^N, $\displaystyle S_2^*$= {$\displaystyle (a_n) \in S_2$; (there exists $\displaystyle k\in N$) s.t ($\displaystyle for all n>=k) a_n = 1$}. Recall that the function $\displaystyle f: S_2-S_2^*--> [0,1)$, given by $\displaystyle f((a_n)) = \displaystyle \sum_{n = 1}^{\infty}a_n/2^n$ is a bijection. Denote by $\displaystyle \varphi: [0,1)-->S_2-S_2^*$the inverse function $\displaystyle f^{-1}$. Note that for $\displaystyle x \in [0,1)$,
$\displaystyle \varphi (x)$ is the sequence $\displaystyle \varphi(x) = (\varphi_n(x))_{n = 1}^{\infty} $$\displaystyle \in S_2-S_2^* with \displaystyle f(\varphi(x)) = \displaystyle \sum_{n = 1}^{\infty} \varphi_n(x)/2^n = x. a) Construct an injection \displaystyle g:$$\displaystyle S_2-S_2^* --> [0,1) x [0,1)$.

b) Construct an injection $\displaystyle h: [0,1) x [0,1) --> S_2-S_2^*$. (Hint: Interlace decimals)

The question is kind of confusing with all these notations, any help will be useful.
• Oct 17th 2011, 01:52 PM
Plato
Re: Constructing injection questions
I am truly not sure what you are asking for?
Do you understand that $\displaystyle S_2$ is the set of infinite bit strings?
That $\displaystyle S_2^*$ is the set of infinite bit strings with at a finite collection of zeros?
Every number in $\displaystyle [0,1)$ has binary representation.
The set $\displaystyle S_2\setminus S_2^*$ represent the binary representation that are unique.

Does that help?
• Oct 17th 2011, 02:53 PM
wopashui
Re: Constructing injection questions
sorry, I do not understand those terms, I think this question has things to do with decimal reprsentation