Take the 2-minute tour ×

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?

share|improve this question
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. –  Dan Turetsky Jun 5 '13 at 23:48
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? –  mtg Jun 6 '13 at 0:15
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer


