Re: Another set with cardinality |Z|
From: Abraham Buckingham (twizlewink_at_hotmail.com)
Date: 09/23/04
- Next message: Georg: "Re: complete measure"
- Previous message: Dave Seaman: "Re: The real numbers, and general comments"
- In reply to: Eray Ozkural exa: "Another set with cardinality |Z|"
- Messages sorted by: [ date ] [ thread ]
Date: 23 Sep 2004 06:00:06 -0700
erayo@bilkent.edu.tr (Eray Ozkural exa) wrote in message news:<fa69ae35.0409221823.682ae186@posting.google.com>...
> 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?
>
> Regards,
All of the numbers you have generated are of finite length, can you
find some numbers who's binary representations never terminate?
Finding counter-examples seems to me to be a form of proof by
contradiction although I find it convienent to distinquish between the
two since counter-examples are sometimes easier to find then a deduced
logical flaw, although essentially I think that's what you're doing.
If you're looking for a mapping from your set to the subset of
naturals you could try taking the set of primes and mapping them like
so, 0.1 = 2^1, 0.01 = 3^1, 0.11 = 2^1 * 3^1 and so on, giving a unique
prime to each binary place and making each of the numbers your
algorithm generates match up with a unique number. of the form p_1^{0
or 1} * p_2^{0 or 1} * ... * p_n^{0 or 1} where p_k is the k-th prime
number and n is the breadth of the number and you select 0 or 1 based
on which binary digit is in the k-th place of the number. You could
then refer to Cantor's proof of the uncountability of the interval
(0,1). Mapping in a similar fashion to powers of primes is an easy way
to show that the cartisan product of two countable sets is also
countable, by mapping it to a subset of N and extends easily to the
case of n cartisean products. Hope this helps. :)
- Next message: Georg: "Re: complete measure"
- Previous message: Dave Seaman: "Re: The real numbers, and general comments"
- In reply to: Eray Ozkural exa: "Another set with cardinality |Z|"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
