# What is it wrong in this argument about the interpretability hierarchy?

This is a question that I fully reedited to make it more precise. Many thanks to the people that answered the previous version to get this distilled one.

Background: (from http://plato.stanford.edu/entries/independence-large-cardinals/)

Definitions:

1) Let T1 and T2 be recursively enumerable axiom systems. We say that T1 is interpretable in T2 (T1 ≤ T2) when, roughly speaking, there is a translation τ from the language of T1 to the language of T2 such that, for each sentence φ of the language of T1, if T1⊢φ then T2⊢τ(φ). We shall write T1 < T2 when T1≤ T2 and T2≰ T1 and we shall write T1≡ T2 when both T1≤ T2 and T2≤ T1. In the latter case, T1 and T2 are said to be mutually interpretable.

In terms of interpretability there are three possible ways in which a statement φ can be independent of a theory T, two of them are:

2)SINGLE JUMP. Only one of φ or ¬φ leads to a jump in strength, that is, T+φ>T and T+¬φ ≡ T (or likewise with φ and ¬φ interchanged)

3)DOUBLE JUMP. Both φ and ¬φ lead to a jump in strength, that is, T+φ>T and T+¬φ>T.

Argument: Let us make from definition (1): T1 be PA, φ be the Paris–Harrington theorem (known to be independent of PA), T2=T1+φ and T3=T1+¬φ . Also, let the translation τ be the identity (so τ(φ)=φ) . Thus, for every φ' in T1, if T1⊢φ' then T2⊢φ'. But there is a φ'=φ such that T2⊢φ but T1 does not prove φ. Thus T1 < T2 . A similar argument can be done using T3 and φ'= ¬φ. Thus T1 < T3 . Then φ is a case of double jump (definition 3).

Problem: Every body agrees that φ is actually a case of single jump (definition 2)!!

Question: Did I wrongly interpreted any of the definitions? Did I introduced a fallacious argument?

Important note: Please try to limit your answer to the specific definitions and argument made above. That is: Did I wrongly interpreted any of the definitions? or, introduced a fallacious argument?
Please keep it simple and try not to answer through a different path, such as by introducing unnecessary (?) concepts (such as model theory, or set theoretical arguments in general), nor self-referential statements such as Con(PA) (or ¬Con(PA) ), which cause me big trouble; and that I will not be able to grasp in the foreseeable future. Thanks!

-
I changed the initial link , which was wrong. – Wolphram jonny Nov 5 '12 at 0:30

To answer the more direct, edited version of the question: Yes, your argument is fallacious, just by a standard quantification error.

The definition says T1 is interpretable in T2 (T1$\leq$T2) if there exists a translation $\tau$ with a certain property.

Now you define T1, T2 = T1 + $\phi$, T3 = T1 + $\lnot\phi$.

To show that T1$\leq$T2, you need to exhibit a translation $\tau$ with the property. You've done this correctly by taking $\tau$ to be the identity. The same argument shows that T1$\leq$T3.

But now you want to show that the inequalities is strict, that is, that T2 $\not\leq$ T1 and T3 $\not\leq$ T1. To do this, you need to show that no such translation can be found. That is, the negation of $\exists \tau\,P(\tau)$ is $\forall\tau\,\lnot P(\tau)$, for any translation you pick, it does not have the desired property.

What you've done in your argument is show that one particular $\tau$, the identity, fails to have the desired property.

