# How can you construct the bijection between real numbers and functions over naturals? [duplicate]

I was reading "Classical Recursion Theory" by Odifreddi and it starts with this phrase:

Recall that Classical Recursion Theory is the study of real numbers or, equivalently, functions over the natural numbers.

I come from Computer Science so this was puzzling to me at first. I understand he's referring to the fact that there is a bijection between $$\mathbb{N}$$ $$\rightarrow$$ $$\mathbb{N}$$ and $$\mathbb{R}$$. I know that |$$\mathbb{N}$$ $$\rightarrow$$ $$\mathbb{N}$$| is greater than |$$\mathbb{N}$$| (Cantor's diagonal), but how can you find the real $$x$$ corresponding to a certain function?

I know that given a real $$x$$ we can construct a function like this: $$f(n) =$$ the $$n$$-th digit of $$x$$. But what is the other way around? We can't use digits in this case, I think, because we have numbers with more than one digit; I don't think changing the digit system would help (I think every digit system has a finite alphabet?) and that way we would link more functions to the same real number.

I know that you can't compute reals in a strict sense (you would need $$\infty$$ digits) but I was wondering if there was at least some sketch-procedure of how to represent a function with a real number, to have at least logically a glimpse of what is the number $$x$$ corresponding to a generic function $$f$$: $$\mathbb{N}$$ $$\rightarrow$$ $$\mathbb{N}$$.

## marked as duplicate by Asaf Karagila♦ set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Feb 22 at 9:21

• post scriptum: I come from CS and I'm not a native english speaker. I've tried to search the site and google for an answer but I can't find anything, perhaps due to my low knowledge of the terminology. If it's a duplicate, let me know (I've found similar questions but they all dealt with smaller subsets of functions). – olinarr Feb 22 at 8:10
• I think you can map a function $f: \mathbb{N} \rightarrow \{1, .., n\}$ to the decimal expansion of a real number in base $n$. You can then argue, that the set of functions $\mathbb{N} \rightarrow \{1, .., n\}$ is the same size as $\mathbb{N} \rightarrow \mathbb{N}$. – quarague Feb 22 at 8:20
• Mind that, as a general principle, you may know that two sets have the same cardinality without being able to define an explicit bijection. – Andrea Mori Feb 22 at 8:22
• @quarague do you mean $n$ as the greatest value of $f$? In that case, wouldn't we let out functions without a maximum? Such as $f(n)=n$. – olinarr Feb 22 at 8:22
• @NetHacker I think you are right, this is not a bijection. It's still surjective, so maybe one can modify it a bit. – quarague Feb 22 at 8:25

Let $$x_0\ge 0$$ be any real number and recursively define for $$n\in\mathbb N=\{0,1,\dots\}$$: \begin{align*} a_n &= \lfloor x_n \rfloor, \\ x_{n+1} &= g(x_n-a_n), \end{align*} for $$g$$ the bijection $$[0,1)\to\mathbb R_{\ge 0}$$ given by $$g(x) = \frac{x}{1-x}$$ with inverse given by $$g^{-1}(y) = \frac{y}{1+y}$$.
I claim that the map $$\mathbb R_{\ge 0} \to \mathbb N^{\mathbb N}$$ given by $$x_0 \mapsto (a_n)_{n\in\mathbb N}$$ is a bijection. Compose this with your favorite bijection between $$\mathbb R_{\ge 0}$$ and $$\mathbb R$$ to obtain what you asked for.