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.

In Goedel incompleteness theorem is Goedel term both true and unproveable, or just unproveable and truth neutral?

Can we add Goedel term to the theory as axiom and get new theory?

Can we add Goedel term negation to the theory and get a new theory? What can be said abot this last one theory: will it be inconsistent but this inconsistency will never manifestate?

share|improve this question
1  
I think, by a 'Goedel term' $\phi$ you mean independent from the axiom system, meaning that extending that either by $\phi$ or by $\lnot\phi$ it will stay consistent. –  Berci Jan 25 '13 at 10:59
    
@Berci: but it is also important to note that extending by $\not \phi$ produces a theory that is not sound since we already know that $\phi$ is true (semantically). –  Marek Jan 25 '13 at 11:56

2 Answers 2

I am interpreting your question as being about the usual Gödel sentence $\theta$ which is interpreted as saying "there is no proof of $\theta$ from $\text{PA}$," or perhaps more formally as "$\neg ( \exists n ) ( \text{Proof}(n,\ulcorner \theta \urcorner) )$," where $\text{Proof}(x,y)$ is the predicate asserting that $x$ codes a proof (from $\text{PA}$) of the sentence coded by $y$. Note that $\theta$ has the property that if $\text{PA}$ is ($\omega$-)consistent, then $\text{PA} \not\vdash \theta$ and $\text{PA} \not\vdash \neg \theta$.

(As a disclaimer of sorts, whenever I speak of "proof" (in English) below, I mean a "proof from $\text{PA}$.")

In a certain sense, $\theta$ is neither of the options you list... at least not without some extra assumptions. As $\text{PA}$ is either consistent or inconsistent, let's look at these cases separately:

  • If $\text{PA}$ is consistent (which it is probably safe to say most mathematicians believe), then as $\text{PA} \not\vdash \theta$ it follows that $\theta$ speaks the truth about itself (as there is no proof of $\theta$ from $\text{PA}$ no natural number can encode a proof of $\theta$ from $\text{PA}$).
  • If $\text{PA}$ is inconsistent, then $\text{PA}$ proves everything, and in particular $\text{PA} \vdash \theta$, and so the assertion that "$\theta$ has no proof in $\text{PA}$" is false, i.e., $\theta$ is false. (We can find a proof of $\theta$ from $\text{PA}$, and convert this proof into a number witnessing $( \mathbb{N} , ... ) \models \neg \theta$.)

To summarise: if $\text{PA}$ is consistent, then $\theta$ is an unprovable sentence which is true; if $\text{PA}$ is inconsistent, then $\theta$ is a provable sentence which is false.

The first case is the interesting one for the remainder of your questions. (If $\text{PA}$ is inconsistent, then so are $\text{PA} + \theta$ and $\text{PA} + \neg \theta$.) Recall that if $T$ is any theory and $\phi$ is any sentence, then $T + \phi$ is consistent iff $T \not\vdash \neg \phi$. So if $\text{PA}$ is consistent we have both $\text{PA} \not\vdash \theta$ and $\text{PA} \not\vdash \neg\theta$, and so both $\text{PA} + \neg \theta$ and $\text{PA} + \theta$ are consistent.


