Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some correct $\forall$-rudimentary sentence.

I have the following facts:

  1. Every recursive function is representable in Q (and by an $\exists$-rudimentary formula).
  2. Every recursive relation is definable in Q (and by an $\exists$-rudimentary formula).

If $T$ is a consistent, axiomatizable theory containing Q:

  1. Every set semi-definable in $T$ is semirecursive.
  2. Every set definable in $T$ is recursive.
  3. Every total function representable in $T$ is recursive.

Are there any examples of semirecursive sets where this structure holds? Or must their existence be proven mathematically?

  • $\begingroup$ Could you state the definition of a $\forall$_rudimentary sentence? $\endgroup$ Apr 13, 2014 at 12:51
  • $\begingroup$ @CarlMummert A rudimentary formula is one built from atomic formulas using only negation, conjucnction, disjunction and bounded quantificiations $\forall x < t$ and $\exists x < t$, where $t$ is any term of the language. By $\exists$-rudimentary, it just means a formula of the form $\exists x F$ where $F$ is rudimentary, and the same for $\forall$. $\endgroup$ Apr 13, 2014 at 19:26

1 Answer 1


There are certainly many examples of sets of natural numbers that are semirecursive but not recursive.

One famous example begins with an enumeration $f_i$ of all the partial recursive functions. Let $A = \{ j : \text{for some $n$, } f_j(n) = 0\}$. That set is easily shown to be semirecursive, but a diagonalization argument shows that it is not recursive.

Another example is related to the halting problem: $B = \{ j : f_j(0) \text{ is defined} \}$. A similar diagonalization argument shows that this set is not recursive, but it is easily shown to be semirecursive.

The phenomenon of sets that are semirecursive but not recursive spreads throughout all of mathematical logic.

For example, the set of (codes of) formulas of the language of Peano Arithmetic that are provable in Peano Arithmetic. This set is semirecursive (search all proofs for a proof of a particular theorem) but, by the incompleteness theorems, it cannot be recursive.

Similarly, we can take the set of (codes of) first order sentences, in a language with one binary function symbol, that are logically valid. This set is semirecursive but not recursive. This is a famous theorem of Trahktenbot about undecidable theories. Many other undecidable theories are known.

For one more example, the set of (codes of) multivariate polynomials over the integers that have at least one root is semidecidable but not decidable - this is the resolution of Hilbert's 10th problem due to Matiyasevich, Davis, Putnam, and Robinson.

Here is the rest of the idea behind the problem. Let $A$ be a semirecursive set that is not recursive.

  1. $A$ is definable by a $\Sigma^0_1$ formula $h$, i.e. a $\Sigma$-rudimentary formula. So we have that, for all $k$, $h(k) \leftrightarrow k \in A$. The complement of $h$ is a $\Pi^0_1$ formula, i.e., a $\forall$-rudimentary formula.

  2. A particular property of $Q$ and stronger theories is that $Q$ is proves every true (i.e. correct) $\Sigma^0_1$ sentence. In particular, for each $k$ such that $k \in A$, we have that $Q$ proves $h(k)$.

  3. Also, because the axioms of $Q$ are all true (i.e. correct), we have that for each $k$, if $Q$ proves $h(k)$ then $k \in A$, and if $Q$ proves $\lnot h(k)$ then $k \not \in A$

  4. If it were also the case that, for all $k \not \in A$, $Q$ proves $\lnot h(k)$, then $A$ would be recursive. The decision procedure would be: given $k$, search for a proof in $Q$ of $h(k)$ or $\lnot h(k)$. Then $k \in A$ or $k \not \in A$, accordingly, from (3).

  5. Thus there is some true $\forall$-rudimentary sentence, which is of the form $\lnot h(k)$ for some $k$, which $Q$ does not prove.

  • $\begingroup$ How do you know that $A$ is definable by a $\exists$-rudimentary formula? I'm not sure how you're making this deduction since $A$ is semirecursive, but not recursive. Explanation might help - this is in reference to (1) at the bottom of your post. $\endgroup$
    – afedder
    Apr 18, 2014 at 17:37
  • 1
    $\begingroup$ I see the leap for a recursive set, but not for a semirecursive set...the standard theorem would be for a recursive set, not for a semirecursive set. $\endgroup$
    – afedder
    Apr 18, 2014 at 18:00
  • 1
    $\begingroup$ @Doubt In Carl's (1), "Definable" means arithmetically definable, which is not at all the same thing as "definable in $Q$". $\endgroup$ Jun 5, 2019 at 0:24
  • 1
    $\begingroup$ @Doubt Other way around. Definable in Q is much stronger. It implies (actually is equivalent to) recursive, whereas non-recursive sets (even non-semi-recursive sets) can be arithmetically definable. $\endgroup$ Jun 5, 2019 at 0:44
  • 1
    $\begingroup$ @Doubt The theory of $\mathbb N$ (i.e. all true first order statements about $\mathbb N$) is much stronger than Q, which can't even prove $\forall x, y (x+y=y+x).$ So it can define way more sets. Despite its weakness even amongst axiomatizable theories, $Q$ can define all recursive sets, which is the most any consistent axiomatizable theory could possibly define. (So, e.g. the much stronger PA, for all its extra strength, can't define any new sets.) The theory of $\mathbb N$ is of course not axiomatizable, and as such, it can define a much larger range of sets than just the recursive ones. $\endgroup$ Jun 5, 2019 at 0:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .