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

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?

• I think there is some confusion here about the meaning of the term "true". If a theory $T$ cannot prove a sentence $\theta$, then either (a) it can prove $\lnot\theta$ or (b) it is consistent with both $\theta$ and $\lnot\theta$, in which case, by the compactness theorem it has models in which $\theta$ holds and models in which $\theta$ does not hold. In case (a) and in case (b), $\theta$ does not hold in some models and so is not "true". Mar 27 at 19:12
• @RobArthan Thank you for your comment. But I am sorry that I didn't quite catch up with the part of compactness theorem, could you explain a bit more about how the conclusion is derived from compactness theorem? And if we restrict the assumption to models where $\theta$ is true, could we still solve the question?
– Shuj
Mar 27 at 19:40
• Sorry, I made a typo: I should have written "completeness theorem". As for your second point: $\theta$ is true means that $\theta$ holds in every model, implying by completeness that it is provable in $T$. Mar 27 at 19:50
• I see. But the question didn't guarantee the completeness of theory T, so we might choose some incomplete theory like Peano Arithmetic, where some thing true within PA is not derivable from PA itself.
– Shuj
Mar 27 at 20:00
• I don't think you have a clear idea of what you mean by "true within PA". (And I think the quotations in your question are not very good in their use of terminology.) "Truth" is a semantic concept (it's about models), while "PA" is a syntactic concept (it's about provability) - so "truth in PA" isn't a well-defined notion. If by "true in PA" you mean true in every model of the axiom system PA, then every sentence that is "true in PA" is provable in PA (by the completeness theorem). Mar 27 at 21:41

• 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.
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$$.