What is the difference between representability and definability?

I am confused about the difference between the representability of a set in a theory and the definability of a set in a theory. Part of any given introduction to the incompleteness theorems goes over the definition of a set being strongly/weakly represented in a theory, and shows that for consistent recursively axiomizable extensions of Robinson Arithmetic, the only sets that are strongly representable are the recursive sets and the only sets that are weakly representable are the recursively enumerable sets, so by Post's theorem they're the $$\Delta^0_1$$ and $$\Sigma^0_1$$ sets, respectively.

The definition that I have seen for weakly representing a set is that a theory $$T$$ weakly represents a set $$S$$ iff for some formula $$A(x)$$ in the language of the theory, if $$n \in S$$, then $$T \vdash A(n)$$.

To me, that seems like it just says that $$S$$ needs to be definable by some formula in the language of $$T$$ and $$T$$ needs to prove $$A$$ holds of each $$n \in S$$.

My issue is that given what I've stated above, it seems to me to imply that a theory can not prove anything other than $$\Delta^0_1$$ and $$\Sigma^0_1$$ statements. But clearly that isn't true, because there are $$\Pi^0_1$$ sentences easily provable in PA, for example.

So clearly I am not understanding something. Why can PA prove some given $$\Sigma^0_3$$ sentence but it cannot represent the $$\Sigma^0_3$$ set that the sentence defines? How can ZFC talk about $$\Pi^2_3$$ sets if it can't represent them? More to my actual point, what part of the definitions am I not understanding?

A sentence doesn't define a set. A formula defines a set.

I assume by "define" you mean define arithmetically. In other words some one variable formula $$\phi(x)$$ in the language of arithmetic defines the set $$\{x\in\mathbb N: \mathcal N\models \phi(x)\}$$ where $$\mathcal N$$ is the standard interpretation of arithmetic in the natural numbers.

(Sometimes people also talk of defining in a particular arithmetic theory, but that is more akin to representing, depending on the exact definitions people use.)

If we want this formula to weakly represent this same set in some arithmetical theory $$T$$, then, according to the definition you gave, we need to have, for every $$n\in S,$$ $$T\vdash \phi(\mathbf n).$$ This is not just one sentence $$T$$ needs to prove, but infinitely many (provided $$S$$ is infinite).

• Depending on the author, "$Σ_n$-formula" may be closed under equivalence, and similarly for $Π_n$ and $Δ_n$. Commented Dec 19, 2019 at 12:22
• @user21820 True. This comment was mostly intended to address OP talking about “$\Delta_1$ sentences” which I think reflects some misunderstanding here, since even if technically making sense, this concept generally isn’t very useful, and is completely trivialized when the natural notion of equivalence is equivalence in a complete theory, as it is here. Commented Dec 19, 2019 at 15:59
• I don't mean to be trying to find any fault, but I'm not seeing how it is trivialized because the question is about extensions of Q that are not stated to be complete. Am I misunderstanding you? In the literature, we sometimes see such statements like "recursive sets are $Δ_1$", for the same reason, referring to the equivalence rather than the syntactic form. I'm not sure which definition I myself prefer. =) Commented Dec 19, 2019 at 16:45
• @user21820 My point is that when we say “recursive sets are $\Delta_1$“, the operative notion of equivalence is arithmetical equivalence, not logical equivalence or equivalence in some effective theory. Commented Dec 19, 2019 at 17:16
• Ah yes indeed usually we mean equivalence in the standard model, and I see you object to calling a sentence "$Δ_1$" because it is a sentence. So can I guess that you won't object to calling a formula "$Δ_1$"? Commented Dec 19, 2019 at 17:25

It's been a long time since this question has been asked, but here is an answer. I am assuming that op knows about the completeness theorem: $$T\vdash \phi$$ iff $$T\models \phi$$.

Notice though that definability is on a model to model basis. Example: $$A=\{x:\mathcal{M}\models\psi(x)\}$$ tells us that $$\psi$$ defines $$A$$ is this particular $$\mathcal{M}\models T$$.

On the other hand representability is for all models: we say that $$T$$ represents $$A$$ if $$x\in A\iff T\vdash\psi(x)$$. We could use $$T\models\psi(x)$$ but as you can see, this means that this should be true in every models of $$T$$.

• Another way to say this is that, while the set $A$ is not definable, the decision about whether an element $x$ is in $A$ depends on the theory and not on a particular model of the theory. Commented Nov 14, 2022 at 16:31