# Thread: Enderton 3.5 Problem 3

1. ## Enderton 3.5 Problem 3

Let $\displaystyle T$ be a theory in a recursively numbered language (with 0 and S). Assume that all recursive subsets of $\displaystyle \mathbb{N}$ are weakly representable in $\displaystyle T$. Show that $\displaystyle \sharp T$ is not recursive. Suggestion: Construct a binary relation $\displaystyle P$ such that any weakly representable subset of $\displaystyle \mathbb{N}$ equals $\displaystyle \{b | <a, b> \in P\}$ for some $\displaystyle a$, and such that $\displaystyle P$ is recursive if $\displaystyle \sharp T$ is.
Consider the set $\displaystyle H=\{b|<b, b> \notin P\}$. See Section 3.0. The argument given there for the "diagonal approach" in the special case $\displaystyle T=\text{Th }N$ can be adapted here.

Remark: This exercise gives a version of the result, "Any sufficient strong theory is undecidable.".

================================================
Could you check if my following sketch of proof is O.K?

By assumption, there is a formula $\displaystyle \rho$ that weakly represents $\displaystyle P$ in $\displaystyle T$ such that
$\displaystyle <a, b> \in P \leftrightarrow \rho(S^a0, S^b0) \in T$ for all $\displaystyle a, b$ in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$ (referred to Enderton pp 241).
$\displaystyle P$ is recursive iff $\displaystyle T$ (including $\displaystyle \sharp T$) is recursive.

Consider the set $\displaystyle P_a = \{b | <a, b> \in P\}$ of P. If P is recursive, then P is definable in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. Then any definable set of natural numbers is somewhere on the list $\displaystyle P_1, P_2, \ldots$ (Enderton pp 186). However, H is not definable in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. (Enderton pp 186). Contradiction. Therefore, P is not recursive, so is $\displaystyle \sharp T$.

2. ## Re: Enderton 3.5 Problem 3

Originally Posted by logics
By assumption, there is a formula $\displaystyle \rho$ that weakly represents $\displaystyle P$ in $\displaystyle T$ such that $\displaystyle <a, b> \in P \leftrightarrow \rho(S^a0, S^b0) \in T$ for all $\displaystyle a, b$ in $\displaystyle N=(\mathbb{N}; 0, S, <, +, \cdot, E)$ (referred to Enderton pp 241).
What is P? The hint contains the desired properties of P, not the definition of P. You have to define it first. Second, why is P weakly representable?

3. ## Re: Enderton 3.5 Problem 3

Originally Posted by emakarov
What is P? The hint contains the desired properties of P, not the definition of P. You have to define it first. Second, why is P weakly representable?
P is defined in the textbook page 186 (Please refer to the textbook page 186 for detailed descriptions of the definition).

$\displaystyle <a, b> \in P \leftrightarrow$ $\displaystyle a$ is the Gödel number of a formula $\displaystyle \alpha(v_1)$ (with just $\displaystyle v_1$ free) and $\displaystyle \models_N\alpha(S^b0)$.

