This question already has an answer here:

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 Feb 22 at 9:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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). $\endgroup$ – olinarr Feb 22 at 8:10
  • $\begingroup$ 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}$. $\endgroup$ – quarague Feb 22 at 8:20
  • 3
    $\begingroup$ Mind that, as a general principle, you may know that two sets have the same cardinality without being able to define an explicit bijection. $\endgroup$ – Andrea Mori Feb 22 at 8:22
  • $\begingroup$ @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$. $\endgroup$ – olinarr Feb 22 at 8:22
  • $\begingroup$ @NetHacker I think you are right, this is not a bijection. It's still surjective, so maybe one can modify it a bit. $\endgroup$ – quarague Feb 22 at 8:25

Here's an idea I didn't check in detail, but maybe it helps:

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.


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