0

For example Godel's Incompleteness Theorem says "Some statement in $Th(\mathbb{N})$ has no proof".

Consider sentence "This sentence is not provable". We can encode this sentence in $Th(\mathbb{N})$.

Thus, "This sentence is not provable" $ \in Th(\mathbb{N})$. But if this sentence is TRUE then it is NOT provable.

$\therefore$ we have some true statements in $Th(\mathbb{N})$ that we cannot prove.

Here I do NOT understand what it means "We can encode 'This sentence is not provable' in $Th(\mathbb{N})$"

How can we encode some sentence in Natural Numbers? I am totally lost here.

Another idea I heard that relates to the same problem is: "Given $M$ and $x$, we want to construct a sentence $Y$ in the language of number theory that says '$M$ does not halt on $x$'. This will be possible because the language of number theory is strong enough to talk about Turing Machines and whether they halt or not".

How it is even possible to talk about Turing Machines in the Theory of Naural Numbers? I appreciate if you can help!

Thank you

YanyongXu
  • 81

1 Answers1

0

Suppose I have some correspondence of letters and symbols with natural numbers (something like $"a"=1$, $"b"=2$, ..., " "$=27$, ..., $"\wedge"=235$, $"\implies"=413$, &c. (and since we use only finitely many symbols, I have enough natural numbers to do so).

Uniqueness of prime factorisation means that I can then produce a unique natural number corresponding to each sentence of finite length, by raising the $n$th prime to the number corresponding to the $n$th character in the sentence (e.g. the natural corresponding to "ab" could be $2^13^2=6$). This construction is often called the statement's Gödel number.

The idea of Turing machines here is that you give the Turing machine some statement's Gödel number, and it attempts to prove the corresponding statement. The statement is decidable if the Turing Machine will halt on it. It turns out that the decidability of a statement is not predictable by a Turing machine in finite time, IIRC.

Chappers
  • 67,606
  • I am not fully clear on "TM attempts to prove the corresponding statement". Like what does it mean? I am also not sure what it means for a statement to be decidable. I know language can be decidable if we have a decider machine s.t. it returns TRUE if input $\in$ language or FALSE if input $\notin$ language. But the notion of statement to be decidable confuses me. – YanyongXu Sep 15 '15 at 23:26