From: ichudov@algebra.com
Date: Sun, 19 Jan 1997 19:43:46 -0800 (PST)
To: Paul Elliott <paul.elliott@hrnowl.lonestar.org>
Subject: Re: Numbers we cannot talk about
Message-ID: <199701200343.TAA29149@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


Paul Elliott wrote:
> -----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).

It is very interesting. My limited understanding of this approach is
that they say that only things that can be constructed by some
positive method exist (please correct me if I am mistaken).

But the question is, where do they stop and what exactly is "construction?"

Say, does sqrt(2) "exist" in their sense of the world? We know we can
calculate any given number of digits in it, is that enough?

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

Some of the applications of these theories are very relevant. For
example, a theorem that proves that it is impossible to write a program
that would determine if any other program would stop or loop forever, is
very relevant and interesting.

	- Igor.