Limitations in Formal Systems and Languages


Master thesis no. 1999-04,
Department of Mathematics, Technical University of Denmark.

2000 AMS Classification: 03
Keywords: Cantor's diagonal argument, semantical paradoxes, Gödel's Incompleteness Theorem

102 pages.

Abstract

This thesis has two major aims. The first is to demonstrate the centrality of Cantor's diagonal argument in the proofs of the classical limitation results concerning formal languages and systems - the second is to generalize these results into a framework of more general languages and systems. The point of generalizing the classical limitation results is to prove that these results are in some way essential and not only results bound to languages or systems of a very restricted type. Our concept of formal language is defined such as to allow for instance sentences with direct self-reference and ``poetical sentences'' that are neither true nor false. The main result of the thesis is a version of Gödel's Incompleteness Theorem valid for these kind of languages equipped with a suitable notion of proof. Two smaller limitation results concerning formal languages are obtained by a transformation of the classical semantical paradoxes of Grelling and Epimenides into the framework of formal languages. In these transformations the close connection between the semantical paradoxes and the diagonal argument is revealed.