Re: Another set with cardinality |Z|

stephen_at_nomail.com
Date: 09/23/04 

Date: 23 Sep 2004 15:24:25 GMT

In comp.theory Eray Ozkural exa <erayo@bilkent.edu.tr> wrote:
: israel@math.ubc.ca (Robert Israel) wrote in message news:<citd77$3o0$1@nntp.itservices.ubc.ca>...
:> In article <fa69ae35.0409221823.682ae186@posting.google.com>,
:> Eray Ozkural exa <erayo@bilkent.edu.tr> wrote:
:> >Let's have an algorithm that starts with
:> >0.1 in binary, and constructs a tree in breadth-first fashion
:>
:> > 0.1
:> > 0.01 0.11
:> >0.001 0.011....
:>
:> >You get the idea... It's obvious that this tree has the same
:> >cardinality as Z, since this is a nonhalting algorithm (or since I can
:> >give an integer to every node, etc.) Now, I want to prove that such a
:> >subdivision procedure cannot generate all x in (0,1) in an intuitive
:> >way. Is the easiest method proof by contradiction?
:>
:> Hint: can you generate 1/3?

: Hmm. In binary, it will go like

: 0.01010101...

: You mean that it cannot generate because this rational number has an
: infinite binary expansion. I am not sure if that is an intuitively
: acceptable explanation, though, simply because of the fact that the
: tree has an infinite number of nodes, e.g. an infinite depth,
: therefore this number is computed in the limit.

I think it may be a mistake to expect there to be an 'intuitively
acceptable explanation' for infinite sets. A lot of the results
simply are counter to most people's intuitions.

Stephen

Relevant Pages

  • Re: Another set with cardinality |Z|
    ... In comp.theory Eray Ozkural exa wrote: ... since this is a nonhalting algorithm (or since I can ... : infinite binary expansion. ... simply are counter to most people's intuitions. ...
    (comp.theory)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: Poetential infinity
    ... > represented more formally as discrete infinite sequences. ... If you search Google with terms "potentially infinite" turing machine tap ... for an algorithm has a finiteness requirement. ... "computational method" which abandons the finiteness requirement: ...
    (sci.logic)
  • "Algorithmic Randomness, Quantum Physics, and Incompleteness"
    ... all finite sequences are to be found infinitely often and ... different members of the infinite set of random numbers. ... Just using random numbers with initial digits 1 thru 9, ... it generated by a shorter input algorithm than the length ...
    (sci.logic)
  • Re: Why does Cantor a target for cranks?
    ... relativity and quantum ... intuitions may be offended in people, ... integrated approach toward the infinite, ... characterizes the naturals, is violated by the ...
    (sci.math)