From: magnus@thep.lu.se (Magnus Olsson)
Subject: Re: Number of numbers (Was Re: PI)
Organization: Theoretical Physics, Lund University, Sweden
Date: Wed, 30 Dec 1992 09:11:30 GMT

In article <1992Dec30.010852.143@front.se> samuel@front.se writes:
>In article <1992Dec29.093759.3737@pollux.lu.se>, magnus@thep.lu.se (Magnus 
>Olsson) writes:
>
>> But please note that Samuel wrote "most of the
>> non-rational/non-algebraic" above. He didn't claim that *all*
>> transcendental (non-algebraic) numbers shared pi's property of having
>> a pseudo-random decimal expansion.
>
>Now that I have thought some more about it, I'm modifying my statement to
>be "ALMOST ALL trancendental numbers".
>
>The reason for this is :
>  - All trancendental numbers that DOESN'T have a pseudo-random decimal
>    expansion must have a rule that describes the principle of
>    how this non-pseudo-random decimal expansion is "implemented".
>  - This rule can be encoded into an integer number.
>  - Thereby, all such trancendental numbers correspond to an integer and
>    are ENUMERABLE.
>  - ...which proves that such trancendental numbers are just as 'rare' as
>    rational or algebraic numbers !
>  - Could also be expressed as : There exists only Aleph-0 (*) "such 
>    trancendental" numbers; where Aleph-0 denotes the (infinite) number of 
>    all enumerable numbers.
>
>But maybe this is old stuff. 

Yep, it's old, being one of the fundamental results of computability theory 
:-).  

But it's a very interesting result, isn't it?

For those who didn't quite follow the last step of Samuel's reasoning above: 

The set of "non-random" real numbers, i.e. the ones that can be
computed as the output of an algorithm, corresponds to an integer.
This can be proved by noting that an algorithm (by definition) can be
dscribed by a finite string over some finite alphabet (for example,
all C programs are finite ASCII strings). Each such string can be
encoded as an integer. 

But there exist far more real numbers than there exist integers. This
is easily proved (look up "Cantor's diagonal proof" in a textbook on
the foundations of analysis). Hence, "almost all" (there is a precise
mathemtical meaning to that phrase, BTW) real numbers can *not* be
computed by any algorithm. But not being computable is one definition
of being random. So almost all real numbers have random decimal expansion.

Of course, "random" really means pseudo-random above.

>If this is the case, does anybody know if there
>is some common denomination for "such trancendental" numbers ?

"Computable numbers"?

>(*) By the way, some facts :
>  - "Aleph-0" denominates the number of all enumerable numbers.

You're being a bit sloppy with the terminology here. You really say
that "Aleph-0 denotes the cardinality of an enumerable set (such as
teh set of integers)". "Cardinality" is a measure of how many elements
there are in a set; two sets are said to be of the same cardinality if
their elements can be set in a one-to-one correspondence to each other.

A canonical example (a variation of which was discovered by none less
than Galileo himself): 

There are as many (in the sense of cardinality) even numbers as there
are integers. 

Proof:
The even numbers can be brought into a one-to-one correspondence with
the integers in this way.

Even numbers: 0, 2, -2, 4, -4, 6, -6, ...
Integers:     0, 1, -1, 2, -2, 3, -3, ...

>  - "C" denominates the number of all real (or complex) numbers.

Same here; C is called the cardinal number of the set of real numbers.

>  - Though both Aleph-0 and C = oo, C is infinitely larger than Aleph-0.

Ouch! The statement that Aleph-0 = infinity is meaningless, unless you
very carefully define what you mean. I assume you mean that both
Aleph-0 and C are greater than any finite cardinal number (finite
cardinal numbers are just our usual integers, BTW).

>  - "Aleph-1" denominates the next infinite number larger than Aleph-0.

Actually, I believe Cantor defined it as the cardinality of the set of
all subsets of a set of cardinality aleph-0, and then went on to prove
that there can't exist any cardinal number between aleph-0 and aleph-1.

>  - It is believed that Aleph-1 = C (the continuum hyothesis), but this
>    has not been proven yet !

In fact, it was proved in the sixties (I think) that the continuum
hypothesis in neither provable nor disprovable in ordinary set theory.
What this means is that you can construct a set theory in which it
holds, and another set theory in which it doesn't hold. Both these set
theories are consistent, and all the usual theorems about sets (that
don't involve the continuum hypothesis) are true in both theories.

Confusing? Well, it's a lot like the parallel postulate in Euclid:
It's not provable from the other axioms, and there exist theories
(non-Euclidean geometries) where it doesn't hold.

              Magnus Olsson                | \e+      /_
    Department of Theoretical Physics      |  \  Z   / q
        University of Lund, Sweden         |   >----<           
 magnus@thep.lu.se, thepmo@seldc52.bitnet  |  /      \===== g
PGP key available via finger or on request | /e-      \q