By weakly representability and assumption, $\displaystyle <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T$ for all b and for some a (The definition of P_a is in #1 post), where $\displaystyle \rho$ weakly represents $\displaystyle P_a$ in a theory T. Is this true? How do I proceed from here?

Any help will be appreciated.

4. ## Re: Enderton 3.5 Problem 3

Originally Posted by logics
$\displaystyle <a, b> \in P \leftrightarrow$ $\displaystyle a$ is the Gödel number of a formula $\displaystyle \alpha(v_1)$ (with just $\displaystyle v_1$ free) and $\displaystyle \models_N\alpha(S^b0)$.
In this case, P is not recursive because formulas true in $\displaystyle \mathbb{N}$ represent a highly complex set (far more complex than decidable or enumerable sets). Besides, the definition is supposed to depend on T.

P should be $\displaystyle \{\langle a,b\rangle\mid a=\sharp\alpha(x)\text{ and }T\vdash\alpha(S^b0)\}$. Then P is recursive if $\displaystyle \sharp T$ is, in conformance to the hint.

5. ## Re: Enderton 3.5 Problem 3

I am trying to revise my previous attempt to the proof. Could you check if the following is O.K? Except $\displaystyle P$ and $\displaystyle A$, definitions and notations are basically reused from the previous posts.

$\displaystyle <a, b> \in P \leftrightarrow$ $\displaystyle a$ is the Gödel number of a formula $\displaystyle \alpha(v_1)$ (with just $\displaystyle v_1$ free) and $\displaystyle \models_A\alpha(S^b0)$ for $\displaystyle A \in K$, where $\displaystyle K$ is a class of structures for which $\displaystyle T$ is a theory in a recursive numbered language with 0 and S and $\displaystyle T=\{\sigma| \sigma \text{ is true in every member of } K\}$.

By weakly representability and assumption, $\displaystyle <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T$ for all b and for some $\displaystyle a$, where $\displaystyle \rho$ weakly represents $\displaystyle P_a$ in a theory T.

Furthermore, $\displaystyle <b> \in P_a \rightarrow <a, b> \in P$ by definition of $\displaystyle P$ and $\displaystyle P_a$.

Since the choice of $\displaystyle a$ is arbitrary, we have $\displaystyle \rho(S^a0, S^b0) \in T \rightarrow <a, b> \in P$ for all $\displaystyle a$ and $\displaystyle b$. Therefore, if $\displaystyle \sharp T$ is recursive, then $\displaystyle P$ is recursive. However, $\displaystyle P$ is not recursive by (*). Therefore, $\displaystyle \sharp T$ is not recursive.

(*) $\displaystyle P$ is not recursive.

Proof. Any definable (in $\displaystyle A$) set of natural numbers is somewhere on the list $\displaystyle P_1, P_2, \ldots$. However, $\displaystyle H = \{b : <b, b> \notin P\}$ is not definable in $\displaystyle A$. If $\displaystyle P$ is recursive, then $\displaystyle H$ should be definable in $\displaystyle A$. Contradiction. Therefore, P is not recursive.

6. ## Re: Enderton 3.5 Problem 3

A general remark is that the proof should be more precise and contain more details. Parts of it are hard to understand.

Originally Posted by logics
$\displaystyle <a, b> \in P \leftrightarrow$ $\displaystyle a$ is the Gödel number of a formula $\displaystyle \alpha(v_1)$ (with just $\displaystyle v_1$ free) and $\displaystyle \models_A\alpha(S^b0)$ for $\displaystyle A \in K$, where $\displaystyle K$ is a class of structures for which $\displaystyle T$ is a theory in a recursive numbered language with 0 and S and $\displaystyle T=\{\sigma| \sigma \text{ is true in every member of } K\}$.
This is one place that is hard to understand. What is K? Is it Mod T? It seems much simpler to say "... and $\displaystyle T\models\alpha(S^b0)$." In fact, in what follows you need an equivalent condition $\displaystyle T\vdash\alpha(S^b0)$ because weak representability involves provability, not logical consequence. It is not clear why involve model theory and completeness theorem into a problem that is purely about proof theory, i.e., syntax.

Originally Posted by logics
By weakly representability and assumption, $\displaystyle <b> \in P_a \leftrightarrow \rho(S^a0, S^b0) \in T$ for all b and for some $\displaystyle a$, where $\displaystyle \rho$ weakly represents $\displaystyle P_a$ in a theory T.
By weak representability of which relation? To use the assumption that every recursive relation is weakly representable, you need to show that some relation is recursive. Which relation is it?

Originally Posted by logics
Since the choice of $\displaystyle a$ is arbitrary, we have $\displaystyle \rho(S^a0, S^b0) \in T \rightarrow <a, b> \in P$ for all $\displaystyle a$ and $\displaystyle b$. Therefore, if $\displaystyle \sharp T$ is recursive, then $\displaystyle P$ is recursive.
To conclude that P is recursive, you need the implication is both directions: $\displaystyle \rho(S^a0, S^b0) \in T \leftrightarrow \langle a, b\rangle \in P$.

Originally Posted by logics
(*) $\displaystyle P$ is not recursive.

Proof. Any definable (in $\displaystyle A$) set of natural numbers is somewhere on the list $\displaystyle P_1, P_2, \ldots$.
What is A? It seems like K = Mod T and then A is some element of K, but which one?

Originally Posted by logics
However, $\displaystyle H = \{b : <b, b> \notin P\}$ is not definable in $\displaystyle A$.
Why?

As I suggested in post #4, define $\displaystyle P=\{\langle a,b\rangle\mid a=\sharp\alpha(x)\text{ and }T\vdash\alpha(S^b0)\}$. Then for every weakly representable subset G of $\displaystyle \mathbb{N}$ there exists a number $\displaystyle a$ such that $\displaystyle G=P_a$. Indeed, suppose G is represented by some formula $\displaystyle \gamma(x)$, i.e., $\displaystyle b\in G$ iff $\displaystyle T\vdash\gamma(S^b0)$ for all b. Then $\displaystyle G=P_{\sharp\gamma}$.

Moreover, if $\displaystyle \sharp T$ is recursive, then we know whether $\displaystyle T\vdash\alpha(S^b0)$ for each $\displaystyle \alpha$ and $\displaystyle b$, and so P is recursive. Therefore, for each $\displaystyle b$ we know whether $\displaystyle \langle b,b\rangle\in P$, so $\displaystyle H=\{b\mid\langle b,b\rangle\notin P\}$ is recursive. By the assumption that every recursive relation is weakly representable and the fact proven above that every weakly representable relation is a projection of P, there exists an $\displaystyle a$ such that $\displaystyle H=P_a$. Now consider two cases: $\displaystyle a\in H$ and $\displaystyle a\notin H$.

In summary, the idea of the proof is the following. We build a relation P that encodes weak representability, i.e., G is a weakly representable set if G is a projection of P, i.e., $\displaystyle G=P_a$ for some $\displaystyle a$. Then we build a diagonalization of P, i.e., a set H that is different from all projections of P. If we were able to prove that H is weakly representable, we would get a contradiction. We prove that H is weakly representable by showing that P and therefore H are recursive and using the assumption.

7. ## Re: Enderton 3.5 Problem 3

Just a remark. I am used to thinking about theories as given by axioms, but the book defines a theory as a set of formulas containing all its corollaries. Therefore, everywhere above $\displaystyle T\vdash\alpha$ can be replaced by $\displaystyle \alpha\in T$ for all formulas $\displaystyle \alpha$.