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

[Richard Heck]

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170301/f638f746/attachment.html>