Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My question is of a logical nature and concerns what I perceive to be two different types of mathematical independence.

Suppose we have a (sufficiently strong) axiomatic theory $T$. Gödel's Incompleteness Theorems state that:

  1. $T$ is not a complete theory. That is, there is a sentence (expressible in the language of the theory) which is true, but not provable in the theory. In what follows, I will refer to such a sentence as a Gödel sentence and denote it by $G$.

  2. $T$ cannot prove its own consistency. That is, assuming that $T$ is consistent, $\not\vdash_T\mathrm{Con}(T)$.

For my question to make sense, I must lay out the following principle, which I take to be "self-evident" (by which I mean that I believe most people would endorse it):

'If one is committed to a theory $T$, then one is also committed to $\mathrm{Con}(T)$.'

In other words, suppose that I accept the axioms of $PA$ (for instance). That means that I am committed to $PA$, in the sense that I believe it to be true, and therefore consistent. As such, it would be incoherent for me to disbelieve $\mathrm{Con}(PA)$.

This situation gives rise to the following state of affairs:

  • On the one hand, there are statements which are independent from a theory $T$, but whose truth is nevertheless implied by $T$, even though $T$ cannot prove them. This is the paradigm of the First Gödel Theorem (cited above) applied to arithmetic: in the context of $PA$, it says that there is a Gödel sentence $G$ which is not provable in $PA$, but that if $PA$ is consistent, then $G$ must nevertheless be true. Thus, if one is committed to $PA$, one is committed to $\mathrm{Con}(PA)$ (by the above principle) and therefore one is committed to the truth of $G$.

  • On the other hand, there are statements which are independent from a theory $T$, and in addition, no judgment regarding their truth value may be inferred from $T$. This is the paradigm of Set Theory ($T=ZFC$) and the Continuum Hypothesis ($CH$). One's commitment to $ZFC$ does not imply anything about the truth of $CH$, since both $ZFC+CH$ and $ZFC+\neg CH$ are consistent. Note that this is different from the first case, in which $PA+\neg G$ is inconsistent.

In essence, I see a dichotomy between statements which are independent from a theory $T$ and also from $\mathrm{Con}(T)$, and those which are independent from $T$ but nevertheless implied by $\mathrm{Con}(T)$. I am tempted to say that there are two types of logical independence; is such a division valid, or would anyone care to contest it?

In case this is a very well-known issue, are there any other examples (aside from Gödel sentences) of statements which are independent from a theory but provable if one assumes consistency? In particular, I am wondering if there are any "natural" such questions. (Of course, the statement $\mathrm{Con}(T)$ is itself an example, albeit a trivial one.)

Thank you!

share|improve this question
    
I'm surprised this blog post didn't get mentioned. xorshammer.com/2009/03/23/… –  user18713 Oct 23 '11 at 1:32

2 Answers 2

up vote 12 down vote accepted

The division you see has to do with the level of conservativity of the theories in question. On the one hand, the theory ZFC + Con(ZFC) is not $\Pi^0_1$-conservative over ZFC since Con(ZFC) is a $\Pi^0_1$ sentence which is not provable from PA. On the other hand, CH is $\Pi^0_1$-conservative over ZFC since ZFC + CH and ZFC prove exactly the same arithmetical facts. Indeed, by the Shoenfield Absoluteness Theorem, ZFC and ZFC + CH prove exactly the same $\Sigma^1_2$ facts. In general, forcing arguments will not affect $\Sigma^1_2$ facts and so any statement whose independence is proved by means of forcing will be $\Sigma^1_2$-conservative over ZFC. By contrast, large cardinal hypotheses are not $\Pi^0_1$-conservative over ZFC.

An example of a natural statement that is independent of PA but nevertheless true is the Paris–Harrington Theorem, which is equivalent to the 1-consistency of PA. In other words, the statement is equivalent to the statement that every PA-provable $\Sigma^0_1$ sentence is true.

