# Thread: Enderton 3.5 Problem 2

1. ## Enderton 3.5 Problem 2

Let $A$ be a recursive set of sentences in a recursively numbered language with $\bold{0}$ and $\bold{S}$. Assume that every recursive relation is representable in the theory $\text{Cn }A$. Further assume that $A$ is $\omega$-consistent; i.e., there is no formula $\phi$ such that $A \vdash \exists x \phi(x)$ and for all $a \in \mathbb{N}$, $A \vdash \neg \phi(\bold{S}^a\bold{0})$. Construct a sentence $\sigma$ indirectly asserting that it is not a theorem of $A$, and show that neither $A \vdash \sigma$ nor $A \vdash \neg \sigma$.

=====================
(Suggestion: See Section 3.0.)
Remark: This is a version of the incompleteness theorem that is closer to Gödel's original 1931 argument. Note that there is no requirement that the axioms $A$ be $true$ in $N=(\mathbb{N}; 0, S, <, +, \cdot, E)$. Nor is it required that $A$ include $A_E$; the fixed point argument can still be applied.
======================

If $\sigma$ says that it is not a theorem of $A$, then it is clear that $A \not\vdash \sigma$. How do I also show $A \not\vdash \neg\sigma$?

Another question is why $\omega$-consistent is considered here?

Thanks.

2. ## Re: Enderton 3.5 Problem 2

Could you check if my following attempt is O.K ?

Since every recursive relation is representable in the theory $\text{Cn }A$ by assumption, there is a formula $\rho$ represents $R$ corresponding to $A$ in the theory $\text{Cn }A$ (Enderton 2nd edition, pp 185).

Let $q$ be the Gödel number of $\forall \neg \rho(v_1, v_1, v_3)$.
Let $\sigma$ be $\forall v_3 \neg \rho(S^q0}, S^q0, v_3)$.

Then, $\sigma$ says that no number is the value of $g$ (Enderton 2nd edition, pp 185) at a deduction of $\sigma$.

If $A \vdash \sigma$, there is a contradiction explained in the textbook (Enderton 2nd edition, pp 185).

Therefore, we have $A \not \vdash \sigma$.

Now, we need to show that $A \not \vdash \neg \sigma$.
Suppose to the contrary that $A \vdash \neg \sigma$.
Then, $A \vdash \exists v_3 \rho(S^q0}, S^q0, v_3)$.

By $\omega$-consistency, it cannot be $A \vdash \neg \rho(S^q0}, S^q0, S^a0)$ for all $a \in \mathbb{N}$. It follows that it cannot be $ \notin R$ for every $k$. Now, $\not\models_N \forall v_3 \neg \rho (S^q0, S^q0, v_3)$. It means $\sigma$ is false in $N$, contradicting that $\sigma$ is true in $N$ (Enderton 2nd edition, pp 185).

Thus $A \not \vdash \neg \sigma$.

3. ## Re: Enderton 3.5 Problem 2

Originally Posted by logics
Since every recursive relation is representable in the theory $\text{Cn }A$ by assumption, there is a formula $\rho$ represents $R$ corresponding to $A$ in the theory $\text{Cn }A$ (Enderton 2nd edition, pp 185).
Without the book, it is unclear what exactly the relation " $R$ corresponding to $A$ in the theory $\text{Cn }A$" is. (Fortunately, I was able to get the book.)

Originally Posted by logics
Now, $\not\models_N \forall v_3 \neg \rho (S^q0, S^q0, v_3)$. It means $\sigma$ is false in $N$, contradicting that $\sigma$ is true in $N$ (Enderton 2nd edition, pp 185).
Where is the assumption that $\sigma$ is true in $N$? The assumption is that $A \vdash \neg \sigma$. Even if A is true in the natural model, that would mean that $\sigma$ is false. However, the hint says that A does not have to be true. In fact, the language of A may include, along with 0 and S, other functional and predicate symbols, and it may not be clear how to interpret them.

I would also prefer to assume the fixpoint theorem for A as the hint seems to imply. The first proof in Section 3.0 of the book (the self-reference approach) seems to incorporate the proof of the fixpoint property, which is quite technical and nonintuitive. It may not be hard to finish your current approach, but I would start as follows. Let us write $\bar{n}$ for $S^n0$. The relation R(x, y) saying that x is a derivation of y is recursive, therefore, representable in A by some formula $\rho$. By the fixpoint property, there exists a formula $\sigma$ such that

