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