[FOM] Are the Decidable Theories R.E.?
Saeed Salehi
saesal at gmail.com
Sat Mar 4 06:53:23 EST 2017
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/
-------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170304/410c1b48/attachment-0001.html>
More information about the FOM
mailing list