Working with the set of real numbers

[Rotwang]

What's this? A discussion about angels dancing on a the head of a pin? 
Great, I'm in.

On 13/02/2014 14:00, Marko Rauhamaa wrote:
> Oscar Benjamin <oscar.j.benjamin at gmail.com>:
>
>> This isn't even a question of resource constraints: a digital computer
>> with infinite memory and computing power would still be limited to
>> working with countable sets, and the real numbers are just not
>> countable. The fundamentally discrete nature of digital computers
>> prevents them from being able to truly handle real numbers and real
>> computation.
>
> Well, if your idealized, infinite, digital computer had ℵ₁ bytes of RAM
> and ran at ℵ₁ hertz and Python supported transfinite iteration, you
> could easily do reals:
>
>      def real_sqrt(y):
>          for x in continuum(0, max(1, y)):
>              # Note: x is not traversed in the < order but some other
>              # well-ordering, which has been proved to exist.
>              if x * x == y:
>                  return x
>          assert False
>
> The function could well return in finite time with a precise result for
> any given nonnegative real argument.


Minor point: ℵ₁ does not mean the cardinality c of the continuum, it 
means the smallest cardinal larger than ℵ₀. It has been proved that the 
question of whether ℵ₁ == c is independent of ZFC, so it is in a sense 
unanswerable.

More importantly, though, such a computer could not complete the above 
iteration in finite time unless time itself is not real-valued. That's 
because if k is an uncountable ordinal then there is no strictly 
order-preserving function from k to the unit interval [0, 1]. For 
suppose otherwise, and let f be such a function. Let S denote the set of 
successor ordinals in k, and let L denote the set of limit ordinals in 
k. Then lambda x: x + 1 is an injective function from L (or L with a 
single point removed if k is the successor of a limit ordinal) to S, so 
that S is at least as large as L and since k == S | L it follows that S 
is uncountable.

For each x + 1 in S, let g(x + 1) = f(x + 1) - f(x) > 0. Let F be any 
finite subset of S and let y = max(F). It is clear that f(y) >= sum(g(x) 
for x in F). Since also f(y) <= 1, we have sum(g(x) for x in F) if <= 1 
for all finite F. In particular, for any integer n > 0, the set S_n = {x 
for x in S if g(x) > 1/n} has len(S_n) < n. But then S is the union of 
the countable collection {S_n for n in N} of finite sets, so is 
countable; a contradiction.


On 13/02/2014 19:47, Marko Rauhamaa wrote:
> My assumption was you could execute ℵ₁ statements per second. That
> doesn't guarantee a finite finish time but would make it possible. That
> is because
>
>     ℵ₁ * ℵ₁ = ℵ₁ = ℵ₁ * 1

I don't think that's enough - assuming the operations of your processor 
during a second can be indexed by some ordinal k with len(k) == c, if 
each of the c operations per iteration must be complete before the next 
step of the for loop is complete then you need an injective function 
from c * c to k that preserves the lexicographic ordering. I don't know 
whether such a function exists for arbitrary such k, but k can be chosen 
in advance so that it does.