Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let A be the set of all sequences of real numbers of size $n$. Does there exist an injection from A to R?

I know this is possible if we are only considering integers instead of real numbers; But I am not sure if it is possible if we consider real numbers instead.

For integers, we can generate a unique integer using the following method: Let S be a sequence of integers of size n. $S = s_1,s_2,\ldots,s_n$. Let $P = p_1,p_2,\ldots,p_n$ be the sequence of $n$ primes. Then $f(S) = (p_1^{s_1})(p_2^{s_2})\cdots(p_n^{s_n})$ creates a unique integer for each sequence $S$.

If each $s_i$ was a real number instead, would $f(S)$ still be an injection? If not, is there an alternative invective function from A to R?

edit:
I fixed some of my poor wording.

I am trying to find an injection function from A to R. Such a function does exist and the function I proposed clearly does not work (From the comments).

If possible, I would like to find an injective function that does not involve directly manipulating the decimal expansions.

share|improve this question
1  
(i) Your wording is bad; "Would $f(S)$ create a unique number?" is not what you want to ask (it would, because the expression is defined and is a real number); what you really want to ask is whether the resulting function $f$ is one-to-one (i.e., if different sequences yield different real numbers). (ii) Such an injection necessarily exists by simple set-theoretic arguments, since the set $A$ and the set $\mathbb{R}$ have the same cardinality; you can even find a bijection! So perhaps you are asking for a special kind of function, perhaps an explicit or constructive embedding? Say so –  Arturo Magidin Feb 6 '12 at 17:22
3  
Think about $(.a_1a_2a_3,\ldots,.b_1b_2b_3,\ldots )\rightarrow .a_1b_1a_2b_2\ldots$ –  David Mitra Feb 6 '12 at 17:22
3  
Your $f$ does not permit unique recovery of an ordered pair. Take $n=2$, $p_1=2$, $p_2=3$. We are asking, if $2^x3^y=2^u3^v$, do we have $x=u$, $y=v$? No, let $x=0$, $u=1$. Can we solve $3^y=2\cdot 3^v$? Sure. For a moderately explicit function that does the job, interleave the decimal expansions of $x$ and $y$. There are some technical difficulties, because the decimal expansion is not unique, $1=0.999\dots$. The difficulties can be resolved, but it is easier to interleave continued fraction expansions. The method goes back to Cantor. –  André Nicolas Feb 6 '12 at 17:24
1  
Ah,classical analysis. So beautiful,so intuitive-yet so frustrating sometimes to make precise. –  Mathemagician1234 Feb 6 '12 at 19:37

2 Answers 2

up vote 2 down vote accepted

I wasn't sure whether we were considering all finite sequences of reals, or just sequences of a predetermined length, so I answered for all finite sequences. Of course, this also works for a predetermined length sequence.

Suppose we have a sequence $\{x_k\}_{k=1}^n$ of real numbers. Generate an integer based on the signs of those reals as follows: $$ \sigma(\{x_k\})=2^{n-1}-1+\sum_{k=1}^{n-1}2^{k-1}\frac{1+\rm{sign}(x_k)}{2} $$ taking $\rm{sign}(0)=1$. Interlace the digits of the absolute values of the $x_k$ (not ending in repeating $9$s) to get a unique non-negative real number $\mathscr{I}(\{x_k\})$ and map it to $[0,1)$ with $$ \phi(x)=\frac{x}{\sqrt{x^2+1}} $$ Then we get a unique real using $$ \rm{sign}(x_n)\left(\phi(\mathscr{I}(\{x_k\}))+\sigma(\{x_k\})\right) $$


Simpler method:

Get a unique real using the seqence of positive reals $\left\{e^{x_k}\right\}$ with $$ n+\phi\left(\mathscr{I}\left(\left\{e^{x_k}\right\}\right)\right) $$

share|improve this answer

Pick a bijection from $\mathbb{R}$ to the set of all infinite sequences of, say, non-negative integers (exercise if you don't already know that this is possible; you can build such a bijection out of continued fraction exansions). Then an element of $\mathbb{R}^n$ (the set of ordered $n$-tuples of real numbers) can be identified with an ordered $n$-tuple of infinite sequences of non-negative integers $a_{i, j}, 0 \le i \le n-1, j \in \mathbb{N}$. Now one can simply interweave these sequences to get a single infinite sequence by setting $$b_{jn + i} = a_{i, j}$$

and this is clearly a bijection.

share|improve this answer
1  
To handle negative elements in the sequence, you can just use the continued fractions of $e^{x_k}$ for each $x_k$. –  robjohn Feb 6 '12 at 20:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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