[FOM] Are the Decidable Theories R.E.?

[Noah Schweber]

The question "Is X r.e.?" should really be asked at the level of index
sets; I assume that what's being asked here is, "Is the set of e such that
W_e is a recursive complete set of sentences in the language of arithmetic
an r.e. set?"

If this interpretation is correct, then - unless I've made a mistake - the
answer to (1) (so (2) also) is no.

For simplicity I'll take the language of arithmetic to be {0, S, +, *}. Let
T be a computable (by Craig's Trick) set of sentences which imply:

The complete theory of (N, S) (which is decidable);

* is trivial: a*b=0 for all a, b;

If a!=b, then a+b=0;

For all a, a+a=0 or a+a=S0; and

Sk+Sk=0 for each k in the Halting Problem (conflating k and its numeral).

Now fix some co-r.e. set P, and some natural n; and let S_P(n) be the
theory gotten from adding to T the sentence "Sk+Sk=0" for each k such that
n has not left P by stage k.

Finally, let R_P(n) be the deductive closure of S_P(n). Then R_P(n) is
decidable iff n is in P, and an index for R_P(n) as an r.e. set of
sentences in the language of arithmetic can be found effectively from n.
But then the map n->R_P(n) is a many-one reduction of P to Decidable; since
P was arbitrary co-r.e., Decidable can't be r.e.



******



I've written this a little quickly, though, so I'm not 100% sure it's
correct.





 - Noah Schweber

On Wed, Mar 1, 2017 at 10:38 AM, Richard Heck <richard_heck at brown.edu>
wrote:

> A student asked me the following question, to which I don't know the
> answer. Anyone?
>
> Actually, it comes in two forms, depending upon what we mean by "theory":
> a set of axioms or a set of theorems.
>
> (1) Let D be the set of all deductively closed, recursive sets of
> sentences of the language of arithmetic (i.e., the decidable theories in
> the "theorems" sense). Is D r.e.?
>
> (2) Let D be the set of all recursive sets of sentences of the language of
> arithmetic whose deductive closure is also recursive (i.e., the decidable
> theories in the "axioms" sense). Is D r.e.?
>
> An affirmative answer to (2) obviously implies an affirmative answer to
> (1), but the converse is not so clear to me.
>
> My first two ideas failed. The obvious diagonalization procedure does not
> work, because there is no guarantee that the generated theory is decidable.
> I also realized quickly that an affirmative answer to (2) implies that the
> inconsistent (formal) theories are r.e., and maybe that would be a
> problem. But it's not, since the inconsistent (formal) theories clearly
> are r.e.: Just start listing the theories and their theorems, and whenever
> you run across a contradiction in a theory, add it to the list. So, well,
> ....
>
> Cheers,
> Richard Heck
>
>
>
> --
> -----------------------
> Richard G Heck Jr
> Professor of Philosophy
> Brown University
>
> Website:         http://rgheck.frege.org/
> Blog:            http://rgheck.blogspot.com/
> Amazon:          http://amazon.com/author/richardgheckjr
> Google+:         https://plus.google.com/108873188908195388170
> Google Scholar:  https://scholar.google.com/citations?user=QUKBG6EAAAAJ
> ORCID:           http://orcid.org/0000-0002-2961-2663
> Research Gate:   https://www.researchgate.net/profile/Richard_Heck
> Academia.edu:    https://brown.academia.edu/RichardHeck
>
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170301/1774ff47/attachment.html>