$A\vdash\sigma\leftrightarrow\neg\exists x\,\rho(x,\overline{\sharp\sigma})$ (*)

Suppose $A\vdash\sigma$. This means that $R(n,\sharp\sigma)$ holds, so...

Suppose that $A\vdash\neg\sigma$. Then $A\vdash\exists x\,\rho(x,\overline{\sharp\sigma})$ by (*), so, as you wrote, by $\omega$-consistency we have $A\not\vdash\neg\rho(\bar{n},\overline{\sharp\sigma })$ for some n. Therefore, ...

4. ## Re: Enderton 3.5 Problem 2

Originally Posted by emakarov
Suppose that $A\vdash\neg\sigma$. Then $A\vdash\exists x\,\rho(x,\overline{\sharp\sigma})$ by (*), so, as you wrote, by $\omega$-consistency we have $A\not\vdash\neg\rho(\bar{n},\overline{\sharp\sigma })$ for some n. Therefore, ...
I am trying to conclude from the above. Is the following O.K?

Suppose that $A\vdash\neg\sigma$. Then, $\sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\text{Cn }A$.
It follows that $A \vdash \neg \exists x \rho(x, \overline{\sharp \sigma})$. Then $A \vdash \sigma$ by (*). It implies that $\sigma \in \text{Cn }A$, contradiction.

Thus $A\not\vdash\neg\sigma$.

5. ## Re: Enderton 3.5 Problem 2

Originally Posted by logics
Suppose that $A\vdash\neg\sigma$. Then, $\sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\text{Cn }A$.
For which exactly formula do you use the fact that it is numeralwise determined and how does it help show that $A\not\vdash\sigma$? I would say that if $A\vdash\sigma$, then the assumption $A\vdash\neg\sigma$ makes A inconsistent, but ω-consistency is stronger than simple consistency.

Originally Posted by logics
It follows that $A \vdash \neg \exists x \rho(x, \overline{\sharp \sigma})$.
Could you explain how it follows? And where do you use ω-consistency?

Continuing your proof, $A\not\vdash\sigma$ means that no number n is the code of a derivation of $\sigma$, i.e., $R(n,\sharp\sigma)$ is false for all n. Since $\rho$ represents R, we have $A\vdash\neg\rho(\bar{n},\overline{\sharp\sigma})$ for all n. Now use ω-consistency and (*).

6. ## Re: Enderton 3.5 Problem 2

Originally Posted by emakarov
For which exactly formula do you use the fact that it is numeralwise determined and how does it help show that $A\not\vdash\sigma$?
I used Theorem 33E and definition in page 207 to denote that either $\sigma \in \text{Cn A}$ or $\sigma \notin \text{Cn A}$. Is this wrong?

7. ## Re: Enderton 3.5 Problem 2

Originally Posted by logics
I used Theorem 33E and definition in page 207 to denote that either $\sigma \in \text{Cn A}$ or $\sigma \notin \text{Cn A}$.
Of course, for any set S and object x at all, either $x\in S$ or $x\notin S$. I am still not sure how you concluded $\sigma\notin\mathop{\mathrm{Cn}}A$ from $\neg\sigma\in\mathop{\mathrm{Cn}}A$ in the following text.

Originally Posted by logics
Suppose that $A\vdash\neg\sigma$. Then, $\sigma \notin \text{Cn A}$ by the assumption that every recursive relation is representable (i.e., numeralwise determined) in the theory $\text{Cn }A$.
Which formula and relation did you use with Theorem 33E and definition in page 207?

For any theory A and a formula $\sigma$, there are four statements:

(1) $A\vdash\sigma$
(2) $A\not\vdash\neg\sigma$
(3) $A\vdash\neg\sigma$
(4) $A\not\vdash\sigma$

In any case, precisely one of (1) and (4), as well as one of (2) and (3) holds. If A is inconsistent, then A derives everything, i.e., (1) and (3) are true and (2) and (4) are false. If A is consistent, then (1) implies (2) and (3) implies (4), but the converse implications are in general false.

8. ## Re: Enderton 3.5 Problem 2

For any theory A and a formula $\sigma$, there are four statements:

(1) $A\vdash\sigma$
(2) $A\not\vdash\neg\sigma$
(3) $A\vdash\neg\sigma$
(4) $A\not\vdash\sigma$

