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
More information about the FOM
mailing list