Prove uncountability of R using an algorithm?

136 Views Asked by At

Let's say I want to prove uncountability of $\mathbb{R}$ using an algorithm (I will use Python).

I will consider reals $0 \le x \lt 1$ and represent the decimal development of $x$ with a generator.

If I have a generator of reals, I can produce a new real (that is, a generator) based on an iterable of reals using diagonal argument :

def diag_argument(reals):
 n = 0
 for x in reals:
   for i, d in enumerate(x):
    if i == n:
     yield (d+1) % 10
     break
   n += 1

If I could write an enumerate_R function, diag_argument(enumerate_R()) would produce a new real.

I would be tempted to say that this proves that $\mathbb{R}$ is not recursively enumerable. Is that correct ? (I don't know much about logic / CS)

If I want to use my diag_argument function to prove that $\mathbb{R}$ is not countable, can I suppose there is some kind of "oracle" function enumerate_R and still use my diag_argument function to show a contradiction ?

Would that be an acceptable proof from a logical point of view, in the context of set theory ?