FOM: 70:Efficient Formulas and Schemes

Raatikainen Panu A K Praatikainen at elo.helsinki.fi
Thu Nov 4 04:49:04 EST 1999


Stephen Fenner is right in pointing out that reasons I gave for my 
claim did not really constitute a proof. I think, however, that it can 
be competed very easily (please correct me if I am wrong):

(Below, by "a theory" I always mean a finitely axiomatizable 
theory) 

First, note that for every sentence/theory there exists an efficient 
sentence/theory that is logically equivalent with it. Next, note that 
one can recursively enumerate all theorems of  f.o. logic that have 
the form S <-> T. 
Assume then that one could recursively enumerate all efficient 
sentences/theories. By simultaneously enumerating them and all 
logical equivalences, one could eventually conclude, for an 
arbitrary* consistent theory or sentence, that it is logically 
equivalent with an efficient sentence/theory more complex than Pa 
& -Pa, and hence consistent. OK?

(* this does not include the finitely many trivial cases that are 
consistent and less complex than Pa & -Pa.)

* * *

About Fenner's conjecture: It was also my initial conjecture too (in 
some 3 years ago), but later I started to doubt it - and I still have a 
hunch that it is false. However, my first idea of how to prove such 
things did not work, and other issue kept me busy, so I forgot the 
whole theme without ever deciding the question. Only the recent 
ideas of Friedman made me to think the issue again.

Panu Raatikainen 




More information about the FOM mailing list