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

[Noah Schweber]

I believe Prof. Salehi is incorrect in his assessment of my answer. There
are no axioms in S_P(n) which imply that Sa+Sa=1 for *any* a; the structure
consisting of the naturals with the usual successor, and + and * being
trivial (a+b=a*b=0 for all a, b) is always a model of S_P(n).

In particular, T does **not** prove S(k)+S(k)=1 if k is not in the halting
problem; T merely proves that if k *is* in the halting problem, then
S(k)+S(k)=0. (Note that T says "Sk+Sk=0 for each k in the Halting Problem"
but does **not** say the converse!)

I could be missing something of course, but I believe my answer does work;
I certainly believe that the theories it produces are not inconsistent,
since the structure described above always satisfies them.


 - Noah Schweber

On Sat, Mar 4, 2017 at 5:53 AM, Saeed Salehi <saesal at gmail.com> wrote:

> As suggested by ​Noah Schweber only index sets should be considered;
> however, unfortunately, this answer is not correct (as is explained below
> in *III*).
> (*I*) Let us assume that there exists a 1-1 (and onto) correspondence
> between all the sentences in the language of arithmetic (say {0,1,*+*,*<*,
> x}) and all the natural numbers (via a Godel numbering). So, every RE set
> *W*_*n* corresponds to an RE set of sentences and vice versa. There
> exists a recursive function *n* |--> *n*' such that *W*_{*n*'}={*x* | Pr_L
> (*z*_1 & ... & *z*_k --> *x*) for some *z*_1,...,*z*_k in *W*_*n*}, where
> Pr_L is the provability predicate in (pure first order) logic (so *W*_{*n*'}
> is the deductive closure of *W*_*n*). Now, the second question is whether
> the set *D*={*n* | *W*_{*n*'} is recursive} is RE or not? The first
> question is whether *D**={*n* | *W*_*n* is deductively closed and
> recursive} is RE or not?
> (*II*) By Rice's Theorem the (index) set *D* is not recursive (since it
> is not trivial).
> (III) By Proposition 5.18 [on page 85] of Bridges' book (Computability: A
> Mathematical Sketchbook (1994) http://www.springer.com/gp/
> book/9780387941745) the (index) set *D* cannot be RE since for some  *i*\in
> *D* and some *j* we have \varphi_*i* \subset \varphi_*j* but* j* is not
> in *D*: Put \varphi_*i* be a recursive function which halts and equals to
> 0 on *n* if and only if *n* is (the  Godel number of) a sentence in which
> x does not appear (it is a sentence in the language {0,1,*+*,*<*}) and is
> true in <*N*;0,1,*+*>; and let \varphi_*j *be a recursive function which
> halts and equals to 0 on *n* if and only if *n* is (the Godel number of)
> a theorem of Peano's Arithmetic, PA. By Presburger's Theorem *i* is in *D*
> (since *W*_*i* is the set of {0,1,*+*,*<*}-sentences true in <*N*;0,1,*+*>)
> but *j* is not in *D* (since *W*_*j* is the set of theorems of PA);
> however, \varphi_*i* is a subset of \varphi_*j *(since all the true
> sentences in the language {0,1,*+*,*<*} are provable in PA).
> Thus *D* is not RE (neither is *D**).
> (*III*) Unfortunately, the proposed answer by ​Noah Schweber  does not
> work:
> (i) if *n* is in P then S_P(*n*)=T + {S*k*+S*k*=0 | *k* in *N*} (*n*
> never leaves P) but for any *k*' not in the Halting Problem we have T|--S
> *k*'+S*k*'=1; so S_P(*n*) is *in*consistent.
> (ii) if *n* is not in P then S_P(*n*)=T + {S*k*+S*k*=0 | *k*<*l*} for
> some *l* (the stage in which *n* leaves P); but if some small *k*' is not
> in the Halting Problem (we may also assume that 0 is not in the Halting
> Problem) then T|--S*k*'+S*k*'=1 which makes S_P(*n*) *in*consistent
> again.
> Whence, for cofinitely many *n*'s we have that R_P(*n*) is *in*consistent
> (and so decidable?) thus the biconditional "*n*\in P *<==>* R_P(*n*) is
> decidable" cannot hold (the co-RE [but non-RE] set P can be neither
> finite nor cofinite).
> Overall, this can be a good exercise in the computability theory and
> mathematical logic course.
>
>
> On Thu, Mar 2, 2017 at 2:08 AM, Noah Schweber <schweber at berkeley.edu>
> wrote:
>
>> 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
>>>
>>>
>>
>> _______________________________________________
>> FOM mailing list
>> FOM at cs.nyu.edu
>> http://www.cs.nyu.edu/mailman/listinfo/fom
>>
>>
>
>
> --
> Saeed Salehi
> -------------------------------
> http://SaeedSalehi.ir/
> -------------------------------
>
> _______________________________________________
> 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/20170304/66885202/attachment-0001.html>