Perhaps the more interesting sentence regarding the second and third questions is $\text{Con} ( \text{PA} )$ which expresses the consistency of $\text{PA}$; something to the effect of $\neg ( \exists n ) ( \text{Proof} ( n , \ulcorner 0 = 0 \wedge \neg 0 = 0 \urcorner )$. This is another sentence known to be independent of $\text{PA}$, provided that $\text{PA}$ is consistent. Following similar reasoning to the above, if $\text{PA}$ is consistent, then $\text{Con} ( \text{PA} )$ is a true (unprovable) sentence, and if $\text{PA}$ is inconsistent, then $\text{Con} ( \text{PA} )$ is a false (provable) sentence. Again, in the former case both $\text{Con} ( \text{PA} )$ and $\neg \text{Con} ( \text{PA} )$ may be appended to $\text{PA}$ to yield a consistent theory.

Looking at the consistency of $\text{PA} + \neg \text{Con} ( \text{PA} )$, recall that this just means, via Gödel's Completeness Theorem, that it has some model $\mathcal{M}$. As $\mathcal{M} \models \neg \text{Con} ( \text{PA} )$, then there is some $a \in \mathcal{M}$ such that $\mathcal{M} \models \text{Proof} ( a , \ulcorner 0=0 \wedge \neg 0=0 \urcorner )$, i.e., $\mathcal{M}$ "thinks" that $a$ codes a proof of $0=0 \wedge \neg 0=0$. However this $a$ will not correspond to any real natural number, so we cannot translate this object into a real proof of $0=0 \wedge \neg 0=0$. ($\mathcal{M}$ will be a nonstandard model of $\text{PA}$, and will contain objects which you can think of as "infinitely big natural numbers;" $a$ will be one of these.)

share|improve this answer
    
You say "If $\text{PA}$ is consistent ... it followes that $\theta$ speaks the truth about itself" and "If $\text{PA}$ is consistent ... then $\text{PA}+\neg \theta$ is consistent". Is the following false? "If $\text{PA}+\neg \theta$ is consistent it followes that $\theta$ speaks the truth about itself". I ask because if this is not the case, then it seems the expression "speaks the truth about itself" is pretty meaningless. –  NikolajK Jan 25 '13 at 12:17
    
@NickKidman: I am a bit confused about exactly what you are asking, but perhaps this clears up something. Note that in all of these matters we give special preference to the system of "real" natural numbers $\mathcal N=(\mathbb N,\ldots)$, and when we mention "truth" it is with respect to this system. Now if $\text{PA}$ is consistent, then $\mathcal N\models\theta$ (no real natural number codes a proof of $\theta$), and so while $\text{PA}+\neg\theta$ is consistent, the system $\mathcal N$ cannot be a model of it. As in my very last paragraph models of this system will be nonstandard. –  Arthur Fischer Jan 25 '13 at 13:16
    
Mhm, okay I get an idea of the argumentation, although I feel thei "real N" thing is a little fuzzy, as I don't know how to know when I got the real one. –  NikolajK Jan 25 '13 at 13:54
    
@NickKidman: If you want to talk about "truth" you have to talk about "truth" within a model, so without some model asking about the "truth" of the Gödel sentence $\theta$ is meaningless. Interpreted in second-order logic the Peano axioms are actually categorical, and so they pick out an (up to isomorphism) unique model, which we can call the real natural numbers. [cont...] –  Arthur Fischer Jan 25 '13 at 14:46
    
[...inued] But if you find the existence of such a model is troubling, note that the details of the proof of the Incompleteness Theorem can be made purely syntactic, without appealing to semantic objects like models or $\mathcal N$. (See, e.g., this MathOverflow question and its answers). –  Arthur Fischer Jan 25 '13 at 14:46

I am not an expert on these matters, but I think I can answer all of your questions, so here goes.

  1. We assume the theory $T$ is strong enough to prove arithmetical truths; the technical qualifications are not that important here. The Goedel term $G$ for a theory $T$ informally states that '$G$ cannot be proved within $T$'. If $T$ is consistent (which we assume, otherwise $T$ would not be very interesting) then $T$ cannot prove $G$ (we'd get a contradiction). Therefore the term $G$ is actually true $-$ it really can't be proved within $T$.

  2. We can add $G$ to $T$ as an axiom to obtain new theory $T'$. There is no problem doing this. We knew $G$ was true, so we are just enlarging $T$, so that it its more powerful and can prove more true statements about the world. $T'$ can now prove $G$ (trivially) but it is still not complete since Goedel's theorem produces a new true term $G'$ that $T'$ can't prove.

  3. We can add $\neg G$ to $T$ as an axiom to obtain new theory $T'$. This new theory will still be consistent if $T$ was because $T$ itself can't prove $G$ and obviously $\lnot G$ won't make proving $G$ any easier. Nevertheless, we know that $G$ was true. Therefore this new theory $T'$ is not sound $-$ it is proving theorems that are not true.

share|improve this answer
    
What does "not sound" mean? –  Suzan Cioc Jan 25 '13 at 12:27
    
@Suzan: in logic you have two sides: syntactic and semantic. Syntactic is what you can prove formally, while semantic is what is really true (in some model). Ideal theory for a given model should be both sound (you can only prove syntactically what is true semantically) and complete (you can prove syntactically everything that is true semantically). So by adding $\neg G$ you obtain a theory that is not sound anymore (relative to the model for $T$ you were working with previously). –  Marek Jan 25 '13 at 13:22

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.