FOM: Induction illogical?
Schalekamp, Hendrik J.
carnun at maths.uct.ac.za
Tue Mar 2 15:02:12 EST 1999
In FOM: Induction illogical?(corrected version) (Thu, 25 Feb 1999
20:37:03 +0100) Harvey Friedman wrote:
> 5. Is there a sentence of predicate calculus that can be proved to be valid
> **via a short proof** with the help of mathematical induction, but which
> cannot be proved in predicate calculus **via a short proof**?
>
> The answer to this is well known, and the answer is yes. But now we ask:
>
> 6. Is there a simple, natural example of 5?
How about the other way around? Does anyone know if there are any predicate calculus
proofs which are neccesarily shorter (in Harvey's sense) than
induction proofs? It doesn't seem that the existance (as demonstrated
by Harvey) of a shorter 'inductive' proof excludes this possibility.
Regards
Hendrik
Carnun, Son of Danu
===================
"A day without sunshine is like... night" - Anon
"I think therefore I am, is a statement of an intellectual
who underrates toothaches." - Milan Kundera (Immortality)
Email: carnun at maths.uct.ac.za
URL: http://www.deathsdoor.com/carnun/
More information about the FOM
mailing list