When it comes to real numbers like $\pi$ it is easy for us giving an algorithm that can compute it (even if the algorithm never halts, we know it will converge so basically we will find new digits and hence we can find the nth digit).

Each algorithm can be encoded to a natural number (Turing used powers of prime numbers to do that), so as long as we give a real number that can be written using an algorithm (Even if the algorithm never halts) that can approximate it as good as long as it is left running, we have a Injection from Real Numbers to Natural Numbers.

However when someone say there are also Reals that can't be represented with an algorithm I have really have some doubt about that fact.

The argument used by people who claim that (if I understood correctly), is to provide an algorithm that if written, would require a tape of infinite lenght, however: to actually prove that this new algorithm is infinite, they should define it.. providing anyway an algorithm.

If I use a TM that writes this "infinite definition" and simulate/execute is as long as it is written, I can create anyway an algorithm, that can be encoded again as natural number.

So actually I think that it is wrong when someone say that there are Real numbers that can't be mapped to natural numbers, but I have anyway the suspect that I'm wrong. Why?

The reason for which Reals are uncountable to me is clear (no bijection with natural numbers), However I'm not convinced that there are real numbers that can't be mapped to a Natural number.


Clarification: I'm not speaking of uncomputable numbers, but to show me a Real number (Even one that we don't know how is value exactly is) that can't be encoded as natural number. This is not the boring and ever asked question about computable numbers ^^.


I assume real numbers are a subclass of algorithms (and hence turing machines), I assume that because I think it is essentially true. When we give transcendent numbers we are actually defining them through an algorithm.

From a comment below:

$\pi$ is a number, and there are various definitions of real numbers in ZFC. Yes, it is computable, which means there exists an algorithm which computes it. Note also that there are many algorithm who compute it, not just onelockquote

How can we construct a number that is not an algorithm? We can't, because to actually show that a number is not in an algorithm set, we have to show the number, actually constructing it (using a algorithm, that regardless if that is computable, we can write, and hence encode as natural number)! So, we give $\pi$ but in reality we defined it through an algorithm.


I also assume that Cantor just showed there's no bijection between natural numbers and reals, he didn't showed in anyway that there are more Reals than Naturals. From the comments below I think to understand that most people is convinced that Real numbers are more than natural numbers, I'm not convinced of that.

Infact every algorithm can be encoded as natural number (skipping some natural numbers), and every natural number can be encoded as a real number (skipping many reals).


closed as unclear what you're asking by Peter Franek, Did, Tobias Kildetoft, Morgan Rodgers, Adam Hughes Dec 7 '16 at 15:30

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ "I assume real numbers are a subclass of algorithms". This is a terrible assumption since it is clearly false by a simple argument of cardinality. $\endgroup$ – Tobias Kildetoft Dec 7 '16 at 13:31
  • 3
    $\begingroup$ Look, stating "I assume" will not magically make false things true. $\endgroup$ – Tobias Kildetoft Dec 7 '16 at 13:39
  • 1
    $\begingroup$ Cantor showed that there is no surjection $f\colon \mathbb{N}\to \mathbb{R}$, which together with the existence of an injection $\iota \colon \mathbb{N}\to \mathbb{R}$ and Cantor-Schröder-Bernstein shows that there is no injection $\mathbb{R}\to\mathbb{N}$. $\endgroup$ – Daniel Fischer Dec 7 '16 at 13:42
  • 2
    $\begingroup$ @DarioOO No, the diagonal argument shows that for all sets $A$ there is no surjection $A \to \mathscr{P}(A)$. If you know that there is a bijection $\mathscr{P}(\mathbb{N}) \to \mathbb{R}$, it follows that there is no surjection $\mathbb{N}\to\mathbb{R}$. $\endgroup$ – Daniel Fischer Dec 7 '16 at 13:55
  • 1
    $\begingroup$ @DarioOO No, the sets both have the same number of elements. See the work of Cantor. You are free to reject this, I won't waste my time trying to argue or enlighten you. $\endgroup$ – Morgan Rodgers Dec 7 '16 at 19:18

Who says there are reals that can't be encoded to a natural number?

Here is a way to encode any real number $x$ to a natural number: if $x$ is a natural number, encode it as itself; otherwise encode $x$ as $1$, encode $1$ as $2$, encode $2$ as $3$, etc.

So I am confident that no competent mathematician says deliberately that there are real numbers that can't be encoded to a natural number.

What mathematicians do say is that there is no single encoding of real numbers to natural numbers such that the domain of that single encoding contains all real numbers. Therefore, once you choose a particular encoding, some real numbers (an uncountable number of them, actually) will be left out.

  • $\begingroup$ Is there an additional proof over diagonalization then? $\endgroup$ – GameDeveloper Dec 7 '16 at 14:03
  • $\begingroup$ @David K. In other words, $\mathbb{N}\cup \{x\}$ is countable. One can generalize that, since a union of countable sets is countable: The set $P$ of positive square roots of prime numbers is a countable set of computable irrational numbers. And $\mathbb{N}\cup P$ is countable.etc. $\endgroup$ – David Snyder Dec 7 '16 at 16:20
  • $\begingroup$ @DavidSnyder True, and you can repeat that trick indefinitely. The original inspiration for my answer was the argument of a high school classmate against the uncountability of the real numbers. He claimed that after using diagonalization to find a number not in the sequence, you could simply insert that number in the sequence. And again with the next missing number you found by diagonalization, etc. Those statements were true, but all they ever did was exchange one non-surjective mapping-of-integers-to-reals for another. $\endgroup$ – David K Dec 7 '16 at 19:34

It is possible to prove (see, for example, Theorem 7.1.5 in the book How to Prove It by Daniel Vellemsn) that the following are equivalent:

  1. A set A is countable (finite or countably infinite).

  2. There is an injection from the set A into the set of positive integers.

  3. There is a surjection from the positive integers onto A.

Since there is no bijection from the reals to the positive integers (i.e. the set of real numbers are not countable) there is no injection from the set of real numbers to the set of positive integers.

  • 1
    $\begingroup$ And no surjection from the positive integers onto the reals. $\endgroup$ – David Snyder Dec 7 '16 at 13:53

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