1
$\begingroup$

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!

  • 0
    I changed the initial link , which was wrong.2012-11-05

3 Answers 3

1

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.

  • 0
    "how can T2 be consistent if it proves 'false'?" It can't! I said "Con(T) is the statement that T does not prove the sentence 'false'". That is, a theory is consistent exactly when it doesn't prove 'false'.2012-11-08
2

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.

  • 0
    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"?2012-11-05
2

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.

  • 0
    Bonus question: τ(φ) has to be invertible, right? Otherwise for any T1 and T2 you could show T1 ≤ T2 , by using τ(φ)=P ∨¬P (for any φ)?2012-11-09