We are talking about ordinary reals in constructive mathematics.


1. Let represent each real number by infinite converging series:
$$r = [\;(a\_0,b\_0),(a\_1,b\_1),...,(a\_i,b\_i),...\;]$$
$$where\quad a\_i \leq b\_i\quad and \quad a\_i \leq a\_{i+1} \; and \; b\_{i+1} \leq b\_i$$


And interval $(a\_i,b\_i)$ converges: for any given rational $e > 0$ there is index $j$ such that $b\_k - a\_k < e$ for all $k \geq j$.
2. There are only one way to construct such a number: to build an algorithm that produces $ (a\_{i+1},b\_{i+1}) $ from (a,b) (or some nearly equivalent).
3. Let model algorithms by lambda terms (we are able to do so because lambda calculus is Turing complete).
4. It is easy to show that each lambda term may be represented by unique natural number (this is simple serialization/deserialization process, well known for every programmer).
5. So there is a one-to-one correspondence between real numbers and subset of natural numbers.
6. This imply that constructive reals and naturals are equipotent sets.


What are not ok with this reasoning and why?



Are real numbers countable in constructive mathematics?
I am going to attempt another answer which directly addresses what you wrote.


It **cannot** be shown constructively that every infinite subset of $\mathbb{N}$ is in bijective correspondence with $\mathbb{N}$. Thus your reasoning has a flaw when going from step 4 to step 5. By "infinite set" here I mean that there is an injective sequence from $\mathbb{N}$ into the set. "Bijective correspondence" means there is a bijection and its inverse between the sets. Concretely:


**Theorem:** Suppose every infinite subset of $\mathbb{N}$ is in bijective correspondence with $\mathbb{N}$. Then we can solve the Halting problem (assuming Markov principle).


*Proof*. The set
$$S = \lbrace n \mid \text{the $n$-th Turing machine diverges}\rbrace$$
is obviously infinite. Suppose we had a surjection $b : \mathbb{N} \to S$. But then we can semidecide whether a given Turing machine diverges, so we can decide whether a given Turing machien halts. (There is a hidden use of Markov principle here, can someone get rid of it?) QED.


Likewise, in your concrete example, it cannot be shown constructively that there is a bijection between $\mathbb{N}$ and constructive reals, or lambda terms representing them, even though it is the case that the lambda terms representing reals are in bijective correspondence with a subset of $\mathbb{N}$. That was precisely the point of my first answer: I gave a proof that any attempt at enumeration of the reals omits a real.


Furthermore, from discussion in my other answer it seems that you claim that in constructive mathematics all subsets of $\mathbb{N}$ are constructively enumerable. That is false. The set $S$ from the above proof is an example of a set which cannot be constructively enumerated. The set $S$ is of course constructively well defined (or "built" in your sense), as it is not too hard to write down a formula that describes it (using Kleene's predicate $T$).


