Re: Another set with cardinality |Z|

• Previous message: LarryLard: "Re: Another set with cardinality |Z|"
• In reply to: Eray Ozkural exa: "Another set with cardinality |Z|"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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. :)

• Previous message: LarryLard: "Re: Another set with cardinality |Z|"
• In reply to: Eray Ozkural exa: "Another set with cardinality |Z|"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]