-
Thanks Alex! I guess I do not deserve to use this site anymore. – Wolphram jonny Nov 9 '12 at 0:04
What makes you say that? I think your question is a reasonable one - it can be very hard to get your head wrapped around things like interpretability and consistency strength for the first time. – Alex Kruckman Nov 9 '12 at 0:06
Yes, but my confusion in the end was due to a much more elementary mistake (this means, I should have been able to find it by myself. But it was not a matter of thinking a little more about it. I would have never find it by myself!. The site says that I have to wait 4 hours to give you your well deserved bounty. Just in case you wonder why you didn't received the points yet. – Wolphram jonny Nov 9 '12 at 0:20
Bonus question: τ(φ) has to be invertible, right? Otherwise for any T1 and T2 you could show T1 ≤ T2 , by using τ(φ)=P ∨¬P (for any φ)? – Wolphram jonny Nov 9 '12 at 19:18

The idea for showing Con(T)$\leftrightarrow$Con(T+$\phi$)( i.e. $T+\phi\equiv T$), is to show that if there is a model of T, then there is also a model of T$+\phi$. Talking about ZFC and CH, Godel showed that any model of ZFC will contain an inner-model called L which satisfies CH, so Con(ZFC)$\rightarrow Con(ZFC+CH)$, and the converse is trivial. Similarly, Cohen showed that any model of ZFC can be extended (using forcing) into a model of $\neg CH$, so Con(ZFC)$\rightarrow Con(ZFC+\neg CH)$. The situation for PA is similar.

-
Let us forget about set theory, I am not still comfortable with inner models and forcing. Let us limit the answer to PA: Both PA+ϕ and PA+notϕ have models (one of them the standard N and the other a non-standard model). So I do not understand why one is stronger and the other is not. Also, is it wrong to state that "stronger" is equivalent to "proves more theorems"? – Wolphram jonny Nov 5 '12 at 2:42

There are two measures of the "strength of a theory" going on here. I'll try to explain them simply.

1: $T \geq T'$ means $T$ implies $T'$. That is, $T$ proves all of the axioms of $T'$ and possibly more. This is what you are referring to when you say "T proves more theorems." Given a consistent theory $T$ and a sentence $\phi$, there are two possibilities:

a. $\phi$ is not independent from $T$. Then either $T$ proves $\phi$ or $T$ proves $\lnot\phi$, let's say that $T$ proves $\phi$. Then $T + \phi \equiv T$: it's easy to see that both sides imply the other. But $T + \lnot\phi > T$ trivially: $T + \lnot\phi$ is inconsistent, and therefore proves all sentences.

b. $\phi$ is independent from $T$. Then $T + \phi > T$ and $T + \lnot\phi > T$, since $T$ does not prove $\phi$ or $\lnot\phi$.

2: $T \geq T'$ means that (relative so some background theory, like $\text{PA}$), $\text{Con}(T)$ implies $\text{Con}(T')$, i.e., if $T$ is consistent, then so is $T'$. This is more or less the relation that the article you link to is discussing. Note that this relation doesn't compare which theorems $T$ and $T'$ can prove, just the strengths of the assertions that they are consistent. By the Completeness Theorem for first-order logic, a theory is consistent if and only if it has a model, so one way to demonstrate that $T \geq T'$ is prove that given a model of $T$, we can obtain a model of $T'$.

Now given a sentence $\phi$ and a theory $T$, we have the three cases you list in your question.

It's important to keep in mind that this is all relative to a background theory. Your preference seems to be to use $PA$. In a comment, you say "Both $PA + \phi$ and $PA + \lnot\phi$ have models". But this is not provable from $PA$! By the second incompleteness theorem, $PA$ cannot prove that $PA$ has a model.

-
You state that case 2 is different than 1 because " ...this relation doesn't compare which theorems T and T′ can prove, just the strengths of the assertions that they are consistent". But is this true? T+Con(T) can prove Con(T), but T cannot. Similarly, T+¬Con(T) can prove ¬Con(T), but T cannot. So, why is not case 2 the same as 1b? The example of Con(T) is self-referential, but there are "natural" examples such as the "strengthened finite Ramsey theorem", which is not provable in PA, but true in N and untrue in some non-standard N. Am I wrong? – Wolphram jonny Nov 5 '12 at 18:27
Also, I am not sure to understand why is it relevant that "PA cannot prove that PA has a model" (I talked about models just to get a clarification from the first answer) – Wolphram jonny Nov 5 '12 at 18:55
@julianfernandez You're right that the sentence Con(PA) falls into case 1b, if by "stronger" we mean "proves more theorems", because Con(PA) is independent from PA. But part 2 of my answer is explaining a totally different meaning of "stronger", which compares the strengths of the sentences Con(T) and Con(T'). – Alex Kruckman Nov 5 '12 at 20:50
So, it is still not clear to me if the following definition: "We say that T1 is interpretable in T2 (T1 ≤ T2) when, roughly speaking, there is a translation τ from the language of T1 to the language of T2 such that, for each sentence φ of the language of T1, if T1⊢φ then T2⊢τ(φ).", correspond to case 1 or case 2?(I mean, to which of my two different definitions of "stronger"? – Wolphram jonny Nov 6 '12 at 18:02
Notice that Con(T1) is the statement that T1 does not prove the sentence "false" or $P\land\lnot P$, if you prefer. Suppose a provability-preserving translation exists, i.e. T1$\leq$ T2. Then if T1 proves false, then T2 proves false. So if T2 is consistent, then T1 is consistent, i.e. T2 $\geq$ T1 in terms of consistency strength. I chose to focus on consistency strength instead of full interpretability in my answer because I think it's easier to understand. – Alex Kruckman Nov 6 '12 at 18:12