MATH3421 Logic and Computability gives an introduction to a subject which may be seen as arising from mathematicians' attempts early in the twentieth century to understand precisely what it is we do when we write a proof or perform a calculation. Therefore, the subject has close and important links with such philosophical problems as the truth (or not!) of mathematical statements and the relationship between mathematics and the real world.
The first section of the course comprises a review of topics on sets, functions and relations, which many students will have seen in first year, and some results on infinite, countable and uncountable sets, which may be new. We take a brief look at the logical construction of Euclid's geometry. The second major topic gives a brief introduction to the mathematical theories of computation and of languages. We study regular languages, the simplest class of languages normally regarded as "interesting", and deterministic finite automata, which can be viewed as computing devices with a fixed, finite amount of memory. Exploration of the connections between regular languages and automata leads us to the Pumping Lemma and the Myhill–Nerode Theorem.
We proceed to introduce the language of propositional calculus, which provides a basis for analysing simple statements and constructing formal proofs founded strictly upon explicitly stated axioms and rules of inference. We prove the compactness theorem for propositional calculus, and give some applications. Next we look at the predicate calculus, which extends the range of statements which we can discuss beyond those for which the propositional calculus suffices. We briefly treat truth in a model and formal proofs, then look at the application of the compactness theorem to non-standard analysis. The chapter concludes with a survey of Gödel's shattering incompleteness theorems from the 1930s.
In the final section we return to the study of computability, introducing Turing's model of computation, and also looking at recursive functions, recursive sets and recursively enumerable sets.
The notes are divided into five sections, corresponding to the five major parts of the course described in the previous paragraphs. They were written by David Angell, with some parts based on earlier work by various members of the School of Mathematics, University of New South Wales. The design, typesetting and production of the notes was carried out by David Angell from 1994 to 1996.