6
$\begingroup$

The incompleteness theorem says that certain theories+deduction system contain at least one sentence (the Gödel sentence "$G$"), which can't be proven (in the system in which it holds).

(i) Is this theorem (incompleteness theorem) a statement formulated within the system of which the statement is about or is the theorem formulated in a meta language?

(ii) As soon as the theorem is established, is there readily the implication that "$\neg G$" is also not provable? And again, is this then a statement of the meta language?

(iii) In case that a mega language is crucial, what are the minimal requirements for it's logic?

(The thread here, "Is it always possible to decide if either a statement or its negation is provable in a given axiomatic system?" is related.)

For me this question is kind of a follow up to Aftermath of the incompletness theorem proof. I don't understand the notion of "A sentence $p$ is true in $\mathbb{N}$" if $p$ is neither an axiom nor provable by a deduction system. My ansatz was to establish "$G$ not provable","$\neg G$ not provable" while $G\lor\neg G$ is true, which would directly imply that one of them ($G$ or $\neg G$) is proven to be true and not provable in the investigated system. If the proposed conditions are always satisfied for the Gödel sentence and the meta language, then I could comprehend the formulation "it's true but unprovable", because "true" wouldn't come from outside.

  • 1
    On one level, it's Platonism – some people believe there is one "true" model of arithmetic, called $\mathbb{N}$. On another level, we're just thinking about provability in a bigger system. As I said before, don't read too much into the word "true".2012-08-16

2 Answers 2

4

To take your three questions in turn:

(i) The incompleteness theorem for theory $T$ is a theorem about what can't be proved in $T$. If $T$ is e.g. a pure theory of arithmetic, its language is about numbers, not about $T$-proofs. The theorem won't even be stateable in $T$'s language: rather is stated in e.g. mathematical English.

Of course, by the trick of Gödel coding we can produce in $T$ a sentence which codes up the claim that if $T$ is consistent then a Gödel sentence for $T$ is unprovable, to get $\mathsf{Con} \to \neg\mathsf{Prov(\overline{\ulcorner{G}_{\mathit{T}}\urcorner})}$. And that sentence will itself be provable in $T$ on very modest assumptions. So we might say that $T$ can itself prove the incompleteness theorem for $T$: but really that is rather careless talk. To repeat, if $T$ is a theory of arithmetic whose interpreted language is about numbers, then its theorems are strictly speaking about numbers and numerical properties, not about proofs.

(ii) No. There are consistent theories $T$ with a Gödel sentence $\mathsf{G}_T$ such that $T$ proves $\neg\mathsf{G}_T$. For example take $T$ to be the consistent but $\omega$-inconsistent theory you get by adding to PA the negation of a standard Gödel sentence for PA. (The unprovability of the negation of the Gödel sentence does indeed require we are dealing with an $\omega$-consistent theory.)

(iii) The proof of Gödel's theorem doesn't require excluded middle: it goes through intuitionistically. (It only involves the intuitionistically acceptable version of reductio.)

  • 1
    @NickKidman I suspect you need to read a textbook or two that gives a good presentation of Gödel's incompleteness theorems. There are plenty out there. For some recommendations see http://www.logicmatters.net/students/tyl/2013-06-10
4

There are two things to be aware of here.

The first one is that the Godel sentence is independent of the theory. It's specifically constructed so that neither G nor not G is a theorem.

The second one is that if one considers a particular model of the theory, then either G is true under that interpretation, or not G is true.

The "unprovable but true" version of Godel's incompleteness theorem only makes sense when the speaker is implicitly referring to a particular model -- usually the particular set of natural numbers that is implicitly part of the theory of formal logic.

  • 0
    I am also more familiar with the usage in which arithmetics with inconsistent proof predicates will prove $(\forall x)\operatorname{Pvbl}(x)$ (that's the definition of an inconsistent proof predicate) and thus will prove the negations of their own Goedel sentences, as Goedel sentences are constructed as a sort of fixed point for $\lnot \operatorname{Pvbl}$.2012-08-20