FOM: Induction illogical?

[Schalekamp, Hendrik J.]

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/