From: Paul Foley <mycroft@actrix.gen.nz>
Date: Sun, 19 Jan 1997 18:12:17 -0800 (PST)
To: tozser@stolaf.edu
Subject: Re: I beg you, PLEASE prove that 0.123456789101112131415 is IRRATIONAL
In-Reply-To: <199701191820.MAA24006@nic.stolaf.edu>
Message-ID: <199701200208.PAA21232@mycroft.actrix.gen.nz>
MIME-Version: 1.0
Content-Type: text/plain


On Sun, 19 Jan 1997 12:20:45 -0600, Sir Robin of Locksley wrote:

    >Is it possible to prove that number 0.1234567891011121314151617181920...
    >iz irrational? 

   Most definately. All you need to do is prove that the set of this number is
   uncountable, ergo is irrational. If you have friend who have done math in real
   analysis they can explain more.

This makes no sense at all.  Presumably "the set of this number" means
the cardinality of the set {1, 2, 3, ...} which is quite obviously
countable!  The definition of countable is that it can be put in one
to one correspondence with exactly this set!

The number is, nevertheless, irrational.  A rational number is one
that can be written as a ratio of two integers (and infinity is _not_
an integer...or any kind of number, for that matter.  Else there would
be no irrational numbers).  Any rational number will end with a
repeating series of digits (which may be 0s, of course).  This number
clearly has no such repeating sequence.

    >Is it REALLY true that there are real numbers that cannot be generated
    >by any algorithm? Some guy said that since the set of algorithms is
    >countable, but the set of real numbers is more than countable, there 
    >must be some numbers for which there is no algorithms that generate them.

   If you show me an algorythm that calculates the real number TT (=3.14.....)
   I'll give you a Nobel Prize personally!

Some things are too easy.  How about pi = 4(1 - 1/3 + 1/5 - 1/7 + ...)
Evaluate.

The prize should probably go to Liebniz, though...

To answer the original question, yes, there are numbers (the vast
majority of numbers, in fact) which cannot be calculated by an
algorithm.  The computable numbers (those which can be generated
algorithmically) are countable (because a universal Turing machine can
emulate any other Turing machine given the appropriate input
(program), you can give each possible algorithm a number corresponding
to the program that implements it.  Such numbers are integers, hence
countable, so the number of algorithms is countable.  Since the real
numbers are not countable, it's obvious that there are real numbers
which are not computable.)

    >But I still do not believe him.
    >
    >Also, is it true that the sequence of digits in e is random because the ONLY
   way to get to the
    >p'th digit is to calculate the p-1'st digits?
    >
   Exactly! This is called recursive definition. To get the p-th set in the
   sequence you need to find p-1 first...

The sequence of digits in e is not random!  You mean the distribution
of digits looks random (is it?).  e is certainly computable, which
implies there is an algorithm that generates successive digits of e
given inputs of 0, 1, 2, 3, ...  I have no idea whether every such
algorithm must generate all preceding digits in doing so.

   >Also, is it the correct definition of a real number: 
    >
    >``A real number is the class of numbers which can represent the length of
    >an arbitrary line.''

   Well, that is not entirely true... The length of any arbitrary line can be any
   number, rational, natural, etc. Real numbers are the numbers that defy all
   other categorization (they are not rational, irrational, natural, etc.) They
   are complex and despite any instinctual perception, there are a lot of them!

No, the original definition is perfectly good.  Natural numbers are
rational, and rational numbers are real numbers.  Irrational numbers
are also real numbers.  The last sentence is correct, though -- real
numbers are complex numbers (although that's not what you meant, I
think) and there are a lot of them (an infinite number, of course, but
a "bigger" infinity than the countable sets of naturals or rationals).

   -----BEGIN PGP SIGNATURE-----
   Version: 4.5

What's version 4.5?

-- 
Paul Foley <mycroft@actrix.gen.nz>       ---         PGPmail preferred

	   PGP key ID 0x1CA3386D available from keyservers
    fingerprint = 4A 76 83 D8 99 BC ED 33  C5 02 81 C9 BF 7A 91 E8
----------------------------------------------------------------------
November, n.:
	The eleventh twelfth of a weariness.
		-- Ambrose Bierce, "The Devil's Dictionary"