A supplement to "The Mathematics of Logic"

[NOTE: These web pages are very much under construction. Much more is planned in the next 4 months or so, and some pages that are here need review and corrections or improvement. Please contact me if you have any special requests. Richard Kaye, October 2009.]

Front matter

Preface. Introductory note, copyright notice and main home page for all these pages.
Contents. This page.
Installation. Notes on installing or configuring a browser with MathML to view these pages.
The contents pages of the published book. PDF taken from the published book, for people who haven't bought it yet!
The preface from the published book. indicating the main aims of the book and how to read it.
A (very short!) list of errata for the published book.
The prfblock.sty LaTeX styles for typesetting proofs with the vertical lines as used in the book.

Answers to selected exercises in the book

In due course I hope to have web pages containing answers or hints to all the exercises in the book. If the one you are looking for is not here yet please be patient.

Additional exercises to test your knowledge and understanding

The following exercises test your knowledge and understanding of the marerial in the book further. They may be suitable for assessments for undergraduate courses, etc. Answers will not normally be provided on these web pages. They may not follow the order of the book exactly.

Exercises and examples on simple formal systems. Systems similar to those in Chapter 3. You need to understand formal derivations and inductions on derivations.
Exercises and examples on completeness and soundness for propositional logic. A complete baby propositional logic based on the arrow relation and the propositional constant bottom.
Exercises and examples on the Sheffer stroke. A system for propositional logic based on a single propositional connective.
Exercises and examples on first-order languages. Introductory exercises on first-order languages.

Supplementary material on propositional and first order logic

This lists some supplementary material for propositional and first order logic, directly related to the book and available here as additional reading, some of it advanced. In particular this includes the proof of the Soundness Theorem, which is quite technical, especially when done properly. Just like the simpler examples of Soundness in the book, it is by induction on the length of proof. This sequence of web pages takes the reader through the material. Along the way you will find precise definitions of truth in an L-structure M and the precise definitions of substitution and the rules for first order logic. It is suitable for readers who want the full details and who have mastered most of The Mathematics of Logic.

More on the König-lemma system. More on the 0,1-System of Chapter 3 of The Mathematics of Logic, including a way to avoid the use of Zorn's lemma and an alternative way of deriving König's lemma from the completeness theorem.
Another 0-1 system. Some tricky variations on the 0-1 system to think about
Between order and logic. Systems for lattices and theories of and and or, intermediate between the systems of chapters 4 and 6 of The Mathematics of Logic.
Different propositional languages. Comparison of different languages and expressive completeness of propositional logical languages.
Boolean terms and unique readability. The formal definition of the set of boolean terms over a set X and the unique readability theorem for these.
Proofs as structured lists and proof trees. More on how to write a formal proof on a page.
Free variables. The definition of free occurences of variables in a formula.
Substitution in first-order language. The definition of valid substitution of terms for variables.
Substitution and the rules for first order logic. The rules of first order logic revisited and made precise using the notion of substitution.
The definition of truth. The definition of semantics for first order logic.
Sematic aspects of substitution. Some preliminary results towards the soundness theorem.
The proof of soundness. The proof of the Soundness Theorem for first order logic.

The Gödel incompleteness theorems

Possibly the most celebrated results in logic, the incompleteness theorems show there are intrinsic limitations to the idea of mechanised proof. (In other words, mathematicians are not and never will be redundant!) The pages here sketch the details and the links with computability.

Overview of the incompleteness theorems. Statements of the main theorems, and definitions of the key terms.
Discretely ordered rings. A minimal algebraic theory of arithmetic.
Exercises on discretely ordered rings.
Exercises on discretely ordered rings - answers.
Computability and the language of arithmetic. Connections between expressibility in the first order language of arithmetic and computability theory.
Representability and diagonalisation. Representing functions and sets in a theory; the Diagonalisation lemma.
Gödel's first incompleteness theorem. The first application of Diagonalisation to incompleteness.
The Gödel-Rosser incompleteness theorem. Rosser's trick to improve Gödel's first incompleteness theorem.
Gödel's second incompleteness theorem. The non-provability of consistency.
Interpretations. Interpretations of arithmetic in another theory, and the Gödel theorems for these theories.
Hilbert's Programme.

Axiomatic set theory

Axiomatic set theory is a first order theory into which all normal mathematics embeds. It formalises many arguments presented in The Mathematics of Logic including results on Zorn's Lemma and cardinal numbers.

Introduction to axiomatic set theory. Basic axioms
The cumulative hierachy of sets.
The Axiom of Foundation.
The Axiom of Infinity.
The Axiom Scheme of Replacement with an application to transitive closure.
Epsilon induction and recursion.
Introduction to ordinals.
Induction and recursion on ordinals.
Ordinal arithmetic.
The cumulative hierarchy and rank.
The Axiom of Choice.
Cardinals.
König's inequality.
Cofinality and inaccessibles.

Some model theory

These pages build on Chapters 10 and 11 of The Mathematics of Logic. The goal is to give more examples and motivate the ideas of independence behind Morley's theorem.

Vector spaces. Some properties of Vector Spaces over a fixed field as examples of a theory and its models.
Embeddings. An exercise sheet on embeddings of structures, including the preservation theorem for embeddings.
The Ryll-Nardzewski theorem. An exercise sheet applying the omitting types theorem to give a characterisation of aleph-zero categoricity.
The theory of a successor function. Including an introduction to quantifier elimination.