From: Paul Elliott <paul.elliott@hrnowl.lonestar.org>
Date: Sun, 19 Jan 1997 16:45:02 -0800 (PST)
To: cypherpunks@toad.com (cypherpunks mailing list)
Subject: Re: Numbers we cannot talk about
In-Reply-To: <"Anonymous"@Jan>
Message-ID: <32e2a55c.flight@flight.hrnowl.lonestar.org>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

> 
> At 10:48 PM 1/18/1997, Secret Squirrel wrote:
> >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.
> 
> There are sets of real numbers whose existence we can prove, but which
> we cannot otherwise describe.  This is more extreme than being
> "generated by an algorithm".  We can't even tell somebody which
> numbers to generate!  (I take "to generate" here to mean "to compute a
> decimal approximation.")
> 
> The set of real numbers is uncountable as is the set of subsets of the
> real numbers.  Yet, we have only countably infinite ways to describe
> sets of numbers.
> 
> All sets of numbers which we can describe can be described with a
> finite set of symbols.  (Human beings are unable to distinguish
> between an infinite number of states.)  The set of combinations of
> this finite set is infinite, but countable.
> 

Perhaps the axioms in set theory that tells us that the integers
have an uncountable number of subsets is, in point of fact, false.
Perhaps only those subsets of the integers that can be described
by an algorithm exist (actually, contrary to what the usual axioms of
set theory assert).

We know that the set of axioms which tell us that there are unaccountably
many reals can be satisfied by a countable model!
(Downward Louwenheim Skolem Tarski theorem.)

I know that Standard mathematical axioms yields lots of interesting
results, but when it talks of the infinite and we are dealing
with a practical subject like cryptography or even physics it
should not be taken too seriously. (With respect to uncountable sets.)

- -- 
Paul Elliott                                  Telephone: 1-713-781-4543
Paul.Elliott@hrnowl.lonestar.org              Address:   3987 South Gessner #224
                                              Houston Texas 77063

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: cp850

iQCVAgUBMuKlNvBUQYbUhJh5AQHZowP/SHm45xKIM5byi4J44tF6ySCilei8ZNC4
f9XgN+VKIQ/Q09tOSnZoRo6e29KKTqV4wxrSCONNu5D691q1atXFw3Z9pdly3INM
Qk3NxxLu+NtldkaaIEkt67s7vri6QORw23gyZmIPOLDQPJZk0LG2wcxxZb6cXOIw
dO4ry2cGOus=
=CJDs
-----END PGP SIGNATURE-----