FOM: 70:Efficient Formulas and Schemes

[Stephen Fenner]

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