5

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?

Nika
  • 727
29ax14
  • 51

2 Answers2

2

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).

spaceisdarkgreen
  • 58,508
  • 1
    Depending on the author, "$Σ_n$-formula" may be closed under equivalence, and similarly for $Π_n$ and $Δ_n$. – user21820 Dec 19 '19 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. – spaceisdarkgreen Dec 19 '19 at 15:59
  • 1
    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. =) – user21820 Dec 19 '19 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. – spaceisdarkgreen Dec 19 '19 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$"? – user21820 Dec 19 '19 at 17:25
  • I haven't gone back through the question to see whether or not I make mistakes between calling something a sentence or a formula, give your answer I'm sure I did, but regardless of that and your point about referring to a sentence which is logically equivalent to a $\Sigma^0_0$ and a $\Pi^0_0$ sentence as a $\Delta^0_1$ sentence, as they're defined in any textbook I've looked at, the rest of your answer hasn't helped me understand the point I'm asking to be addressed. – 29ax14 Dec 19 '19 at 18:24
  • And I'm clearly not talking about completed theories, I expressly stated that I'm talking about "consistent recursively axiomizable extensions of Robinson Arithmetic", and as we all know, consistent recursively axiomizable extensions of Robinson Arithmetic are not complete. – 29ax14 Dec 19 '19 at 18:29
  • @29ax14 Frankly, your confusion runs deeper than the minutiae we’re discussing in the comments here. The point is addressed rather directly in the last paragraph (and the first sentence). There is a big difference between proving some $\Pi_2$ sentence, and proving a set of infinitely many $\Pi_2$ sentences of a prescribed form. And as for the second thing, sure, but the theory of $\mathbb N$ is complete and that’s what the arithmetical hierarchy is with respect to. But this second issue is extremely unimportant compared to the first. – spaceisdarkgreen Dec 19 '19 at 19:10
  • @29ax14 (Also, very minor note, $\phi(x)$ may have a certain complexity while the complexity of instances $\phi(\mathbf n)$ may be different, and vary with $n.$) – spaceisdarkgreen Dec 19 '19 at 19:16
  • @user21280 Yes I rescind my original statement as too strong... though I’m currently in the mood of avoiding that usage, I know for a fact I have used it that way before and in certain cases it can be useful. And there’s no reason to draw the line at sentences, other than what I’ve said before about its usefulness in this context. (Again this was brought on OP’s second to last paragraph... I’m not sure I’ve found occasion to think about a theory “proving $\Delta_1$ statements” though I’ve often thought about a theory proving a given concept is $\Delta_1$.) – spaceisdarkgreen Dec 19 '19 at 19:25
0

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

Nation
  • 1
  • 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. – Nation Nov 14 '22 at 16:31