Foundations of Logic

The course presents basic facts which lie at the foundation of modern logic. First, we show that first-order logic itself is complete, in the sense that there is a simple system of axioms and rules (that we present) which derives all logical consequences of any given premises. Then we look at theories expressed in this language. After a glimpse of what one can say about models of such theories, we present Gödel's famous incompleteness theorems: in any axiomatic theory, which is free from contradiction and contains a bare minimum of arithmetic, there are true statements which cannot be proved in the theory. The methods used to show this lead to other important facts, such as Tarski's theorem on the undefinability of truth, and the fact that the freedom of contradiction of such a theory cannot be proved in the theory itself (the second incompleteness theorem). We discuss the philosophical import of these results, but our main focus is on how they are established. Finally, we show that first-order logic is undecidable: there is no effective method (computer program) which can decide, for any premises and conclusion, if the conclusion follows logically from the premises or not.