Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
I changed the initial link , which was wrong. –  julian fernandez Nov 5 '12 at 0:30
add comment

3 Answers

up vote 2 down vote accepted
+50

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.

share|improve this answer
    
Thanks Alex! I guess I do not deserve to use this site anymore. –  julian fernandez 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. –  julian fernandez 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 φ)? –  julian fernandez Nov 9 '12 at 19:18
add comment

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.

share|improve this answer
    
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"? –  julian fernandez Nov 5 '12 at 2:42
add comment

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.

share|improve this answer
    
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? –  julian fernandez 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) –  julian fernandez 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"? –  julian fernandez 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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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