share|improve this answer
    
Thank you for your prompt answer! The Paris-Harrington Theorem really does seem like the example I was looking for. –  Alex Lupsasca Aug 11 '10 at 17:45

First, a minor correction to the end of the second bullet item in the question: $PA+\neg G$ is consistent (that's the same as saying that $PA$ doesn't prove $G$); what you presumably meant is that $PA+Con(PA)+\neg G$ is inconsistent.

Now concerning the actual question: What you've described is the beginning of a whole hierarchy of "commitments implicit in accepting a theory." Your principle, that anyone accepting a theory $T$ must also accept $Con(T)$, can be iterated. Having accepted PA, and therefore having accepted $Con(PA)$, I ought to also accept $Con(PA+Con(PA))$ and then $Con(PA+Con(PA+Con(PA)))$, etc. In fact, this process can even be iterated transfinitely. Ultimately, what I ought to accept (in this sense) will depend on my knowledge that certain orderings are well-orderings (so that iterating the "Con" process along those orderings is justified). Such iterations have been studied by Turing and (later) Feferman. If I remember correctly, if I'm willing to iterate along all computable well-orderings, this process will produce enough "Con" axioms to imply all true $\Pi^0_1$ statements about the natural numbers.

The philosophy behind your argument about being committed to $Con(T)$ seems to actually justify a stronger principle, namely that anyone who accepts $T$ should also accept the principle that anything provable in $T$ is true. Because of the undefinability of truth, this stronger principle should be formulated as a schema, called the reflection schema: $Prov_T(\lceil\phi\rceil)\to\phi$, where $Prov_T(\lceil\phi\rceil)$ formalizes, in terms of the G"odel number \lceil\phi\rceil, the statement that $\phi$ is provable in $T$. If I rememeber correctly, iteration of this reflection principle, along all computable well-orderings, suffices to prove all arithmetical truths. (That doesn't contradict G"odel's incompleteness theorems, because the notion of "all computable well-orderings" isn't computable nor even arithmetically definable.) Note, by the way, that $Con(T)$ is equivalent to the particular instance of the reflection principle where $\phi$ is a contradiction.

In light of all this, I'd say that your distinction between those statements that are independent of $T$ but provable in $T+Con(T)$ and those that are independent of $T+Con(T)$ is "valid" in the sense of being a well-defined mathematical distinction, but it is not "valid" in the sense of capturing the full import of your dictum that whoever accepts $T$ should accept $Con(T)$, because it does not take into account the possibility of iterating this dictum. In addition, it seems to me that the reflection principle more completely captures the intuition behind your dictum.

share|improve this answer
    
willing to iterate along all computable well-orderings ... imply all true Pi-0-1 statements - IIRC, this isn't true: you need more than the computable WOs to get such strong soundness results. I think we need to track down a reference to sort out these battling indistinct recollections! –  Charles Stewart Aug 11 '10 at 9:59
    
The relevant reference is Feferman's "Transfinite recursive progressions of axiomatic theories" [J. Symbolic Logic 27 259-316]. Shoenfield's review (MR0172792) confirms, in its second paragraph, what I wrote about $Pi^0_1$. But it also says I was wrong about the more general reflection principle. To get all truths, you need to iterate the schema "If every closed numerical instance of $\phi(x)$ is provable then $\forall x$ $\phi(x)$" through all recursive ordinals. (If you needed to go beyond the recursive ordinals, I'm not sure how you could express provability.) –  Andreas Blass Aug 11 '10 at 15:54
    
Thank you for this great answer! Francois's reply, which mentions the Paris-Harrington Theorem, directly answers my question and so I was compelled to choose it over yours. Nonetheless, I find your contribution much more informative: assuming the principle that " is provable implies " (which I am certainly inclined to believe) allows one to prove all the arithmetical truths! If I understand correctly, this is a very satisfying state of affairs :) –  Alex Lupsasca Aug 11 '10 at 17:50

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.