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
operations:
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 R.Standish.domain.name.hidden
Room 2075, Red Centre
http://parallel.hpc.unsw.edu.au/rks
----------------------------------------------------------------------------
Received on Thu Apr 12 2001 - 18:52:52 PDT