MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\mathcal{L}$ be some first-order language, and $T$ be a consistent set of formulas of $\mathcal{L}$ which is not recursively enumerable.

Under what conditions will there be $T'\supset T$ such that $T'$ is consistent and recursively enumerable?

share|cite|improve this question
Are there any specific kinds of conditions you seek? One condition that gives more than you're after: if $T$ is co-r.e. then it has an extension which is not only consistent and r.e., but also complete (hence decidable too). – Ed Dean Jan 17 '11 at 16:58

I'm not sure what kind of conditions you seek, but let me simply point out that one can build a decidable theory $T'$ having continuum many inequivalent subtheories $T$. Since only countably many of these subtheories can be decidable (or even c.e., co-c.e. or even arithmetic, etc.), we would thereby produce continuum many theories with no nice computability features, but which have a decidable extension.

For an example, consider the language having infinitely many constant symbols $c_n$, and let $T'$ be the theory asserting $c_n\neq c_m$ for distinct $n$ and $m$. This is a completely trivial, decidable theory, but every partition of the constant symbols gives rise to a distinct subtheory $T$, which asserts merely that constants in different classes of the partition are distinct. Since there are continuum many partitions, we have continuum many inequivalent subtheories of $T'$, most of which are therefore not c.e.

Similar examples can be made whenever a theory $T'$ asserts the truth of infinitely many logically independent statements, since there would be continuum many subtheories asserting any particular subset of those statements. Most of these subtheories will not be c.e., since there are only countably many c.e. theories, even when $T'$ is decidable.

share|cite|improve this answer
There is an accompanying question that ought to be easier: For any r.e. set there is a theory of the same degree (Feferman). Can we ensure that if $A$ is an r.e. consistent set of sentences, then there is a theory $T'$ extending $A$ and of the same degree? – Andrés E. Caicedo Jan 17 '11 at 23:44
I guess you are requiring theories to be closed under consequence, and in this case the answer seems to be negative, since we can find a c.e. non-computable enumeration of axioms that that axiomatize a complete decidable theory, just by taking complex combinations $\varphi\wedge\cdots\wedge\varphi$ of the axioms so as to code a c.e. non-computable set. – Joel David Hamkins Jan 17 '11 at 23:53
Oh, of course! Too bad. – Andrés E. Caicedo Jan 18 '11 at 0:24

Let $A = T \cup R$ where $R$ is any set of refutable statements from $T$ (i.e., $T \vdash \lnot \varphi$ for all $\varphi$ in $R$). A simple necessary condition for such a $T^{\prime}$ to exist is that $A$ is not recursively (computably) enumerable. If it were, then given a r.e. (c.e.) $T^{\prime} \supseteq T$, we could recursively enumerate all statements of $T$ by listing only the ones in $T^{\prime}$ that also appear in $A$ (i.e., $T = T^{\prime} \cap A$). The reason for this equality is that $T^{\prime}$ is an extension of $T$ so it must contain all the statements in $T$ but then it cannot include any in $R$ by its consistency.

Now let $I$ be the set of all statements that are independent of $T$ (i.e. all $\varphi$ such that $T \nvdash \varphi$ and $T \nvdash \lnot \varphi$). In the case that $T$ is deductively closed meaning $T \vdash \varphi$ implies that $\varphi \in T$, a corollary of the above result is that $I$ cannot be the complement of a recursively enumerable set. This is the instance of letting $R$ be the set of all statements refutable from $T$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.