Logic - Is it possbile that two formulas represent the same set in some theory T, but they are not equivalent?

Question

I am working on exercises from logic lectures. Here's one question which confuses me:

Suppose that a formula $\varphi(x)$ represents the set $A$ in $T$, where $T$ is a true theory. Also suppose that $T \models \theta$, where $\theta$ is true but unprovable in $T$. (Existence of $\theta$ follows from 1st incompleteness theorem).
Let $\varphi'(x) := \varphi(x) \wedge \theta$, show that $\varphi'(x)$ arithmatically defines $A$, and that, if $A \neq \emptyset$, $\varphi(x)$ and $\varphi'(x)$ are not equivalent in T.

The professor has noted in textbooks that some terms may vary. So, I'll just write down the definition for representability and arithmatical definability to avoid confusion:

(Representable) The set $A \subseteq \mathbb{N}$ is said to be represented by formula $\varphi(x)$, iff:
(a) $a \in A$ implies $T \vdash \varphi(\textbf{a})$
(b) $a \not\in A$ implies $T \vdash \neg\varphi(\textbf{a})$
where $\textbf{a}$ stands for the encoding of $a$ in the language of $T$.

(Arithmatically Definable) The set $A$ is said to be arithmatically defined by formula $\varphi(x)$, iff:
$a \in A$ iff. $\varphi(\textbf{a})$ is true for all $a$.

With these definitions, the first part of the question is easy (show $\varphi'(x)$ arithmatically defines $A$), but the second part really confuses me. The second part shows that whenever $A$ is not empty, the two formulas are not equivalent, which I think is to show that:

$T \not\models \forall x\ \varphi(x) \leftrightarrow \varphi'(x) $

But take $A = \{0\}$, $\varphi(x) := x = 0$, and $T = PA$ for example. $\varphi(x)$ is true and can be proved from $PA$ if and only if $x = 0$, so it represents $A$ by definition. Then following the exersice, we need to show:

$T \not\models \forall x\ x = 0 \leftrightarrow x = 0 \wedge \theta$

However, since $\theta$ is provable from some true theory, by soundness, $\theta$ is also a truth in $T$. So, I am wondering how could $\forall x\ x = 0 \leftrightarrow x = 0 \wedge \theta$ not be a truth in $T$? Because in our example, if $x = 0$, the both sides are true, and if $x \neq 0$, the both sides are false.

It really confuses me what am I doing wrong here?

Answer 1

I find this question interesting and I think there are some points in your assumptions that you need to clarify:

• You suppose that $T\models\theta$ while $T\not\vdash\theta$ at the first place, but it seems not reasonable: given $T\models\theta$, by compactness theorem, there is some finite subset $T'$ such that $\models\bigwedge T'\to\theta$, which entails $T\vdash\theta$. So I think we can drop the assumption $T\models\theta$, but just keep that $\theta$ is true (maybe more precisely, $\theta$ is true in the standard arithmetic model $\mathcal{N}$).

• When giving the definition of arithmetically definability, you may also clarify what is the meaning of the expression '$\varphi(\mathbf{a})$ is true'. I guess it should be $\mathcal{N}\models\varphi(\mathbf{a})$, where $\mathcal{N}$ is the standard arithmetic model.

I think things will be clearer if the concepts above are clarified :)

Btw, the first incompleteness theorem says that: every consistent axiomatizable extension $T$ of $PA$ is incomplete. In this statement, $T$ is claimed to be an incomplete theory, i.e., there is some sentence $\theta$ such that $T\not\vdash\theta$ and $T\not\vdash\neg\theta$. But you still see that for all sentence $\alpha$, $T\models\alpha$ implies $T\vdash\alpha$.

Hope this will help :)