MATH3400 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. We then 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.
The course continues with 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. We conclude with a section on computability, introducing Turing's model of computation, and also looking at recursive functions, recursive sets and recursively enumerable sets.
The notes are divided into four sections, corresponding to the four 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.
The lecture notes are in the form of PostScript files. You will need Ghostview to access them. If you are a student at UNSW and have an account on sigma, Ghostview is available on your account. You can then obtain the notes just by clicking below. Brief information on the use of Ghostview can be found here.