Let$\:$ $T=\{\varphi \in \Pi_1: PA+Con(PA) \vdash \varphi\:\:and\:\: PA\nvdash \varphi \}$. $\:$By the facts presented here Are undecidable consequences of Con recursively enumerable? by Andreas Blass and Emil Jerabek, we know that:

$(1)$ $T$ is $\Pi_1$-hard.

However it seems we can also prove that

$(2)$ $Cn(PA+Con(PA)) = Cn(PA+T)$

Let $\varphi$ be such that $PA+Con(PA) \models \varphi$. Obviously $Con(PA) \in T$, therefore trivially $PA+T \models \varphi$.

In the other direction, let $\varphi$ be such that $PA+T \models \varphi$. Since this is a first-order theory, by completeness and compactness we can infer that in the proof of $\varphi$ from $PA+T$ we use finitely many formulae, namely: $\phi_1, \phi_2, \dots \phi_n$ . All of them either belong to $PA$ or belong to $T$ or can be inferred from $PA+T$. In particular they are implied by $PA+Con(PA)$. If so, they can be used in the proof of $\varphi$ form $PA+Con(PA)$, so $PA+Con(PA) \models \varphi$.

But from the work of Jeroslow http://www.jstor.org/discover/10.2307/30226121?uid=3738840&uid=2&uid=4&sid=21102368601827 (Corollary 4) we find out that:

$(3)$ $Cn(PA+\{\varphi \in \Pi_1: \mathbb{N} \models \varphi \})$ is not $\Delta_2$

Since $(1)$ and due to the fact that the set above (I mean: $\Pi_1 \cap Th(\mathbb{N})$) has got its own truth definition and is $\Pi_1$ we infer that it is reducible to $T$.

So it seems that $Cn(PA+T)$ should also be "hard" and "not learnable" (in the sense of not being $\Delta_2$ ).

However we also know that $Cn(PA+Con(PA))$ is $\Sigma_1$. Since $(2)$ however $Cn(PA+T)$ is the same set of formulae.

So my question is: did I make any mistake in the reasoning above and one of $(1)$, $(2)$, $(3)$ is false or it can be the case that when we close some "hard" set up logical consequence, we can get an "easier" set. If so, the question is: how come?

  • $\begingroup$ I don't see any mistakes. A good chunk of the complexity of T comes from excluding certain sentences; specifically, those sentences provable in PA. But adding PA and then closing under consequence restores those sentences. That's why the complexity decreases. $\endgroup$ Jun 5 '13 at 23:48
  • $\begingroup$ Thanks. You're right, but let's look at the theory I mentioned: PA+(Set of true Pi_1-sentences) which closed under consequence gives us nonlearnable theory. I don't "see", how - having a computable reduction of Set of true Pi_1-sentences to the set T- we obtain theories with different complexities? $\endgroup$
    – mtg
    Jun 6 '13 at 0:15

The $\Pi_1$-hardness of $T$ comes from the clause $PA\not\vdash\varphi$. But when you consider $Cn(PA+T)$ its influence vanishes.

As $$T\subset Cn(PA+Con(PA))$$ we have $$Cn(PA+T)\subseteq Cn(PA+Cn(PA+Con(PA)))=Cn(PA+Con(PA)).$$ On the other hand $Con(PA)\in T$ therefore $Cn(PA+Con(PA))\subseteq Cn(PA+T)$.

Thus we have the equality $Cn(PA+T) = Cn(PA+Con(PA))$ indeed.

This also does not contradict Jeroslow's results as in $PA+\Pi_1(\mathbb{N})$ there are all $Con(X)$ (not just $Con(PA)$) and which is a sourse of complexity of this theory.

It is not very suprising that Cn operator can decrease the complexity of a set of sentences - you can always add a negation of a sentence of any given set to obtain an inconsistent theory i.e. primitive recursive. But it is a nice example how it can decrease it to something higher than just PR.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.