# FOM: 70:Efficient Formulas and Schemes

Stephen Fenner fenner at cs.sc.edu
Fri Nov 5 11:18:26 EST 1999

```On Thu, 4 Nov 1999, Raatikainen Panu A K wrote:

> 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?

Yes, you're right.  In fact, this shows that the set of beta-efficient
theories is Turing-equivalent to the halting problem:

{e}(x) halts  ==>  PA |- {e}(x) halts
{e}(x) doesn't halt  ==> (PA + "{e}(x) doesn't halt") is consistent
==> ( ..."...) <--> some beta-efficient sentence
longer than Pa & -Pa

So no natural intermediate c.e. degree here ;-)

> 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.

I think the answer would be interesting.  R (the Kolmogorov random
strings) is a very natural, interesting example of an immune set, and
there aren't many natural examples of immune sets out there.

Steve

```