# Relationship between complexity of a formula and complexity of an encoding of a proof of the formula

We classify sets of natural numbers based on the complexity of the formulas that describe them and this classification is intimately linked to Turing machines and oracles via Post's theorem.

Via encodings like Gödel numbering, we can encode formulas as well as rules of inference as natural numbers. A set of formulas is said to be recursively enumerable if there exists a Turing machine which will enumerate the set of numbers which encode all of the formulas.

Peano Arithmetic is a recursively axiomizable formal theory, which means it's set of axioms and theorems are recursively enumerable.

My question is this:

Suppose that PA proves a specific statement with complexity, say, $\Sigma^0_4$. Is the relationship between the set of natural numbers which encode this formula and the set of natural numbers represented by that formula such that:

The set of numbers which encode the statement are $\Sigma^0_1$ and the set of numbers represented by the formula could only be enumerated by a Turing machine with an oracle of Turing degree $0'''$

?

If this is true, is this always the relationship between the set of natural numbers which encode a statement, that they're $\Sigma^0_1$ regardless of what that statement is, and the statements themselves of arbitrarily complexity?

• If I understand you correctly: Yes, the set of natural numbers which encode a given formula is very simple, regardless of that formula's complexity. This is because the formula is literally just a string of symbols, and the number which encodes it is encoding those symbols, without regard for the formula's meaning. In most treatments the complexity of these encodings is even lower than $\Sigma_1$, in fact, because every formula has exactly one $n$ which encodes it. – realdonaldtrump Jun 26 '18 at 14:27
• Cross-posted: cs.stackexchange.com/q/93511/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Jun 26 '18 at 15:41
• Maybe you want to ask instead about the set of numbers which code formulas equivalent to the given formula? – Noah Schweber Jun 26 '18 at 15:52
• @D.W. If there is an official rule that crossposting isn't allowed (which does not seem to be the case, an accepted answer on a meta question is not an official rule and there are also multiple examples of them across many different SE sites that haven't been closed) then that's fine I won't do it. But the statement that crossposting isn't respecting people's time is a non sequitur. That's like saying that two people answering a single question is wasting someone's time; the design paradigm of stack exchange is not such that more than one answer is a waste of time. – user462082 Jun 26 '18 at 17:09
• @user462082, yes, there is an accepted policy on this. The policy is linked to in my comment. This is a community-led site, so a long-standing highly-upvoted answer on a meta often does basically amount to an official "rule"/policy. There are multiple reasons for this policy, and I'm not going to go into them in depth in a comment here. You are welcome to post on CS.SE meta to inquire about what the policy there is or to ask for the justification of it or to request that it be changed. See also cs.meta.stackexchange.com/q/1276/755. – D.W. Jun 26 '18 at 17:33

As you've written it, the question is trivial: any formula is encoded by exactly one number, so the complexity of the set of codes of a given formula is trivial regardless of the formula.

I suspect, however, that you mean (something closer to) the following:

Given a formula $\varphi(x)$ (single-variable for simplicity), let $EC(\varphi)$ be the set of codes of equivalents of $\varphi$ - that is, $EC(\varphi)=\{\ulcorner\psi\urcorner: \psi^\mathbb{N}=\varphi^\mathbb{N}\}$.

(Here "$\ulcorner$$\cdot$$\urcorner$" is the Godel number operation, and "$\chi^\mathbb{N}$" denotes $\{n\in\mathbb{N}: \mathbb{N}\models\chi(n)\}$; note that $\chi_1^\mathbb{N}=\chi_2^\mathbb{N}$ iff $\mathbb{N}\models\forall x(\chi_1(x)\iff\chi_2(x))$.)

Then we can ask how the complexity of $EC(\varphi)$ is related to the complexity of $\varphi$. This is a priori more meaningful.

However, it turns out that this is still trivial in a precise sense, and indeed it appears difficult to formulate your question in a way which will avoid such issues.

Let's start with a bit of optimism. The following observation suggests that there may be some interesting complexity relationship between $EC(\varphi)$ and $\varphi$:

• Fact $1$: $EC(\varphi)$ is at least as complicated as $\varphi^\mathbb{N}$. (Precisely, $\varphi^\mathbb{N}\le_m EC(\varphi)$.)

Proof: There is a computable function $h$ such that $h(n)$ is the Godel number of the formula $$\varphi_n(x): \quad\varphi(x)\vee x=\underline{n}$$ (where "$\underline{n}$" is the numeral corresponding to the natural number $n$). Now we have $h(n)\in EC(\varphi)\iff n\in\varphi^\mathbb{N}$. $\quad\Box$

However, it turns out this is trivial:

• Fact $2$: Regardless of what $\varphi$ is, $EC(\varphi)$ has the same complexity as the true first-order theory of arithmetic, $Th(\mathbb{N})$. (Precisely, $EC(\varphi)\equiv_m Th(\mathbb{N})$.)

Proof: $\psi$ is in $EC(\varphi)$ iff $\forall x(\varphi(x)\iff\psi(x))$ is in $Th(\mathbb{N})$; since the map sending the Godel number of $\psi$ to the Godel number of $\forall x(\varphi(x)\iff\psi(x))$ is computable, this shows $EC(\varphi)\le_m Th(\mathbb{N})$.

In the other direction, we have $\chi\in Th(\mathbb{N})$ iff the Godel number of the formula $\varphi(x)\wedge\chi$ is in $EC(\varphi)$. Since again the map sending the Godel number of $\chi$ to the Godel number of $\varphi(x)\wedge\chi$ is computable, this shows $Th(\mathbb{N})\le_m EC(\varphi)$. So we're done. $\quad\Box$

More generally, the same argument shows that the complexity of the set of Godel numbers of $\Sigma^0_n$ formulas equivalent to $\varphi$ depends only on $n$, not on $\varphi$. So it will be difficult to formulate your question in a nontrivial way.

• I don't think that I ever implied my question wasn't trivial or that there was more depth to it than what I was intending to ask. It may be trivial, and now that I see it explained fully I understand why it is, but I was unclear on the concepts and wanted to make sure that I did understand them correctly. Thing's aren't trivial to people who don't understand the context in which they appear. That's why I asked this on cs and here instead of theoretical cs or mathoverflow, because I knew the question was basic but I was confused. That being said, thank you for the detailed answer. – user462082 Jun 26 '18 at 18:21