Hal Ruhl wrote:
> Dear Russell:
> At 4/13/01, you wrote:
> >Bounded complexity does not imply bounded length. Examples include an
> >infinite sting of '0's, and the string '1234...9101112...'
> That was part of the old debate and one of my initial mistakes.  I am not 
> now talking about the length of theorems but the length of their proofs.

Why bound the proof?

> >It must be true that the set of all theorems derivable from a finite
> >set of axioms contains no more information (or complexity) than is
> >contained in the set of axioms itself. However, as pointed out, this
> >doesn't imply the theorems are bounded in length, merely that their
> >complexity is bounded.
> >
> >Does this shed light on this issue?
> With this I agree.   There are however only a finite number of theorems 
> with a finite complexity.  So number theory is either finite in theorem 
> count or it is infinite in complexity.

There can only ever be a finite number of independent theorems, in
fact the number is equal to the number of axioms. However, one can
easily construct an infinite chain of theorems through logical

If T1, T2, T3 etc are theorems, then

T4=T1 and T2, T5=T1 or T2, T6=T1 and T2 or T3, are also theorems. 

We can construct an infinite variety of these theorems. Of course
there will be many tautological relationships between the theorems,
but they're still distinct theorems, just as 

1+1=2, 2+1=3, 3+1=4 ...

are all distinct theorems.

> Hal

Dr. Russell Standish                     Director
High Performance Computing Support Unit, Phone 9385 6967                    
UNSW SYDNEY 2052                         Fax   9385 6965                    
Australia                                [EMAIL PROTECTED]             
Room 2075, Red Centre                    http://parallel.hpc.unsw.edu.au/rks

Reply via email to