From: hale@mailhost.tcs.tulane.edu (William Hale)
Subject: Re: Can a real number be constructed?
Date: Wed, 05 May 1999 16:20:20 +0100
Newsgroups: sci.math
Keywords: Existence e.g. through lambda calculus

In article <37300E73.C4EA9173@ashland.baysat.net>, Nathan the Great
<mad@ashland.baysat.net> wrote:

> I'm having trouble understanding the way Cantorians use real
> numbers.  Can someone explain the following program?
> 
>   Third$ = "."
>   n = 0
>   Number$(n) = "."
>   Do
>     Third$ = Third$ + "3"
>     n = n + 1
>     Number$(n) = Number$(n-1) + "3"
>   Loop
> 
> Does this program have any end results...
>  (1) in a constructive sense?
>  (2) in a platonic sense?
> 
> When considering the end results...
>  (3) is Third$ = ".333... ?
>  (4) is Third$ a real number?
>  (5) does Third$ equal 1/3?
>  (6) does Number$(oo) exist?
> 
> If real numbers can't be constructed...
>  (7) can they be listed?
>  (8) can they be deconstructed, digit by digit?
>  (9) can diagonalization be performed on them?

You asked a lot of questions there. The answers to them are
not easy.

Although I am sure that people will post answers to some
of your questions, I think that there are a couple of more
basic questions that need to be answered or looked into first.
I will give these more basic questions shortly.

Your given program has two aspects that make the questions
that you ask more complex. First, the program does not
terminate. This in itself is not bad, but it does add
an additional complexity to the problem. Second, the
result Number$(n) produced by the program does not
have a finite representation: it is changing its value
as the program runs. This in itself is also not bad, but
it does add another complexity to the problem.

In summary, your program runs forever and the output does
not have a finite representation (in decimal notation).

First, I will consider a program that terminates and the output
has a finite representation. I will then ask similar questions
to yours about it.

Second, I will consider a program that terminates, but the input
does not have a finite representation. I will then ask similar questions
to yours about it. I will do this second consideration in a later
post.

But before I do that, I would like to consider four different contexts
where these questions might be asked. They are independent of one another
and should be kept separated. The four different contexts are:

   A) Turing machine
   B) Church's Lambda Calculus
   C) Zermelo Fraenkel axioms for set theory
   D) Peano's axioms for natural numbers

Three of the above have been mentioned in various threads of this
newsgroup. Church's Lambda Calculus may be new to some. There
is an excellent site about the Lambda Calculus at this URL:

   http://www.cs.monash.edu.au/~lloyd/tildeFP/Lambda/Ch/01.Calc.html

This site is nice because it allows you to compile and run programs
that are written in the Lambda Calculus.

The Lambda Calculus does not depend upon set theory. In fact, it
defines functions not as ordered pairs with a domain and a codomain,
but more in an operational, computational manner.

In order to keep this post short, I will consider only one question
similar to yours. Your question was "Does 1/3 exists?" My question
is "Does 3 exists?"

====================================================================
A) Turing machine
====================================================================

The program for the number 3 is:

   Three$ = "."
   n = 0
   Number$(n) = "."
   Three$ = "3" + Three$
   n = n + 1
   Number$(n) = "3" + Number$(n-1)

Does this program have any end results...
  (1) in a constructive sense?
  (2) in a platonic sense?

====================================================================
B) Church's Lambda Calculus
====================================================================

The program for the number 3 is:

   ZERO = lambda s. lambda z. z,
   ONE  = lambda s. lambda z. s(z),
   TWO  = lambda s. lambda z. s(s(z)),
   THREE = lambda s. lambda z. s(s(s(z)))

Does this program have any end results...
  (1) in a constructive sense?
  (2) in a platonic sense?

====================================================================
C) Zermelo Fraenkel axioms for set theory
====================================================================

The definition for the number 3 is:

   ZERO = {},
   ONE  = {ZERO},
   TWO  = {ZERO, ONE},
   THREE = {ZERO, ONE, TWO}

Does this definition have any end results...
  (1) in a constructive sense?
  (2) in a platonic sense?

====================================================================
C) Peano's axioms for natural numbers
====================================================================

The definition for the number 3 is:

   ONE  = succ(ZERO),
   TWO  = succ(ONE),
   THREE = succ(TWO)

Does this definition have any end results...
  (1) in a constructive sense?
  (2) in a platonic sense?

--
Bill Hale