[FOM] Question on Equivalence of Theorems
Robin Adams
radams at maths.man.ac.uk
Thu Jan 16 12:01:52 EST 2003
Mathematicians often talk of two theorems being equivalent, or one being
stronger or weaker than another. This cannot mean logical equivalence or
strength; any two theorems are logically equivalent, since both are true.
Nor does it seem to be anything related to proof theoretic strength.
`Theorems T1 and T2 are equivalent' seems to mean that there is a simple
derivation of T2 from T1 and vice versa; smipler than any proof of the
theorem from scratch (i.e. the axioms). `Stronger' and `Weaker' indicates
that there is such a proof in one direction, but not the other.
Has this notion ever been formalised in proof theory? I have in mind the
assignment of a level of compexity to proofs and derivations; then a
definition along the lines of
`T1 and T2 are equivalent iff there are complexity 0 derivations of T2
from T1 and vice versa'
or
`T1 and T2 are equivalent iff there are derivations of T2 from T1 and vice
versa of complexity <= n, while every proof of T1 and T2 is of complexity
>n.'
--
Robin Adams
More information about the FOM
mailing list