Skip to main content
1 of 16
Vag
  • 342
  • 4
  • 13

Are constructive real numbers equipotent to natural numbers?

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+1} \geq a_i \; and \; b_{i+1} \leq b_i$$

In constructive mathematics, 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).

Let model algorithms by lambda terms (we are able to do so because lambda calculus is Turing complete).

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).

So there is a one-to-one correspondence between real numbers and subset of natural numbers.

This imply that constructive reals and naturals are equipotent sets.

Correct?

Vag
  • 342
  • 4
  • 13