[FOM] Fwd: Are the Decidable Theories R.E.?
Saeed Salehi
saesal at gmail.com
Sun Mar 5 02:11:04 EST 2017
Yes (my mistake); the answer of Prof. Noah Schweber works (by using an
effective padding lemma: for any *i*,*l* there is some *j>l* such that
\varphi_*i* = \varphi_*j*). Then, as before, (i) if *n* *is* in P then
S_P(*n*)=T + {S*k*+S*k*=0 | *k* \in *N*} (*n* never leaves P) *is*
decidable; and (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) is *un*decidable
(since, by the effective padding lemma, for any *l* the intersection of the
Halting Problem with the set {*m* | *m**>**l*} is still undecidable).
I forgot to mention the complexity of *D* and *D** in my previous message:
For *D*={*n* | *W*_{*n*'} is recursive} and *D**={*n* | *W*_*n* *=* *W*_{
*n*'} is recursive} we can write
*n* \in *D* *<==>* \exists *m* \forall *x* ([*x*\in *W*_{*n*'} & \varphi_*m*
(*x*)=1] *\/* [*x*\not\in *W*_{*n*'} & \varphi_*m*(*x*)=0] ) and *n* \in *D**
*<==>** n* \in *D* & *W*_*n* *=* *W*_{*n*'}. So, *D* and *D** are in \Sigma_
3. Now that we know *D*,*D** \not \in \Sigma_1, I think one can also show
that *D*,*D** are not \Pi_1,\Sigma_2, \Pi_2 or \Pi_3 either; I even believe
that *D*,*D** are \Sigma_3--complete (good exercises---if true).
On Sat, Mar 4, 2017 at 8:41 PM, Noah Schweber <schweber at berkeley.edu> wrote:
> 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/boo
>> k/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
>>
>>
>
> _______________________________________________
> 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/20170305/687e1f2f/attachment-0001.html>
More information about the FOM
mailing list