I was trying to understand Godel's theorem from here Godel's First Incompleteness theorem. I still do not completely understand the theorem, but have a broad idea about it. As the link mentions Godel's first theorem addresses statements in Typographical Number Theory ( TNT ) which are true but unprovable using the axioms. The link assumes any statement about natural numbers can be written in TNT, such as "4 is a prime", "2 is the smallest prime number" etc. But it does not prove it in general. I am not even sure what qualifies as a statement about natural numbers. How do I put it mathematically what qualifies as a statement about natural numbers and how do I prove that every such statement can be written using TNT ?
Sorry if my question is vague or lacks correct terminology, I can improve it if suggested.

  • $\begingroup$ Note that TNT is Hofstadter's invention, not Gödel's; Gödel himself used an entirely different axiomatization. The article you're looking at is a little sketchy in spots, but in brief it can be said that we define the set of 'statements about numbers' to be the statements that can be expressed in one of these theories. (Peano Arithmetic is perhaps the most canonical). For instance, the (informal) statement that '5 is blue' is not a statement about numbers because there's no formal definition of the notion 'is blue' in such a theory. $\endgroup$ – Steven Stadnicki Nov 17 '15 at 0:25

There are lots of statements which are not expressible in the language of any specific theory, such as TST or Peano arithmetic (which I'm more familiar with). Any statement involving a symbol/word not in the language of the theory can't be directly expressed. Specific examples depend on the theory involved, but for a general kind of example, the sentence "$N$ is (the Godel number of) a sentence in the language $L$ which is true of the natural numbers" is never expressible in the language $L$ - this is Tarski's theorem on the undefinability of truth, and is a direct consequence of the diagonal lemma.

But we're not really interested in non-expressible statements most of the time. The surprise of Godel's theorem is that (for any reasonable system) there are expressible statements which are not decidable.

  • 1
    $\begingroup$ To tell specifically whether a sentence is expressible in TNT, you need a formal definition of TNT; often in expositions people will blackbox this bit, and just sweep the expressibility of every relevant sentence under the rug, but you do need to do this. $\endgroup$ – Noah Schweber Nov 17 '15 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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