In any case, precisely one of (1) and (4), as well as one of (2) and (3) holds. If A is inconsistent, then A derives everything, i.e., (1) and (3) are true and (2) and (4) are false. If A is consistent, then (1) implies (2) and (3) implies (4), but the converse implications are in general false.
A is $\omega$-consistent by assumption, so it is consistent.

$A\vdash\sigma\leftrightarrow\neg\exists x\,\rho(x,\overline{\sharp\sigma})$ (*)
What conditions are required to apply the fixed point lemma to A instead of $A_E$?

The below one is my updated proof based on the textbook page 266.

To express $A \vdash \sigma$ for a sentence $\sigma$, we define

$\text{Prb}_A\sigma = \exists v_2 \pi(S^{\sharp\sigma}0, v_2)$,

where $\pi(v_1, v_2)$ numeralwise represents the binary relation (a, d) in $A_E$. (referred to textbook page 206 for the corresponding description including the binary relation).

(Enderton, Page 266)

(*) Whenever $A \vdash \sigma$, then $A_E \vdash \text{Prb}_A\sigma$.

(**) $A_E \vdash (\sigma \leftrightarrow \neg\text{Prb}_A\sigma)$ (by Fixed Point lemma).

Since $A$ itself is a recursively axiomatizable theory,

(***) If $A \vdash \sigma$, then $A_E \vdash \sigma$.

(****) If $A \vdash \neg\sigma$, then $A_E \vdash \neg\sigma$.

Now, suppose $A \vdash \sigma$. Then, $A_E \vdash \sigma$ and $A_E \vdash \text{Prb}_A\sigma$ by (*) and (***). We also have $A_E \vdash \neg\sigma$ by (**), contradicting that $\text{Cn }A_E$ is consistent. Therefore, $A \not\vdash \sigma$.

Suppose $A \vdash \neg\sigma$. Then, $A_E \vdash \neg\sigma$. It follows that $A_E \not\vdash \sigma$ (by consistency of $\text{Cn }A_E$), which implies that $A_E \vdash \neg \text{Prb}_A\sigma$ (by $\omega$-consistency of $A$). Then, $A_E \vdash \sigma$, contradicting that $\text{Cn }A_E$ is consistent. Therefore, $A \not\vdash \neg\sigma$.

9. ## Re: Enderton 3.5 Problem 2

Originally Posted by logics
What conditions are required to apply the fixed point lemma to A instead of $A_E$?
Good question. Hopefully, the fact that every recursive relation is representable is sufficient, but one has to go over the proof of fixpoint lemma and verify it.

Originally Posted by logics
Since $A$ itself is a recursively axiomatizable theory,

(***) If $A \vdash \sigma$, then $A_E \vdash \sigma$.

(****) If $A \vdash \neg\sigma$, then $A_E \vdash \neg\sigma$.
This is not correct because A may have functional and predicate symbols that are outside the language of $A_E$. It may also have additional axioms. If you want to interpret A in $A_E$, you need to resort to encoding. That's why (and also because A is ω-consistent, which we have to use somehow) I suggest assuming the fixpoint lemma for A. Then it is not necessary to consider $A_E$ at all because by assumption A represents every recursive relation. In particular, there exists a formula $\pi$ representing the relation R(d, a) expressing "d is a derivation of a" in A.

The fact that $A\vdash\phi$ implies $A\vdash\mathop{\mbox{Prb}}\phi$ for any formula $\phi$ can be easily adapted from $A_E$ to A. This covers the case when $A\vdash\sigma$.

Originally Posted by logics
Suppose $A \vdash \neg\sigma$. Then, $A_E \vdash \neg\sigma$. It follows that $A_E \not\vdash \sigma$ (by consistency of $\text{Cn }A_E$), which implies that $A_E \vdash \neg \text{Prb}_A\sigma$ (by $\omega$-consistency of $A$).
I don't see how ω-consistency implies that $A_E \vdash \neg \text{Prb}_A\sigma$. At most, it says that $A_E \not\vdash \text{Prb}_A\sigma$. This inference also requires (replacing $A_E$ with A) the assumption that $\pi$ represents R and deserves to be written in more detail. It is sufficient to finish the proof because $A\vdash\neg\sigma$ implies $A\vdash\mathop{\mbox{Prb}}\sigma$ by the fixpoint lemma. Thus, the contradiction in the case when $A \vdash \neg\sigma$ comes from the fact that $A\vdash\phi$ and $A\not\vdash\phi$ for some formula $\phi$, not from $A\vdash\phi$, $A\vdash\neg\phi$ and consistency.