Showing that a certain recursive set cannot exist?

Question

I'm having a lot of trouble with problem 17.2 of Computability and Logic (Boolos, Burgess, Jeffrey). Here's the problem:

Let $T$ be a consistent, axiomatizable theory (in the language of arithmetic) extending $\textbf{Q}$ (the minimal theory of arithmetic). Consider the set $P^{yes}$ of (code numbers of) formulas that are provable in $T$, and the set $P^{no}$ of (code numbers of) formulas that are disprovable in $T$. Show that there is no recursive set $R$ such that $P^{yes}$ is a subset of $R$ while no element of $R$ is an element of $P^{no}$.

Here are a few things I've tried so far (that have not worked out yet):

• Attempt to show that $T$ is recursive (which is a contradiction), i.e. for a given sentence $A$, consider whether $A$ is in $T$ for each of the following cases:
  • $A \not\in R$ (then $A$ is not in $R$)
  • $A \in R$ and $~A \in R$ (then $A$ is not in $R$)
  • $A \in R$ and $~A \not\in R$ (I got stuck on this case)
• Attempt to use the diagonal lemma to construct a sentence $G$ that can neither be in $R$ or not in $R$ (I couldn't derive a contradiction for the case where $G$ is in $R$)
• Attempt to show that the Rosser sentence can be either proved or disproved in $T$ (which is a contradiction)--I just didn't get very far with this

Any hints would be greatly appreciated.

Answer 1

Thanks for the hint Asaf!

Note that $\textbf{Q}$ represents every recursive set. Suppose $R$ is recursive, and let $\phi(x)$ be the formula that represents $R$. By the diagonal lemma, we can find a sentence $G$ such that $T \vdash G \leftrightarrow {\sim}\phi(\textbf{g})$ (where $\textbf{g}$ is the code for $G$). Furthermore, we can find an $\exists$-rudimentary sentence $G^*$ that is logically equivalent to $G$.

Suppose $G^*$ is true in the standard interpretation; then since $T$ extends $\textbf{Q}$, we have $T \vdash G^*$, which implies $T\vdash G$, which implies $T \vdash{\sim}\phi(\textbf{g})$, which implies $G \notin R$. But this contradicts that $T \vdash G$, because $R$ was defined to contain every sentence provable in $T$.

Otherwise, suppose $G^*$ is not true in the standard interpretation; then $T \vdash{\sim}G^*$, which implies $T \vdash{\sim}G$, which implies $T \vdash \phi(\textbf{g})$, i.e. $G \in R$. But this contradicts that $T \vdash{\sim}G$, because $R$ does not contain any sentences disprovable in $T$.

Since $G^*$ must be either true or not true in the standard interpretation, and both possibilities lead to a contradiction, we conclude that $R$ cannot be recursive.

Answer 2

I think this works. Basically, the existence of $R$ would let you build a recursive complete extension of $T$.

Assume $R$ is recursive with the given property.

Let $P_0,P_1,\dots$ be an effective enumeration of all statements in the theory.

We will define recursively an additional set of axioms, $A_i$, that makes the theory complete.

Define $F_{n}=(A_0\lor \dots A_{n-1})\implies P_{n}$. ($F_0=P_0$.) Then if $F_{n}\in R$ define $A_{n}=P_{n}$ and otherwise define $A_{n}=\lnot P_{n}$.

Claim: The set $A_0,A_1,\dots$ is a recursive set of statements, and they are consistent inside $T$.

Proof: It is recursive because we can walk through the $P_i$ and check whether $P_n$ or $\lnot P_n$ gets added to the axioms.

If inconsistent, then let $n$ be the smallest so that $A_n$ is inconsistent with $A_0,\dots,A_{n-1}$.

If $F_n\in R$, then $A_n=P_n$ and we know that $F_n=(A_0\land\cdots\land A_{n-1})\implies A_n$ is not disprovable, since it is in $R$. So $A_n$ would consistent with the previous axioms.

If $F_n\notin R$, then if we could get a contradiction from $A_0,\dots,A_{n-1},\lnot P_n$, you could prove $(A_0\land\cdots\land A_{n-1})\implies P_n$, which would mean $F_n\in P^{yes}\subseteq R$. So $A_n=\lnot P_n$ is consistent with the previous $A_i$.

Claim: Adding the $A_i$ as axioms to $T$ gives a complete theory.

Proof: Given any $P$, either $P$ or $\lnot P$ ends up an axiom.

Answer 3

Thomas Andrews posted a proof that uses the fact that $T$ has no computable, complete, consistent extension. Here is a different method that goes through some elementary recursion theory. Let $\phi_e$ be the standard numbering of the partial computable functions.

First, we will verify that the sets $A = \{e : \phi_e(0) \downarrow = 0\}$ and $B = \{ e : \phi_e(0) \downarrow=1\}$ are recursively inseparable. These sets are easier to work with because they don't refer to formal theories. Suppose that $C$ is any computable set. We want to prove that either $A \not \subseteq C$ or $B \cap C \not = \emptyset$. Using Kleene's recursion theorem, there is an $e$ such that $\phi_e(0) = 1$ if $e \in C$ and $\phi_e(0) = 0$ if $e \not \in C$. Thus, if $e \in C$ then $C \cap B \not = \emptyset$, and if $ e \not \in C$ then $A \not \subseteq C$. This is what we wanted to prove.

Note that $Q$, and thus also any extension, proves every true statement of the form $$H(e,n,k) \equiv \phi_e(n) \downarrow = k$$ and also proves $H(e,n,k) \to \lnot H(e,n,k')$ whenever $k \not = k'$. This is the only fact about $Q$ we will need.

Suppose that $T$ is an extension of $Q$ and let $$ A' = \{ \theta : T \vdash \theta\} \\ B' = \{ \theta: T \vdash \lnot \theta\} $$ Assume for a contradiction that $C'$ is a computable separating set for $A'$ and $B'$. Note that if $\phi_e(0) \downarrow = 0$ then $H(e,0,0) \in A' \subseteq C'$, and if $\phi_e(0)\downarrow = 1$ then $H(e,0,0) \in B'$ and hence $H(e,0,0) \not \in C'$. Thus $C = \{ e : H(e,0,0) \in C'\}$ is a computable separating set for $A$ and $B$, which is impossible.

Note that there is no need to assume $T$ is computable, just that it extends $Q$. But $A'$ and $B'$ may not be c.e. unless $T$ is computable.