Working with the set of real numbers
Rotwang
sg552 at hotmail.co.uk
Thu Feb 13 22:29:37 CET 2014
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.
More information about the Python-list
mailing list